Module: merkle

This module contains functions for constructing Merkle roots and verifying Merkle paths. It is a custom implementation based on IETF RFC 6962. It creates a skewed Merkle tree. The tree is constructed by first selecting the largest subset of leaves that can form a complete binary Merkle tree and obtaining their root. To compute the overall Merkle root, the root of this subset is treated as a left sibling. The right sibling is computed by repeating this process recursively on the remaining leaves. It is implemented with in-place transforms.

While hashing leaves and intermediate nodes, the preimage is prefixed with LEAF_TAG and PAIR_TAG respectively to prevent second preimage attacks.

Function: proof_path

This function computes a minimal Merkle proof of inclusion of a leaf at index leaf_idx.

Inputs

• leaf_idx: The index of the leaf for which the path is to be derived.

• leaves: The list of all leaves in the Merkle tree.

• digest_cb: The function encapsulating the logic for hashing a leaf struct.

Function: root_from_proof

This function computes the Merkle root from a proof of inclusion of a leaf at index leaf_idx.

Inputs

• leaf: The leaf for which the proof of inclusion is provided.

• leaf_idx: The index of the proven leaf.

• leaves_len: The total number of leaves — used to calculate parity for all steps in Merkle proof verification.

• proof: The Merkle proof of inclusion of the leaf.

• digest_cb: The function encapsulating the logic for hashing a leaf struct.

Function: root_from_leaves

This function computes the Merkle root for a given list of leaves.

Inputs

• leaves: The list of all leaves in the Merkle tree.

• digest_cb: The function encapsulating the logic for hashing a leaf struct.