# R1CS-NARK accumulation: accumulate one proof, fold more in, decide once.
#
# Accumulation's whole promise is deferral. A NARK proof commits to A·z, B·z, C·z
# with three size-n MSMs; checking k proofs the naive way costs 3k of them. An
# accumulation scheme instead FOLDS each new proof into a running accumulator with
# only in-circuit work — no size-n MSM — and pays the six-MSM decider exactly
# once, at the very end. So k proofs cost one decide, not k.
#
# The statement, per proof: "I know a secret seed w_0 whose chain w <- (w + 5)*w
# lands on the public `out` after N steps." R1CS writes that as three matrices
# over z = public ‖ witness, each row asserting (A·z)_i * (B·z)_i = (C·z)_i.
#
# The Fiat-Shamir challenges that bind each fold come from the SAME instantiated
# Poseidon the prover uses everywhere here — arkworks' PoseidonSponge<Fq>, shipped
# in-package (sponge.default_params), so nothing below needs a fixture.
#
# Everything is plain accumulation-zorch; change N (or PALLAS -> VESTA) and re-run.
import numpy as np

from accumulation_zorch import curve, r1cs_nark_as, sponge
from accumulation_zorch.curve import PALLAS as cv

N = 16  # chain steps = R1CS rows = the size of each commitment MSM

# A committer key: one base per row, plus a hiding base for the zk blinders. The
# g1 dtype reads an integer k as k·G, so this is [1·G .. (N+1)·G] — enough to
# exercise the commitments, but deliberately NOT a sound Pedersen key: these bases
# have known discrete-log relations (G_i = i·G), which is exactly what binding
# forbids. A real key comes from a setup with unknown relations.
bases = list(np.arange(1, N + 2, dtype=cv.g1))
generators, hiding = bases[:N], bases[N]

# z = [1, out] ‖ [w_0 .. w_{N-1}]: wire 0 is the constant 1, wire 1 the public
# output, the rest the secret chain. A adds 5·1 to w_i and B selects w_i, so the
# Hadamard product is (w_i + 5)·w_i; C names the next wire, and the last row names
# `out`, pinning the chain to the public value.
W = 2
a = [[(1, W + i), (5, 0)] for i in range(N)]
b = [[(1, W + i)] for i in range(N)]
c = [[(1, W + i + 1)] for i in range(N - 1)] + [[(1, 1)]]

# fr elements reduce mod r, so no explicit modulus; the prover canonicalizes them.
witness = [cv.fr(3)]
for _ in range(N - 1):
    witness.append((witness[-1] + cv.fr(5)) * witness[-1])
public = [cv.fr(1), (witness[-1] + cv.fr(5)) * witness[-1]]

params = sponge.default_params(cv)   # the in-package ark-sponge Poseidon
rng = np.random.default_rng(0)


def prove_step(acc=None):
    """Accumulate the statement, or fold it into `acc`, on fresh randomness."""
    rnd = r1cs_nark_as.sample_randomness(cv, rng, len(witness))
    args = (cv, a, b, c, public, witness, generators, hiding, params, N)
    if acc is None:
        return r1cs_nark_as.accumulate(*args, rnd)[0]
    return r1cs_nark_as.fold(*args, acc, rnd)[0]


def decider_accepts(acc):
    """ASForR1CSNark::decide — re-derive the six commitments from the
    accumulator's witness and check they equal the ones it carries. This is the
    whole deferred cost, paid once no matter how many proofs were folded in."""
    got = r1cs_nark_as.decide(cv, a, b, c, generators, hiding, acc.to_decide())
    return all(curve.point_to_bytes(cv, g) == curve.point_to_bytes(cv, s)
               for g, s in zip(got, acc.comms))


acc = prove_step()          # accumulate proof #1
for _ in range(3):          # fold proofs #2..#4 in — each is only in-circuit work
    acc = prove_step(acc)

