stark证明实操python实现01
- w3hitchhiker
- 更新于 2023-02-28 10:13
- 阅读 941
通过stark简单证明实操python-01
译者：Xiang｜W3.Hitchhiker
本教程基于stark101教程翻译，可参考以下链接
https://github.com/starkware-industries/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)本文首发于：https://w3hitchhiker.mirror.xyz/aiuefqnoIDYIBUTD7bBDj-0uKagF5GW8QtnXfQ6tJX0
stark证明实操python实现02：https://learnblockchain.cn/article/5455
