1  # Groth.jl — Package Reference & Notes
  2  
  3  This is the canonical reference for the repository. Each package section lists
  4  its purpose, key modules, noteworthy implementation details (original notes are
  5  annotated rather than discarded), and follow-ups.
  6  
  7  ## GrothAlgebra
  8  
  9  **Purpose**
 10  - Prime-field arithmetic (BN254, secp256k1) plus generic polynomial and group
 11    utilities consumed by higher-level packages.
 12  
 13  **Key modules**
 14  - `src/FiniteFields.jl` — BigInt-backed fields with normalization, `invmod`,
 15    `powermod`, and display helpers.
 16  - `src/Polynomial.jl` — Degree/leading-coefficient management, Horner
 17    evaluation, Lagrange interpolation, derivative, FFT scaffolding.
 18  - `src/Group.jl` — Generic group/curve interface with scalar multiplication,
 19    w-NAF utilities, and MSM helpers.
 20  
 21  **Implementation notes**
 22  - (original) FFT helpers were stubs; dense interpolation handled `h(x)`.
 23  - (2025-09-29) Added `interpolate_prefix_points` so subset domains recover
 24    coefficients before padding for coset FFTs.
 25  
 26  **Follow-ups**
 27  - Evaluate FFT twiddle caching / mixed-radix support once the QAP domain aligns
 28    with arkworks.
 29  
 30  ## GrothCurves
 31  
 32  **Purpose**
 33  - BN254 tower fields, curve arithmetic, and pairing engine integration.
 34  
 35  **Key modules**
 36  - `src/BN254Fp2.jl`, `src/BN254Fp6_3over2.jl`, `src/BN254Fp12_2over6.jl` —
 37    Extension tower with optimized multiply/square/inverse.
 38  - `src/BN254Curve.jl` — G1/G2 Jacobian ops, generators, checks.
 39  - `src/BN254MillerLoop.jl`, `src/BN254FinalExp.jl`, `src/BN254Pairing.jl` —
 40    Optimal ate pairing pipeline and pairing engine wrapper.
 41  
 42  **Implementation notes**
 43  - Sparse Fp12 placement and Frobenius corrections follow standard BN254 refs.
 44  - Projective point abstraction (`ProjectivePoint{Curve,F}`) enables additional
 45    curve engines in future work.
 46  
 47  **Follow-ups**
 48  - Prototype a second curve/engine (e.g., BLS12-381) to validate abstractions.
 49  - Investigate GT cyclotomic optimisations if benchmarks surface bottlenecks.
 50  
 51  ## GrothProofs
 52  
 53  **Purpose**
 54  - R1CS/QAP conversion, Groth16 setup/prove/verify, and supporting tests.
 55  
 56  **Key modules**
 57  - `src/R1CS.jl`, `src/QAP.jl`, `src/Groth16.jl`.
 58  - Tests in `test/runtests.jl` and `test/random_circuits.jl`.
 59  
 60  **Implementation notes**
 61  - (original) QAP interpolation used dense Lagrange polys over `[1..n]`, with a
 62    future FFT path planned.
 63  - (2025-09-29) Coset path is default; dense vs coset equality asserted. Subset
 64    domains recover coefficients via barycentric interpolation before FFT (dense
 65    fallback retained for tests).
 66  - (TODO) Align evaluation domain population with arkworks (fill entire domain,
 67    drop barycentric shim).
 68  
 69  **Follow-ups**
 70  - Optional proof aggregation (arkworks-style) if bandwidth savings are needed.
 71  - Execute the domain-alignment work tracked in `docs/ROADMAP.md`.
 72  
 73  ## GrothExamples
 74  
 75  **Purpose**
 76  - Educational scripts matching the tutorial narrative.
 77  
 78  **Key modules**
 79  - `src/test_r1cs_qap.jl` — Prints domain/coset info plus coset vs dense parity.
 80  - `src/multiplication_proof.jl` — End-to-end Groth16 example.
 81  
 82  **Notes**
 83  - Scripts now print both coset/dense `h(x)` so learners see parity.
 84  - README highlights the coset quotient check.
 85  
 86  ## Benchmarks
 87  
 88  **Purpose**
 89  - `run.jl` / `plot.jl` microbenchmarks with JSON/PNG artefacts.
 90  
 91  **Notes**
 92  - Latest run: `results_2025-09-29_121914.json` (coset path default). README
 93    records medians; PNGs regenerated from this run.
 94  
 95  ## Docs
 96  
 97  - `docs/RareSkills_Groth16_Map.md` — RareSkills mapping (updated Sep 2025).
 98  - `docs/Implementation_vs_Arkworks.md` — Compare implementation choices with
 99    arkworks.
