您当前位置: 首页> 资讯> 零知识证明的好兄弟,STARKs代码如何实施?

热门标签

热门动态

零知识证明的好兄弟,STARKs代码如何实施?

作者:链大全 日期:2018-08-13 10:17:49


此文主要目的,是向大家展示如何才能用python语言,来部署STARK算法。

STARKs(可扩容的透明知识论证)是创建一种证明的技术,这项证明中f(x)=y,其中f可能要花很长的时间来进行计算,但是这个证明可以被很快验证。STARK是“双重扩容”:对于一个需要t步骤的计算,这会花费大约O(t * log(t))步骤才能完成这个证明,这可能是最优的情况,而且这需要通过~O(log2(t))个步骤才能验证,对于中等大小的T值,它比原始计算快得多。STARKs也拥有隐私保护的“零知识证明”的特性,虽然我们将这类使用案例应用到其中,从而完成可验证的延迟功能,不需要这类性质,所以我们不用担心。

首先,先请几项说明:
• 这个代码还没有完全审核;在实际使用案例中的情况,还不能保证
• 这部分代码是还没有达到理想状态(是用Python语言写的)
STARKs 的“真实情况” 倾向于使用二进制字段而不是素数域的特定应用程序效率的原因;但是,他们确实也表现出,这里写出的代码是合法并且可用的。
• 没有一个真实的方法来使用STARK。它是一个非常宽泛的加密和数学架构,同时为不同的应用有不同的设置,以及连续的研究来减少证明者和验证者的复杂性,同时提高可用性。
• 此文希望大家能够知道,模运算和素数域是如何运行的,
并且和多项式概念,插值和估值进行结合。
现在,让我们一起来了解吧!

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)]) % modulus
    print("MIMC computed in %.4f sec" % (time.time() - start_time))
    return inp

我们选择MIMC作为案例,因为它(i)很容易理解,(ii)在真实世界使用的很多。函数功能见下图:

注意:在很多关于MIMC的讨论中,你可以典型地看出使用了XOR,而不是+;这是因为MIMC可以在二进制情况下使用,其中添加是XOR;这里我们会在素数领域进行。

在我们的案例中,常数相对而言会是比较小的列表(例如,64位),这会一直连续地进行周期循环(也就说,在k[64]之后)。MIMC自身可以获得这个特性,因为MIMC可以向后进行计算(从相应的输出获得输入),但是往后计算需要比向前计算多花费100倍的时间(并且没有方向可以同步进行)。所以你可以将往后计算的功能想象成计算不能同步的工作量证明,并且往前方向计算的功能可以作为验证的过程。

x -> x(2p-1)/3 是x -> x3 的反函数;根据费马小定理,这是真实的,尽管这个定理没有费马大定理出名,但是依然对数学的贡献很大。

我们尝试使用STARK来进行更加有效的验证,而不是让验证者必须在向前方向运行MIMC,在完成向后计算之后,证明者可以在向前方向进行STARK计算,并且验证者可以很简单地验证STARK。我们希望计算STARK可以比MIMC向前和向后之间的运行速度差别要小,所以证明者的时间仍然是有初始的向后计算来主导的。而并不是STARK计算。STARK的认证会相对较快(在python语言算法中,可以是0.05-0.3秒),不论初始的计算时间有多长。
所有的计算会在2256 – 351 * 232 + 1个模内完成;我们使用素数模,因为它是小于2256 最大的素数,其中乘法群包含了232 个子集(也就是说,有这样一个数g,从而在完全232次循环之后,G素数环的连续幂模绕回到1),而且是按照6k+5的形式。首个特性是保证FFT和FRI算法的有效版本,其次是保证MIMC实际上可以向后计算(请见上面提到的x -> x(2p-1)/3 使用方法)。

素域操作

我们通过建立方便的等级来进行素域的操作,同时也有多项式的操作。代码如下,收首先是小数位数:

class PrimeField():
    def __init__(self, modulus):
        # Quick primality test
        assert pow(2, modulus, modulus) == 2
        self.modulus = modulus

    def add(self, x, y):
        return (x+y) % self.modulus

    def sub(self, x, y):
        return (x-y) % self.modulus

    def mul(self, x, y):
        return (x*y) % self.modulus

