The tree module provides the radix-4 transaction tree structure used in Ark rounds. Trees enable efficient creation of many VTXOs in a single round with shared cosigning.
Overview ArkRounds use transaction trees to:
Batch VTXO creation : Create hundreds of VTXOs in one roundEfficient cosigning : MuSig2 aggregation across tree branchesMinimize transactions : Radix-4 structure reduces tree depthEnable exits : Each leaf has a path to the on-chain anchor
Trees support two modes:
clArk (classic Ark): Cosigned tree with immediate finalityhArk (hash-locked Ark): Hash-locked leaves for atomic swaps
Tree Structure A basic radix-4 tree with 4 leaves.
pub struct Tree { nodes : Vec < Node >, nb_leaves : usize , }
Radix : Maximum 4 children per nodeNode ordering : Leaves first, then internal nodes toward the rootTree Construction pub fn new ( nb_leaves : usize ) -> Tree
Create a radix-4 tree with the given number of leaves.
Panics if nb_leaves == 0. pub fn nb_nodes_for_leaves ( nb_leaves : usize ) -> usize
Calculate total nodes needed for a tree with nb_leaves leaves.
Example tree sizes:
1-4 leaves: 5 nodes total (4 leaves + 1 root)
5-16 leaves: 20 nodes (16 leaves + 4 level-1 + 1 root)
100 leaves: 133 nodes
Tree Methods pub fn nb_leaves ( & self ) -> usize pub fn nb_nodes ( & self ) -> usize pub fn nb_internal_nodes ( & self ) -> usize
Get tree dimensions.
pub fn node_at ( & self , node_idx : usize ) -> & Node pub fn root ( & self ) -> & Node
Access specific nodes.
pub fn iter ( & self ) -> Iter <' _ , Node > pub fn iter_internal ( & self ) -> Iter <' _ , Node > pub fn into_iter ( self ) -> IntoIter < Node >
Iterate over nodes (all or internal only).
pub fn iter_branch ( & self , leaf_idx : usize ) -> BranchIter <' _ >
Iterate from a leaf to the root.
pub fn iter_branch_with_output ( & self , node_idx : usize ) -> BranchWithOutputIter <' _ >
Iterate ancestors with their child indices.
let tree = Tree :: new ( 10 ); // Iterate branch from leaf 6 to root for node in tree . iter_branch ( 6 ) { println! ( "Node {} at level {}" , node . idx (), node . level ()); } // Iterate with output indices for ( ancestor_idx , child_idx ) in tree . iter_branch_with_output ( 6 ) { println! ( "Node {} is child {} of node {}" , 6 , child_idx , ancestor_idx ); }
Node Structure pub struct Node { idx : u32 , parent : Option < u32 >, children : [ Option < u32 >; RADIX ], leaves : ( u32 , u32 ), nb_tree_leaves : u32 , level : u32 , }
Node Methods pub fn idx ( & self ) -> usize
The node’s index in the tree (leaves start at 0).
pub fn internal_idx ( & self ) -> usize
Index among internal nodes (starts after leaves). Panics if called on a leaf.
pub fn parent ( & self ) -> Option < usize >
Parent node index, or None for root.
pub fn children ( & self ) -> impl Iterator < Item = usize >
Iterator over child node indices.
pub fn level ( & self ) -> usize
Level in the tree (0 for leaves).
pub fn internal_level ( & self ) -> usize
Level among internal nodes (0 for parent of leaves). Panics on leaf.
pub fn leaves ( & self ) -> impl Iterator < Item = usize >
Iterator over all leaf indices under this node.
pub fn is_leaf ( & self ) -> bool pub fn is_root ( & self ) -> bool
Check node type.
VtxoTreeSpec Specifies a VTXO tree before signing.
pub struct VtxoTreeSpec { pub vtxos : Vec < VtxoLeafSpec >, pub expiry_height : BlockHeight , pub server_pubkey : PublicKey , pub exit_delta : BlockDelta , pub global_cosign_pubkeys : Vec < PublicKey >, }
Fields:
vtxos: Leaf VTXO specifications (one per leaf)expiry_height: When VTXOs expireserver_pubkey: Server’s signing keyexit_delta: Timelock for unilateral exitsglobal_cosign_pubkeys: Pubkeys that cosign all nodes (e.g., server’s round key)
Construction pub fn new ( vtxos : Vec < VtxoLeafSpec >, server_pubkey : PublicKey , expiry_height : BlockHeight , exit_delta : BlockDelta , global_cosign_pubkeys : Vec < PublicKey >, ) -> VtxoTreeSpec
Panics if vtxos is empty. Key Methods pub fn nb_leaves ( & self ) -> usize pub fn nb_nodes ( & self ) -> usize pub fn nb_internal_nodes ( & self ) -> usize
Tree dimensions.
pub fn total_required_value ( & self ) -> Amount
Sum of all VTXO amounts.
pub fn funding_tx_script_pubkey ( & self ) -> ScriptBuf pub fn funding_tx_txout ( & self ) -> TxOut
The output that funds this tree (round funding tx output).
pub fn unsigned_transactions ( & self , utxo : OutPoint ) -> Vec < Transaction >
Build all unsigned transactions (leaves to root).
pub fn cosign_agg_pks ( & self ) -> impl Iterator < Item = PublicKey >
Aggregate cosign pubkeys for all nodes.
pub fn into_unsigned_tree ( self , utxo : OutPoint ) -> UnsignedVtxoTree
Convert to unsigned tree for signing.
VtxoLeafSpec Specifies a leaf VTXO in the tree.
pub struct VtxoLeafSpec { pub vtxo : VtxoRequest , pub cosign_pubkey : Option < PublicKey >, pub unlock_hash : UnlockHash , }
Fields:
vtxo: The actual VTXO request (policy + amount)cosign_pubkey: For interactive participants (None for async/non-interactive)unlock_hash: Hash lock for hArk leaves
UnsignedVtxoTree A VTXO tree ready to be signed (with cached data).
pub struct UnsignedVtxoTree { pub spec : VtxoTreeSpec , pub utxo : OutPoint , pub cosign_agg_pks : Vec < PublicKey >, pub txs : Vec < Transaction >, pub internal_sighashes : Vec < TapSighash >, // ... }
Construction pub fn new ( spec : VtxoTreeSpec , utxo : OutPoint ) -> UnsignedVtxoTree
Create unsigned tree from spec. Computes all transactions and sighashes.
Signing Methods pub fn cosign_branch ( & self , cosign_agg_nonces : & [ AggregatedNonce ], leaf_idx : usize , cosign_key : & Keypair , cosign_sec_nonces : Vec < SecretNonce >, ) -> Result < Vec < PartialSignature >, IncorrectSigningKeyError >
User cosigns their branch (from leaf to root).
cosign_agg_nonces: Aggregated nonces for all internal nodesleaf_idx: Index of user’s leaf in the treecosign_key: User’s cosigning keypaircosign_sec_nonces: User’s secret nonces for the branch pub fn cosign_tree ( & self , cosign_agg_nonces : & [ AggregatedNonce ], keypair : & Keypair , cosign_sec_nonces : Vec < SecretNonce >, ) -> Vec < PartialSignature >
Sign all internal nodes (for global signers like the server).
Verification Methods pub fn verify_branch_cosign_partial_sigs ( & self , cosign_agg_nonces : & [ AggregatedNonce ], request : & VtxoLeafSpec , cosign_pub_nonces : & [ PublicNonce ], cosign_part_sigs : & [ PartialSignature ], ) -> Result <(), String >
Verify a user’s branch partial signatures.
pub fn verify_global_cosign_partial_sigs ( & self , pk : PublicKey , agg_nonces : & [ AggregatedNonce ], pub_nonces : & [ PublicNonce ], part_sigs : & [ PartialSignature ], ) -> Result <(), CosignSignatureError >
Verify global signer’s (server’s) partial signatures.
Finalization pub fn combine_partial_signatures ( & self , cosign_agg_nonces : & [ AggregatedNonce ], branch_part_sigs : & HashMap < PublicKey , Vec < PartialSignature >>, global_signer_part_sigs : & [ impl AsRef <[ PartialSignature ]>], ) -> Result < Vec < schnorr :: Signature >, CosignSignatureError >
Combine all partial signatures into final Schnorr signatures.
pub fn verify_cosign_sigs ( & self , signatures : & [ schnorr :: Signature ], ) -> Result <(), XOnlyPublicKey >
Verify final signatures are valid.
pub fn into_signed_tree ( self , signatures : Vec < schnorr :: Signature >, ) -> SignedVtxoTreeSpec
Convert to signed tree with final signatures.
SignedVtxoTreeSpec A fully signed VTXO tree.
pub struct SignedVtxoTreeSpec { pub spec : VtxoTreeSpec , pub utxo : OutPoint , pub cosign_sigs : Vec < schnorr :: Signature >, }
Construction pub fn new ( spec : VtxoTreeSpec , utxo : OutPoint , cosign_signatures : Vec < schnorr :: Signature >, ) -> SignedVtxoTreeSpec
Methods pub fn nb_leaves ( & self ) -> usize
pub fn exit_branch ( & self , leaf_idx : usize ) -> Vec < Transaction >
Get exit transactions from root to leaf (reversed order).
For repeated calls, use CachedSignedVtxoTree instead. pub fn all_final_txs ( & self ) -> Vec < Transaction >
All transactions (leaves to root), with signatures on internal nodes.
pub fn into_cached_tree ( self ) -> CachedSignedVtxoTree
Convert to cached tree for efficient branch extraction.
CachedSignedVtxoTree Signed tree with cached transactions for fast access.
pub struct CachedSignedVtxoTree { pub spec : SignedVtxoTreeSpec , pub txs : Vec < Transaction >, }
Methods pub fn exit_branch ( & self , leaf_idx : usize ) -> Vec < & Transaction >
Efficiently get exit branch (root to leaf).
pub fn all_final_txs ( & self ) -> & [ Transaction ] pub fn unsigned_leaf_txs ( & self ) -> & [ Transaction ] pub fn internal_node_txs ( & self ) -> & [ Transaction ]
Access transaction sets.
pub fn build_vtxo ( & self , leaf_idx : usize ) -> Vtxo
Build the final VTXO for a specific leaf.
pub fn output_vtxos ( & self ) -> impl Iterator < Item = Vtxo > + ExactSizeIterator
All output VTXOs from the round.
pub fn internal_vtxos ( & self ) -> impl Iterator < Item = ServerVtxo > + ExactSizeIterator
All internal server VTXOs (for tracking).
pub fn spend_info ( & self ) -> impl Iterator < Item = ( VtxoId , Txid )>
VTXO spending relationships.
Usage Examples Creating a Simple Tree let nb_leaves = 10 ; let tree = Tree :: new ( nb_leaves ); assert_eq! ( tree . nb_leaves (), 10 ); assert_eq! ( tree . nb_internal_nodes (), 3 ); // 3 internal nodes for 10 leaves println! ( "Tree has {} total nodes" , tree . nb_nodes ()); for node in tree . iter_internal () { println! ( "Internal node {} has {} leaves" , node . idx (), node . leaves () . count () ); }
Building and Signing a VTXO Tree // 1. Create leaf specs let vtxo_specs : Vec < VtxoLeafSpec > = users . iter () . map ( | user | { VtxoLeafSpec { vtxo : VtxoRequest { policy : VtxoPolicy :: new_pubkey ( user . pubkey), amount : Amount :: from_sat ( 100_000 ), }, cosign_pubkey : Some ( user . cosign_pubkey), unlock_hash : user . unlock_hash, } }) . collect (); // 2. Create tree spec let tree_spec = VtxoTreeSpec :: new ( vtxo_specs , server_pubkey , expiry_height , exit_delta , vec! [ server_round_pubkey ], // global cosigner ); // 3. Convert to unsigned tree let funding_utxo = OutPoint :: new ( round_tx . compute_txid (), 0 ); let unsigned_tree = tree_spec . into_unsigned_tree ( funding_utxo ); // 4. Generate aggregate nonces let user_nonces = collect_user_nonces ( & users ); // from users let server_nonces = generate_server_nonces ( & unsigned_tree ); let agg_nonces = unsigned_tree . spec . calculate_cosign_agg_nonces ( & user_nonces , & [ server_nonces ], ) ? ; // 5. Collect partial signatures let mut branch_sigs = HashMap :: new (); for user in & users { let leaf_idx = tree_spec . leaf_idx_of_req ( & user . vtxo_request) . unwrap (); let sigs = unsigned_tree . cosign_branch ( & agg_nonces , leaf_idx , & user . cosign_key, user . secret_nonces, ) ? ; branch_sigs . insert ( user . cosign_pubkey, sigs ); } // 6. Server signs all nodes let server_sigs = unsigned_tree . cosign_tree ( & agg_nonces , & server_round_key , server_secret_nonces , ); // 7. Combine signatures let final_sigs = unsigned_tree . combine_partial_signatures ( & agg_nonces , & branch_sigs , & [ server_sigs ], ) ? ; // 8. Verify and finalize unsigned_tree . verify_cosign_sigs ( & final_sigs ) ? ; let signed_tree = unsigned_tree . into_signed_tree ( final_sigs ); // 9. Cache for efficient access let cached_tree = signed_tree . into_cached_tree (); // 10. Distribute VTXOs to users for ( idx , user ) in users . iter () . enumerate () { let vtxo = cached_tree . build_vtxo ( idx ); send_to_user ( user , vtxo ); }
Important Notes Radix-4 trees minimize depth while keeping the radix manageable. A 100-leaf tree has only ~3-4 levels, reducing the exit transaction count.
Nonces for MuSig2 must be unique . Never reuse secret nonces across different signing sessions or trees.
Global cosigners (like the server) sign all internal nodes. Leaf cosigners only sign their branch from leaf to root.
Use CachedSignedVtxoTree for repeated access to branches and VTXOs. It pre-computes all transactions for O(1) lookups.