相信很多人都聽過 ZK-SNARKS，一個(gè)通用而簡潔的零知識證明技術(shù)，從可驗(yàn)證計(jì)算到需要隱私保護(hù)的加密貨幣拘鞋，它可以被應(yīng)用于各類場景。不過矢门，可能你還不知道現(xiàn)在 ZK-SNARKs 有了一個(gè)新兄弟：ZK-STARKs. 這里的 T 表示 “transparent”盆色，“透明的”，ZK-STARKs 解決了 ZK-SNARKs 的一個(gè)主要的缺點(diǎn)祟剔，即 ZK-SNARKs 依賴于“可信啟動（trusted setup）”隔躲。ZK-STARKs 也帶來了更加簡單的密碼學(xué)假設(shè)，避免了使用橢圓曲線物延，配對和指數(shù)知識的假設(shè)（the knowledge-of-exponent assumption）宣旱，并且完全地基于哈希和信息論。這也意味著叛薯，即使是面對使用量子計(jì)算機(jī)的攻擊者响鹃，它仍然是安全的。

當(dāng)然案训，這也是有代價(jià)的：一個(gè)證明的大小將從 288 字節(jié)（b）上升到幾百 千字節(jié)（kb）。盡管在某些情況下粪糙，這些代價(jià)可能并不十分劃得來强霎，不過在另一些場景下，尤其對于需要高度的信任最小化的區(qū)塊鏈應(yīng)用蓉冈，它可能是物有所值城舞。而一旦橢圓曲線被破解，或者量子計(jì)算機(jī)真的到來的話寞酿，那么它必然是非常值得的家夺。

那么，這種新的零知識證明到底是如何工作的呢伐弹？在這之前拉馋，先讓我們來回顧一下，簡潔通用的零知識證明做的是什么事情惨好。假設(shè)你現(xiàn)在有一個(gè)（公開煌茴，public）函數(shù) f趁蕊，一個(gè)（私有哀军，private）輸入 x凌停，和一個(gè)（公開计贰，public）輸入 y摔认。在不透露 x 是什么的情況下秀菱，你想要證明你知道有一個(gè) x 能夠使得 f(x) = y（譯者注：比如有一個(gè)保險(xiǎn)箱基显，你要在不透漏密碼具體是什么的情況下挑随，證明你確實(shí)知道這個(gè)保險(xiǎn)箱的密碼）。此外傀蓉，為了這個(gè)證明具有一定的簡潔性欧漱，相比于通過計(jì)算 f 本身，你希望它能夠通過一種更快的方式進(jìn)行驗(yàn)證僚害。

general-purpose ZKP

讓我們來討論幾個(gè)案例：

• f 是一個(gè)計(jì)算硫椰，它需要在一臺普通計(jì)算機(jī)上運(yùn)行兩周，但是一個(gè)數(shù)據(jù)中心只需要兩小時(shí)即可完成萨蚕。你可以把計(jì)算任務(wù)（也就是運(yùn)行 f 的代碼）發(fā)送給數(shù)據(jù)中心靶草，數(shù)據(jù)中心執(zhí)行計(jì)算，然后返回答案岳遥，也就是 y 證明奕翔。在幾毫秒之內(nèi)你就可以完成驗(yàn)證，并且可以確信 y 就是真實(shí)的答案浩蓉。

• 你有一筆經(jīng)過加密的交易派继，形式為 “X1 是我舊的余額。X2 是你舊的余額捻艳。X3 是我新的余額驾窟。X4 是你新的余額”。你想要構(gòu)建一個(gè)證明认轨，證明這筆交易是有效的（具體來說绅络，證明舊的和新的余額都是非負(fù)的，并且我的余額減少量剛好是你的余額增加量）嘁字。x 可能是一對加密密鑰恩急，f 可能是一個(gè)函數(shù)，這個(gè)函數(shù)包含了一個(gè)內(nèi)置公開輸入的交易纪蜒，輸入密鑰衷恭，解密交易，執(zhí)行檢查纯续，如果通過的話返回 1随珠，否則返回 0。y 必然是 1 了杆烁。

