TaprootBuilder Class Reference

Utility class to construct Taproot outputs from internal key and script tree. More...

#include <standard.h>

Collaboration diagram for TaprootBuilder:

Classes
struct	LeafInfo
	Information about a tracked leaf in the Merkle tree. More...
struct	NodeInfo
	Information associated with a node in the Merkle tree. More...

Public Member Functions
TaprootBuilder &	Add (int depth, Span< const unsigned char > script, int leaf_version, bool track=true)
	Add a new script at a certain depth in the tree. More...
TaprootBuilder &	AddOmitted (int depth, const uint256 &hash)
	Like Add(), but for a Merkle node with a given hash to the tree. More...
TaprootBuilder &	Finalize (const XOnlyPubKey &internal_key)
	Finalize the construction. More...
bool	IsValid () const
	Return true if so far all input was valid. More...
bool	IsComplete () const
	Return whether there were either no leaves, or the leaves form a Huffman tree. More...
WitnessV1Taproot	GetOutput ()
	Compute scriptPubKey (after Finalize()). More...
TaprootSpendData	GetSpendData () const
	Compute spending data (after Finalize()). More...
std::vector< std::tuple< uint8_t, uint8_t, std::vector< unsigned char > > >	GetTreeTuples () const
	Returns a vector of tuples representing the depth, leaf version, and script. More...
bool	HasScripts () const
	Returns true if there are any tapscripts. More...

Static Public Member Functions
static bool	ValidDepths (const std::vector< int > &depths)
	Check if a list of depths is legal (will lead to IsComplete()). More...

Private Member Functions
void	Insert (NodeInfo &&node, int depth)
	Insert information about a node at a certain depth, and propagate information up. More...

Static Private Member Functions
static NodeInfo	Combine (NodeInfo &&a, NodeInfo &&b)
	Combine information about a parent Merkle tree node from its child nodes. More...

Private Attributes
bool	m_valid = true
	Whether the builder is in a valid state so far. More...
std::vector< std::optional< NodeInfo > >	m_branch
	The current state of the builder. More...
XOnlyPubKey	m_internal_key
	The internal key, set when finalizing. More...
XOnlyPubKey	m_output_key
	The output key, computed when finalizing. More...
bool	m_parity
	The tweak parity, computed when finalizing. More...

Detailed Description

Utility class to construct Taproot outputs from internal key and script tree.

Definition at line 226 of file standard.h.

Member Function Documentation

Add()

TaprootBuilder & TaprootBuilder::Add	(	int	depth,
		Span< const unsigned char >	script,
		int	leaf_version,
		bool	track = true
	)

Add a new script at a certain depth in the tree.

Add() operations must be called in depth-first traversal order of binary tree. If track is true, it will be included in the GetSpendData() output.

Definition at line 441 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

AddOmitted()

TaprootBuilder & TaprootBuilder::AddOmitted	(	int	depth,
		const uint256 &	hash
	)

Like Add(), but for a Merkle node with a given hash to the tree.

Definition at line 454 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Combine()

TaprootBuilder::NodeInfo TaprootBuilder::Combine ( NodeInfo &&  a, NodeInfo &&  b  )

staticprivate

Combine information about a parent Merkle tree node from its child nodes.

Definition at line 360 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Finalize()

TaprootBuilder & TaprootBuilder::Finalize

(

const XOnlyPubKey &

internal_key

)

Finalize the construction.

Can only be called when IsComplete() is true. internal_key.IsFullyValid() must be true.

Definition at line 464 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

GetOutput()

WitnessV1Taproot TaprootBuilder::GetOutput

(

)

Compute scriptPubKey (after Finalize()).

Definition at line 475 of file standard.cpp.

Here is the caller graph for this function:

GetSpendData()

TaprootSpendData TaprootBuilder::GetSpendData

(

)

const

Compute spending data (after Finalize()).

Definition at line 477 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

GetTreeTuples()

std::vector< std::tuple< uint8_t, uint8_t, std::vector< unsigned char > > > TaprootBuilder::GetTreeTuples

(

)

const

Returns a vector of tuples representing the depth, leaf version, and script.

Definition at line 639 of file standard.cpp.

Here is the call graph for this function:

HasScripts()

bool TaprootBuilder::HasScripts ( ) const

inline

Returns true if there are any tapscripts.

Definition at line 319 of file standard.h.

Insert()

void TaprootBuilder::Insert ( TaprootBuilder::NodeInfo &&  node, int  depth  )

private

Insert information about a node at a certain depth, and propagate information up.

Definition at line 392 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

IsComplete()

bool TaprootBuilder::IsComplete ( ) const

inline

Return whether there were either no leaves, or the leaves form a Huffman tree.

Definition at line 309 of file standard.h.

Here is the caller graph for this function:

IsValid()

bool TaprootBuilder::IsValid ( ) const

inline

Return true if so far all input was valid.

Definition at line 307 of file standard.h.

Here is the caller graph for this function:

ValidDepths()

bool TaprootBuilder::ValidDepths ( const std::vector< int > &  depths )

static

Check if a list of depths is legal (will lead to IsComplete()).

Definition at line 418 of file standard.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_branch

std::vector<std::optional<NodeInfo> > TaprootBuilder::m_branch

private

The current state of the builder.

For each level in the tree, one NodeInfo object may be present. m_branch[0] is information about the root; further values are for deeper subtrees being explored.

For every right branch taken to reach the position we're currently working in, there will be a (non-nullopt) entry in m_branch corresponding to the left branch at that level.

For example, imagine this tree: - N0 - / \ N1 N2 / \ / \ A B C N3 / \ D E

Initially, m_branch is empty. After processing leaf A, it would become {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already exists, and it would thus be combined with it to produce a level 1 one, resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C} and {nullopt, N1, C, D} respectively. When E is processed, it is combined with D, and then C, and then N1, to produce the root, resulting in {N0}.

This structure allows processing with just O(log n) overhead if the leaves are computed on the fly.

As an invariant, there can never be nullopt entries at the end. There can also not be more than 128 entries (as that would mean more than 128 levels in the tree). The depth of newly added entries will always be at least equal to the current size of m_branch (otherwise it does not correspond to a depth-first traversal of a tree). m_branch is only empty if no entries have ever be processed. m_branch having length 1 corresponds to being done.

Definition at line 284 of file standard.h.

m_internal_key

XOnlyPubKey TaprootBuilder::m_internal_key

private

The internal key, set when finalizing.

Definition at line 286 of file standard.h.

m_output_key

XOnlyPubKey TaprootBuilder::m_output_key

private

The output key, computed when finalizing.

Definition at line 287 of file standard.h.

m_parity

bool TaprootBuilder::m_parity

private

The tweak parity, computed when finalizing.

Definition at line 288 of file standard.h.

m_valid

bool TaprootBuilder::m_valid = true

private

Whether the builder is in a valid state so far.

Definition at line 247 of file standard.h.

---

The documentation for this class was generated from the following files:

• src/script/standard.h
• src/script/standard.cpp