在本系列的上一篇文章中斧账，我們談到了二跋，如何能夠做出一些非常有意思且簡潔的計算證明，比如通過利用多項式復合和除法技術弹渔，證明你算出了第一百萬個斐波那契數(shù)。但是宏胯，它依托于一個非常重要的元素：給定一個集合羽嫡，里面有很多的點，你必須能夠證明集合里的大部分點都在同一個低次多項式上（譯者注：本文所譯的多項式度數(shù)或次數(shù)肩袍，皆對應 degree 一詞）杭棵。這個叫做“低次測試”的問題，可能是協(xié)議中最為復雜的部分了牛。
首先颜屠，再次回顧一下我們的問題。假設有一些點鹰祸，你聲稱它們都在同一個多項式上甫窟，并且該多項式的度少于 D（也就是說，如果度小于 2蛙婴，意味著這些點在同一直線粗井。如果度小于 3，意味著它們在同一直線或拋物線街图，等等）浇衬。而你想創(chuàng)建一個簡潔的概率證明，證明的確如此餐济。
如果你想要驗證，這些點全部都在同一個度小于 D 的多項式上絮姆，那么實際上你將不得不對每一個點進行檢查醉冤，因為哪怕是僅僅漏掉一個點，也可能會出現(xiàn)差錯：漏掉的這個點剛好不在這個多項式上篙悯，而其他點恰好都在上面蚁阳。不過，你可以做的是鸽照，在所有的這些點中螺捐，概率性地檢測至少有部分（比如 90%）點都在同一個多項式上。
如果你能夠檢查多項式上的每一個點糠悼，那么問題非常簡單。但是浅乔，如果你只能夠檢查幾個點呢？ -- 也就是說，你可以要求檢查任意幾個點靖苇，作為協(xié)議的一部分席噩，證明者也有義務給你這些點，但是查詢次數(shù)總數(shù)是有所限制的贤壁？那么問題來了悼枢，你需要檢查多少個點，才能在一定程度上進行確認脾拆？
顯然馒索，D 個點是不夠的。因為 D 個點恰好可以唯一定義一個度小于 D 的多項式名船，所以你得到的任意的點集合绰上，都只會與某個度小于 D 的多項式相關。從上圖可以看出渠驼，D+1 或更多的點蜈块，肯定可以給我們帶來更多信息。
給定一些值迷扇，通過 D+1 次查詢百揭，檢測這些值是否在同一個度小于 D 的多項式上，其算法其實并不十分復雜蜓席。首先器一，從 D 個點中隨機挑選一個子集，并用像拉格朗日插值法（在 這里 搜索 “Lagrange interpolation” 獲得更多介紹）來還原這個唯一的度小于 D 的多項式厨内，并且該多項式能夠通過這些所有的點祈秕。然后，隨機再采樣一個點隘庄，檢測該點是否在同一個多項式上踢步。
注意获印，這僅僅是一個臨近測試（proximity test），因為無可避免地會出現(xiàn)這樣一種情況街州，即雖然大部分點都在同一個低次多項式上兼丰，但卻有另外一些點不在該多項式上，而第 D+1 個采樣點恰好完全地錯過了這些點唆缴。不過鳍征，我們可以對結果進行派生，如果在同一個度小于 D 的多項式上的點低于 90%面徽，那么測試將很大可能失敗艳丛。具體來說匣掸，如果你進行 D+k 次查詢，有至少 p% 的點不在同一個多項式上氮双，而其他點卻在上面碰酝，那么通過測試的概率僅有 (1-p) ^k。
但是戴差，如果像上一篇文章的例子那樣送爸， D 非常大，而你想要在少于 D 次查詢的情況下暖释，驗證一個多項式的度袭厂，那該怎么辦呢？當然球匕，這不太可能直接“對癥下藥”纹磺， 因為上面已作出了簡單的論證（即，任意 k <= D 個點至少全部都在一個度小于 D 的多項式上）谐丢。但是爽航，通過提供輔助數(shù)據(jù)，間接地進行驗證還是非常有可能的乾忱，并且能夠獲得大幅地效率提升讥珍。這就是像 FRI（“Fast RS IOPP”，RS=“Reed-Solomon
”窄瘟， IOPP = “Interactive Oracle Proofs of Proximity”） 這樣的新協(xié)議想要做的事情衷佃，它與早先叫做近似概率可檢驗性證明（probabilistically checkable proofs of proximity (PCPPs) ）的設計相類似。
初識亞線性
為了證明這一切都是可行的蹄葱，我們從一個相對簡單的協(xié)議開始氏义，雖然有非常粗糙的折衷操作，但是仍然可以達到亞線性驗證復雜度的目的 -- 也就是說图云，你可以通過少于 D 次查詢惯悠，近似證明一個度小于 D 的多項式（在這里也就是，通過少于 O(D) 次計算來對證明進行驗證）竣况。
思路如下克婶。假設有 N 個點（比方說 N 等于 10 億），并且它們都在一個度小于 1,000,000 的多項式 f(x) 上丹泉。我們找到一個二元多項式（像 1 + x + xy + x^5*y^3 + x^12 + x*y^11 這樣的表達式）情萤，表示為 g(x, y)，并且 g(x, x^1000) = f(x)摹恨。通過如下操作即可完成：對于 f(x) 中第 k 度項（比如筋岛，1744 * x^185423），我們將它分解為 x^(k % 1000) * y^floor(k / 1000)（在該例中晒哄，1744 * x^423 * y^185）睁宰。你可以看到肪获，如果 y = x^1000，那么 1744 * x^423 * y^185 等于 1744 * x^185423勋陪。
在證明的第一階段贪磺，證明者提交在整個正方形上 [1..N] x {x^1000: 1 <= x <= N} 上 g(x, y) 的值（也就是說硫兰，求一個 Merkle 樹）-- 也就是诅愚，列上的所有 10 億個 x 坐標，以及所有 10 億個對應的行上 y 坐標的一千次劫映。正方形的對角線表示 g(x, y) 的值违孝，其形式為 g(x, x^1000)，因此關聯(lián)到 f(x) 的值泳赋。
然后雌桑，驗證者可能隨機選出幾十行和幾十列（如果我們想要一個非交互式的證明，可能使用 the Merkle root of the square as a source of pseudorandomness）祖今，對于所選的每一行或列校坑，比如說，驗證者要求從行和列的 1010 個點中采樣一個點千诬，以確保在每種情況下耍目，要求的點都在對角線上。證明者必須對這些點作出回應徐绑，通過 Merkle 分支邪驮，證明它們是給證明者提交原始數(shù)據(jù)的一部分。驗證者檢查 Merkle 分支的確相匹配傲茄，這表明證明者所提供的這些點確實與 1000 次多項式相關毅访。
這給了驗證者一個統(tǒng)計證明：
大部分行主要被度小于 1000 的多項式上的點所填充
大部分列主要被度小于 1000 的多項式上的點所填充
對角線大部分都在這些多項式上
因而，這使得驗證者相信在對角線上的大部分點盘榨，確實與一個次數(shù)小于 1,000,000 的多項式相關喻粹。
如果我們選出 30 行和 30 行列，驗證者需要檢測總共 1010 個點 * 60 行+列 = 60600 個點草巡，雖然少于原始的 1,000,000 個點守呜，但仍是差強人意。就計算時間而言捷犹，盡管由于多項式插值可以變?yōu)榇味危╯ubquadratic）弛饭，但對度小于 1000 的多項式進行插值，也有其自身的開銷萍歉，從整體上看侣颂，算法驗證仍是亞線性的。證明者的復雜度更高了：證明者需要計算并提交整個 NN 長方形枪孩，這總共是 10^18 的計算成本（實際上還要更多一點憔晒，因為多項式求值仍然是超線性（superlinear）的）藻肄。在所有的這些算法中，對計算進行證明拒担，遠比單單執(zhí)行該計算要復雜的多嘹屯，但是我們將會看到，其實這些開銷并非需要如此*地高从撼。
模塊化數(shù)學插曲
在深入到更復雜的協(xié)議之前州弟，我們需要稍微偏離下主題，討論一下模塊化數(shù)學（modular math）低零。通常婆翔，當面對代數(shù)表達式和多項式時，我們所面對的是使用的是 +,-,,/（還有求冪掏婶，不過它實際只是重復的乘法而已）這樣操作符的常規(guī)數(shù)字和運算啃奴，這些都是我們在學校里面就學會的知識：2 + 2 = 4, 72 / 5 = 14.4, 1001 * 1001 = 1002001 等等。但是雄妥，數(shù)學家們已經(jīng)意識到最蕾，這些定義加法，乘法老厌，減法和除法的方式瘟则，并不是唯一*定義這些操作符的自洽（self-consistent）方式。
定義這些操作符梅桩，另一種可替代也是最簡單的例子是壹粟，下面定義的模塊化數(shù)學。% 操作符代表“取余”宿百，15 % 7 = 1, 53 % 10 = 3, 等等（注意答案始終是非負的趁仙，比如 -1 % 10 = 9）。對于任意指定的素數(shù) p垦页，我們可以重新定義：
x + y ---> (x + y) % p
x * y ---> (x * y) % p
x ^ y ---> (x ^ y) % p
x - y ---> (x - y) % p
x / y ---> (x * y ^ (p-2)) % p
上面的例子都是自洽的雀费。比如，如果 p = 7, 那么：
- 5 + 3 = 1 (as 8 % 7 = 1)
- 1 - 3 = 5 (as -2 % 7 = 5)
- 2 * 5 = 3
- 3 / 5 = 2 (as (3 * 55) % 7 = 9375 % 7 = 2)
對于像分配律這樣更復雜的內容同樣成立： (2 + 4)3 和 2 * 3 + 4 * 3 都等于 4痊焊。在這種新的數(shù)學中盏袄，甚至像 (a2-b2)=(a-b)(a+b) 也仍然是成立的。除法是其中最困難的部分：我們無法使用常規(guī)除法薄啥，因為我們想要結果始終是整數(shù)辕羽，但是常規(guī)除法常常會得到非整數(shù)的結果（比如 3/5）。在上面的除法公式中垄惧，p-2 次冪是一個使用 費馬小定理 直面該問題的結果刁愿，它表示對于任意非零的 x < p，都有 x^(p-1)%p = 1.這表明 x^(p-2) 給出一個數(shù)到逊，如果再乘以一個 x铣口，得到 1滤钱，所以我們可以說 x^(p-2)（是一個整數(shù)）等于 1/x。對模塊化除法操作符求值脑题，一個有點更為復雜件缸，但是更快的方式是 擴展歐幾里得算法，其 Python 實現(xiàn)在 這里叔遂。
通過模塊化數(shù)學，我們已經(jīng)創(chuàng)立了一個全新的數(shù)學系統(tǒng)掏熬，因為它與傳統(tǒng)數(shù)學在各個方面都是自洽的佑稠，所以我們在模塊化數(shù)學里面討論各種同樣的結構，包括我們以“常規(guī)數(shù)學”論之的多項式旗芬。密碼學家喜歡用模塊化數(shù)學（或者，更通俗一點捆蜀，“有限域”）疮丛，因為一個數(shù)字的大小有界，它可以作為任意一個模塊化數(shù)學的計算結果 -- 無論你做什么辆它，值都不會“跳出” {0, 1, 2 ... p-1} 的范圍誊薄。
費馬小定理還有另一個有趣的結論。如果 p-1 是某個數(shù) k 的倍數(shù)锰茉，那么函數(shù) x -> x^k 有一個小的“像（image）” -- 也就是呢蔫，這個函數(shù)只能夠給出 (p-1)/k + 1 個可能的結果。比如飒筑， x -> x^2 在 p=17 時片吊，只有 9 個可能的結果。
指數(shù)越高协屡，效果越明顯：比如俏脊，x -> x^8 在 p = 17 時，只有 3 個可能的結果肤晓。當然爷贫， x -> x^16 在 p=17 是只有 2 個可能的結果。如果是 0补憾，返回 0漫萄，其他任何都返回 1.
淺談效率
讓我們來繼續(xù)討論一個稍微復雜點的協(xié)議，它的目標在于盈匾，將證明者的復雜度從 10^18 降至 10^15腾务，繼而降至 10^9。首先威酒，我們并不是針對常規(guī)數(shù)字進行操作窑睁，而是使用模塊化數(shù)學檢查多項式的近似程度挺峡。正如在上篇文章所述，在
STARKs 中担钮，我們無論如何都要防止數(shù)字增長至 200,000 位橱赠。但是在這里，我們將要利用確定的模冪（modular exponentiation）的“小像（small image）”屬性箫津，并將其視作為一個副作用狭姨，來使得我們的協(xié)議更有效率。
具體來說苏遥，我們將選用 p = 1,000,005,001饼拍。之所以選擇這個系數(shù)（modulus），是因為：
它比 10 億大田炭，因為我們需要它至少是 10 億师抄，這樣才能檢測 10 億個點。
它是質數(shù)
p-1 是 1000 的偶數(shù)倍教硫。
冪 x^1000 的像大小為 1,000,006 -- 也就是說叨吮，這個冪只有 1,000,006 個可能的結果。
這意味著“對角線”（x, x^1000） 現(xiàn)在變成了一個被包著（with a wraparound）的對角線瞬矩；因為 x^1000 只可以取 1,000,006 個可能值茶鉴，所以我們僅需要 1,000,006 行。故而景用，g(x, x^1000) 的所有取值現(xiàn)在只有 ~10^15 個元素涵叮。
這表明，我們可以更進一步地：讓證明者僅提交在一個單列上 g 的值伞插。關鍵技巧在于割粮，原始數(shù)據(jù)本身已經(jīng)包含了 1000 個點，而這些點在給定的任意行上蜂怎，所以我們可以簡單采樣這些點穆刻，推導出它們所在的度小于 1000 的多項式，然后檢查列上相關的點在同一個多項式上杠步。再接著檢查列本身是一個小于 1000 的多項式氢伟。
雖然驗證者復雜度仍然是亞線性的，但是證明者復雜度已經(jīng)降到了 10^9幽歼，并與查詢次數(shù)成線性關系（盡管在實踐中由于多項式求值的開銷朵锣，仍是超線性的）。
二談效率
雖然證明者復雜度現(xiàn)在已經(jīng)無法再低了甸私，但是我們仍然可以進一步地降低驗證者復雜度诚些，即從二次降至對數(shù)。我們的方法是讓算法遞歸。從上面談到的協(xié)議開始诬烹，但是并非試圖將一個多項式嵌入到一個 x 和 y 度相等的二維多項式中砸烦，我們將多項式嵌入到一個二維多項式中，該二維多項式的度 x 下界是一個小的常量值绞吁。簡單來說幢痘，我們甚至可以說就是 2 。也就是說家破，我們表示 f(x) = g(x, x^2)颜说，所以行檢驗僅需每個采樣行的 3 個點（2 個來自對角線，還有 1 個來自列）汰聋。
如果原始多項式的度小于 n门粪，那么行的度小于 2（也就是說，這些行是直線）烹困，列的度小于 n/2玄妈。因此，我們現(xiàn)在得到的是一個線性時間過程韭邓，它將證明一個度小于 n 的近似多項式問題轉變?yōu)樽C明度小于 n/2 的問題措近。進一步地，需要提交的點數(shù)女淑，和證明者的計算復雜度，每次會減少 1/2（Eli BenSasson 喜歡將 FRI 的這一點與fast fourier transforms 相比較辜御，與 FFT 不同的關鍵在于鸭你，每一步遞歸都只進入一個新的子問題，而不是將問題一分為二
）擒权。因此袱巨，我們可以簡單地繼續(xù)使用在上一輪協(xié)議所創(chuàng)建的列上的協(xié)議，直到列變得足夠小碳抄，小到我們可以簡單地直接檢查愉老。整體復雜度大概是 n + n/2 + n/4 + … ~= 2n.
實際上，協(xié)議將需要被重復多次剖效，因為仍有極大的可能嫉入，攻擊者會在協(xié)議的某一輪作弊。但是璧尸，只要證明不是太大咒林，驗證復雜度在量級上仍然是對數(shù)級，盡管它會上升到 log^2(n) 爷光，如果你把 Merkle 證明的大小也算進去的話垫竞。
“真正”的 FRI 協(xié)議也有一些其他的修改。比如蛀序，它使用一個二分的 Galois 域（另一種奇怪的有限域欢瞪。本質上活烙，與我在
這里 討論的第 12 度擴展域是同樣的東西，不過素數(shù)模是 2
）遣鼓。行所使用的指數(shù)通常是 4 而不是 2啸盏。這些修改提升了效率，并使系統(tǒng)更加友好譬正，在上面更易構建 STARKs宫补。但是，對于理解算法的工作原理曾我，這些修改并非十分必要粉怕。如果你真的想要理解算法的話，利用這里所述的基于模塊化數(shù)學的 FRI抒巢，雖然簡單了一點贫贝，但是應付 STARKs 絕對是夠了。
可靠性
我必須要提醒 計算可靠性（calculating soundness） -- 也就是蛉谜，無論概率有多低稚晚，對于給定次數(shù)的檢查，一個經(jīng)過優(yōu)化后的假證明型诚，仍可能會通過測試客燕。 -- 這依舊是這個領域中的“危險”地帶≌幔可以簡單測試一下也搓，取 1,000,000 + k 個點，有一個簡單的下界：如果一個給定的數(shù)據(jù)集有這樣一個屬性涵紊，對于任意多項式傍妒，數(shù)據(jù)集中至少有 p% 的點沒有在多項式上，那么在該數(shù)據(jù)集通過測試的概率將至多是(1-p)^k摸柄。但是颤练，即使下界很低 -- 比如，不可能同時有超過 50% 的點接近兩個低次多項式驱负，并且你首先選擇的點會是上面最多的點的概率相當?shù)袜戮痢τ谝粋€成熟的 FRI 來說，仍會涉及各種特定類型攻擊的復雜度电媳。
這里 是 Ben-Sasson 等人最近的一篇文章踏揣，里面在完整的 STARK fang'an背景下，介紹了 FRI 的可靠性屬性匾乓±谈澹總的來說，“好消息”是，為了在 STARK 上通過 D(x) * Z(x) = C(P(x)) 檢查娱局，一個無效方案的 D(x) 將需要是某種意義上的“最壞情況” - 他們需要最大化地遠離任意有效的多項式彰亥。這表明，我們不需要檢查那么近的距離衰齐。雖然有已證明的下界任斋，但是這些界限表明一個真正的 STARK 在大小上需要 ~1-3 MB；一個屬于推測尚未被證明的更嚴格界限耻涛，減少所需檢測次數(shù)的 1/4废酷。
本系列的第三部分，將討論構建 STARKs 的最后一個主要的挑戰(zhàn)：如何構建約束檢查多項式（constraint checking polynomial）抹缕，才能夠證明任意的計算語句澈蟆，而不僅僅是幾個斐波那契數(shù)。
