Transaction Merkle Tree

Similar to how a miner in Bitcoin builds a Merkle tree of block transactions, as well as a Merkle tree of transaction witnesses (after the Segwit upgrade), in Ergo, a miner should build a Merkle tree (and include a correct root hash of the tree into a block header), which is in case of Ergo combines both transactions and their respective spending proofs.

This tree is to be constructed as follows. A data block under a leaf of the tree could be empty or 64 bytes in length. Data of 64 bytes contains the identifier of the transaction (256-bit digest of transaction bytes without spending proofs) and 256 bits of a digest of all the spending proofs for the transaction combined. Data for the \(i-th\) transaction in the block (starting from 0) is authenticated by the \(i-th\) leaf. A leaf is \(hash(0 || pos || data)\), if the \(data\) is not empty (we do add prefix for domain separation), or \(null\) otherwise. Here, \(pos\) is the position of the transaction in the block. For internal nodes, a node is \(hash(1 || left\_child || right\_child)\); if either the node's left child or right child is not \(null\), \(null\) otherwise. If the root hash is \(null\), we write all zeros (of hash function output length) instead.