proof

Overview ¶

Package proof provides helper functions for merkle tree operations. # Merkle Trees and Proof Generation

We demonstrate the Merkle tree functionality in the context of the beacon state. There are two key concepts for understanding how fields are accessed in the tree:

**Field Index vs Generalized Index:**

1. Field Index: Position of a field in the BeaconState struct (0-based)

   BeaconState struct { GenesisTime [0] GenesisValidatorsRoot [1] <-- Field index is 1 Slot [2] Fork [3] ... }

2. Generalized Index: Position in the binary Merkle tree

   Root [1] / \ [2] [3] / \ / \ [4] [5] [6] [7] / \ / \ / \ / \ [8] [9] [10][11] [12][13] [14][15] <-- Leaf level | | | | | | | | GT GVR S F ... ... ... ... <-- Fields

For example, GenesisValidatorsRoot (field index 1):

depth = ceil(log2(num_fields))  // = 4 for this example
general_index = 2^depth + field_index = 9

**Proof Generation:**

A Merkle proof consists of the sibling hashes needed to reconstruct the root:

                Root [R]
            /              \
        [A]                [B]
      /    \             /    \
   [C]     [D]        [E]     [F]
  /  \    /  \      /  \     /  \
[G] [H] [J] [K]   [L] [M]  [N] [O]
    ^
    GenesisValidatorsRoot

To prove GenesisValidatorsRoot exists: 1. Start at H (GenesisValidatorsRoot) 2. Collect siblings: [G, D, B] 3. To verify:

• Hash(G,H) = C
• Hash(C,D) = A
• Hash(A,B) = R

Since the proof process can be applied to any leaf (A-O), we need to always use the generalized index for proof generation.