• 你有一個(gè)像以太坊一樣的區(qū)塊鏈牙丽，并下載了最新的塊。你想要構(gòu)造一個(gè)證明兔魂，證明這個(gè)塊是有效的烤芦，并且它是鏈上最新的塊，同時(shí)這個(gè)鏈里面的每個(gè)塊都是有效的析校。你向一個(gè)已知的全節(jié)點(diǎn)詢問來提供這樣一個(gè)證明构罗。x 是整個(gè)（全部铜涉？或者是部分）的區(qū)塊鏈，f 是一個(gè)按塊處理它的函數(shù)遂唧，驗(yàn)證有效性并輸出上一個(gè)塊的哈希芙代，而 y 就是你剛剛下載的塊哈希。

validate transaction

那么盖彭，對于所有這些案例纹烹，其困難之處在哪兒呢？事實(shí)證明召边，零知識（也就是隱私）保證是（相對Ｆ毯恰）容易提供的。有多種方式可以將任何計(jì)算轉(zhuǎn)換成一個(gè)類似三色圖問題的一種隧熙，圖的三著色與原始問題的解決方案有關(guān)片挂，然后在不透露具體方案的情況下，使用一個(gè)傳統(tǒng)的零知識證明協(xié)議贞盯，來證明你有一個(gè)有效的圖色方案音念。這篇來自 Matthew Green 2014 年很棒的文章 對其中細(xì)節(jié)做了闡釋。

更加困難的一件事情是 簡潔性躏敢。直觀來講闷愤，簡潔地證明計(jì)算相關(guān)的事情十分困難，因?yàn)橛?jì)算 極其脆弱件余。如果你有一個(gè)很長很復(fù)雜的計(jì)算肝谭，并且假設(shè)你有一種能夠在計(jì)算中間將任何一位（bit）從 0 變?yōu)?1 的能力，那么在很多情況下蛾扇，即使是僅僅改變其中某一位，也足夠使得計(jì)算產(chǎn)生一個(gè)完全不同的結(jié)果魏滚。因此镀首，很難看出如何才能通過一些手段判定其正確性，比如隨機(jī)采樣一個(gè)計(jì)算軌跡鼠次，因?yàn)榉浅Ｈ菀拙蜁e(cuò)過那“邪惡的一位（one evil bit）”更哄。不過，通過一些花哨的數(shù)學(xué)方法腥寇，可以證明其實(shí)你是可以做到的成翩。

一般高層次的直覺是協(xié)議可以實(shí)現(xiàn)這一點(diǎn)，類似 擦除編碼 中使用的數(shù)學(xué)赦役，它經(jīng)常被用于使得數(shù)據(jù)具有容錯(cuò)性麻敌。如果你有一些數(shù)據(jù)，并且將這些數(shù)據(jù)編碼為一條線掂摔，然后你可以從這條線上選出四個(gè)點(diǎn)术羔。這四個(gè)點(diǎn)中的任意兩個(gè)都可以重建這條線赢赊，因此也會給你另外兩個(gè)點(diǎn)。進(jìn)一步地级历，即使你對這些數(shù)據(jù)做出極微小的改變释移，然后保證這四個(gè)點(diǎn)的至少三個(gè)。你可以將這些數(shù)據(jù)編碼為一個(gè) 1,000,000 次多項(xiàng)式寥殖，然后在這個(gè)多項(xiàng)式上選出 2,000,000 個(gè)點(diǎn)玩讳，任意一個(gè) 1,000,001 個(gè)點(diǎn)都會恢復(fù)原始數(shù)據(jù)，繼而恢復(fù)其他點(diǎn)嚼贡，原始數(shù)據(jù)的任何一點(diǎn)偏離都會改變至少 1,000,000 個(gè)點(diǎn)熏纯。這里展示的算法，大量通過這個(gè)途徑利用了多項(xiàng)式來進(jìn)行錯(cuò)誤放大编曼。

