Circom SHA256
Introduction
After studying the circom getting-started, I felt like it wouldn’t be a big challenge to come up with a simple circuit myself.
My idea was to prove that you know someone’s birthday without revealing the date in a DD::MM::YY format.
I immediately wrote a simple circuit and thought I was done after just a few minutes:
pragma circom 2.0.0;
template Birthday () {
// Declaration of signals.
signal input d;
signal input m;
signal input y;
// c will be written to public.json
signal output a;
signal output b;
signal output c;
// Constraints.
// two outputs so d and m are not interchangeable
a <== d * y;
b <== m * y;
c <== d * m;
}
component main = Birthday();However I came to realise that it’s quite simple to derive values d, m and y from the public parameters a, b and c. To find d, m and y one would only have to solve for the unique values a, b and c by setting up simultaneous equations:
a = d*y
b = m*y
c = d*m
=> m = sqrt((bc)/a)
...Therefore every observer could easily derive d, m and y (which are supposed to be secrets shared between only the prover and the verifier).
This issue can be resolved by including a one-way (hash) function, that’ll make it extremely computationally expensive to find d, m and y.
To achieve this, we have to add some complexity to the circuit:
hash = h(x)where the function h(x) is a one-way hash function, like, for example, SHA256. Now the value h(x) will be public, but it won’t be possible to derive x knowing just h(x).
Circom standard library
Iden3’s circom provides a standard library that includes an implementation of the SHA256 hash function in circom language:
pragma circom 2.0.0;
include "constants.circom";
include "sha256compression.circom";
template Sha256(nBits) {
signal input in[nBits];
signal output out[256];
var i;
var k;
var nBlocks;
var bitsLastBlock;
nBlocks = ((nBits + 64)\512)+1;
signal paddedIn[nBlocks*512];
for (k=0; k<nBits; k++) {
paddedIn[k] <== in[k];
}
paddedIn[nBits] <== 1;
for (k=nBits+1; k<nBlocks*512-64; k++) {
paddedIn[k] <== 0;
}
for (k = 0; k< 64; k++) {
paddedIn[nBlocks*512 - k -1] <== (nBits >> k)&1;
}
component ha0 = H(0);
component hb0 = H(1);
component hc0 = H(2);
component hd0 = H(3);
component he0 = H(4);
component hf0 = H(5);
component hg0 = H(6);
component hh0 = H(7);
component sha256compression[nBlocks];
for (i=0; i<nBlocks; i++) {
sha256compression[i] = Sha256compression() ;
if (i==0) {
for (k=0; k<32; k++ ) {
sha256compression[i].hin[0*32+k] <== ha0.out[k];
sha256compression[i].hin[1*32+k] <== hb0.out[k];
sha256compression[i].hin[2*32+k] <== hc0.out[k];
sha256compression[i].hin[3*32+k] <== hd0.out[k];
sha256compression[i].hin[4*32+k] <== he0.out[k];
sha256compression[i].hin[5*32+k] <== hf0.out[k];
sha256compression[i].hin[6*32+k] <== hg0.out[k];
sha256compression[i].hin[7*32+k] <== hh0.out[k];
}
} else {
for (k=0; k<32; k++ ) {
sha256compression[i].hin[32*0+k] <== sha256compression[i-1].out[32*0+31-k];
sha256compression[i].hin[32*1+k] <== sha256compression[i-1].out[32*1+31-k];
sha256compression[i].hin[32*2+k] <== sha256compression[i-1].out[32*2+31-k];
sha256compression[i].hin[32*3+k] <== sha256compression[i-1].out[32*3+31-k];
sha256compression[i].hin[32*4+k] <== sha256compression[i-1].out[32*4+31-k];
sha256compression[i].hin[32*5+k] <== sha256compression[i-1].out[32*5+31-k];
sha256compression[i].hin[32*6+k] <== sha256compression[i-1].out[32*6+31-k];
sha256compression[i].hin[32*7+k] <== sha256compression[i-1].out[32*7+31-k];
}
}
for (k=0; k<512; k++) {
sha256compression[i].inp[k] <== paddedIn[i*512+k];
}
}
for (k=0; k<256; k++) {
out[k] <== sha256compression[nBlocks-1].out[k];
}
}as you can see, circom SHA256 performs mathematical operations on a bit-array meaning input, as well as output size need to be specified.
Proving a SHA256 hash
Let’s try to write a circuit that proves that we know some integer array ‘date’, with hash SHA256(date):
pragma circom 2.0.0;
include "./circomlib/circuits/sha256/sha256.circom";
template Birthday(){
component SHA = Sha256(6);
signal input date[6];
SHA.in <== date;
signal output date_out[256];
date_out <== SHA.out;
}
component main = Birthday();if we want to prove that we know a birthday 13.03.2001, our input.json would look like this:
{"date":["1","3", "0", "3", "0", "1"]}Why circom/ zero knowledge?
We could just submit the hash and show with high probability that we know the value for ‘date’.
However, without the proof attached to the computation, one could just randomly guess the hash and there would be no proof of origin for the process of its computation. This would become a problem when multiple parties submit their answers independently, as only one of them would have to know “date” and the others could copy and submit the public parameter SHA256(date).
With a zk-proof, we can prove that we know some value ‘date’ whose hash is SHA256(date) instead of just proving that we know a hash SHA256(date).
Assuming the range of possible values for date is 01.01.1900–01.01.2000, there are about 365 * 100 = 36500 possible combinations. Therefore the chance of guessing a date correctly with n attempts is n/36500.
In a real-world zk application, this would not be considered secure, as a commonly used threshold for guessing the secret correctly is
n/2¹²⁸ < n/36500
Powersoftau constraints
Download a ptau file depending on the amount of constraints in your circuit.
For the “Proving a SHA256 hash” example above, based on it’s size of roughly 30000 constraints, I used this file.
Complete list of ptau files from iden3:
Generating and verifying the proof
After contributing to the powersoftau ceremony and generating a proof, the 256 bit SHA256 output can be found in public.json.
To generate a proof for the computation, follow the circom getting-started, but instead of generating pot12_final.ptau use the previously downloaded ptau file.
Running the verification checks out as expected:
[INFO] snarkJS: OK!We have successfully generated a valid proof for SHA256(date).
Limitations and proper use
During the trusted setup phase, it is recommended that many parties contribute to the generation of the verification key. This is necessary because circom relies on a high degree of randomness due to the fact that the same verification key is used over and over again for a single circuit, to both generate and verify proofs. A single honest contribution during this setup phase is enough to ensure cryptographic security.
Bonus: Proving an Ed25519 Signature
Electron-Labs created a circom project for Ed25519 signatures, utilizing the circom_tester wasm-testing framework.
I was able to successfully work through their readme after updating the circom-tester dependency:
The verify.circom script requires these inputs for a single signature:
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 ed25519verification test includes an example of how these inputs are constructed in javascript:
describe('When testing against the RFC test vector', () => {
it('should verify correctly', async () => {
const cir = await wasmTester(path.join(__dirname, 'circuits', 'verify.circom'));
const pointA = [
43933056957747458452560886832567536073542840507013052263144963060608791330050n,
16962727616734173323702303146057009569815335830970791807500022961899349823996n,
1n,
47597536765056690778342994103149503974598380825968728087754575050160026478564n];
const pointR = [
26073464383897998325899031212762184271676052677226679463708862316754828477519n,
20246927599389923510374971105736264637524117420538179767629249587300902801762n,
1n,
7867784340861643381702890578607277776011430152424699121581244161773093676488n];
const A = 16962727616734173323702303146057009569815335830970791807500022961899349823996n;
const msg = 33456n;
const R8 = 78142972218048021222160463610080218564159109753358461787358041591257467621730n;
const S = 4869643893319708471955165214975585939793846505679808910535986866633137979160n;
const bufMsg = utils.bigIntToLEBuffer(msg);
const bufR8 = utils.bigIntToLEBuffer(R8);
const bufS = utils.bigIntToLEBuffer(S);
const bufA = utils.bigIntToLEBuffer(A);
const bitsMsg = utils.buffer2bits(bufMsg);
const bitsR8 = utils.pad(utils.buffer2bits(bufR8), 256);
const bitsS = utils.pad(utils.buffer2bits(bufS), 255).slice(0, 255);
const bitsA = utils.pad(utils.buffer2bits(bufA), 256);
const chunkA = [];
const chunkR = [];
for (let i = 0; i < 4; i++) {
chunkA.push(utils.chunkBigInt(pointA[i], BigInt(2 ** 85)));
chunkR.push(utils.chunkBigInt(pointR[i], BigInt(2 ** 85)));
}
for (let i = 0; i < 4; i++) {
utils.pad(chunkA[i], 3);
utils.pad(chunkR[i], 3);
}
try {
const witness = await cir.calculateWitness({
msg: bitsMsg, A: bitsA, R8: bitsR8, S: bitsS, PointA: chunkA, PointR: chunkR,
});see the complete example here.
Conclusion
Circom is easy to use for developers and the circom-library enables everyone, regardless the level of expertise in math, to implement complex circuits.
Circom is a great entry point for those who seek some hands-on experience in the zero-knowledge space.
I could, however, have done more, had there been a few advanced examples in the getting-started. These would have especially helped me during my studies of Electron-Labs ed25519-circom, where input signals have reached a certain level of complexity and I spent hours formatting the inputs manually before finding the example shown above.
Nonetheless I am glad that I was able to use the wasm-tester in ed25519-circom and prove the SHA256 computation.
If you wish to reproduce the SHA256 example, where we prove that we know a value d such that SHA(date), follow the instructions on my github.
