Light Client Prototyping Update - Oct 29

Creating Multi Merkle Proofs on SSZ objects

Implemented

Creating multiproofs on SSZ objects is a (mostly) straightforward process:

  • Top-level function signature (SSZObject, Path[]) => Proof
  • Helper functions:
    • convert Path to GeneralizedIndex (SSZType, Path) => GeneralizedIndex
    • find helper/proof indices (GeneralizedIndex) => GeneralizedIndex[]
  • Naive Algorithm:
    • Convert paths to generalized indices
      • store as leafIndices
    • Find helper indices of leafIndices
      • store as proofIndices
    • Run hashTreeRoot
      • calculating the generalized index of every field/intermediate hash
      • store field/intermediate hash if the index is in leafIndices or proofIndices
  • Implementation notes:
    • Use a builder pattern (or other) to abstract the proof backing / allow for different proof representations
      • minimal interface:
        • constructor(leafIndices: GeneralizedIndex[], proofIndices: GeneralizedIndex[]): ProofBuilder<Backing>
        • add(index: GeneralizedIndex, chunk: Bytes32): void
        • proof(): Backing

Verifying Multi Merkle Proofs

Implemented

Verifying proofs is easy, we're working directly at the merkle tree level with no SSZ type information is necessary.

No matter the proof backing, the algorithm is the same.

Creating SSZ Partials from Proofs

Not Implemented / Partially Implemented

Recreating SSZ partials from proofs is similar to creating proofs, with some caveats:

  • Helper function:
    • convert GeneralizedIndex to Paths (GeneralizedIndex) => Path[]
      • one index does not necessarily map to only one path, eg: in packed vectors of primitives
    • convert Bytes32 chunk(s) into objects
      • multiple objects can be in a single chunk
      • single objects can span multiple chunks
      • arrays may be missing their length
  • Naive Algorithm:
    • Optionally verify proof against a root
    • convert leaf generalized indices into paths
    • best effort recreate the object from chunks in the proof
  • Implementation notes:
    • It may be difficult to represent partials similarly to full SSZ objects, especially in typed languages
    • implementation-dependent issues may arise w some partials (eg: not including the length of a bitlist in the proof in an implementation that needs the length for its representation of bitlists)

Open SSZ Proof Questions

  • Handling of ssz expansions/summaries
    • Handling paths and partial reconstruction across expansions is tricky especially for typed languages
    • eg: stateRoot and parentRoot in BeaconBlock can be expanded to state and parent, full BeaconState and BeaconBlock objects respectively
    • Related questions:
      • How should expanded sub-objects be managed? Eg: should expanded sub-objects/partials be managed separately, or merged together w/ their parents? On proof generation + object recreation
  • Tying proofs to light client request/response interactions
    • How these proofs will be used, concretely, within the greater eth2 machinery?
    • How can we smooth out the differences between interactions on the beacon/shard level and the EE level?
Select a repo