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

很希望現(xiàn)在很多人都聽說過ZK-SNARKs協(xié)議，這是零知識證明技術(shù)的通用性說法，使用它的案例從可驗(yàn)證的計算到私人保護(hù)的數(shù)字貨幣。也許你不知道，ZK-SNARKs協(xié)議有更新的版本，ZK-STARKs。其中改變的字母T代表的是“透明”，ZK-STARKs解決ZK-SNARKs的其中一個弱勢，它依賴于一種“可信任的配置”。而且ZK-STARKs也有更加簡單的加密假設(shè)，從而避免橢圓曲線，配對以及指數(shù)假設(shè)的知識，而是僅僅依賴于哈希和信息的理論；這也就意味著他們對于量子計算機(jī)的攻擊來說，是安全的。

但是，這也會有代價：證明的存儲大小也從288字節(jié)增加到幾百千兆字節(jié)。有時候這個代價并不值得，但是有時候，特別是在討論公鏈應(yīng)用的時候，需要的最小信任非常高，事情就很可能這樣。并且如果橢圓曲線打破或者量子計算機(jī)真地出現(xiàn)，這事情就肯定會發(fā)生。

所以這種零知識證明是如何工作呢？首先，讓我們來看看通用的ZKP協(xié)議是做什么的。假設(shè)你現(xiàn)在有一個公開函數(shù)f，一個私密的輸入x以及一個公開的輸出y。你想要證明你知道一個x，從而得到f(x) = y，而不用泄露x是什么。并且，為了保證這個協(xié)議足夠簡單，你想要它的驗(yàn)證比計算f本身還要快。

讓我們來舉個例子：

f 是一個需要在普通計算機(jī)上運(yùn)行2周的計算，但是在數(shù)據(jù)中心只需要2小時。你給數(shù)據(jù)中心發(fā)送了這個計算（也就是說，運(yùn)行f的代碼），然后數(shù)據(jù)中心就會運(yùn)行，并且通過證明反饋了答案y。你在幾毫秒之內(nèi)，就驗(yàn)證了這個證明，并且相信y其實(shí)就是答案。

你有一個加密的交易，表格中的X1是我之前的余額。X2是你之前的余額。X3是我新的余額。X4是你新的余額。你想要創(chuàng)建一個證明，其中這個交易是有效的（特別指出，之前和現(xiàn)在的余額都是正的，而且我余額的減少抵消了你余額的增加）。x可以是秘鑰對，并且f可以是一個函數(shù)，其中包含了內(nèi)置公開輸入的交易，而且作為輸入秘鑰，解密了交易，完成了檢驗(yàn)，如果通過就返回1，如果失敗就返回0。y 當(dāng)然會是1。

你有個類似以太坊的區(qū)塊鏈，而且你下載了最近的區(qū)塊。你想要一個證明，表示這個區(qū)塊是有效的，而且這個區(qū)塊是在鏈的頂端，其中鏈上任何區(qū)塊都是有效的。你想讓一個現(xiàn)存的全節(jié)點(diǎn)來提供這樣的驗(yàn)證。x是整個區(qū)塊鏈，f是區(qū)塊處理的函數(shù)，驗(yàn)證有效性并且輸出最后區(qū)塊的哈希，而且y就是你之前下載區(qū)塊的哈希。

所以這些問題的困難點(diǎn)在哪呢？就像它表現(xiàn)出來的，需要很容易為零知識證明（也就是，隱私性）提出保證；現(xiàn)在有很多種方法來將任何計算轉(zhuǎn)換為例如三色圖表問題的情況，其中圖表的三種顏色都對應(yīng)原始問題的解決方案，然后使用傳統(tǒng)的零知識證明協(xié)議來證明，你即使不揭露它的信息，也可以獲得有效的圖表顏色。

