Merkle Tree Builder

Block Merkle Tree

Block Merkle tree is in-memory structure build from all block transaction hashes and used to generate proof for transaction exist in specific block, provided block header and transaction index in the block.

Block header contains root of block Merkle tree, It used for proofs validation.

Contrary to QLDB approach, we not use blocks Merkle tree to prove the block existence in Ledger, but Skip-List like structure. For more information about skip list proofs, see Skip List Proofs

// Node struct keep data for Merkle tree node. For now, it is binary Merkle tree
// BuildTreeForBlockTx builds Merkle tree from block transactions.
func BuildTreeForBlockTx(block *types.Block) (*Node, error)

// Proof calculate intermediate hashes between leaf with given index and root (caller node)
func (n *Node) Proof(leafIndex int) ([][]byte, error)

type Node struct {
	sibling   *Node
	left      *Node
	right     *Node
	hash      []byte
	leafRange *leafRange
}

type leafRange struct {
	startIndex int
	endIndex   int
}