Non-Interactive Zero Knowledge Proof (NI-ZKP) allows us to prove knowledge of a value, without giving away the value. This example uses Fiat-Shamir transformation and where Alice has a secret value of \(x\). Alice can then show a public value of \(xG\), and which is a point on the elliptic curve. Bob can then prove that Alice knows the value of \(x\) with (NI-ZKP). In this case, Alice will generate a random value (\(v\) and then send Bob the values of \(vG\), r and c, and where Bob can then tell that Alice knows the value of \(x\).
NI-ZKP (Zero Knowledge Proof) - using secp256k1 curve |
Theory
We use a Fiat Shamir method to prove that Alice knows \(x\). As we are using a non-interative method, Alice will create her own challenge with:
\(c=Hash((G) || (x) || (xG))\)
Alice then creates a random value (\(v\)) and computes:
\(V = vG\)
and:
\(r=(v-c x_1) % n\)
She sends the value of \(V\), \(r\) and \(c\) to Bob, and who computes:
\(V_{check} = rG + c (x G)\)
If \(V\) is equal to \(V_{check}\) Alice has proven that she knows \(x\).
Coding
The following is the code:
from secp256k1 import curve,scalar_mult, point_add import random import hashlib import sys secret="Hello" if (len(sys.argv)>1): secret=sys.argv[1] s=int(hashlib.md5(secret.encode()).hexdigest(),16) # Alice generates x = random.randint(0, curve.n-1) # Alice generates xG = scalar_mult(x, curve.g) print ("Let's prove that Alice knows x_1 with Fiat Shamir\n") chal=str(curve.g)+str(x)+str(xG) h=hashlib.md5() h.update(chal.encode()) v= random.randint(0, curve.n-1) vG = scalar_mult(v, curve.g) c=int(h.hexdigest(),16) r=(v-c*x) % (curve.n) Vcheck = point_add(scalar_mult(r,curve.g),scalar_mult(c,xG)) print (f"Value to prove is {x}") print (f"\nxG= {xG}") print (f"\nv= {v}, vG={vG}") print (f"\nr= {r}, c={c}") if (vG==Vcheck): print("\nIt has been proven!!!") else: print("\nNot proven!!!")
And a sample run:
Let's prove that Alice knows x with Fiat Shamir Value to prove is 39453035061538730972132695346908823374110795235584446095883797470940865348994 xG= (52703639832503000505077557980078009970772547026601077545536339809954486869925, 12363048174182892782319863380403495488032363119655628220124431198942731243202) v= 98396675227169707736279864870068519402460952354104047156332609011117300100943, vG=(14016909468776439795043314130921003740628054308305540209140154480453375930010, 67584014808474750334396552926202969762318607494050062127693077653569242017613) r= 40712767959947310716586609772122992272926753311240994230761195540243256850243, c=295426976571940371371606051744349077967 Vcheck= (14016909468776439795043314130921003740628054308305540209140154480453375930010, 67584014808474750334396552926202969762318607494050062127693077653569242017613) It has been proven!!!