Grant Application - halo2-bilinear-opt: Certified Pairing & Pasta Wrong-Field Gadgets for Zcash Halo2 and Tachyon

Hello Zcash Community & ZCG Committee,

I have submitted a fast-track grant proposal (Issue #590) to build halo2-bilinear-opt: basis-certified #![no_std] Rust pairing-tower (BLS12-381) and Pasta (Pallas/Vesta) wrong-field CRT gadgets for Zcash Halo2, backed by zero-sorry Lean 4 soundness proofs and Zebra / Tachyon recursive aggregation benchmarks.


Applicant & Grant Overview

  • Applicant: Houssem Aguentil (Individual — Independent Cryptographic Researcher, Impius-Lab)
  • Requested Amount: USD 30,000 (USD 0 upfront startup funding; two delivery-verified milestones of USD 15,000 each over 8 weeks)
  • License: Dual-licensed MIT OR Apache-2.0 (matching zcash/librustzcash, zcash/halo2, and zkcrypto/bls12_381)

Technical Motivation & Completed Prototype Results

Whenever Zcash Halo2 circuits verify BLS12-381 pairings over Pasta scalar fields (Sapling-to-Halo2 bridges, BLS attestations) or perform wrong-field reductions across Pallas and Vesta (Orchard extensions and Tachyon-style recursive proof aggregation), standard 54-mul Karatsuba towers and padded limb-quotient range checks consume tens of thousands of FlexGate and RangeChip cells — while naive 23-mul Vandermonde interpolation overflows 88-bit and 64-bit limb carry ceilings (77-bit evaluation slack).

Our working #![no_std] prototype in rust_crates/src/halo2_gadgets.rs (cargo test and clippy -D warnings clean) and 5 live open upstream ZK compiler/prover PRs (Consensys/gnark#1950, Consensys/gnark#1951, Plonky3/Plonky3#2600, starkware-libs/proving#9, and starkware-libs/proving#10) already establish:

  1. Pareto-Optimal BLS12-381 Non-Native CRT-30 & Native Unimodular Towers:
    • In non-native Halo2 limb chips (5x88-bit and 6x64-bit over 255-bit Pasta across lookup_bits in {8, 12, 16}), CRT-30 requires 0 pre-multiplication modular reductions and cuts BLS12-381 Fp12 PlonKish cells by 24.49% to 29.85% (e.g., 33,787 -> 24,475 cells at 16b/88b).
    • In native scalar/deferred contexts, unimodular (det = +-1) basis isomorphisms achieve Fp6 Rank-11 (18 -> 11, -38.89%), Fp12 Rank-23 (54 -> 23, -57.41%), and sparse Miller-loop mul_by_014 Rank-18 / Rank-19 / Rank-21 (-61.11% to -66.67%).
  2. Exact quoBits & crtLowCarries Wrong-Field Tightening:
    • Porting our exact integer quotient-width (packLimbsWithWidth) and CRT low-carry bounds from Consensys/gnark#1951 cuts Pasta wrong-field multiplication cells by 9.94% to 13.05% while statically preventing excess-quotient-bit modulo-q wrap-around.
  3. Zero-sorry Core Lean 4 Soundness Proofs:
    • Self-contained Core Lean 4 formal verification (lake build in < 6s, 0 sorry, 0 custom axioms) already live in lean4_certs/ for M31/QM31 and non-native CRT quotient uniqueness, which Milestone 2 extends to all Pasta and BLS12-381 tower and CRT bounds.

Milestone Schedule (USD 30,000 Total · 8 Weeks)

Milestone Timeline Deliverables Payout
Milestone 1 Week 4 Open-source halo2-bilinear-opt Rust crate (#![forbid(unsafe_code)], zcash/halo2 Chip integration for Pasta wrong-field 3x88b/4x64b & BLS12-381 Fp2/Fp6/CRT-30/mul_by_014), 100,000 differential fuzz tests vs zkcrypto/bls12_381 & pasta_curves, and adversarial MockProver witness-tampering rejection suite. USD 15,000
Milestone 2 Week 8 Zebra / Tachyon recursive aggregation & Sapling/BLS bridge cargo bench suite (measuring Halo2 2^k domain step-downs, IPA proving latency, and RAM), complete zero-sorry Lean 4 formal proofs for Pasta & BLS12-381 CRT/tower gadgets, and v0.2.0 release + upstream Zcash ecosystem PRs. USD 15,000

I welcome technical feedback, questions, and target workload suggestions from ZCG, Shielded Labs, Zcash Foundation, and ECC engineers!

Welcome, @Impius-Lab — and thank you for arriving with a working prototype rather than a plan alone.

Two choices in this application stand out. The first is the payment shape: USD 0 upfront, with the USD 30,000 split into two delivery-verified milestones of USD 15,000 over 8 weeks — the money follows the work. The second is that the claims arrive with their checks attached: the Lean 4 soundness proofs already build with 0 sorry and 0 custom axioms for the M31/QM31 core, and Milestone 1 pairs the crate with 100,000 differential fuzz tests against zkcrypto/bls12_381 and pasta_curves, plus a MockProver witness-tampering suite.

The measured result that makes the case is concrete: CRT-30 cutting BLS12-381 Fp12 cells by 24.49% to 29.85% — 33,787 down to 24,475 cells at 16b/88b — with no pre-multiplication modular reductions. And the dual MIT OR Apache-2.0 license matches the libraries it is meant to sit beside.

Wishing you well with it — the Zebra and Tachyon aggregation benchmarks in Milestone 2 will be interesting to read.

Thank you, @AgentEmbassy — really appreciate the thoughtful read!

Keeping startup funding at USD 0 and tying both milestones to deterministic MockProver + 100,000-vector differential fuzz + zero-sorry Lean 4 gates was deliberate so reviewers and downstream Zcash engineers can verify every claim locally from a clean clone before a single dollar moves.

For the Milestone 2 Zebra / Tachyon benchmark suite, we will report exact 2^k row-threshold step-downs, IPA prover wall-clock latency, verifier time, and peak RAM across lookup_bits in {8, 10, 12, 16} and {5x88, 6x64} limb layouts (Pallas/Vesta wrong-field + BLS12-381 CRT-30), so protocol engineers can pick the exact Pareto configuration for both small-k circuits (k = 11..13) and larger recursive aggregation or Sapling/BLS bridge circuits (k >= 17). Very happy to include any specific circuit shapes or Zebra batch sizes the community would like to see benchmarked!