更困難的地方在于提供簡潔性。直觀地來說，證明關(guān)于計算簡潔性是困難的，因?yàn)橛嬎闶请y以置信地脆弱。如果你有個很長很復(fù)雜的計算，那么你需要有能力在計算過程中的任何地方，從0跳到1，然后再很多情況下，甚至很小的失誤都會導(dǎo)致計算結(jié)果完全不同。因此，很難知道你如何才能做出例如對計算過程地隨機(jī)取樣，才能保證正確性。因?yàn)椋苋菀拙蜁e過“很小部分的計算”。但是，通過一些厲害的數(shù)學(xué)方法，你就可以做到。

整體的感覺是，和這些聯(lián)合在一起的協(xié)議，都在使用糾偏編碼的數(shù)學(xué)方式，這種方式通常用來讓數(shù)據(jù)可以容錯。如果你有項(xiàng)目數(shù)據(jù)，那么你可以將這些數(shù)據(jù)作為行代碼，然后你可以在這行中選出四個點(diǎn)。其中任何兩個點(diǎn)都足夠來重新構(gòu)造這條線，因此也給你另外兩個點(diǎn)。并且，如果你甚至對數(shù)據(jù)進(jìn)行了很小的改變，那么它至少保證了你四個點(diǎn)中的三個。你也可以將數(shù)據(jù)編碼成1,000,000維度的多項(xiàng)式，并且從中選出2,000,000個點(diǎn)；這些點(diǎn)中的任意1,000,001個都會獲得初始數(shù)據(jù)，因此其他點(diǎn)，以及數(shù)據(jù)的任何偏離都會至少改變1,000,000個點(diǎn)。這里的算法將會這樣利用多項(xiàng)式，從而使得誤差放大。

原始數(shù)據(jù)更改1個點(diǎn)，對于多項(xiàng)式都會有很大的改變

簡單舉例

假設(shè)你想要證明，你有個多項(xiàng)目P，從而對于x從1到100萬，P(x)是0 <= P(x) <= 9之間的整數(shù)。這就是“范圍檢查”的簡單舉例；也許你會假設(shè)這類檢查可以用來進(jìn)行驗(yàn)證，例如在進(jìn)行轉(zhuǎn)賬后，賬戶余額仍然是正數(shù)。如果1 <= P(x) <= 9成立，那么這可能是檢查這些值形成正確的數(shù)獨(dú)解決方案的一部分。

“傳統(tǒng)”的方式是證明這會顯示所有1,000,000個點(diǎn)，并且通過檢查這些數(shù)值來驗(yàn)證。但是，我們想要看到是否我們能夠做出證據(jù)，可以在少于1,000,000個步驟的時候就被驗(yàn)證。簡單隨機(jī)檢查P的估值不會這樣做；總會有欺詐者出現(xiàn)，來證明P是滿足999,999個位置，但是不能滿足最后一個，而且隨機(jī)取樣就幾個數(shù)字，通常總是會錯過那個。那么我們可以怎么做呢？

讓我們從數(shù)學(xué)方式來轉(zhuǎn)化這個問題。假設(shè)C(x)是多項(xiàng)式檢驗(yàn)；如果0 <= x <= 9，那么C(x) = 0，否則，C(x)就是非零數(shù)字。有一種很簡單的方法，就可以構(gòu)建C(x)：x * (x-1) * (x-2) * … * (x-9)（我們會假設(shè)，所有我們的多項(xiàng)式和其他數(shù)字都會使用常數(shù)，所有我們不需要擔(dān)心之間的數(shù)字）。

現(xiàn)在，問題變成了：證明你知道P，然后對于所有的x從1到1,000,000，C(P(x)) = 0。讓Z(x) = (x-1) * (x-2) * … (x-1000000)。很基本的數(shù)學(xué)事實(shí)是，對于x從1到1,000,000，任何等于零的多項(xiàng)式都是Z(x)的乘積。因此，問題再次轉(zhuǎn)變成了：證明你知道P和D，然后對于所有的x，C(P(x)) = Z(x) * D(x)（需要注意到，如果你知道一個合適的C(P(x))，那么用Z（x）除以計算D（x）不是太困難；你可以使用長多項(xiàng)式除法或者基于FFT算法來進(jìn)行更快地運(yùn)算）。現(xiàn)在，我們將最初的問題轉(zhuǎn)換成了數(shù)學(xué)問題，并且看起來可以順利解決。

