TMT观察网_独特视角观察TMT行业

STARKs（可擴(kuò)容的透明知識(shí)論證）是創(chuàng)建一種證明的技術(shù)，這項(xiàng)證明中f(x)=y，其中f可能要花很長(zhǎng)的時(shí)間來(lái)進(jìn)行計(jì)算，但是這個(gè)證明可以被很快驗(yàn)證。STARK是“雙重?cái)U(kuò)容”：對(duì)于一個(gè)需要t步驟的計(jì)算，這會(huì)花費(fèi)大約O(t * log(t))步驟才能完成這個(gè)證明，這可能是最優(yōu)的情況，而且這需要通過(guò)~O(log2(t))個(gè)步驟才能驗(yàn)證，對(duì)于中等大小的T值，它比原始計(jì)算快得多。STARKs也擁有隱私保護(hù)的“零知識(shí)證明”的特性，雖然我們將這類使用案例應(yīng)用到其中，從而完成可驗(yàn)證的延遲功能，不需要這類性質(zhì)，所以我們不用擔(dān)心。

首先，先請(qǐng)幾項(xiàng)說(shuō)明：
這個(gè)代碼還沒(méi)有完全審核；在實(shí)際使用案例中的情況，還不能保證
這部分代碼是還沒(méi)有達(dá)到理想狀態(tài)（是用Python語(yǔ)言寫的）
STARKs 的“真實(shí)情況” 傾向于使用二進(jìn)制字段而不是素?cái)?shù)域的特定應(yīng)用程序效率的原因；但是，他們確實(shí)也表現(xiàn)出，這里寫出的代碼是合法并且可用的。
沒(méi)有一個(gè)真實(shí)的方法來(lái)使用STARK。它是一個(gè)非常寬泛的加密和數(shù)學(xué)架構(gòu)，同時(shí)為不同的應(yīng)用有不同的設(shè)置，以及連續(xù)的研究來(lái)減少證明者和驗(yàn)證者的復(fù)雜性，同時(shí)提高可用性。
此文希望大家能夠知道，模運(yùn)算和素?cái)?shù)域是如何運(yùn)行的，
并且和多項(xiàng)式概念，插值和估值進(jìn)行結(jié)合。
現(xiàn)在，讓我們一起來(lái)了解吧！

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作為案例，因?yàn)樗╥）很容易理解，（ii）在真實(shí)世界使用的很多。函數(shù)功能見(jiàn)下圖：

注意：在很多關(guān)于MIMC的討論中，你可以典型地看出使用了XOR，而不是 ；這是因?yàn)镸IMC可以在二進(jìn)制情況下使用，其中添加是XOR；這里我們會(huì)在素?cái)?shù)領(lǐng)域進(jìn)行。

在我們的案例中，常數(shù)相對(duì)而言會(huì)是比較小的列表（例如，64位），這會(huì)一直連續(xù)地進(jìn)行周期循環(huán)（也就說(shuō)，在k[64]之后）。MIMC自身可以獲得這個(gè)特性，因?yàn)镸IMC可以向后進(jìn)行計(jì)算（從相應(yīng)的輸出獲得輸入），但是往后計(jì)算需要比向前計(jì)算多花費(fèi)100倍的時(shí)間（并且沒(méi)有方向可以同步進(jìn)行）。所以你可以將往后計(jì)算的功能想象成計(jì)算不能同步的工作量證明，并且往前方向計(jì)算的功能可以作為驗(yàn)證的過(guò)程。

x -> x(2p-1)/3 是x -> x3 的反函數(shù)；根據(jù)費(fèi)馬小定理，這是真實(shí)的，盡管這個(gè)定理沒(méi)有費(fèi)馬大定理出名，但是依然對(duì)數(shù)學(xué)的貢獻(xiàn)很大。

我們嘗試使用STARK來(lái)進(jìn)行更加有效的驗(yàn)證，而不是讓驗(yàn)證者必須在向前方向運(yùn)行MIMC，在完成向后計(jì)算之后，證明者可以在向前方向進(jìn)行STARK計(jì)算，并且驗(yàn)證者可以很簡(jiǎn)單地驗(yàn)證STARK。我們希望計(jì)算STARK可以比MIMC向前和向后之間的運(yùn)行速度差別要小，所以證明者的時(shí)間仍然是有初始的向后計(jì)算來(lái)主導(dǎo)的。而并不是STARK計(jì)算。STARK的認(rèn)證會(huì)相對(duì)較快（在python語(yǔ)言算法中，可以是0.05-0.3秒），不論初始的計(jì)算時(shí)間有多長(zhǎng)。
所有的計(jì)算會(huì)在2256 – 351 * 232 1個(gè)模內(nèi)完成；我們使用素?cái)?shù)模，因?yàn)樗切∮?256 最大的素?cái)?shù)，其中乘法群包含了232 個(gè)子集（也就是說(shuō)，有這樣一個(gè)數(shù)g，從而在完全232次循環(huán)之后，G素?cái)?shù)環(huán)的連續(xù)冪模繞回到1），而且是按照6k 5的形式。首個(gè)特性是保證FFT和FRI算法的有效版本，其次是保證MIMC實(shí)際上可以向后計(jì)算（請(qǐng)見(jiàn)上面提到的x -> x(2p-1)/3 使用方法）。

