verkle_constraints_msm.py

#!/usr/bin/env python3

import math

n = 2**29 # 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)

N = 25000 # total number of verkle tree openings

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

def multiexp(s):
    ratio = 52 # exp. ratio found, between the size and the number of additions
    order = 256
    return s * ratio * c_a + 2 * order # 2 times to be sure we cover, it's on expectation "order" but...

# Verkle tree part
verkle = N * c_h # seed computation
verkle += N * d * c_h # verkle tree encoding checks
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 += d * N * c_v # commitment to g1
multi += multiexp(d * N)
print("Multi points constraints: ", fo(multi))

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

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

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