Open dzyphr opened 1 year ago
I went through the tutorial session file to try and figure out the different approach being used there, I noticed someone had committed a change to it which allows it to pass the tests which are listed in the tutorial but not checked for in the tutorial_sessions.py file. I have created a version of this file with the updates, this required me to update the channel state and the value of the last fri layer constants. Once key values are found to be different, such as the coef value or the last fri layer constants, the channel state will also be different so the failing checks for the channel state are a key indicator of an error and will always need to be updated when a key value is updated. Here is my file, please let me know if these updates make sense.
from channel import Channel, serialize
from field import FieldElement
from merkle import MerkleTree
from polynomial import interpolate_poly, Polynomial
from hashlib import sha256
import time
def main():
# part1()
# part2()
#part3()
part4()
def part1():
t = [FieldElement(1), FieldElement(3141592)]
while len(t) < 1023:
t.append(t[-2] * t[-2] + t[-1] * t[-1])
assert len(t) == 1023, 'The trace must consist of exactly 1023 elements.'
assert t[0] == FieldElement(1), 'The first element in the trace must be the unit element.'
for i in range(2, 1023):
assert t[i] == t[i - 1] * t[i - 1] + t[i - 2] * t[i - 2], f'The FibonacciSq recursion rule does not apply for index {i}'
assert t[1022] == FieldElement(2338775057), 'Wrong last element!'
print('Fib Sq Trace Success!')
g = FieldElement.generator() ** (3 * 2 ** 20)
points = [g ** i for i in range(1024)]
# Checks that g and G are correct.
assert g.is_order(1024), 'The generator g is of wrong order.'
b = FieldElement(1)
for i in range(1023):
assert b == points[i], 'The i-th place in G is not equal to the i-th power of g.'
b = b * g
assert b != FieldElement(1), f'g is of order {i + 1}'
if b * g == FieldElement(1):
print('Generator Order Success!')
else:
print('g is of order > 1024')
h_gen = FieldElement.generator() ** ((2 ** 30 * 3) // 8192)
h = [h_gen ** i for i in range(8192)]
domain = [FieldElement.generator() * x for x in h]
from hashlib import sha256
assert len(set(domain)) == len(domain)
w = FieldElement.generator()
w_inv = w.inverse()
assert '55fe9505f35b6d77660537f6541d441ec1bd919d03901210384c6aa1da2682ce' == sha256(str(h[1]).encode()).hexdigest(),\
'H list is incorrect. H[1] should be h (i.e., the generator of H).'
for i in range(8192):
assert ((w_inv * domain[1]) ** i) * w == domain[i]
print('Eval Domain Success!')
p = interpolate_poly(points[:-1], t)
ev = [p.eval(d) for d in domain]
assert '1d357f674c27194715d1440f6a166e30855550cb8cb8efeb72827f6a1bf9b5bb' == sha256(serialize(ev).encode()).hexdigest()
print('Coset Eval Success!')
mt = MerkleTree(ev)
assert mt.root == '6c266a104eeaceae93c14ad799ce595ec8c2764359d7ad1b4b7c57a4da52be04'
print('Commitments Success!')
ch = Channel()
ch.send(mt.root)
return t, g, points, h_gen, h, domain, p, ev, mt, ch
def part2():
t, g, points, h_gen, h, domain, p, ev, mt, ch = part1()
numer0 = p - Polynomial([FieldElement(1)])
denom0 = Polynomial.gen_linear_term(FieldElement(1))
p0 = numer0 / denom0
assert p0(2718) == 2509888982
print('p0 test Success!')
q0, r0 = numer0.qdiv(denom0)
numer1 = p - Polynomial([FieldElement(2338775057)])
denom1 = Polynomial.gen_linear_term(points[1022])
q1, r1 = numer1.qdiv(denom1)
p1 = numer1 / denom1
assert p1(5772) == 232961446
print('p1 test Success!')
inner_poly0 = Polynomial([FieldElement(0), points[2]])
final0 = p.compose(inner_poly0)
inner_poly1 = Polynomial([FieldElement(0), points[1]])
composition = p.compose(inner_poly1)
final1 = composition * composition
final2 = p * p
numer2 = final0 - final1 - final2
coef = [FieldElement(-1)] + [FieldElement(0)] * 1023 + [FieldElement(1)]##this seems to be the only change made that effects the computation
numerator_of_denom2 = Polynomial(coef)
factor0 = Polynomial.gen_linear_term(points[1021])
factor1 = Polynomial.gen_linear_term(points[1022])
factor2 = Polynomial.gen_linear_term(points[1023])
denom_of_denom2 = factor0 * factor1 * factor2
denom2, r_denom2 = numerator_of_denom2.qdiv(denom_of_denom2)
p2 = numer2 / denom2
assert p2.degree() == 1023, f'The degree of the third constraint is {p2.degree()} when it should be 1023.'
assert p2(31415) == 2090051528
print('p2 test Success!')
print('deg p0 =', p0.degree())
print('deg p1 =', p1.degree())
print('deg p2 =', p2.degree())
q2, r2 = numer2.qdiv(denom2)
cp0 = q0.scalar_mul(ch.receive_random_field_element())
cp1 = q1.scalar_mul(ch.receive_random_field_element())
cp2 = q2.scalar_mul(ch.receive_random_field_element())
cp = cp0 + cp1 + cp2
cp_ev = [cp.eval(d) for d in domain]
cp_mt = MerkleTree(cp_ev)
#print(cp_mt.root)
#if above is correct including change to coef then this is the merkle root
assert cp_mt.root == 'd7e5200e990727c6da6bf711aeb496244b8b48436bd6f29066e1ddb64e22605b', 'Merkle tree root is wrong.'
# assert cp_mt.root == 'a8c87ef9764af3fa005a1a2cf3ec8db50e754ccb655be7597ead15ed4a9110f1', 'Merkle tree root is wrong.'#original
print('Merkle Root Success!')
return cp, cp_ev, cp_mt, ch, domain
def next_fri_domain(domain):
return [x ** 2 for x in domain[:len(domain) // 2]]
def next_fri_polynomial(poly, alpha):
odd_coefficients = poly.poly[1::2]
even_coefficients = poly.poly[::2]
odd = Polynomial(odd_coefficients).scalar_mul(alpha)
even = Polynomial(even_coefficients)
return odd + even
def next_fri_layer(poly, dom, alpha):
next_poly = next_fri_polynomial(poly, alpha)
next_dom = next_fri_domain(dom)
next_layer = [next_poly.eval(x) for x in next_dom]
return next_poly, next_dom, next_layer
def part3():
cp, cp_ev, cp_mt, ch, domain = part2()
next_p = next_fri_polynomial(cp, FieldElement(987654321))
assert '242f36b1d7d5b3e19948e892459774f14c038bc5864ba8884817112aa1405257' == sha256(','.join([str(i) for i in next_p.poly]).encode()).hexdigest()
print('Next p test Success!')
fri_polys = [cp]
fri_doms = [domain]
fri_layers = [cp_ev]
merkles = [cp_mt]
while fri_polys[-1].degree() > 0:
alpha = ch.receive_random_field_element()
next_poly, next_dom, next_layer = next_fri_layer(fri_polys[-1], fri_doms[-1], alpha)
fri_polys.append(next_poly)
fri_doms.append(next_dom)
fri_layers.append(next_layer)
merkles.append(MerkleTree(next_layer))
ch.send(merkles[-1].root)
ch.send(str(fri_polys[-1].poly[0]))
assert len(fri_layers) == 11, f'Expected number of FRI layers is 11, whereas it is actually {len(fri_layers)}.'
assert len(fri_layers[-1]) == 8, f'Expected last layer to contain exactly 8 elements, it contains {len(fri_layers[-1])}.'
print(([x for x in fri_layers[-1]]))
#edited fieldelement value
assert all([x == FieldElement(1443223587) for x in fri_layers[-1]]), f'Expected last layer to be constant.'
assert fri_polys[-1].degree() == 0, 'Expected last polynomial to be constant (degree 0).'
print(merkles[-1].root)
#edited root
assert merkles[-1].root == '38fe69bdc218d0327beba3197aaee3c0ba707912d0dec81301b8a7fca6a022bf', 'Last layer Merkle root is wrong.'
print(ch.state)
#edited state
assert ch.state == 'eba2039aca50b08d50c5f4775863e1adccc9d133dd52e74b624efb9937780ae7', 'The channel state is not as expected.'
print('FRI Commit Success!')
return fri_polys, fri_doms, fri_layers, merkles, ch
def part4():
_, _, _, _, _, _, _, f_eval, f_merkle, _ = part1()
fri_polys, fri_domains, fri_layers, fri_merkles, _ = part3()
def decommit_on_fri_layers(idx, channel):
for layer, merkle in zip(fri_layers[:-1], fri_merkles[:-1]):
length = len(layer)
idx = idx % length
sib_idx = (idx + length // 2) % length
channel.send(str(layer[idx]))
channel.send(str(merkle.get_authentication_path(idx)))
channel.send(str(layer[sib_idx]))
channel.send(str(merkle.get_authentication_path(sib_idx)))
channel.send(str(fri_layers[-1][0]))
test_channel = Channel()
for query in [7527, 8168, 1190, 2668, 1262, 1889, 3828, 5798, 396, 2518]:
decommit_on_fri_layers(query, test_channel)
print(test_channel.state)
assert test_channel.state == '0c7931382b6a846b4d91b485dcb51f8511b971f94513f72870392bfe7641ca36', 'State of channel is wrong.'
# assert test_channel.state == 'ad4fe9aaee0fbbad0130ae0fda896393b879c5078bf57d6c705ec41ce240861b', 'State of channel is wrong.'
#original state
print('FRI layers decommit test Success!')
def decommit_on_query(idx, channel):
assert idx + 16 < len(f_eval), f'query index: {idx} is out of range. Length of layer: {len(f_eval)}.'
channel.send(str(f_eval[idx])) # f(x).
channel.send(str(f_merkle.get_authentication_path(idx))) # auth path for f(x).
channel.send(str(f_eval[idx + 8])) # f(gx).
channel.send(str(f_merkle.get_authentication_path(idx + 8))) # auth path for f(gx).
channel.send(str(f_eval[idx + 16])) # f(g^2x).
channel.send(str(f_merkle.get_authentication_path(idx + 16))) # auth path for f(g^2x).
decommit_on_fri_layers(idx, channel)
test_channel = Channel()
for query in [8134, 1110, 1134, 6106, 7149, 4796, 144, 4738, 957]:
decommit_on_query(query, test_channel)
print(test_channel.state)
assert test_channel.state == '856682d2782140a10a371eb258ee85c05618f34ee0c695ae836aec6e4fc3f9b1', 'State of channel is wrong.'
#assert test_channel.state == '16a72acce8d10ffb318f8f5cd557930e38cdba236a40439c9cf04aaf650cfb96', 'State of channel is wrong.'
#old state
print('query decommit Success!')
def decommit_fri(channel):
for query in range(3):
# Get a random index from the verifier and send the corresponding decommitment.
decommit_on_query(channel.receive_random_int(0, 8191-16), channel)
test_channel = Channel()
decommit_fri(test_channel)
print(test_channel.state)
assert test_channel.state == '3424b78347d24261f921cd1a3b6dec864c90729b8d7c2c678cde327c68ab7c5b', 'State of channel is wrong.'
# assert test_channel.state == 'eb96b3b77fe6cd48cfb388467c72440bdf035c51d0cfe8b4c003dd1e65e952fd', 'State of channel is wrong.'
#old state
print('FRI decommitment Success!')
start = time.time()
start_all = start
print("Generating the trace...")
_, _, _, _, _, _, _, f_eval, f_merkle, _ = part1()
print(f'{time.time() - start}s')
start = time.time()
print("Generating the composition polynomial and the FRI layers...")
fri_polys, fri_domains, fri_layers, fri_merkles, channel = part3()
print(f'{time.time() - start}s')
start = time.time()
print("Generating queries and decommitments...")
decommit_fri(channel)
print(f'{time.time() - start}s')
start = time.time()
print(channel.proof)
print(f'Overall time: {time.time() - start_all}s')
print(f'Uncompressed proof length in characters: {len(str(channel.proof))}')
if __name__ == "__main__":
main()
Yeah, the random_field_element is different from the tutorial, because the cp_merkle.root
isn't sent to channel
in the part2 tutorial.
The tutorial seems to work very well up to part 2. At part 3 right after the
next_fri_polynomial
function is created, the test ofsha256(','.join([str(i) for i in next_p.poly]).encode()).hexdigest()
will fail even though the followingnext_fri_layer
test will pass indicating that thenext_fri_polynomial
function is working as intended (which is not what the previous failure suggests). Then when it comes to theFriCommit
function I tested it across the example_session.py file and found that they both fail to pass these three tests:assert all([x == FieldElement(-1138734538) for x in fri_layers[-1]]), f'Expected last layer to be constant.'
assert fri_merkles[-1].root == '1c033312a4df82248bda518b319479c22ea87bd6e15a150db400eeff653ee2ee', 'Last layer Merkle root is wrong.'
assert test_channel.state == '61452c72d8f4279b86fa49e9fb0fdef0246b396a4230a2bfb24e2d5d6bf79c2e', 'The channel state is not as expected.'
Up to the points mentioned my program was not failing any tests. I will share my relevant python file, please let me know if I have followed the tutorial incorrectly or any other relevant info.