素域操作

我們通過(guò)建立方便的等級(jí)來(lái)進(jìn)行素域的操作，同時(shí)也有多項(xiàng)式的操作。代碼如下，收首先是小數(shù)位數(shù)：

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

并且使用擴(kuò)展歐幾里得算法，來(lái)計(jì)算模塊逆轉(zhuǎn)（這和在素域中計(jì)算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

上面的算法是相對(duì)昂貴的；幸運(yùn)地是，對(duì)于特定的案例，我們需要做很多的模逆計(jì)算，有一個(gè)數(shù)學(xué)方法可以讓我們來(lái)計(jì)算很多逆運(yùn)算，被稱為蒙哥馬利批量求逆：

使用蒙哥馬利批量求逆來(lái)計(jì)算模逆，其輸入為紫色，輸出為綠色，乘法門為黑色，紅色方塊是唯一的模逆。

下面的代碼是算法的體現(xiàn)，其中包含一些特別的邏輯。如果我們正在求逆的集合中包含零，那么它會(huì)將這些零的逆設(shè)置為 0 并繼續(xù)前進(jìn)。

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

這部分算法接下來(lái)會(huì)驗(yàn)證稱為非常重要的東西，特別是當(dāng)我們開(kāi)始和不同階的多項(xiàng)式進(jìn)行計(jì)算的時(shí)候。
現(xiàn)在我們來(lái)看看一些多項(xiàng)式計(jì)算。我們把多項(xiàng)式當(dāng)做一個(gè)數(shù)據(jù)集，其中的i是第i階（例如，x3 2x 1變成[1, 2, 0, 1]）。下面就是在一個(gè)點(diǎn)進(jìn)行多項(xiàng)式估算的方法：

# 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

困難和挑戰(zhàn)

f.eval_poly_at([4, 5, 6], 2)的輸出是多少？模是31嗎？

下面的解釋就是答案

.其實(shí)也有代碼是多項(xiàng)式加法，減法，乘法和除法；這是很長(zhǎng)的加減乘除運(yùn)算。有一個(gè)很重要的內(nèi)容是拉格朗日插值，它將一組 x 和 y 坐標(biāo)作為輸入，并返回通過(guò)所有這些點(diǎn)的最小多項(xiàng)式（你可以將其視為多項(xiàng)式求值的逆）：

# 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]

相關(guān)數(shù)學(xué)知識(shí)請(qǐng)參見(jiàn)此文的M-N部分。需要注意，我們也會(huì)有特別的方法lagrange_interp_4和lagrange_interp_2來(lái)加速次數(shù)小于 2 的拉格朗日插值和次數(shù)小于 4 的多項(xiàng)式運(yùn)算。

快速傅立葉變換

如果你仔細(xì)閱讀上面的算法，你也許會(huì)發(fā)現(xiàn)拉格朗日插值和多點(diǎn)求值（即求在N個(gè)點(diǎn)處次數(shù)小于N的多項(xiàng)式的值）都需要耗費(fèi)2次時(shí)間，例如對(duì)于1000個(gè)點(diǎn)求拉格朗日插值，需要幾百萬(wàn)個(gè)步驟，而且100萬(wàn)個(gè)點(diǎn)的拉格朗日插值需要萬(wàn)億個(gè)步驟。這是不可接受的低效率，所以我們需要使用更加有效的算法，快速傅立葉變換。

FFT只需要花費(fèi)O(n * log(n))的時(shí)間（也就是說(shuō)，1000個(gè)點(diǎn)的計(jì)算需要10,000步，100萬(wàn)個(gè)點(diǎn)的計(jì)算需要2000步），雖然它的范圍更受限制；x坐標(biāo)必須是單位根部的完全集合，必須滿足N = 2k 階。也就是說(shuō)，如果有N個(gè)點(diǎn)，那么x坐標(biāo)必須某個(gè)P值的連續(xù)冪，1, p, p2, p3…，其中pN = 1。這個(gè)算法能夠用來(lái)進(jìn)行多點(diǎn)計(jì)算和插值計(jì)算，而且只需要調(diào)整一個(gè)小參數(shù)。

