Zero-Knowledge Proofs 101

If you have been keeping up with the trends in the crypto ecosystem you might have noticed that zero-knowledge proofs are being widely used to solve the scalability problem that blockchains tend to struggle with. Big names like Polygon and Loopring have been heavily investing in research as they find this solution might be something to keep an eye on.

Scalability is not even the only issue that zero-knowledge proofs tend to solve for blockchains. As you might know, everything that happens on the blockchain is public for everyone. Other blockchain users can see your balance, your payments, and your contract transactions. Details like that are not something you want to have accessible to the wide public. With zero-knowledge proofs, you can control the privacy of sensitive info.

This sounds all too good to be true. Then you decide to do your own research you stumble upon complex terms like finite fields, arithmetic circuits, and witnesses. You are wondering what did I get into. But keep calm, all these words are not as complex as they might sound. It’s just that math nerds tend to use complex words to scare away ordinary people. FINITE FIELDS, BOOO ????! See, it works. The point of this blog post is to explain what zero-knowledge proofs are without using any complex math terms. Basically, if you are familiar with Reddit culture: it’s an ELI5 post (explain like I’m 5 post).

Zero-Knowledge Proofs

So what are zero-knowledge proofs? A zero-knowledge proof is proving that you have knowledge or ownership of something without revealing any additional details. The easiest way to explain this is to think of a real-life example. Let me tell you a hypothetical story so I can explain ZKP. Let’s say in front of you there’s a safe that you think only you can open. This is not the case tho. Actually, I can also open that safe but you don’t believe my claim. The easiest way to prove that to you is to open it in front of you but I don’t want to show the way I can open it. So we create a small protocol that we both agree on.

I tell you that you can pick 2 objects and put only one of them in the safe. You decide to put an orange or a banana in the safe. So we make the first round.

1. I leave the room so I don’t see if you put the object.
2. You decide you will put the banana in the safe.
3. You leave the room.
4. I open that safe and see that:

When you return I tell you what I found… At first, you are surprised and shocked. But then you get even more suspicious. You think I just got lucky and keep executing the protocol again and again… and again. I keep guessing the object that you put. Finally, you believe me. There’s no way I could have guessed it correctly 10 times in a row. That would be 1/2 to the power 10 percent ~ or in human language – 0.1%.

Now let’s meet some basic terms that the experts in zero-knowledge proofs use. All of these should be easier to understand now.

Provers – The prover in this scenario is me. I had to prove to you that I have some knowledge, in this case – that I can open the safe.

Verifiers – The verifier in this game of ours is yourself. You verified that I indeed opened the case.

Statement – The statement that I proved to you is “I can open this safe.”.

But in order to have zero knowledge proof you and I both agreed to some kind of protocol that we won’t break in order to have valid proof.

The three requirements for a zero-knowledge protocol

• completeness
• soundness
• zero knowledge

I will try to explain these using some more analogies from our previous game.

What’s completeness?

“If the statement is really true and both you and I follow the rules properly, then you would be convinced that my statement is indeed true.”

https://ethereum.org/en/zero-knowledge-proofs/

If the verifier keeps putting objects in that safe again as long as the verifier is truthful they will always tell the prover that their statement is true.

What’s soundness?

If the input is invalid, it is theoretically impossible to fool the zero-knowledge protocol to return ‘true’. Hence, a lying prover cannot trick an honest verifier into believing an invalid statement is valid (except with a tiny margin of probability).

https://ethereum.org/en/zero-knowledge-proofs/

Let’s say the prover and verifier decide to play another round of “Guess the object in the safe”. But this time the prover decides to lie and tells the verifier a false statement. Again, as long as the verifier is truthful, they can quickly tell the prover that their statement is false.

What’s zero knowledge?

The verifier learns nothing about a statement beyond its validity or falsity (they have “zero knowledge” of the statement). This requirement also prevents the verifier from deriving the original input (the statement’s contents) from the proof.

https://ethereum.org/en/zero-knowledge-proofs/

