Merkle Proofs

The Proofs contain different types of Merkle Proofs.

Patricia Merkle Proof

The Patricia Merkle Proof is a proof for a single leaf and is used in the execution layer of Ethereum for states of accounts and storage, transaction receipts, and more. This is what you get when calling eth_getProof.

SSZ Merkle Proof

These Merkle Trees are used within the beacon chain. The structure is based on the definition of the SSZ types and allows for the proof of individual properties. Another feature is the option to proof multiple leaves at once, which is used in different types of proofs in the Colibri client.

All ssz proofs for single or multiple leaves follow the same structure:

• Only required nodes (32 bytes each) are added.

• The nodes are always sorted by their generalized index, starting with the highest number.

While a Merkle proof for a single proof always has the same fixed size (which is equal to its depth), the size of a multi-proof depends on the number of leaves and their position within the tree. To verify a multi-proof, we first need to determine which nodes (represented by the generalized index) are required. For example, a multi-proof for a small tree with four leaves would end up with an empty list if you actually request all 4 leaves because there would be no nodes left to prove.

  // define a small tree with 3 leaves
  ssz_def_t TEST_SUB[] = {
      SSZ_UINT8("a"),
      SSZ_UINT8("b"),
      SSZ_UINT8("c"),
  };

  ssz_def_t TEST_ROOT[] = {
      SSZ_UINT8("count"),
      SSZ_CONTAINER("sub", TEST_SUB),
  };

  ssz_def_t TEST_TYPE_CONTAINER = SSZ_CONTAINER("TEST_ROOT", TEST_ROOT);

  // create a container with the defined ssz type
  uint8_t   ssz_data[]          = {1, 2, 3, 4}; // serialized data of the container
  ssz_ob_t  val                 = ssz_ob(TEST_TYPE_CONTAINER, bytes(ssz_data, 4));

  // create a multi-proof the properties count,  a and b
  bytes_t multi_proof = ssz_create_multi_proof(res, 3,
                            ssz_gindex(res.def, 1, "count"),
                            ssz_gindex(res.def, 2, "sub", "a"),
                            ssz_gindex(res.def, 2, "sub", "b")
                       );

 // This proof has only one witness

 // verify the proof
 // create a Leafs array for the required Leafs
  uint8_t leafes[96] = {0};
  leafes[0]          = 1; // count = 1
  leafes[32]         = 2; // a = 2
  leafes[64]         = 3; // b = 3

  // define the gindexes of the required lproperties
  gindex_t gindexes[] = {
    ssz_gindex(res.def, 1, "count"),
    ssz_gindex(res.def, 2, "sub", "a"),
    ssz_gindex(res.def, 2, "sub", "b")};

  // verify the proof and store the calculated root hash in proofed_root
  bytes32_t proofed_root = {0};
  ssz_verify_multi_merkle_proof(multi_proof, bytes(leafes, sizeof(leafes)), gindexes, proofed_root);

  // now the root contains the root hash, which you can compare with the hash_tree_root of the container
  bytes32_t root = {0};
  ssz_hash_tree_root(val, root);

  // assert
  TEST_ASSERT_EQUAL_UINT8_ARRAY_MESSAGE(root, proofed_root, 32, "root hash must be the same after merkle proof");