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 with Golang |
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:
package main import ( "crypto/rand" "crypto/sha256" "fmt" "github.com/coinbase/kryptology/pkg/core/curves" ) func main() { curve := curves.K256() G := curve.Point.Generator() x := curve.Scalar.Random(rand.Reader) M := G.Mul(x) x = curve.Scalar.Random(rand.Reader) Y := G.Mul(x) Z := M.Mul(x) k := curve.Scalar.Random(rand.Reader) A := G.Mul(k) B := M.Mul(k) h := sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A.ToAffineCompressed()) h.Write(B.ToAffineCompressed()) c, _ := curve.Scalar.SetBytes(h.Sum(nil)) // s=k−h*x % o s := c.Mul(x).Sub(k) s = s.Neg() sG := G.Mul(s) cY := Y.Mul(c) A_ := sG.Add(cY) sM := M.Mul(s) cZ := Z.Mul(c) B_ := sM.Add(cZ) h = sha256.New() h.Write(G.ToAffineCompressed()) h.Write(Y.ToAffineCompressed()) h.Write(M.ToAffineCompressed()) h.Write(Z.ToAffineCompressed()) h.Write(A_.ToAffineCompressed()) h.Write(B_.ToAffineCompressed()) c2, _ := curve.Scalar.SetBytes(h.Sum(nil)) fmt.Print("Peggy's secret:\n") fmt.Printf("x= %s\n", x.BigInt()) fmt.Print("\nPeggy Computes):") fmt.Printf("\nxG %x\n", Y.ToAffineCompressed()) fmt.Printf("\nxM %x\n", Z.ToAffineCompressed()) fmt.Printf("A %x\n", A.ToAffineCompressed()) fmt.Printf("B %x\n", B.ToAffineCompressed()) fmt.Print("\nPeggy sends (s,c):") fmt.Printf("\ns %x\n", s.Bytes()) fmt.Printf("\nc %x\n", c.Bytes()) fmt.Print("\nVictor computes:") fmt.Printf("\nA_ %x\n", A_.ToAffineCompressed()) fmt.Printf("B_ %x\n", B_.ToAffineCompressed()) fmt.Printf("c2=%x", c2.Bytes()) if c.Cmp(c2) == 0 { fmt.Printf("\nProven") } }
A sample run is:
Peggy's secret:x= 85627829484113824886347178375789944915152802890040658632276559586099284639581 Computes): xG 02013c7ecc9d95fa9773b3baeb2bf6c6de6550b70a9871cd6cebfe30bad7fc80ba xM 02ea2dcbae992cb482e9a1944aff1c8628dcf3ee506bb98e0a137e4458ccd157b7 A 03a09063605d790ca4d20e4fb91c41cfd59e93fb46495206062719891e5c96d8e3 B 037168416af730e890c5bcd655fd0ad80b2ce7538e3f7fffa954a7cae8b32af884 Peggy sends (s,c): s 591f65d19c5fe0ca161ac36a54323ed1fcc9abb41df477b00f8b03435865bf11 c 90ab8ba7b0f4bcc2df96c7d027e3e5f213d7c22a49dff684072f899ea99ae895 Victor computes: A_ 03a09063605d790ca4d20e4fb91c41cfd59e93fb46495206062719891e5c96d8e3 B_ 037168416af730e890c5bcd655fd0ad80b2ce7538e3f7fffa954a7cae8b32af884 c2=90ab8ba7b0f4bcc2df96c7d027e3e5f213d7c22a49dff684072f899ea99ae895 Proven
References
[1] Chaum, David, and Torben Pryds Pedersen. "Wallet databases with observers." Annual international cryptology conference. Springer, Berlin, Heidelberg, 1992 [paper].