Every time the prover and verifier engage in the protocol the prover should not give any additional information that’s gonna reveal anything else other than “I indeed can open this safe”.

Types of Zero Knowledge Proofs

There are two types of ZKPs that are currently being used by developers:

• Interactive Zero Knowledge Proof

These proofs require a Challenge-Response protocol. This means that the verifier needs to keep issuing challenges (think of it like asking the prover questions) so that the verifier can ensure that the prover didn’t simply get lucky with his answer to the question. Of course, these challenges adhere to the ZKP protocol properties that we’ve previously covered. They should not reveal any additional information and should possess soundness and completeness.

This zero-knowledge proof is interactive because the verifier keeps asking the prover questions. These questions are also called challenges. And the response is … well, our response to the challenges. This example should provide a good illustration of interactive zero-knowledge proofs. Now, let’s move on to the next type.

• Non-Interactive Zero Knowledge Proof

Interactive ZKPs have their disadvantage like the need for multiple rounds where the verifier continues to present challenges and they can’t scale due to the same reason. So thanks to recent advancements in ZKPs, a new type of ZKP called – Non-Interactive Zero Knowledge Proof (commonly called NI-ZKP) has emerged. With these types of proofs, there is no need for multiple types of interactions between the verifier and prover, hence the name Non-Interactive. You can also prove your knowledge to multiple parties without the need for the same exchanges of challenges and responses.

However, it’s not all smooth sailing. In order for NI-ZKPs to work they need a trusted setup and also have increased complexity. They need specialized knowledge and careful attention to ensure the security of ZKPs. Thankfully the increased complexity of Non-Interactive ZKPs has recently been abstracted, making it less complicated.

So how do you pick what kind of proof do you use? The choice between Non-Interactive ZKPs and Interactive ZKPs depends on the specific requirements and constraints of the application or use case. Due to their efficiency, scalability, privacy and available compatibility with smart-contracts, it has been commonly accepted to use non-interactive types of proofs in the crypto world.

zkSNARK

Alright, it’s time to level up as things are about to get slightly more complicated. Let’s dive deep into this complicated matter. I promise I will make it understandable for you.

zkSNARK is the most popular type of non-interactive proof. The zk in zkSNARK stands for… yeah, you guessed right – zero knowledge. And SNARK stands for:

Succinct

Non-interactive

Argument of

Knowledge.

Most of the acronym words are self-explanatory. The only one that probably needs some explaining is “Succint”. Due to sophisticated mathematical computations, the generated proofs are small and compact. Here’s an example of what a zkSNARK proof looks like:

{
 "pi_a": [
  "5858158181707459640841125710146513947725877509687555760098485666341474760522",
  "4889399530896063964235764965486462397103407363022428231550894996415779301548",
  "1"
 ],
 "pi_b": [
  [
   "20314454273152028585822429384657351636711478476575331263518189980735732770257",
   "17138524009845114738063988700429713524279722948743184396014413475266222444894"
  ],
  [
   "8643544986865743686274520979278831327188345591265326733105028010085243627284",
   "18060697313329349004876778152941056812780763073935003257832809724794057140561"
  ],
  [
   "1",
   "0"
  ]
 ],
 "pi_c": [
  "17311751841243789630014262247786775288258452744358110844385569525939688972838",
  "20991165655617937280301256598953028609941390691876249521424629640971949352593",
  "1"
 ],
 "protocol": "groth16",
 "curve": "bn128"
}

“????‍♂️ Woah, woah. Calm down, OP. You posted some mumbo-jumbo. Please, explain what that means”

You, right now – circa 2023

Well, here’s the best part about zkSNARKs. the complexities, such as the underlying mathematics, have been abstracted away, so you don’t have to worry about them.

But for the curious ones let’s explain what this file contains. This kind of file is called a JSON. JSON uses curly braces {} to define objects. An object is a collection of key-value pairs. The key is a string enclosed in double quotes, followed by a colon :, and then the value. Multiple key-value pairs are separated by commas. This specific file has 5 keys and 5 values. The keys are pi_a, pi_b, pi_c, protocol and curve.

