DLEQ - Non-interactive zero-knowledge (NIZK) proofs for the equality (EQ) of discrete logarithms (DL)We can use Non-interactive zero-knowledge (NIZK) proofs, and where Peggy (the 'Prover') just has to prove that she still knows her secret. For this Victor (the 'Verifier') can send Peggy a challenge, and where Peggy can prove that she can provide a solution for it. Peggy creates a secret value (\(x\)) and then we creates two values \(xG\) and \(xH\), and can check that \(log_{G}(xG) == log_{H}(xH)\). We will use a range of curves for this example, including secp256k1, Curve 25519 and Curve 448. |
Method
Peggy creates a secret value (\(x\)) and then we creates two values \(xG\) and \(xH\), and can check that \(log_{G}(xG) == log_{H}(xH)\). Peggy first creates her secret (\(x\)), and then calculates \(xG\) and \(xH\), and where \(G\) and \(H\) are two random points on an elliptic curve.
With the challenge, Victor generates a random value (\(v\)) and computes \(vG\) and \(vH\).
Next Victor creates a challenge (\(c\)) and which is a hash of \(xG,xH,vG,vH\):
\(c = H(xG,xH,vG,vH)\)
Peggy then responds back with:
\(r= v - cx\)
The proof this then \((c,r,vG,vH)\).
Victor then proves that Peggy still knows the secret with:
\(vG == rG + c(xG)\)
\(vH == rH + c(xH)\)
If both are equal, Peggy has proven that she still knows \(x\).
This works because:
\(rG + c(xG) = (v-cx)G + c(xG) = vG - cxG + cxG = vG\)
Over the method is based on the technique described in "Wallet Databases with Observers - David Chaum and Torben Pryds Pedersen" and defined in this [paper] here:
Outline
The following is the code [taken from here]:
from ecpy.curves import Curve import web3 import hashlib import sys import random o=3 if (len(sys.argv)>1): o=int(sys.argv[1]) cv = Curve.get_curve('Curve25519') if (o==1): cv = Curve.get_curve('Curve25519') if (o==2): cv = Curve.get_curve('Curve448') if (o==3): cv = Curve.get_curve('Ed25519') if (o==4): cv = Curve.get_curve('Ed448') if (o==5): cv = Curve.get_curve('secp160r2') if (o==6): cv = Curve.get_curve('secp256k1') if (o==7): cv = Curve.get_curve('secp521r1') if (o==8): cv = Curve.get_curve('NIST-P192') if (o==9): cv = Curve.get_curve('NIST-P224') if (o==10): cv = Curve.get_curve('NIST-P256') def dleq(cv,G, xG, H, xH, x) -> [int, int]: """ DLEQ... discrete logarithm equality Proof xG = G**x and xH = H**x without revealing x """ v = random.getrandbits(256) vG = v*G vH = v*H c=hashlib.sha256() if (o>4): c.update(bytearray(cv.encode_point(vG))+bytearray(cv.encode_point(vH))+bytearray(cv.encode_point(G))+bytearray(cv.encode_point(H))) else: c.update(cv.encode_point(vG)+cv.encode_point(vH)+cv.encode_point(G)+cv.encode_point(H)) c = int.from_bytes(c.digest(), "big") r = (v - x * c) % cv.order return c, r def dleq_verify(cv,G, xG, H, xH, c, r) -> bool: v1 = r*G+c*xG v2 = r*H+c*xH c1=hashlib.sha256() if (o>4): c1.update(bytearray(cv.encode_point(v1))+bytearray(cv.encode_point(v2))+bytearray(cv.encode_point(G))+bytearray(cv.encode_point(H))) else: c1.update(cv.encode_point(v1)+cv.encode_point(v2)+cv.encode_point(G)+cv.encode_point(H)) c1 = int.from_bytes(c1.digest(), "big") return c == c1 import sys o=3 k=3 if (len(sys.argv)>1): o=int(sys.argv[1]) if (len(sys.argv)>2): k=int(sys.argv[2]) cv = Curve.get_curve('Curve25519') if (o==1): cv = Curve.get_curve('Curve25519') if (o==2): cv = Curve.get_curve('Curve448') if (o==3): cv = Curve.get_curve('Ed25519') if (o==4): cv = Curve.get_curve('Ed448') if (o==5): cv = Curve.get_curve('secp160r2') if (o==6): cv = Curve.get_curve('secp256k1') if (o==7): cv = Curve.get_curve('secp521r1') if (o==8): cv = Curve.get_curve('NIST-P192') if (o==9): cv = Curve.get_curve('NIST-P224') if (o==10): cv = Curve.get_curve('NIST-P256') G=cv.generator k=random.getrandbits(256) x=random.getrandbits(256) H = k*G xG = x*G xH = x*H c,r = dleq(cv,G,xG,H,xH,x) rtn=dleq_verify(cv,G,xG,H,xH,c,r) print(f"Secret: {x}") print(f"\nG {G}\nH {H}") print(f"xG {xG}\nxH {xH}") print(f"\nr {r}\nc {c}") print(f"Proven {rtn}") xG = 2*G rtn=dleq_verify(cv,G,xG,H,xH,c,r) print(f"\nNow trying with incorrect proof") print(f"Proven {rtn}")
For secp256k1 (as used in Bitcoin and Ethereum):
Secret: 63982215263568247601745311631279003465202433780512241072054048030573259797262 Curve: secp256k1 G (0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 , 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) H (0xc9e777de60dff3bb651b89183754bbc633c34b124429afe8cbaff130abb7bff5 , 0xc226252a3b46aca469f5c60cc6b9cc0269b4eb4ad00aca854c4ca32fe334a4d3) xG (0x6d90b9f5b46f3941e6348d8ed92782854a5ea9ee8a272a98b85a514ce19bf629 , 0xa065adb62fc072d595283e7e253be84e0e153dbd9e64e5460c98f2e65fecef8f) xH (0xbdfe73185998a544a1a0cb6a9295fbfb92e6f1540cedf36ce580aea0e4671a9c , 0x731aae59708adea73764f3d23f5a56a81058bf608442ba0c79766ea17806a766) r 90125572668683711489603164368065495744006174654104460425802198919169858499368 c 107825937711403206968145780031564534539988692950620669132412079396450712146098 Proven True Now trying with incorrect proof Proven False
For Curve 25519:
Secret: 18690474683086461460713063461271754220444615402100495222015265116086925442926 Curve: Curve25519 G (0x9 , 0x5f51e65e475f794b1fe122d388b72eb36dc2b28192839e4dd6163a5d81312c14) H (0x1115482bb646364e6eae3d75c7be354fdea754993540821f0d93fc025243c317 , 0x4fb440cfdf983b7b76662f1e06c07d08ce551d4db5d8877cdab163757caa2ed0) xG (0x29285bb17b1837a33c288bde67e245f1aa6a7159401f9bb5dd7d28be53aad233 , 0x4f450d66a8d9e1ac494962011924c099f14b8a3e4712b69722ca130e9dd4a519) xH (0x2816f0ea79681abefab52173789c4d7ff6c4afd43890553fd7715b3794bf9da5 , 0x4bd0ceb7a2cf802228c3bb90266e84624baa2c9ff26b6793492513a669c2c1ea) r 3020462407827138719390545969150100991159209441873956011173253330680110398838 c 24663589667284146045712092283857168740281469540443435182701292915331871018466 Proven True Now trying with incorrect proof Proven False
For Ed25519:
Secret: 53150667177630954558948916043054575388575447559883635385178918453231792231668 Curve: Ed25519 G (0x216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a , 0x6666666666666666666666666666666666666666666666666666666666666658) H (0x3ed49f0233613edff78010d357083d956210b8120874dadad04c9630b6bd8faa , 0x2e39074e246ebd0ef767bc48326df9fff88feba65c2876a99bd9f8779cb18eb0) xG (0x1bce91ca723dd02861f24d18b41f9ea2e771d325fc20ddac947ab15563e058db , 0x2ef92082fdf09d71982ca676ef14897b88e09ddb8404ace5d72a4f5ab78d7c5b) xH (0x9cc0e7846314ce0fcd5c86b6af2ddff28b84758f8b7f04f9ddb08389a447b55 , 0xc32284b06042defb3a7418f139b3d4e77bed4b375e4113b2e713d746efded3f) r 482262004192736350534770495755607021245328043610490554249313891448423906414 c 12978835977895637836006126852005025434540990349922731043054450819666689792385 Proven True Now trying with incorrect proof Proven False
For P-256:
Secret: 32372559162141655911813246899809165191446435355245933411392154216743033477002 Curve: NIST-P256 G (0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296 , 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5) H (0xe3adee74f5c2208077f252b255fdc6739a1b291e425bbfc588ee6858ab7874a3 , 0x9cb0402f8cd23afffa06556f88c9d40e8962ec9f8f593283b995dad590d1a758) xG (0x28600cec40d7b2560594108cb6d53585afdc7025444e49d03318f210823625ec , 0x711a821dacb4ee6e9a2c300fe35e2a362951d7b8f8b2c94893ce38a94b658a8d) xH (0xdc4e40cc3dc36b2b04758aed3095214c7d9692b40e41d49626ebbe87d4434e6f , 0xd5b91e6f29772256a06a17459f64a231608418c897570c3004756e8224d56881) r 13135691426624617228902919140539332010568758739660654298001729075045165597426 c 9972507816518806546289082327267621972354879441607739859149165437955343031562 Proven True Now trying with incorrect proof Proven False