DLEQ - 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)\). 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. The secret in this case is \(x\), and we will use the sepc256k1 curve, with the method linked to the creation of an Ethereum smart contract (and so uses keccak for our hashing methods). |
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\)
Overall 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]:
## Code derived from https://github.com/PhilippSchindler/EthDKG import secrets import web3 from py_ecc.optimized_bn128 import G1, G2 from py_ecc.optimized_bn128 import add, multiply, neg, normalize, pairing, is_on_curve from py_ecc.optimized_bn128 import curve_order as CURVE_ORDER from py_ecc.typing import Optimized_Point3D from py_ecc.fields import optimized_bn128_FQ, optimized_bn128_FQ2 PointG1 = Optimized_Point3D[optimized_bn128_FQ] PointG2 = Optimized_Point3D[optimized_bn128_FQ2] from typing import Tuple, Dict, List, Iterable, Union FQ = optimized_bn128_FQ FQ2 = optimized_bn128_FQ2 keccak_256 = web3.Web3.solidityKeccak def random_scalar() -> int: """ Returns a random exponent for the BN128 curve, i.e. a random element from Zq. """ return secrets.randbelow(CURVE_ORDER) def dleq(G: PointG1, xG: PointG1, H: PointG1, xH: PointG1, x: int) -> Tuple[int, int]: """ DLEQ... discrete logarithm equality Proof xG = G**x and xH = H**x without revealing x """ v = random_scalar() vG = multiply(G, v) vH = multiply(H, v) c = keccak_256( abi_types=["uint256"] * 12, values=[ int(v) for v in normalize(vG) + normalize(vH) + normalize(G) + normalize(xG) + normalize(H) + normalize(xH) ], ) c = int.from_bytes(c, "big") r = (v - x * c) % CURVE_ORDER return c, r def dleq_verify(G: PointG1, xG: PointG1, H: PointG1, xH: PointG1, c: int, r: int) -> bool: v1 = add(multiply(G, r), multiply(xG, c)) v2 = add(multiply(H, r), multiply(xH, c)) c1 = keccak_256( abi_types=["uint256"] * 12, # 12, values=[ int(v) for v in normalize(v1) + normalize(v2) + normalize(G) + normalize(xG) + normalize(H) + normalize(xH) ], ) c1 = int.from_bytes(c1, "big") return c == c1 x = random_scalar() G = G1 H = multiply(G1, random_scalar()) xG = multiply(G, x) xH = multiply(H, x) c, r = dleq(G, xG, H, xH, x) rtn= dleq_verify(G, xG, H, xH, c, r) print(f"x={x}\n\nG={G}\nxG={xG}\n\nH={H}\nxH={xH}\n\n") print("\nChecking xG = x.G and xH = x.H: ",rtn) rtn =dleq_verify(multiply(G1, 2), xG, H, xH, c, r) print("Checking xG = x.(2.G1) and xH= = x.H: ",rtn)
A sample run is:
x=1144840832071170684604960224055715539196473344976926145558227418488802461816 G=(20216955493980673351168688362608790503544706131663103661336303476090464043145, 11807000992250538846058008588560007106010888421947699746347174168479456669765, 209124209203815488252704698480655047026779884379921211681415502478087044613) xG=(3467865013696112012569336570511139429809178257634174091289376043656086272260, 10034455186714807346961838953098987862957339686750028044994978693345171610569, 18448056193695930936115265337514037216410997903725543739598982127653343108513) H=(9909253962266353143981556010240627955318011898789309898602743544532417306950, 13759968873124243025232260032254723989473606911747006070098230881077763369157, 18920654578265859492315962763233374106905672775017443419785893614079848770380) xH=(4516958546851672444140142589964729471787062458480434923566490314402184946669, 10513981680365179538593362654511341525768179593655092348053565741389178551388, 3531999860556858991133050815994186466619359468086666395324846398067233537676) Checking xG = x.G and xH = x.H: True Checking xG = x.(2.G1) and xH= = x.H: False