DLEQ - Using the BN128 curve and Keccak-256This page provides a Non-interactive zero-knowledge (NIZK) proof for the equality (EQ) of discrete logarithms (DL). For this, Peggy (the 'Prover') is able to prove that she still knows her secret (such as being the holder of a private key), without giving away its value. Peggy creates a secret value (\(x\)) and then registers two values of \(xG\) and \(xH\), and where \(G\) and \(H\) are two points on the BN128 curve. Victor can check that \(log_{G}(xG) == log_{H}(xH)\). For each proof, Peggy produces her own challenge (\(c\)) and a response (\(r\)) - these provide the proof of knowledge. Victor (the 'Verifier') can then prove this against the two public key values that she has already sent to Victor. In this case, we will use the BN128 curve, and use the Keccak256 hash for the challenge. The use of the BN128 curve and Keccak are well matched to an implementation within an Ethereum smart contract [1]. |
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 has a secret (\(x\)) and then calculates \(x.G\) and \(x.H\), and where \(G\) and \(H\) are two random points on an elliptic curve. These can be registered with Victor. For each proof, she creates a challenge (\(c\)) and which is a hash of \(wG,wH,xG,xH\):
\(c = H(wG,wH,vG,vH)\)
Peggy then responds back with:
\(r= w - cx \pmod o\)
and where \(o\) is the order of the curve. 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][1]:
# Code extracted from https://github.com/PhilippSchindler/ethdkg import web3 from typing import Tuple import secrets 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.optimized_bn128 import field_modulus as FIELD_MODULUS # from py_ecc.typing import Optimized_Point3D, Optimized_FQ, Optimized_FQ2 from py_ecc.typing import Optimized_Point3D from py_ecc.fields import optimized_bn128_FQ, optimized_bn128_FQ2 keccak_256 = web3.Web3.solidityKeccak PointG1 = Optimized_Point3D[optimized_bn128_FQ] PointG2 = Optimized_Point3D[optimized_bn128_FQ2] FQ = optimized_bn128_FQ FQ2 = optimized_bn128_FQ2 H1 = ( FQ(9727523064272218541460723335320998459488975639302513747055235660443850046724), FQ(5031696974169251245229961296941447383441169981934237515842977230762345915487), FQ(1), ) H2 = ( FQ2((9110522554455888802745409460679507850660709404525090688071718755658817738702, 14120302265976430476300156362541817133873389322564306174224598966336605751189)), FQ2((8015061597608194114184122605728732604411275728909990814600934336120589400179, 21550838471174089343030649382112381550278244756451022825185015902639198926789)), FQ2((1, 0)) ) 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(x1: PointG1, y1: PointG1, x2: PointG1, y2: PointG1, alpha: int) -> Tuple[int, int]: """ DLEQ... discrete logarithm equality Proofs that the caller knows alpha such that y1 = x1**alpha and y2 = x2**alpha without revealing alpha. """ w = random_scalar() a1 = multiply(x1, w) a2 = multiply(x2, w) c = keccak_256( abi_types=["uint256"] * 12, values=[ int(v) for v in normalize(a1) + normalize(a2) + normalize(x1) + normalize(y1) + normalize(x2) + normalize(y2) ], ) c = int.from_bytes(c, "big") r = (w - alpha * c) % CURVE_ORDER return c, r def dleq_verify( x1: PointG1, y1: PointG1, x2: PointG1, y2: PointG1, challenge: int, response: int) -> bool: a1 = add(multiply(x1, response), multiply(y1, challenge)) a2 = add(multiply(x2, response), multiply(y2, challenge)) c = keccak_256( # pylint: disable=E1120 abi_types=["uint256"] * 12, # 12, values=[ int(v) for v in normalize(a1) + normalize(a2) + normalize(x1) + normalize(y1) + normalize(x2) + normalize(y2) ], ) c = int.from_bytes(c, "big") return c == challenge x=random_scalar() pub1=multiply(G1, x) pub2=multiply(H1, x) c,r = dleq(G1, pub1, H1, pub2,x) rtn=dleq_verify(G1, pub1, H1,pub2, c, r) print(f"Secret: {x}") print(f"x.G: {pub1}") print(f"x.H: {pub2}") print (f"\nc={c}, r={r}") print(f"Proven: {rtn}")
A sample run gives:
x: 10366729598460110564106835528331459549420144661779728900553421386151727683717 x.G: (19264659997498337231621849020324059839727633018344333818406571209706203133187, 12311200540645983074100160614979827101793507198593933504549623882564840726866, 20670726114001654463056991634829687089002941232072263069935333565317103573495) x.H: (14945644336923121346342859944168545416458423597018613969345084948695366548579, 6287194924561282354354695364050405821231283221714798271249840862954991383974, 9769023299891292075968207384775446300063615377412681646013428758993263180405) c=51608323136266335612692795096660702882832975771701719531287921368851758992301, r=5697936578451188395987467431508950282667773400761457095498679147707605201421 Proven: True
Reference
[1] Schindler, P., Judmayer, A., Stifter, N., & Weippl, E. (2019). Ethdkg: Distributed key generation with ethereum smart contracts. Cryptology ePrint Archive.