Skip to content

Instantly share code, notes, and snippets.

@marekyggdrasil

marekyggdrasil/ecc.py

Last active Jun 22, 2021
Embed
What would you like to do?
Example code for the tutorial on Pedersen Commitments and Confidential Transactions available under https://mareknarozniak.com/2021/06/22/ct/
import numpy as np
# ECC addition in R
def eccContAddition(Px, Py, Qx, Qy, a, b):
if np.isclose([Px], [Qx])[0]:
m = (3.*Px**2.+a)/(2.*Py)
else:
m = (Py-Qy)/(Px-Qx)
Rx = m**2 - Px - Qx
Ry = Py + m*(Rx - Px)
return Rx, Ry, m
# EC point addition
def onCurve(X, Y, a, b, p):
# None is the infinity point
if X is None and Y is None:
return True
return np.mod(Y**2 - X**3 - a*X - b, p) == 0
def extendedEuclideanAlgorithm(x1, x2):
# base case
if x1 == 0:
return x2, 0, 1
# recursive call
gcd, x_, y_ = extendedEuclideanAlgorithm(x2 % x1, x1)
x = y_ - (x2 // x1) * x_
y = x_
return gcd, x, y
# modular multiplicative inverse
def inverse(n, p):
if n == 0:
raise ZeroDivisionError('Stahp dividing by zero you!!!')
if n < 0:
# k ** -1 = p - (-k) ** -1 (mod p)
return p - inverse(-n, p)
gcd, x, _ = extendedEuclideanAlgorithm(n, p)
assert gcd == 1
assert np.mod(n*x, p) == 1
return np.mod(x, p)
def eccFiniteAddition(Px, Py, Qx, Qy, a, b, p):
if None in [Px, Py]:
return Qx, Qy
if None in [Qx, Qy]:
return Px, Py
# print(Px, Py, Qx, Qy)
assert onCurve(Px, Py, a, b, p)
assert onCurve(Qx, Qy, a, b, p)
if Px == Qx and Py != Qy:
# point1 + (-point1) = 0
return None, None
if Px == Qx:
m = (3*Px**2 + a)*inverse(2*Py, p)
else:
m = (Py - Qy)*inverse(Px - Qx, p)
Rx = np.mod(m**2 - Px - Qx, p)
Ry = np.mod(-(Py + m*(Rx - Px)), p)
assert onCurve(Rx, Ry, a, b, p)
return Rx, Ry
def eccNegation(Px, Py, a, b, p):
assert onCurve(Px, Py, a, b, p)
Rx = Px
Ry = np.mod(-Py, p)
assert onCurve(Rx, Ry, a, b, p)
return Rx, Ry
# EC point multiplication
def eccScalarMult(k, Px, Py, a, b, p):
assert onCurve(Px, Py, a, b, p)
if np.mod(k, p) == 0:
return [], [], None, None
if k < 0:
# k * point = -k * (-point)
Rx, Ry = eccNegation(Px, Py)
return eccScalarMult(-k, Rx, Ry)
rx, ry = Px, Py
Rxs, Rys = [rx], [ry]
for i in range(k-1):
rx, ry = eccFiniteAddition(rx, ry, Px, Py, a, b, p)
assert onCurve(rx, ry, a, b, p)
Rxs.append(rx)
Rys.append(ry)
return Rxs, Rys, rx, ry
def generateGroup(Gx, Gy, a, b, p):
Qx, Qy = Gx, Gy
orbit = [(0, 0)]
while (not (Qx == 0 and Qy == 0)) and (None not in [Qx, Qy]):
point = tuple([Qx, Qy])
orbit.append(point)
Qx, Qy = eccFiniteAddition(Qx, Qy, Gx, Gy, a, b, p)
return orbit
def bruteForceKey(Px, Py, pub_x, pub_y, a, b, p):
for k in range(p):
_, _, public_x, public_y = eccScalarMult(k, Px, Py, a, b, p)
if public_x == pub_x and public_y == pub_y:
return k
#!/bin/sh
convert -background none inputs_before.png inputs_after.png +append inputs.png
import numpy as np
import matplotlib.pyplot as plt
def plotF(sols_x, sols_y, p,
arrows=[],
highlights=[],
annotations=[],
title=None,
url=False,
filename='curve_finite_field.png'):
fig, axs = plt.subplots(1, 1)
axs.scatter(sols_x, sols_y, zorder=1)
delta = 0.1
for xs, ys, color in highlights:
if xs is None:
xs = 0
if ys is None:
ys = 0
axs.scatter(xs, ys, color=color)
for txt, Rx, Ry in annotations:
if Rx is None:
Rx = 0
if Ry is None:
Ry = 0
axs.annotate(txt, (Rx - 6*delta, Ry + 3*delta))
for Raxs, Rays, color, thickness in arrows:
if None in Raxs and None in Rays:
Raxs[Raxs.index(None)] = 0
Rays[Rays.index(None)] = 0
for k in range(len(Raxs)-1):
ox, oy = Raxs[k], Rays[k]
dx, dy = Raxs[k+1], Rays[k+1]
axs.arrow(ox, oy, dx-ox, dy-oy, head_width=thickness*2, length_includes_head=True, color=color, width=thickness)
axs.set_title(title)
axs.set_xticks(range(p))
axs.set_yticks(range(p))
axs.set_xlim([-1, p])
axs.set_ylim([-1, p])
axs.set_axisbelow(True)
axs.grid()
if url:
plt.figtext(0.0, 0.01, url, rotation=0)
plt.tight_layout()
fig.savefig(filename)
def plotSig(es, ss, rs, r_primes, labels, n, p,
title=None,
url=False,
filename='signatures.png'):
fig, axs = plt.subplots(len(es), 1)
plt.suptitle(title)
for ax, e, s, r, r_p, label in zip(axs, es, ss, rs, r_primes, labels):
ax.set_xticks(range(p+1))
ax.set_yticks(range(5))
ax.set_yticklabels(['', '$e$', '$s$', '$r$', '$r^\prime$'])
ax.set_xlim([-1, p+1])
ax.set_ylim([0, 5])
ax.set_axisbelow(True)
ax.grid()
ax.axvline(p, color='black')
ax.axvline(n, color='black', linestyle='dotted')
ax.text(p - 0.5, 0.5, '$p$', va='center')
ax.text(n - 0.5, 0.5, '$n$', va='center')
ax.axvline(e, color='tab:purple')
ax.axvline(s, color='tab:orange')
color = 'tab:red'
if r == r_p:
color = 'tab:blue'
ax.axvline(r, color=color, linestyle='dashed')
ax.axvline(r_p, color=color, linestyle='dotted')
ax.scatter(e, 1, color='tab:purple')
ax.scatter(s, 2, color='tab:orange')
ax.scatter(r, 3, color=color)
ax.scatter(r_p, 4, color=color)
ax.text(p + 1.25, 2.5, label, rotation=-90, va='center')
if url:
plt.figtext(0.0, 0.01, url, rotation=0)
plt.tight_layout()
fig.savefig(filename)
'''
plt.figure()
a = [1,2,5,6,9,11,15,17,18]
# Draw a horizontal line
plt.eventplot(a, orientation='horizontal', colors='b')
plt.axis('off')
plt.show()
'''
import math
import matplotlib.pyplot as plt
import numpy as np
import hashlib
from ecc import inverse, eccFiniteAddition, eccScalarMult, generateGroup, eccNegation, onCurve
from plotting import plotF, plotSig
def add_digits(num, p=17):
return (num - 1) % p + 1 if num > 0 else 0
def hashtard(m, p=17):
hash = hashlib.sha256(str.encode(m))
num = int.from_bytes(hash.digest(), 'big')
num = add_digits(num, p=p)
return num
def sign(m, k, d, Gx, Gy, n, p=17, a=0, b=7):
# calculate public key R = k*G
_, _, Rx, Ry = eccScalarMult(k, Gx, Gy, a, b, p)
# calculate e = H(M || r) where || is concatenation
e = hashtard(m, p=n)
# calculate the signature
s = np.mod(k - d*e, n)
# signature is s, R
return s, Rx, Ry
def verify(m, s, Gx, Gy, Px, Py, Rx, Ry, n, p=17, a=0, b=7):
# e_v = H(M || r_v)
e = hashtard(m, p=n)
# lhs = s*G
_, _, sGx, sGy = eccScalarMult(s, Gx, Gy, a, b, p)
# e*P
_, _, ePx, ePy = eccScalarMult(e, Px, Py, a, b, p)
# rhs = R+(e*P)
r_x, r_y = eccFiniteAddition(Rx, Ry, ePx, ePy, a, b, p)
# test if lhs = rhs
if r_x == sGx and r_y == sGy:
return True, r_x, r_y
return False, r_x, r_y
# n is a group order
def isTransactionValid(Gx, Gy, inputs_data, outputs_data, n, p=17, a=0, b=7):
inputs, inputs_multisignature = inputs_data
outputs, outputs_multisignature = outputs_data
# calculate inputs - outputs
inp_x, inp_y = inputs
inp_x, inp_y = eccNegation(inp_x, inp_y, a, b, p)
out_x, out_y = outputs
Px, Py = eccFiniteAddition(out_x, out_y, inp_x, inp_y, a, b, p)
# check if signature matches proving the difference is 0
inp_s, inp_rx, inp_ry = inputs_multisignature
out_s, out_rx, out_ry = outputs_multisignature
r_x, r_y = eccFiniteAddition(inp_rx, inp_ry, out_rx, out_ry, a, b, p)
s_comb = np.mod(out_s-inp_s, p)
valid, _, _ = verify('m', s_comb, Gx, Gy, Px, Py, r_x, r_y, n, p=p, a=a, b=b)
return valid
# article URL
url = 'https://mareknarozniak.com/2021/06/22/ct/'
# eliptic curve and finite field parameters
p = 29
a = 0
b = 7
# secp256k1 curve over finite field
sols_x = [0]
sols_y = [0]
points = []
for cx in range(p):
for cy in range(p):
if np.mod(cy**2-cx**3-cx*a-b, p) == 0:
sols_x.append(cx)
sols_y.append(cy)
point = tuple([cx, cy])
points.append(point)
# I found a nice point on this curve with prime order
idG = 14
Gx = sols_x[idG]
Gy = sols_y[idG]
# generate a cyclic group and get its order
group = generateGroup(Gx, Gy, a, b, p)
nG = len(group)
print('Order of G: ', str(nG))
# https://gist.github.com/cescapa/c655e8e0c1558660150f
if sum([ True if nG%factor == 0 else False for factor in ( [2] + list(range(3, int(math.sqrt(nG))+1,2) )) ]):
raise ValueError('Group order n is not prime, chose different generator point, id:', idG)
idH = 1
Hx = sols_x[idH]
Hy = sols_y[idH]
# generate a cyclic group and get its order
group = generateGroup(Hx, Hy, a, b, p)
nH = len(group)
print('Order of H: ', str(nH))
# https://gist.github.com/cescapa/c655e8e0c1558660150f
if sum([ True if nH%factor == 0 else False for factor in ( [2] + list(range(3, int(math.sqrt(nH))+1,2) )) ]):
raise ValueError('Group order n is not prime, chose different generator point, id:', idH)
# construct the inputs
# blinding factors
#bs = [1, 4, 2, 3]
# bs = [1, 4]
bs = [1, 3]
# amounts
#am = [2, 3, 1, 4]
# am = [2, 3]
am = [2, 4]
# compute blinded inputs
inpX = []
inpY = []
for bsv, amv in zip(bs, am):
# blinding factor curve point for current input
_, _, Bx, By = eccScalarMult(bsv, Gx, Gy, a, b, p)
# amount curve point for current input
_, _, Ax, Ay = eccScalarMult(amv, Hx, Hy, a, b, p)
# add them together
Rx, Ry = eccFiniteAddition(Bx, By, Ax, Ay, a, b, p)
inpX.append(Rx)
inpY.append(Ry)
# visualize pre-transaction space
annotations = [
('G', Gx, Gy),
('H', Hx, Hy),
('?', inpX[0], inpY[0]),
('Alice', inpX[1], inpY[1])]
highlights = [
([Gx], [Gy], 'tab:green'),
([Hx], [Hy], 'tab:cyan')]
for Rx, Ry in zip(inpX, inpY):
highlights.append(([Rx], [Ry], 'tab:orange'))
plotF(sols_x, sols_y, p,
annotations=annotations,
highlights=highlights,
url=url,
title='Inputs before the transaction',
filename='inputs_before.png')
# perform the transaction
# the payor owns an input of value of 4 coins
# is going to transfer 1 coin to payee and 3 coins
# back to him/herself as a change
inp_x, inp_y = inpX[1], inpY[1]
# payor signs input with blinding factor as the private key
k = 4
inp_s, inp_rx, inp_ry = sign('m', k, bs[1], Gx, Gy, nG, p=p, a=a, b=b)
# calculate the change, sending 3 coins back and choosing
# the blinding factor 4
_, _, Bx, By = eccScalarMult(4, Gx, Gy, a, b, p)
_, _, Ax, Ay = eccScalarMult(3, Hx, Hy, a, b, p)
chn_x, chn_y = eccFiniteAddition(Bx, By, Ax, Ay, a, b, p)
# payor signs change with blinding factor as the private key
k = 1
chn_s, chn_rx, chn_ry = sign('m', k, 4, Gx, Gy, nG, p=p, a=a, b=b)
# now the payee creates own output, is receiving 1 coin
# and choses the blinding factor of 2
_, _, Bx, By = eccScalarMult(2, Gx, Gy, a, b, p)
_, _, Ax, Ay = eccScalarMult(1, Hx, Hy, a, b, p)
nout_x, nout_y = eccFiniteAddition(Bx, By, Ax, Ay, a, b, p)
assert onCurve(nout_x, nout_y, a, b, p)
# payee signs own output with newly chosen blinding factor
k = 3
out_s, out_rx, out_ry = sign('m', k, 2, Gx, Gy, nG, p=p, a=a, b=b)
# gather all the outputs together to form a single output
out_x, out_y = eccFiniteAddition(nout_x, nout_y, chn_x, chn_y, a, b, p)
# add output signatures as well
out_rx, out_ry = eccFiniteAddition(out_rx, out_ry, chn_rx, chn_ry, a, b, p)
out_s = np.mod(out_s + chn_s, p)
# prepare data for the verifier
inputs = inp_x, inp_y
inputs_signature = inp_s, inp_rx, inp_ry
inputs_data = inputs, inputs_signature
outputs = out_x, out_y
outputs_signature = out_s, out_rx, out_ry
outputs_data = outputs, outputs_signature
valid = isTransactionValid(Gx, Gy, inputs_data, outputs_data, nG, p=p, a=a, b=b)
print('Is transaction valid?', valid)
# visualize the finite field after the transaction is made
# start by removing the input that was just spent from the
# finite field
del inpX[1]
del inpY[1]
# include the newly created inputs into the field
inpX.append(chn_x)
inpY.append(chn_y)
inpX.append(nout_x)
inpY.append(nout_y)
# plot again
annotations = [
('G', Gx, Gy),
('H', Hx, Hy),
('?', inpX[0], inpY[0]),
('Alice', inpX[1], inpY[1]),
('Bob', inpX[2], inpY[2])]
highlights = [
([Gx], [Gy], 'tab:green'),
([Hx], [Hy], 'tab:cyan')]
for Rx, Ry in zip(inpX, inpY):
highlights.append(([Rx], [Ry], 'tab:orange'))
plotF(sols_x, sols_y, p,
annotations=annotations,
highlights=highlights,
title='Inputs after the transaction',
filename='inputs_after.png')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment