Skip to main content

3 posts tagged with "zkp"

View All Tags

PSE Core Program 2024 Capstone Project

· 7 min read
Jimmy Chu
Jimmy Chu
Site Author

PSE Core Program​

In the past two months, I got into PSE Core Program and have intensively studied zero-knowledge cryptography. In the first five weeks, we have a curated list of materials to study, ranging from cryptographic primitives such as Merkle tree, symmetric and asymmetric encryption to going more in-depth about various zk-SNARK protocols such as Groth16 and PLONK, and finally being introduced to the frontier of cryptography, or so they are called, including multi-party computation (MPC) and fully homomorphic encryption (FHE).

In the last three weeks of the program, we are open to scoping and working on our project to put the previous learning into practice. We can either tackle issues from various PSE projects or develop our idea. I decided to build a dApp end-to-end, meaning:

  1. Having a zk-SNARK component generating proofs on the client side (front end),
  2. Having a smart contract component that verifies the proof on-chain and
  3. Building the front end that interacts with users and connects the above two components.

This way, I will be able to see how they connect and how each component interfaces with the others. So let this be the goal!

Capstone Project: Number Guessing Game 🎮​

I decided to build a Number Guessing Game. In this game, the goal of each player is to guess the closest to the mean of submissions from all participating players. Each game is divided into multiple rounds. Players first commit to a guess between 1 and 100. The guess value and a randomly generated value, aka nullifier, are processed through a zk-SNARK circuit on the client side, and the commitment [Poseidon(guess, nullifier), Poseidon(nullifier)] and proof are then submitted on-chain.

After all players have submitted their commitments and proofs, they open and reveal their commitments. Then, the game host will conclude the round. The mean of all guesses will be computed (on-chain), and the player who has submitted the guess closest to the mean will win the round. The player who wins three rounds first wins the game.

The following is the game flow:

Game Flowchart

  • Alice (the first player) initiates a game and becomes the game host.
  • In this phase, Other players can join the game. In this case, Bob, Charlie, and Dave join.
  • Alice starts the game, and the first game round begins. No more players will be able to join.
  • Players submit their commitment on-chain.
  • Once all players finish submitting their commitments. They open the commitment. After all players open their commitments, the game host concludes the round. The mean of all submissions is computed, and the round winner is determined.
  • If the winner has won three rounds, the game ends. Otherwise, another round begins.

The project is finally built, and you can try it out at:

You can see the demo of a game walkthrough below:

Some Technicalities ⚙️​

  1. The zero-knowledge part kicks in when a player submits a guess on the chain. A 128-bit random value, a.k.a. nullifier, is generated. The guess and nullifier are passed into a wasm zk-circuit with a return value of [Poseidon(guess, nullifier), Poseidon(nullifier)]. The circuit performs a range check that the guess is between 1 and 100.

    We need a nullifier here to expand the preimage domain. We know the guess is a value between 1 and 100. Suppose we store Poseidon(guess) as a commitment. In that case, an attacker/cheater can Poseidon hash all values between 1 to 100 and compare the digest with the one on-chain and be able to figure out what other players' preimages (their guess value) are. So we add a 128-bit nullifier to expand the preimage domain.

  2. This is how the player commitment is stored on-chain.

    Inspecting on-chain storage on commitment

  3. On the front end, upon a round conclusion, only the winning guess is revealed but not the actual mean. This gives the game a "fog of truth" element and will make the game a bit more interesting. But the player openings are actually stored as plain numbers on-chain. So, tech-savvy players can still inspect the smart contract storage to compute the mean. I would love to explore further ZK protocols (multi-party computation, maybe?) that could be used even to hide these openings and be able to compute the mean and the distances between users' guesses and the mean. This will then truly make this game zero-knowledge!

  4. UX matters a lot. The following is my development time allocation for this project.

    • 15% on circuit development, thanks to circomkit library that eases my development workflow.
    • 30% on smart contract development and proof parameter interfacing. The time spent on writing the smart contract logic and comprehensive test cases is about 50-50.
    • 45% is spent on front-end development. The front end involves interacting with various components, e.g., user wallets, loading wasm and generating proofs, transforming proofs to a format appropriate for on-chain submission, etc.

    Many details on the front end must be done right to deliver a great UX. Right now, there is still a lot of room for improvement: e.g., the wallet display on the navbar keeps reloading when navigating within the site, and the page has to be manually refreshed to get the latest game status instead of subscribing to the smart contract events. I truly appreciate front-end engineers who build a great user experience on a Web3 app or web app.

Standing on the Shoulders of Many Giants​

Standing on the Shoulder of Giant

In the past eight weeks I have been truly standing on the shoulders of, not one, but many giants enabling me to deliver this capstone project.

I am grateful PSE Team has selected me for their Core Program and has an excellent curation of study materials. One can find a lot of materials on zero-knowledge cryptography on the internet and be easily overwhelmed by them. The curated study materials, with mentors and tutors always available to answer your questions and teammates holding regular weekly study groups/presentations, definitely helped push me through the study barrier.