下面就是算法詳情（這是個(gè)簡(jiǎn)單的表達(dá)方式；更詳細(xì)內(nèi)容可以參閱此處代碼）

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))]

你可以自己通過(guò)一些輸入來(lái)運(yùn)行代碼，并且看看是否能得到想要的結(jié)果，當(dāng)你使用eval_poly_at的時(shí)候，給出你期望得到的答案。例如：

>>> 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]

傅里葉變換會(huì)把[x[0] …. x[n-1]]作為輸入，并且它的目標(biāo)是輸出x[0] x[1] … x[n-1]作為首個(gè)元素，x[0] x[1] * 2 … x[n-1] * w**(n-1)作為第二個(gè)元素，等等；快速傅里葉變換可以通過(guò)把數(shù)據(jù)分為兩半，來(lái)完成這個(gè)，在兩邊都進(jìn)行FFT，然后將結(jié)果結(jié)合在一起。

上圖就是信息如何進(jìn)行FFT運(yùn)算的解釋。請(qǐng)注意FFT是如何進(jìn)行兩次數(shù)據(jù)復(fù)制，并且進(jìn)行粘合，直到你得到一個(gè)元素。

現(xiàn)在，我們把所有部分組合起來(lái)，看看整件事情是如何：def mk_mimc_proof(inp, steps, round_constants)，它生成運(yùn)行 MIMC 函數(shù)的執(zhí)行結(jié)果的證明，其中給定的輸入為步驟數(shù)。首先，是一些 assert 函數(shù)：

# 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))

擴(kuò)展因子是我們將要拉伸的計(jì)算軌跡（執(zhí)行 MIMC 函數(shù)的“中間值”的集合）。

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)])

我們需要步數(shù)乘以擴(kuò)展因子最多為 2^32，因?yàn)楫?dāng) k > 32 時(shí)，我們沒(méi)有 2^k 次的單位根。

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

我們首個(gè)計(jì)算會(huì)是得出計(jì)算軌跡；也就是說(shuō)，所有的計(jì)算中間值，從輸入到輸出。

assert steps <= 2**32 // extension_factor
assert is_a_power_of_2(steps) and is_a_power_of_2(len(round_constants))
assert len(round_constants) < steps

然后，我們會(huì)從將計(jì)算軌跡轉(zhuǎn)換為多項(xiàng)式，在單位根 g （其中，g^steps = 1）的連續(xù)冪的軌跡上“放下”連續(xù)值，然后我們對(duì)更大的集合——即單位根 g2 的連續(xù)冪，其中 g2^steps * 8 = 1（注意 g2^8 = g）的多項(xiàng)式求值。

# 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。你可以將連續(xù)的單位根看作一個(gè)按這種方式排列的圓圈。我們沿著 g1的冪“放置”計(jì)算軌跡，然后擴(kuò)展它來(lái)計(jì)算在中間值處（即 g2 的冪）的相同多項(xiàng)式的值。

我們可以將MIMC的循環(huán)常數(shù)轉(zhuǎn)換為多項(xiàng)式。因?yàn)檫@些循環(huán)常數(shù)鏈?zhǔn)欠浅Ｍǔ０l(fā)生地（在我們的測(cè)試中，每64個(gè)步驟都會(huì)進(jìn)行），最終證明他們形成了64階的多項(xiàng)式，而且外面可以很容易計(jì)算出它的表達(dá)式，以及擴(kuò)展式：

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))

假設(shè)其中有8192個(gè)步驟，并且有64個(gè)循環(huán)常數(shù)。這是我們想要做的：我們正在進(jìn)行FFT，從而計(jì)算循環(huán)常數(shù)來(lái)作為g1128 的功能。然后我們?cè)谥g加入很多零，來(lái)完成g1本身的功能。因?yàn)間1128 大約每64步進(jìn)行循環(huán)，我們知道g1這個(gè)功能也會(huì)同樣。我們只計(jì)算這個(gè)擴(kuò)展中的512個(gè)步驟，因?yàn)槲覀冎肋@個(gè)擴(kuò)展會(huì)在每512步之后重復(fù)。現(xiàn)在，我們按照斐波那契案例中那樣，計(jì)算C(P(x))，除了這次是計(jì)算，需要注意，我們不在計(jì)算使用系數(shù)形式的多項(xiàng)式；而是根據(jù)高次單位根的連續(xù)冪來(lái)對(duì)多項(xiàng)式進(jìn)行求值。

c_of_p需要滿足Q(x) = C(P(x), P(g1*x)，K(x)) = P(g1*x) – P(x)**3 – K(x)；目標(biāo)是對(duì)于任何我們放入計(jì)算軌道的x（除了最后一步，因?yàn)樵谧詈笠徊街螅蜎](méi)有步驟），計(jì)算軌跡中的下個(gè)數(shù)值就和之前的相等，再加上循環(huán)常量。與第1部分中的斐波那契示例不同，其中如果某個(gè)計(jì)算步驟是在k向量，下個(gè)就會(huì)是k 1向量，我們把低次單位根（ g1 ）的連續(xù)冪放下計(jì)算軌跡，所以如果某個(gè)計(jì)算步驟是在x = g1i ，下個(gè)步驟就會(huì)在g1i 1 = g1i * g1 = x * g1。因此，對(duì)于低階單位根（ g1 ）的每一個(gè)冪，我們希望最終會(huì)是P(x*g1) = P(x)**3 K(x)，或者P(x*g1) – P(x)**3 – K(x) = Q(x) = 0。因此，Q(x) 會(huì)在低次單位根 g 的所有連續(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')

有個(gè)代數(shù)定理證明，如果Q(x)在所有這些x坐標(biāo)，都等于零，那么最小多項(xiàng)式的乘積就會(huì)在所有這些x坐標(biāo)等于零：Z(x) = (x – x_1) * (x – x_2) * … * (x – x_n)。通過(guò)證明在任何單個(gè)的坐標(biāo)，Q(x)是等于零，我們想要證明這個(gè)很難，因?yàn)轵?yàn)證這樣的證明比運(yùn)行原始計(jì)算需要耗費(fèi)更長(zhǎng)的時(shí)間，我們會(huì)使用一個(gè)間接的方式來(lái)證明Q(x)是Z(x)的乘積。并且我們會(huì)怎么做呢？通過(guò)證明D(x) = Q(x) / Z(x)，并且使用FRI來(lái)證明它其實(shí)是個(gè)多項(xiàng)式，而不是個(gè)分?jǐn)?shù)。

我們選擇低次單位根和高次單位根的特定排列，因?yàn)槭聦?shí)證明，計(jì)算Z(x)，而且除以Z(x)也十分簡(jiǎn)單：Z 的表達(dá)式是兩項(xiàng)的一部分。

需要注意地是，直接計(jì)算Z的分子和分母，然后使用批量模逆的方法將除以Z轉(zhuǎn)換為乘法，隨后通過(guò) Z(X) 的逆來(lái)逐點(diǎn)乘以 Q(x) 的值。需要注意，對(duì)于低次單位根的冪，除了最后一個(gè)，都可以得到Z(x) = 0，所以這個(gè)計(jì)算包含其逆計(jì)算就會(huì)中斷。這是非常不幸的，雖然我們會(huì)通過(guò)簡(jiǎn)單地修改隨機(jī)檢查和FRI算法來(lái)堵住這個(gè)漏洞，所以就算我們計(jì)算錯(cuò)誤，也沒(méi)關(guān)系。

因?yàn)閆(x)可以簡(jiǎn)潔地表達(dá)，我們也可以獲得另個(gè)好處：驗(yàn)證者對(duì)于任何特別的x，可以快速計(jì)算Z(x)，而且還不需要任何提前計(jì)算。對(duì)于證明者來(lái)說(shuō)，我們可以接受證明者必須處理大小等于步數(shù)的多項(xiàng)式，但我們不想讓驗(yàn)證者做同樣的事情，因?yàn)槲覀兿Ｍ?yàn)證過(guò)程足夠簡(jiǎn)潔。

# 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')

在幾個(gè)隨機(jī)點(diǎn)上，進(jìn)行概念檢測(cè)D(x) * Z(x) = Q(x)，從而可以驗(yàn)證轉(zhuǎn)賬約束，每個(gè)計(jì)算步驟是之前步驟的有效結(jié)果。但是我們也想驗(yàn)證邊界約束，其中計(jì)算的輸入和輸出就是證明者所說(shuō)的那樣。只是要求證明者提供P(1), D(1), P(last_step)還有D(last_step)的數(shù)值，這些都是很脆弱的；沒(méi)有證明，那些數(shù)值都是在同個(gè)多項(xiàng)式。所以，我們使用類似的多項(xiàng)式除法技巧：

