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.
- ZCG GitHub Application (#590): Grant Application - halo2-bilinear-opt: Certified Pairing & Pasta Wrong-Field Gadgets for Zcash Halo2 and Tachyon · Issue #590 · ZcashCommunityGrants/zcashcommunitygrants · GitHub
- Open-Source Repository & Working
#![no_std]Prototype (rust_crates/src/halo2_gadgets.rs): GitHub - Impius-Lab/zk-bilinear-opt: Certified optimal extension-field and non-native pairing gadgets for STARK/SNARK verifiers (QM31, Plonky3, BN254, BLS12-381) · GitHub
Applicant & Grant Overview
- Applicant: Houssem Aguentil (
Individual— Independent Cryptographic Researcher,Impius-Lab) - Requested Amount: USD 30,000 (
USD 0upfront startup funding; two delivery-verified milestones ofUSD 15,000each over 8 weeks) - License: Dual-licensed
MIT OR Apache-2.0(matchingzcash/librustzcash,zcash/halo2, andzkcrypto/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:
- Pareto-Optimal
BLS12-381Non-NativeCRT-30& Native Unimodular Towers:- In non-native
Halo2limb chips (5x88-bit and6x64-bit over 255-bitPastaacrosslookup_bitsin{8, 12, 16}),CRT-30requires 0 pre-multiplication modular reductions and cutsBLS12-381Fp12PlonKish cells by 24.49% to 29.85% (e.g.,33,787 -> 24,475cells at16b/88b). - In native scalar/deferred contexts, unimodular (
det = +-1) basis isomorphisms achieveFp6Rank-11 (18 -> 11,-38.89%),Fp12Rank-23 (54 -> 23,-57.41%), and sparse Miller-loopmul_by_014Rank-18 / Rank-19 / Rank-21 (-61.11%to-66.67%).
- In non-native
- Exact
quoBits&crtLowCarriesWrong-Field Tightening:- Porting our exact integer quotient-width (
packLimbsWithWidth) and CRT low-carry bounds fromConsensys/gnark#1951cutsPastawrong-field multiplication cells by 9.94% to 13.05% while statically preventing excess-quotient-bit modulo-qwrap-around.
- Porting our exact integer quotient-width (
- Zero-
sorryCore Lean 4 Soundness Proofs:- Self-contained Core Lean 4 formal verification (
lake buildin< 6s,0sorry,0customaxioms) already live inlean4_certs/forM31/QM31and non-native CRT quotient uniqueness, which Milestone 2 extends to allPastaandBLS12-381tower and CRT bounds.
- Self-contained Core Lean 4 formal verification (
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!