C 523: zk-SNARKs (20 pts extra)

What you need:

Purpose

To run a very basic example of a zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge): a system by which a prover proves that they know a secret to a verifier, without revealing the secret to the verifier.

This would prevent attacks like the one Mark Zuckerberg used to steal journalists' passwords in 2010.

Instead of sending a secret to the verifier, the prover sends a "proof.json" file containing a blob of hexadecimal data.

The verifier performs calculations on that data using only public information and a smart contract, and the only output is true or false. The verifier discovers whether the claim is true, but does not learn any secrets.

See these articles for more explanations:

Install Node

On your Linux machine, in a Terminal window, execute these commands: 
sudo apt update
sudo apt install nodejs npm -y
node --version
Make sure you have a version number of 10.12.0 or higher, as shown below.

Installing Rust

On your Linux machine, in a Terminal window, execute these commands: 
sudo apt install curl -y
sudo apt install cmake build-essential -y
curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh
When you are prompted to, enter 1 to proceed.

Installing Circom

One of the main tools for making ZK-SNARKs is "circom", the Circuit Compiler.

On your Linux machine, in a Terminal window, execute these commands: 

git clone https://github.com/iden3/circom.git
cd circom
source $HOME/.cargo/env
cargo build --release
The code will take a few minutes to compile.

On your Linux machine, in a Terminal window, execute these commands: 

cargo install --path circom
circom --help
You see the Circom help message, as shown below.

Installing Snarkjs

On your Linux machine, in a Terminal window, execute this command: 
sudo npm install -g snarkjs
The package installs, as shown below.

Configure Powers of Tau

"Powers of Tau" is a multi-party computation (MPC) ceremony.

To prepare it, execute these commands: 

cd
mkdir snark
cd snark
snarkjs powersoftau new bn128 12 pot12_0000.ptau -v

snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v
Enter some random text when you are prompted to.

You see a lot of random hash values, as shown below.

Execute these commands, replacing "some random text" with something random. 

snarkjs powersoftau contribute pot12_0001.ptau pot12_0002.ptau --name="Second contribution" -v -e="some random text"

snarkjs powersoftau verify pot12_0002.ptau
You see a lot of random hash values, ending with a "Powers of Tau Ok!" message, as shown below.

Execute these commands: 

snarkjs powersoftau beacon pot12_0002.ptau pot12_beacon.ptau 0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f 10 -n="Final Beacon"

snarkjs powersoftau prepare phase2 pot12_beacon.ptau pot12_final.ptau -v
It takes a few minutes to do the calculations.

When it's done, execute this command to verify it: 

snarkjs powersoftau verify pot12_final.ptau
At the end, you see a "Powers of Tau Ok!" message, as shown below.

Building a Circuit

Our prover will prove knowledge of two private keys, a and b, which are multiplied to produce number c, as shown below.

On your Linux machine, in a Terminal window, execute these commands: 

nano circuit.circom
Paste in this code, as shown below. 
pragma circom 2.0.0;

template Multiplier(n) {
    signal input a;
    signal input b;
    signal output c;

    signal int[n];

    int[0] <== a*a + b;
    for (var i=1; i<n; i++) {
    int[i] <== int[i-1]*int[i-1] + b;
    }

    c <== int[n-1];
}

component main = Multiplier(1000);

Save the file with Ctrl+X, Y, Enter.

Compile the Circuit

On your Linux machine, in a Terminal window, execute this command: 
circom circuit.circom --r1cs --wasm --sym
It writes three files, as shown below.

View Information About the Circuit

On your Linux machine, in a Terminal window, execute this command: 
snarkjs info -r circuit.r1cs
You see a description of the circuit, with two private inputs, one output, and 1000 constraints, as shown below.

To see the constraints of the circuit, execute this command: 

snarkjs r1cs print -r circuit.r1cs -s circuit.sym
A thousand lines scroll by, ending with 998, as shown below.

Calculating a Witness

First we need to export the r1cs file to human-readable json.

Execute these commands: 

snarkjs r1cs export json circuit.r1cs circuit.r1cs.json
head circuit.r1cs.json
You see the start of the file, with "nConstraints" equal to 1000, as shown below.

C 523.1: nLabels (10 pts)

The flag is covered by a green rectangle in the image below.

Next we specify the inputs. We'll use a=3 and b-11.

Execute this command: 

nano input.json
Paste in this code, as shown below. 
{"a": 3, "b": 11}
Save the file with Ctrl+X, Y, Enter.

To create the witness, execute these commands: 

cd circuit_js
node generate_witness.js circuit.wasm ../input.json ../witness.wtns
ls
ls ..
You see the file witness.wtns as shown below.

Setting Up a PLONK Proving System

Execute these commands: 
cd ..
snarkjs plonk setup circuit.r1cs pot12_final.ptau circuit_final.zkey
ls
You see a circuit_final.zkey file, as shown below.

Export the zkey

Execute these commands: 
snarkjs zkey export verificationkey circuit_final.zkey verification_key.json
head verification_key.json
You see the start of a key, using a "protocol" of "plonk", as shown below.

Create the Proof

Execute these commands: 
snarkjs plonk prove circuit_final.zkey witness.wtns proof.json public.json
head proof.json
head public.json
You see values for a and b, as shown below.

Verify the Proof

Execute this command: 
snarkjs plonk verify verification_key.json public.json proof.json
You see the "OK!" message, as shown below.

Exporting the Proof to a Smart Contract

Execute these commands: 
snarkjs zkey export solidityverifier circuit_final.zkey verifier.sol
head verifier.sol
You see start of the Solidity contract, as shown below.

Execute this command: 

nano verifier.sol
Adjust the font to be very small, so you can see a lot of code at once, as shown below.

Opening the Remix IDE

In Chrome, go to
https://remix.ethereum.org/
In the left pane, right-click contracts and click "New File", as shown below.

Type the name PlonkVerifier.sol and press Enter.

A "PlonkVerifier.sol" tab appears on the right side.

Carefully copy the code from nano and paste it in. It will take several cycles of copying and pasting.

There are more than 600 lines of code, as shown below.

Compiling the Contract

On the left side, click the third icon, outlined in green in the image above. The "SOLIDITY COMPILER" appears. At the bottom, click the blue "PlonkVerifier Coin.sol" button.

On the left side, the third icon now has a green check-mark on it, as shown below.

Using the JavaScript VM

On the left side, click the fourth icon from the top, outlined in red in the image above.

The "DEPLOY & RUN TRANSACTIONS" pane opens.

Use the default Environment of "JavaScript VM (London)".

Deploying your Contract

Click the orange Deploy button.

On the lower left, in the Deployed Contracts section, you see "PLONKVERIFIER". Click the > sign next to "PlonkVerifier" to expand that section.

You see a blue verifyProof button, as shown below.

Simulate a Verification Call

In your Linux terminal, if nano is still open, type Ctrl+X to exit it.

Restore the font to a normal size.

Execute this command: 

snarkjs zkey export soliditycalldata public.json proof.json
You see a blob of hexadecimal code. Highlight and copy it to the Clipboard, as shown below.

C 523.2: Result (10 pts)

Paste the blob of hexadecimal code into the field next to the verifyProof button and click verifyProof button.

The result is true -- the verification succeeds!

The flag is covered by a green rectangle in the lower left, in the image below.

Changing the Proof

In the field next to the verifyProof button, scroll to the right end.

Change the last character.

Click the verifyProof button.

The result changes to false.

References

Create your first zero-knowledge snark circuit using circom and snarkjs
iden3 / snarkjs
Zero-Knowledge Proofs

Posted 11-14-21
Meaning of zk-SNARK added 11-16-21