algo

一個(gè)簡單的例子

假設(shè)豆巨，你想要證明你有一個(gè)多項(xiàng)式 P，對于從 1 到 1 百萬之間的所有 x掐场，P(x) 是一個(gè)整數(shù)且 0 <= P(x) <= 9往扔。這是十分常見的 “范圍檢查” 的一個(gè)簡單示例。你可以把這種檢查想象成某種驗(yàn)證熊户，比如萍膛，在執(zhí)行一些交易以后，一些賬戶余額仍然是正數(shù)嚷堡。如果 1 <= P(x) <= 9蝗罗，這就可能是檢測一個(gè)正確的數(shù)獨(dú)解的一部分。

證明這個(gè)問題的“傳統(tǒng)” 方法是蝌戒，遍歷所有的 1,000,000 點(diǎn)串塑，逐個(gè)對值進(jìn)行校驗(yàn)來進(jìn)行驗(yàn)證。但是北苟，我們想要知道是否我們能夠構(gòu)造一個(gè)證明桩匪，它可以在小于 1,000,000 步的情況下得到驗(yàn)證。簡單地隨機(jī)對 P 進(jìn)行求值校驗(yàn)無法做到這一點(diǎn)友鼻；總是有可能出現(xiàn)一個(gè)惡意證明者傻昙，他會想出一個(gè) P，這個(gè) P 滿足在 999,999 位置內(nèi)的限制彩扔，但是不滿足最后一個(gè)妆档，那么隨機(jī)采樣僅有的幾個(gè)值，將會總是錯(cuò)過那個(gè)正確的值虫碉。那么贾惦，我們可以做什么呢？

polynomial

讓我們從數(shù)學(xué)上對這個(gè)問題進(jìn)行一下轉(zhuǎn)化。讓 C(x) 為一個(gè) 約束檢查多項(xiàng)式（constraint checking polynomial）纤虽，如果 0 <= x <= 9乳绕，C(x) = 0 否則為非 0。構(gòu)造 C(x) 有一個(gè)簡單的方式： x * (x-1) * (x-2) * ... * (x-9)逼纸。

C(x)

現(xiàn)在洋措，問題變成了：證明你知道 P，對于從 1 到 1,000,000 的所有 x杰刽，都有 C(P(x)) = 0菠发。讓 Z(x) = (x-1) * (x-2) * ... (x-1000000)。這是一個(gè)已知的數(shù)學(xué)事實(shí)贺嫂，對于從 1 到 1,000,000 的所有 x滓鸠，任何等于零的多項(xiàng)式都是 Z(x) 的一個(gè)乘積。因而第喳，問題可以被再次轉(zhuǎn)化：對于所有的 x 糜俗，證明你知道 P 和 D, 滿足 C(P(x)) = Z(x) * D(x) （注意，如果你知道一個(gè)合適的 C(P(x))）曲饱，然后除以 Z(x) 來計(jì)算 D(x) 并不太難悠抹；你使用 多項(xiàng)式長除法 ，或基于 快速傅里葉變換 更具有實(shí)際意義更快的算法）±┑恚現(xiàn)在楔敌，我們已經(jīng)將原始命題轉(zhuǎn)化為一個(gè)看起來數(shù)學(xué)上更清晰，也更可證的一個(gè)問題驻谆。

那么卵凑，要如何證明呢？我們可以把證明過程想象成證明者和驗(yàn)證者之間一個(gè)三步的交流過程：

1. 證明者發(fā)送一些信息
2. 然后驗(yàn)證者發(fā)送一些請求
3. 然后證明者再發(fā)送一些信息

