Skip to content

Instantly share code, notes, and snippets.

@HarryR
Last active December 24, 2017 16:35
Show Gist options
  • Save HarryR/16bbefd0b9fdba4da2732f33c1ecaa26 to your computer and use it in GitHub Desktop.
Save HarryR/16bbefd0b9fdba4da2732f33c1ecaa26 to your computer and use it in GitHub Desktop.
Zero Knowledge Proof of a preimage, without revealing the preimage
# Random element of S
ℝ ∈ S = λS -> {ω ∈ Ω | ℝ_ω ∈ S}
# A homomorphic function which transforms `x` from its additive
# group into its equivalent in the multiplicative group
G^x = {λx | x ∈ Z_(q-1)} -> X
# Maps `x` to `X` within `Z_q` while adhering to the random oracle model
H = λx -> X ∈ Z_q
# a, n and c are 'secret parameters'
# Alice knows `a`, Bob knows `b` and `c` is known by both
a, b, c <- ℝ ∈ Z_q
# X and Y are the public parameters
A, B <- G^a, G^b
# Generating the preimage proves knowledge of `A`, `B` and `c`
p = (a+b)*c % Z_q
= (a*c + b*c) % Z_q
# Proof of the preimage discloses neither `A`, `B` or `c`
P = G^p
= (A+B)^c
= A^c + B^c
w = H(c)
T = G^w
z = H(P||T)
Z = G^z
y = (w + (p*z)) % Z_q
= (w + (z*p)) % Z_q
S = G^y
= T+(P^z)
= T+(Z^p)
= T+(((A+B)^c)^z)
= T+(((A+B)^z)^c)
# Therefore, with only knowledge of `A` and `B`, `c` and `z` Alice can forge a signature on behalf of Bob, without needing `b`
from py_ecc import bn128
from random import randint
from hashlib import sha256
from py_ecc.bn128 import add, multiply, curve_order, G1, eq
def bytes_to_int(x):
o = 0
for b in x:
o = (o << 8) + ord(b)
return o
rands = lambda: randint(1, curve_order - 1)
sbmul = lambda s: multiply(G1, s)
hashs = lambda *x: bytes_to_int(sha256('.'.join(['%X' for _ in range(0, len(x))]) % x).digest()) % curve_order
hashp = lambda *x: hashs(*[item.n for sublist in x for item in sublist])
ecdhs = lambda A, b: hashp(multiply(A, b))
"""
Given public knowledge of `y`, `Y` and `(X+Y)^z`, prove that you know `Y`
without revealing `y`, `Y` or `z`.
This mechanism forms the basis of an exchange between two parties,
Alice and Bob.
1) Alice proves knowledge of `y` so an honest verifier with only `Y`.
2) This reveals `y` to Bob
3) Bob then reveals knowledge of `y` to an honest verifier with only `(X+Y)^z`
Both Alice and Bob can verify each other are honest with knowledge of `X`, `Y` and `z`.
An observer cannot link the actions of Alice and Bob without learning `z`.
By learning `z` and `y` an observer can determine what `X` is from `(X+Y)^z`
and subsequently determine that Alice's proof of `y` is related to Bob's proof of `y`.
Given `(X+Y)^z - Y^z = X^z` is a valid curve point, this creates an oracle of proof.
`z` can be derived `ECDH(X, y)` or `ECDH(Y, x)`, so if `X` is ever revealed
then `z` will be known too.
"""
exch_x = rands() # Only Bob knows `x`
exch_y = rands() # Bob learns `y` from the exchange after Alice reveals it
# Alice and Bob know X, Y and z
X = sbmul(exch_x)
Y = sbmul(exch_y)
exch_z = rands()
# Only Bob can prove knowledge of the preimage without revealing `y`
preimage = ((exch_x + exch_y) * exch_z) % curve_order
B = sbmul(preimage)
assert B == multiply(add(X, Y), exch_z)
# Bob constructs Schnorr proof of knowledge of `preimage`
# Because `w` and `t` are fixed to specific values and
# cannot be changed the attack against Schnorr protocol fails.
w = hashs(exch_z)
t = sbmul(w)
c = hashp(B, t)
Proof = w + (c * preimage) % curve_order
# Honest verifier checks proof of `y` without knowing `X`, `Y` or `z`
# Verifier knows `B`, `t`, will only allow Bob to prove
# This requires one PointAdd, two ScalarMult and one `Hash` operations
v_c = hashp(B, t)
v_x = add(t, multiply(B, v_c))
v_s = sbmul(Proof)
assert eq(v_x, v_s)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment