verkle_constraints_msm_h3.py

#!/usr/bin/env python3

import math

n = 2**30 # number of nodes in total
f = 256 # width of each node in the vtree
lf = math.log(f,2) 
d = math.log(n,f) # number of layers in the vtree
c_h = 505 # constraints to hash 
c_f = 506 # constraints to perform fixed based multiplication
c_v = 2249 # constraints to perform variable based multiplication
c_a = 6 # constraints to perform a simple addition
c_d = 5 # constraints to perform doubling (squaring in pippenger's)
c_decomp = 392 # decompression - see section A.3.3 of zcash specs 
c_check = 20 # check on curve and no small order - see section A.3.3 of zcash specs 
N = 25000 # total number of verkle tree openings

def fo(i):
    return '{:,}'.format(int(i)).replace(',', ' ')

def multiexp(s,decomp=False,check=False):
    ratio = 52 # exp. ratio found, between the size and the number of additions
    order = 256
    cost = s * ratio * c_a # number of additions
    cost += 2 * order  * c_d # number of point doubling roughly
    if check == True:
        cost = s * c_check # check points given are correct
    if decomp == True:
        cost += c_decomp * s # (de)compress the points
    return cost

# Verkle tree part
# verkle tree encoding checks - we only take the x coordinate (we check points are correct)
verkle = N * (d-1)  * c_check
print("Verkle Tree part constraints: ", fo(verkle))

# Multi point opening part
multi = 3 * c_h # hashes
multi += 3 * d * N # compute g2(t)
print("Multi points constraints ##1: ", fo(multi))
multi += multiexp(d * N) # commitment to g1 - points are already checked at previous part
print("Multi points constraints: ", fo(multi))

# IPA verification
ipa = lf * c_h # intermediate challenges computation
ipa += multiexp(lf * 2) # intermediate commitments computation
ipa += lf * 3 # final polynomial for bases
ipa += multiexp(f,check=True) # Compute g'
ipa += f * 3 # Compute b'
ipa += 2 * c_v # Final check

print("IPA constraints: ", fo(ipa))

print("TOTAL constraints: ",fo(ipa + multi + verkle))