# RSA Verification Circuit in Halo2 and its Applications
## Introduction
We released an RSA verification circuit compatible with the [halo2 library developed by the privacy-scaling-explorations team](https://github.com/privacy-scaling-explorations/halo2). It allows halo2 developers to write circuits to verify RSA-based cryptographic schemes such as RSA signature, RSA accumulator, and [verifiable delay function based on groups of unknown order](https://eprint.iacr.org/2018/623.pdf). This post describes the background design and its applications.

Github repo: [halo2-rsa](https://github.com/SoraSuegami/halo2_rsa)
## Circuit Specification
Our circuit supports verification of the RSA relationship, i.e., $x^e \mod n$ for the integer $x$ and RSA public key $(n,e)$. At a high level, it provides the following three functions.
1. Modular exponentiation
It takes as inputs the integer $x$ and the RSA public key $(n,e)$, outputs an integer $x^e \mod n$.
2. Modular exponentiation with fixed $e$.
Its functionality is equivalent to that of the first one, except that the exponent integer $e$ is fixed in advance.
3. Pkcs1v15 signature verification.
It takes as inputs the pkcs1v15 signature $c$, the RSA public key $(n,e)$, and the signed message $m$, makes constraints to verify that $c$ is a valid signature for $(n,e)$ and $m$. Note that pkcs1v15 is a specification of the RSA signature defined in [RFC3447](https://www.rfc-editor.org/rfc/rfc3447).

The above functions were developed with reference to the [circom-rsa-verify repository](https://github.com/zkp-application/circom-rsa-verify), which contains a circuit for pkcs1v15 signature verification in the [circom language](https://docs.circom.io/). It first defines a circuit for modular multiplication of big integers, that is to say, integers whose size is larger than that of the native field of the arithmetic circuit, and then verifies the signature by computing modular exponentiation with that circuit. We took a similar approach for our circuits. In addition, the range check, the verification of whether a given integer is within a certain range, was optimized with a lookup table.

Specifically, the constraints for the big integer computation is defined as follows.

## Big Integer Computations on the Circuit
A big integer is represented by multiple values in the native field of the arithmetic circuit, each value being called a limb. It is classified into two types: **Fresh type** and **Muled type**. The former type is assigned to the big integers that have not yet been multiplied, while the latter type is assigned after multiplication. We distinguish them to manage the maximum value of the limbs; the limbs of the Fresh type big integer must fit into $w$-bit, and those of the Muled type may overflow it.

For example, we consider a 2048-bit big integer that consists of 32 64-bit limbs. The big integer has the Fresh type when newly allocated on the circuit, and its limb value is less than $2^{64}$. When two big integers are added or subtracted, the resulting big integer has the Fresh type, and only the number of limbs is modified. However, in multiplication, the output big integer has Muled type, whose limb can be larger than $2^{64}-1$. This is because the big integer multiplication is computed in the same way as polynomial multiplication. Formally, for two big integers $a=a_0x^0+a_1x^1+\dots+a_{31}x^{31}$ and $b=b_0x^0+b_1x^1+\dots+b_{31}x^{31}$, where $x=2^{64}$, their multiplication is defined as follows.
$$ab=(a_0x^0+a_1x^1+\dots+a_{31}x^{31})(b_0x^0+b_1x^1+\dots+b_{31}x^{31})=\sum_{n=0}^{62}(\sum_{i+j=n}a_ib_jx^n)$$
To convert the Muled type big integer back into the Fresh type one, our circuit provides a refresh function that creates a big integer equal to the given big integer where each limb value is 64-bit with increasing the number of limbs. By refreshing the product with that function, multiplication can be performed multiple times.

Our circuit also supports modular multiplication, i.e., $a * b \mod n$ for big integers $a,b$ and a modulus $n$. It first calculates the quotient $q=\frac{ab}{n}$ and the remainder $r=ab \mod n$ without making constraints. It then constrains $q$ and $r$ to satisfy the following conditions.
1. The product $ab$ is equal to $qn+r$.
2. Each limb of $q$ and $r$ is in the range of $[0,2^{64})$.

To verify the first condition, the (not modular) multiplication function is used. For the second condition, existing circuits such as [circom-bigint](https://github.com/alex-ozdemir/circom-bigint) assign a new value to each bit and verify that the composed value is equal to the original value; however, our circuit uses a lookup table. This optimization allows the prover to prove that multiple values are in the specified range in batch as described in [Plookup protocol](https://eprint.iacr.org/2020/315.pdf).

By repeating the modular multiplication described above, the modular power $a^e \mod n$ for an exponent big integer $e$ is computed. Formally, it is implemented as follows.
1. Decompose $e$ into $n$ bits $(e_0,e_1,\dots,e_{n-1})$.
2. Let $y=1$ be a modular power result.
2. For $i \in \{0,\dots,n-1\}$, update $y$ to $e_iya^{2^i}+(1-e_i)y$.

Notably, if $e$ is fixed in the circuit, we can reduce the number of the modular multiplication because $ya^{2^i}$ does not need to be computed for $i$ where $e_i=0$ holds. Our circuit switches the definition of the constraints depending on whether $e$ is variable or fixed. Therefore, when $e$ of the RSA public key is fixed, e.g., pkcs1v15 signature verification, the number of constraints for modular multiplication is minimum.

## Application: ZK-Mail
As an application of the RSA verification circuit, we are considering ZK-Mail, a smart contract that performs email verification using ZKP. Today, digital signatures, especially RSA signatures, are widely used in email protocols such as S/MIME and DKIM to authenticate email senders. Our main idea is that a smart contract can authenticate those emails by verifying the RSA signatures with ZKP. If they pass the authentication, the smart contract can interpret their contents as oracle data provided by the email senders.

The smart contract described above is also useful as a contract wallet. Instead of using the wallet application to make a transaction, the user sends an email to the operator of the contract wallet specifying the transfer amount and the destination in its email message. The operator generates a ZKP proof indicating that the received email has been authorized, submitting it to the smart contract. The smart contract verifies the proof and transfers the user's assets according to the contents of the email. It allows users to manage their assets on Ethereum without modifying current email systems or installing new tools. If the user is different from the administrator of the sending email server, the security of the user's assets depends on trust in the administrator because the administrator can steal them by forging the user's emails. However, trust in the operator is not necessary. This is because even if the operator modifies the contents of the received emails, the operator cannot forge the signature corresponding to the email sender. In summary, this is a custodial wallet whose security is guaranteed under trust in the email server administrator, allowing users to manage their assets by simply sending emails using their existing email services.

In the following, we present two situations where the ZK-Mail can be used.

### Scenario 1: Email as oracle data
#### Players and situations
- Alice delivers the latest cryptocurrency prices via email. She attaches her RSA signature to the email following the DKIM protocol.
- Bob subscribes to Alice's emails and provides them for some DeFi contracts as price oracle data.

#### Assumptions
- A public key corresponding to Alice's domain name (e.g. alice.com) is published in DNS and not changed.
- Alice's public key and email address are registered in the ZK-Mail contract in advance.

#### Procedures
1. Bob receives Alice's latest email.
2. Bob extracts the cryptocurrency name and price data from the contents of the email.
3. Taking Alice's RSA signature and the header/contents of the email as private inputs (witnesses), and her public key, her email address, and the cryptocurrency name and price data as public inputs (statements), Bob generates a ZKP proof confirming the following conditions.
- The RSA signature is valid for the header/contents and the public key.
- The From field in the header is equivalent to the provided email address, i.e., Alice's email address.
- The contents include the cryptocurrency name and price data.
4. Bob provides the price oracle contract with the cryptocurrency name and price data and the ZKP proof.
5. The contract calls the ZK-Mail contract with the provided data. It verifies the ZKP proof using Alice's public key and email address registered in advance.
6. If the proof passes the verification, the price oracle contract accepts the provided name and price data.

### Scenario 2: Email as transaction data for the contract wallet
#### Players and situations
- Alice operates an email service. She attaches her RSA signature to her users' emails following the DKIM protocol. Her domain name is alice.com.
- Bob is a user of Alice's email service. His email address is [e-mail].
- Carol operates a contract wallet service. Her email address is [e-mail].

#### Assumptions
- A public key corresponding to Alice's domain name (e.g. alice.com) is published in DNS and does not change.
- Alice's public key is registered in the ZK-Mail contract in advance.
- Bob already registered Carol's wallet service. His email address is registered in the ZK-Mail contract, and he has 2 ETH in his wallet.
- **Alice never attaches her RSA signature to forged emails.**

#### Procedures
1. Bob wants to transfer 1 ETH to his friend whose email address is [e-mail].
2. Bob sends an email to [e-mail]. Its message is "Transfer 1 ETH to [e-mail]".
3. Alice attaches her RSA signature to the Bob's email.
4. Carol receives the email from Bob. She extracts the transfer amount and the destination (1 ETH and [e-mail] in this case) from the contents of the email.
5. Taking Alice's RSA signature and the header/contents of the email as private inputs (witnesses), and her public key, sender's email address, and the transfer amount and the destination as public inputs (statements), Carol generates a ZKP proof confirming the following conditions.
- The RSA signature is valid for the header/contents and the public key.
- The From field in the header is equivalent to the provided email address, i.e., [e-mail].
- The message in the contents is in the form of "Transfer (transfer amount) to (destination)".
6. Carol provides her service's contract with transaction data including the transfer amount and the destination and the ZKP proof.
7. The contract calls the ZK-Mail contract with the provided data. It verifies the ZKP proof using Alice's public key and Bob's email address registered in advance.
7. If the proof passes the verification, the contract wallet transfers Bob's 1 ETH to the wallet corresponding to the email address of [e-mail]. (In detail, the contract wallet has storage where the hash of the email address is mapped to the ETH balance. It decreases 1 from the balance of Hash([e-mail]) and increases that of Hash([e-mail]) by the same amount.)