# ZK Regex in o1js (Enhancements)

**URL:** <https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271>\
**Category:** Mina Navigator Proposals\
**Created:** [June 2, 2024, 6:37pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271 "2024-06-02T18:37:04Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![hgedia](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/hgedia/32/1734_2.png) [@hgedia](https://forums.minaprotocol.com/u/hgedia)\
**Post date:** [June 2, 2024, 6:37pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/1 "2024-06-02T18:37:04Z")

</div>

This topic is to discuss the proposal submitted by @Shigoto-dev19  
Please see below for the details of the proposal and discussion.

**31st July, 2024**  
_Current status: Delivered_  
_Presentation: [Link](https://www.youtube.com/watch?v=M6T3eEtgRwE&list=PLnupbCpmBldYfr-68e5UfKq81Vx-pw3xI)_

**16th July,2024**  
_The end date of this project is extended to 22nd, July after discussing with the proposer_

**14th June,2024**  
_Current status: Funded_  
_Funding Note: We see this proposal to introduce a package/tooling that could be very useful to build several applications in the ecosystem and thus has a high impact. The builder is part of the ecosystem and has delivered successfully so the risk is classified as low. Budget is inline with the work proposed._

**2nd June, 2024**  
_Current status: Under Consideration._  
_Opened for community discussion on : 02 June, 2024._

---

<div class="post-metadata">

**Author:** ![Shigoto-dev19](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/shigoto-dev19/32/2043_2.png) [@Shigoto-dev19](https://forums.minaprotocol.com/u/Shigoto-dev19)\
**Post date:** [June 2, 2024, 10:15pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/2 "2024-06-02T22:15:43Z")

</div>

## Title

Further Development of ZK Regex in o1js

## Project Background

- **ZK Regex in o1js** was a project developed as part of the Mina Navigators S1 program during March and April 2024.
- The project evolved from initial research and theoretical learning to a functional circuit compiler by the end of April 2024.
- This work is inspired by the original [zk-regex by zkEmail](https://github.com/zkemail/zk-regex), a Rust compiler that outputs regex Circom or Halo2 circuits as strings in the terminal given inputs as a JSON file.
- I can confidently declare that zk-regex in o1js excels in both performance and developer experience (devX) compared to the original work.
- ZK Regex in o1js outputs a regex circuit with a single command, given a regex pattern and optional sub-patterns to reveal if desired.
- ZK Regex represents a groundbreaking advancement in zero-knowledge proof ZKP technology, enabling the verification of text data within a ZKP framework.

For more details on the project background, please refer to the project’s [README](https://github.com/Shigoto-dev19/zk-regex-o1js?tab=readme-ov-file#description).

## Proposal Overview

The zk-regex project was developed in a short amount of time and still has room for improvement, which is the main purpose of this proposal.

### Problems

1. Currently, zk-regex-o1js is a compiler that relies on process arguments to write a specific regex circuit into the terminal.
  - Some users asked to use the exisiting zk-regex as an npm package but so far, this is not possible because the compiler is not structured as an exectuable binary to be published.
  - In order to use the regex compiler, it is required to clone the repo and follow the readme to run the following [possible commands](https://github.com/Shigoto-dev19/zk-regex-o1js?tab=readme-ov-file#options-graph).

2. Some regex patterns require a deep understanding of syntax support.
3. The compiler code has interconnecting components that make it delicate to change and difficult for other developers to contribute.
4. It’s challenging to implement conditional control flow on field element processing due to the algebraic nature of zk circuits. Users rely on `Provable.switch` or `Provable.if` to build nested flow to validate conditions
  - Example: `f1 or f2 or (f1 and f3 and f4) or (range(f2, f3))`.

### Solutions

1. Wrap the compiler into a CLI using the oclif/commander package to create a zk-regex CLI and publish the binary as an npm package.
2. Parse raw regex patterns to specify the exact number of repetitions for certain inputs.
3. Refactor the compiler code into a class to separate the regex circuit building process and facilitate component tweaking.
4. Utilize regex theory to operate on field elements instead of UTF-8 bytes. Users can use the regex utility to generate this control flow:
  - Enter regex pattern `(f1 | f2 | (f1 f3 f4) | [f2-f3])`
  - Copy generated circuit from terminal
  - Paste the circuit as a function inside a zkapp
  - Use the function to validate the control flow
  - Also possible for any desired regex/flow pattern

### Impact

- **Adoption** : Enhances the Mina ecosystem by providing a tool for processing text/strings inside circuits, bridging many web2 protocols to Mina.
- **Novel Applications** : With regex theory operating on finite fields, it is possible to build unprecedented and novel primitives in o1js, expanding the toolkit available for developers.
  - For example, the `(a|b|[0-9])` regex pattern matches the character `a` alone, `b` alone, or any digit between `0` and `9`.
  - The current compiler matches the UTF8 bytes of the pattern characters, in this case, `61` for `a`, `62` for `b`, and the range between `30` and `39` for UTF8 digits.
  - The circuit accepts the bytes as `UInt8` field elements, but the compiler can be upgraded to process full field elements or `Bool` inputs for weaving complex multiplexers or any other pattern following DFA theory.
  - In this example, if we replace `a` and `b` with certain field elements, i.e., `f1` for `a` and `f2` for `b`, and `0` and `9` with `f3` and `f4`, we create a multiplexer that returns `Bool(true)` for the equality of `f1` or `f2` alone or any field in the range between `f3` and `f4`.
  - This is a simple example, but imagine the extent of implementations that DFA inside a circuit can open up for developers on Mina.

- **Attraction** : zk-regex will attract developers to Mina by offering ready-to-use primitives for deploying web2 protocols.
- **Innovation** : zk-regex in o1js is the first adaptation of the original zk-regex in a different proof system, following the release of work in Circom and Halo2 by the zkEmail team.

### Audience

- Developers in the Mina ecosystem.

## Architecture & Design

### Detailed Design/Architecture

- For development workflow details, please refer to the project’s [readme](https://github.com/Shigoto-dev19/zk-regex-o1js?tab=readme-ov-file#raw-regex-syntax-guide).

### Vision

- Currently, the compiler outputs a regex circuit in the terminal as a string to be copied.
  - Ideally, the compiler would output generic circuits at runtime.
  - Develop a generic compiler that operates on arbitrary field elements or other types (UInt32, Bool, UInt64, etc.) in o1js.
  - This proposal is a step toward realizing this vision.

- Support rich regex syntax similar to common programming languages.

### Existing Work

- Yes, [zk-regex-o1js](https://github.com/Shigoto-dev19/zk-regex-o1js).

### Production Timeline

- The project is already operational in o1js.
- Requesting funding for one month, with the possibility of extending with a second proposal depending on future progress/changes.

## Budget & Milestones

### Deliverables

- An npm package with an executable to generate zk-regex circuits in o1js based on various regex patterns.
- Expanded regex pattern syntax support:
  - Specific range grouping (e.g., `[b-x]`).
  - Specific repetitions (e.g., 2, 3, 5 times).

- Refactor the compiler code into a class to separate the regex circuit building process.
- Innovative example of a regex circuit operating on full-size field elements or Bool instead of UTF-8 bytes.
- Updated documentation for easy usability and adoption.

### Project Timeline

- 1 month.

### Budget Requested

- 8,000 MINA.

### Wallet Address

- _B62qpeTKjVfijTqEmpBmCej2kj2oEpoMTWrbt1U48EZEz22aP9FsFvX_

## Team Info

### Proposer Github

- [Shigoto-dev19](https://github.com/Shigoto-dev19).

### Proposer Experience

- Built various projects during Navigators S1:
  - sha256-o1js.
  - mina-battleships.
  - zk-regex-o1js.

- Conducted a **mina-mastermind** project during the **Encode: ZK Bootcamp**.
- Building zkEmail and its primitives in o1js.

### Team Members

- Mahmoud Kaffel.

### Achievements

- ZK Hack Istanbul **“Chewing Glass”** prize winner for building technically difficult projects (sha256-o1js). Also won the o1Labs prize for the crypto primitives category.
- Navigators S1 badge.
- zkIgnite cohort3 grantee for building zkEmail in o1js.

## Risks & Mitigations

- **Complexity** : zk-regex development is delicate.
- **Syntax Expansion** : Expanding syntax support might require significant changes to AST parsing and extensive testing.
- **Code Refactoring** : Wrapping compiler code might disrupt component connections; if issues arise, changes will be reverted to maintain functionality.

---

<div class="post-metadata">

**Author:** ![anks](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/anks/32/2048_2.png) [@anks](https://forums.minaprotocol.com/u/anks)\
**Post date:** [June 3, 2024, 1:20pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/3 "2024-06-03T13:20:14Z")

</div>

So the improvements will allow to derive functions logically composed of simpler regex functions by extending the currenly supported syntax instead of dealing with o1js.Provable control flow functions?

---

<div class="post-metadata">

**Author:** ![Shigoto-dev19](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/shigoto-dev19/32/2043_2.png) [@Shigoto-dev19](https://forums.minaprotocol.com/u/Shigoto-dev19)\
**Post date:** [June 3, 2024, 3:15pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/4 "2024-06-03T15:15:46Z")

</div>

For a complicated control flow, it’s possible to use a simple regex pattern and compile a function instead of weaving the logic manually with `Provable.if` or `Provable.switch` APIs.

Expanding the regex syntax is a separate deliverable that will aid in abstracting long or repetitive regex patterns.

I hope this clarifies things! ☀

---

<div class="post-metadata">

**Author:** ![zk\_kirol](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/zk_kirol/32/2046_2.png) [@zk\_kirol](https://forums.minaprotocol.com/u/zk_kirol)\
**Post date:** [June 7, 2024, 9:05pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/5 "2024-06-07T21:05:06Z")

</div>

hey, great work!

I wanted to understand bit more why there is need to make the package as CLI ?  
Maybe I’m oversimplifying it but if a developer want to create some particular circuit based on some pattern, ‘in-line’ code could potentially create it.

Maybe that can be somehow useful

> **[Using the Compiler API](https://github.com/microsoft/TypeScript/wiki/Using-the-Compiler-API)**
>
> TypeScript is a superset of JavaScript that compiles to clean JavaScript output. - microsoft/TypeScript

regardless even as CLI I see it as very valuable package !

---

<div class="post-metadata">

**Author:** ![Shigoto-dev19](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/shigoto-dev19/32/2043_2.png) [@Shigoto-dev19](https://forums.minaprotocol.com/u/Shigoto-dev19)\
**Post date:** [June 11, 2024, 9:52am UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/6 "2024-06-11T09:52:34Z")

</div>

Good point! Thank you for the comment! This question was the motivation to add a CLI deliverable to the proposal.

I’m not sure if it’s possible to compile binary executable files from the ‘Compiler API’ link you attached. Before the proposal, I even tried using external packages to generate binary files from the existing TS regex compiler files to publish as npm packages, but they didn’t work and things got chaotic.

Initially, my intention was to have zk-regex in o1js as executable ‘in-line’ code. This would allow Mina devs to execute the regex commands as shown in the project’s readme, offering greater flexibility and integration within a project’s codebase.

However, some devs requested the project as an npm package. To accommodate this, the regex compiler would be better suited as a binary executable CLI. CLI packages like oclif or commander offer cross-platform commands in npm package scripts, enhancing usability.

Additionally, a CLI provides better in-terminal documentation, abstracts complexity, and is more practical for developers. For example, instead of opening the codebase and executing a command with a specific regex pattern, a global executable package would streamline the process and be more convenient.

All in all, while ‘in-line’ code is sufficient and operational, the proposed CLI package will be more practical, readable, and easier to use.

---

<div class="post-metadata">

**Author:** ![hgedia](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/hgedia/32/1734_2.png) [@hgedia](https://forums.minaprotocol.com/u/hgedia)\
**Post date:** [June 14, 2024, 8:54am UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/7 "2024-06-14T08:54:25Z")

</div>

This application is approved for Funding.

We see this proposal to introduce a package/tooling that could be very useful to build several applications in the ecosystem and thus has a high impact. The builder is part of the ecosystem and has delivered successfully so the risk is classified as low. Budget is inline with the work proposed.

---

<div class="post-metadata">

**Author:** ![Shigoto-dev19](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/shigoto-dev19/32/2043_2.png) [@Shigoto-dev19](https://forums.minaprotocol.com/u/Shigoto-dev19)\
**Post date:** [July 2, 2024, 12:24pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/9 "2024-07-02T12:24:04Z")

</div>

Here is the mid-point progress report for the zk-regex enhancements:

- **Added Features:**

- **Enhanced Meta Character Support:**

- **Ensured Comprehensive Syntax Parsing:**

- **Performance Improvements:**

- **Code Refinements:**

---

<div class="post-metadata">

**Author:** ![hgedia](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/hgedia/32/1734_2.png) [@hgedia](https://forums.minaprotocol.com/u/hgedia)\
**Post date:** [July 16, 2024, 10:15am UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/10 "2024-07-16T10:15:53Z")

</div>

The end date of this project is extended to 22nd, July after discussing with the proposer

---

<div class="post-metadata">

**Author:** ![Shigoto-dev19](https://yyz1.discourse-cdn.com/flex035/user_avatar/forums.minaprotocol.com/shigoto-dev19/32/2043_2.png) [@Shigoto-dev19](https://forums.minaprotocol.com/u/Shigoto-dev19)\
**Post date:** [July 22, 2024, 6:59pm UTC](https://forums.minaprotocol.com/t/zk-regex-in-o1js-enhancements/6271/11 "2024-07-22T18:59:19Z")

</div>

Repository Link: [GitHub - Shigoto-dev19/zk-regex-o1js: A library for verifying zero-knowledge regular expressions on the Mina blockchain.](https://github.com/Shigoto-dev19/zk-regex-o1js)

With these milestones achieved, the deliverables of this proposal are successfully completed. Here is a report detailing the progress and enhancements made after the midpoint milestones:

- **ZK Regex CLI Development**

- **Add a new shell script** to automate the compilation of regex examples:

- **Add various field regex examples** that operate on full field elements, demonstrating how regex DFA theory can be leveraged to create different primitives for processing field arrays and handling conditional control flow:

- **Update README**

- **Publish [NPM package](https://www.npmjs.com/package/zk-regex-o1js) containing the ZK Regex CLI**