Let's say we have two base points on an elliptic curve (\(G\) and \(M\)), and then have two random values (\(k\) and \(x\)). If we have \(Y=xG\) and \(Z=xM\), can we prove that \(Y\) and \(Z\) use the same scalar value (\(x\))? For this, we then use \(G,Y,M,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(xG\) and \(xM\). In this case, we will use the sepc256k1 elliptic curve (as used in Bitcoin) to perform the operations.
NIZK (Non-interactive Zero Knowledge) proofs of discrete - log equality |
Theory
Let's say we have two base points on an elliptic curve (\(G\) and \(M\)), and then have two random values (\(k\) and \(x\)). If we have \(Y=xG\) and \(Z=xM\), can we prove that \(Y\) and \(Z\) use the same scalar value (\(x\))? For this, we then use \(G,Y,M,Z\) within a Chaum-Pedersen proof [1] to provide a zero-knowledge proof that \(log_G(Y) == log_M(Z)\). This is defined as DLEQ(Z/M == Y/G) - discrete log equality. With this we can prove that the same private key has been used for \(xG\) and \(xM\).
Let say Peggy (the prover) needs to prove that two public keys use the same private key (\(x\)) but with different base points:
\(Y = xG\)
\(Z = xM\)
Peggy will generator a random value (\(k\)) and then computes two points (\(A\) and \(B\)) based on the generator points used (\(G\) and \(M\)):
\(A = kG\)
\(B = kM\)
With non-interactive proofs, Peggy then creates a challenge (\(c\)) of:
\(c=Hash(G,Y,M,Z,A,B)\)
And then calculates:
\(s=k - cx \pmod n\)
and where \(n\) is the order of the curve. As the proof, Peggy then sends the following to Victor:
\((c,s)\)
The verifier (Victor) then computes:
\(A'=sG + cY\)
\(B'=sM + cZ\)
\(c'=Hash(G,Y,M,Z,A',B')\)
If \(c==c'\), the proof has been proven.
This works because:
\( \begin{align} A'+B' &= sG + cY + sM + cZ = (k-cx)G + cY + (k-cx)M + cZ = kG + cxG + cY + kM - cxM + cZ\\ &= kG - cY + cY + kM -cZ + cZ = kG + kM = A + B \end{align} \)
Code
Here is the code:
import random import hashlib from secp256k1 import curve,scalar_mult,point_add # Can we prove x is used x = random.randint(0, curve.n-1) # Peggy generates k k = random.randint(0, curve.n-1) r = random.randint(0, curve.n-1) # Two base points used G= curve.g M = scalar_mult(r,G) # Peggy wants to prove that Y and Z share x Y = scalar_mult(x,G) Z = scalar_mult(x,M) # Peggy generates to points A = scalar_mult(k,G) B = scalar_mult(k,M) G_x,_ = G M_x,_ = M A_x,_ = A B_x,y = B Y_x,y = Y Z_x,_ = Y # G,Y=xG, M , Z=xM, A=kG, B=kM # We will just use x co-ordinates for hash c=hashlib.sha256(G_x.to_bytes(32,'big')+Y_x.to_bytes(32,'big')+M_x.to_bytes(32,'big')+Z_x.to_bytes(32,'big')+A_x.to_bytes(32,'big')+B_x.to_bytes(32,'big')) digest = c.hexdigest() c = int(digest, 16) s=(k-c*x) % curve.n print (f"c={c}, s={s}\n\n") A_ = point_add(scalar_mult(s,G), scalar_mult(c,Y)) B_ = point_add(scalar_mult(s,M), scalar_mult(c,Z)) A_x,y = A_ B_x,y = B_ c_=hashlib.sha256(G_x.to_bytes(32,'big')+Y_x.to_bytes(32,'big')+M_x.to_bytes(32,'big')+Z_x.to_bytes(32,'big')+A_x.to_bytes(32,'big')+B_x.to_bytes(32,'big')) digest = c_.hexdigest() c_ = int(digest, 16) print (f"c={c_}") if (c==c_): print("\nProven!") else: print("\nNot proven!") print (f"\n\nA_x={A_x}, B_x={B_x}\n")
and here is the elliptic curve code for secp256k1 [code]:
# Code from: https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py import collections EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result def point_neg(point): """Returns -point.""" assert is_on_curve(point) if point is None: # -0 = 0 return None x, y = point result = (x, -y % curve.p) assert is_on_curve(result) return result
A sample run is:
x=35416836453933982290692276802598715692905104517036468320404568776284340190568, k=61373966280138216830657815314248992751337679135921632607587699413140057084241 G=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) M=(109313334810958477418321835497480696076356416408825979038916417641071785535510, 42436860500151098909615340702882320805111643294553141226977160459787210738143) A=(26826796251558955079235317283165928536253935451929951990183532315705741952623, 53202342644011362078490686414790012377384041579381932109021711369293617190511) B=(37944664236701417783091257402619603205531606235126016164345783936286432951278, 19113513177578213715672495528475763450271451179938795510108690299122769339603) Y=(106019702204816351426185591575742138944700259248555020992462182754709470335838, 26181941002749499427020424114275285554323295122454952021326958976654928222676) Z=(23511017161302932771891246196142291697198231493335006173532379876249399496914, 96295158920223023012699200915630000951625615202868968718354010341712645117480) c=14636018495143715303382353400769555713839065472325893247770338859312295689520, s=52676127977070219726246270185135606392788025498048831023138207679810143799338 c=14636018495143715303382353400769555713839065472325893247770338859312295689520 Proven! A_x=26826796251558955079235317283165928536253935451929951990183532315705741952623, B_x=37944664236701417783091257402619603205531606235126016164345783936286432951278
References
[1] Chaum, David, and Torben Pryds Pedersen. "Wallet databases with observers." Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].