Introduction

This is a report from the R&D team at a42x. We are building zk circuits that enable people to prove their possession of a My Number Card, a personal identification card issued by the Japanese government, while hiding the information inside the card. We have conducted an experiment that implements MVP circuits in both Circom and Halo2 to see which proof system is more suitable for our use case.

Overview

Brief summary about My Number Card specifications

There are two certificates in the My Number Card. In the following report, we will treat the electronic certificate for user identification as the certificate that is easier to handle. The differences between the two certificates are described below. Within that certificate there is a TBS Certificate associated with the user’s information and the government’s signature (To be precise, it is a signature by a certificate authority operated by Japan Agency for Local Authority Information Systems, but in this report, for simplicity, we will refer this organization as government.) on that information. The TBS Certificate also contains the public key (modulus and exponent) with which the user generates the RSA digital signature. The format of the RSA digital signature used for the My Number Card follows the RSASSA-PKCS1-v1.5 scheme, and the exponent is the same for all users at 65537. For simplicity, modulus is referred to as “public key” in the following text.

Circuit Detail

To prove possession of a My Number Card, and create an AA wallet associated with the card, one has to implement roughly 3 things in the circuit:

  • Generate a SHA256 hash
  • Verify a RSA signature
  • Generate a Poseidon hash

Summary of inputs and outputs:

  • Public inputs
    • The government’s public key which they use to verify TBS certificate
    • The signature from government inside the My Number Card
  • Private inputs
    • TBS certificate inside My Number Card
    • Public key
    • user secret
  • Outputs
    • Identity Commitment
    • True or False of the verification for TBS certificate We verify the validity of the TBS Certificate by hashing the information in the TBS Certificate using the SHA256 circuit and inputting it into the RSA validation circuit along with the government signature and public key. It also reads the public key in the TBS Certificate and performs poseidon hash with the user secret to generate an identity commitment.

Here is the example of the ASN .1 DER encoded certificate inside My Number Card and conceptual diagram for this circuit.

Figure1. The example of the ASN .1 DER encoded certificate inside My Number Card


Figure2. Conceptual diagram for this circuit

What is an identity commitment?

The Japanese government knows every citizen’s public key. Thus, proving that you know your public key is not enough to prove your identity. To prevent the government from tracking your on-chain activity, we came up with this identity commitment scheme. To create an AA wallet, you first generate an identity commitment. It sounds fancy but it’s just a C = Poseidon(P, S) where P is your public key and S is a user secret chosen by you. And you then generate a zero-knowledge proof that proves a) P is signed by the Japanese government. b) you know S. Then you send C and the proof to the factory contract. Notice that you don’t disclose P or S here. The factory contract will create your wallet account associated with C for you. This scheme lets you create an AA wallet associated with your My Number Card and your user secret. This scheme prevents the government who knows your public key P from tracking your on-chain activity since the government doesn’t know S.

Referenced Circuit

On the halo2 side, we have used these implementations

On the Circom side, we have used these implementations

Benchmarks

To take benchmarks we have used these instances

  • High performance
    • Google Compute Engine c2d-highcpu-112 (vCPUs: 112, RAM: 224GB)
  • Normal performance
    • Google Compute Engine e2-standard-8 (vCPUs: 8, RAM: 32GB)
Table 1. Benchmarks for the circuit above

Conclusion

Based on the above research, we have decided to use Circom + Groth16 for the current MynaWallet considering the time required to generate the proof and the gas required for verification. We also plan to research and develop client-side zkp generation using libraries such as mopro, which are highly compatible with this technology selection. However, we are still working on other functions not introduced in this report and will continue to search for the ideal proof system in the future.

Appendix

Halo2

We implemented two versions of the MVP circuit for Halo2.

Using halo2-sha256-unoptimized

We first experimented with this SHA256 implementation. This circuit is implemented on top of halo2-base which is a magical framework developed by axiom that lets us choose the number of columns the circuit consumes. We configured the circuit to consume just 1 column, and the result was 318891 gas which roughly is $32 (as of 2023/11/30). This is cheap! But the flip side is that it takes too much RAM to prove. We benchmarked the circuit in a machine with 224GB RAM, and the time it took to generate a proof was roughly 100 seconds. This bloated RAM requirement is mainly because of the number of cells the circuit consumes, which is over 2^23 in our case. A question arises: Is it an acceptable UX that you need a monster machine just to prove you live in Japan?

Using PSE’s SHA256 implementation

The alternative SHA256 implementation we used is based on this which is a circuit optimized for faster proof generation. This enabled us to generate a proof for our MynaWallet MVP circuit in roughly 8 seconds.

