Pure Python Borromean Ring Signatures

borromean.py

'''
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'