ZK Regex in o1js (Enhancements)

Mina Navigator Proposals
11

Repository Link: GitHub - Shigoto-dev19/zk-regex-o1js: A library for verifying zero-knowledge regular expressions on the Mina blockchain.

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

    • Build a CLI with the same functionality as the zk-regex script.
    • Split reveal options into two variadic options for better collection of inputs for subpatterns or manually entered transitions.
    • Add a checker to validate manually entered reveal transitions:
      • Previously, the compiler wouldn’t complain if some transitions were entered that didn’t exist among the full pattern transitions.
      • It used to attach such transition pairs but would give an error when using the circuit, as non-existent transitions would cause the circuit to throw an error.
      • This was impractical and allowed room for user mistakes.
      • Now, the checker will complain if a non-existent transition pair is entered, logging the first invalid transition pair in the terminal.
      • It will also log all the transitions of the full regex pattern to provide insight into valid transitions that can be revealed.
      • This keeps the user informed about valid reveal transitions and prevents the entry of invalid transitions.
    • Add a --functionName option to specify the function name for the compiled regex circuit:
      • Previously, users would manually add the function name in the TypeScript file where the regex function body was pasted.
      • With this CLI option, the circuit is compiled directly with the functionName specified.
    • Add a --filePath option to manage file output for the compiled regex circuit:
      • Requires the --functionName option to specify the function name for correct integration.
      • If the file already exists, only the compiled regex circuit will be appended.
      • If the file does not exist, it will be created with an import statement for required types and the regex circuit will be added.
      • Previously, users had to manually create the file, import the necessary statements, and paste the compiled regex circuit code.
    • Capture and prepend the command used to execute the CLI as a comment in the compiled regex function:
      • This adds the command used to run the CLI as a comment at the top of the compiled regex circuit function.
      • It helps automate and document the command execution, making it easier to record and reproduce zk-regex commands.

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

    • The ./src/compileExamples.sh script clears the existing examples file and writes all updated regex circuits.
    • This simplifies recompiling regex circuits following updates to the compiler or CLI changes.
    • Running the tests after executing the script ensures the integrity of the changes.
    • Previously, the process involved manually compiling, copying, and pasting circuits into the examples file and then running tests, which was time-consuming and error-prone.
    • The new script streamlines the process, making it quick and efficient to update examples and verify changes with no more manual effort.

  • 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:

    • This includes inclusionRegex for matching ranges and specific exact values.
    • sequenceRegex to validate the existence of a sequence of fields or a subarray within a field array.
    • countInRangeRegex for counting values within a specified range in an array of fields.
    • excludeRegex to validate that an array of fields does NOT contain particular field elements.
    • Unit tests to showcase the integrity and usage of these functionalities.

  • Update README

    • Update instructions following CLI commands.
    • Add more details on instructions and exception handling.
    • Update graphs to reflect the latest changes.

  • Publish NPM package containing the ZK Regex CLI

    • Install the package by running npm i -g zk-regex-o1js.
    • Use zkr or zk-regex as a binary in the terminal.
1 Like