With HH we aim to prove that Alice knows two values (x, y) to equal a given answer (ans). Alice will pass the encrypted values for x and y, and Bob will verify that the sum is equal to an encrypted value of the answer (ans):
zkSnark (Homomorphic Hiding) |
Method
Let's say you want to prove that Alice can produce two number 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. They are 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) \times 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=7 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('======Encrypted values============') print('g^x=',(g**x) % n) print('g^y=',(g**y) % n) 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)