Vitalik ：理解新型通用零知識證明方案PLONK_VITA

特別感謝JustinDrake、KarlFloersch、XiaoWeiWang、BarryWhitehat、DankradFeist以及ZacWilliamson的審查工作。

注：原文作者是以太坊聯合創始人VitalikButerin

以下是譯文：

最近，ArielGabizon、ZacWilliamson和OanaCiobotaru公布了一種新的通用零知識證明方案PLONK，其全稱是笨拙的“PermutationsoverLagrange-basesforOecumenicalNoninteractiveargumentsofKnowledge”。雖然對通用零知識證明協議的改進研究已進行了多年，但PLONK帶來的是一系列的改進，這些改進可能會總體上大大提高這類證明的可用性及進展。

第一個改進：雖然PLONK仍需要一個類似ZcashSNARKs的可信設置過程，但它是一個“通用且可更新”的可信設置。這意味著兩件事：首先，不需要為每一個你想證明的程序都設置一個單獨的可信設置，而是為整個方案設置一個單獨的可信設置，之后你可以將該方案與任何程序一起使用。第二，有一種方法可以讓多方參與可信設置，這樣只要其中任何一方是誠實的，那這個可信設置就是安全的，而且這種多方過程是完全連續的：首先是第一個人參與，然后是第二個人，然后是第三個……參與者們甚至不需要提前知道，新的參與者可以把自己添加到最后。這使得可信設置很容易擁有大量參與者，從而在實踐中確保設置是非常安全的。

第二個改進是它所依賴的“奇特密碼學”是一個單一的標準化組件，稱為“polynomialcommitment”。PLONK使用基于可信設置和橢圓曲線對的“Katecommitments”，但你也可以用其它方案替換它，例如FRI或者DARK。這意味著該方案在理論上與證明大小和安全性假設之間的任何權衡兼容。

這意味著需要在證明大小與安全性假設之間進行不同權衡的用例，仍然可以為“算術化”共享大部分相同的工具。如果這種方案被廣泛采用，那我們可期待在改進共享算術化技術方面的快速進展。

Vitalik Buterin：基于MPC的EOA錢包有根本缺陷，智能合約錢包是唯一選擇:6月29日消息，以太坊創始Vitalik Buterin發推回應如何看待基于MPC（EOA）的錢包與智能合約錢包的優缺點時表示，基于MPC的EOA錢包存在根本缺陷，因為它們無法撤銷密鑰（重新共享不算在內；舊持有者仍然可以恢復密鑰），智能合約錢包是唯一的選擇。[2023/6/29 22:07:37]

PLONK是如何工作的

讓我們從解釋PLONK的工作原理開始，我們只關注多項式方程而不立即解釋如何驗證這些方程。PLONK的一個關鍵組成部分，就像SNARKs中使用的QAP一樣，這是一個轉換問題的過程，形式是“給我一個值X，我給你一個特定的程序P，這樣當X作為輸入進行計算時，給出一些具體的結果Y，”放到問題“給我一組滿足一組數學方程的值”當中。程序p可以表示很多東西，例如，問題可能是“給我一個數獨的解決方案”，你可以通過將P設置為數獨驗證器加上一些編碼的初始值并將Y設置為1來對其進行編碼，一個令人滿意的輸入X將是數獨的有效解決方案。這是通過將P表示為一個帶有邏輯門的加法和乘法電路，并將其轉換為一個方程組來完成的，其中變量是所有線上的值，每個門有一個方程。

下面是一個求x問題的例子，這樣P(x)=x**3+x+5=35(提示:x=3):

我們按如下方式給門和線貼上標簽：

在門和線上，我們有兩種類型的約束：門約束和復制約束。我們需要創建一個結構化的方程組，它最終將減少到一個非常少數量的多項式方程組，來表示這兩個方程組。

在PLONK中，這些方程的設置和形式如下：

每個Q值都是一個常數，每個方程中的常數對于每個程序都是不同的。每個小寫字母值都是一個變量，由用戶提供：ai是第i個門的左輸入線，bi是右輸入線，ci是第i個門的輸出線。對于加法門，我們設置：

Watcher.Guru：Vitalik Buterin撰寫以太坊白皮書時只有19歲:金色財經報道，Watcher.Guru發推特表示，Vitalik Buterin撰寫Ethereum白皮書時只有19歲。[2023/2/20 12:16:52]

將這些常數插入方程并進行簡化，得到ai+bi-oi=0，這正是我們想要的約束條件。對于乘法門，我們設置：

對于將ai設置為某個常數x的常數門，我們設置：

