Circom Ed25519

Curve operations and signature verification for Ed25519 digital signature scheme in circom

WARNING: This is a research project. It has not been audited and may contain bugs and security flaws. This implementation is NOT ready for production use.

The circuits follow the reference implementation from IETF RFC8032

1. Installing dependencies

• npm install -g snarkjs
• Install Rust: curl --proto '=https' --tlsv1.2 https://sh.rustup.rs -sSf | sh
• Clone and install circom - circom docs
• If you want to build the verify circuit, you'll need to download a Powers of Tau file with 2^22 constraints and copy it into the circuits subdirectory of the project, with the name pot22_final.ptau. You can download Powers of Tau files from the Hermez trusted setup from this repository

2. Run the project

2.1. Clone code and install dependencies

git clone this-project-code

cd /path/to/this/project/folder/

Run command to install package dependencies

npm install

2.2. Compile circuits

Enter the circuits directory, we can compile the circuit with the following command:

circom verify.circom --r1cs --wasm --sym --c

With these options we generate three types of files:

• --r1cs: it generates the file verify.r1cs that contains the R1CS constraint system of the circuit in binary format.
• --wasm: it generates the directory verify_js that contains the Wasm code (verify.wasm) and other files needed to generate the witness.
• --sym : it generates the file verify.sym , a symbols file required for debugging or for printing the constraint system in an annotated mode.
• --c : it generates the directory verify_cpp that contains several files (verify.cpp, verify.dat, and other common files for every compiled program like main.cpp, MakeFile, etc) needed to compile the C code to generate the witness.

Notice: If you encounter JavaScript Heap Out of Memory Error during operation, please refer to the documentation to solve it.

2.3. Computing the witness

Enter in the directory verify_js, add the input in a file input.json (Simply copy the input.json in the root directory of the project) and execute:

node generate_witness.js verify.wasm input.json witness.wtns

2.4. Proving circuits

2.4.1. Powers of Tau

First, re-enter the circuits directory, we start a new "powers of tau" ceremony:

snarkjs powersoftau new bn128 23 pot23_0000.ptau -v

Then, we contribute to the ceremony:

snarkjs powersoftau contribute pot23_0000.ptau pot23_0001.ptau --name="First contribution" -v

Now, we have the contributions to the powers of tau in the file pot23_0001.ptau and we can proceed with the Phase 2.

2.4.2. Phase 2

The phase 2 is circuit-specific. Execute the following command to start the generation of this phase:

snarkjs powersoftau prepare phase2 pot23_0001.ptau pot23_final.ptau -v

Next, we generate a .zkey file that will contain the proving and verification keys together with all phase 2 contributions. Execute the following command to start a new zkey:

snarkjs groth16 setup verify.r1cs pot23_final.ptau verify_0000.zkey

Contribute to the phase 2 of the ceremony:

snarkjs zkey contribute verify_0000.zkey verify_0001.zkey --name="1st Contributor Name" -v

Export the verification key:

snarkjs zkey export verificationkey verify_0001.zkey verification_key.json

2.4.3. Generating a Proof

Once the witness is computed and the trusted setup is already executed, we can generate a zk-proof associated to the circuit and the witness:

use snarkjs:
snarkjs groth16 prove verify_0001.zkey ./verify_js/witness.wtns proof.json public.json

This command generates a Groth16 proof and outputs two files:

• proof.json: it contains the proof.
• public.json: it contains the values of the public inputs and outputs.

This step can use rapidsnark to speed up the generation of zkSnark proofs, please refer to the documentation of rapidsnark.

So you can replace snarkjs command by this one:

./build/prover <verify_0001.zkey> <witness.wtns> <proof.json> <public.json>

2.4.4. Verifying a Proof

To verify the proof, execute the following command:

snarkjs groth16 verify verification_key.json public.json proof.json

The command uses the files verification_key.json we exported earlier,proof.json and public.json to check if the proof is valid. If the proof is valid, the command outputs an OK.

A valid proof not only proves that we know a set of signals that satisfy the circuit, but also that the public inputs and outputs that we use match the ones described in the public.json file.

2.4.5. Verifying from a Smart Contract

It is also possible to generate a Solidity verifier that allows verifying proofs on Ethereum blockchain.

First, we need to generate the Solidity code using the command:

snarkjs zkey export solidityverifier verify_0001.zkey verifier.sol

This command takes validation key verify_0001.zkey and outputs Solidity code in a file named verifier.sol. You can take the code from this file and cut and paste it in Remix. You will see that the code contains two contracts: Pairing and Verifier. You only need to deploy the Verifier contract.

The Verifier has a view function called verifyProof that returns TRUE if and only if the proof and the inputs are valid. To facilitate the call, you can use snarkJS to generate the parameters of the call by typing:

snarkjs generatecall

You can get something like the following in return:

["0x0ec85fd1ea811b909863cf37b8a1a6b56a31860ef86521be290b1d94798bd959", "0x0020ab9504c61e7f727107ec26a9cef4377ffa1538e4a32471b2b2e487c081c3"],[["0x1e5098bad0f155d03b2541e5a667e363470df87f566e816669c56528efbb6f96", "0x07ea1d74db9d31ebf14ebaed5de0acbd1fc4e3d1fe37b2b7fe4b368c1eba07d7"],["0x0dadfd2cab5dd3b1d98effd276ec72fcae58e78b8d3c430b4e6db11630ef7e3b", "0x252f441aae698b08ace1a9f279a7b0098f533a28ce648511c6fe6c6bb846fe26"]],["0x2bcc945073c6a6d4195aa9408b5a2f03fd369c4d0afa19573032fc217d2449c3", "0x02dd8a748ec77bb39754bc23a589ed3458167d9ae51735d3f8d40502ed46ab20"],["0x0000000000000000000000000000000000000000000000000000000000000001"]

Cut and paste the output of the command to the parameters field of the verifyProof method in Remix. If everything works fine, this method should return TRUE. You can try to change just a single bit of the parameters, and you will see that the result is verifiable FALSE.

Appendix

1. Inputs

msg is the data for the signature

R8 is the first 256 bits of the signature (LSB to MSB)

S is the first 255 bits of the last 256 bits of the signature (LSB to MSB)

A is the public key in binary (LSB to MSB)

PointA is the point representing the public key on the elliptic curve (encoded in base 2^85 for brevity)

PointR is the point representing the R8 value on the elliptic curve (encoded in base 2^85)

The algorithm we follow only takes in A and R8 in binary form, and is decompressed to get PointA and PointR respectively. However, decompression is an expensive algorithm to perform in a circuit. On the other hand, compression is cheap and easy to implement. So, we use a nifty little trick to push the onus of providing both on the prover and perform equality checks after compressing the points within the circuit. Ref

You can find all helper functions to change encodings from well-known formats to circuit friendly formats here