Brave Proposes Coral to Fix Parsing Gaps in Zero-Knowledge Proofs

Brave Software has unveiled Coral, a novel system that brings provable parsing into the domain of zero-knowledge proofs (ZKPs).

Coral addresses a long-standing blind spot in privacy-preserving systems, which is the assumption that structured inputs like JSON or HTML are well-formed without verifiable parsing.

The new system was developed by Brave’s Sofía Celi in collaboration with Sebastian Angel, Elizabeth Margolin, Pratyush Mishra, Martin Sander, and Jess Woods of the University of Pennsylvania. The project tackles the core challenge of verifying that a byte stream conforms to a formal grammar, such as a JSON API response or a piece of source code, without revealing the input itself.

Details of the Coral proposal

Parsing is an omnipresent but often invisible step in computing. It’s what turns raw byte streams into structured data for browsers, compilers, and firewalls. But in zero-knowledge settings, where proving something without revealing the underlying data is the goal, this assumption of well-formed inputs becomes a security risk. A malicious actor could commit to malformed data and still produce a seemingly valid proof, exploiting the verifier's inability to inspect the parsing step.

Brave’s Coral addresses this vulnerability by enabling zero-knowledge proofs that include the parsing phase itself. It ensures that a committed byte stream corresponds to a syntactically valid object as defined by a public context-free grammar (CFG), without requiring the verifier to see the data.

Coral’s design is grounded in the observation that while parsing is computationally complex, verifying a parse tree is much simpler. Instead of embedding the parsing logic directly into a zero-knowledge virtual machine (zkVM), an approach that has proven resource-intensive, Coral assumes an untrusted parser has produced a parse tree and focuses on verifying its correctness against the original bytes and grammar.

To make this verification compatible with constraint-based proof systems, Coral transforms traditional parse trees, which can have nodes with arbitrary children, into binary trees using the left-child right-sibling (LCRS) representation. This allows Coral to express parsing in a format compatible with Rank-1 Constraint Systems (R1CS), a foundational building block for many ZKPs.

A key innovation in Coral is its NP checker, a recursive verification loop that confirms each parse tree node matches the grammar and original data. This uniform approach is compatible with advanced folding schemes like Nova, allowing efficient aggregation of thousands of verification steps into a single, succinct proof.

Memory management is handled through a segmented memory model. Coral separates public grammar rules, persistent private data, and volatile stacks used during tree traversal, all accessible through a unified interface optimized for zero-knowledge execution.

Real-world practicability and limitations

The Coral system is implemented in Rust. It can handle realistic inputs like JSON responses, TOML files, and subsets of C source code. Proofs are under 20 kB in size, generated in seconds, and verified in under 70 milliseconds, without requiring specialized hardware. This makes Coral practical on consumer-grade machines, significantly lowering the barrier for adoption.

Brave Software, best known for its privacy-centric web browser and related cryptographic innovations, continues to invest in foundational privacy technologies. Coral fits within this strategy, targeting gaps in systems like zk-TLS, zk-Authorization (e.g., JWTs), and privacy-preserving network middleboxes, where the validity of structured inputs has historically been assumed rather than proven.

Despite its achievements, Coral is not a universal parsing verifier. Some data formats, such as HTML, PDF, and Python, rely on context-sensitive or ambiguous grammars that go beyond the scope of context-free grammars (CFGs). Supporting these formats would require significant extensions, such as supporting priority rules or negative predicates.

At this stage, Coral is strictly a research prototype and is not integrated into any Brave product. While the system is fully implemented in Rust and demonstrates strong real-world performance on formats like JSON, TOML, and C, it is best understood as a foundational contribution to the broader zero-knowledge ecosystem. Brave's involvement signals strategic interest in building privacy infrastructure, but for now, Coral serves as an open research tool for developers, cryptographers, and systems researchers, not as a feature users can directly interact with in Brave’s browser or services.