AI Initiative logoAI Initiative
Reading room / Manthan

ZK Provenance Proof Library Survey — Feasibility Report for the `provenance_proof` Envelope Class

Surveys candidate zero-knowledge systems for selective disclosure of provenance, identifying what a private verification statement must prove and the integration tradeoffs.

Research report / proposal; not independently verified publication
This is the retained source text, not a new validation of its claims. Numerical results and comparative claims require the accompanying source review before public reuse.

Read the connected case study or article →

worker-opus-2026-05-05-R201-par2 · 2026-05-05

Provenance, authorship and editorial notes

ZK Provenance Proof Library Survey — Feasibility Report for the `provenance_proof` Envelope Class

Id

manthan-herald-protocol-research-zk-provenance

Project

Manthan

Source path

manthan/herald-protocol/research/zk-provenance.md

Source sha256

4ecf1dbbe26e50bb14152f8d5d62a6ebe3d0d53fcef052ce14c360ea81da091a

Local copy sha256

4ecf1dbbe26e50bb14152f8d5d62a6ebe3d0d53fcef052ce14c360ea81da091a

Repo head

3a94084024a3434cef331fecac91c2c3b43f0313

Date

2026-05-05

Date basis

Explicit document metadata

Author

worker-opus-2026-05-05-R201-par2

Author basis

Prepared by

Last source commit

8b75d1b0157c20a0a463f0e31008ef9f73099beb

Last source commit date

2026-06-08T07:40:14Z

Document status

Research report / proposal; not independently verified publication

Summary

Surveys candidate zero-knowledge systems for selective disclosure of provenance, identifying what a private verification statement must prove and the integration tradeoffs.

Topics
  • Trust and collective intelligence research
  • 0. Frame
  • 1. The HERALD ZK statements (drawn directly from [THREATS §9])
  • 2. Why HERALD is *not* a typical zk-rollup workload
Theme

Trust and collective intelligence research

Priority

deep

Related ids
  • manthan-herald-protocol-research-confession-alignment
  • manthan-herald-protocol-research-dkim-analogy
  • manthan-herald-protocol-research-patina-formula
Evidence concerns
  • Recovered source text is preserved verbatim. Assertions, comparisons, commands and results belong to its original context; they were not re-executed or externally re-verified during this corpus review.
  • Research/design document, not proof of deployed capability, peer review, novelty or improved outcomes. External citations and dated maturity claims need independent verification before public reuse.
Word count

5499

Bytes

39644

Source relative

herald-protocol/research/zk-provenance.md

Remote mirror

manthan/herald-protocol/research/zk-provenance.md

Full text preserved

True

ZK Provenance Proof Library Survey — Feasibility Report for the provenance_proof Envelope Class

Task: R-201 — Survey ZK provenance proof libraries; feasibility report for provenance_proof envelope class.
Prepared by: worker-opus-2026-05-05-R201-par2
Date: 2026-05-05
Sources last checked: 2026-05-05.

0. Frame

[SPEC §11.2] (line 494) names zero-knowledge selective disclosure as "the most load-bearing future research direction." [THREATS §9] (lines 535–562) enumerates exactly the statements a ZK substrate would need to express. [EXT §2.8] (line 201) goes further than SPEC: it promotes ZK provenance proofs to a Phase-1 EXT deliverable on the grounds that the audit-log primitive is otherwise dual-use surveillance infrastructure.

The R-208 finding (manthan/state/findings/R-208/research/dkim-analogy.md) returns to ZK five times as the only path that dissolves the bilateral-conversation lie-detection problem. So the strategic stakes are:

Without ZK, HERALD's most defensible deployments are also its most surveilled. Reputation laundering, conduit collusion, surveillance-by-default audit logs, and lineage-cluster surveillance all collapse if the protocol can prove "I descend validly from a Herald-attested model" without revealing the trace.

This report assesses whether 2026-era ZK proof libraries can express HERALD's required statements, at what maturity, with what tooling, and with what residual risks. It does not propose a circuit, build a prototype, or prescribe a single library. It is a navigation document: which library family to pick for a v0.3-era PoC, and what conditional roadmap follows that choice.

1. The HERALD ZK statements (drawn directly from [THREATS §9])

The threat model lists five statements a verifier should be able to confirm without seeing the trace ([THREATS §9] lines 540–545):

#StatementRequired structure
S1Envelope's lineage chain terminates at a Herald-attested model hash.Recursive verification of N signatures over a chain of parent-linked envelopes ending in a birth envelope counter-signed by a Herald with a known public key. Variable depth (typical N small, but unbounded).
S2A given envelope has been logged in a conformant audit log.Merkle-tree inclusion proof against a published Signed Tree Head ([EXT §2.3]). STH itself signed by a known log operator key.
S3Capability manifest's signer holds a non-deprecated sigil.Signature verification + non-membership proof (signer not in revocation/molt list at time ts). Non-membership over a published, signed registry.
S4Trace's genesis matches a participant's claimed genesis.Equality of trace field across two envelope sets, plus a single signature check on the genesis envelope. Cheapest of the five.
S5Patina score exceeds threshold t, without revealing the underlying envelope set.Cardinality / range proof over a privately committed multiset of envelopes, each individually signature-checked, each falling in a declared time window, each tagged with the relevant attestation type.

Two further candidates not in §9 but mentioned by the R-208 finding are likely to enter [EXT §2.8]'s scope:

For library evaluation, the load-bearing primitive across all seven is:

Signature verification (Ed25519) inside the circuit, composed with Merkle-inclusion / non-inclusion proofs, with optional recursion to handle variable-depth chains, and small range/cardinality predicates on top.

If a library does this well, HERALD can express its statements. If it does not, HERALD cannot.

2. Why HERALD is not a typical zk-rollup workload

A clarifying note before the library survey. zkVM marketing in 2024–2026 is dominated by Ethereum block proving: tens of millions of cycles, single proof per ~12s slot, GPU farms, real-time. HERALD is the opposite shape:

Dimensionzk-rollup workloadHERALD provenance_proof
ProverBatched, server-side, well-resourcedOften sigil-side (laptop, phone, edge agent)
FrequencyOne proof per blockPer-envelope, potentially millions/day system-wide
Latency budgetSeconds per proof OKMilliseconds-to-seconds per proof; verification <10ms
Workload size10⁶–10⁹ cycles10²–10⁴ "cycles" (a handful of sig-checks + a Merkle proof)
Dominant costMemory / RAM / FFTsPer-statement constant overhead and signature precompiles
Recursion needAggregating thousands of proofsVariable-depth lineage chains (≤20 hops typical)
Trusted setup toleranceHas been accepted (KZG ceremonies)Should be avoided where possible — HERALD's trust model is "no chokepoint" ([SPEC §0])

The mismatch is significant: a zkVM optimised for million-cycle Ethereum blocks is underpowered per dollar for HERALD's tiny circuits, because the constant per-proof overhead dominates. Conversely, a hand-tuned circuit (Halo2, Circom, Noir) where the prover does only the Ed25519 + Merkle work HERALD actually needs may produce a 100ms / kilobyte proof on a phone.

This frames the survey: HERALD wants small, hand-tuned, transparent over large, general-purpose, ceremony-dependent.

3. Per-library survey

For each library: repo URL, license, last-checked release info, proof system, target backend, tooling maturity, audit status, performance ballpark for HERALD-shaped circuits, and a per-statement (S1–S7) readiness column. All "estimated" rows are flagged. All "measured" rows cite a benchmark source.

3.1 Halo2 (Zcash and PSE forks)

S1 (lineage chain)S2 (log inclusion)S3 (manifest + non-revoc)S4 (genesis eq)S5 (patina ≥ t)S6 (recip-obs)S7 (refusal rate)
Halo2Strong (recursion mature)Strong (mature Merkle gadgets)Medium (non-membership trickier; needs custom gadget)Strong (trivial)Medium (range-proof gadgets exist; cardinality custom)StrongMedium

3.2 Plonky2 / Plonky3

S1S2S3S4S5S6S7
Plonky2/3Strong (designed for recursion)StrongMedium (non-membership needs custom AIR)StrongMediumStrongMedium

3.3 RISC Zero zkVM

3.4 SP1 (Succinct Labs)

S1S2S3S4S5S6S7
SP1Strong (Ed25519 precompile + recursion)Strong (SHA256 precompile)Strong (precompile + Rust logic)StrongMedium (Rust logic; cycle cost grows)StrongMedium

3.5 Noir (Aztec) + Barretenberg backend

3.6 gnark (Consensys, Go)

3.7 arkworks (Rust)

3.8 Circom + snarkjs (iden3)

4. Comparison table

The single matrix view, with 2026-05 data:

LibraryLast release (≈)LicenseTrusted setupRecursionTooling maturityAudit statusEd25519 nativeSuited for HERALD?
Halo2 (Zcash)0.3.x lineMIT/ApacheNo (IPA)NativeHighMultiple deep auditsCustom gadget requiredYes — strong
Halo2 (PSE/KZG)activeMIT/ApacheYes (KZG)NativeHighMultiple auditsCustom gadget requiredYes (with ceremony)
Plonky2activeMIT/ApacheNo (FRI)Native, fastMediumPolygon-internalCustom gadget requiredYes — strong
Plonky3"production ready" 2024-07MIT/ApacheNo (FRI)NativeLower (toolkit)"Extensively audited"Via SP1 precompileYes (toolkit-level)
RISC Zero1.x lineApache/MITNo (STARK) / Yes (Groth16 wrap)YesHighHexens (3 audits)Rust crate, no precompileYes (high overhead)
SP1Hypercube 2026MITSame trade-offYesHigh4 audits + formal verifYes (precompile)Yes — strong
Noir / Barretenberg1.0 pre-release 2026ApacheYes (KZG)YesHigh (DSL)In progressCustom impl requiredYes — strong
gnarkv0.14.0 2025-06ApacheYes (Groth16/KZG)LimitedHigh (Go native)Production-testedCustom impl requiredYes (Go-native plus)
arkworksalgebra 2026-04MIT/ApachePer-schemePer-schemeMedium (low-level)Self-declared "not production"PossiblePrototype only
Circom + snarkjsactiveGPL-3 / ApacheYesLimitedHighestFootgun-proneCustom (iden3 EdDSA is BabyJubjub)Yes (with care)

Bold entries indicate first-tier candidates for the v0.3 PoC.

5. Recommendation: which library family for v0.3-era PoC

The recommendation is two-track, not single-library, because HERALD's optimal answer depends on which of two paths the protocol commits to.

Track A — "Ship a working PoC fast." → SP1 (or RISC Zero)

If the goal of v0.3 is to demonstrate that the protocol can produce ZK provenance proofs at all — to unblock [SPEC §11.2] from "open question" status and to give [EXT §2.8]'s Phase-1 promise concrete substance — pick a zkVM. Specifically SP1, on the basis that:

1. Ed25519 verification is a precompile, not a circuit you write.
2. Audit + formal verification posture is the strongest in this survey.
3. The HERALD developer writes a Rust function prove_lineage_chain(envelopes, attestations) -> Proof that is structurally identical to the existing reference verifier. The "circuit" is the existing verifier code.
4. The Groth16 wrapping path lets verifiers be small and on-chain if needed; the STARK path keeps everything transparent.

The cost is per-proof overhead. SP1 provers will be slower per HERALD envelope than a hand-tuned Halo2 circuit by a meaningful margin (estimated 3–10×, not measured in this survey). For low-traffic conduits and Heralds, this is acceptable. For per-envelope provenance proofs at internet scale, it will not be.

RISC Zero is the second-choice in this track — the same model, slightly less aggressive precompile suite, more mature browser/proof-aggregation tooling.

Track B — "Optimise per-envelope cost from day one." → Halo2 (Zcash variant) or Plonky2

If HERALD's intended deployment shape is per-envelope proofs at high frequency (the [EXT §2.8] promotion of provenance_proof to default-mode log entries), the per-proof overhead of a zkVM is too much. Pick a hand-tuned circuit framework.

What to do now (concrete, scoped)

1. Build a minimal SP1-based PoC that proves S1 (lineage chain terminates at a Herald-attested model hash). Time-budget: 1–2 weeks. This validates that the developer-effort claim above is real and produces measurable numbers to replace this report's estimates.
2. In parallel, build the same circuit in Halo2 (Zcash variant). Compare proof size, prover time, verifier time, RAM consumption, on the same input.
3. Use the comparison to decide Track A or Track B at v0.4.
4. Both prototypes should live under experiments/zk/ and explicitly not be promoted to the main spec until reviewed.