Kudo to the Semaphore project team too. Studying the source code of the Semaphore Protocol and its Boilerplate has significantly contributed to this project. In fact, my project is a fork of the Boilerplate template, which is a well-architected demonstration of how a React (Next.js) front-end interfaces with the zk circuit and smart contract. I have also learned a lot of coding and optimization tricks from them.

The project has been made feasible with countless libraries that I used. For example, circom, Circomkit, snark.js, Hardhat, Next.js, Wagmi and Viem, Web3Modal etc, just to name a few. Of course, I also deployed it to the Optimism ecosystem.

Finally, I stand in awe when looking at all the researches that have gone through on pushing the boundary of zero-knowledge protocols and the field of programmable cryptography.

This is just the beginning of my BUIDLing journey, and hopefully I will share more projects with you soon.

Semaphore - part 1

· 3 min read
Jimmy Chu
Jimmy Chu
Site Author

I have been studying about zero-knowledge proof in the past eight weeks. It is hard to grasp how a software project could integrate zero-knowledge proof. Then, through some community chat groups, I came across Privacy & Scaling Explorations group and one of their projects, Semaphore. Semaphore is a very educational project. In this project, I see how ZKP is being applied (in a fashion I understand) and observe excellent software engineering inside.

Semaphore allows users belonging to a certain group to vote without revealing which member they are, aka anonymous voting. There is also a mechanism to prevent users from double-voting, which is done by posting some "residues" generated by the zero-knowledge proof protocol on-chain.

But what is great about the project is that it is very beginner-friendly, and I say this with great respect. The whole project is architected very nicely. It can even be viewed as a model project for how software and packages are structured in modern-day dApps. I have learned a lot from their software structure and encapsulation.

  • The core software project: Semaphore protocol, with a nice structure of:

    • contracts package - the smart contract that verify the proof generated offchain.

    • proof package - the off-chain logics that generate the ZKP with wasm code generated by an arithmetic circuit.

    • circuits package - contains the arithmetic circuit written in circom that generates and verifies proof.

    • hardhat package - a package that allows developers to deploy the core semaphore contract via hardhat without downloading the semaphore project.

  • A template to see how the protocol can be incorporated into other projects. It consists of:

  • The project leverages the Merkle tree structure to verify that a member belongs to a group, with all the tree leaves being the users' identity commitment. The user will generate a Merkle proof to show that he belongs to the group. The core team implements the Merkle tree structure separately as a Lean Incremental Merkle Tree (with a summary note).

  • The project has excellent documentation and website as well, including as two different packages inside the source code.

Studying the project taught me a lot of optimization tricks I can apply in the zk-battleship codebase. I also saw how they used to save on-chain gas costs, particularly using emitted events to store voting results (the user feedback messages) instead of on-chain storage to reduce gas costs further. This is something that never crossed my mind before.

There are two feature enhancements I can help implement on the current Semaphore basis to further my engineering understanding in zk-app development.

  1. Users can later prove they have voted without revealing their voting option, which can become proof of participation for them.

  2. The voting result is hidden during the voting phase until it ends. In this way, the choices made by late voters won't be affected by the given voting result so far.

On Learning zk-SNARK

· 2 min read
Jimmy Chu
Jimmy Chu
Site Author

Recently I am picking up the knowledge necessary to understand what is going on in zk-SNARK. For those who are not familiar with this term, "zk" stands for zero-knowledge, and "SNARK" stands for succinct, non-interactive, argument of knowledge. What this term means is:

  • zero-knowledge: this is a way for a prover proving "something" to a verifier in such a way that the verifer will not gain any additional knowledge than before the interaction. We will elaborate the "something" in the following bullet points.

  • succinct: the proof is going to be short compared to the actual knowledge, and the verifier will be able to perform the verification quite fast. To be more concrete, if the knowledge m has a length of |m|, the proof may probably be O(log |m|) or even shorter.

  • non-interactive: there won't be rounds of back and forth interactions between the prover and verifier. The prover will only send a single message to the verifier.

  • Argument of Knowledge: This is the "something" mentioned in the first bullet point. Notice that this is not the knowledge itself, but a proof that demonstrate that the prover indeed knows the knowledge.

Yes, this is quite an abstract concept. But what is the most puzzling in this learning journey is that though there are tons of useful online resources, such as:

I CANNOT integrate the theoretical aspect together with its engineering aspect in this domain. For example, the high level concept of a zk-SNARK is a combination of one of the functional commitments with one form of interactive oracle proof (IOP). But in implementing a actual zero-knowledge proof project, how do I actually choose a zk-SNARK scheme with a particular functional commitment and a particular interactive oracle proof?

So now, my learning approach is as follows:

  • Studying in-depth about the source code of the Semaphore project.
  • Meanwhile continue reading rareskill zk-book
  • At the same time, I am also applying for bootcamp program to solidify my understanding and hoping to get hands-on experience of putting zkp knowledge into engineering practice.

To be continued.