Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs
Sebastian Angel (University of Pennsylvania), Sofía Celi (Brave Software), Elizabeth Margolin (University of Pennsylvania), Pratyush Mishra (University of Pennsylvania), Martin Sander (University of Pennsylvania), Jess Woods (University of Pennsylvania) | Security, Cryptography
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.