# 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)亮點(diǎn)的線，于是P(x) – I(x)就會(huì)在這亮點(diǎn)上等于零。因此，它會(huì)證明P(x) – I(x)是P(x) – I(x)的乘積，并且我們通過(guò)提高商數(shù)來(lái)證明這點(diǎn)。

紫色：計(jì)算軌跡多項(xiàng)式 (P) 。綠色：插值 (I)（注意插值是如何構(gòu)造的，其在 x = 1 處等于輸入（應(yīng)該是計(jì)算軌跡的第一步），在 x=g^(steps-1) 處等于輸出（應(yīng)該是計(jì)算軌跡的最后一步）。紅色：P-I。黃色：在x = 1和 x=g^(steps-1)（即 Z2）處等于 0 的最小多項(xiàng)式。粉紅色：(P – I) / Z2。

現(xiàn)在，我們來(lái)看看將P，D和B的默克爾根部組合在一起。

現(xiàn)在，我們需要證明P，D和B其實(shí)都是多項(xiàng)式，并且是最大的正確階數(shù)。但是FRI證明是很大且昂貴的，而且我們不想有三個(gè)FRI證明，所以，我們計(jì)算 P，D 和 B 的偽隨機(jī)線性組合，并且基于它來(lái)進(jìn)行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')

除非所有這三個(gè)多項(xiàng)式有正確的低階，不然幾乎不可能有隨機(jī)選擇的線性組合，所以這很足夠。

我們想要證明D的階數(shù)小于2 * steps，而且P 和 B 的次數(shù)小于steps，所以我們其實(shí)使用了隨機(jī)的P, P * xsteps, B, Bsteps 和 D的隨機(jī)組合，并且可以看出這部分組合是小于2 * steps。

現(xiàn)在，我們來(lái)檢查下所有的多項(xiàng)式組合。我們先獲得很多隨機(jī)的索引，然后在這些索引上為默克爾樹(shù)枝提供多項(xiàng)式：

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函數(shù)會(huì)回復(fù)[0…precision-1]范圍中的隨機(jī)索引，而且exclude_multiples_of參數(shù)并不會(huì)給出特定參數(shù)倍數(shù)的值。這就保證了，我們不會(huì)沿著原始計(jì)算軌跡進(jìn)行采樣，否則就會(huì)獲得錯(cuò)誤的答案。

證明是由一組默克爾根、經(jīng)過(guò)抽查的分支以及隨機(jī)線性組合的低次證明組成：

# 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)

整個(gè)證明最長(zhǎng)的部分是默克爾樹(shù)分支，還有FRI證明，這是有更多分支來(lái)組成的。這是驗(yàn)證者的實(shí)質(zhì)結(jié)果：

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

在每個(gè)位置，證明者需要提供一個(gè)默克爾證明，從而讓驗(yàn)證者能夠檢查這個(gè)默克爾證明，并且檢查C(P(x), P(g1*x), K(x)) = Z(x) * D(x)以及B(x) * Z2(x) I(x) = P(x)（提醒：對(duì)于不在初始計(jì)算軌道上的x，Z(x)不會(huì)是零，所以C(P(x), P(g1*x), K(x)也不會(huì)是零)。驗(yàn)證者也會(huì)檢查線性組合是正確的，然后調(diào)用。

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

其實(shí)還沒(méi)有完成成功；證明對(duì)跨多項(xiàng)式檢查和 FRI 所需的抽查次數(shù)的可靠性分析是非常棘手的。但是這些就是所有代碼，至少你不用擔(dān)心進(jìn)行瘋狂的優(yōu)化。當(dāng)我運(yùn)行以上代碼的時(shí)候，我們會(huì)獲得STARK證明，會(huì)有300-400倍的證明成本例如，一個(gè)需要 0.2 秒的 MIMC 計(jì)算需要 60 秒來(lái)證明）。這就使得4核機(jī)器計(jì)算MIMC中的 STARK，實(shí)際上可以比后向計(jì)算 MIMC 更快。也就是說(shuō)，在python語(yǔ)言，這會(huì)相對(duì)低效的實(shí)現(xiàn)，并且這也會(huì)證明運(yùn)行時(shí)間比例會(huì)不同。同時(shí)，也值得指出，MIMC 的 STARK 證明成本非常低，因?yàn)镸IMC幾乎是完美地可計(jì)算，它的數(shù)學(xué)形式很簡(jiǎn)單。對(duì)于平均計(jì)算，會(huì)包含更少的清晰計(jì)算（例如，檢查一個(gè)數(shù)是大于還是小于另一個(gè)），其計(jì)算成本可能會(huì)更高，會(huì)有大約10000-50000倍。