译者：Xiang｜W3.Hitchhiker

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

在线运行

基础

FieldElement 类（class）

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

，所有操作都是基于模 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!')

多项式的思考

找一 d 个大小为 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 大小的定义域上工作。

提示: 你已经知道如何获取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)