Skip to content

Instantly share code, notes, and snippets.

@davidp94
Forked from badmofo/borromean.py
Created February 8, 2019 09:18
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save davidp94/0c0508548324b0a64ac448efa841d17e to your computer and use it in GitHub Desktop.
Pure Python Borromean Ring Signatures
'''
Pure Python Borromean Ring Signatures
DEPENDS ON: pip install ecdsa
WARNING: THIS IS A PEDAGOGICAL IMPLEMENTATION.
PERFORMANCE IS HORRIBLE AND NON-CONSTANT.
CORNER CASES ARE NOT PROPERLY CHECKED.
FOR THE LOVE OF GOD USE THE CODE FROM THE ELEMENTS PROJECT.
https://gist.github.com/badmofo/2d6e66630e4a6748edb7
'''
from hashlib import sha256
from itertools import izip, count, chain
from struct import pack
from ecdsa.curves import SECP256k1
from ecdsa.util import string_to_number, number_to_string, randrange
from ecdsa.ellipticcurve import Point
Point.__hash__ = lambda self: hash(self.x() + self.y())
Point.__repr__ = Point.__str__
G = SECP256k1.generator
def H(m):
return sha256(m).digest()
def string_to_scalar(s):
n = string_to_number(s)
assert 0 <= n < SECP256k1.order
return n
def random_scalar():
return randrange(SECP256k1.order)
def bor_H(m, r, i, j):
r = serialize_point(r) if isinstance(r, Point) else r
return string_to_scalar(H(m + r + pack('!ii', i, j)))
def serialize_point(p): # SEC compressed format
return chr((p.y() & 1) + 2) + number_to_string(p.x(), SECP256k1.order)
def sign(message, rings, secret_keys):
'''
message: the message to sign
rings: an array rings; each ring is an array of pubkeys (as ecdsa.ellipticcurve.Point objects)
secret_keys: an array of signing keys (as raw numbers)
'''
secret_keys = {G * secret: secret for secret in secret_keys}
known_pubkeys = secret_keys.keys()
known_keys_by_ring = [set(known_pubkeys) & set(ring) for ring in rings]
# check we know a secret key in each ring
assert all(known_keys_by_ring)
known_key_indexes = [ring.index(known.pop()) for ring, known in zip(rings, known_keys_by_ring)]
M = H(message + ''.join(map(serialize_point, chain(*rings))))
s = [[random_scalar() for _ in ring] for ring in rings]
k = [random_scalar() for _ in ring]
e0_hash = sha256()
for ring,known_key_index,i in izip(rings, known_key_indexes, count()):
r_i_j = k[i] * G
for j in range(known_key_index + 1, len(ring)):
e_i_j = bor_H(M, r_i_j, i, j)
r_i_j = s[i][j] * G + e_i_j * ring[j]
e0_hash.update(serialize_point(r_i_j))
e0_hash.update(M) # this step not in paper?
e0 = e0_hash.digest()
for ring,known_key_index,i in izip(rings, known_key_indexes, count()):
e_i_j = bor_H(M, e0, i, 0)
for j in range(0, known_key_index):
r_i_j = s[i][j] * G + e_i_j * ring[j]
e_i_j = bor_H(M, r_i_j, i, j+1)
secret = secret_keys[ring[known_key_index]]
s[i][known_key_index] = (k[i] - e_i_j * secret) % SECP256k1.order
return e0, s
def verify(message, rings, signature):
e0, s = signature
M = H(message + ''.join(map(serialize_point, chain(*rings))))
e0_hash = sha256()
for i,ring in enumerate(rings):
e_i_j = bor_H(M, e0, i, 0)
for j,pubkey in enumerate(ring):
r = s[i][j] * G + pubkey * e_i_j
e_i_j = bor_H(M, r, i, j+1)
e0_hash.update(serialize_point(r))
e0_hash.update(M)
return e0_hash.digest() == e0
if __name__ == '__main__':
import random
secrets = [random_scalar() for i in range(8)]
pubkeys = [G * s for s in secrets]
rings = [pubkeys[:4], pubkeys[4:]]
secret_keys = [random.choice(secrets[:4]), random.choice(secrets[4:])]
message = 'hello world!'
signature = sign(message, rings, secret_keys)
result = verify(message, rings, signature)
assert result
print 'OK'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment