zkARc: Succinctly Verifiable Proofs for Neurosymbolic Natural Language Formalization and Verification
Organizations: ICME Labs · Imperial College London · Amazon Web Services
Abstract
Autonomous agents increasingly execute consequential actions on behalf of users, but ordinary middleware guardrails do not provide cryptographic proof that a policy was actually enforced. Their verdicts leave counterparties dependent on the operator unless they repeat the checks themselves, potentially exposing sensitive policies and inputs. We present zkARc, a modular proof-carrying framework that wraps each stage of Automated Reasoning checks (ARc) in an independent, succinctly verifiable zero-knowledge proof. ARc is a neurosymbolic system that translates natural language policies into formal logic and verifies AI-generated content against them using SMT solvers. zkARc certifies the planner's output, the policy's formalization, the action's formalization and both solver queries. The receipt binds these computations to the exact action received and, under the stated assumptions, reveals no additional information about private policies and intermediate model values beyond the declared public information and verdict. This lets a third party check the claimed policy enforcement without re-running the pipeline or trusting the operator. We prove completeness, knowledge soundness and zero knowledge for the composed receipt under explicit assumptions. An implementation on Qwen2-0.5B enforces a spending policy end to end, approving two purchases and denying a third. A full receipt, which also proves model inference, takes about an hour to issue with CPU-only proving and verifies in under a minute, and the solver proof alone is 88 KiB and verifies in 0.3 seconds.
Figures & tables
| Policy and action | |
|---|---|
| , | natural language policy, formal policy model ( ) |
| , | prompt, natural language action plan |
| , , | structured action, action schema, action hash |
| , | state supplied by the receiver , its authenticated state hash |
| Solver | |
| solver inputs: premise , conclusion | |
| Component | Verified fact | What remains assumed | Proved |
|---|---|---|---|
| Provenance | The committed planner used the prompt committed by and produced the action object bound to the received action. | The verifier authorizes the prompt and accepts that the planner output reflects the principal’s intent. | Per action |
| Policy compilation | The committed compiler produced from the authorized source policy. | The policy owner accepts that faithfully represents the source policy. | Per policy |
| Action formalization | The exact received action produced the bound solver instance . | Deterministic extraction is faithful to the declared schema. A configuration with LLM action translation also assumes that its declared translation rule is adequate. | Per action |
| Solver | The committed solver processed , returned both results, and derived the declared verdict. | The solver program implements the intended SMT semantics correctly. | Per action |
| Full solver in Jolt | Certificate checker in Jolt | |
|---|---|---|
| Proved claim | The committed solver constructs both queries and derives the verdict. | The committed checker accepts evidence for both results and derives the verdict. |
| Private witness | The solver execution traces. | A SAT model or UNSAT certificate per query. |
| Primary guarantee | Solver-execution binding. The receipt identifies the solver that ran. | Certificate validity. The producing solver need not be identified or trusted. |
| What remains assumed | The committed solver implements SMT semantics correctly. | The checker is sound and the format covers every relevant theory step. |
| Cost driver | Solver cycles for both queries. | Certificate size and checker cycles, lower when compact certificates exist. |
| Theory support | Any theory the committed solver implements. | Only theories the format and checker cover. |
| System | Checked natively | Certified by | Checked directly |
|---|---|---|---|
| Dory | Sum-checks, evaluation claims, and Fiat–Shamir challenges. | Packed and group operations, packed operations, wiring, and one Hyrax opening. | Final size- multi-pairing. |
| HyperKZG | Joint-evaluation reduction, folding equations, and Fiat–Shamir challenges. | The joint-commitment fold and the final linear combinations and , with one Hyrax opening. | . |
| Spending total ($) | Time (s) | |||||||
|---|---|---|---|---|---|---|---|---|
| Request | Prior | Proposed | Final | Verdict | Request to decision | Verify | Verify now | Proof bytes |
| 0 | 200 | 350 | 350 | VALID | 3,903.81 | 33.03 | 8.35 | 23,695,245 |
| 1 | 350 | 500 | 500 | VALID | 3,529.27 | 33.27 | 8.26 | 23,695,242 |
| 2 | 500 | 650 | 500 | INVALID | 3,401.80 | 32.71 | 8.19 | 23,692,263 |
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
| Request | |||
| 0 | 1 | 2 | |
| Model proving stages (s) | |||
| Public model preprocessing | 201.63 | 0.00 | 0.00 |
| Dory setup call | 122.66 | 0.00 | 0.00 |
| Public cache identity check | 31.89 | 30.60 | 24.63 |
| Witness and commitments | 686.60 | 660.49 | 620.61 |
| Time (s) | |||
| Cache load | Prove | Command | |
| Planner prompt | |||
| Request 0 | 83.30 | 352.92 | 440.46 |
| Request 1 | 82.49 | 350.53 | 437.07 |
| Request 2 | 81.89 | 354.68 | 441.17 |
| Exact action extraction | |||
| Time (s) | Without reuse | With reuse |
|---|---|---|
| First request: time to decision | 3,627.89 | 3,602.39 |
| Later requests: time to decision (mean) | 3,229.12 | 2,301.84 |
| Model prover including preparation, later requests (mean) | 2,251.07 | 1,327.69 |
| Model proof generation in later requests (mean) | 749.25 | 760.55 |
| Measured artifact | Proof size | Verified computation |
| Qwen generation and receipts | ||
| Short prompt and conversions | 22.8 MiB | Bounded Atlas model generation with canonical prompt and response |
| Two linked generations | 45.3 MiB | Both Atlas model stages , canonical conversions and equal hidden text |
| Policy generation, bindings and SMT | 10.4 MiB | Native policy generation, exact source and response conversion checks , and both solver queries |
| Static structured-action receipt | 22.6 MiB | Policy and planner generation, all required Jolt checks , exact action extraction and both queries |
| Solver proofs in Jolt | ||
| Native Qwen generation | Short prompt | Policy |
|---|---|---|
| Context positions / generated tokens | 32 / 2 | 128 / 27 |
| Setup and proving (s) | ||
| Dory setup call | 86.00 | 102.82 |
| Public parameter preprocessing | 161.76 | 164.01 |
| Witness construction and commitments | 583.46 | 673.49 |
| Proving after commitments | 810.16 | 613.49 |
| Time (s) | Proof | Peak | |||
| Policy check | Setup | Prove | Verify | (KiB) | (GiB) |
| Conversions, Xeon Platinum 8272L | |||||
| Source policy and prompt | 68.82 | 276.42 | 0.298 | 92.4 | 50.7 |
| Response and compilation | reused | 237.56 | 0.300 | 92.3 | 50.7 |
| Solver, Xeon E5-2699 v3 | |||||
| VALID | 10.38 | 30.17 | 0.292 | 87.6 | 10.6 |
| Time (s) | Proof | Peak | ||
| Component | Prove | Verify | size | memory |
| Short-prompt generation | ||||
| Qwen short prompt, first | 1,394.24 | 65.21 | 22.3 MiB | 126.1 GiB |
| Qwen short prompt, second | 1,394.51 | 66.93 | 22.3 MiB | 123.4 GiB |
| Conversions, one generation | 268.38 | 0.63 | 491.7 KiB | 38.7 GiB |
| Conversions, linked pair | 476.62 | 0.96 | 743.6 KiB | 53.2 GiB |
| Full program | Program commitment | |
| Size | ||
| Proof body (KiB) | 88.4 | 88.6 |
| Public IO and framing (bytes) | 155 | 155 |
| Proof size (KiB) | 88.6 | 88.7 |
| Verifier preprocessing (bytes) | 90,922,838 | 53,899 |
| Complete verifier input (bytes) | 91,013,553 | 144,746 |
| Time (s) | ||||
|---|---|---|---|---|
| Case | Authorize | Jolt prove | Receipt verify | |
| Allowed | (SAT, UNSAT) | Yes | 29.644 | 1.438 |
| Blocked | (UNSAT, SAT) | No | 29.854 | 1.483 |
| Ambiguous | (SAT, SAT) | No | 29.949 | 1.468 |
| Operation | Host | Cores | Time (ms) |
| Sum-check | |||
| Prove, , | 2700X | 1 | 18.127 |
| Claim merging | |||
| Verify, , , 16 polynomials | 2700X | 1 | 0.254 |
| Verify, , , 8 polynomials | 2700X | 1 | 0.183 |
| Prove, , , 16 polynomials | 7600 | 1 | 9.897 |
| Time (ms) | Payload | ||
|---|---|---|---|
| Layout | Prove | Verify | (bytes) |
| Per instance | 1,293.150 | 35.496 | 106,280 |
| By family | 368.192 | 10.295 | 39,640 |
| Operation count | |||
| Group operation | Symbolic | , | , |
| Certified by | |||
| scalar multiplication | |||
| addition | |||
| scalar multiplication | |||
| addition | |||
| Operation count | |||
| Phase | Group operation | Symbolic | , |
| Certified by | |||
| Joint commit fold | scalar multiplication | ||
| addition | |||
| KZG batch (MSM) | scalar multiplication | ||
| addition | |||
Formal Verification
Formal verification uses mathematical models and machine-checked proofs to establish whether software and systems satisfy precise specifications.
See all 381 papers