Reef

This is an implementation of Reef, a system for generating zero-knowledge proofs that a committed document matches or does not match a regular expression. The details of Reef are described in our paper: Reef: Fast Succinct Non-Interactive Zero-Knowledge Regex Proofs.

Compile

cargo build --release

With metrics:

cargo build --release --features metrics

Usage

Usage: reef [OPTIONS] <--commit|--prove|--verify|--e2e> [ALPHABET]
Alphabet:
ascii Accepts ASCII regular-expressions and documents
utf8 Accepts UTF8 regular-expressions and documents
dna Accepts DNA base ASCII files
help Print this message or the help of the given subcommand(s)
Options:
--commit
--prove
--verify
--e2e
--cmt-name <FILE> Optional name for .cmt file
--proof-name <FILE> Optional name for .proof file
-d, --doc <FILE>
--metrics <FILE> Metrics and other output information
-r, --re <RE> Perl-style regular expression
-b, --batch-size <USIZE> Batch size (override auto select) [default: 0]
-p, --projections Use document projections
-y, --hybrid Use hybrid nlookup
-m, --merkle Use merkle tree for document commitment
-n, --negate Negate the match result
-h, --help Print help
-V, --version Print version

There are four different "parties" that can run reef. They all require an alphabet mode. Running --commit requires --doc. Running --prove (or --e2e) requires --doc and --re. Running --verify only requires --re. It's important that each party uses the same alphabet, document, regular expression, and merkle/projection/hybrid flags (when appropriate).

Note that you can use --cmt-name and --proof-name to choose names for your commitment and proof files. This is optional - Reef will choose a name for the commitment/proof based on the document/regex if you do not - except in the case of verification, when you are required to specify the commitment file name (verification does not read the document).

A good starting point is to generate the proof that aaaaaaaab matches the regex .*b.

$ echo aaaaaaaab > document
$ reef -d document --commit ascii
$ reef -d document -r ".*b" --prove ascii
$ reef -r ".*b" --verify --cmt-name document.cmt ascii

Note that you can use the same document commitment to generate proofs for multiple different regexes.

Or another example, with metrics and end-to-end running.

$ echo "hello world happy to be here" > hello.txt
$ reef -d hello.txt --metrics metrics.txt -r "hello.*" --e2e ascii

Reproducing Baseline Results

If you're interested in reproducing our baseline results (DFA and DFA with recursion), you'll need to checkout the branch reef_with_baselines and build as follows:

For DFA

cargo build --release --features naive

For DFA with Recursion

cargo build --release --features nwr

Thank you for using Reef, Happy proving!