forged = acc.blinded_witness.copy()
forged[0] = forged[0] + cv.fr(1)
tampered = acc._replace(blinded_witness=forged)
print(f"accumulator after 1 accumulate + 3 folds, {N} constraints each")
print("decider accepts the accumulator:       ", decider_accepts(acc))
print("decider accepts a tampered accumulator:", decider_accepts(tampered))

accumulation-zorch

A GPU accumulation prover over the Pasta curve. The arkworks ark-accumulation native prove path (r1cs_nark_as + hp_as), with the whole prover authored in Python/FRX and compiled to a single fused GPU kernel — byte-identical to the reference arkworks prover.

The GPU prove path is fused (src/fused.rs): the frx port of the prove (python/accumulation_zorch/) — every commitment, the NARK + HP cores, and all three Fiat-Shamir Poseidon sponges — is exported to one StableHLO .mlirbc (export/export_prove.py) and run as a single PJRT call, à la bellman-zorch. Rust is a thin consumer that feeds the committer key + assignment/randomness and re-serializes the output. The assignment + all replayed randomness are runtime PJRT inputs, so one exported core proves any statement (not a fixture replayer).

The byte-match oracle is the pristine, unmodified arkworks prover itself (the ark-accumulation dev-dependency at ../accumulation); the repo never re-implements it. The fixture generators (examples/dump_*.rs and tests/recursion_step.rs) drive arkworks to emit the golden (acc.instance ‖ acc.witness ‖ proof) bytes, and the frx CPU port + the fused GPU core are each gated byte-for-byte against those golden bytes.

Accumulation schemes

Two ark-accumulation schemes are ported, each a fused GPU core byte-identical to the unmodified arkworks prover over the Pasta cycle (Pallas + Vesta):

• r1cs_nark_as (+ its hp_as Hadamard-product sub-step) — the R1CS-NARK accumulation the Pasta-cycle recursion uses. The whole zk prove — every commitment, the NARK + HP cores, all three Fiat-Shamir sponges — is one fused PJRT call. The prover is MSM-heavy (big Pedersen witness commitments), so the GPU win is the prove itself (the "Single AS prove" benchmark; the recursion IVC fold wins by less — accumulation is light by design, deferring verification).
• ipa_pc_as — the IPA-PC (Halo / DL-style) accumulation of BCMS20, prove + decide, no-zk and zk. Here the prover is field-heavy (building the degree-d check polynomial) with only small MSMs; the heavy size-d MSM is the decider (final_comm_key == ⟨combined_check_poly_coeffs, generators⟩). So the decider MSM is the GPU-value op — a pure MSM that scales far better than the fold (the "Decider size-d MSM" benchmark). The IPA-PC prover/verifier primitive itself (commit / open fold / reduce) is zorch's zorch.pcs.ipa (a pinned Bazel dependency — git_override in MODULE.bazel), driven by an arkworks-faithful challenger (ipa_challenger.py); ipa_pc_as supplies only the accumulation scheme on top.

The in-circuit verifier gadgets are reused from ark-accumulation as-is (they have no prover MSM); the repo re-derives neither.

Setup

Clone this repo and the arkworks oracle side by side, then cd in. They must be siblings because the crate's dev-dependency points at ../accumulation:

git clone https://github.com/fractalyze/accumulation-zorch
git clone https://github.com/arkworks-rs/accumulation
git -C accumulation checkout 4a680af   # the revision the crate's ark-* 0.2 deps build against
cd accumulation-zorch

Run every command below from inside accumulation-zorch/. The other git deps (ark-sponge / ark-poly-commit, on their accumulation-experimental branches) are fetched by Cargo automatically — only accumulation is a manual clone.

Reproduction has two layers: a Rust toolchain regenerates the golden fixtures by driving the pristine arkworks prover directly (no GPU, no Python); the frx byte-match then checks the port against them. The frx port builds under Bazel (zorch and the xla Pasta frx build are Bazel deps), so the CPU byte-match needs only Bazel; the GPU byte-match additionally needs the xla Pasta GPU plugin.