并且使用扩展欧几里得算法,来计算模块逆转(这和在素域中计算1/x相同):

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

上面的算法是相对昂贵的;幸运地是,对于特定的案例,我们需要做很多的模逆计算,有一个数学方法可以让我们来计算很多逆运算,被称为蒙哥马利批量求逆:

使用蒙哥马利批量求逆来计算模逆,其输入为紫色,输出为绿色,乘法门为黑色,红色方块是唯一的模逆。

下面的代码是算法的体现,其中包含一些特别的逻辑。如果我们正在求逆的集合中包含零,那么它会将这些零的逆设置为 0 并继续前进。

def multi_inv(self, values):
    partials = [1]
    for i in range(len(values)):
        partials.append(self.mul(partials[-1], values[i] or 1))
    inv = self.inv(partials[-1])
    outputs = [0] * len(values)
    for i in range(len(values), 0, -1):
        outputs[i-1] = self.mul(partials[i-1], inv) if values[i-1] else 0
        inv = self.mul(inv, values[i-1] or 1)
    return outputs

这部分算法接下来会验证称为非常重要的东西,特别是当我们开始和不同阶的多项式进行计算的时候。
现在我们来看看一些多项式计算。我们把多项式当做一个数据集,其中的i是第i阶(例如,x3 + 2x + 1变成[1, 2, 0, 1])。下面就是在一个点进行多项式估算的方法:

# Evaluate a polynomial at a point
def eval_poly_at(self, p, x):
    y = 0
    power_of_x = 1
    for i, p_coeff in enumerate(p):
        y += power_of_x * p_coeff
        power_of_x = (power_of_x * x) % self.modulus
    return y % self.modulus

困难和挑战

f.eval_poly_at([4, 5, 6], 2)的输出是多少?模是31吗?

下面的解释就是答案

.其实也有代码是多项式加法,减法,乘法和除法;这是很长的加减乘除运算。有一个很重要的内容是拉格朗日插值,它将一组 x 和 y 坐标作为输入,并返回通过所有这些点的最小多项式(你可以将其视为多项式求值的逆):

# Build a polynomial that returns 0 at all specified xs
def zpoly(self, xs):
    root = [1]
    for x in xs:
        root.insert(0, 0)
        for j in range(len(root)-1):
            root[j] -= root[j+1] * x
    return [x % self.modulus for x in root]

def lagrange_interp(self, xs, ys):
    # Generate master numerator polynomial, eg. (x - x1) * (x - x2) * ... * (x - xn)
    root = self.zpoly(xs)

    # Generate per-value numerator polynomials, eg. for x=x2,
    # (x - x1) * (x - x3) * ... * (x - xn), by dividing the master
    # polynomial back by each x coordinate
    nums = [self.div_polys(root, [-x, 1]) for x in xs]

    # Generate denominators by evaluating numerator polys at each x
    denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))]
    invdenoms = self.multi_inv(denoms)

    # Generate output polynomial, which is the sum of the per-value numerator
    # polynomials rescaled to have the right y values
    b = [0 for y in ys]
    for i in range(len(xs)):
        yslice = self.mul(ys[i], invdenoms[i])
        for j in range(len(ys)):
            if nums[i][j] and ys[i]:
                b[j] += nums[i][j] * yslice
    return [x % self.modulus for x in b]

相关数学知识请参见此文的M-N部分。需要注意,我们也会有特别的方法lagrange_interp_4和lagrange_interp_2来加速次数小于 2 的拉格朗日插值和次数小于 4 的多项式运算。

快速傅立叶变换

如果你仔细阅读上面的算法,你也许会发现拉格朗日插值和多点求值(即求在N个点处次数小于N的多项式的值)都需要耗费2次时间,例如对于1000个点求拉格朗日插值,需要几百万个步骤,而且100万个点的拉格朗日插值需要万亿个步骤。这是不可接受的低效率,所以我们需要使用更加有效的算法,快速傅立叶变换。

FFT只需要花费O(n * log(n))的时间(也就是说,1000个点的计算需要10,000步,100万个点的计算需要2000步),虽然它的范围更受限制;x坐标必须是单位根部的完全集合,必须满足N = 2k 阶。也就是说,如果有N个点,那么x坐标必须某个P值的连续幂,1, p, p2, p3…,其中pN = 1。这个算法能够用来进行多点计算和插值计算,而且只需要调整一个小参数。

