STARK 101 - Part 3 FRI 承诺

[Whisker17]

Part 3 FRI 承诺

• Video
• Slides
• Notebook

Originally posted by @Whisker17 in https://github.com/Whisker17/learning-STARKs/issues/2#issuecomment-1126864104

[Whisker17]

• 我们的目标从证明 CP 是一个多项式转换成了证明 CP 接近于一个低幂次的多项式

• 低幂次的定义

  • 多项式的幂次是有上限的

• 什么是接近

  • 即两个多项式的距离（即点不同的数量）是一个比较小的数

[Whisker17]

FRI

过程：

• 总的来说，就是一个就是一个迭代降幂次的过程

[Whisker17]

FRI 折叠的过程

def next_fri_domain(fri_domain):
    return [x ** 2 for x in fri_domain[:len(fri_domain) // 2]]

[Whisker17]

• 多项式的形式

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)
    return odd + even

[Whisker17]

• 进行迭代

def next_fri_layer(poly, domain, beta):
    next_poly = next_fri_polynomial(poly, beta)
    next_domain = next_fri_domain(domain)
    next_layer = [next_poly(x) for x in next_domain]
    return next_poly, next_domain, next_layer

[Whisker17]

FRI 的承诺

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