Regenerate the golden fixtures (Rust only — no GPU, no Python)

Just a Rust toolchain. The fixture generators (examples/dump_*.rs, tests/recursion_step.rs) drive the unmodified ../accumulation prover, so they compile ../accumulation — which needs RUSTFLAGS="--cap-lints=warn" (arkworks' #![deny(warnings)] breaks modern rustc). The commands are under Reproduce; plain cargo build / cargo test (the crate's own suite) need no extra flags.

CPU byte-match (Bazel)

The frx port and its byte-match tests build under Bazel — no venv, no PYTHONPATH, nothing vendored in-tree. zorch (the IPA-PC prover/verifier + Poseidon sponge) is a pinned git_override dependency and the xla Pasta frx build is pulled from the public Fractalyze index through Bazel's pip hub. Install Bazel via bazelisk (.bazelversion pins the version), then:

bazel test //python/...   # the full CPU byte-match suite (FRX_PLATFORMS=cpu, set in .bazelrc)

The pinned xla Pasta frx build registers the Pasta curve dtypes and zk-dtypes carries them; both are pinned in requirements.in (locked in requirements_lock_3_11.txt). bazel test //python/... is 20/20 byte-match vs arkworks (Pallas + Vesta, no-zk + zk); it excludes the three manual-tagged recursion gates, which byte-match at recursion-circuit scale against large off-tree fixtures no clean checkout has (see python/accumulation_zorch/testing/BUILD.bazel). To bump the zorch pin, edit the git_override commit in MODULE.bazel and keep requirements.in's frx / zk-dtypes in lockstep (both this repo's pip hub and zorch's must resolve frx to the same wheel), then bazel run //:requirements.update. For dev against a local zorch checkout, add common --override_module=zorch=/abs/path/to/zorch to .bazelrc.user.

GPU byte-match tier (the xla Pasta GPU plugin)

The GPU byte-match is the Rust side (cargo test --features gpu, hardware-gated). It needs an NVIDIA GPU (CUDA), clang/libclang (the xla-pjrt shim generates its PJRT bindings with bindgen at build time), and the xla Pasta GPU PJRT plugin .so. Install the plugin from the public Fractalyze index into a venv and point XLA_PJRT_PLUGIN at it:

# Take frx / zk-dtypes from requirements.in so the plugin stack can't drift from
# what the Bazel tier lowers the .mlirbc with. The frx-cuda12 wheels ship in
# lockstep with frx, so they carry the same version.
FRX_VER=$(grep '^frx==' requirements.in | cut -d= -f3)
ZK_VER=$(grep '^zk-dtypes==' requirements.in | cut -d= -f3)

uv venv --python 3.11 .venv
uv pip install --python .venv --index-strategy unsafe-best-match \
  --index-url https://fractalyze.github.io/pypi/simple/ \
  --extra-index-url https://pypi.org/simple/ \
  "frx==$FRX_VER" "frxlib==$FRX_VER" \
  "frx-cuda12-pjrt==$FRX_VER" "frx-cuda12-plugin==$FRX_VER" \
  "zk-dtypes==$ZK_VER" numpy absl-py
export XLA_PJRT_PLUGIN=$PWD/.venv/lib/python3.11/site-packages/frx_plugins/xla_cuda12/xla_cuda_plugin.so

