Bitcoin Core  21.99.0
P2P Digital Currency
Classes | Public Member Functions | Static Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
TaprootBuilder Class Reference

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

#include <standard.h>

Collaboration diagram for TaprootBuilder:
[legend]

Classes

struct  NodeInfo
 Information associated with a node in the Merkle tree. More...
 

Public Member Functions

TaprootBuilderAdd (int depth, const CScript &script, int leaf_version)
 Add a new script at a certain depth in the tree. More...
 
TaprootBuilderAddOmitted (int depth, const uint256 &hash)
 Like Add(), but for a Merkle node with a given hash to the tree. More...
 
TaprootBuilderFinalize (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...
 

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...
 

Detailed Description

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

Definition at line 213 of file standard.h.

Member Function Documentation

◆ Add()

TaprootBuilder & TaprootBuilder::Add ( int  depth,
const CScript script,
int  leaf_version 
)

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

Add() operations must be called in depth-first traversal order of binary tree.

Definition at line 438 of file standard.cpp.

Here is the call 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 450 of file standard.cpp.

Here is the call 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 377 of file standard.cpp.

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 460 of file standard.cpp.

Here is the call graph for this function:

◆ GetOutput()

WitnessV1Taproot TaprootBuilder::GetOutput ( )

Compute scriptPubKey (after Finalize()).

Definition at line 471 of file standard.cpp.

◆ 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 389 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 283 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 281 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 415 of file standard.cpp.

Here is the call 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 260 of file standard.h.

◆ m_internal_key

XOnlyPubKey TaprootBuilder::m_internal_key
private

The internal key, set when finalizing.

Definition at line 262 of file standard.h.

◆ m_output_key

XOnlyPubKey TaprootBuilder::m_output_key
private

The output key, computed when finalizing. *‍/.

Definition at line 263 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 223 of file standard.h.


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