區(qū)塊鏈新型零知識(shí)證明是怎么工作的

這篇文章主要介紹“區(qū)塊鏈新型零知識(shí)證明是怎么工作的”，在日常操作中，相信很多人在區(qū)塊鏈新型零知識(shí)證明是怎么工作的問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”區(qū)塊鏈新型零知識(shí)證明是怎么工作的”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

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

讓我們來舉個(gè)例子：

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

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

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

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

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

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

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

簡(jiǎn)單舉例

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

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

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

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

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

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

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

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

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

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

前景展望

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

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

現(xiàn)在，為了完成這個(gè)，還需要解決2個(gè)問題。第一個(gè)是，如果我們嘗試進(jìn)行列舉數(shù)字的方法來解決這個(gè)問題，效率就會(huì)很低，因?yàn)檫@些數(shù)字通常都會(huì)很大。例如，第100萬個(gè)斐波納契數(shù)有208988個(gè)數(shù)字。如果我們其實(shí)想要獲得簡(jiǎn)單性，與其使用常規(guī)數(shù)字進(jìn)行列舉，我們需要使用有限的數(shù)字系統(tǒng)，始終符合我們了解的規(guī)則，例如a * (b+c) = (ab) + (ac) and (a^2 – b^2) = (a-b) * (a+b)，但是每個(gè)數(shù)字都會(huì)占據(jù)一定空間的數(shù)據(jù)。證明關(guān)于斐波納契數(shù)數(shù)字的問題，需要更加復(fù)雜的設(shè)計(jì)。最簡(jiǎn)單的模式，就是將每個(gè)a + b用a + b的N進(jìn)制數(shù)來代替，對(duì)減法和乘法也是同樣地方法，對(duì)于除法，使用模塊逆轉(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億個(gè)點(diǎn)上相同，就不會(huì)應(yīng)用了，而且會(huì)非常不同，而且更有效的攻擊是有可能發(fā)生的。例如 ，一個(gè)攻擊者會(huì)保證任何x都有一個(gè)隨機(jī)數(shù)p，那么計(jì)算d = C(p) / Z(x)，并且將這些數(shù)字都放入P(x)和D(x)。這些數(shù)字不會(huì)在任何低維度的多項(xiàng)式，但是它們會(huì)通過檢測(cè)。

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

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

到此，關(guān)于“區(qū)塊鏈新型零知識(shí)證明是怎么工作的”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！