那么如何證明這個問題呢？我們可以假設(shè)，證明過程是證明者和驗(yàn)證者之間的三步溝通：證明者發(fā)出了一些信息，然后驗(yàn)證者發(fā)出一些需求，之后證明者發(fā)出更多的信息。首先，證明者承認(rèn)（也就是說，創(chuàng)建一個Merkle樹，并且給驗(yàn)證者發(fā)去根哈希）對于1到10億之間x的所有P(x) 和 D(x)的估值。這就包含了0 <= P(x) <= 9之間的100萬個點(diǎn)，以及剩下的9.99億個點(diǎn)。

假設(shè)驗(yàn)證者已經(jīng)知道Z(x)在這些點(diǎn)的估值;那么Z(x)就像一個“公共的驗(yàn)證秘鑰”，從而每個人都必須提前知道（沒有地方存儲Z(x)的客戶端，可以簡單地將它存儲在Z(x)的Merkle樹根部，而且需要證明者也為每個Z(x)的數(shù)值提供驗(yàn)證者需要的分支；或者，有些數(shù)字字段，對于x和Z(x)都很容易計算）。在獲得這個認(rèn)可（也就是說，Merkle樹的根部），驗(yàn)證者然后會在1和10億之間選擇隨機(jī)的16x數(shù)值，而且讓證明者來提供P(x)和D(x)的Merkle樹分支。證明者提供了這些數(shù)值，而且驗(yàn)證者會檢查(i)這些分支和之前提供的Merkle樹根部符合（ii）C(P(x))其實(shí)等于Z(x) * D(x)。

我們知道這個證明有很好的完整性，如果你其實(shí)知道一個合適的P(x)，那么你可以計算D(x)并且構(gòu)建正確的證明，來通過16個檢查點(diǎn)。但是穩(wěn)定性又如何呢？也就是說，如果欺詐的證明者提供了個錯誤的P(x)，他們被抓的最小可能性是多少？我們可以進(jìn)行如下分析。因?yàn)镃(P(x))是由1,000,000維度多項(xiàng)式組成的10維度多項(xiàng)式。整體來說，我們知道這兩個不同的多項(xiàng)式最多在N個點(diǎn)符合；因此，10,000,000維度的多項(xiàng)式和任何等于Z(x) * D(x)的多項(xiàng)式都不會相等。對于x來說，至少在990,000,000個點(diǎn)都不會同意。因此，對于不好的P(x)，在一輪被抓住的概率已經(jīng)是99%；通過16輪檢查，被抓住的概率是1 – 10-32 ，也就是說，這個機(jī)制不可能存在欺詐。

那么，我們剛剛做了什么？我們使用多項(xiàng)式來推動任何不良解決方案的錯誤，以至于對于初始問題的任何錯誤解決方案，都需要100萬個檢查才能發(fā)現(xiàn)，最終導(dǎo)致驗(yàn)證協(xié)議的解決方案，可以99%的概率發(fā)現(xiàn)錯誤。

我們可以將這三步的機(jī)制轉(zhuǎn)換成一個非交互式的證明，這可以通過單個的證明者來廣播，然后被任何人使用菲亞特-夏米爾啟發(fā)式算法來進(jìn)行驗(yàn)證，證明者首先構(gòu)建P(x) 和 D(x)數(shù)值的Merkle樹，然后計算樹的根哈希。這個根部本身被用于作為熵的來源，用來決定證明者需要提高這個樹的哪些分支。證明者然后就會廣播Merkle樹的根部，分支還有證明。計算全部會在提供方完成；從數(shù)據(jù)計算Merkle樹根部的過程，然后是使用這些來選擇經(jīng)過審計的分支，有消息地完成了交互性驗(yàn)證者的需求。

欺詐者在不需要有效的P(x)前提下，唯一能做的事情，就是嘗試進(jìn)行有效驗(yàn)證，直到最終他們特別幸運(yùn)，選擇到了正確的Merkle樹分支，但是概率只有1 – 10-32 （也就是說，至少有1 – 10-32 的概率，虛假的證明不會通過檢查），欺詐者需要花費(fèi)幾十億年，才能得到可以通過的證明。