下面就是算法详情(这是个简单的表达方式;更详细内容可以参阅此处代码)

def fft(vals, modulus, root_of_unity):
    if len(vals) == 1:
        return vals
    L = fft(vals[::2], modulus, pow(root_of_unity, 2, modulus))
    R = fft(vals[1::2], modulus, pow(root_of_unity, 2, modulus))
    o = [0 for i in vals]
    for i, (x, y) in enumerate(zip(L, R)):
        y_times_root = y*pow(root_of_unity, i, modulus)
        o[i] = (x+y_times_root) % modulus
        o[i+len(L)] = (x-y_times_root) % modulus
    return o

def inv_fft(vals, modulus, root_of_unity):
    f = PrimeField(modulus)
    # Inverse FFT
    invlen = f.inv(len(vals))
    return [(x*invlen) % modulus for x in
            fft(vals, modulus, f.inv(root_of_unity))]

你可以自己通过一些输入来运行代码,并且看看是否能得到想要的结果,当你使用eval_poly_at的时候,给出你期望得到的答案。例如:

>>> fft.fft([3,1,4,1,5,9,2,6], 337, 85, inv=True)
[46, 169, 29, 149, 126, 262, 140, 93]
>>> f = poly_utils.PrimeField(337)
>>> [f.eval_poly_at([46, 169, 29, 149, 126, 262, 140, 93], f.exp(85, i)) for i in range(8)]
[3, 1, 4, 1, 5, 9, 2, 6]

傅里叶变换会把[x[0] …. x[n-1]]作为输入,并且它的目标是输出x[0] + x[1] + … + x[n-1]作为首个元素,x[0] + x[1] * 2 + … + x[n-1] * w**(n-1)作为第二个元素,等等;快速傅里叶变换可以通过把数据分为两半,来完成这个,在两边都进行FFT,然后将结果结合在一起。

上图就是信息如何进行FFT运算的解释。请注意FFT是如何进行两次数据复制,并且进行粘合,直到你得到一个元素。

现在,我们把所有部分组合起来,看看整件事情是如何:def mk_mimc_proof(inp, steps, round_constants),它生成运行 MIMC 函数的执行结果的证明,其中给定的输入为步骤数。首先,是一些 assert 函数:

# Calculate the set of x coordinates
xs = get_power_cycle(root_of_unity, modulus)