But the flip side is that it takes too much gas to verify the proof on-chain. A proof verification contract generated by this consumes 5586597 gas (= roughly $250 at the time of 2023/11/30) to verify a proof for our MVP circuit. This bloated gas cost is mainly because of the number of columns the circuit consumes, which is over 200 in our case. A question arises: Is there a better way?

The path going forward

It seems that there is a way to make the verification gas cost cheaper for a circuit with many columns. privacy-scaling-explorations/snark-verifier provides a way to compress a big proof into a tiny one. We’re currently learning how it works. We’ll experiment with this method.

Circom & weak eKYC Demo App

RSA verification circuit for normal use

The zk circuit described above is designed for the registration for the first use of MynaWallet. On the Circom side, in addition to the registration circuit, we have built a circuit for normal-use. The normal-use circuit is simply designed for signing UserOperation with My Number Card and executing tx through an AA wallet. This normal-use circuit performs the following verifications:

  • Verify the correctness of the user by calculating the identity commitment from the public key and the user secret while hiding that information
  • Verify the relationship between the public key, the UserOperation to be signed, and the signature with the RSA digital signature circuit The benchmarks for the normal circuit are as follows:
  • constraints: 150121
  • proving time
    • on high performance instance: 9.48 sec
    • on normal performance instance: 5.3 sec
  • smart contract size: 1.83 kB
  • verification gas on chain: 208392 gas

Weak eKYC demo app

We have tried to incorporate the zk circuit we have created into an iOS application we had already built. Here is a demo of the application.

demo video

It may be hard to understand just by looking at this demo video, but behind the scenes, the proof is generated for the information in the My Number Card, the UserOperation of AA wallet is created from that proof, and the weak eKYC of AA wallet is done via the verification contract. Weak eKYC is the term we use in our team and expresses the situation that the user of this AA wallet is at least a person entitled to have a My Number Card in this context. The problem is, since it is not possible to generate the proof on the client side now, we need to send the information in My Number Card to our server which is not ideal and should be avoided when we start selective disclosure. As mentioned above, we will continue to research and develop client-side proof generation using libraries such as mopro.

Here is the sequence diagram of this eKYC demo app.

Figure 3. Sequence diagram of this eKYC demo app

Extraction of public key from the certificate in the My Number Card

My Number Card contains two certificates in addition to one key pair for generating RSA digital signatures, and each certificate plays a different role.

  • Electronic certificate for user identification
    • Used when logging in to Internet websites or multi-purpose terminals at convenience stores.
    • Contains information about the public key of the RSA digital signature
  • Electronic certificate for the bearer’s signature
    • Used when creating or submitting electronic documents over the Internet
    • In addition to information about the public key, contains the user’s personal information, which can be used for selective disclosure In the case of the Electronic certificate for the bearer’s signature, personal information appears before the public key, so the position where the public key starts varies from user to user, and it’s difficult to read the public key in the zk circuit. On the other hand, the Electronic certificate for the bearer’s signature can be used to verify the correctness of this personal information. The MynaWallet team is currently researching how to efficiently verify and selectively disclose these personal information while preserving their privacy.

What you can expect for the current MynaWallet

In the current implementation, MynaWallet is an AA wallet that allows you to operate by a simple tap of your My Number Card. As MynaWallet does not require the management of seed phrases and you can manage your assets with the card issued by the Japanese government, it can achieve the ideal UX and security for mass adoption. It also ensures your privacy by using the zk circuit introduced above. However, Sybil resistance does not exist in the current implementation, since you are able to create multiple MynaWallet accounts from one public key by providing different user secrets. We can achieve Sybil resistance if we do not require a user secret when you create MynaWallet, but in that case, the government can track your on-chain activity. (There is actually a gradient and even if Sybil resistance is ensured, privacy is also ensured for the general public.) We are also currently researching the ideas that would solve both Sybil resistance and privacy at the same time.

FAQ

  • Could the government manipulate the assets in MynaWallet?
    • This is not possible under the specifications.
    • The private key is stored in a secure element within the My Number Card, and any attempt to forcibly retrieve that information will destroy the information itself.
  • Could the government track MynaWallet’s on-chain activity?
    • This is not possible with the current MynaWallet implementation.
    • For a detailed explanation, please read the section on identity commitment.
  • Will the personal information inside My Number Card be disclosed?
    • Nothing, including my number, will be made public under the current implementation.
    • Depending on the intended use, we are considering a version that publishes the public key for RSA digital signatures, but even in that case, it is impossible for the general public to link your on-chain identity to your real identity.
    • When development progresses to the practical stage, we plan to publish the information, including precautions for use.