ZKP tutorial introduction for working programmers.
Do you know why zebras have stripes? One theory is that it is a form of camouflage. When zebras gather together, it makes it more difficult for lions to distinguish their prey. Lions must isolate their prey from the group in order to hunt it[^1].
Humans also like to hide in the crowd. A specific example is when multiple people act as a whole under a collective name. This is how the Federalist Papers were created[^2]. Another example is Bourbaki, a collective pseudonym for a group of French mathematicians in the 1930s. This led to a complete rewriting of much of modern mathematics, with an emphasis on rigor and axiomatic methods[^3].
Bourbaki Congress
In the digital age, let's say you are in a group chat and want to send a controversial message. You want to prove that you are a member of it without revealing which one. How can we do this using cryptography in the digital realm? We can use something called group signatures.
Traditionally, group signatures are mathematically quite complex and difficult to implement. However, using zero-knowledge proofs (ZKPs), this math problem becomes a simple programming task. By the end of this article, you will be able to write a group signature yourself.
Introduction
This post will show you how to write a basic zero-knowledge proof (ZKP) from scratch.
When learning a new technology stack, we want to master the edit-build-run cycle as quickly as possible. Only then can we start learning from our own experience.
We will first have you set up your environment, write a simple program, perform a so-called trusted setup, and then generate and verify proofs as quickly as possible. After that, we will identify some ways to improve our program, implement these improvements, and test them. In the process, we will build a better mental model for programming ZKPs in practice. Finally, you will be familiar (sort of) with writing ZKPs from scratch.
We will step by step build a simple signature scheme where you can prove that you sent a specific message. ="" url="" url="" src="https://mp.weixin.qq.com/s/1.11111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111.1111 18px;"> #Clone the repository and run the preparation script git clone [email protected]:oskarth/zkintro-tutorial.git cd zkintro-tutorial &n bsp; # Browse the contents of this file before executing less ./scripts/prepare.sh ./scripts/prepare.sh
We recommend you browse the contents of ./scripts/prepare.sh to see what this will install, or install manually if you prefer. After execution, you should see Installation complete and no errors.
If you run into problems, check out the latest official documentation here[7]. Once completed, you should have the following versions (or higher) installed:
pragma circom 2.0.0; - Defines the version of Circom used
template Multiplier() - Templates are the equivalent of objects in most programming languages and are a common form of abstraction
signal input a; - Our first input, a; inputs are private by default
signal input b; - Our second input, b; also private by default
signal output b; - Our output, c; outputs are always public
c <== a * b; - This does two things: assigns the signal c to And constrain c to be equal to the product of a and b
component main = Multiplier2() - instantiates our main component
The most important line is c <== a * b;. This is where we actually declare the constraint. This expression is actually a combination of two: <-- (an assignment) and === (an equality constraint). [^7] Constraints in Circom can only use operations involving constants, addition, or multiplication. It enforces that both sides of the equation must be equal. [^8]
About Constraints
How do constraints work? In a context like Sudoku, we might say that a constraint is "a number between 1 and 9". However, in the context of Circom, this is not a single constraint, but something we have to express using a set of simpler equality constraints ( ===). [^9]
Why is this the case? It has to do with the underlying math. Fundamentally, most ZKPs use _arithmetic circuits_, which represent computations on polynomials. When dealing with polynomials, you can easily introduce constants, add them, multiply them, and check if they are equal. [^10] Other operations must be expressed in terms of these basic operations. You don't have to understand this in detail to write a ZKP, but it can be useful to understand what's going on under the hood. [^11]
We can visualize the circuit as follows:
Building our circuit
For your reference, the final file can be found in example1-solution.circom. For more details on the syntax, see the official documentation[9].
We can compile our circuit by running the following command:
This is a simple wrapper around calling circom to create the example1.r1cs and example1.wasm files. You should see something like this:
This specifies the proof in the form of some mathematical objects (three elliptic curve elements) pi_a, pi_b, and pi_c. [^20] It also includes metadata about the protocol (groth16) and the _curve_ used (bn128, a mathematical implementation detail we'll ignore for now). This lets the verifier know how to process this proof in order to verify it correctly.
Notice how short the proof is; no matter how complicated our special program is, it is only this size. This demonstrates the succinctness property of ZKPs that we discussed in the _Friendly Introduction to Zero-Knowledge Proofs_[10]. The above command also outputs our _public outputs_:
This is a list of all the public outputs that correspond to our witness and circuit. In this case, there is one public output corresponding to c: 33. [^21]
What have we proved? We know two secret values a and b, and their product is 33. This demonstrates the privacy property that we discussed in the previous post.
Note that a proof is not useful in isolation; it requires the public outputs that go along with it.
Verifying the Proof
Next, let’s verify this proof. Run:
just verify_proof example1
This requires the verification key, the public output, and the proof. With these, we are able to verify the proof. It should print "Proof verified". Note that the verifier never touched any of the private inputs.
What happens if we change the output? Open example1/target/public.json, change 33 to 34, and run the above command again.
You will notice that the proof is no longer verified. This is because our proof did not prove that we have two numbers whose product is 34.
Congratulations, you have now written your first ZKP program, done a trusted setup, generated a proof, and finally verified it!
Exercise
What are the two key properties of a ZKP and what do they mean?
What is the role of the prover and what input does she need? What about the verifier?
Explain what the line c <== a * b; does.
Why do we need a trusted setup? How do we use the product?
Code: Complete example1 until you have generated and verified a proof.
Second Iteration
With the above circuit, we have proved that we know the product of two (secret) numbers. This is closely related to the prime factorization problem, which is the basis of much of cryptography. [^22] The idea is that if you have a very large number, it is difficult to find two prime numbers whose product equals this large number. In contrast, checking if the product of two numbers is equal to another number is pretty straightforward. [^23]
However, there is a big problem with our circuit. Can you see it?
We can easily change the inputs to "1" and "33". That is, a number c is always the product of 1 and c. That's not very impressive, right?
What we want to do is add another _constraint_ such that a or b cannot be equal to 1. That way, we are forced to do proper integer factorization.
How do we add this constraint, and what changes do we need to make?
Updating our circuit
We will use the example2 folder for these changes. Unfortunately, we can't just write a !== 1, as this is not a valid constraint. [^24]It is not made up of constants, additions, multiplications, and equality checks. How do we express "something is not"?
This is not immediately intuitive, and this type of question is part of the art of writing circuits. Developing this skill takes time and is beyond the scope of this initial tutorial; fortunately, there are many good resources to consult. [^25]
However, there are some common idioms. The basic idea is to use the IsZero() template to check if an expression is equal to zero. It outputs 1 for true values and 0 for false values.
It is often helpful to use a truth table[^26] to show the possible values. Here is the truth table for IsZero():
This is such a useful building block that it is included in Circom's library circomlib. There are many other useful components in circomlib. [^27]
We can include it by creating an npm project (JavaScript) and adding it as a dependency. In the example2 folder, we have already done this for you. To import the relevant modules, we add the following line to the top of example2.circom:
include "circomlib/circuits/comparators.circom";
Using IsZero(), we can check if a or b is equal to 1. Modify the example2.circom file so that it contains the following lines:
just generate_proof example2 just verify_proof example2
It still generates and verifies the proof as expected.
If we change the inputs to example2/input.json to 1 and 33 and try to run the above command, we will see an assertion error. That is, Circom will not even let us generate a proof because the input violates our constraints.
Full Flowchart
Now that we’ve gone through the entire flow twice, let’s take a step back and see how all the pieces fit together.
Hopefully things are starting to make sense. Next, let's step it up a notch and make our circuit more useful.
Exercise
Why do we have to run phase 2 of example2, but not phase 1?
What was the main problem with the previous example, and how did we solve it?
Code: Complete example2 until you can't generate a proof.
Third Iteration
With the above circuit, we have proven that we know the product of two secret values. This alone isn't very useful. What is useful in the real world is a _digital signature scheme_. With it, you can prove to someone else that you wrote a specific message. How do we achieve this using ZKPs? To get to this, we must first cover some basic concepts.
Now is a good time to take a short break and go grab a glass of your favorite beverage.
Digital Signatures
Digital signatures have been around and are ubiquitous in our digital age. The modern internet couldn't function without them. Typically, these are implemented using public key cryptography. In public key cryptography, you have a private key and a public key. The private key is for your use only, while the public key is shared publicly and represents your identity.
A digital signature scheme consists of the following parts:
Key generation: Generates a private key and a corresponding public key
Signing: Creates a signature using a private key and a message
Signature verification: Verifies that a message was signed by the corresponding public key
Although the specific details may look different, the program we wrote and the key generation algorithm described above share a common element: they both use a _one-way function_, more specifically a _trapdoor function_. A trapdoor is something that is easy to fall into but difficult to climb out of (unless you can find a hidden ladder) [^30].
For public key cryptography, it is easy to construct a public key from a private key, but the reverse is very difficult. The same is true of our previous program. If the two secret numbers are very large prime numbers, then it is very difficult to turn that product back into the original value. Modern public key cryptography often uses _elliptic curve cryptography_ under the hood.
Traditionally, creating cryptographic protocols like these digital signature schemes requires a lot of work and requires coming up with a specific protocol involving some clever math. We don't want to do that. Instead, we want to write a program that achieves the same result using ZKP.
Instead of this: [^31]
We just want to write a program that generates the proof we want and then verifies that proof.
Hash Functions and Commitments
Instead of using elliptic curve cryptography, we're going to use two simpler tools: _hash functions_ and _commitments_.
Hash functions are also one-way functions. For example, in the command line, we can use the SHA-256 hash function like this:
You may have some questions at this point. Let’s address some of the questions you may have in your mind.
First, why does this work and why do we need ZKPs? When someone verifies a proof, they only have access to the commitment, the message, and the signature. There is no direct way to verify that the commitment corresponds to a secret without revealing the secret. In this case, we are simply “revealing” the secret when generating the proof, so our secret remains safe.
Second, why use these hash functions and commitments inside ZKPs, instead of public key cryptography? You can absolutely use public key cryptography inside ZKPs, and there are valid reasons to do so. It is much more expensive to implement than the above schemes in terms of constraints. This makes it slower and more complex than the above. As we will see in the next section, the choice of hash function is very important.
Finally, why would we use ZKP when we already have public key cryptography? In this simple example, there is no need to use ZKP. However, it serves as a building block for more interesting applications, such as the group signature example mentioned at the beginning of this article. After all, we want to _program cryptography_.
That was a lot to take in! Fortunately, we are over the hump. Let's start coding. Don't worry if you don't fully understand the above at first. It takes some time to get used to this way of reasoning.
Back to the Code
We will start working from the example3 directory.
To implement digital signatures, the first thing we need to do is generate our keys. These correspond to private and public keys in public key cryptography. Since the secret key corresponds to an identity (you, the prover), we will call them identity_secret and identity_commitment respectively. Together they form an identity pair.
These will be used as inputs to the circuit, along with the message we want to sign. As public outputs we will have the signature, the commitment, and the message. This will allow someone to verify that the signature is indeed correct.
Since we need identity pairs as input to the circuit, we will generate these separately: just generate_identity
This will produce something similar to the following:
include "circomlib/circuits/poseidon.circom";
Poseidon The hash template is used as follows:
component main {public [identity_commitment, message]} = SignMessage();
By default, all inputs to our circuit are private. With this, we explicitly mark identity_commitment and message as public. This means that they will be part of the public output.
With this information, you should have enough knowledge to complete the example3.circom circuit. If you’re still stuck, you can refer to example3-solution.circom for the full code.
Like before, we have to build the circuit and run phase 2 of the trusted setup:
Feel free to change the identity pair to one you generated using just generate_identity. After all, you want to keep your identity a secret to yourself!
You may notice that the message is just a number referenced as a string ("42"). Unfortunately, due to the way constraints work mathematically (using linear algebra and _arithmetic circuits_), we can only use numbers and not strings. The only operations supported inside the circuit are basic arithmetic operations like addition and multiplication. [^37]
We can now generate and verify a proof:
["48968[...]5499", "48269[...]7915", "42"]
These correspond to the signature, commitment, and message, respectively.
Let's see how things can go wrong if we're not careful. [^38]
First, what happens if we change the identity commitment to something random in input.json? You'll notice that we can no longer generate a proof. This is because we're also checking the identity commitment inside the circuit. It's critical to keep the relationship between the identity and the commitment secret.
Second, what happens if we don't include the message in the output? We do get a proof, and it verifies. But the message could be anything, so it doesn't actually prove that you sent a specific message. Similarly, what happens if we don't include the identity commitment in the public output? This means that the identity commitment could be anything, so we don't actually know who signed the message.
As a thought exercise, think about what would happen if we omitted either of these two key constraints:
identity_commitment === identityHasher.out
signature <== signatureHasher.out
Congratulations, now you know how to program crypto! [^39]
Exercise
What are the three components of a digital signature scheme?
What is the purpose of using a "ZK-Friendly hash function" like Poseidon?
What are commitments? How do we use them in a digital signature scheme?
Why do we mark the identity commitment and the message as public?
Why do we need identity commitment and signature constraints?
Code: Complete example3 until you have generated and verified a proof.
Next Steps
With the digital signature scheme above, and some of the tricks we saw in the article, you have all the tools to implement the group signature scheme mentioned at the beginning of the article. [^40]
The skeleton code is in example4. You only need 5-10 lines of code. The only new syntax is the for loop, which works the same way as in most other languages. [^41].
This circuit will allow you to:
Sign a message
Prove that you are one of three people (identity commitment)
without revealing which one
You can think of it as a puzzle. The key insight basically boils down to an arithmetic expression. If you can, try to solve it on paper. If you get stuck, you can look up the solution as before.
Finally, if you want some extra challenge, here are some extensions:
Allow any number of people in the group
Implement a new circuit reveal that proves you signed a specific message
Implement a new circuit deny that proves you did not sign a specific message
Creating such a cryptographic protocol using classical tools would be a huge task, requiring a lot of expertise. [^42] With ZKPs, you can become efficient and dangerous in an afternoon, treating these problems as programming tasks. This is just the tip of the iceberg of what we can do.
Exercises
How do group signatures differ from normal signatures? How can they be used?
Questions
These questions are optional and require more effort.
Find out how IsZero() is implemented.
Code: Complete the group signature scheme above (see example4).
Code: Extend the above group signature example: allow more people and implement reveal and/or deny circuits.
How would you design a "ZK identity" system to prove that you are over 18? What other properties you might want to prove? At a high level, how would you implement it, and what challenges do you see? Study existing solutions to better understand how they are implemented.
For public blockchains like Ethereum, a Layer 2 (L2) is sometimes used to allow for faster, cheaper, and more transactions. At a high level, how would you design an L2 using ZKPs? Explain some of the challenges you see. Study existing solutions to better understand how they are implemented. ## Conclusion
In this tutorial introduction, we got familiar with how to write and modify basic zero-knowledge proofs (ZKPs) from scratch. We set up our programming environment and wrote a basic circuit. We then went through a trusted setup, created, and verified the proof. We identified some issues and improved the circuit, making sure to test our changes. After that, we implemented a basic digital signature scheme using hash functions and commitments.
We also learned enough skills and tools to be able to implement group signatures, which is difficult to achieve without zero-knowledge proofs.
I hope you have a better mental model of what is involved in writing a zero-knowledge proof, and a better understanding of the edit-run-debug cycle in action. This will serve as a good foundation for any other zero-knowledge proof programs you might write in the future, regardless of what technology stack you end up using.
Acknowledgements
Thanks to Hanno Cornelius, Marc Köhlbrugge, Michelle Lai, lenilsonjr, and Chih-Cheng Liang for reading drafts and providing feedback.
Images
Bourbaki Congress 1938 - Unknown, Public Domain, via Wikimedia[11]
Hartmann's Zebras - J. Huber, CC BY-SA 2.0, via Wikimedia[12]
Trapdoor Spider - P.S. Foresman, Public Domain, via [Wikimedia](https://commons.wikimedia.org/wiki/File:Trapdoor_(PSF\ "Wikimedia").png)
Kingsley Lockbox - P.S. Foresman, Public Domain, via Wikimedia[13]
Reference materials
[1] AI translator: https://learnblockchain.cn/people/19584
[16]^2]: See [The Federalist Papers (Wikipedia): https://en.wikipedia.org/wiki/The_Federalist_Papers#Authorship
[17]^3]: See [Bourbaki (Wikipedia): https://en.wikipedia.org/wiki/Nicolas_Bourbaki#Membership
[18]^8]: This makes writing constraints quite challenging, as you can imagine. For more details on constraints in Circom, see [https://docs.circom.io/circom-language/constraint-generation/: https://docs.circom.io/circom-language/constraint-generation/
[19]^12]: A linear constraint means that it can be expressed as a linear combination using only addition. This is equivalent to multiplication by a constant. The main thing to note is that linear constraints are simpler than nonlinear constraints. For more details, see [Constraint Generation: https://docs.circom.io/circom-language/constraint-generation/
[21]^13]: Mathematically speaking, what we have done is to ensure that the equation Az * Bz = Cz holds, where Z=(W,x,1). A, B, and C are matrices, W is the witness (private input), and x is the public input/output. While it is useful to know this, it is not necessary to understand it to write the circuit. See [Rank-1 Constraint System: https://docs.circom.io/background/background/#rank-1-constraint-system
[22]^15]: As mentioned in the Friendly Introduction article, there is a good layman’s podcast of the 2016 Zcash ceremony that you can watch [here: https://radiolab.org/podcast/ceremony
[23]^17]: We call this the 1-out-of-N trust model. There are many other trust models; the one you’re probably most familiar with is majority rule, where you trust the majority to make the right decision. This is essentially how democracy and majority voting work. [↩: #user-content-fnref-17
[24]^22]: Also known as the _cryptographic difficulty hypothesis_. See [Computational Hardness Assumption (Wikipedia): https://en.wikipedia.org/wiki/Computational_hardness_assumption#Common_cryptographic_hardness_assumptions
[25]^23]: For more information, see [https://en.wikipedia.org/wiki/Integer_factorization: https://en.wikipedia.org/wiki/Integer_factorization
[26]^24]: While we can add _asserts_, these are not actually constraints and are only used to sanitize the input. For more information on how this works, see [https://docs.circom.io/circom-language/code-quality/code-assertion/: https://docs.circom.io/circom-language/code-quality/code-assertion/
[28]^25]: This is an excellent resource by 0xPARC if you want to dive into the art of writing (Circom) circuits: [https://learn.0xparc.org/materials/circom/learning-group-1/circom-1/: https://learn.0xparc.org/materials/circom/learning-group-1/circom-1/
[29]^26]: This situation arises frequently due to the nature of writing constraints. See [https://en.wikipedia.org/wiki/Truth_table: https://en.wikipedia.org/wiki/Truth_table
[30]^27]: For more information on circomlib, see [https://github.com/iden3/circomlib: https://github.com/iden3/circomlib
[31]^28]: See [https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom: https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom
[32]^29]: People often share these ptau files between projects for increased security. For more information, see [https://github.com/privacy-scaling-explorations/perpetualpowersoftau: https://github.com/privacy-scaling-explorations/perpetualpowersoftau
[34]^30]: The ladder here represents some kind of value that allows us to proceed in the opposite "difficult" way. Another way to think about it is as a padlock. You can lock it easily, but it's hard to unlock it unless you have the key. Trapdoor functions also have a more formal definition, see [https://en.wikipedia.org/wiki/Trapdoor_function: https://en.wikipedia.org/wiki/Trapdoor_function
[35]^31]: Screenshot from Wikipedia. See [ECDSA (Wikipedia): https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Signature_verification_algorithm
[36]^38]: In real-world digital signature schemes, when multiple messages are exchanged, we may also want to introduce a cryptographic random number. This is to prevent replay attacks, where someone can reuse the same signature at a later time. See [https://en.wikipedia.org/wiki/Replay_attack: https://en.wikipedia.org/wiki/Replay_attack
[37]^40]: The implementation of group signatures in ZKP was inspired by 0xPARC, see [https://0xparc.org/blog/zk-group-sigs: https://0xparc.org/blog/zk-group-sigs
[38]^41]: See [https://docs.circom.io/circom-language/control-flow/: In contrast, papers implementing group signatures such as [https://eprint.iacr.org/2015/043.pdf: https://eprint.iacr.org/2015/043.pdf
[39]^42]: In contrast, papers implementing group signatures such as [https://eprint.iacr.org/2015/043.pdf: https://eprint.iacr.org/2015/043.pdf
Preview
Gain a broader understanding of the crypto industry through informative reports, and engage in in-depth discussions with other like-minded authors and readers. You are welcome to join us in our growing Coinlive community:https://t.me/CoinliveSG
JinseFinance
Beincrypto
Coindesk
Bitcoinist
Cointelegraph