Found Several Test Bugs

[dzyphr]

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 of sha256(','.join([str(i) for i in next_p.poly]).encode()).hexdigest() will fail even though the following next_fri_layer test will pass indicating that the next_fri_polynomial function is working as intended (which is not what the previous failure suggests).
Then when it comes to the FriCommit 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.

from polynomial import X, interpolate_poly, prod, Polynomial
from hashlib import sha256
from channel import serialize, Channel
from merkle import MerkleTree

def main():
    a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel = part1()
    cp, cp_eval, cp_merkle, channel, eval_domain = part2(a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel)
    part3(cp, cp_eval, cp_merkle, channel, eval_domain)

def part3(cp, cp_eval, cp_merkle, channel, eval_domain):
    '''
    print(eval_domain[100] ** 2)
    half_domain_size = len(eval_domain) // 2
    print(eval_domain[half_domain_size + 100] ** 2)
    '''
    def next_fri_domain(fri_domain):
        return [x**2 for x in fri_domain[:len(fri_domain) // 2]]
    '''
    next_domain = next_fri_domain(eval_domain)
    assert '5446c90d6ed23ea961513d4ae38fc6585f6614a3d392cb087e837754bfd32797' == sha256(','.join([str(i) for i in next_domain]).encode()).hexdigest()
    print('Next fri domain Success!')
    '''
    def next_fri_polynomial(poly,  beta):
        odd_coefficients = poly.poly[1::2]
        even_coefficients = poly.poly[::2]
        odd = beta * Polynomial(odd_coefficients)
        even = Polynomial(even_coefficients)
        # They are of the same degree so this will just add coefficients.
        return odd + even
    '''
    next_p = next_fri_polynomial(cp, FieldElement(987654321))
    assert '6bff4c35e1aa9693f9ceb1599b6a484d7636612be65990e726e52a32452c2154' == sha256(','.join([str(i) for i in next_p.poly]).encode()).hexdigest()
    print('Next Fri Polynomial Success!')
    #THIS TEST IS INCORRECT HOWEVER THE FUNCTIONALITY SEEMS TO BE WORKING PROBABLY SHOULD SUBMIT BUG
    '''
    def next_fri_layer(poly, domain, beta):
        next_poly = next_fri_polynomial(poly, beta)
        next_domain = next_fri_domain(domain)
        next_layer = [next_poly(d) for d in next_domain]
        return next_poly, next_domain, next_layer

    test_poly = Polynomial([FieldElement(2), FieldElement(3), FieldElement(0), FieldElement(1)])
    test_domain = [FieldElement(3), FieldElement(5)]
    beta = FieldElement(7)
    next_p, next_d, next_l = next_fri_layer(test_poly, test_domain, beta)
    assert next_p.poly == [FieldElement(23), FieldElement(7)]
    assert next_d == [FieldElement(9)]
    assert next_l == [FieldElement(86)]
    print('FRI Layer Success!')

    def FriCommit(cp, domain, cp_eval, cp_merkle, channel):
        fri_polys = [cp]
        fri_domains = [domain]
        fri_layers = [cp_eval]
        fri_merkles = [cp_merkle]
        while fri_polys[-1].degree() > 0:
            beta = channel.receive_random_field_element()
            next_poly, next_domain, next_layer = next_fri_layer(fri_polys[-1], fri_domains[-1], beta)
            fri_polys.append(next_poly)
            fri_domains.append(next_domain)
            fri_layers.append(next_layer)
            fri_merkles.append(MerkleTree(next_layer))
            channel.send(fri_merkles[-1].root)
        channel.send(str(fri_polys[-1].poly[0]))
        return fri_polys, fri_domains, fri_layers, fri_merkles

    test_channel = Channel()
    fri_polys, fri_domains, fri_layers, fri_merkles = FriCommit(cp, eval_domain, cp_eval, cp_merkle, test_channel)
    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])}.'
    assert all([x == FieldElement(-1138734538) for x in fri_layers[-1]]), f'Expected last layer to be constant.'
    assert fri_polys[-1].degree() == 0, 'Expacted last polynomial to be constant (degree 0).'
    assert fri_merkles[-1].root == '1c033312a4df82248bda518b319479c22ea87bd6e15a150db400eeff653ee2ee', 'Last layer Merkle root is wrong.'
    assert test_channel.state == '61452c72d8f4279b86fa49e9fb0fdef0246b396a4230a2bfb24e2d5d6bf79c2e', 'The channel state is not as expected.'
    print('FRI Commit Success!')



