Zoro is the SNARK circuit implementation of Ziesha's Main Payment Network contract.
The process of selecting transactions and proving/compressing them is separated in Ziesha Network. Validators who are elected according to their stake, have to select the transactions they want to include in the next block. The process of packaging isn't computationally intensive since packagers do not need to bother themselves proving the blocks. They will just make drafts of their block and provide these drafts to the provers.
The Pelmeni testnet is currently considering 90% of block rewards to be distributed between provers, and 10% of the rest to be distributed among stakers.
In order to setup a prover, you will need a machine with:
- At least 32GB of RAM
- 1 high-end Nvidia GPU Connected directly to the motherboard (Risers will slow down the process significantly!)
You will first need to install zoro:
git clone https://github.com/ziesha-network/zoro
cd zoro
cargo update
cargo install --path .
Now you'll need to generate the parameters needed for proving. You will need 64GB of memory for generating the params! If your RAM is 32GB, you can create an extra 32GB swap space.
zoro generate-params
Now you will need to connect to packagers and prove their drafted blocks for them:
zoro prove --gpu ---address MPN_ADDRESS --connect 65.108.248.12:8767 --connect 93.81.246.111:8767 --connect 136.169.209.154:8767 --connect 5.78.75.120:8767 --connect 34.125.14.164:8767 --connect 178.208.252.54:8767 --connect 185.188.249.208:8767 --connect 78.46.185.127:8767 --connect 94.16.109.190:8767 --connect 159.69.146.240:8767 --connect 65.108.65.36:8767 --connect 3.239.88.25:8767 --connect 178.238.230.218:8767 --connect 65.108.240.128:8767 --connect 65.108.218.99:8767 --connect 61.213.68.129:8767 --connect 135.181.199.165:8767 --connect 65.108.72.230:8767 --connect 65.108.193.133:8767 --workers 1
(Note: the IPs are for the current validators of the Pelmeni Testnet)
MPN_ADDRESS is the address which will receive your proving rewards!
This readme tries to explain the circuit in detail, for someone who is not an expert in Zero-Knowledge proofs.
Prime Field elements are integers that reside in the range [0..p) where p is a prime number. For different configurations of different proving systems, the value of p is different. E.g for proving systems based on Bls12-381 elliptic-curves (Which is the curve used by Ziesha Network), p is:
0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
These Prime-Fields are also known as the "Scalar Field" of the elliptic-curve being used. So, we are using the Scalar Field of Bls12-381 elliptic curve as our Prime-Field.
Prime-Fields form a mathematical field which means you can add, subtract, multiple or divide these numbers and the operations are associative and commutative:
Add: (a + b) mod P
Subtract: (a - b) mod P
Multiply: (a * b) mod P
Negate: (P - a) (Because (a + (P - a)) mod P = 0)
Divide: (a * (1/b)) mod P (1/b can be calculated using euclidean algorithm. E.g if P==7, then inverse of 2 is 4, because 2 * 4 mod 7 = 1. So if you want to divide a field-element by 2, you should just multiply it by 4, easy!)
- Associativity means: a + (b + c) = (a + b) + c, and a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c.
- Commutativity means: a + b = b + a, and a ⋅ b = b ⋅ a.
These field-elements are the building blocks of Zero-Knowledge proof circuits.
Let's say you have a list variables all residing in a Prime-Field: W=[w_0, w_1, w_2, w_3]. You can put mathematical constraints in the form of a⋅W * b⋅W + c⋅W==0, where (a, b, c) are vectors and ⋅ is dot-product.
We can model unimaginable forms of computations using this constraints. Some examples are provided below:
We want to make sure that w_1 * w_3 = w_2 + w_0:
We can represent this as: (1*w_1) * (1*w_3) + (-1*w_2 + 1*w_0)==0
Or: (0*w_0 + 1*w_1 + 0*w_2 + 0*w_3) * (0*w_0 + 0*w_1 + 0*w_2 + 1*w_3) + (1*w_0 + 0*w_1 + -1*w_2 + 0*w_3)==0
Simplified version using vectors: (0,1,0,0)⋅W * (0,0,0,1)⋅W + (1,0,-1,0)⋅W == 0
We want to make sure w_0 is either 0 or 1 and nothing else. We can use what we learnt from previous example to create a constraint for this equation:
w_0 * (1 - w_0) == 0
This can only happen when w_0 is really a binary number. The constraint is not satisfied if w_0 is not binary.
We have a number a, we want to make sure is_zero is 1 if a == 0 and is_zero is 0 if a != 0.
We define an auxiliary witness a_inv and put these constraints:
is_zero == -a_inv * a + 1
is_zero * a == 0
Now, if a is not zero, then is_zero has no choice but to be zero in order to satisfy the second constraint. If is_zero is 0, then a_inv should be set to inverse of a in order to satisfy the first constraint. inverse of a exists, since a is not zero.
If a is zero, the first constraint is reduces to is_zero == 1.
Assuming w_0 and w_1 are binary with these constraints:
w_0 * (1 - w_0) == 0
w_1 * (1 - w_1) == 0
Different logical operations can be done:
AND: w_0 * w_1 == w_2
OR: w_0 + w_1 - w_0 * w_1 == w_2
NOT: 1 - w_0 == w_2
Let's say w_0 is a k-bit number and we want to convert it to its binary form and store the bits in [w_1, w_2, ..., w_k].
This can be done using k+1 constraints. We first make sure all [w_1, w_2, ..., w_k] variable are binary using these k constraints:
w_1*(1-w_1)==0
w_2*(1-w_2)==0
...
w_k*(1-w_k)==0
Now we make sure the bits are really the binary representation of w_0 with a single constraint:
w_0 == [1, 2, 4, 8, ..., 2^(k-1)].[w_1, w_2, w_3, ..., w_k]
Note: These constraints also make sure the number is a k-bit number, i.e if the number has more than k-bits, the verification fails
Let's say w_0 is a k-bit signed integer and we want to negate then convert it to its binary form and store the bits in [w_1, w_2, ..., w_k].
This can be done using k+3 constraints. We first make sure all [w_1, w_2, ..., w_k] variable are binary using these k constraints:
w_1*(1-w_1)==0
w_2*(1-w_2)==0
...
w_k*(1-w_k)==0
Now we make sure the bits are really the binary representation of negate of w_0 with a single constraint:
2^k - w_0 == [1, 2, 4, 8, ..., 2^(k-1)].[w_1, w_2, w_3, ..., w_k]
You might notice that this constraint does not hold when w_0 is zero. So what's the solution?
We use these constraints instead:
w_0_is_zero == is_zero(w_0) // 2 constraints
2^k - w_0 == [1, 2, 4, 8, ..., 2^(k-1), 2^k].[w_1, w_2, w_3, ..., w_k, w_0_is_zero] // 1 constraint
Let's say s is a selector bit, a and b are inputs, and we want c == a if s == 0 and c == b if s == 1. (I.e c == s ? a : b)
We first make sure s is a bit:
(1 constraint)
s*(1-s)==0
Then:
(1 constraint)
(a - b) * s == a - c
Let's say s is a selector bit, a and b are inputs, and we want x,y == a,b if s == 0 and x,y == b,a if s == 1.
We first make sure s is a bit:
(1 constraint)
s*(1-s)==0
Then we put these constraints:
(2 constraints)
(a - b) * s == a - x
(b - a) * s == b - y
Now if s is 0 it equations become:
0 == a - x
0 == b - y
And if s is 1 it equations become:
a - b == a - x
b - a == b - y
We have a value v and 3 proof values p0, p1, p2. We have two selector bits s0 and s1.
In case of different s0 | s1 values we want to change the permutation of values. Outputs are v0, v1, v2 and v3.
s v0 v1 v2 v3
00 v p0 p1 p2
01 p0 v p1 p2
10 p0 p1 v p2
11 p0 p1 p2 v
We first check if s0 and s1 are boolean:
(2 constraints)
s0*(1-s0)==0
s1*(1-s1)==0
And then calculate outputs according to the table:
(8 contraints)
s0_and_s1 == s0 * s1
s0_or_s1 == s0 + s1 - s0*s1
v0 == s0_or_s1 ? p0 : v
v1p == s0 ? v : p0
v1 == s1 ? p1 : v1p
v2p == s0 ? p2 : v
v2 == s1 ? v2p : p1
v3 == s0_and_s1 ? v : p2
We want to make sure: lte == w_0 <= w_1
We do the following:
a_bits = to_k_bits(w_0) // k+1 constraints
b_bits_neg = to_k_bits_neg(w_1) // k+3 constraints
a_sub_b = sum_bits(a_bits, b_bits_neg) // 1 constraint
a_sub_b_bits = to_[k+1]_bits(a_sub_b) // k+2 constraint
gte == a_sub_b_bits[k-1] // 1 constraint
We want to build a hash function that gets a single number w_0 and returns w_1. It should be a one-way function, meaning that having w_1, it should be very hard (Or impossible) to determine w_0.
Repeated cubing and adding seems to provide this feature for us.
w_1 = (...((((w_0^3 + k_0)^3 + k_1)^3 + k_2)^3 + k_3) ...)^3 + k_n)
Where [k_0, k_1, ..., k_n] are fixed numbers.
In literature, this is called a MiMC hash function.
There is a group of elliptic-curves known as Twisted Edwards curves, which can be used as the building block of a Digital Signature Algorithm, called EdDSA. Twisted Edwards curves are defined using the following equation:
a.x^2 + y^2 = 1 + d.x^2.y^2
x and y are scalars that reside in a Prime-Field. If the Prime-Field of the EdDSA curve is different from the Scalar Field of our proving system, the we must somehow implement Prime-Field operations within the Prime-Field of our proving system, which is a very hard thing to do (Since we must implement the Modulus (%) operation using mathematical constraints). But if the Prime-Field of the EdDSA curve is same as Prime-Field of the proving system, then there is no need to implement Mod operation in our circuit, because all numbers are by default mod-ed into the Prime-Field of the EdDSA curve.
We mentioned that Ziesha uses Bls12-381 curve as the main curve in its proving system. There is a certain kind of Twisted Edwards curve available called JubJub which is defined on the Bls12-381's Scalar Field, allowing it to be easily integrated into a SNARK circuit. JubJub is a Twisted Edwards curve with following parameters.
A = -1
D = -(10240/10241)
Ziesha's zero-Knowledge transactions are signed using EdDSA signatures that are built on JubJub elliptic curve.
A Sparse Merkle Tree is a full binary-tree, which has 2^N leaves. N is generally 32 or 64. Thus the proofs are ~32 or ~64 hashes long. The leaves can be represented in a HashMap (E.g HashMap<uint64, FieldElem>).
If the value of a certain index in this tree is not present in the HashMap, it means the value is 0. Thus we call it sparse.
The directions of each proof element is derived from the binary representation of leaf index.
E.g suppose there is a Sparse Merkle Tree with 2^3 leaves. The root value is ROOT. We want to prove that 5th leaf of this tree has a value of VAL. Binary representation of 5 is 101. The proof is [P0, P1, P2]
Then the corresponding constraints of merkle-proof check would be:
t1 == MiMC(P0, val)
t2 == MiMC(t1, P1)
t3 == MiMC(P2, t2)
ROOT == t3