The frx lowering to StableHLO .mlirbc runs under Bazel (bazel run //export:export_*), so it needs no venv — only the GPU run loads the plugin.

Reproduce

Regenerate the golden fixtures from arkworks (fully external)

The golden (acc.instance ‖ acc.witness ‖ proof) bytes the byte-match tests check against are produced by driving the unmodified arkworks prover — no GPU, no Python (the generators compile ../accumulation, hence --cap-lints=warn):

RUSTFLAGS="--cap-lints=warn" cargo run --example dump_as_zk > python/testdata/as_zk_fixtures.json
# regenerates the committed golden; a clean `git diff` confirms it still matches arkworks

Python frx prove byte-match (CPU)

The frx port reproduces the arkworks (acc.instance ‖ acc.witness ‖ proof) bytes on CPU (the same trace the GPU export lowers) — run one test, or the whole suite:

bazel test //python/accumulation_zorch/testing:as_zk_test   # one test
bazel test //python/...                                      # the full 20-test suite
# seed 0 / 42: (acc.instance 398B ‖ acc.witness 922B ‖ proof 482B) byte-matches arkworks

Fused GPU byte-match (one core proves every seed)

# 1. Lower the ONE general fused core (CPU; no GPU needed for lowering). Bazel
#    supplies zorch + the frx fork; ACCUMULATION_ZORCH_ARTIFACTS picks the out dir.
ACCUMULATION_ZORCH_ARTIFACTS=artifacts FRX_PLATFORMS=cpu \
  bazel run //export:export_prove              # -> artifacts/prove_zk_general.mlirbc
ACCUMULATION_ZORCH_ARTIFACTS=artifacts FRX_PLATFORMS=cpu \
  bazel run //export:export_prove -- no-zk     # -> artifacts/prove_no_zk_general.mlirbc

# 2. GPU byte-match: the one core, fed each seed's witness/randomness at run time.
#    (`XLA_PJRT_PLUGIN` is read from the Setup export; --nocapture shows the
#     per-seed "byte-matches arkworks" lines)
cargo test --features gpu --test gpu_fused_prove_byte_match -- --ignored --test-threads=1 --nocapture
cargo test --features gpu --test gpu_fused_no_zk_prove_byte_match -- --ignored --test-threads=1 --nocapture

Benchmark

Every accumulation scheme has two operations with opposite GPU stories: accumulate (the per-step prove / IVC fold, which defers verification) and decide (the deferred check, run once at the end). The two schemes sit at opposite ends — R1CS-NARK's prover is MSM-heavy (so accumulate already wins on GPU), while IPA-PC's prover is field-heavy with only small MSMs (so the GPU win is the decider) — but both deciders are MSM-bound, and that is where the GPU advantage is largest. Numbers are RTX-5090-class GPU; the fused GPU output byte-matches arkworks at every size.

R1CS-NARK — accumulate

Single AS prove (one input). Fused GPU prove (one PJRT call, warm) vs the arkworks AS prove (CPU, --release), as the circuit size n (num_constraints) grows:

• The GPU prove is a flat ~659 ms floor — 8× more MSM work (4 096 → 32 768) moves it +2%. It is GPU-compute-bound (the Pippenger bucket-reduction MSM kernel + the Poseidon Fiat-Shamir sponge + dispatch), not transfer. The five sequential Pasta MSMs and the composite sponge are the optimization target.
• The CPU prove is ~O(n) (MSM-bound). Crossover ≈ n ≈ 8 K; the GPU win grows with size.
• Reproduce: PROVE_SIZES="4096 16384 32768" bench/bench.sh prove (or bench/bench.sh all). Needs an idle GPU + the XLA_PJRT_PLUGIN env from Setup; the frx lowering runs via bazel run //export:....

Recursion IVC fold. The actual PCD step — fold one verifier-circuit NARK proof into a prior accumulator (num_addends = 3), at recursion scale (n = 77 556):

The fold's GPU win is smaller than the single prove's because per-step accumulation is light by design — it defers verification to the decider, so proportionally less of the step is the MSM-heavy work the GPU wins on. Reproduce: bench/bench.sh fold.

R1CS-NARK — decide

The deferred verification the accumulate step set up: recompute the six size-n Pedersen commitments — comm_{a,b,c} = commit(M·z, σ) and the hp_as check's test_comm_{1,2,3} = commit(a_vec, ρ₁), commit(b_vec, ρ₂), commit(a_vec∘b_vec, ρ₃) — and accept iff they equal the accumulator's stored commitments. The six MSMs run as one fused PJRT call vs the CPU's six sequential variable-base MSMs:

• The GPU is a slow-growing floor (18 → 54 ms over 16× the points) while the CPU is O(6·n); the win grows from 29× to 117×. Fusing the six MSMs into one call (vs six separate CPU MSMs) compounds the per-MSM GPU advantage — the largest GPU win of any operation here.
• One lowered core is curve-generic and zk-agnostic: the same as_decider_<curve>.mlirbc decides both the no-zk and zk accumulators (the randomizers σ / ρ are runtime inputs, 0 on the no-zk path). Each row gates GPU == arkworks at scale.
• Reproduce: bench/bench.sh r1cs-decide (sizes from R1CS_DECIDE_SIZES).

IPA-PC — decide

The IPA-PC prover is field-heavy (building the degree-d check polynomial) with only small MSMs, so — mirror-image to R1CS-NARK — the GPU-value op is the decider's size-d MSM (final_key = Σ generatorsᵢ·coeffsᵢ), not the accumulate step:

• The GPU MSM is a ~16-18 ms floor at these sizes (the Pippenger bucket-reduction kernel), so 4× the points (2¹⁴→2¹⁶) barely moves it while the CPU MSM is O(d) — the win grows from 5.3× to 34.9× across the sweep.
• The decider MSM core is curve-specific but zk-agnostic: the same lowered lax.msm decides both no-zk and zk accumulators (the zk-ness is in the host-computed coefficients). Each row gates GPU == arkworks at scale.
• Reproduce: bench/bench.sh decide (sizes from DECIDE_SIZES).

IPA-PC — accumulate

The accumulate completes the matrix: the AS prove (combine several inputs' succinct checks into one accumulator) and the fold (accumulate one input INTO a prior accumulator — old_accumulators non-empty, the IVC step). An accumulator is an InputInstance of the same shape as an input, so arkworks succinct-checks the inputs then the accumulators into one list and combines them identically — the fold is the prove fed [inputs…, accumulators…], a prior hiding accumulator's succinct check taking the zk path.

The fold's IpaPC::open is sequential — each round's Fiat-Shamir challenge is squeezed from that round's L/R fold commitments, so the per-round MSMs and the Poseidon sponge interleave with a two-way data dependency (the MSMs need the prior challenge; the next challenge needs the MSMs). There is no host-challenge shortcut like the decider has, so the fused fold core runs the whole open on-device — the lax.scan basis fold, the Poseidon sponge squeezed on-device per round, and the final_comm_key MSM — as one PJRT call (fused::open_ipa_fold_fused, export/export_ipa_fold.py). It byte-matches the golden folded accumulator's IPA proof (l_vec/r_vec/final_comm_key/c) over both curves — and the zk twin (ipa_fold_zk_<curve>.mlirbc, the hiding prelude + blinded fold) additionally reproduces hiding_comm/rand, completing no-zk + zk on GPU:

• That ~255 ms is a fixed floor — the Pippenger bucket-reduction MSM kernel is size-independent (the same ~100 ms-class floor the R1CS prove hits), and the accumulate's MSMs are tiny (8 coeffs), so the run is dominated by dispatch + kernel overhead and does not beat the CPU open at accumulate scale. That is the result: the accumulate is host/overhead-bound by design — accumulation defers verification — so the GPU-value op for IPA-PC is the decider above, mirror-image to R1CS-NARK where it is the accumulate.
• The CPU port is curve-generic and zk-agnostic in structure: prove and fold, no-zk and zk, Pallas and Vesta all run the one combine + IpaPC::open, each byte-matched to arkworks; the fused GPU fold core covers the fold both no-zk and zk (both curves).
• Reproduce: ipa_as_test.py (prove) and ipa_as_fold_test.py / ipa_as_fold_zk_test.py (fold), the CPU byte-match (run as in Python frx prove byte-match); the GPU fold byte-matches + bench are gpu_fused_ipa_fold_byte_match / gpu_fused_ipa_fold_zk_byte_match / gpu_fused_ipa_fold_bench (as in Fused GPU byte-match).