Client-side Zero-Knowledge Proofs: Challenges and Solutions

Original Title: ZKP on the Client-side: Challenges \& Our Solutions

TLDR

Building a good zero-knowledge proof system on the client side is much more challenging than it seems. However, with the development of ZKP, it has become possible to generate ZKP on the client side and verify it on-chain. The year 2024 will be a year when client-side zero-knowledge proof systems enter the public eye. This article will discuss from a technical perspective why client-side zero-knowledge proofs are so difficult, and how OpenID3 addresses the corresponding challenges.

In the Web3 tracks, including decentralized social networks, full-chain games, privacy authentication, and privacy KYC/AML, client-side zero-knowledge proofs will provide very important infrastructure.

I am a cryptographic engineer at OpenID3. As one of the pioneers of client-side zero-knowledge proofs, I would like to briefly discuss why client-side zero-knowledge proofs are so challenging and how OpenID3 addresses these issues in this blog.

What is it like to build a zero-knowledge proof system?

The zero-knowledge proof systems (ZKP) we have today mainly serve to scale Ethereum. Over time, there have indeed been some great client applications, but most are based on the operation of other systems, consist of simple circuits, or do not pay much attention to user experience.

When I introduce myself as a ZKP engineer at industry events, the most common reaction is whether I work for zkSync or if we are building another zkRollup Layer2. After a while, it becomes a bit annoying. It's a bit like saying you live in Singapore, and people start asking if they really have caning. Anyway, I just want to roughly describe the scene here: most ZKP systems are not built for client applications.

Why not? There are several main considerations. Before I delve into the important directions engineers consider, let me introduce some basic components of ZKP.

1. Prover/Verifier: Simply put, the prover program spends a lot of computational resources proving some specific program and corresponding inputs, allowing the verifier program to easily and quickly prove that the prover is honest. For most ZKP systems, the verifier is usually a smart contract.
2. Circuit & Witness: The information held by the prover is called the witness, and the defined program is referred to as the circuit. Given the circuit and witness, a proof can be generated.
3. Public & Private Witness: When constructing the circuit, the witness is private by default, but in some cases, certain information may be marked as public. This public information helps the verifier validate the circuit or execute the logic of the smart contract.
4. Application & Aggregation Proof: Most ZKPs require aggregation. Aggregating multiple application proofs together generates an aggregation proof. Aggregation proofs allow verifiers to batch-verify ZKPs, saving Gas Fees and reducing on-chain information pollution.

Now, after understanding these basic concepts, ZKP engineers typically consider the following points:

1. Prover Time & Memory Consumption
2. Verifier Cost
3. Size: The size of files and keys involves several types, including:
4. Proof Size: The size of the proof, which is usually positively correlated with Gas Fees.
5. Executable Size: The size of the packaged program.
6. Parameter Size: Some ZKP systems require trusted setups, and the size of the trusted setup file is positively correlated with circuit complexity.
7. Key Size: The size of the keys. Some verification systems have very large prover keys. In the early days of OpenID3, we tried to build circuits using Halo2, and the generated prover keys reached up to 3GB.

Client-side ZKP

The priorities of zkRollup proof systems and typical client proof systems are different. Similarly, it is usually difficult to achieve all advantages without making compromises. ZKP has essential differences between client-side and server-side. Generally speaking, zkRollup proof systems run on the server side, where they can allocate nearly unlimited computational resources and ultra-fast networks. However, on the client side, computational resources are very limited, user networks are likely to be unstable, and users will not patiently wait and continuously refresh the webpage.

Thus:

• Prover time and memory consumption are the top priorities for client-side ZKP, while they are much more lenient on the server side.
• File size. For some circuits we write, trusted parameters can be as large as 20MB, and for some ZKP systems, the generated WASM executable files can reach hundreds of MB. We cannot send these files to clients and expect them to be patient with the long wait for downloads. Any executable file, key, or parameter larger than 3MB will be difficult for users to accept.
• On-chain verification costs. The cost of verifying Rollup can be shared by a massive number of users, but client-side ZKP proofs usually require each user to bear the cost.
• Latency. zkRollup does not need to compute aggregation proofs for every block, but client-side ZKP needs to complete as quickly as possible under the system's capabilities. Users will not wait days to verify their proofs on-chain; rather, a few minutes will be the limit of acceptable time for users.