你可能已注意到線的每一端，以及一組線中的每根線，顯然必須具有相同的值對應于一個不同的變量；到目前為止，沒有什么能強迫一個門的輸出與另一個門的輸入相同。PLONK當然有一種強制復制約束的方法，我們稍后會討論這個問題。所以現在我們有一個問題，證明者想要證明他們有一堆Xai,Xbi以及Xci值滿足了一堆相同形式的方程。這仍然是一個大問題，但不像“找到這個計算機程序的一個令人滿意的輸入”，這是一個非常結構化的大問題，我們有數學工具可用于“壓縮”它。

從線性系統到多項式

如果你了解過STARKs或QAPs，下一節中描述的機制會讓人覺得有些熟悉，但如果你沒有，那也沒有關系。這里的主要內容是將多項式理解為一種數學工具，用于將大量值封裝到單個對象中。通常，我們是以“系數形式”來看待多項式，即如下表達式：

但我們也可用“定值形式”來看待多項式。例如，我們可以認為上面是在坐標處分別定值的“度數<4”的多項式。

下面是下一步。許多形式相同的方程組可重新解釋為多項式上的一個方程組。例如，假設我們有一個系統：

我們用定值形式定義四個多項式：L(x)是在坐標(0,1,2)處定值為的度數<3的多項式，在同樣的坐標系下，M(x)定值為(-1,4,-1)，R(w)定值為(3,-5,-1)以及O(x)定值為(8,5,-2)。現在，考慮下面這個等式：

Vitalik：與PoW的共識機制相比，PoS消耗的電力減少99.95%:金色財經聯合Coinlive現場報道Singapore FinTech Festival 2022，以太坊創始人Vitalik Buterin發表題為《大合并：與 Vitalik Buterin 一起重構以太坊》的演講，談到了以太坊的合并的好處、困難和問題。Vitalik表示，與PoW的共識機制相比，PoS 消耗的電力減少了 99.95%。強大的共識設計和并行確認，讓攻擊鏈的難度增加、更容易進行升級、降低了代幣發行要求，這些都為以太坊帶來更好的穩定性。未來以太坊要提升可擴展性、用戶體驗、安全問題和隱私，Vitalik已經想到了幾個解決方案，例如danksharding，通過添加大量數據空間來改進以太坊基礎層。[2022/11/3 12:13:04]

在這里，Z(x)是(x-0)*(x-1)*(x-2)的簡寫，它是在定值域(0,1,2)上返回零的最小多項式。這個方程的解(x1=1,x2=6,x3=4,H(x)=0)也是原方程組的解，只是原方程組不需要H(x)。還要注意，在這種情況下，H(x)很方便為零，但在更復雜的情況下，H可能需要為非零。

所以現在我們知道，我們可以在少數數學對象中表示一個大的約束集。但在我們上面建立的表示門線約束的方程中，x1,x2,x3變量在每個方程中是不同的。我們可以用同樣的方法使變量本身成為多項式而不是常數來處理這個問題。所以我們得到：

如前所述，每個Q多項式是由正在驗證的程序生成的參數，a,b,c多項式是用戶提供的輸入。

復制約束(Copyconstraints)

現在，讓我們回到“連接”線上。到目前為止，我們所擁有的是一組關于不相交值的不相交方程，這些方程獨立且易于滿足：常數門可通過將值設置為常數來滿足，加法和乘法門可通過將所有線設置為零來滿足！為了使問題具有實際的挑戰性，我們需要添加一個驗證“復制約束”的等式，這需要一些巧妙的技巧。

Vitalik Buterin：開發人員還不知道“Merge + surge + verge + purge + splurge”的執行順序:金色財經報道，以太坊聯合創始人“V神” Vitalik Buterin 今日在社交媒體上發文稱“Merge + surge + verge + purge + splurge”不是5個階段，而是會并行發生。在回應加密社區質疑“合并后不會立即發生所有事情”的問題時，Vitalik Buterin 進一步解釋說，這一切都是同時發生，實際的部署會在單獨的硬分叉進行，但是不同的團隊正在并行完成工作，在某些情況下，開發人員甚至還不知道事情的執行順序。[2022/7/26 2:38:57]

我們的策略是設計一個“坐標對累加器”，一個多項式p(x)的工作原理如下：首先，讓X(x)和Y(x)兩個多項式表示一組點的x和y坐標給定的位置，所以p(0)從1開始，p(1)只代表第一個點，p(2)是第一個點和第二個點，諸如此類。我們將通過“隨機”選擇兩個常數v1和v2，并使用約束p(0)=1以及p(x+1)=p(x)*(v1+X(x)+v2*Y(x))構造p(x)，至少在域內。例如，讓v1=3和v2=2，我們得到：

注意每個p(x)值，等于它左邊的值乘以它左上面的值。

我們關心的結果是

p(4)=-240。現在，考慮這樣的情況，我們設置X(x)=2?3x^3-4x^2+19?3x（即，在坐標

