Hunting the SNARK … How Do We Prove A Mathematical Computation Without Knowing The Values Used?

In the future, we need to be much more careful in how we use data and how much personal data we reveal.

Let’s say you want to prove that Alice can produce two numbers which adds up to 8. How does Bob prove that she knows them, without actually knowing the numbers that she picks? This method is the core of zkSNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) and overcomes the major problem of Blockchain — which is the lack of privacy in computations and transactions. It is used in zCash, and now being considered in a number of application areas around blockchain technology, as they can hide the entities, data and transaction details.

The core element of the method is the usage of HH (Homomorphic Hiding), and which allows us to perform a mathematical operation on encrypted values. For example if we have a value x and a value y, and we want to encrypt them we get:

E(x) and E(y)

Now with homomorphic encryption we can take the encrypted values and multiply them to get the addition:

E(x+y) = E(x) E(y)

We can perform this with discrete logs and where:

E(x+y) = g^{(x+y) mod p-1}

which is equal to:

E(x+y) = g^x g^y

Thus Alice encrypts x at g^x, and y with g^y, and then just multiply the values together to get:

E(x+y)

Now if Bob wanted to know if x plus y equals 8, Bob will then encrypt:

E(8)

and check they are the same. If they are then Alice knows how two numbers which add to 8. Here is the code:

import sys
import random
n=101
g= 3
ans=8
x = 3
y = 4
E1= g**( (x+y) % (n-1)) % n
E2= (g**x * g**y) % n
E3 = g**(ans) % n

print '======Agreed parameters============'
print 'P=',n,'\t(Prime number)'
print 'G=',g,'\t(Generator)'
print 'x=',x,'\t(Value 1 - Alice first value)'
print 'y=',y,'\t(value 2 - Alice second value)'
print 'ans=',ans,'\t(Answer = x+y?)'
print '======zkSnark===================='
print 'E1=',E1
print 'E2=',E2
print 'E3=',E3
if (E2==E3):
	print 'Alice has proven she knows the sum is ',ans
else:
	print 'Alice has proven she does not know the sum is ',ans

Here is a sample run here.

Blind evaluation problem

In the blind evaluation problem, we do not want Bob to determine the method we are using to implement a given function, but we want him to know the result with a value of s. Then although we get Alice to compute the result, she will not know s.

For this we use polynomials, and where we have an equation such as:

P(x)= a₀ + a₁ x + a₂ x²

Bob sends all the elements — known as hidings — of the computation for a value of s:

E(a₀), E(a₁ s) and E(a₂ s²)

Alice will not know the value of s used, but she knows the “wiring” of the function. In this case she knows that it is a simple adding operation, so she can compute using Homomorphic encryption:

E(P(s)) = E(a₀) + E(a₁ s) + E(a₂ s²)

She can do this because:

E(ax+by)=g^(ax+by)=g^(ax)⋅g^(by)=(g^x)^a⋅(g^y)^b=E(x)^a⋅E(y)^b

So Alice, who knows a and b, can simply raise the values received to the polynomial factors and multiply and return to Bob. Bob then knows the answer, but Alice doesn’t know the value of s used.

Here is some sample code for an equation of a x + b x²:

import sys
import random
n=101
g= 3
x=5
a = 3
b = 4
# eqn = ax + b x^2
E1= g**( a *x ) % n
E2= g**(b*x*x) % n
E3 = (E1 * E2) % n
E4 = g**(a*x + b*x*x) % n
print '======Agreed parameters============'
print 'P=',n,'\t(Prime number)'
print 'G=',g,'\t(Generator)'
print 'a=',a
print 'b=',b
print 'x=',x,'\t(Eqn= ax + bx^2)'
print '======zkSnark===================='
print 'E3=',E3
print 'E4=',E4
if (E3==E4):
	print 'Alice has computed the result'
else:
	print 'Alice has proven she does not know result'

Alice gets sent E1 and E2 and then she adds then (which is a multiplication with discrete logarithms), and sends E3 back. This is the result of E(3x + 4x²) for a value of x = 5. Alice does not know the value of x, and Bob doesn’t know how Alice did the computation.

Here is an example.

Conclusions

Within some blockchain implementations, we cannot hide the identities involved in a transaction and the code the implement. Thus we can tell how many bitcoins that Bob has in his account and all of this transactions. With zkSNARK we can hide the values used within computations on the blockchain.

If you are interested in Homomorphic encryption, try here.