Bitcoin Core
24.99.0
P2P Digital Currency

Utility class to construct Taproot outputs from internal key and script tree. More...
#include <standard.h>
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, const CScript &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, CScript > >  GetTreeTuples () const 
Returns a vector of tuples representing the depth, leaf version, and script. 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...  
Utility class to construct Taproot outputs from internal key and script tree.
Definition at line 226 of file standard.h.
TaprootBuilder & TaprootBuilder::Add  (  int  depth, 
const CScript &  script,  
int  leaf_version,  
bool  track = true 

) 
Add a new script at a certain depth in the tree.
Add() operations must be called in depthfirst traversal order of binary tree. If track is true, it will be included in the GetSpendData() output.
Definition at line 446 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 459 of file standard.cpp.

staticprivate 
Combine information about a parent Merkle tree node from its child nodes.
Definition at line 360 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 469 of file standard.cpp.
WitnessV1Taproot TaprootBuilder::GetOutput  (  ) 
Compute scriptPubKey (after Finalize()).
Definition at line 480 of file standard.cpp.
TaprootSpendData TaprootBuilder::GetSpendData  (  )  const 
Compute spending data (after Finalize()).
Definition at line 482 of file standard.cpp.
std::vector< std::tuple< uint8_t, uint8_t, CScript > > TaprootBuilder::GetTreeTuples  (  )  const 
Returns a vector of tuples representing the depth, leaf version, and script.
Definition at line 644 of file standard.cpp.

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

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

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

static 
Check if a list of depths is legal (will lead to IsComplete()).
Definition at line 423 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 284 of file standard.h.

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

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

private 
The tweak parity, computed when finalizing.
Definition at line 288 of file standard.h.

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