首先胜臊，證明者提交（也就是勺卢，生成一個(gè) Merkle 樹并且將根哈希發(fā)送給驗(yàn)證者）對于從 1 到 10 億（是的，10 億）之間的所有 x象对， P(x) 和 D(x) 的值. 這包含了 1 百萬個(gè)點(diǎn)值漫，而 0 <= P(x) <= 9 且 9.99 億個(gè)（可能）是狀況外的點(diǎn)。

我們假設(shè)驗(yàn)證者已經(jīng)知道了 Z(x) 在所有這些點(diǎn)上的值织盼；在這個(gè)方案中，Z(x) 就像是一個(gè) 公開驗(yàn)證密鑰酱塔，每個(gè)人都必須提前知道（客戶端沒有存儲 Z(x) 的空間沥邻，因?yàn)樗麄€(gè)可能只是簡單地存儲了 Z(x) 的 Merkle 根，并需要證明者同時(shí)提供驗(yàn)證者需要查詢的每個(gè) Z(x) 值的分支羊娃；又或者唐全，對于某個(gè) x ，有一些在 Z(x) 之上非常容易計(jì)算的數(shù)字）。在獲得提交（也就是 Merkle 根）后邮利，驗(yàn)證者在 1 和 10 億之間隨機(jī)選擇 16 個(gè) x 的值弥雹，并要求證明者提供這些值上 P(x) 和 D(x) 的 Merkle 分支。證明者提供這些值延届，驗(yàn)證者檢查：

1. 分支與之前提供的 Merkle 根相匹配
2. C(P(x)) 在所有 16 種情況下都等于 Z(x) * D(x)

image.png

我們知道這個(gè)證明改善了完備性 -- 如果你真的知道一個(gè)合適的 P(x)剪勿，然后如果你計(jì)算 D(x) 并且正確地構(gòu)造出證明，那么這 16 個(gè)檢查都將順利通過方庭。但是 可靠性 怎么樣呢厕吉？ -- 也就是，如果一個(gè)惡意證明者提供了一個(gè)壞的 P(x)械念，他們被發(fā)現(xiàn)的最小概率是多少头朱？我們可以進(jìn)行如下分析：因?yàn)?C(P(x)) 是一個(gè) 1,000,000 次多項(xiàng)式，它的次數(shù)至多是 10,000,000龄减。通常來說项钮，我們知道兩個(gè)不同的 N 次多項(xiàng)式至多相交 N 個(gè)點(diǎn)。因此希停，對于某個(gè) x烁巫，一個(gè) 1,000,000 次多項(xiàng)式，一個(gè)總是等于 Z(x) * D(x) 的任意多項(xiàng)式脖苏，這兩個(gè)多項(xiàng)式若不同程拭，那么將會必然在至少 990,000,000 個(gè)點(diǎn)上都不同。故而棍潘，即使是只檢查一次恃鞋，一個(gè)壞的 p(x) 被發(fā)現(xiàn)的概率已經(jīng)是 99%，再加上有 16 次檢查亦歉，被發(fā)現(xiàn)的概率會上升到 1- 10 ^ -32恤浪。也就是說，該方案與計(jì)算哈希沖突一樣難以欺騙肴楷。

所以水由，我們剛剛到底分析了些什么？我們使用多項(xiàng)式“增強(qiáng)”了在任何不好的解決方案中的錯(cuò)誤赛蔫，也就是將原始問題糟糕的解決方案砂客，即需要直接執(zhí)行一百萬次檢查，變成了一個(gè)驗(yàn)證協(xié)議的方案呵恢，該方案即使進(jìn)行一次檢查鞠值，就能夠 99% 地標(biāo)識出錯(cuò)誤。