100  
101  ## Roadmap snapshot (see `docs/ROADMAP.md`)
102  
103  - Immediate: align QAP domain population with arkworks.
104  - Stretch: proof aggregation, pairing optimisations, second curve prototype.
105  
106  ---
107  
108  # Groth.jl — Repository Status and Pairings-Oriented Overview
109  
110  This document summarizes what’s implemented and well-documented in the repository, clarifies the mathematics versus representation and algorithm choices (with an emphasis on BN254 extension fields and pairings), and outlines concrete next steps to complete a functional Groth16 stack. Inline references point to files in this repo.
111  
112  ## Executive Summary
113  
114  - Solid foundation in finite fields, basic algebra, and polynomials: clear, documented implementations with tests in `GrothAlgebra`.
115  - BN254 curve, extension fields, and the BN254 optimal ate pairing are implemented end-to-end in `GrothCurves`:
116    - Fp2/Fp6/Fp12 extension tower with explicit formulas and optimized squarings.
117    - G1/G2 in Jacobian coordinates with addition/doubling.
118    - Miller loop with D-twist line placement and Frobenius correction steps.
119    - Final exponentiation (easy + hard parts) with Frobenius maps and precomputed twist constants.
120    - A large test suite exists under `GrothCurves/test` (good sign of maturity).
121  - R1CS and QAP conversion are present and readable in `GrothProofs`, but QAP uses a simplified evaluation domain and the Groth16 is a demonstrative, simplified version (not the full scheme yet).
122  
123  Overall, the pairing stack looks coherent and well structured; the proof system side needs domain/FFT upgrades and a production-level Groth16 (setup/prove/verify) to align with the mathematical design.
124  
125  ## What’s Well Implemented and Documented
126  
127  - Finite fields and polynomials (GrothAlgebra)
128    - `GrothAlgebra/src/FiniteFields.jl`: BigInt-backed prime fields (BN254 prime, secp256k1) with normalized arithmetic, inversion via `invmod`, power via `powermod`, plus helpful display and utilities. Clean docstrings and straightforward APIs.
129    - `GrothAlgebra/src/Polynomial.jl`: Polynomials over a field with degree/leading coefficient handling, Horner evaluation, Lagrange interpolation, derivative, and a placeholder for FFT multiply. Well commented; operations are correct and readable.
130    - `GrothAlgebra/src/Group.jl`: A generic `GroupElem` interface with scalar multiplication, w-NAF utilities, Straus MSM, and helpers. Clear documentation of expectations from concrete curve types.
131  
132  - BN254 extension tower and curve arithmetic (GrothCurves)
133    - `GrothCurves/src/BN254Fp2.jl`: Fp2 with u² = −1; real/imag accessors, conjugate, norm, inverse, Frobenius as conjugation. Docstrings explain representation and formulas.
134    - `GrothCurves/src/BN254Fp6_3over2.jl`: Fp6 over Fp2 via v³ = ξ with ξ = 9 + u (D-twist nonresidue). Uses Karatsuba-like multiplication and optimized squaring. Includes a clear `inv` via norm decomposition.
135    - `GrothCurves/src/BN254Fp12_2over6.jl`: Fp12 over Fp6 via w² = v. Optimized squaring and inversion, conjugation, and a baseline Frobenius (later enhanced by final exponentiation module).
136    - `GrothCurves/src/BN254Curve.jl`: G1 (over Fp) and G2 (over Fp2) in Jacobian coordinates with addition/doubling, affine conversion, curve membership checks, and standard generators. Nicely separated and easy to follow.
137    - `GrothCurves/src/BN254MillerLoop.jl`: Miller loop for the optimal ate pairing on BN254.
138      - D-twist line placement with explicit coefficient ordering, mixed addition, and careful mapping to sparse Fp12 coordinates in `evaluate_line`.
139      - Frobenius-based endomorphism on G2 using constants (`P_POWER_ENDOMORPHISM_COEFF_*`) from known references, and the NAF loop count for u.
140    - `GrothCurves/src/BN254FinalExp.jl`: Final exponentiation split into easy and hard parts.
141      - Precomputes sextic-twist Frobenius `γ` constants (GAMMA1/2/3) and provides `frobenius_p1/p2/p3` for Fp12.
142      - Implements the standard BN254 exponentiation ladder (`exp_by_u`, y₀..y₆ combination) consistent with literature.
143    - `GrothCurves/src/BN254Pairing.jl`: Composes Miller loop + final exponentiation into `optimal_ate_pairing`, plus batch pairing.
144  
145  - R1CS and QAP (GrothProofs)
146    - `GrothProofs/src/R1CS.jl`: Clean R1CS representation with constraint checking and an example circuit (r = x·y·z·u). Well-documented and approachable.
147    - `GrothProofs/src/QAP.jl`: Readable R1CS→QAP conversion via Lagrange interpolation and direct polynomial division for h(x). The domain is simplified to integers `[1..n]` (works for pedagogy; needs true roots-of-unity domain for FFT acceleration later).
148    - `GrothProofs/src/Groth16.jl`: A simplified, educational Groth16 (CRS, prove, verify) that demonstrates the flow but is intentionally not the full construction.
149  
150  [... original deep-dive continues ...]
151  
152  ## BN254 Field Extensions, Tower, and Pairing: A Focused Overview
153  
154  This section distinguishes between (a) the math we need, (b) representation options, and (c) algorithmic choices taken here, with references.
155  
156  ### The Math We Need
157  
158  - Fields and Tower
159    - Base field: Fp with BN254 prime p. See `BN254_PRIME` in `GrothCurves/src/BN254Fp2.jl` and field arithmetic in `GrothAlgebra/src/FiniteFields.jl`.
160    - Quadratic extension: Fp2 = Fp[u]/(u² + 1). Elements are a + b·u.
161      - Multiplication: (a₀ + a₁u)(b₀ + b₁u) = (a₀b₀ − a₁b₁) + (a₀b₁ + a₁b₀)u.
162      - Conjugate: \(\overline{a + bu} = a - bu\).
163      - Norm: \(N(a + bu) = a^2 + b^2\).
164      - Inverse: \((a + bu)^{-1} = (a - bu)/(a^2 + b^2)\).
165    - Fp6 = Fp2[v]/(v³ - ξ) with ξ = 9 + u; split into cubic extension over Fp2.
166    - Fp12 = Fp6[w]/(w² - v); final extension needed for GT.
167  
168  - Curve Groups
169    - G1: E(Fp) defined by y² = x³ + b with b = 3.
170    - G2: defined over Fp2, using the sextic twist.
171  
172  - Pairing
173    - Optimal ate pairing e : G1 × G2 → GT with embedding degree 12.
174    - Follows standard loop count (six bits of BN parameter u in NAF form) with Frobenius corrections.
175  
176  ### Representation Options (semantics-preserving)
177  
178  - Field elements stored as small static tuples (`SVector`) to keep heap allocations down.
179  - G1/G2 stored in Jacobian coordinates (X:Y:Z) with the curve parameter a = 0 simplifying formulas.
180  - Fp12 stored as `Fp6_c0 + Fp6_c1 · w` with Fp6 stored as three Fp2 elements.
181  
182  ### Algorithmic Choices (performance / implementation detail)
183  
184  - Fp2/Fp6/Fp12 multiplication uses Karatsuba-like decompositions and leverages nonresidue relationships to cut multiplications.
185  - Miller loop uses sparse line evaluation and explicit negation steps to minimise Fp12 multiplies.
186  - Final exponentiation uses Frobenius maps for the easy part and a standard BN ladder for the hard part (`exp_by_u`, `frobenius_p1/p2/p3`).
187  - MSM and fixed-base tables currently live in `GrothAlgebra/src/Group.jl` with Straus-style combination; Pippenger and w-NAF tables remain on the roadmap.
188  
189  ## Where We Are vs. What’s Left for Groth16
190  
191  - Groth16 pipeline (CRS, prove, verify) is educationally complete but needs FFT-backed domain alignment to match arkworks (work in progress).
192  - Coset FFT path is implemented and default; dense path survives only for assertions/tests.
193  - Prepared verifier matches arkworks’ prepared path (batched pairing with a single final exponentiation).
194  - Proof aggregation is still outstanding.
195  
196  ## Implementation-Focused Math Notes (with Repo Mapping)
197  
198  - Fp2 arithmetic (BN254, u² = −1) — `BN254Fp2.jl`
199    - \((a_0 + a_1 u)(b_0 + b_1 u) = (a_0 b_0 - a_1 b_1) + (a_0 b_1 + a_1 b_0) u)\).
200    - Conjugate \(\overline{a_0 + a_1 u} = a_0 - a_1 u\) and norm \(N(a) = a_0^2 + a_1^2\).
201  - Fp6 over Fp2 via v³ = ξ (ξ = 9 + u) — `BN254Fp6_3over2.jl`
202    - Elements \(c_0 + c_1 v + c_2 v^2\) with Karatsuba cross-terms folded via ξ.
203  - Fp12 over Fp6 via w² = v — `BN254Fp12_2over6.jl`
204    - Multiplication reduces `(d0 + d1w)(e0 + e1w)` using the relation w² = v.
205  - G1/G2 Jacobian formulas — `BN254Curve.jl`
206    - Doubling: `M = 3X^2`, `S = 4XY^2`, etc. Mixed addition leverages affine second operand.
207  - Miller loop — `BN254MillerLoop.jl`
208    - D-twist line evaluation, sparse Fp12 multiplication, Frobenius corrections.
209  - Final exponentiation — `BN254FinalExp.jl`
210    - Easy part (`(f^p^6 / f)` etc.) and hard part via Frobenius + `exp_by_u` combos.
211  
212  ## Practical Distinctions: Math vs. Representation vs. Algorithms
213  
214  - **Math invariants** — group laws, pairing bilinearity, field identities.
215  - **Representation** — coordinate systems, tower shapes, data layout; doesn’t change correctness but impacts performance.
216  - **Algorithms** — Karatsuba, sparse Fp12 ops, NAF loops, w-NAF MSM, etc.
217  
218  ## Glossary of Notation
219  
220  - Fp, Fp2, Fp6, Fp12: Base and extension fields.
221  - G1, G2: Curve groups used in Groth16.
222  - GT: Multiplicative subgroup of Fp12 where the pairing lands.
223  
224  ## Concrete Next Steps Checklist
225  
226  - [x] Coset FFT path default with dense assertion.
227  - [ ] Align QAP domain population with arkworks.
228  - [ ] Implement Pippenger MSM (variable/fixed base) and use in prover/setup.
229  - [ ] Prototype second pairing engine (BLS12-381).
230  - [ ] Port proof aggregation.
231  
232  ## Pointers Into This Repo
233  
234  - `GrothAlgebra/src/*.jl`
235  - `GrothCurves/src/BN254*.jl`
236  - `GrothProofs/src/*.jl`
237  - `GrothExamples/`
238  - `benchmarks/`
239