Paper 2024/562
Practical Proofs of Parsing for Context-free Grammars
Abstract
We present a scheme to prove, in zero-knowledge (ZK), the correct parsing of a string in context-free grammar (CFG). This is a crucial step towards applications such as proving statements about web API responses in ZK. To the best of our knowledge, this is the first ZK scheme to prove the correctness of CFG parsing with complexity linear in the length of the string. Further, our algorithm flexibly accommodates different ZK proof systems. We demonstrate this flexibility with multiple implementations using both non-interactive and interactive proof paradigms. Given general-purpose ZK programming frameworks, our implementations are not only compact (e.g., around 200 lines of code for the non-interactive version) but also deliver competitive performance. In the non-interactive setting, proving the correct parsing of a $\approx 1$KB string takes 24 seconds, even for grammars with $2^{10}$ production rules. In the interactive setting the same proof takes just 1.6 seconds.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- parsingcontext-free grammarszero-knowledge proofs
- Contact author(s)
-
hmalvai2 @ illinois edu
siam hussain @ smartcontract com
gregory neven @ chainlinklabs com
soc1024 @ illinois edu - History
- 2024-09-27: last of 2 revisions
- 2024-04-11: received
- See all versions
- Short URL
- https://ia.cr/2024/562
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/562,
author = {Harjasleen Malvai and Siam Hussain and Gregory Neven and Andrew Miller},
title = {Practical Proofs of Parsing for Context-free Grammars},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/562},
year = {2024},
url = {https://eprint.iacr.org/2024/562}
}