我們可以將這個(gè)三步的機(jī)制轉(zhuǎn)化為一個(gè)非交互式證明渗钉，也就是在利用 Fiat Shamir heuristic 的基礎(chǔ)上彤恶，一個(gè)證明者可以將它進(jìn)行廣播钞钙，然后被所有人進(jìn)行驗(yàn)證。證明者首先構(gòu)建一棵 P(x) 和 D(x) 值的 Merkle 樹声离，然后計(jì)算樹的根哈希芒炼。根自身隨后被用作是熵的來源，熵決定了證明者需要提供樹的哪個(gè)分支术徊。證明者然后一起廣播 Merkle 樹根和分支作為證明本刽。計(jì)算全部在證明者一端完成。從數(shù)據(jù)中計(jì)算 Merkle 樹根弧关，然后用它來挑選要審計(jì)的分支盅安，高效地取代了一個(gè)交互式驗(yàn)證者的需要。

對于一個(gè)沒有有效 P(x) 的惡意證明者世囊，他能做的唯一事情是進(jìn)入盡力不斷地構(gòu)造一個(gè)有效證明别瞭，直到他們最終足夠幸運(yùn)的話，找到了他們選擇計(jì)算的 Merkle 樹根分支株憾。不過鑒于可靠性是 1 - 10 ^ -32（也就是蝙寨，對于一個(gè)給定的假證明，至少有 1-10^-32 的概率無法通過檢查）嗤瞎，這可能會耗費(fèi)惡意證明者數(shù)十億年的時(shí)間來找到一個(gè)可通過檢查的證明墙歪。

image.png

進(jìn)一步探究

為了闡釋這個(gè)技術(shù)的強(qiáng)大之處，讓我們來用它做一點(diǎn)不尋常的事情：證明你知道第一百萬個(gè)斐波那契數(shù)贝奇。為此虹菲，我們會證明你知道一個(gè)表示一個(gè)計(jì)算帶的多項(xiàng)式，而 P(x) 表示第 x 個(gè)斐波那契數(shù)掉瞳。約束檢驗(yàn)多項(xiàng)式現(xiàn)在會跨越 3 個(gè) x 坐標(biāo)：C(x1, x2, x3) = x3 - x2 - x1（注意毕源，對于所有的 x， P(x) 表示一個(gè)斐波那契額序列陕习，如果 C(P(x), P(x+1), P(x+2)) = 0 會怎樣）霎褐。

fibonacci

轉(zhuǎn)換后的問題變成了：驗(yàn)證你知道 P 和 D 使得 C(P(x), P(x+1), P(x+2)) = Z(x) * D(x)。對于證明審計(jì)的 16 中情況中的每一個(gè)该镣，證明者需要提供用于 P(x)冻璃，P(x+1)，P(x+2) 和 D(x) 的 Merkle 分支损合。證明者額外還需要提供 Merkle 分支來表明 P(0) = P(1) = 1省艳。否則，整個(gè)過程都是一樣的嫁审。

現(xiàn)在跋炕，要想在現(xiàn)實(shí)中實(shí)現(xiàn)它，還需要解決兩個(gè)問題土居。第一個(gè)問題是，如果想要實(shí)際應(yīng)用于普通數(shù)字，這個(gè)方案不夠高效擦耀，因?yàn)閿?shù)字本身非常容易變的極大棉圈。比如，第一百萬個(gè)斐波那契數(shù)有 208988 位眷蜓。如果我們真的想要在實(shí)踐中達(dá)到簡潔的要求分瘾，不是在普通數(shù)字上計(jì)算多項(xiàng)式，而是需要使用有限域（finite field） -- 即仍然遵循同樣數(shù)學(xué)規(guī)則的數(shù)字系統(tǒng)吁系，比如 a * (b+c) = (a*b) + (a*c) 和 (a^2 - b^2) = (a-b) * (a+b)德召，但是這個(gè)數(shù)字系統(tǒng)中的每一個(gè)數(shù)字都保證只占據(jù)常量空間。證明第一百萬個(gè)斐波那契數(shù)將會需要一個(gè)更加復(fù)雜的設(shè)計(jì)汽纤，這個(gè)設(shè)計(jì)在這個(gè)有限域數(shù)學(xué)之上實(shí)現(xiàn)大數(shù)算術(shù)上岗。