前景展望

為了說明這項(xiàng)技術(shù)的能力，我們來做些看起來不是很重要的事情：證明你知道第100萬個斐波納契數(shù)。為了完成這個，我們會證明你對多項(xiàng)式有了解，P(x)代表第x個斐波納契數(shù)。多項(xiàng)式檢驗(yàn)就會從3個維度進(jìn)行：C(x1, x2, x3) = x3-x2-x1（需要注意，如果對所有x來說，C(P(x), P(x 1), P(x 2)) = 0，那么P(x)久代表斐波納契數(shù)）。

所以問題就變成了：證明你知道有個P和D，然后C(P(x), P(x 1), P(x 2)) = Z(x) * D(x)。對于其中的16個因子，證明者需要為P(x), P(x 1), P(x 2) and D(x)提供Merkle樹的分支。證明者而且還需要保證所提供的Merkle樹的分支可以保證，P(0) = P(1) = 1。否則，整個流程就是一樣的。

現(xiàn)在，為了完成這個，還需要解決2個問題。第一個是，如果我們嘗試進(jìn)行列舉數(shù)字的方法來解決這個問題，效率就會很低，因?yàn)檫@些數(shù)字通常都會很大。例如，第100萬個斐波納契數(shù)有208988個數(shù)字。如果我們其實(shí)想要獲得簡單性，與其使用常規(guī)數(shù)字進(jìn)行列舉，我們需要使用有限的數(shù)字系統(tǒng)，始終符合我們了解的規(guī)則，例如a * (b c) = (a*b) (a*c) and (a^2 – b^2) = (a-b) * (a b)，但是每個數(shù)字都會占據(jù)一定空間的數(shù)據(jù)。證明關(guān)于斐波納契數(shù)數(shù)字的問題，需要更加復(fù)雜的設(shè)計。最簡單的模式，就是將每個a b用a b的N進(jìn)制數(shù)來代替，對減法和乘法也是同樣地方法，對于除法，使用模塊逆轉(zhuǎn)（例如，如果N=7，那么3 4 = 0, 2 6 = 1, 3 * 4 = 5, 4 / 2 = 2而且5 / 2 = 6）。

其次，你也許注意到了，在上面的證明中，我忽略了一種攻擊：如果攻擊者不是通過看似真實(shí)的P(x)，而是使用了并不在這些多項(xiàng)式的數(shù)據(jù)？那么，無效的C(P(x))必須要和有效的C(P(x))在至少9.9億個點(diǎn)上相同，就不會應(yīng)用了，而且會非常不同，而且更有效的攻擊是有可能發(fā)生的。例如 ，一個攻擊者會保證任何x都有一個隨機(jī)數(shù)p，那么計算d = C(p) / Z(x)，并且將這些數(shù)字都放入P(x)和D(x)。這些數(shù)字不會在任何低維度的多項(xiàng)式，但是它們會通過檢測。

這就證明了這種可能性會很有效地抵抗攻擊，雖然做這些的工具相對復(fù)雜，而且你可以說它們組成了STARKs協(xié)議中的數(shù)學(xué)創(chuàng)新。同時，這個解決方案有個限制：你可以清除這些數(shù)據(jù)，但是你不能清除和你的多項(xiàng)式存在一個或兩個變量差別的多項(xiàng)式。因此，這些工具會提供接近性證明，證明大多數(shù)在P和D的點(diǎn)上，都會代表正確的多項(xiàng)式。

所以最終證明，這已經(jīng)足夠來打造證明，盡管會有兩個小問題。首先，驗(yàn)證者需要檢查更多的指數(shù)來彌補(bǔ)錯誤占據(jù)的有限空間。其次，如果我們正在打造邊界檢測，那么我們需要將接近性證明擴(kuò)大到不止是證明大多數(shù)點(diǎn)是在同個多項(xiàng)式，而且證明這兩個特別的點(diǎn)是在那個多項(xiàng)式上。