Paper 2025/1420

Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs

Abstract

We introduce Coral, a system for proving in zero- knowledge that a committed byte stream corresponds to a structured object in accordance to a Context Free Grammar. Once a prover establishes the validity of the parsed object with Coral, they can selectively prove facts about the object—such as fields in Web API responses or in JSON Web Tokens—–to third parties or blockchains. Coral reduces the problem of correct parsing to a few simple checks over a left-child right-sibling tree and introduces a novel segmented memory abstraction that unifies and extends prior constructions for RAM in zkSNARKs. Our implementation of Coral runs on a standard laptop, and non-interactively proves the parsing of real Web responses (JSON) and files (TOML and C) in seconds. The resulting proofs are small and cheap to verify.

Note: This is the extended version of our paper Coral, which appears at IEEE S&P 2026. This version includes 4 extra appendices over the conference paper. Appendix C includes details on how Coral implements Hypernova's witness blinding technique to Nova's codebase. Appendix D shows the soundness of Coral's memory and its optimizations. Appendix E describes Split-witness Committed Relaxed R1CS in detail, a folding scheme for it (based on Nebula), and a SNARK. Appendix F has security proofs of the end-to-end system.