Skip to content

Merkle Tree

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.