Undoubtedly, building a Rollup-style ZKP system is a very complex task. However, building a functional client-side ZKP system is not an easy task and actually imposes more stringent requirements on system functionality.

Thoughts on ZKP Systems

Based on the above considerations, we began building OpenID3. OpenID3 is an open protocol based on ZKP used to prove the ownership of users' Web2 social accounts on-chain. OpenID3 will prove users' identity credentials on the client side, then publish the ZKP to an open ZKP aggregator network and submit it on-chain. During this process, all user information will not leave the user's local environment and can be verified cheaply and efficiently on-chain. Application scenarios include:

1. Permissionless and decentralized secure on-chain user Web2 identities.
2. Decentralized, self-hosted social login wallets.

The early beta has already verified over 400,000 identity information on the Linea network.

In simple terms, we have achieved the following results:

1. The client will download a WASM executable file of about 2MB in size.
2. The client will generate application proofs in about 30 seconds.
3. Then, the client will pass the application proof to one of the general aggregators and queue it. The aggregator will be triggered regularly. The aggregator will spend a lot of memory and about 3 minutes to aggregate the proofs and return the proofs to the client. The aggregator will also register all public inputs of the proofs into a Merkle tree and publicly disclose the root of the tree as the public witness of the aggregation proof.
4. The aggregator will submit the aggregation proof on-chain, and the smart contract can verify the proof and record the Merkle Tree root at about 250,000 Gas. (Equivalent to the price of a Uniswap call from ETH to some ERC-20 tokens). Currently, a proof contains 32-64 user proofs, and the verification Gas Fee will be shared among these users, making the Gas Fee each user pays for ZKP verification roughly equivalent to a single ETH transfer on-chain.
5. Users can submit a "claim" call and perform a Merkle proof to identify their identity using a hash message, linking the proven ZKP to their address.

Aside from the on-chain address and the identity hash submitted by the user, the aggregator, smart contract, and we know nothing about the user's identity.

How to implement and improve

This part may be a bit technical and requires some background knowledge of ZKP.

1. On the client side, we chose to use Plonky2, which is a ZKP system using FRI+Plonk with Goldilocks. It does not require a trusted setup, has fast proof times, and reasonable memory consumption. We streamlined the circuit to meet the minimum requirements for verifying identity, resulting in a compiled WASM blob of about 3MB.
2. On the aggregator side, we first aggregate Plonky2 proofs into a "wrapped" Plonky2 proof that can aggregate a large number of Plonky2 proofs into one, verifying the correct circuit structure (i.e., users are executing the exact circuit as we expect, compressing public witnesses into a Merkle tree to save space, etc.).
3. After the Plonky2 aggregation, we run the Plonky2 verifier internally in Gnark, which converts the proof and verifier key into a quickly verifiable form on-chain. Gnark aggregation is the main time consumer, taking about 2 and a half minutes.
4. Finally, through the aggregation proof, users can use a general Plonky2+Gnark verifier contract to verify themselves at a low cost, requiring only 211,000 Gas, and with the overhead of on-chain call storage, the verification cost is controlled to below 250,000 Gas.

Currently, OpenID3's ZKP side is working on two tasks:

• We hope to speed up Gnark aggregation time through GPU acceleration and aim for under half a minute;
• We are shaking up tree dependencies to further minimize the size of the executable file, ideally below 1MB.

In Conclusion

Client-side ZKP is a field with too few explorers, and we hope to collaborate with any other teams to standardize the processes we have taken.

• Frameworks and DSLs can be built around easily composable Plonky2 circuits for application proofs.
• We have not yet introduced folding optimizations for many processes, and we expect to achieve significant performance improvements through aggregation folding.
• Aggregator services or general on-chain verification services can be built as key infrastructure for the future of ZKP, bringing security, decentralization, and an excellent developer experience to a larger community.