calc-curve-trees.py

import math

# Estimates for Curve Trees
# Author: Mathias Hall-Andersen

GRP_SIZE = 256

def rel_point_check():
    return 4

def rel_unary(l):
    '''
    Constrain a vector of l elements to be of the form:
    (0, 0, ..., 0, 1, 0, ..., 0, 0)
    i.e. all but 1 entry is zero and the last entry is 1
    '''
    return l

def incomp_add():
    '''
    Incomplete addition on a Weierstrass curve
    '''
    return 3

def not_eq():
    '''
    Check that two variables are not equal
    '''
    # (y1 - y2) != 0
    return 1

def rel_is_bits(l):
    return l

def lookup_3bit(width=2):
    return width + 1

def rel_random_3bit(slen=GRP_SIZE):
    wins = math.ceil(slen / 3) # windows
    return sum([
        not_eq() + incomp_add(),   # final montgomery addition, with check for exception: require x1 != x2
        rel_is_bits(slen),         # bit check
        wins*lookup_3bit(width=2), # window lookups
        incomp_add()*(wins-1),     # incomplete additions
    ])

def rel_comm(dimension):
    return dimension

def rel_inner_prod(l):
    return l

def rel_decompress():
    return 3

rel_random = rel_random_3bit

'''
def rel_random():
    l = GRP_SIZE
    c = math.ceil(l / 3) # windows
    return sum([
        not_eq() + incomp_add(), # final montgomery addition, with check for exception: require x1 != x2
        l,                       # bit check
        2*c,                     # window lookups
        incomp_add()*c,          # incomplete additions
        rel_add_full()
    ])
'''

def rel_single(l, e):
    cost = 0
    cost += rel_decompress()
    cost += rel_point_check()
    cost += rel_random()

    cost += rel_unary(l)
    cost += rel_comm(l)
    cost += rel_inner_prod(l)

    cost += rel_unary(e)
    cost += rel_comm(e)
    cost += rel_inner_prod(l)
    return cost

def rel_range(b):
    return b

def rel_open(b):
    return rel_range(b)

def time_single(cons):
    # Rough estimate based on
    # https://eprint.iacr.org/2017/1066.pdf
    # Note: verification time has some non-linear behavior: due to multi-exponentation
    per_cons = 114.9 / 4096
    return per_cons * cons

def time_batch(cons):
    per_cons = 6.93 / 4096
    return per_cons * cons

def time_prove(cons):
    per_cons = 2551 / 4096
    return per_cons * cons

def size(cons):
    elems = 13 + 2 * math.ceil(math.log(cons, 2))
    return (elems * GRP_SIZE) // 8

RANGE = 64

TARGET = 2**32

import math

t = 6

ell = math.ceil(TARGET**(1/t))

print('Anonymity set:', ell**t, '(%.2f bits)' % math.log(ell**t, 2))

def print_circuit(c, ind=' '):
    # Intel i7-6820HQ system throttled to 2.00 GHz
    print(ind + 'Constraints  :', c)
    print(ind + 'Time (single): %.2f ms' % time_single(c))
    print(ind + 'Time (batch) : %.2f ms' % time_batch(c))
    print(ind + 'Time (prove) : %.2f ms' % time_prove(c))
    print(ind + 'Size         :', size(c), 'bytes')

print('Levels:', t, 'Dimension:', ell)

left = sum([rel_single(ell,1) for _ in range(0,t,2)])
right = sum([rel_single(ell,1) for _ in range(1,t,2)])

print('Membership:')
print('LEFT:')
print_circuit(left)
print('RIGHT:')
print_circuit(right)


create = sum([rel_range(RANGE)])

left_utxo = left + create
right_utxo = right


print('2 UTXO:')
print('LEFT:')
print_circuit(2 * left_utxo)
print('RIGHT:')
print_circuit(2 * right_utxo)
print('Plus:', t * 32 + 64 * 2, 'bytes')

for levels in range(2, 33):

    dim = math.ceil(TARGET**(1/levels))
    price = rel_single(dim, 1) * levels

    elems = dim**levels

    print('Total const:', price, 'levels:', levels, 'dimension:', dim, 'elems: %.2f' % math.log(elems, 2))