The next stop point in code is when we check that our votingWeight
is less than factoryWeight
and we encounter the sub-circuit LessEqThan
. Inside the cicomlib’s comparators.circom
it uses LessThan here
that allows to make the so-called “range proofs”. We see Num2Bits
transform containing at least “bits amount” of contstraints and signals because in order to compare two numbers on the curve, we cannot simply “sub” them since the result of addition on a curve can lead to a situation when c = a + b
will be less (from our usual binary point of view) than a
, or b
, and there is no way other than analyse the bits. That’s why range proofs are really expensive in zkSNARKs circuits, they add many constraints, especially if they are used with different bitlengths, as a non-optimizable part of the circuits, etc. In the same time they are unavoidable for business logic and security purposes, there are no “overflows” in field arithmetics, and totally different values (in binary) can be “equal” in the field.
Next stop: the Baby JubJub private key -> public key transform is here
and then hashing it with Poseidon is here
. This simple part of the circuit shows how effective snark-friendly alorithms can be - Baby JubJub requires a small amount of constraints (thanks to optimized multiplications), Poseidon uses the signals without any bits transformations. All these choices allow to significantly reduce the witness size and proof generation time.
Next: the ZkAddress
circuit is here
(the code is above in the same file). Here, the Poseidon hash of the Baby JubJub public key is reduced to 20 bytes (to produce Vocodni address which is 20 bytes long). It requires the Num2Bits
sub-circuits adding another pack of contstraints (for inputs-outputs of bits<->num). There is no choice here, but if it’s possible, it’s better to avoid bits expansions and reductions (it can also sometimes lead to a lower cryptographic security level).
Next: the Merkle tree, and the verifier of a Merkle proof is here
. Here, we work with a sparse Merkle tree - implemented here
. The optimization trick of this tree is the design adding new values “from left to right” (a new value is added to the next “free” index) making it possible to have a “sparse” tree at the right side (most of right branches are empty and contain zeroes) while the “condensed” branches with values are at the left side. The description and discussion of these ideas are here
(a short version is here
). Now, with this primitive we can make the inclusion/exclusion (INSER/UPDATE/DELETE) proofs effectively. In the current circuit:
We check inclusion proof by setting smtClaimExists.fnc <== 0 here
(smtClaimExists.fnc <== 1
for exclusion proof) and prove that the previous value in the tree was zero here
The last: the check of the nullifier is here
: it must be equal to the hash made from processId
You can perform all steps to play around with the presented proof-of-concept, I simply compiled the census.circom
circuit and recieved ~40k of constraints for 160 levels in the Merkle tree (compare it to the single Keccak hashing from the first
article with ~150k of constraints). We used a private->public transform, verified the Merkle proof, hashed some intermediate signals - all this has been done only for 40k constraints saving the witness size and proof generation time for the users. Of course, to become a real application many things need to be added: the second part of circuit with commit-reveal keys, client-side sofrware, preparing proofs, management contracts - all of it is important for the voting system. But the core zk-part seems to be usable enough to become a good solution.
The description of the full voting cycle using Vocdoini was presented in this video
and described here