Paper 2025/1420 Original: eprint.iacr.org/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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2025-11-06: last updated
- 2025-08-04: published
- Short URL
- https://ia.cr/2025/1420
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2025/1420,
author = {Sebastian Angel and Sofía Celi and Elizabeth Margolin and Pratyush Mishra and Martin Sander and Jess Woods},
title = {Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1420},
year = {2025},
url = {https://eprint.iacr.org/2025/1420}
}