Binius64 zk-SNARK Implementation

repository·main·Indexed 41 days ago

https://github.com/binius-zk/binius64

A high-performance zk-SNARK implementation in Rust designed for 64-bit word computations. Binius64 optimizes bitwise operations through shifted value indices to reduce constraint complexity and is optimized for modern 64-bit CPUs using SIMD instructions.

Tokens
49.2K
Snippets
145
Records
211
Agent score
53%

What's inside Binius64

  1. Overview of Binius64

    main

    Binius64 is a zero-knowledge succinct argument system (zk-SNARK) implemented in Rust. It is designed to prove arbitrary computations expressed as non-deterministic circuits over 64-bit words.

    Key features include:

    • 64-bit Word Support: Uses shifted value indices to natively encode bitwise operations, reducing constraint complexity by 64x compared to bit-level approaches.
    • Performance: Optimized for modern 64-bit CPUs using SIMD instructions.
    • Successor to Binius: Focuses on simplicity and CPU performance over the original Binius protocol.
  2. Navigate the Binius64 crate organization

    main

    The project is organized into functional layers. Use this guide to identify which crate to use for your specific task:

    Shared Crates (Foundational)

    • binius-field: Binary field arithmetic (optimized).
    • binius-math: Math primitives (FFT, Reed-Solomon, multilinear polynomials).
    • binius-hash: Hash functions (SHA-256) and compression.
    • binius-transcript: Fiat-Shamir transcript handling.
    • binius-utils: Serialization and bitwise utilities.

    Frontend Crates (Circuit Construction)

    • binius-frontend: The primary API for Binius64 circuit construction (CircuitBuilder, wires, witness).
    • binius-core: Shared constraint system data structures.
    • binius-circuits: Standard library of gadgets (SHA256, ECDSA, base64).
    • binius-spartan-frontend: Builder for Iron Spartan.

    Verifier Crates (Verification)

    • binius-verifier: High-level Binius64 verification API.
    • binius-spartan-verifier: Iron Spartan verification.
    • binius-ip / binius-iop: Low-level interactive protocol structures (sumcheck, FRI, Merkle trees).

    Prover Crates (Proof Generation)

    • binius-prover: High-level Binius64 proof generation API.
    • binius-spartan-prover: Iron Spartan proof generation.
    • binius-ip-prover / binius-iop-prover: Low-level prover implementations.

    Examples and Benchmarks

    • binius-examples: Example circuits with a CLI framework.
    • binius-arith-bench: Arithmetic microbenchmarks.
  3. Binius64 Core Terminology

    main

    Understanding the following terms is essential for working with the Binius64 constraint system and circuits:

    • Value index: (segment, index) naming a word in a value vector. Segment is Constant, InOut, Private, or Scratch. Packed into a u32.
    • Value segment: One of four sections a circuit allocates values in (Constant, InOut, Private, Scratch).
    • Shifted value index: (value_index, shift_op, shift_amount) referencing a witness word with an optional shift.
    • AND constraint: A & B ^ C = 0 where A, B, C are XOR combinations of shifted values.
    • MUL constraint: A * B = HI || LO (unsigned 64-bit multiplication producing 128-bit result).
    • Tower field $T_i$: Binary extension field $\mathbb{F}{2^{2^i}}$ (e.g., $T_7 = \mathbb{F}{2^{128}}$).
    • Sumcheck: Protocol reducing multivariate polynomial evaluation to univariate checks.
    • BaseFold: Polynomial commitment scheme using FRI over binary fields.
    • Witness: Secret input values (64-bit words) satisfying the constraint system.
    • Circuit: High-level representation of computation built with CircuitBuilder.
    • Constraint system: Low-level AND/MUL constraints compiled from a circuit.
  4. Follow Binius64 design principles for development

    main

    When extending or building on top of Binius64, adhere to these architectural constraints:

    Dependency Direction

    • Prover $\rightarrow$ Verifier: Prover crates depend on verifier crates. This allows verifiers to be deployed independently and ensures provers use consistent data structures. Verifier crates must not depend on prover crates.
    • Frontend Independence: Frontend crates must not depend on backend (prover/verifier) crates. Circuit definitions must remain independent of the specific proving system used.

    Implementation Priorities

    • Verifier Crates: Focus on security, auditability, and clarity. Use only scalar fields (avoid packed fields), avoid parallelization, and use simple data structures.
    • Prover Crates: Focus on performance. Use packed fields, SIMD optimizations, and parallelization (via Rayon).

    Testing

    • Most tests are located in prover crates because they can test the full end-to-end flow (prove $\rightarrow$ verify), whereas verifier crates cannot generate the proofs required for testing.
  5. Binius design principles for code review

    main

    When reviewing code, use these tradeoff guidelines to evaluate design decisions. These are not hard rules, but signals for when a developer might be choosing the wrong side of a tradeoff.

    Field crate ease-of-use over ease-of-extension

    • Prefer keeping binius-field easy for library consumers to use over making it easy to extend.
    • Why: The crate is consumed everywhere but extended rarely. Avoid propagating complex bounds through public APIs; instead, push complexity down into the crate (e.g., make capabilities parent traits of PackedField/Field).
    • Reconsider when: No sensible default implementation exists, or it causes a coherence mess (overlapping blanket impls).

    No backwards compatibility

    • Prefer strongly building clean, targeted interfaces over maintaining backwards compatibility.
    • Why: The codebase is not in production; breaking changes are acceptable to improve design. Isolate breaking changes to specific commits.
    • Reconsider when: The breakage requires a massive, unjustified whole-codebase change.

    Avoid premature generalization

    • Prefer weakly simple logic over perfectly DRY (Don't Repeat Yourself) code.
    • Why: Readability and understandability are prioritized over extensibility. Small amounts of repeated logic are better than one complex, generalized instance.
    • Reconsider when: The generalization is simple and improves decoupling/understandability.

    Generous bounds over caller contortion

    • Prefer adding trait/associated-type bounds that every implementation trivially satisfies (e.g., Clone, Sum) over keeping bounds minimal at the cost of complex call sites.
    • Why: Bounds that cost nothing to implement should be used to prevent ergonomic issues and bugs at the call sites (e.g., avoiding array::from_fn or mem::take just to satisfy a minimal bound).
    • Reconsider when: Some implementations cannot satisfy the bound, or the narrowness is required for safety/coherence.

    Don't trade loose coupling for method-call convenience

    • Prefer keeping functions in their respective module boundaries (e.g., separating algorithm code from data types) over making them methods on a type.
    • Why: Converting a free function to a method (x.method()) is only a win if the type is the sole owner of that responsibility. Avoid moving functions to types if it drags in heavy dependencies (like rayon or compute) into a data-structure module.
    • Reconsider when: The type is the genuine sole owner and moving it doesn't cross module boundaries unnecessarily.

    Cohesive commits and PRs

    • Prefer multiple small, logically cohesive commits/PRs over one large monolithic change.
    • Why: Smaller PRs (~200–500 lines) are easier to review, reason about, and revert. Use jj for stacked PR workflows.
    • Reconsider when: Changes are genuinely inseparable (e.g., a mechanical rename that would break compilation if split).
  6. Understand snapshot file format and constraints

    main

    Snapshot files follow the naming convention <circuit_name>.snap.

    Key properties:

    • Content: They contain the expected output of the circuit's stat command, including detailed statistics about the constraint system (e.g., number of gates, constraints, witness values).
    • Parameter Sensitivity: Snapshots are strictly dependent on the parameters used. When checking or updating a snapshot, you must use the exact same parameters (e.g., --max-message-len) that were used to create the original snapshot, otherwise the check will fail.
  7. Best practices for Binius circuit design

    main

    When building circuits with Binius, follow these design guidelines to ensure correctness and reproducibility:

    1. Separation of Concerns

    • Params (Compile-time): Use for structural configuration like max_len or use_optimization. These affect how the circuit is built.
    • Instance (Runtime): Use for actual input values (e.g., message, seed). These should be validated against Params during witness population.

    2. Circuit Building (build method)

    • Use builder.add_witness() for witnesses.
    • Use builder.add_constant_64() for constants.
    • Use builder.add_inout() for input/output wires.
    • Store references to gadgets or wires in your example struct so they can be accessed during witness population.

    3. Witness Population (populate_witness method)

    • Validate Early: Use ensure! to check that instance data is compatible with circuit parameters.
    • Deterministic Randomness: Always use a fixed seed with StdRng::seed_from_u64(0) for any required randomness to ensure reproducibility.
    • Populate All: Ensure all wires/gadgets created in build are correctly populated.

    4. Error Handling

    • Return Result<()> from all trait methods.
    • Use ensure! for validation with clear, descriptive error messages.
  8. Understand the difference between Binius64 and Iron Spartan proof systems

    main

    The repository implements two distinct proof systems with different properties and use cases:

    Binius64

    • Zero-Knowledge: No
    • Constraint Type: AND/MUL on 64-bit words
    • Mechanism: Proves satisfiability of constraint systems over 64-bit words using shifted value indices (word index + shift operation + shift amount).
    • Key Operations:
      • AND constraints: Bitwise AND relations.
      • MUL constraints: 64-bit unsigned integer multiplication ($p \times q = 2^{64} \times hi + lo$).
    • Efficiency: Achieves a 64-fold reduction in complexity compared to bit-level approaches by using XOR for free linear combinations.

    Iron Spartan

    • Zero-Knowledge: Yes
    • Constraint Type: Multiplication over $GF(2^{128})$
    • Mechanism: Uses multiplication constraints over the GHASH binary field $GF(2^{128})$. Constraints follow the form $A \times B = C$, where operands are XOR-sums of witness field elements. Sparse constraint matrices contain only 0 and 1 entries.
  9. Run tests with cargo-nextest

    main

    The project uses cargo-nextest for testing, as it executes each test in its own process, making panics and hangs easier to isolate. Note that nextest does not run documentation tests; those must be run separately using cargo test --doc.

    # One-time setup
    $ cargo install cargo-nextest --locked
    
    # Run the full test suite
    $ cargo nextest run --workspace
    
    # Run tests for a specific crate
    $ cargo nextest run -p <crate>
    
    # Run tests matching a filter expression
    $ cargo nextest run -E 'test(<substring>)'
    
    # Run documentation tests (required separately)
    $ cargo test --doc --workspace
  10. Create a new circuit example using the ExampleCircuit trait

    main

    To create a new circuit example in Binius, implement the ExampleCircuit trait. This requires defining two associated types, Params (for compile-time configuration like maximum sizes) and Instance (for runtime witness data like user inputs), and implementing two methods: build and populate_witness.

    Implementation Steps:

    1. Define Params: A struct using #[derive(Args)] for circuit structure configuration (e.g., max_size).
    2. Define Instance: A struct using #[derive(Args)] for runtime witness data (e.g., input values).
    3. Implement build: Use the CircuitBuilder to add witnesses, constants, and gadgets. Store any necessary references in your main example struct for later use.
    4. Implement populate_witness: Process the Instance data, validate it against Params, and populate the witness using the stored references.
    5. Register: Add the circuit to your main.rs using .circuit::<MyCircuitExample>("name", "description").
    use anyhow::{ensure, Result};
    use binius_examples::ExampleCircuit;
    use binius_frontend::compiler::{circuit::WitnessFiller, CircuitBuilder, Wire};
    use clap::Args;
    
    struct MyCircuitExample {
        params: Params,
    }
    
    #[derive(Args, Debug)]
    struct Params {
        #[arg(long, default_value_t = 1024)]
        max_size: usize,
        #[arg(long, default_value_t = false)]
        optimized: bool,
    }
    
    #[derive(Args, Debug)]
    struct Instance {
        #[arg(long)]
        input: Option<String>,
        #[arg(long)]
        size: Option<usize>,
    }
    
    impl ExampleCircuit for MyCircuitExample {
        type Params = Params;
        type Instance = Instance;
    
        fn build(params: Params, builder: &mut CircuitBuilder) -> Result<Self> {
            // 1. Add witnesses: builder.add_witness()
            // 2. Add constants: builder.add_constant_64()
            // 3. Create inouts: builder.add_inout()
            Ok(Self { params })
        }
    
        fn populate_witness(&self, instance: Instance, w: &mut WitnessFiller) -> Result<()> {
            // Process and validate instance data, then populate witness
            Ok(())
        }
    }
  11. Optimize Binius64 builds for target architectures

    main

    To enable architecture-specific optimizations (like SIMD) during compilation, export the RUSTFLAGS environment variable with target-cpu=native.

    When using Binius64 as a dependency in your own Rust project, it is recommended to enable Link Time Optimization (LTO) in your Cargo.toml to ensure optimizations are applied across crate boundaries.

    # Enable architecture optimizations
    export RUSTFLAGS="-C target-cpu=native"
    # Add to your Cargo.toml for cross-crate optimizations
    [profile.release]
    lto = "thin"
  12. Build Binius64

    main

    Use standard Cargo commands to build the project. For optimal performance on your local machine, export RUSTFLAGS with -C target-cpu=native to enable architecture-specific optimizations.

    export RUSTFLAGS="-C target-cpu=native"
    cargo build                    # Debug build
    cargo build --release          # Release build