Reef: A zkSNARK system for proving that a committed document matches a regex

Overview

CircleCI

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

With metrics:

cargo build --feature metrics

Usage

Usage: reef [OPTIONS] --input <FILE> --output <FILE> --re <RE> <COMMAND>

Commands:
  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:
  -i, --input <FILE>
  -o, --output <FILE>
  -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

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

$ echo aaaaaaaab > input.txt
$ reef -i input.txt -o metrics.txt -r ".*b" ascii

or another example

$ echo "hello world happy to be here" > hello.txt
$ reef -i hello.txt -o metrics.txt -r "hello.*" 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 --feature naive

For DFA with Recursion

cargo build --feature nwr

Thank you for using Reef, Happy proving!

You might also like...
A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Zerokit A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments. Initial scope Focus on RLN

A super simple dialogue system for Rust.

📝 Dialogos A super simple dialogue system for Rust. It's nothing special, but that's the point! It's something that just works. This library is ideal

Operating system based off of blog_os, with the goal of running wasm modules as executables

yavkOS - A OS that attempts at running WASM modules as userspace programs Recommended Development Environment You need nix with the flakes, and nix-co

Generic inventory system built in pure rust.

game_inventory A framework for generalizing inventory logic and abstracting it away from item data in your specific game. See more examples and specif

Rust library provides a standalone implementation of the ROS (Robot Operating System) core

ROS-core implementation in Rust This Rust library provides a standalone implementation of the ROS (Robot Operating System) core. It allows you to run

(early experiments toward) a version-control system for structured data
(early experiments toward) a version-control system for structured data

chit: (early experiments toward) a version-control system for structured data please note, very little is actually implemented here. this is not usefu

A typesafe, flexible, simple, and user-friendly unit system library for Rust that has good error messages.

uy A typesafe, flexible, simple, and user-friendly unit system library for Rust that has good error messages. Usage uy not only stores the unit of a v

Easy c̵̰͠r̵̛̠ö̴̪s̶̩̒s̵̭̀-t̶̲͝h̶̯̚r̵̺͐e̷̖̽ḁ̴̍d̶̖̔ ȓ̵͙ė̶͎ḟ̴͙e̸̖͛r̶̖͗ë̶̱́ṉ̵̒ĉ̷̥e̷͚̍ s̷̹͌h̷̲̉a̵̭͋r̷̫̊ḭ̵̊n̷̬͂g̵̦̃ f̶̻̊ơ̵̜ṟ̸̈́ R̵̞̋ù̵̺s̷̖̅ţ̸͗!̸̼͋

Rust S̵̓i̸̓n̵̉ I̴n̴f̶e̸r̵n̷a̴l mutability! Howdy, friendly Rust developer! Ever had a value get m̵̯̅ð̶͊v̴̮̾ê̴̼͘d away right under your nose just when

This crate converts Rust compatible regex-syntax to Vim's NFA engine compatible regex.

This crate converts Rust compatible regex-syntax to Vim's NFA engine compatible regex.

A document-code sync tools for document engineering.

Writing A document-code sync tools for document engineering. Writing 是一个自动 “文档-代码” 同步工具。解析 Markdown 中的代码定义,读取目标代码,并嵌入到新的文档中。 Language parse support by

A library in Rust for theorem proving with Intuitionistic Propositional Logic.

Prop Propositional logic with types in Rust. A library in Rust for theorem proving with Intuitionistic Propositional Logic. Supports theorem proving i

A collection of comparison-benchmarks for Nova & related Proving systems

Nova benchmarks Here's a list of some of the benchmarks we've been taking to better understand how Nova performs vs other proof systems. Live version:

Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study
Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

a nom parser combinator that matches a psql statement.

psql_splitter a nom parser combinator that matches a psql statement. Postgres has a dialect of SQL that I'm going to call pgsql. Postgres also has a c

Utility to quickly setup Starcraft Broodwar matches between 2 or more bots

BWAIShotgun Utility to quickly setup Starcraft Broodwar matches between 2 or more bots Be aware that all bots will be executed directly, without any l

SHA256 sentence: discover a SHA256 checksum that matches a sentence's description of hex digit words.

SHA256 sentence "The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine." Inspired by @lauriewired post Inspired by @humbleha

zkSnark circuit compiler
zkSnark circuit compiler

Quickstart == Get started here ℹ Important deprecation note The old circom compiler written in Javascript will be frozen, but it can still be downloa

A Rust library for the Marlin preprocessing zkSNARK
A Rust library for the Marlin preprocessing zkSNARK

Marlin marlin is a Rust library that implements a preprocessing zkSNARK for R1CS with universal and updatable SRS This library was initially developed

Bellman zkSNARK library for community with Ethereum's BN256 support

bellman "Community edition" Originally developed for ZCash, with extensions from us to make it a little more pleasant. Uses our "community edition" pa

Owner
University of Pennsylvania | Distributed Systems Lab
University of Pennsylvania | Distributed Systems Lab
Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Elemental System Designs is an open source project to document system architecture design of popular apps and open source projects that we want to study

Jason Shin 9 Apr 10, 2022
An API for getting questions from http://either.io implemented fully in Rust, using reqwest and some regex magic. Provides asynchronous and blocking clients respectively.

eithers_rust An API for getting questions from http://either.io implemented fully in Rust, using reqwest and some regex magic. Provides asynchronous a

null 2 Oct 24, 2021
🎨🦀 A system information tool for Rustaceans

?? ?? ferris-fetch Inspired by gofetch ?? ??️ Cross platfrom System Info Tool for Rustaceans ?? Installation ?? cargo install ferris-fetch Contributin

Ilya Revenko 107 Dec 19, 2022
Fegeya Elitebuild, small, powerful build system. Written in Rust.

Fegeya Elitebuild Small, powerful, work-in-progress build system. Written in Rust. Features: No functions (all are built-ins) All variables are global

Ferhat Geçdoğan 25 Nov 9, 2022
An i386 operation system written in pure rust for fun and no profit.

OrustS An i386 operation system written in pure rust (for fun and no profit). This operation system is under active developing. Checklist implement a

M4tsuri 10 Aug 12, 2022
A conky-like system monitor made for the sole purpose of teaching myself rust-lang.

Pomky A conky-like system monitor made for the sole purpose of teaching myself rust-lang. It is not as configurable, modular, or feature packed as con

null 3 Nov 17, 2022
Dataflow system for building self-driving car and robotics applications.

ERDOS ERDOS is a platform for developing self-driving cars and robotics applications. Getting started The easiest way to get ERDOS running is to use o

ERDOS 163 Dec 29, 2022
ArbOS operating system, to run at Layer 2 on Arbitrum chains. Also a compiler for Mini, the language in which ArbOS is written.

ArbOS and Mini compiler ArbOS is the "operating system" that runs at Layer 2 on an Arbitrum chain, to manage the chain's operation, maintain security,

Offchain Labs 88 Nov 6, 2022
rusty-riscy is a performance testing and system resource monitoring tool written in Rust to benchmark RISC-V processors.

rusty-riscy rusty-riscy is a performance testing and system resource monitoring tool written in Rust to benchmark RISC-V processors. Objectives To cre

Suhas KV 4 May 3, 2022