stark 证明实操 python 实现 01

译者：Xiang｜W3.Hitchhiker

W3.Hitchhiker

Feb 16, 2023

无监督方法实现C++、Java、Python 代码转换，程序员：出了bug怎么办，两种语言都要看吗？_训练

本教程基于 stark101 教程翻译，可参考以下链接：

https://github.com/starkware-industries/stark101

在线运行

我们要用 STAEK 证明有限域内的 FibonacciSq 序列，这个 FibonacciSq 序列定义的关系为：

\(a_{n+2}=a_{n+1}^2+a_n^2\)

我们的代码将生成 STARK 证明，证明以下陈述(statement)：

我知道一个域元素

\(X ∈ F \)

, 从1开始的 FibonacciSq 序列，第 1023 个元素 X 是 2338775057。

基础

FieldElement 类（class）

我们用 FieldElement 类代表域元素，你可以从整型构造 FieldElement 的实例，然后进行加减乘除，求逆等操作，这个域大小为

\(\mathbb F_{3221225473}(3221225473=3*2^{30}+1)\)

，所有操作都是基于模 3221225473 运算的。

from field import FieldElement
FieldElement(3221225472) + FieldElement(10)

FibonacciSq 轨迹（trace）

首先，让我们构造一个长度为 1023 的列表 a，其前两个元素将分别是表示 1 和 3141592 的 FieldElement 对象。接下来的 1021 个元素由前两元素推导得出。a 称为 FibonacciSq 的执行轨迹

a = [FieldElement(1), FieldElement(3141592)]
while len(a) < 1023:
    a.append(a[-2] * a[-2] + a[-1] * a[-1])

测试你的代码

运行下面的代码块测试填充到 a 的元素是否正确，注意这其实是个验证器，尽管非常幼稚与不简洁，因为它是逐个检查元素，从而确保是正确的。

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('Success!')

多项式的思考

找一个大小为1024的群

g = FieldElement.generator() ** (3 * 2 ** 20)
G = [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 == 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('Success!')
else:
    print('g is of order > 1024')

多项式类

我们提供一个类叫 Polynomial。最简单的构建一个 Polynomial 使用变量 X (注意是大写的 X) 代表的正常变量 x :

from polynomial import X
# The polynomial 2x^2 + 1.
p = 2*X**2 + 1
# Evaluate p at 2:
print(p(2))
# Type a polynomial's name, on its own, in the last line of a cell to display it
p

多项式插值(Interpolating a Polynomial)

我们 polynomial 模块提供了拉格朗日插值功能，它的参数包括:

x_values：G 的 x 值，他们的多项式值是已知的。[列表]
y_values：对应的 y 值。[列表]

他返回唯一的次数(degree)小于 len(x_values) 对所有 i 的x_values[i] 值求值为y_values[i]的多项式实例。

运行以下代码块以获取有关函数 interpolate_poly 的帮助。

from polynomial import interpolate_poly
interpolate_poly?

假设 a 包含一些关于 G （除了 G[-1] 以外，因为 a 少一个元素）多项式的值，使用 interpolate_poly() 得到 f 然后获取它在 FieldElement(2) 的值。

from polynomial import interpolate_poly

f = interpolate_poly(G[:-1], a)
v = f(2)

跑测试：

assert v == FieldElement(1302089273)
print('Success!')

在更大的定义域上进行评估

轨迹(trace)，被视为多项式 f 在 G 上的评估, 可以在更大的定义域上评估 f 扩展，从而创建 Reed-Solomon 纠错码。

陪集（Cosets）

为此，我们必须决定一个更大的定义域来评估 f 。我们将在 8 倍 G 大小的定义域上工作。

这样一个定义域的自然选择是采取一些大小为 8192 的群 H (存在是因为 8192 能除

\( |\mathbb F^×|\)

，并通过

\(\mathbb F^×\)

的生成元对其进行移位 , 从而获得 H 的陪集 coset 。

提示：你已经知道如何获取 H - 用前面获取 G 同样的方式。

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]

跑测试：

from hashlib import sha256
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('Success!')

在陪集上评估

是时候使用 interpolate_poly 和 Polynomial.poly 来评估陪集。请注意，它是在我们的 Python 模块中原生实现的，因此插值可能需要长达一分钟的时间。事实上，插值和评估多项式轨迹是 STARK 协议中计算量最大的步骤之一，即使使用更有效的方法（例如 FFT，傅里叶变化）也是如此。

f = interpolate_poly(G[:-1], a)
f_eval = [f(d) for d in eval_domain]

承诺

我们将使用基于 Sha256 的 Merkle 树作为我们的承诺方式。你可以在 MerkleTree 类中获得它的简单实现。运行下一个代码块（为了本教程的目的，这也用于测试到目前为止整个计算的正确性）：

from merkle import MerkleTree
f_merkle = MerkleTree(f_eval)
assert f_merkle.root == '6c266a104eeaceae93c14ad799ce595ec8c2764359d7ad1b4b7c57a4da52be04'
print('Success!')

信道(Channel)

从理论上讲，STARK 证明系统是双方之间交互的协议 - 证明者和验证者。在实践中，我们使用 Fiat-Shamir Heuristic 式将这种交互式协议转换为非交互式证明。在本教程中，你将使用 Channel 类来实现此转换。在证明者（你正在编写的）将发送数据的意义上来说，此信道取代了验证者，并接收随机数或随机 FieldElement 实例。

这段简单的代码实例化一个信道对象，将默克尔树的根发送到它。稍后，可以调用信道对象以提供随机数或随机域元素。

from channel import Channel
channel = Channel()
channel.send(f_merkle.root)

最后 - 你可以通过打印成员 Channel.proof 来检索到目前为止的证明（即，在信道中传递到某个点的所有内容）

print(channel.proof)