Balanced binary trees provide logarithmic-sized membership paths.
LET’S PICTURE IT
A branching directory needs one choice per level rather than one record per entry.
SEE IT FOR YOURSELF
Build a root and follow one membership proofStep 1 / 4
This example hashes UTF-8 A, B, C and D. The displayed hashes are abbreviated, and the tree uses the playground’s sorted-pair convention.
This example hashes UTF-8 A, B, C and D. The displayed hashes are abbreviated, and the tree uses the playground’s sorted-pair convention.Each pair of raw child hashes is sorted, concatenated and hashed. The resulting parent fingerprints commit to their children.Hash the two parents under the same rule to obtain one root commitment. Changing a leaf changes the hashes on its path.The highlighted siblings are B and hash(C,D). Starting with A, the verifier recomputes its path and compares the final result with a trusted root.
Animated local teaching model. No wallet, RPC or live blockchain data. Some labels and hashes are abbreviated for readability.
Count levels for a full tree
A full balanced binary tree with eight leaves has three edges from a leaf to the root. A basic membership proof uses three sibling hashes.
Translate hashes into bytes
Three thirty-two-byte siblings occupy ninety-six raw hash bytes. Serialization, leaf data and other metadata can add to the complete transmitted proof size.
Handle incomplete shapes
Odd-node promotion and other construction choices can produce paths of differing lengths. Do not apply a perfect-tree count without checking the actual shape.
Separate verification cost
A shorter path generally needs fewer pair hashes, but total application gas includes input handling and surrounding checks. Proof size is not the whole transaction cost.