Simulating Boolean Computations with GF(p) Circuits
Written: , Published: , Author: Kimberlee Model, Tags: circuits, simple circuits,
In ZK Proofs it is difficult to compute some common operations because the typical GF(p) operations only allow two useful operations: addition and multiplication.
From these two simple operations, many others can be built, but many others cannot.
For example, exact equality or inequality can take advantage of Fermat’s Little Theorem, and from this we can build multiplexers to implement conditionals.
But comparative inequalities (less than, greater than, etc) are still impossible without further work.
In this post we’ll start by simulating Boolean logic in GF(p), then build up to comparison operations, and show how we can use these to simulate integer division.
To read this post you should be familiar with prime-modulus finite fields (GF(p)), Boolean arithmetic, and with Zero Knowledge Proofs as a concept.
I’ll also use snippets of C code for demonstration, along with truth-tables.
In C code, I’ll use unsigned int and show modular operations with (expr) % P.
Throughout this example we’ll use the prime 101, and we know that its bit-width is 7.
We’ll also use big-end first bit vectors, where relevant.
const unsigned int P = 101;
const unsigned int P_WIDTH = 7;Simulated Boolean Basics
To simulate Booleans we want values in GF(p), but we want to constrain them such that they only ever equal 0 or 1.
In ZK, it is easy to check that a value is equal to zero (for example with the SIEVE IR @assert_zero directive).
We can take advantage of this to make a simple test proving to the verifier that a value is in fact a Boolean value.
void assert_boolean(unsigned int v) {
assert(0 == (v * (v - 1) % P));
}When v == 0, this multiplies out as 0, and when v == 1 then v - 1 multiplies out to 0.
For any other value of v, it multiplies out to something non-zero.
Next we want some simple Boolean operations and, or, xor, etc.
and is the simplest because it is just multiplication.
l |
r |
l && r |
l * r |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
So we can make a simple function for Boolean and.
unsigned int bool_and(unsigned int l, unsigned int r) {
return (l * r) % P;
}or and xor (inclusive and exclusive or) are a bit trickier.
Addition is a good first try, but it produces 2 in the case where both operands are 1.
l |
r |
l || r |
l + r |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The next try is to notice that we already know that last case from and, so we can get rid of it by subtraction.
For or we subtract once, and xor we subtract twice.
const unsigned int NEG1 = (P - 1) % P;
unsigned int bool_or(unsigned int l, unsigned int r) {
return ((l + r) % P + (NEG1 * (l * r) % P)) % P;
}
const unsigned int NEG2 = (NEG1 * 2) % P;
unsigned int bool_xor(unsigned int l, unsigned int r) {
return ((l + r) % P + (NEG2 * (l * r) % P)) % P;
}Now we get the truth tables we want.
l |
r |
bool_or(l, r) |
bool_xor(l, r) |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lastly, the obvious implementation of not would be to xor by 1.
But a colleague showed me a trick where you multiply by -1 and then add 1.
unsigned int bool_not(unsigned int v) {
return ((v * NEG1 % P) + 1) % P;
}Unfortunately, every Boolean gate now costs a multiplication, instead of the "free xor" most ZK practitioners are accustomed to from legitimate Boolean ZK.
Bit Decomposition
Bit decomposition takes an arithmetic value, and produces bits, such that the total of all bits multiplied by their place all add back up to the original value.
In general there will be ceiling(log_2(P)) many bits for any field element v.
In plaintext, the prover — who knows all the values in the circuit — can decompose to bits as follows.
Then the prover can insert the bits as witness values into a circuit.
unsigned int value = /* value to be decomposed */;
unsigned int bits[P_WIDTH];
unsigned int val_cpy = value;
for(size_t i = 1; i <= P_WIDTH; i++) {
bits[P_WIDTH - i] = val_cpy & 1;
val_cpy = val_cpy >> 1;
}Of course the verifier isn’t about to believe that the prover got those all correct, so the prover needs to convince the verifier of the following three conditions.
-
Each bit is in fact a bit (Perhaps with the prior defined
assert_booleanfunction) -
The bits add up to the original value
-
And that the prover hasn’t exploited overflow with a value between
Pandpow(2, P_WIDTH)
The first two are easy to show using existing ZK functionality, as shown in the following snippet.
unsigned int recomp = bits[0];
assert_boolean(bits[0]);
for(size_t i = 1; i < P_WIDTH; i++) {
assert_boolean(bits[i]);
recomp = ((recomp * 2 % P) + bits[i]) % P;
}
assert(0 == (value + (recomp * NEG1) % P) % P);Proving that overflow has not been exploited will require a less-than comparison.
A decomposition of P can be provided in the instance — known to both prover and verifier — so that a verifiable decomposition is known to the verifier.
The next section will show the actual implementation of a less than circuit.
unsigned int prime_bits[P_WIDTH] = /* verifier already knows this */;
assert(0 == less_than_bits(prime_bits, bits));To better understand why this comparison is necessary, consider the case where the prover attempts to cheat by fudging the decomposition, inserting decomposition of a number greater than P when possible.
val_cpy = value;
if(val_cpy < (1 << P_WIDTH) - 1 - P) { val_cpy += P; }In this case, the recomposition — modulo P — would add up to the original value, but comparisons could be switched because the decomposition bits represents a much larger integer than they should.
The only way to prevent this is with the extra comparison to P's decomposition, which the verifier already knows.
Comparison Circuits
Comparing two bits has a fairly simple truth table.
l |
r |
l == r |
l < r |
l ⇐ r |
|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
For equality we get (l && r) || (!l && !r), but a careful examination will show us that the truth table is the opposite of xor, cutting us down to just 2 multiplications.
For strict less than, we get !l && r, also just two multiplications.
For less than or equal, because strict less than and equal share no common rows in the truth-table a simple add will suffice to combine them.
But even better, since a number is composed of many bits, we can postpone this add until each bit has been combined with its neighbors.
To combine them we’ll look at the truth table for "previous bits' equality", p, along with l < r.
p |
l |
r |
p && (l < r) |
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
What we’ve done here is and the less than comparator with a bit indicating if all prior bits were equal.
If a higher placed bit were inequal, then that value should take priority.
We can combine all these truth tables into a simple comparison function.
Again, when combining prior comparisons we can use addition in place of an or, as we know that if a higher placed bit were inequal, then this comparison will be 0.
unsigned int bits_less_than(
const unsigned int l_bits[P_WIDTH], const unsigned int r_bits[P_WIDTH])
{
unsigned int lt = bool_and(bool_not(l_bits[0]), r_bits[0]);
unsigned int p = bool_not(bool_xor(l_bits[0], r_bits[0]));
for(size_t i = 1; i < P_WIDTH - 1; i++) {
unsigned int tmp_lt = bool_and(bool_not(l_bits[i]), r_bits[i]);
lt = (bool_and(p, tmp_lt) + lt) % P;
p = bool_and(p, bool_not(bool_xor(l_bits[i], r_bits[i])));
}
return (bool_and(bool_and(
bool_not(l_bits[P_WIDTH - 1]), r_bits[P_WIDTH - 1]), p) + lt) % P;
}Less than or equal is a nearly identical function, changing only the last line so that less-than and equality are added together.
unsigned int bits_less_than_equal(
unsigned int const l_bits[P_WIDTH], unsigned int const r_bits[P_WIDTH])
{
unsigned int lt = /* ... */;
unsigned int p = /* ... */;
for(/* ... */) {
/* ... */
}
lt = (bool_and(bool_and(
bool_not(l_bits[P_WIDTH - 1]), r_bits[P_WIDTH - 1]), p) + lt) % P;
return (bool_and(bool_not(
bool_xor(l_bits[P_WIDTH - 1], r_bits[P_WIDTH - 1])), p) + lt) % P;
}Comparing two GF(p) values is now a simple matter of composing bit decomposition with one of our comparators.
Integer Division
Although integer division "doesn’t exist" in GF(p), we can now allow the prover to calculate integer division in clear text and prove its correctness under ZK.
Given a numerator n and a denominator d, the prover can calculate a quotient q and remainder r.
Then the prover must prove the following two things
-
n == q*d + r -
r < d
With a little bit of arithmetic, we can just use one of our recently developed comparison functions.
// return quotient, return remainder by pointer
unsigned int int_division(unsigned int n, unsigned int d, unsigned int* q)
{
unsigned int q;
if(I_AM_PROVER) {
q = n / d;
*r = n % d;
}
assert(0 == ((n * NEG1 % P) + ((q * d % P) + r) % P) % P);
unsigned int r_bits[P_WIDTH];
unsigned int d_bits[P_WIDTH];
bit_decompose(r_bits, r);
bit_decompose(d_bits, d);
assert(0 == bits_less_than_equal(d_bits, r_bits));
return q;
}Conclusion
In this post we started out with just GF(p) arithmetic in ZK, and used that to simulate Boolean logic.
Unfortunately every Boolean gate wound up costing us a multiplication, but we saw a few tricks to occasionally eliminate them.
Then we decomposed field elements into bits and used the bits to make comparators.
Lastly, these enabled us to simulate division in GF(p).
For convenience, I’ve attached a sample C file with this post’s example code.