處定值為

的多項式），而不是X(x)=x。

如果你運行同樣的過程，你會發現你也會得到p(4)=-240。

這不是巧合。相反，這是因為Y(1)=Y(3)，所以如果你“交換”點(1,1)和的X坐標，你就不會改變點的集合，并且因為累加器對集合進行編碼，所以最后的值將是相同的。

現在，我們可以開始了解我們將用來證明復制約束的基本技術。首先，考慮一個簡單的例子，我們只想證明在一組線中的復制約束=a）。我們將生成兩個坐標累加器：一個是X(x)=x和Y(x)=a(x)，另一個是Y(x)=a(x)，而X’(x)是對每個復制約束中的值的翻轉排列定值的多項式。在a(1)=a(3)的情況下，這意味著排列將開始于03214....第一個累加器將壓縮((0,a(0)),(1,a(1)),(2,a(2)),(3,a(3)),(4,a(4))...，第二個壓縮），），），），）……只有當a(1)=a(3)時，兩者才能給出相同的結果。

聲音 | Vitalik評論澳本聰轉賬假新聞：不要在沒有親自驗證原文鏈接的情況下相信推特上的截圖:針對“澳本聰從最大BTC地址向幣安轉出5萬BTC事件”，Primitive Ventures的創始合伙人萬卉在推特上表示：“這個伎倆很容易被許多詐騙者所使用，很多中國加密媒體都通過微信上面的圖片傳播突發新聞，而不是傳播新聞鏈接。所以任何人都可以使用相同的主題模板，然后PS一條假新聞。”以太坊創始人Vitalik今日在推特上評論稱，我們迫切需要經過網站驗證且有數字簽名的截屏，這也會讓智能合約預言機更容易些。他還配上一張P圖，圖中美國總統特朗普表示，不要在沒有親自驗證原文鏈接的情況下相信推特上的截圖。[2019/5/30]

為了證明a，b和c之間的約束，我們使用了相同的過程，但是我們將所有三個多項式的點“累加”在一起。我們給a,b,c賦值一些X坐標=b，那么X’a(x)將有定值01934，X’b(x)將有定值56782。然后，我們將不再像以前那樣檢查一次過程中的相等性，而是檢查每側三次不同運行的乘積：

兩邊的三個p(n)定值的乘積將a、b和c中的所有坐標對累加在一起，因此這允許我們像以前一樣進行檢查，除此之外，我們現在不僅可檢查三組線A、B或C中一組內的位置之間的復制約束，還可以檢查一組線與另一組線之間的復制約束。

就這些了！

把所有東西放到一起

實際上，所有這些數學運算都不是在整數上進行的，而是在素數域上進行的；請檢查此處的“模塊化數學插曲”部分，以了解素數域是什么。此外，出于數學上的原因，最好是用快速傅里葉變換實現來閱讀和理解這篇文章，而不是用x=0....n-1表示線指數，我們將使用ω：1，ω，ω^2….ω^n-1的冪,其中ω是域中的一個高次單位根。這與數學無關，只是坐標對累加器約束檢查方程從p(x+1)=p(x)*(v1+X(x)+v2*Y(x))更改為p(ω*x)=p(x)*(v1+X(x)+v2*Y(x))，而不是使用0..n-1,n..2n-1,2n..3n-1作為坐標，我們使用ω^i,g*ω^i,其中g可以是域中的某些隨機高階元素。

現在讓我們寫出所有需要檢查的方程式。首先，主門約束滿足性檢查：

然后是多項式累加器轉換約束：

然后多項式累加器開始和結束約束：

用戶提供的多項式是：

線分配a(x),b(x),c(x)；

坐標累加器Pa(x),Pb(x),Pc(x),Pa’(x),Pb’(x),Pc’(x)；

商H(x)和H1(x)…H6(x)；

證明者和驗證者需要提前計算的程序特定多項式為：

QL(x),QR(x),QO(x),QM(x),QC(x)，它們共同代表電路中的門；

“排列多項式”σa(x),σb(x)和σc(x)，它們編碼a,b和c線之間的復制約束；

注意，驗證者只需要存儲這些多項式的承諾。上述方程中僅存的多項式是Z(x)=(x-1)*(x-ω)*…*(x-ω^(n-1))，其設計目的是在所有這些點上計算為零。幸運的是，可以選擇ω使這個多項式很容易計算：通常的方法是選擇ω來滿足ω^n=1,在這種情況下Z(x)=x^n-1。

對v1和v2的唯一限制是，在v1和v2已知之后，用戶不能選擇a(x),b(x)或c(x)，所以我們可通過計算a、b和c的承諾哈希的v1和v2來滿足這個要求。。

所以現在我們已經把程序滿足問題，變成了用多項式滿足幾個方程的簡單問題，PLONK中有一些優化，其可以允許我們去掉上面方程中的很多多項式，為了簡單考慮，我將不再討論這些。但是多項式本身，都是很大的。

所以下一個問題是，我們如何繞過這個問題，才能讓證明變簡短？

多項式承諾

多項式承諾是一個短對象，其“代表”一個多項式，并允許你驗證該多項式的計算，而不需要實際包含多項式中的所有數據。也就是說，如果有人給你一個代表P(x)的承諾c，他們可以給你一個證明，然后說服你對于某個特定的z，P(z)值是多少。還有一個進一步的數學結果表明，在一個足夠大的域上，如果關于在隨機z上定值的多項式的某些類型的方程是真的，那么這些相同的方程對整個多項式也是真的。例如，如果P(z)*Q(z)+R(z)=S(z)+5，那么我們知道P(x)*Q(x)+R(x)=S(x)+5通常是極有可能的。使用這樣的多項式承諾，我們可以很容易地檢查上面所有的多項式方程。作出承諾，使用它們作為輸入生成z，證明在z上每個多項式的定值是什么，然后用這些定值來運行方程，而不是原來的多項式。那這些承諾是如何運作的呢？

有兩部分：對多項式P(x)->c的承諾，以及在某個z處對值P(z)的opening。而要作出承諾，有很多技術，一個例子是FRI，另一個是Kate承諾，我將在下面描述。為了證明一個opening，有一個簡單的通用“減除”技巧：為了證明P(z)=a，你要證明

也是一個多項式。這是因為如果商是一個多項式，那么x-z是P(x)-a的一個因子，所以(P(x)-a)(z)=0，所以P(z)=a。用一些多項式試試，比如P(x)=x^3+2*x^2+5(z=6，a=293),然后試試(z=6,a=292)，看看它是如何失敗的，）

另請注意一個一般優化：為了同時證明多個多項式的多個opening，在提交輸出后，對多項式和輸出的隨機線性組合執行減除技巧。

那么，承諾本身是如何運作的呢？幸運的是，Kate承諾要比FRI簡單得多。可信設置過程生成一組橢圓曲線點G,G*s,G*s^2….G*s^n，以及G2*s，其中G和G2是兩個橢圓曲線組的生成器，而s則是一個一旦程序完成就會被遺忘的秘密。這些點會被公布，并被認為是方案的“證明關鍵”，任何需要作出多項式承諾的人都需要使用這些點。通過將證明密鑰中的前d+1個點中的每一點乘以多項式中的相應系數，并將結果相加，對d次多項式作出承諾。

注意，這提供了在s處的多項式的“定值”，而不知道s。例如，x^3+2x^2+5將由(G*s^3)+2*(G*s^2)+5*G表示。我們可以用符號來表示用這種方式編碼的P。在做減除技巧時，可以使用橢圓曲線對來證明這兩個多項式實際上滿足關系：檢查e(-G*a,G2)=e(,-G2*z)是否作為檢查P(x)-a=Q(x)*(x-z)的代理。

但最近也出現了其他類型的多項式承諾。一個新的方案被稱為DARK使用了“隱序組”如類組來實現另一種多項式承諾。隱藏順序組是唯一的，因為它們允許你將任意大的數字壓縮到組元素當中，甚至可以壓縮比組元素大得多的數字，這樣就不會被“欺騙”。從VDF到累加器，從范圍證明到多項式承諾的構造，都可在此基礎上構建。另一種選擇是使用防彈證明，使用常規的橢圓曲線組，代價是驗證所需的時間要長得多。因為多項式承諾比完全零知識證明方案要簡單得多，我們可以期望將來會有更多這樣的方案被創建出來。

概括

最后，我們再討論一下這個方案，給定一個程序P，將其轉換為一個電路，并生成一組如下所示的方程：

然后將這組方程轉換為一個多項式方程：

你還可以從回路中生成復制約束的列表。從這些復制約束生成表示排列線指數的三個多項式：σa(x),σb(x),σc(x)。要生成證明，需要計算所有線的值，并將其轉換為三個多項式：a(x),b(x),c(x)。作為置換檢查參數的一部分，你還可以計算六個“坐標對累加器”多項式。最后計算輔因子Hi(x)。

多項式之間有一組方程需要檢查，你可以通過對多項式作出承諾，在某些隨機z處打開它們，并在這些求值結果上運行方程，而不是在原始多項式上運行方程來完成這項工作。證明本身只是一些承諾和opening，可以用幾個方程式來檢查，就是這些啦。

Tags：VITATALIITAVITcurriculum-vitaeVitalick NeuterinRadiant CapitalGravityCoin

TRX