Function: getproof in merkle-tree/merkletree.py

Date: 2026-05-29

Time: 11:46

MerkleTree.get_proof — Merkle Inclusion Proof Generator

Purpose

get_proof constructs a Merkle inclusion proof (also called an authentication path) for a specific leaf. The proof is the minimal set of sibling hashes needed to recompute the root hash starting from that leaf. A verifier who holds the root hash can use this proof to confirm that a particular data block exists in the tree without needing the entire tree — this is the core mechanism behind efficient data verification in systems like certificate transparency logs, BitTorrent, and Dynamo-style anti-entropy protocols.

Contract

• Precondition: index must be in [0, self.leafcount). The tree must be fully constructed (all internal hashes computed).
• Postcondition: The returned MerkleProof contains exactly height sibling entries — one per level from leaf to root (exclusive). Feeding these siblings back through verify_proof with the original data will return True.
• Invariant: The proof is read-only; calling get_proof does not mutate the tree.

Parameters

| Parameter | Type | Description |

|-----------|------|-------------|

| index | int | Zero-based index into the *real* leaves (not the padded array). Must satisfy 0 <= index < self.leafcount. |

Edge cases: negative indices are explicitly rejected (not treated as Python-style negative indexing). An index equal to leafcount raises even though the backing array has padded slots beyond it.

Return Value

Returns a MerkleProof dataclass with:

• leaf_hash: the SHA-256 hash of the leaf at index
• leaf_index: the original index (echoed back for convenience)
• siblings: list of (hash, direction) tuples, ordered bottom-up (leaf level first, root's children last). direction is "left" or "right", indicating where the sibling sits relative to the current node — this tells the verifier which side to place the sibling hash when concatenating.
• root_hash: the tree's root hash at proof-generation time

The caller must understand that the proof is a snapshot — if update_leaf is called after proof generation, the proof becomes invalid against the new root.

Algorithm

1. Bounds check — reject out-of-range indices immediately.

2. Map logical index to array index — the tree is stored as a flat array in level-order. Leaves start at position paddedsize - 1, so leaf i lives at array index paddedsize - 1 + i.

3. Collect siblings bottom-up — walk from the leaf toward the root:

• Compute the parent: parent = (arr_idx - 1) // 2 (standard heap-array formula).
• Determine whether the current node is the left child (2*parent + 1) or right child (2*parent + 2).
• Grab the other child's hash (the sibling) and record which side it's on.
• Move up: arr_idx = parent.
• Stop when arr_idx == 0 (the root has no sibling).

4. Package the proof — wrap the leaf hash, siblings list, and current root hash into a MerkleProof.

The key insight in step 3: the direction label tells the verifier how to reconstruct each internal hash. If the sibling is on the "right", the verifier computes H(current || sibling). If on the "left", it computes H(sibling || current). This matches how verify_proof consumes the proof.

Side Effects

None. This is a pure read operation — no mutations to hashes, data, or any other state.

Error Handling

• IndexError: raised if index < 0 or index >= self.leafcount. The error message includes the valid range.
• No other exceptions are possible assuming the tree was constructed correctly (array indices are always valid given correct paddedsize).

Usage Patterns

Typical usage pairs getproof with verifyproof:

tree = MerkleTree([b"alice", b"bob", b"carol"])
proof = tree.get_proof(1)  # proof for "bob"

# Later, possibly on a different machine:
assert MerkleTree.verify_proof(b"bob", proof)

Also used in KeyRangeMerkleTree.getkeyproof, which translates a key lookup into a leaf index and delegates here.

Caller obligations:

• The caller must retain the original data to verify later (the proof contains hashes, not data).
• If the tree is mutable, the caller should not assume the proof remains valid after update_leaf.

Dependencies

• _sha256 — the project-local wrapper around hashlib.sha256 (used indirectly; the proof itself just reads precomputed hashes).
• MerkleProof — the dataclass that packages the proof.
• The array-backed tree layout: the entire method depends on the convention that node i's children are at 2i+1 and 2i+2, and that leaves are padded to the next power of 2.

Assumptions Not Enforced by the Type System

1. index is treated as a non-negative integer — Python's int permits arbitrary values; only the runtime bounds check catches violations.

2. The internal hashes array is assumed to be fully populated — there is no check for empty strings or sentinel values. If the tree were partially constructed, getproof would silently return a proof with invalid hashes.

3. Padding leaves use EMPTYHASH — the proof may include EMPTYHASH siblings for trees whose leaf count isn't a power of 2. This is correct but means a verifier could construct a valid proof for "empty" data at a padding index if the bounds check were bypassed.

Beliefs

• merkle-proof-sibling-order-bottom-up — getproof returns siblings ordered from leaf level to root level (bottom-up), and verifyproof consumes them in that same order
• merkle-proof-direction-is-sibling-position — The direction field in each sibling tuple indicates where the sibling sits (left or right), not where the current node sits — this controls concatenation order during verification
• merkle-proof-length-equals-height — A proof for a tree with paddedsize = 2^h contains exactly h sibling entries, one per tree level excluding the root
• merkle-proof-is-snapshot — Proofs are not invalidated in-place; a proof generated before update_leaf will fail verification against the new root hash
• merkle-get-proof-rejects-padding-indices — The bounds check uses leafcount (real leaves), not paddedsize, so proofs cannot be generated for padding slots even though they have valid hashes in the array