Bitcoin Core
21.99.0
P2P Digital Currency

Utility class to construct Taproot outputs from internal key and script tree. More...
#include <standard.h>
Classes  
struct  NodeInfo 
Information associated with a node in the Merkle tree. More...  
Public Member Functions  
TaprootBuilder &  Add (int depth, const CScript &script, int leaf_version) 
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...  
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...  
Utility class to construct Taproot outputs from internal key and script tree.
Definition at line 213 of file standard.h.
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 depthfirst traversal order of binary tree.
Definition at line 438 of file standard.cpp.
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.

staticprivate 
Combine information about a parent Merkle tree node from its child nodes.
Definition at line 377 of file standard.cpp.
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.
WitnessV1Taproot TaprootBuilder::GetOutput  (  ) 
Compute scriptPubKey (after Finalize()).
Definition at line 471 of file standard.cpp.

private 
Insert information about a node at a certain depth, and propagate information up.
Definition at line 389 of file standard.cpp.

inline 
Return whether there were either no leaves, or the leaves form a Huffman tree.
Definition at line 283 of file standard.h.

inline 
Return true if so far all input was valid.
Definition at line 281 of file standard.h.

static 
Check if a list of depths is legal (will lead to IsComplete()).
Definition at line 415 of file standard.cpp.

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 (nonnullopt) 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 depthfirst 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.

private 
The internal key, set when finalizing.
Definition at line 262 of file standard.h.

private 
The output key, computed when finalizing. */.
Definition at line 263 of file standard.h.

private 
Whether the builder is in a valid state so far.
Definition at line 223 of file standard.h.