In real life Zero-Knowledge Proofs can be used to prove different statements using math or if we want to be even more precise – arithmetic circuits. Arithmetic circuits can have inputs and outputs.

pi_a which stands for “Proof Input A” is an array of elements that represents the input values These inputs are typically encoded using a specific format defined by the zkSNARK protocol (groth16) in our case.

pi_b is an encoded array of elements that represent the computation of the proof.

And lastly pi_c – this is an array of elements that represent the encoded output of the proof.

The 4th key-value pair is the protocol that we’ve used. This proof uses Groth16 which is a non-interactive zero-knowledge proof system. It’s mostly known for its succinct proof size and for its fast verification speed which are the core requirements for zero-knowledge proofs.

The last key-pair value is the elliptic curve used. Our zero-knowledge proof uses the BN128 which is used for its high security and its efficiency.

The important thing you should know is that behind all these code lines there is proof that you know my two favorite numbers hidden without you actually saying them. For more complicated explanatory you might need the “Zero Knowledge Proof 201” class.

Okay, this is the proof, but who is the verifier?” Who checks if you have indeed provided your two favorite numbers? This is where we introduce our verifier. In our case, there is a contract that performs this task. Curious about what it looks like? Here’s a glimpse:

//
// Copyright 2017 Christian Reitwiessner
// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
// 2019 OKIMS
//      ported to solidity 0.6
//      fixed linter warnings
//      added requiere error messages
//
//
// SPDX-License-Identifier: GPL-3.0
pragma solidity ^0.8.10;
library Pairing {
    struct G1Point {
        uint X;
        uint Y;
    }
    // Encoding of field elements is: X[0] * z + X[1]
    struct G2Point {
        uint[2] X;
        uint[2] Y;
    }
    /// @return the generator of G1
    function P1() internal pure returns (G1Point memory) {
        return G1Point(1, 2);
    }
    /// @return the generator of G2
    function P2() internal pure returns (G2Point memory) {
        // Original code point
        return G2Point(
            [11559732032986387107991004021392285783925812861821192530917403151452391805634,
             10857046999023057135944570762232829481370756359578518086990519993285655852781],
            [4082367875863433681332203403145435568316851327593401208105741076214120093531,
             8495653923123431417604973247489272438418190587263600148770280649306958101930]
        );

/*
        // Changed by Jordi point
        return G2Point(
            [10857046999023057135944570762232829481370756359578518086990519993285655852781,
             11559732032986387107991004021392285783925812861821192530917403151452391805634],
            [8495653923123431417604973247489272438418190587263600148770280649306958101930,
             4082367875863433681332203403145435568316851327593401208105741076214120093531]
        );
*/
    }
    /// @return r the negation of p, i.e. p.addition(p.negate()) should be zero.
    function negate(G1Point memory p) internal pure returns (G1Point memory r) {
        // The prime q in the base field F_q for G1
        uint q = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
        if (p.X == 0 && p.Y == 0)
            return G1Point(0, 0);
        return G1Point(p.X, q - (p.Y % q));
    }
    /// @return r the sum of two points of G1
    function addition(G1Point memory p1, G1Point memory p2) internal view returns (G1Point memory r) {
        uint[4] memory input;
        input[0] = p1.X;
        input[1] = p1.Y;
        input[2] = p2.X;
        input[3] = p2.Y;
        bool success;
        // solium-disable-next-line security/no-inline-assembly
        assembly {
            success := staticcall(sub(gas(), 2000), 6, input, 0xc0, r, 0x60)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require(success,"pairing-add-failed");
    }
    /// @return r the product of a point on G1 and a scalar, i.e.
    /// p == p.scalar_mul(1) and p.addition(p) == p.scalar_mul(2) for all points p.
    function scalar_mul(G1Point memory p, uint s) internal view returns (G1Point memory r) {
        uint[3] memory input;
        input[0] = p.X;
        input[1] = p.Y;
        input[2] = s;
        bool success;
        // solium-disable-next-line security/no-inline-assembly
        assembly {
            success := staticcall(sub(gas(), 2000), 7, input, 0x80, r, 0x60)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require (success,"pairing-mul-failed");
    }
    /// @return the result of computing the pairing check
    /// e(p1[0], p2[0]) *  .... * e(p1[n], p2[n]) == 1
    /// For example pairing([P1(), P1().negate()], [P2(), P2()]) should
    /// return true.
    function pairing(G1Point[] memory p1, G2Point[] memory p2) internal view returns (bool) {
        require(p1.length == p2.length,"pairing-lengths-failed");
        uint elements = p1.length;
        uint inputSize = elements * 6;
        uint[] memory input = new uint[](inputSize);
        for (uint i = 0; i < elements; i++)
        {
            input[i * 6 + 0] = p1[i].X;
            input[i * 6 + 1] = p1[i].Y;
            input[i * 6 + 2] = p2[i].X[0];
            input[i * 6 + 3] = p2[i].X[1];
            input[i * 6 + 4] = p2[i].Y[0];
            input[i * 6 + 5] = p2[i].Y[1];
        }
        uint[1] memory out;
        bool success;
        // solium-disable-next-line security/no-inline-assembly
        assembly {
            success := staticcall(sub(gas(), 2000), 8, add(input, 0x20), mul(inputSize, 0x20), out, 0x20)
            // Use "invalid" to make gas estimation work
            switch success case 0 { invalid() }
        }
        require(success,"pairing-opcode-failed");
        return out[0] != 0;
    }
    /// Convenience method for a pairing check for two pairs.
    function pairingProd2(G1Point memory a1, G2Point memory a2, G1Point memory b1, G2Point memory b2) internal view returns (bool) {
        G1Point[] memory p1 = new G1Point[](2);
        G2Point[] memory p2 = new G2Point[](2);
        p1[0] = a1;
        p1[1] = b1;
        p2[0] = a2;
        p2[1] = b2;
        return pairing(p1, p2);
    }
    /// Convenience method for a pairing check for three pairs.
    function pairingProd3(
            G1Point memory a1, G2Point memory a2,
            G1Point memory b1, G2Point memory b2,
            G1Point memory c1, G2Point memory c2
    ) internal view returns (bool) {
        G1Point[] memory p1 = new G1Point[](3);
        G2Point[] memory p2 = new G2Point[](3);
        p1[0] = a1;
        p1[1] = b1;
        p1[2] = c1;
        p2[0] = a2;
        p2[1] = b2;
        p2[2] = c2;
        return pairing(p1, p2);
    }
    /// Convenience method for a pairing check for four pairs.
    function pairingProd4(
            G1Point memory a1, G2Point memory a2,
            G1Point memory b1, G2Point memory b2,
            G1Point memory c1, G2Point memory c2,
            G1Point memory d1, G2Point memory d2
    ) internal view returns (bool) {
        G1Point[] memory p1 = new G1Point[](4);
        G2Point[] memory p2 = new G2Point[](4);
        p1[0] = a1;
        p1[1] = b1;
        p1[2] = c1;
        p1[3] = d1;
        p2[0] = a2;
        p2[1] = b2;
        p2[2] = c2;
        p2[3] = d2;
        return pairing(p1, p2);
    }
}
contract Verifier {
    using Pairing for *;
    struct VerifyingKey {
        Pairing.G1Point alfa1;
        Pairing.G2Point beta2;
        Pairing.G2Point gamma2;
        Pairing.G2Point delta2;
        Pairing.G1Point[] IC;
    }
    struct Proof {
        Pairing.G1Point A;
        Pairing.G2Point B;
        Pairing.G1Point C;
    }
    function verifyingKey() internal pure returns (VerifyingKey memory vk) {
        vk.alfa1 = Pairing.G1Point(
            9999516263328768367197110527672383766447270883615574746621117268545763327099,
            7049650421369123110317742474934121221402302194678163497531773109723580126301
        );

        vk.beta2 = Pairing.G2Point(
            [7409385866943097044132768504282029191736069720103705182384012535626563199525,
             1403420408494617326268255987768127220648464374410092405851665856726666160160],
            [14540955040930579245823182183502353468515056291737548985666539614600588268574,
             13205959281410125626710611095865131490888958387998637752358550317918785844131]
        );
        vk.gamma2 = Pairing.G2Point(
            [11559732032986387107991004021392285783925812861821192530917403151452391805634,
             10857046999023057135944570762232829481370756359578518086990519993285655852781],
            [4082367875863433681332203403145435568316851327593401208105741076214120093531,
             8495653923123431417604973247489272438418190587263600148770280649306958101930]
        );
        vk.delta2 = Pairing.G2Point(
            [14100386100905191284068474763764095008110198030066839107836983616243993661483,
             2122275581737299094680478049936857060784245728664623008792056442116730552126],
            [15770530112045100812469152749705383309406592691879412524730729245135675011708,
             17682797418669056390375596361299126493754481695863715518427669768825193625495]
        );
        vk.IC = new Pairing.G1Point[](2);
        
        vk.IC[0] = Pairing.G1Point( 
            14371197861038493077485942976290214193746313819746142230153082549331701593558,
            17527501504908826544377433076016336773981448462427785297902880254901952580374
        );                                      
        
        vk.IC[1] = Pairing.G1Point( 
            17993497415762909312115150384761453112126301520134395636641701088430587232555,
            1525794497600362527981342825612707116842201633513363044894817361272007058227
        );                                      
        
    }
    function verify(uint[] memory input, Proof memory proof) internal view returns (uint) {
        uint256 snark_scalar_field = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
        VerifyingKey memory vk = verifyingKey();
        require(input.length + 1 == vk.IC.length,"verifier-bad-input");
        // Compute the linear combination vk_x
        Pairing.G1Point memory vk_x = Pairing.G1Point(0, 0);
        for (uint i = 0; i < input.length; i++) {
            require(input[i] < snark_scalar_field,"verifier-gte-snark-scalar-field");
            vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.IC[i + 1], input[i]));
        }
        vk_x = Pairing.addition(vk_x, vk.IC[0]);
        if (!Pairing.pairingProd4(
            Pairing.negate(proof.A), proof.B,
            vk.alfa1, vk.beta2,
            vk_x, vk.gamma2,
            proof.C, vk.delta2
        )) return 1;
        return 0;
    }
    /// @return r  bool true if proof is valid
    function verifyProof(
            uint[2] memory a,
            uint[2][2] memory b,
            uint[2] memory c,
            uint[1] memory input
        ) public view returns (bool r) {
        Proof memory proof;
        proof.A = Pairing.G1Point(a[0], a[1]);
        proof.B = Pairing.G2Point([b[0][0], b[0][1]], [b[1][0], b[1][1]]);
        proof.C = Pairing.G1Point(c[0], c[1]);
        uint[] memory inputValues = new uint[](input.length);
        for(uint i = 0; i < input.length; i++){
            inputValues[i] = input[i];
        }
        if (verify(inputValues, proof) == 0) {
            return true;
        } else {
            return false;
        }
    }
}

In reality, for the generation of this contract is automatically done once you explain what exactly you are verifying with the help of a compiler in this case – circom.

What this contract does is let you pass the proof(Remember the first line of codes that I sent?) to a function called verifyProof(a,b,c,input) and this contract will tell you if your proof is valid or not.

Conclusion

Zero-Knowledge Proof systems are something worth keeping an eye on as they have the potential to shape the future for privacy and scalability of blockchain networks such as Ethereum. If you are interested in this topic and eager to learn more I would highly recommend you check out this list of helpful resources:

• Circom library
• Ethereum’s blog post about ZKPs
• Vitalik Buterin’s blog post about zkSNARK
• Two Number Product ZK proof example – GitHub repository

In this list, you’ll also find a recently created repository by our team at Hack. It provides a comprehensive explanation of the entire process of proof generation, including the creation of the verifier contract, generation of witness (think of this like a file where your information is concealed before you generate the proof), deployment of all contracts and how you could use them.