[NCR#1 Proposal] Regex.nr: A Noir Library for Compiling Regular Expression Circuits for Text Verification

[mohammed7s]

Summary

Regex.nr is a Noir library designed to compile zero-knowledge regular expression (zk-regex) circuits. This library facilitates the verification of string data within a zero-knowledge circuit, enabling privacy-preserving applications. Regex.nr is particularly valuable for applications such as secure email proofing, where it can privately and efficiently verify email body components. Additionally, it is applicable to other domains requiring text verification, such as secure messaging or confidential document validation.

Methodology

Research Approach:

1. Study Existing Implementations: Analyze existing zk-regex implementations, such as Circom, Halo2, and o1js.
2. Leverage Noir-Specific Features: Utilize Noir-specific features like ROM tables and ultrahonk.
3. Extensive Testing: Focus on comprehensive testing to ensure robustness.

Design Strategy:

Our design will follow the general approach of the original zkemail regex library which has the following funcionalities:

• AST (Abstract Syntax Tree): Parse regular expressions into an abstract syntax tree.
• NFA (Nondeterministic Finite Automaton): Convert the AST into a Nondeterministic Finite Automaton.
• DFA (Deterministic Finite Automaton): Transform the NFA into a Deterministic Finite Automaton.
• Min-DFA (Minimal Deterministic Finite Automaton): Minimize the DFA to produce the minimal deterministic version.
• DFA JSON Serializer: Serialize the Min-DFA into a JSON format, including transition details.
• Compile Noir Circuit: Produce the desired circuit corresponding to the transitions.

The exact architecture of the project will be determined by the end of the research phase.

Timeline and Deliverables

• Milestone 1: Research Phase

  • Objective: Study regex implementation, Noir-specific features, and review regex theory.
  • Deliverable: Regex.nr architecture
  • Completion Date: 20.09 (Duration: ~2 weeks)

• Milestone 2: Implement Core Functionalities

  • Objective: Complete AST, NFA, DFA
  • Deliverable: Tested functionalities and progress report for month 1
  • Completion Date: 05.10 (Duration: ~2 weeks)

• Milestone 3: Advanced Functionalities

  • Objective: Complete Min-DFA and DFA JSON serializer
  • Deliverable: Tested functionalities
  • Completion Date: 20.11 (Duration: ~2 weeks)

• Milestone 4: Final Compilation and Documentation

  • Objective: Complete the compiler and create documentation
  • Deliverable: Fully tested library with documentation
  • Completion Date: 06.11 (Duration: ~2 weeks)

Team

• Matteo (Core Engineer)

  • Contact: @Matteo_Mer (Telegram)
  • Previous Work: Jolt contributor
  • GitHub: https://github.com/MatteoMer

• Mohammed (Core Engineer)

  • Contact: @m38mah (Telegram)
  • Previous Work: zkemail o1js
  • GitHub: https://github.com/mohammed7s

• Shigoto (Reviewer)

  • Contact: @mamudKFL (Telegram)
  • Previous Work: Author of regex-o1js library
  • GitHub: https://github.com/Shigoto-dev19

Supported by:

• Jack Gilcrest (Noir Developer)
  • Contact: @jp4g0x(Telegram)
  • Previous Work: kemail.nr, battlezips
  • GitHub: https://github.com/jp4g

Start Date

Preferred start date: 09 September 2024

[Divide-By-0]

You should be able to rip steps 2 and most of 3 fully out of the zk-regex compiler we put up -- it automatically strips all the looping functions like lookarounds and generates the min-dfa from the regex expression! Then, instead of converting the gates into arithmetic gates like circom, you can just make lookups like the halo2 design instead.

[Savio-Sou]

Selected proposals for NCR#1 are announced: https://github.com/orgs/noir-lang/discussions/5932

Thank you for your support on the initiative. NCR is just one of the many ways to start your explorations with Noir, check the announcement for more potential ways to collaborate.

Let's bring the world ZK!