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

#include <signingprovider.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 45 of file signingprovider.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 366 of file signingprovider.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 379 of file signingprovider.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 285 of file signingprovider.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 389 of file signingprovider.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 400 of file signingprovider.cpp.

Here is the caller graph for this function:

◆ GetSpendData()

TaprootSpendData TaprootBuilder::GetSpendData ( ) const

Compute spending data (after Finalize()).

Definition at line 402 of file signingprovider.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 564 of file signingprovider.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 138 of file signingprovider.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 317 of file signingprovider.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 128 of file signingprovider.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 126 of file signingprovider.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 343 of file signingprovider.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 103 of file signingprovider.h.

◆ m_internal_key

XOnlyPubKey TaprootBuilder::m_internal_key

private

The internal key, set when finalizing.

Definition at line 105 of file signingprovider.h.

◆ m_output_key

XOnlyPubKey TaprootBuilder::m_output_key

private

The output key, computed when finalizing.

Definition at line 106 of file signingprovider.h.

◆ m_parity

bool TaprootBuilder::m_parity

private

The tweak parity, computed when finalizing.

Definition at line 107 of file signingprovider.h.

◆ m_valid

bool TaprootBuilder::m_valid = true

private

Whether the builder is in a valid state so far.

Definition at line 66 of file signingprovider.h.

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

src/script/signingprovider.h
src/script/signingprovider.cpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ Add()

◆ AddOmitted()

◆ Combine()

◆ Finalize()

◆ GetOutput()

◆ GetSpendData()

◆ GetTreeTuples()

◆ HasScripts()

◆ Insert()

◆ IsComplete()

◆ IsValid()

◆ ValidDepths()

Member Data Documentation

◆ m_branch

◆ m_internal_key

◆ m_output_key

◆ m_parity

◆ m_valid