最簡單最可能的有限域是模塊化數(shù)學(xué)。也就是蕴坪，對于某個(gè)質(zhì)數(shù) N肴掷，使用 a + b mod N 替換每一個(gè) a + b 。將同時(shí)的操作應(yīng)用與減法和乘法背传，對于除法呆瞻，使用 modular inverses（比如，如果 n = 7径玖，那么 3 + 4 = 0痴脾，2 + 6 = 1，3 * 4 = 5梳星，4 / 2 = 2 赞赖，5 / 2 = 6）。你可以 這里 （在頁面上搜索 "prime field"）了解更多關(guān)于這類數(shù)字系統(tǒng)丰泊，在里面我對質(zhì)數(shù)域做了一些介紹薯定。或者從有關(guān)模塊化數(shù)學(xué)的 維基百科（在文章內(nèi)直接搜索 “finite fields” 和 “prime fields”瞳购，可能看起來非常復(fù)雜话侄，與抽象代數(shù)直接相關(guān)，但是不要在意這些）了解更多学赛。

第二年堆，你可能已經(jīng)注意到，在我上面的可靠性證明梗概中盏浇，我忽略了一種攻擊：不用似然的 1,000,000 次 P(x) 和 9,000,000 次 D(x)变丧，攻擊者提交另一些值，這些值不來源與任何相對低次的多項(xiàng)式绢掰？然后痒蓬，一個(gè)無效 C(P(x)) 的參數(shù)童擎，必須在至少 990 百萬不適用的點(diǎn)上不同于任何有效 C(P(x))，所以也就可能出現(xiàn)更多的這種有效攻擊攻晒。比如顾复，一個(gè)攻擊者可以為每一個(gè) x 生成一個(gè)隨機(jī)值 p，然后計(jì)算 d = C(p) / Z(x) 鲁捏，然后提交這些值替換 P(x) 和 D(x)芯砸。這些值不會是基于任何一種低次多項(xiàng)式，但是它們會通過測試给梅。

事實(shí)證明假丧，盡管用到的工具可能相當(dāng)復(fù)雜，但上面這種可能性仍然可以進(jìn)行有效地防范动羽，現(xiàn)在你可以非常負(fù)責(zé)任地說包帚，它們確實(shí)填補(bǔ)了 STARKs 中數(shù)學(xué)創(chuàng)新的空缺。不過曹质，這個(gè)解決方法也有一個(gè)限制：雖然你可能會剔除與 1,000,000 次多項(xiàng)式相差甚遠(yuǎn)（比如婴噩，你會需要改變所有值的 20% ，使它成為一個(gè) 1,000,000 次多項(xiàng)式）的一些數(shù)據(jù)保證（commiment to data）羽德，但是你無法排除僅在于只有一兩個(gè)坐標(biāo)不同的多項(xiàng)式數(shù)據(jù)几莽。因此，這些工具將提供臨近證明（proof of proximity） -- 證明 P 和 D 上的大多數(shù)點(diǎn)都與那類多項(xiàng)式相關(guān)宅静。

因此章蚣，盡管有兩個(gè)“意外情況（catches）”，但是構(gòu)建一個(gè)證明仍然是足夠的姨夹。首先纤垂，驗(yàn)證者需要再多檢查一些情況，為其局限性所引入的錯(cuò)誤留一些余地磷账。第二峭沦，如果我們正在做“邊界約束檢查（boundary constraint checking）”（比如，證明上面斐波那契案例中的 P(0) = P(1) = 1 ）逃糟，然后吼鱼，我們需要擴(kuò)展臨近證明，不僅證明大多數(shù)點(diǎn)都在同一個(gè)多項(xiàng)式上绰咽，而且證明這兩個(gè)（或你想要檢查的任何點(diǎn)數(shù)）特定點(diǎn)都在這個(gè)多項(xiàng)式上菇肃。

在這個(gè)系列的下一部分，我會繼續(xù)解讀臨近檢查問題的解決方案取募。

原文：STARKs, Part I: Proofs with Polynomials