def part2(a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel):
    print('Part 1 constraints Success!')

    numer0 = f - 1
    denom0 = X - 1
    p0 = numer0 / denom0
    assert p0(2718) == 2509888982
    print('[ f(x) - 1 / (x - 1) ] Constraint Check Success!')
    p1 = (f - 2338775057) / (X - g**1022)
    assert p1(5772) == 232961446
    print("[x of p1 = (f(x) - 2338775057) / (x - g**1022)] Constraint Check Success!")

    #
    #            f(g**2 * x) - (f(g * x))**2 - (f(x))**2
    #   (x) = --------------------------------------------
    # p2                      x**1024 - 1
    #              ---------------------------------
    #              (x-g**1021)(x-g**1022)(x-g**1023)

    lst = [(X - g**i) for i in range(1024)]
    prod(lst)

    q = 2*X ** 2 + 1
    r = X - 3
    cmp = q(r)
    numer2 = f(g**2 * X) - f(g * X)**2 - f**2
    denom2 = (X**1024 - 1) / ((X - g**1021) * (X - g**1022) * (X - g**1023))
    print("Numerator at g^1020 is", numer2(g**1020))
    print("Numerator at g^1021 is", numer2(g**1021))
    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('Degree boundary constraint check success!')

    print('deg p0 =', p0.degree())
    print('deg p1 =', p1.degree())
    print('deg p2 =', p2.degree())


    def get_CP(channel):
        alpha0 = channel.receive_random_field_element()
        alpha1 = channel.receive_random_field_element()
        alpha2 = channel.receive_random_field_element()
        return alpha0*p0 + alpha1*p1 + alpha2*p2

    #test_channel = Channel()
    #CP_test = get_CP(test_channel)
    #assert CP_test.degree() == 1023, f'The degree of cp is {CP_test.degree()} when it should be 1023.'
    #assert CP_test(2439804) == 838767343, f'cp(2439804) = {CP_test(2439804)}, when it should be 838767343'
    #print('Compositional Polynomial Test Success!')
    channel = Channel()
    cp = get_CP(channel)

    def CP_eval(channel):
        CP = get_CP(channel)
        return[CP(e) for e in eval_domain]

    channel = Channel()
    cp_eval = CP_eval(channel)
    CP_merkle = MerkleTree(cp_eval)
    channel.send(CP_merkle.root)
    assert CP_merkle.root == 'a8c87ef9764af3fa005a1a2cf3ec8db50e754ccb655be7597ead15ed4a9110f1', 'Merkle tree root is wrong.'
    print('Compositional Polynomial Merkle Root Commit Success!')
    return cp, cp_eval, CP_merkle, channel, eval_domain


def part1():
    a = [FieldElement(1), FieldElement(3141592)]
    while len(a) < 1023:
        a.append(a[-2] * a[-2] + a[-1] * a[-1])
    print(a[-1])
    assert len(a) == 1023, 'The trace must consist of exactly 1023 elements.'
    assert a[0] == FieldElement(1), 'The first element in the trace must be the unit element.'
    for i in range(2, 1023):
       assert a[i] == a[i - 1] * a[i - 1] + a[i - 2] * a[i - 2], f'The FibonacciSq recursion rule does not apply for index {i}'
    assert a[1022] == FieldElement(2338775057), 'Wrong last element!'
    print("basic fib sq trace success!")

    multiplicative_group_size = FieldElement.k_modulus - 1
    subgroup_size = 1024
    k = multiplicative_group_size / subgroup_size
    g = FieldElement.generator() ** (3 * 2 ** 20)
    G = [g**i for i in range(subgroup_size)]

    assert g.is_order(1024), 'The generator g is of wrong order.'
    b = FieldElement(1)
    for i in range(1023):
        assert b == G[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("Finding group of size 1024 success!")
    else:
        print("g is of order > 1024")

    p = 2*X**2 + 1
    print(p(2))
    f = interpolate_poly(G[:-1], a)  # a is the FibonacciSq sequence we generated above
    v = f(2)
    assert v == FieldElement(1302089273)
    print('Interpolating polynomials Success!')

    w = FieldElement.generator()
    h = w ** ((2 ** 30 * 3) // 8192)
    H = [h**i  for i in range(8192)]
    eval_domain = [w * x for x in H]
    assert len(set(eval_domain)) == len(eval_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 * eval_domain[1]) ** i) * w == eval_domain[i]
    print('Large Eval Domain Success!')

    f = interpolate_poly(G[:-1], a)
    f_eval = [f(x) for x in eval_domain]
    assert '1d357f674c27194715d1440f6a166e30855550cb8cb8efeb72827f6a1bf9b5bb' == sha256(serialize(f_eval).encode()).hexdigest()
    print('Coset Eval Success!')

    f_merkle = MerkleTree(f_eval)
    assert f_merkle.root == '6c266a104eeaceae93c14ad799ce595ec8c2764359d7ad1b4b7c57a4da52be04'
    print('Merkle root committment Success!')
    channel = Channel()
    channel.send(f_merkle.root)
    print("Channel proof so far:\n", channel.proof)
    return a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel


if __name__=="__main__":
    main()

[dzyphr]

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()

[dajuguan]

Yeah, the random_field_element is different from the tutorial, because the cp_merkle.root isn't sent to channel in the part2 tutorial.