Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge

John Kolesar, Shan Ali, Timos Antonopoulos, Ruzica Piskac · 2025

Read Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge by John Kolesar, Shan Ali, Timos Antonopoulos, Ruzica Piskac (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-01198.txt.

Introduction

Proving two programs equal without showing either one is a natural job for zero-knowledge proofs, and regular expressions are everywhere in real software. John Kolesar, Shan Ali, Timos Antonopoulos, and Ruzica Piskac tackle expression equivalence in 2025, a problem hard enough to sit in the PSPACE-complete class. Their protocol, Crepe, is the first of its kind. It rests on a custom proof calculus built from expression derivatives and coinduction, with an algorithm that writes each proof.

Hundreds of test cases pass, and even large proofs check in a few seconds each. The authors note Crepe is also the first zero-knowledge protocol aimed at any problem of this hardness class. They frame it as a step toward private, checkable software claims.

Catalog record

CREATORJohn Kolesar, Shan Ali, Timos Antonopoulos, Ruzica Piskac
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-01198

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge John Kolesar, Shan Ali, Timos Antonopoulos, Ruzica Piskac Abstract Zero-knowledge (ZK) protocols enable software developers to provide proofs of their programs’ correctness to other parties without revealing the programs themselves. Regular expressions are pervasive in real-world software, and zero-knowledge protocols have been developed in the past for the problem of checking whether an individual string appears in the language of a regular expression, but no existing protocol addresses the more complex PSPACE-complete problem of proving that two regular expressions are equivalent. We introduce Cr^epe , the first ZK protocol for encoding regular expression equivalence proofs and also the first ZK protocol to target a PSPACE-complete problem. Cr^epe uses a custom calculus of proof rules based on regular expression derivatives and coinduction, and we introduce a sound and complete algorithm for generating proofs in our format. We test Cr^epe on a suite of hundreds of regular expression equivalence proofs. Cr^epe can validate large proofs in only a few seconds each. 1 Introduction Software verification is the process of translating a program into a mathematical formalism and then constructing a proof that the formalized program satisfies some specification. Traditional verification tools do not allow programmers to hide the implementation details of their software from other parties. The tools require all relevant information to be fully visible to all parties involved in the verification process, so they are inadequate for verification problems involving third-party libraries, cloud-based services, or other proprietary software: the owners of the software cannot share the evidence of the program’s correctness with other parties without losing their privacy. To make verification of private programs possible, recent research at the intersection of cryptography and formal verification has focused on the development of zero-knowledge (ZK) protocols for encoding proofs of programs’ correctness [ 50 , 49 , 46 ] . A zero-knowledge protocol is a cryptographic method of communication that allows one party to demonstrate knowledge of a secret to another party without revealing the secret [ 36 , 35 ] . The ZK program verification process involves two parties: the prover who owns the private program and the verifier whom the prover wants to convince of the program’s correctness. (In the domain of ZK protocols, the terms “prover” and “verifier” have different meanings than they do in the domain of non-cryptographic formal verification.) The prover constructs a proof of the program’s correctness offline and then engages in an interactive zero-knowledge protocol with the verifier. During the protocol, the prover provides evidence that suffices to convince the verifier that the program is correct but does not reveal additional information about the program’s implementation. To be efficient and scalable, ZK protocols must be tailored for specific domains. Existing ZK verification protocols have targeted Boolean logic [ 50 ] , quantifier-free first-order logic with EUF and LIA [ 49 ] , and Lean’s calculus of dependent types [ 46 ] , but currently no ZK protocol exists for the problem of regular expression equivalence. Regular expressions are a common formalism for defining string patterns, and their uses in modern software are pervasive [ 17 , 55 , 58 ] . In particular, the applications of regular expression equivalence include correctness proofs for compiler optimizations [ 44 ] , translation validation [ 31 ] , and query optimization [ 19 ] . Also, individual regular expressions for tasks such as intrusion detection and prevention for network packets [ 66 ] can be sensitive intellectual property, so programmers can benefit from a ZK protocol for reasoning about the semantics of private regular expressions. Importantly, we cannot reformulate the problem of regular expression equivalence in terms of problems that existing ZK protocols handle. Existing ZK regular expression protocols [ 65 , 51 , 52 , 5 ] reason only about the problem of matching individual strings against regular expressions. Regular expression equivalence is a PSPACE-complete problem [ 56 , 57 ] , and string matching is at most NP-complete if generalized [ 1 ] , so we cannot reduce regular expression equivalence to string matching unless P=PSPACE or NP=PSPACE. In fact, no existing practical ZK protocol targets a PSPACE-complete problem at all, even though it has been known for decades that the complexity class IP (the set of all problems that can be solved with interactive ZK proofs) is equal to PSPACE [ 54 ] . In this paper, we introduce the first practical ZK protocol for the problem of regular expression equivalence. More specifically, we developed a tool called Cr^epe (Cryptographic Regex Equivalence Proof Engine) that validates regular expression equivalence proofs in ZK. When two parties communicate using Cr^epe , the owner of a hidden proof that two regular expressions are equivalent can convince the other party that the proof is valid without leaking the regular expressions or the proof. Also, we introduce a new decision procedure to generate the proofs that Cr^epe validates. We cannot rely on an existing solver to generate proofs for us: older tools have only limited support for regular expression proofs. Modern SMT solvers can reason about other formalisms effectively, but there is no well-established format for providing proof certificates about regular expression equivalence analogous to the existing formats for Boolean logic, EUF, and LIA [ 21 ] . Given two equivalent regular expressions as input, our decision procedure constructs an equivalence proof for them in a custom calculus of proof rules that we introduce. Instead of converting regular expressions into state machines or other objects, as standard solvers do [ 67 , 10 ] , our rules apply coinduction to reason about regular expressions directly, eliminating the need to validate a conversion between different formats. We prove that our rules are sound and complete for regular expression equivalence. In summary, we make four main research contributions: 1. ZK Protocol. We introduce Cr^epe , the first zero-knowledge protocol designed to validate regular expression equivalence proofs and also the first practical ZK protocol to target a PSPACE-complete problem. 2. Proof Generator. We develop a backend for Cr^epe that generates regular expression equivalence proofs in a custom calculus, and we prove the calculus sound and complete, which is of independent interest. 3. Proof Generator Evaluation. We test our custom proof generator on a suite of commonly-used regular expression benchmarks from FlashRegex [ 48 ] . The regular expressions range from 2 to 60 characters in length. Our proof generator scales to handle large, complex inputs, and it generates equivalence proofs successfully for almost all of the equivalent pairs in the suite. 4. ZK Protocol Evaluation. We test Cr^epe on a suite of hundreds of equivalence proofs from our custom proof generator. Cr^epe can validate 84.39 percent of the proofs in 15 seconds or less. Also, we run Cr^epe on the same suite with alternative configurations that change the amount of information that it leaks. Our default settings provide strong safety guarantees and incur only a 35% median slowdown relative to a version that leaks more information. 2 Motivating Example Unsafe usage of regular expressions opens a window for attacks that flood a network server with unwanted slow traffic, making it inaccessible. A denial-of-service attack against a regular expression (ReDoS or simply DoS) is the

Read the complete text