This is the substance the report can responsibly recommend. Anything more specific is unfounded without prototyping.

6. Gotchas — known traps that survey-only work cannot dissolve

6.1 Trusted setup vs transparent — politics, not just math

KZG-based systems (PSE Halo2, Noir/Barretenberg, gnark Groth16/PLONK, snarkjs PLONK) require a one-time ceremony. The Aztec ignite ceremony, Ethereum's KZG ceremony, and Filecoin's powers-of-tau are real precedents. For HERALD:

Recommendation: prefer transparent setups (Halo2-IPA, Plonky2/3, RISC0/SP1 STARK) at the cost of larger proofs. This is consistent with HERALD's stated values.

6.2 Recursion costs are real

Variable-depth lineage chains (S1) require either:

A bounded-depth-32 circuit is a reasonable v0.3 simplification. It is not what [SPEC §2.3] permits — lineage is unbounded — but it would unblock a PoC.

6.3 Witness-size limits

For Groth16 + Circom on 256M-constraint trusted-setup parameters, Ed25519 batch verification fits at most 99 signatures per proof. HERALD's S5 (patina ≥ threshold over a set of envelopes) hits this limit when the patina set is large. For sets of thousands of envelopes:

6.4 Ed25519-in-circuit is not free

RFC 8032 Ed25519 uses the prime 2^255 - 19 and the non-pairing-friendly Curve25519. Inside a SNARK over (e.g.) BN254, the prover must simulate the curve via non-native field arithmetic. Hand-tuned circuits have brought this to ~1.5M constraints per signature (NEAR Rainbow Bridge work, Electron Labs zk-Ed25519). SP1's Ed25519 precompile is the path of least resistance.

If HERALD ever considers swapping its core signature suite to a SNARK-friendly one (e.g. EdDSA-on-BabyJubjub, or a curve-cycle-friendly choice like Pasta), the ZK story improves dramatically — but [SPEC §3.x] currently mandates Ed25519, and this is a load-bearing interop / browser / hardware-token compatibility decision. Do not change the signature suite for ZK convenience without a separate decision document.

6.5 Soundness bugs from circuit authors, not libraries

The Halo2 "query collision" bug (2024), and the long history of circom circuits with under-constrained signals, illustrate: most ZK soundness failures in the wild come from circuit authors mis-using a sound library. Whatever HERALD picks, the circuit needs:

6.6 Browser / mobile prover feasibility

For HERALD to be honest about the "sigil-side prover" pattern (an agent generates its own provenance proof), browser/mobile feasibility matters. Status:

If sigil-side mobile proving is required, Noir or Halo2 are the only mature paths.

7. Conditional roadmaps

7.1 If HERALD picks Halo2 (Zcash IPA variant)

1. Build per-statement gadgets: EnvelopeSig (Ed25519 verification), MerkleInclude (against an STH-rooted tree), LineageStep (recursive accumulator).
2. Compose into per-statement circuits (one for S1, one for S2, etc.). Resist building a monolithic circuit; keep statements composable.
3. Standardise the wire format for provenance_proof.payload as (statement_id, public_inputs, proof_bytes).
4. Audit each gadget separately. Engage a ZK-specialist firm before the first production deployment.
5. Plan a Plonky2/3 migration path for recursion-heavy patterns; Halo2 → Plonky2 inter-op is non-trivial but feasible.
6. Budget: 4–6 person-months for first audited release of S1+S2+S4. S3, S5–S7 are follow-on.

7.2 If HERALD picks Plonky2/3

