Generalized Merkle Proof (GMP) Meta Tracking Issue

[fernantho]

Note

This issue aims at providing a concrete task lists for Generalized Merkle Proof generation inSSZ-QL in Prysm. This meta issue replaces the prior (Merkle Proofs of everything#15344)
This document follows the structure of the Github issue for the previous EPF project (Light Client Support #12991).

Note

The development done in this issue heavily depends on the SSZ-QL.

Must have

Implement hash tree root recursive computation

• Implement func hash_tree_root(info *sszquery.Info, data []bytes) which for a given sszInfo object/instance and a marshaled bytes slice computes its hash tree root as per SSZ spec Merkleization:
  • Entry point + dispatcher: HashTreeRootFromBytes + hashTreeRootFromBytes (switch on info.Type()).
  • create a computeHashTreeRoot{Type}(info *sszquery.Info, data[]bytes) where {Type} are the different data types.
• Integrate parallel chunk-hasher optimizations such as parallelize hasing for validator entries in beacon state. SSZ-QL MUST be as efficient as it is already.
• Benchmark recursive hash_tree_root against existing ones.

Merkle Proofs

• Generalized Indices (GI) of interest:
  • computeGeneralizedIndices(leaves...) compute the GI of the requested fields.
  • computePathAndHelperIndices(...) based on the leaves GI, compute the path and helper/sibling indices.
• Adapt the recursive hash_tree_root computation to feed the fastssz multiproof type MerkleProof struct:
• verifyMerkleProofs(...) function that checks if a given Multiproof verifies against a given root
• Benchmarking.

Nice to have

• Efficiency improvements. Research state of the art efficient hashing libraries and apply optimizations to GMP.
• Coverage tests for Merkle proofs in the upcoming ProgressiveLists.
• Visualization tool.

Fixes

TBD

Cosmetic

TBD

Other

References

Specification

• EPF6-Project Proposal - SSZ-QL with Merkle Proofs of everything.
• postSszQuery API Specification: This specification contains the very first version of SSZ-QL API, as well as our primary goal for the EPF6.
• SSZ-QL full specification.
• SSZ-QL playground Pythonic PoC.

Write-ups

TBD