上区块链零知识证明：STARKs，Part-3：攻坚 _运算

现在，我们进入正题。
MIMC
这是我们将要实现的 STARK 函数：
def mimc(inp, steps, round_constants):start_time = time.time()for i in range(steps-1):inp = (inp**3 + round_constants[i % len(round_constants)]) % modulusprint("MIMC computed in %.4f sec" % (time.time() - start_time))return inp
我们之所以选择 MIMC（参见论文）作为例子，是因为它既（i）易于理解，同时（ii）足够有趣，并且在现实生活中实在的用处。该函数可被看作下图的形式：
注意：在许多关于 MIMC 的讨论中，你通常会看到人们使用的是 XOR 而不是 + 。这是因为 MIMC 通常在二进制域上完成，而二进制域的加法就是 XOR 。在这里，我们主要围绕素域进行。
在本例中，循环常量是一个相对较小的列表（例如只包含 64 项），列表中的数据不断循环（也就是说，在 k[64] 之后循环回到 k[1]）。
正如我们在这里所做的那样，具有非常多轮次的 MIMC 作为可验证的延迟函数是非常有用的——这是一种难以计算的函数，尤其是无法并行计算，但验证过程相对容易。MIMC 本身在某种程度上实现了“零知识”属性，因为 MIMC 可以“向后”计算（从其相应的“输出”中恢复“输入”），但向后计算需要的计算时间比向前计算多 100 倍（并且两种方向的计算时间都无法通过并行化来显著加快）。因此，你可以将向后计算函数视为“计算”不可并行化工作量证明的行为，并将前向计算函数计算为“验证”它的过程。
-我们可以由x -> x^(2p-1)/3 得出 x -> x^3 的倒数。根据费马小定理，这是正确的。费马小定理尽管“小”，但毫无疑问，它对数学的重要性要大于更着名的“费马最后定理” 。-
我们在这里尝试实现的是，通过使用 STARK 使验证更有效——相对于验证者必须自己在前向运行 MIMC，证明者在完成“后向”计算后，将计算“前向”计算的 STARK，并且验证者只需简单地验证 STARK 。我们希望计算 STARK 的开销能够小于前向运行 MIMC 的速相对于后向的速度差异，因此证明者的时间仍将由最初的“后向”计算而不是（高度可并行化的）STARK 计算主导。无论原始计算的耗时多长，STARK 的验证都可以相对较快（在我们的实现中，约为 0.05 到 0.3 秒）。
所有计算均以 2^256 – 351 * 2^32 + 1 为模。我们之所以使用这个素域模数是因为它是 2^256 以内最大的素数，它的乘法组包含一个 2^32 阶亚组（也就是说，存在数字 g，使得 g 的连续幂模这个素数之后能够在 2^32 个循环以后回到 1），其形式为 6k + 5 。第一个属性是必要的，它确保我们的FFT和FRI算法的有效版本可以发挥作用。第二个属性确保 MIMC 实际上可以“向后”计算（参见上述关于 x -> x^(2p-1)/3 的使用）。
素域运算
我们首先构建一个可进行素域运算以及在素域上进行多项式运算的方便的类。其代码在此。初始的细节如下：
class PrimeField():def __init__(self, modulus):# Quick primality testassert pow(2, modulus, modulus) == 2self.modulus = modulusdef add(self, x, y):return (x+y) % self.modulusdef sub(self, x, y):return (x-y) % self.modulusdef mul(self, x, y):return (x*y) % self.modulus
以及用于计算模逆的扩展欧几里德算法（相当于在素域中计算1 / x）：

文章插图

# Modular inverse using the extended Euclidean algorithmdef inv(self, a):if a == 0:return 0lm, hm = 1, 0low, high = a % self.modulus, self.moduluswhile low > 1:r = high//lownm, new = hm-lm*r, high-low*rlm, low, hm, high = nm, new, lm, lowreturn lm % self.modulus

上述算法的开销相对较大。所幸的是，在需要进行众多模逆计算的特殊情况中，有一个简单的数学技巧可以帮助我们计算多个逆，我们称之为蒙哥马利批量求逆：

上 区块链零知识证明：STARKs，Part-3：攻坚

上区块链零知识证明：STARKs，Part-3：攻坚