zkARc: Succinct Verifiable Proofs for Neurosymbolic Natural Language Formalization and Verification
zkARc: Succinctly Verifiable Proofs for Neurosymbolic Natural Language Formalization and Verification
The researchers propose zkARc, a modular framework that wraps each stage of Automated Reasoning checks (ARc) in an independent, succinct verifiable zero-knowledge proof, so that a third party can verify that the policy was actually enforced without rerunning the pipeline or trusting the operator. ARc is a neurosymbolic system that translates natural language policies into formal logic and then uses an SMT solver to check AI-generated content; zkARc issues proofs for the planner output, policy formalization, action formalization, and two solver queries, with receipts bound to the actions actually executed, and under the stated assumptions it does not leak private policies or intermediate model values beyond the public information and verdicts declared. The authors prove completeness, knowledge soundness, and zero-knowledge of the composite receipt under explicit assumptions. An implementation based on Qwen2-0.5B executes a spending policy end to end, approving two purchases and rejecting a third; the full receipt including the model inference proof is generated in about 1 hour on pure CPU and verified in under 1 minute, while the solver-only proof is 88 KiB and verifies in under 0.3 seconds.