[NCR#1 Proposal] zkEmail implementation + KYC (Know Your Community) tool

[Alex-distributed-lab]

Summary

First, we aim to build the zkEmail library in Noir and provide certain primitives to the language ecosystem, such as a regex mechanism tailored for ZK.

Secondly, based on the zkEmail solution, we are going to implement a tool for community driving. The logic is straightforward here:

1. Emails are the most powerful tool for driving and communicating with community members (or client base).
2. Businesses have their client base in the form of email addresses (+ history of interactions). It's how that works now.
3. Businesses use emails to keep their clients and community updated. Good services also provide loyal clients with “goodies” such as discounts, vouchers, and airdrops.
4. Clients receive these bonuses PERSONALLY through email and should PERSONALLY prove this ownership (using zkEmail protocol). It forms strong service <-> community member relations.

As a PoC of the tool mentioned, we would build a solution that allows businesses to make airdrops through their mailing list.

Methodology

Stage 1: Implementation of Noir Primitives

Objective: Engineer regex pattern matching library.
Approach:

• Implement regex transformation paths (Regex → Postfix → NFA → DFA).
• Use auxiliary Sage scripts to adjust parameters and automate configuration dynamically.

Stage 2: Implementation of zkEmail protocol

Objective: Engineer zkEmail library in Noir.
Approach:

• Increase performance by implementing a full Noir version and a hybrid Noir+Rust version.
• Integrate regex for selective verification of email parts, reducing the computational load.

Stage 3: Implementation of PoC of email-powered airdrop

Objective: Show how the zkEmails protocol helps communities driving
Approach:

• Implement the web application that consumes the mailing list and makes the distribution of emails to community members.
• After receiving the email, users can generate appropriate proof and claim tokens reserved by the contract to any preferred EOA.

RegExp implementation Logic:

We envision two possible variants for solving the task of implementing the zkEmail SDK on Noir:

• The full Noir implementation uses a Sage script to pass the message and regex to the Noir program;
• The hybrid implementation with Rust which passes a ready-made state graph to Noir. Noir checks whether the message matches the regex structure or not.

Noir Full Implementation:

The implementation includes the following stages: Regex → Postfix Notation → NFA → Checking the Message. The initial version of the program assumes the use of visible ASCII characters plus space characters, excluding the following control characters, which are encoded in Base64 format.
Operations: The main operations that this regex will support:

op	meaning
.	concatenation character
?	matches 0 or 1 of the previous symbols
*	match 0 or more of the previous (e.g. xy*z could correspond to "xz", "xyz", "xyyz", etc.)
+	matches 1 or more of the previous symbols
|	matches a specific character or group of characters on either side (e.g. a|b corresponds to a or b)
(abc)	a grouping of characters

Hybrid implementation of Noir RegExp with Rust:

In this implementation, Rust will translate the Regex into its final form, i.e., DFA. Then, write this data to the Noir program and the message, and Noir will check the message structure with this regex.
Operations: This implementation will have all the same operations as the Noir full implementation, but some new ones are added:

op	meaning
.	wildcard which matches any character
[]	matches a range of characters (e.g., x or y, or z)
\	used to escape a special character

DKIM Signature Verification Logic:

Inputs: e and m values for RSA, DKIM signature, raw_msg, regex.

1. Check regex pattern: regex_check(raw_msg, regex).
2. Calculate the hash of the message msg_hash = sha256(raw_msg).
3. Check msg_hash == decode_base64(DKIM.body_hash).
4. Unsign the encrypted structure with the public parameters decode_base64(DKIM.signature_value) ^ e % n == x.
5. Check x == sha256(construct_sign_struct(raw_msg))

Solution PoC logic:

Timeline and Deliverables

Stage 1. The Regex library in Noir is tested and validated.

Deliverables. Implementation will have a noir-only version and a hybrid one.
Timeline. 1 month

Stage 2. zkEmail library in Noir, tested and validated.

Deliverables. Enabling full zkEmail proof generation logic in Noir.
Timeline. 1 month

Stage 3. zkEmail-powered airdrop.

Deliverables. Deployed solution. Then we will send airdrops to Distributed Lab team members by emails =)
Timeline. 1.5 months

Team:

Distributed Lab, 10 years of blockchain development:

• Site: distributedlab.com
• Github: github.com/distributed-lab
• Point of contact: Oleksandr Kurbatov, research and cryptography at Distributed Lab
  • Email: [email protected]
  • Twitter

Past contributions to Aztec:
Hashmap lib: #4241
PLUME signature: https://github.com/distributed-lab/noir-plume

Start Date

The next day after the announcement

Additional research points:

• Research decoding of base64 attachment files (e.g., jpg, png, pdf...) and support regex patterns for them.
• Automatic regex calculation for working with common data from several emails.
• Research the synergy and integration with zk social https://rarimo.com/ protocol (we are one of the contributors here).
• Utilization of Aztek Network | Sandbox for better UX.

Questions

Are any specific performance benchmarks for the final ZK Email SDK that are nice to meet?
Are there any additional compliance or security standards we must consider during development?

[YashBit]

@Alex-distributed-lab Hi Alex, is this inspired from the ZK Regex -> Circom tool?

[NikitaMasych]

Hi, @YashBit, for sure, if you are talking about hybridization approach with rust.

[Savio-Sou]

Hi @Alex-distributed-lab, thanks for submitting the proposal!

A few early questions and thoughts:

Potential users

Would be great if you could shine light on teams / projects that showed interest in the idea through the lens of a potential user, if you happen to know any.

Timeline

Noticed that the timeline proposed is >2 months.

Mind that audit partners for NCR#1 are being onboarded with the assumption of a 2-month NCR#1 R&D timeline. If the proposal gets selected, audit scope and timeline review might be needed depending on progress.

(Happy to guide the process then, simply an early heads up.)

[Alex-distributed-lab]

Hi @Savio-Sou, thanks for the response

Regarding the timelines, this is an internal feeling; we will try to do everything faster (there is some reserve in the deadlines), but it is better to focus on the pessimistic scenario. In any case, we should finish the main part within 2 months (so they should be ready for audit) and then switch to the app part.

Let me think about who can be the first consumers.

[Savio-Sou]

Re questions:

Are any specific performance benchmarks for the final ZK Email SDK that are nice to meet?

Can definitely define in more detail as R&D goes, but a good initial target would be matching the current ZK Email implementations (e.g. Circom, Halo2).

Are there any additional compliance or security standards we must consider during development?

Not sure if I understand the question; happy to discuss further if you could elaborate.

[Alex-distributed-lab]

I mean the following points:

• what the code license must be
• IP rights
• other specific things we need to know

[Divide-By-0]

Btw we rewrote zk-regex to support almost all syntax except lookarounds, so I think the easiest way to tackle week 1 (while expanding available syntax) would be to just rip out the circom parts from the existing zk-regex compiler at the step where it generates the min-dfa and transition table 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.

[Alex-distributed-lab]

Good to know, thanks!

[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!