Skip to content

Latest commit

 

History

History
187 lines (142 loc) · 6.78 KB

PLANNING.md

File metadata and controls

187 lines (142 loc) · 6.78 KB
Raw

Constantine's planning

This document is current as of June 23, 2024.

This splits Constantine's axis of development under various tracks. Priority is given to Ethereum, proof systems and optimization tracks.

Other tracks are stretch goals, contributions towards them are accepted.

Table of Contents

Tracks

Tech debt track

  • Endomorphism splitting bounds guarantee: i.e. division-based vs lattice-based splitting

Ethereum Consensus Track

Ethereum Execution Track

Proving Ethereum track

Optimization track

  • ARM assembly
  • Finish Nvidia GPU codegenerator up to MSM
  • Implement a backend for prime moduli of special form with fast reduction that don't need Montgomery form
  • Implement an unsaturated finite fields backend for Risc-V, WASM, WebGPU, AMD GPU, Apple Metal, Vulkan, ...
    • ideally in LLVM IR so that pristine Risc-V assembly can be generated and used in zkVMs without any risk of C stdlib or syscalls being used and without depending on the Nim compiler at build time.
  • introduce batchAffine_vartime
  • Optimized square_repeated in assembly for Montgomery and Crandall/Pseudo-Mersenne primes
  • Optimized elliptic curve directly calling assembly without ADX checks and limited input/output movement in registers or using function multi-versioning.
  • LLVM IR:
    • use internal or private linkage type
    • look into calling conventions like "fast" or "Tail fast"
    • check if returning a value from function is propely optimized compared to in-place result
    • use readnone (pure) and readmem attribute for functions
    • look into passing parameter as arrays instead of pointers?
    • use hot function attribute

User Experience track

Create a "Constantine book" to introduce Constantine concepts and walkthrough available protocols.

Technical marketing track

  • Create Python bindings

    • provide primitives appealing to cryptography researchers and enabling fast prototyping

  • Create a Constantine benchmark CLI and UI.

    • Make it easy-to-use from tools like Phoronix test suite
    • Give a single-threaded/multi-threaded, for use in say EthDocker to rank hardware.
    • Integrate building it in CI
    • Goal: the reference cryptographic benchmark

  • Participate in secp256k1 programming language benchmark:

ZK and proof systems track

  • Transcripts (Halo2, Merlin)

  • SNARKS:

    • Polynomial IOP (Interactive Oracle Proof) Implement BabySpartan (Spartan+Lasso) or Spartan or Spartan2

    • Lookup Argument One that commits to only small field elements if the witness contains small field elements Example: Lasso or LogUp+GKR

    • Multilinear Polynomial Commitment Schemes For efficiency when commiting to small values (for example coming from bit manipulation in hash functions) Example: KZG+Gemini/Zeromorph, Dory, Hyrax, Binius, ...

  • STARKS:

    • Implement small fields:
      • Mersenne31: 2^31-1
      • BabyBear
      • Goldilocks
    • Optimize small fields with Neon / Avx512
    • Implement FRI and/or STIR
      • Prerequisites:
        • Erasure codes
        • Merkle Trees

Long-term, unspecified:

  • zkML

Multi-party computation (MPC) track

  • Implement Shamir Secret Sharing
  • Threshold signatures and Distributed Key Generation for DVT (Distributed Validator Technology)

Core crypto track

Fully-Homomorphic encryption (FHE) track

  • Implement lattice-based RLWE: Ring-Learning-With-Errors

Long-term, unspecified:

  • Privacy-preserving machine learning

Post-Quantum cryptography (PQC) track

  • Implement a lattice-based cryptography scheme