column = []
for i in range(len(xs)//4):
    x_poly = f.lagrange_interp_4( 
        [xs[i+len(xs)*j//4] for j in range(4)],
        [values[i+len(values)*j//4] for j in range(4)],
    )
    column.append(f.eval_poly_at(x_poly, special_x))

扩展因子是我们将要拉伸的计算轨迹(执行 MIMC 函数的“中间值”的集合)。

m2 = merkelize(column)

# Pseudo-randomly select y indices to sample
# (m2[1] is the Merkle root of the column)
ys = get_pseudorandom_indices(m2[1], len(column), 40)

# Compute the Merkle branches for the values in the polynomial and the column
branches = []
for y in ys:
    branches.append([mk_branch(m2, y)] +
                    [mk_branch(m, y + (len(xs) // 4) * j) for j in range(4)])

我们需要步数乘以扩展因子最多为 2^32,因为当 k > 32 时,我们没有 2^k 次的单位根。

computational_trace_polynomial = inv_fft(computational_trace, modulus, subroot)
p_evaluations = fft(computational_trace_polynomial, modulus, root_of_unity)

我们首个计算会是得出计算轨迹;也就是说,所有的计算中间值,从输入到输出。

assert steps 

然后,我们会从将计算轨迹转换为多项式,在单位根 g (其中,g^steps = 1)的连续幂的轨迹上“放下”连续值,然后我们对更大的集合——即单位根 g2 的连续幂,其中 g2^steps * 8 = 1(注意 g2^8 = g)的多项式求值。

# Generate the computational trace
computational_trace = [inp]
for i in range(steps-1):
    computational_trace.append((computational_trace[-1]**3 + round_constants[i % len(round_constants)]) % modulus)
output = computational_trace[-1]

黑色: g1 的幂。紫色: g2 的幂。橙色:1。你可以将连续的单位根看作一个按这种方式排列的圆圈。我们沿着 g1的幂“放置”计算轨迹,然后扩展它来计算在中间值处(即 g2 的幂)的相同多项式的值。

我们可以将MIMC的循环常数转换为多项式。因为这些循环常数链是非常通常发生地(在我们的测试中,每64个步骤都会进行),最终证明他们形成了64阶的多项式,而且外面可以很容易计算出它的表达式,以及扩展式:

skips2 = steps // len(round_constants)
constants_mini_polynomial = fft(round_constants, modulus, f.exp(subroot, skips2), inv=True)
constants_polynomial = [0 if i % skips2 else constants_mini_polynomial[i//skips2] for i in range(steps)]
constants_mini_extension = fft(constants_mini_polynomial, modulus, f.exp(root_of_unity, skips2))

假设其中有8192个步骤,并且有64个循环常数。这是我们想要做的:我们正在进行FFT,从而计算循环常数来作为g1128 的功能。然后我们在之间加入很多零,来完成g1本身的功能。因为g1128 大约每64步进行循环,我们知道g1这个功能也会同样。我们只计算这个扩展中的512个步骤,因为我们知道这个扩展会在每512步之后重复。现在,我们按照斐波那契案例中那样,计算C(P(x)),除了这次是计算,需要注意,我们不在计算使用系数形式的多项式;而是根据高次单位根的连续幂来对多项式进行求值。

c_of_p需要满足Q(x) = C(P(x), P(g1*x),K(x)) = P(g1*x) – P(x)**3 – K(x);目标是对于任何我们放入计算轨道的x(除了最后一步,因为在最后一步之后,就没有步骤),计算轨迹中的下个数值就和之前的相等,再加上循环常量。与第1部分中的斐波那契示例不同,其中如果某个计算步骤是在k向量,下个就会是k+1向量,我们把低次单位根( g1 )的连续幂放下计算轨迹,所以如果某个计算步骤是在x = g1i ,下个步骤就会在g1i+1 = g1i * g1 = x * g1。因此,对于低阶单位根( g1 )的每一个幂,我们希望最终会是P(x*g1) = P(x)**3 + K(x),或者P(x*g1) – P(x)**3 – K(x) = Q(x) = 0。因此,Q(x) 会在低次单位根 g 的所有连续幂上等于零(除了最后一个)。

# Create the composed polynomial such that
# C(P(x), P(g1*x), K(x)) = P(g1*x) - P(x)**3 - K(x)
c_of_p_evaluations = [(p_evaluations[(i+extension_factor)%precision] -
                          f.exp(p_evaluations[i], 3) -
                          constants_mini_extension[i % len(constants_mini_extension)])
                      % modulus for i in range(precision)]
print('Computed C(P, K) polynomial')

有个代数定理证明,如果Q(x)在所有这些x坐标,都等于零,那么最小多项式的乘积就会在所有这些x坐标等于零:Z(x) = (x – x_1) * (x – x_2) * … * (x – x_n)。通过证明在任何单个的坐标,Q(x)是等于零,我们想要证明这个很难,因为验证这样的证明比运行原始计算需要耗费更长的时间,我们会使用一个间接的方式来证明Q(x)是Z(x)的乘积。并且我们会怎么做呢?通过证明D(x) = Q(x) / Z(x),并且使用FRI来证明它其实是个多项式,而不是个分数。

我们选择低次单位根和高次单位根的特定排列,因为事实证明,计算Z(x),而且除以Z(x)也十分简单:Z 的表达式是两项的一部分。

需要注意地是,直接计算Z的分子和分母,然后使用批量模逆的方法将除以Z转换为乘法,随后通过 Z(X) 的逆来逐点乘以 Q(x) 的值。需要注意,对于低次单位根的幂,除了最后一个,都可以得到Z(x) = 0,所以这个计算包含其逆计算就会中断。这是非常不幸的,虽然我们会通过简单地修改随机检查和FRI算法来堵住这个漏洞,所以就算我们计算错误,也没关系。

因为Z(x)可以简洁地表达,我们也可以获得另个好处:验证者对于任何特别的x,可以快速计算Z(x),而且还不需要任何提前计算。对于证明者来说,我们可以接受证明者必须处理大小等于步数的多项式,但我们不想让验证者做同样的事情,因为我们希望验证过程足够简洁。

# Compute D(x) = Q(x) / Z(x)
# Z(x) = (x^steps - 1) / (x - x_atlast_step)
z_num_evaluations = [xs[(i * steps) % precision] - 1 for i in range(precision)]
z_num_inv = f.multi_inv(z_num_evaluations)
z_den_evaluations = [xs[i] - last_step_position for i in range(precision)]
d_evaluations = [cp * zd * zni % modulus for cp, zd, zni in zip(c_of_p_evaluations, z_den_evaluations, z_num_inv)]
print('Computed D polynomial')

在几个随机点上,进行概念检测D(x) * Z(x) = Q(x),从而可以验证转账约束,每个计算步骤是之前步骤的有效结果。但是我们也想验证边界约束,其中计算的输入和输出就是证明者所说的那样。只是要求证明者提供P(1), D(1), P(last_step)还有D(last_step)的数值,这些都是很脆弱的;没有证明,那些数值都是在同个多项式。所以,我们使用类似的多项式除法技巧:

# Compute interpolant of ((1, input), (x_atlast_step, output))
interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output])
i_evaluations = [f.eval_poly_at(interpolant, x) for x in xs]

zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1])
inv_z2_evaluations = f.multi_inv([f.eval_poly_at(quotient, x) for x in xs])

# B = (P - I) / Z2
b_evaluations = [((p - i) * invq) % modulus for p, i, invq in zip(p_evaluations, i_evaluations, inv_z2_evaluations)]
print('Computed B polynomial')

那么,我们的论证如下。证明者想要证明P(1) == input和P(last_step) == output。如果我们将I(x)作为插值,那么就是穿越(1, input)和(last_step, output)亮点的线,于是P(x) – I(x)就会在这亮点上等于零。因此,它会证明P(x) – I(x)是P(x) – I(x)的乘积,并且我们通过提高商数来证明这点。

紫色:计算轨迹多项式 (P) 。绿色:插值 (I)(注意插值是如何构造的,其在 x = 1 处等于输入(应该是计算轨迹的第一步),在 x=g^(steps-1) 处等于输出(应该是计算轨迹的最后一步)。红色:P-I。黄色:在x = 1和 x=g^(steps-1)(即 Z2)处等于 0 的最小多项式。粉红色:(P – I) / Z2。

现在,我们来看看将P,D和B的默克尔根部组合在一起。

现在,我们需要证明P,D和B其实都是多项式,并且是最大的正确阶数。但是FRI证明是很大且昂贵的,而且我们不想有三个FRI证明,所以,我们计算 P,D 和 B 的伪随机线性组合,并且基于它来进行FRI证明:

# Compute their Merkle roots
mtree = merkelize([pval.to_bytes(32, 'big') +
                   dval.to_bytes(32, 'big') +
                   bval.to_bytes(32, 'big') for
                   pval, dval, bval in zip(p_evaluations, d_evaluations, b_evaluations)])
print('Computed hash root')

除非所有这三个多项式有正确的低阶,不然几乎不可能有随机选择的线性组合,所以这很足够。

我们想要证明D的阶数小于2 * steps,而且P 和 B 的次数小于steps,所以我们其实使用了随机的P, P * xsteps, B, Bsteps 和 D的随机组合,并且可以看出这部分组合是小于2 * steps。

现在,我们来检查下所有的多项式组合。我们先获得很多随机的索引,然后在这些索引上为默克尔树枝提供多项式:

k1 = int.from_bytes(blake(mtree[1] + b'\x01'), 'big')
k2 = int.from_bytes(blake(mtree[1] + b'\x02'), 'big')
k3 = int.from_bytes(blake(mtree[1] + b'\x03'), 'big')
k4 = int.from_bytes(blake(mtree[1] + b'\x04'), 'big')

# Compute the linear combination. We don't even bother calculating it
# in coefficient form; we just compute the evaluations
root_of_unity_to_the_steps = f.exp(root_of_unity, steps)
powers = [1]
for i in range(1, precision):
    powers.append(powers[-1] * root_of_unity_to_the_steps % modulus)

l_evaluations = [(d_evaluations[i] +
                  p_evaluations[i] * k1 + p_evaluations[i] * k2 * powers[i] +
                  b_evaluations[i] * k3 + b_evaluations[i] * powers[i] * k4) % modulus
                  for i in range(precision)]

get_pseudorandom_indices函数会回复[0…precision-1]范围中的随机索引,而且exclude_multiples_of参数并不会给出特定参数倍数的值。这就保证了,我们不会沿着原始计算轨迹进行采样,否则就会获得错误的答案。

证明是由一组默克尔根、经过抽查的分支以及随机线性组合的低次证明组成:

# Do some spot checks of the Merkle tree at pseudo-random coordinates, excluding
# multiples of `extension_factor`
branches = []
samples = spot_check_security_factor
positions = get_pseudorandom_indices(l_mtree[1], precision, samples,
                                     exclude_multiples_of=extension_factor)
for pos in positions:
    branches.append(mk_branch(mtree, pos))
    branches.append(mk_branch(mtree, (pos + skips) % precision))
    branches.append(mk_branch(l_mtree, pos))
print('Computed %d spot checks' % samples)

整个证明最长的部分是默克尔树分支,还有FRI证明,这是有更多分支来组成的。这是验证者的实质结果:

o = [mtree[1],
     l_mtree[1],
     branches,
     prove_low_degree(l_evaluations, root_of_unity, steps * 2, modulus, exclude_multiples_of=extension_factor)]

在每个位置,证明者需要提供一个默克尔证明,从而让验证者能够检查这个默克尔证明,并且检查C(P(x), P(g1*x), K(x)) = Z(x) * D(x)以及B(x) * Z2(x) + I(x) = P(x)(提醒:对于不在初始计算轨道上的x,Z(x)不会是零,所以C(P(x), P(g1*x), K(x)也不会是零)。验证者也会检查线性组合是正确的,然后调用。

for i, pos in enumerate(positions):
    x = f.exp(G2, pos)
    x_to_the_steps = f.exp(x, steps)
    mbranch1 =  verify_branch(m_root, pos, branches[i*3])
    mbranch2 =  verify_branch(m_root, (pos+skips)%precision, branches[i*3+1])
    l_of_x = verify_branch(l_root, pos, branches[i*3 + 2], output_as_int=True)

    p_of_x = int.from_bytes(mbranch1[:32], 'big')
    p_of_g1x = int.from_bytes(mbranch2[:32], 'big')
    d_of_x = int.from_bytes(mbranch1[32:64], 'big')
    b_of_x = int.from_bytes(mbranch1[64:], 'big')

    zvalue = f.div(f.exp(x, steps) - 1,
                   x - last_step_position)
    k_of_x = f.eval_poly_at(constants_mini_polynomial, f.exp(x, skips2))

    # Check transition constraints Q(x) = Z(x) * D(x)
    assert (p_of_g1x - p_of_x ** 3 - k_of_x - zvalue * d_of_x) % modulus == 0

    # Check boundary constraints B(x) * Z2(x) + I(x) = P(x)
    interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output])
    zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1])
    assert (p_of_x - b_of_x * f.eval_poly_at(zeropoly2, x) -
            f.eval_poly_at(interpolant, x)) % modulus == 0

    # Check correctness of the linear combination
    assert (l_of_x - d_of_x -
            k1 * p_of_x - k2 * p_of_x * x_to_the_steps -
            k3 * b_of_x - k4 * b_of_x * x_to_the_steps) % modulus == 0

其实还没有完成成功;证明对跨多项式检查和 FRI 所需的抽查次数的可靠性分析是非常棘手的。但是这些就是所有代码,至少你不用担心进行疯狂的优化。当我运行以上代码的时候,我们会获得STARK证明,会有300-400倍的证明成本例如,一个需要 0.2 秒的 MIMC 计算需要 60 秒来证明)。这就使得4核机器计算MIMC中的 STARK,实际上可以比后向计算 MIMC 更快。也就是说,在python语言,这会相对低效的实现,并且这也会证明运行时间比例会不同。同时,也值得指出,MIMC 的 STARK 证明成本非常低,因为MIMC几乎是完美地可计算,它的数学形式很简单。对于平均计算,会包含更少的清晰计算(例如,检查一个数是大于还是小于另一个),其计算成本可能会更高,会有大约10000-50000倍。