-
Notifications
You must be signed in to change notification settings - Fork 0
Mathematical Background
Compiler works for inputs from finite field F[p], for prime p.
This is required because the Elliptic Curves used later on during proof setup, generation and verification (Calculating the Common Reference String, and Pairing-based comparisons) are defined on prime fields. As far as I understand, zkSNARKS could in theory work with polynomials on arbitrary fields and this limitation results from the cryptographic methods employed.
To be more precise, the field must be the field of discrete logarithms of the generator of a bilinear group the pairing function used maps to (Parno, Gentry - Pinnochio; p.241).
Default value: (zCash q in base Field F_q for G1) 21888242871839275222246405745257275088696311157297823662689037894645226208583
Field operations can only be applied to field elements. So make sure all inputs are in the field. I don't think it is sensible to "interpret" violating inputs by applying the modulo operator. For example, this excludes negative inputs.
Sources:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627#.9vw195ipm
Note, that in many programming languages, the % operator does not correctly calculate modulo for negative numbers but rather returns a negative remainder.
Modulo is defined mathematically as returning r in the following decomposition of a:
a = bq + r
where
0 ≤ r < |b|
Implementations usually satisfy:
a = bq + r
where
|r| < |b|
but r can be negative.
(https://en.wikipedia.org/wiki/Modulo_operation)
For now, it seems reasonable to use:
a mod b = a−⌊a/b⌋b
(A + B) mod C = (A mod C + B mod C) mod C
(a + b) % p
(A - B) mod C = (A mod C - B mod C) mod C
a - b: (a - b) % p
(A * B) mod C = (A mod C * B mod C) mod C
a * b: (a * b) % p
Division is defined as multiplication with the modular inverse: (a/b) mod p = (a * b^(-1)) mod p.
The modular inverse of
A (mod C) is A^-1
(A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (mod C)
The inverse element always exists in prime fields.
'a / b: (a * b^(p-2)) % p' can be used but is slow.
Rather, the extendet Euclidean Algorith should be used, which calculates the Greatest Common Denominator and gives the coefficients of Bézout's identity:
GCD(a,b)=s*a + t*b
In prime fields, this can be used to calculate the modular inverse a^(-1) of a field element a:
GCD(a,p) = s*a + t*p = 1, since a and p coprime.
Hence, (s*a) mod p = 1
Thus, a^(-1)=s.
A^B mod C = ( (A mod C)^B ) mod C
A≡B (mod C)
is equivalent to
A mod C = B mod C
and
A = B + K⋅C
Comparison is hard as there is no way to specify a purely arithmetic comparison operation which returns a boolean value.
Hence, we ask for a bit decomposition of all inputs as additional input, verify this decomposition and then use it for comparison operations.
Assuming we have a, b and decomp(a), decomp(b).
Using the binary decomposition, we can then check a_i == b_i for all positions i by using boolean XNOR.
XNOR can be computed with an arithmetic gate of the following form: x XNOR y = 1+(x-y)(y-x)
To arrive at the final out, we use a boolean AND gate to make sure all positions were equal. x AND y = xy
Hence, we multiply a_i XNOR b_i for all i.
###Non-optimized version a, b, bin(a), bin(b) given. Calculate a-b on binary level, i.e., for all i a_i - b_i. look at overflow bit (position n+1 when length(bin(a))=n)
a >= b -> no overflow
a < b -> overflow
###Optimized version (since p-1/2 known a-priori)
Compare bin(c) = bin(a-b) with (p-1)/2:
c < (p-1/2) <=> a>b <=> c-(p-1)/2 overflows
c >= (p-1/2) <=> a<= b <=> c-(p-1)/2 doesn't overflow