译者：Xiang｜W3.Hitchhiker

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

GitHub - starkware-industries/stark101

Contribute to starkware-industries/stark101 development by creating an account on GitHub.

https://github.com

https://hub.ovh2.mybinder.org/user/starkware-industries-stark101-25kx5my7/lab/tree/tutorial/NotebookTutorial.ipynb

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

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

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

首先，让我们构造一个长度为 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!')

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

我们 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 纠错码。

为此，我们必须决定一个更大的定义域来评估 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!')

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

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

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

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

print(channel.proof)

译者：Xiang｜W3.Hitchhiker

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

GitHub - starkware-industries/stark101

Contribute to starkware-industries/stark101 development by creating an account on GitHub.

https://github.com

https://hub.ovh2.mybinder.org/user/starkware-industries-stark101-25kx5my7/lab/tree/tutorial/NotebookTutorial.ipynb

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

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

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

首先，让我们构造一个长度为 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!')

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

我们 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 纠错码。

为此，我们必须决定一个更大的定义域来评估 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!')

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

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

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

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

print(channel.proof)