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 otherwise. If the root hash is
null, we write all zeros (of hash function output length) instead.