Architecture of the SNARK-friendly STM library

[jpraynaud]

Why

Building a SNARK friendly STM library requires that the following elements cohabit:

• 2 signature schemes (BLS multi signature and Schnorr signature)
• 2 commitment schemes (Merkle trees with different leaves, or Merkle tree and Pedersen commitment)
• 2 proof systems (Concatenation and SNARK)

We have the following constraints:

• Do not introduce any breaking change to the stable implementation for Concatenation proofs
• Support the optional activation of the unstable implementation for SNARK proofs (via feature)

What

Design an architecture and an implementation plan for the SNARK-friendly STM library.

How

• Design an ideal architecture for the SNARK friendly STM
• Prototype a non working implementation of this architecture
• Prepare the implementation path for the SNARK-friendly STM library

Constraints to solve:

• Support activation of the SNARK signature by activation of a feature
• Do not change the stable Concatenation proof system to provide full backward compatibility for:
  • Signer node (key registration and signature diffusion messages)
  • Client node (aggregate signature verification message)
• Decouple BLS keys from signer registration
• Support different types of leaves in Merkle tree
• Support for eventual different commitment scheme for SNARKs
• Support for a an Initializer which creates Single signatures for both BLS and Schnorr
• Support for a SignatureAggregator (aka Clerk) which creates either Concatenation proof or SNARK proof
• Support for a Basic verifier which does not check the registration of the signers (do we want to keep that feature?)

[jpraynaud]

Proposed STM library target architecture to support multiple signature schemes

[jpraynaud]

Prototype of a non working implementation solving the constraints at branch:
[jpraynaud/prototype-snark-friendly-stm/mithril-stm/src/snark_friendly]

[jpraynaud]

Proposed implementation plan for a SNARK-friendly version of the Mithril STM protocol:

Note: This should not introduce backward compatibility with existing protocol artifacts (signatures, keys, proofs, ...)

• Step 1: Code re-organization
  • Create a commitment_scheme module and move merkle_tree in it
  • Create a signature_scheme module and move bls_multi_signature and schnorr_signature in it
  • Create a proof_system module and move concatenation_proof in it
  • Create a core or protocol module and move all the other modules in it
• Step 2: Code simplification
  • Move errors to their belonging modules
  • Remove the future_proof_system feature and replace it with the existing future_snark feature
  • Limit usage of <D: Digest> generics to merkle_tree module only (to be rechallenged)
  • Remove BasicVerifier implementation (and create a ticket for supporting this feature in a cleaner way in the future?) (to be rechallenged)
• Step 3: Implement SNARK-friendly changes for concatenation proof
  • Update the Merkle tree to support multiple leaves (for concatenation and following proof systems)
  • Update the key registration to support the new Merkle tree structure
  • Move responsibility of creating single signature artifacts to the concatenation proof system (in the proof_system module)
• Step 4: Implement SNARK pre-aggregation primitives (i.e. not the circuit(s) themselves)
  • Create a halo2 proof system sub-module in the proof_system module (it will embed all the halo2 circuits -non-recursive, recursive, etc.- in the future)
  • Implement the creation of the single signature artifacts using schnorr signatures
  • Adapt the key registration to support the new halo2 proof system