1. Accept the steeper learning curve. Hire or contract a Plonky2 specialist; the library's tooling assumes circuit-design competence.
2. Use Plonky3 for new work; Plonky2 only for components where existing gadgets save effort.
3. Recursion is the design centre, not an afterthought — design every statement as composable in a recursion tree.
4. Goldilocks field is a quirk: Poseidon hash on Goldilocks is fast; SHA256 (HERALD's hash) is not — there is a real overhead to expressing HERALD's existing hash choice. Either:
- Build SHA256 inside Plonky2 (expensive but feasible);
- Or change HERALD's commitment hash to a SNARK-friendly choice (Poseidon, Rescue) for the ZK envelopes specifically. This is a zk_hash extension, not a SPEC change.
5. Budget: 6–9 person-months for first audited release. Higher than Halo2 due to tooling immaturity.

7.3 If HERALD picks SP1 (Track A)

1. Treat the existing HERALD reference verifier as the "circuit." Compile it for the SP1 RISC-V target.
2. Use Ed25519 + SHA-256 + Keccak precompiles. They cover ~80% of HERALD's per-envelope cost.
3. Decide: STARK proofs (~1–2 MB, transparent) or Groth16-wrapped (~200 B, requires the wrap ceremony). Transparent is the [SPEC §0]-aligned choice; Groth16-wrapped is the on-chain-friendly choice. HERALD does not currently have an on-chain anchor, so the case for Groth16-wrapping is weak.
4. Plan for proof aggregation — prove batches of envelopes together to amortise per-proof overhead. SP1's Plonky3 backbone is good at this.
5. Budget: 1–2 person-months for first PoC; 3–4 person-months for production-quality with audit.

7.4 If HERALD picks Noir + ACIR (deferred backend)

1. Author circuits in Noir, targeting Barretenberg for fast iteration.
2. Plan an ACIR → Halo2 (transparent) migration when the protocol matures.
3. Track Noir 1.0 stability — as of 2026-05, 1.0 is pre-release. Production use is a year-out judgement call.
4. Budget: 2–4 person-months for first audited PoC (lower than Halo2 due to DSL); higher for migration work.

8. Honest residuals — what we cannot judge without prototyping

This is a survey, not a benchmark. Specifically the report cannot answer:

1. Actual proof size, prover time, and verifier time for HERALD's compound circuit (3–5 sig + Merkle + non-membership + small range proof) on each library. Estimates in §3 are extrapolations from public benchmarks of similar primitives. The numbers move within an order of magnitude; ranking between Halo2 and SP1 on HERALD-specific shapes is not knowable without measurement.
2. The audit cost of each circuit. For a small hand-tuned Halo2 circuit, an audit might be $30–80k. For a full SP1 zkVM-resident verifier, the audit reuses SP1's existing audit work and is cheaper for the wrapper but more expensive for the application logic. Real numbers require quotes.
3. The GDPR / right-to-be-forgotten interaction. [SPEC §11.4] (Open Q4) flags this. ZK proofs are immutable commitments; "tombstone with proof of erasure" is unspecified for any of these libraries. Likely an EXT-layer pattern, not a circuit choice.
4. Quantum migration. All surveyed libraries use elliptic-curve cryptography in some part of their stack (KZG ceremonies, Ed25519 verification, signature suites). [SPEC §11.5] flags PQ migration as deferred; the ZK story will need re-evaluation when HERALD's signature suite changes.
5. Composition with multi-signature envelopes ([SPEC §3.4]). A provenance_proof over a multi-sig envelope must verify all signatures and prove the threshold logic. None of the surveyed libraries make this trivial; it is custom circuit work in every case.
6. Plonky3's specific audit content. "Extensively audited" is a press claim; the report could not locate publicly published audit reports for Plonky3 itself (as opposed to SP1 or Polygon zkEVM-using-Plonky3) as of 2026-05. This is a gap a prototyping team should close before commitment.
7. The recipient_observation envelope (S6) is hypothetical from the R-208 finding, not in any of SPEC/EXT/CHARTER. Its ZK shape depends on a SPEC decision that has not happened.

These residuals should drive the prototyping decisions in §5 — measure first, recommend later.

9. Citations

HERALD-internal

External (last checked 2026-05-05)

10. Final position

The honest framing is this:

Recommendation 19 in [02-redteam] (promote ZK from open question to Phase-1 deliverable) is technically sound on 2026-05 evidence. The protocol's case for not doing this work is now substantially weaker than it was in 2024. ZK provenance proofs should move from "research direction" to "scoped engineering project with a measurable deliverable" in v0.3+.

Continue exploring