V神新作：一文了解什么是\tPLONK_LON

摘要：零知識證明新突破。

今年8月底，AZTEC協議官推宣布，開發出了PLONK，這是一種全新的高效通用ZK-SNARK架構。PLONK只需要一個可信設置，所有程序都可以重復使用這個設置。PLONK足以在以太坊上被實際采用。

以太坊2.0研究員JustinDrake稱，PLONK是一種全新的零知識證明系統，支持通用或可更新的可信設置，而且相比Sonic有顯著的性能提升。這將會是在真實環境中使用零知識證明的一個巨大進步，并且不會由于可信設置而產生信任問題。

鑒于零知識證明技術衍生出了太多的術語名詞，在使用中很容易被混淆。近日，以太坊創始人V神在其博客上發布了一篇名為“understandPLONK”的文章，以便人們更容易了解到底什么是PLONK。

以下為該博客全文：

最近，ArielGabizon、ZacWilliamson和OanaCiobotaru宣布了一種新的通用的零知識證明方案PLONK。

雖然通用零知識證明協議已經改進多年，但PLONK(以及更早但更復雜的Sonic和最近的Marlin)帶來的是一系列的增強，可以極大地提高這些類型證明的可用性和進展。

第一個改進是，雖然PLONK仍然與Zcash中的snark有著類似的可信設置過程，但它是一個“通用的、可更新的”可信設置。

這意味著兩件事：

1、你想證明的不是每個程序都有一個獨立的可信設置，整個方案只有一個可信的設置，在此之后，您可以將該方案用于任何程序(在進行設置時選擇的最大尺寸)。

2、有一種方法可以讓多方參與受信任的設置，只要其中一方是誠實的，那么該設置就是安全的，而且這種多方參與的過程是完全按順序的:第一個人參與，然后是第二個，然后是第三個……所有參與者甚至不需要提前知道;新參與者可以把自己加到最后。這使得可信設置很容易擁有大量參與者，從而在實踐中非常安全。

第二個改進是它所依賴的“fancycryptography”是一個單一的標準化組件，被稱為“polynomialcommitment”。

PLONK使用“Katecommitment”，基于可信設置和橢圓曲線配對，但你可以用其他方案替換它，比如FRI(這將使PLONK變成一種STARK)或DARK(基于隱藏順序組)。這意味著該方案在理論上兼容證明大小和安全性假設之間的任何(可實現的)折中。

V神：第一批支持EVM的Rollup或將于3月上線:2月19日，V神在社區中表示，第一批支持EVM的Rollup或將于3月上線，上線之后將降低99%的交易費用。同時，V神還表示，Optimism和arbitrum處于領先位置。[2021/2/19 17:31:29]

這意味著需要在證明大小和安全假設之間進行不同權衡的用例(或者對于這個問題有不同意識形態立場的開發人員)仍然可以共享大部分相同的“算術化”工具——將一個程序轉換成一組多項式方程的過程，然后用多項式承諾來檢查這些方程。如果這種方案被廣泛采用，我們可以期待在改進共享算術化技術方面取得快速進展。

PLONK是怎樣工作的

讓我們從解釋PLONK是如何工作開始，以某種抽象的格式，側重于多項式方程，而不是立即解釋如何驗證這些方程。

PLONK的一個關鍵組成部分，就像snark中使用的QAPs一樣，是一個轉換問題形式的過程，從“給一個值X，使用特定程序P，當用X作為輸入求值時，得到特定的結果Y。”變成了"給我一組值滿足一組數學方程"。

程序P可以表示很多東西，例如，問題可以是“給我一個sudoku的解”，你可以通過設置P為一個sudoku驗證器加上一些初始值編碼，并設置Y為1(即："是的，這個解是正確的")，

一個令人滿意的輸入X將是sudoku的有效解。這是通過把P表示成一個帶邏輯門的電路，用于加法和乘法，并把它轉換成一個方程組，其中變量是所有導線上的值，每個門有一個方程(例如：x6=x4*x7，加法x8=x5x9)。

。Vitalik在2016年寫過的QAP介紹，深入淺出的解釋NP問題的算術電路生成和QAP問題的轉化）

下面是一個求x的例子，P(x)=x**3x5=35(提示:x=3):

我們可以給這些門和電路貼上如下標簽:

在門和電路上，我們有兩種約束:門約束(同一門上的電路之間的方程式，例如：a1*b1=c1)和復制約束(關于電路中任意位置不同電線的相等性的聲明，例如：a0=a1=b1=b2=a3或c0=a1)。我們將需要創建一個結構化的方程組，它最終將減少到一個非常少的多項式方程，以表示兩者。

在PLONK中，這些方程的設置如下。每個方程的形式如下(想想:L=左，R=右，O=輸出，M=乘法，C=常數):

動態 | V神反對將Defi抵押倉位稱為借貸：傳統借貸要還，Defi是杠桿交易:近日美國媒體Mashable發布了一篇名為《我沒有簽文件、沒有見人就借到了一筆錢》的文章，文章內描述了作者如何使用Compound借出一筆資金的事情，在這個過程中，貸款者不需要向任何機構提出申請，也不需要簽署任何文件就可以輕松地借到DAI穩定幣。 但該文章所描述的內容引發了以太坊創始人Vitalik（V神）的異見，他認為“媒體認為 DeFi 可以讓人不簽任何文件就貸出錢的說法不妥。主要原因是傳統的借貸需要簽署一些文件來確定貸款者可以清償債務，而在 DeFi 里，數字資產一直都在用戶手里，只是加了杠桿的倉位罷了”。 V神表示：”傳統貸款和 Defi 的區別在于，房子是不可以再分的，再加上貸款買房的時候房子也有人住，這就讓 Defi 和貸款在量數上產生了不同。“為此，Vitalik 將這種通過 DeFi 貸出資金的行為稱之為”CDP 抵押倉位“以及”主動杠桿交易“，并表示自己一直以來都反對在 DeFi 上使用借貸一詞。[2020/1/30]

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

把這些常數代入方程，化簡得到aibi-oi=0，這正是我們想要的約束條件。對于乘法門，我們設:

對于將ai設為某常數x的常數門，我們設:

您可能已經注意到，一根電路的每一端以及一組電路中的每一根電路都必須具有相同的值(例如，對應一個不同的變量。到目前為止，還沒有強迫一個門的輸出與另一個門的輸入相同的東西(我們稱之為“復制約束”)。

PLONK當然有一種強制執行副本約束的方法，但是我們將在稍后進行討論。現在我們有一個問題，驗證者想要證明他們有一堆xai、xbi、xci值滿足一堆相同形式的方程。這仍然是一個大問題，但與“為這個計算機程序找到一個滿意的輸入”不同，這是一個非常結構化的大問題，我們有數學工具來“壓縮”它。

從線性系統到多項式

如果您已經閱讀過關于STARKs或QAPs的內容，那么在下一節中描述的機制可能會讓您感到有些熟悉，但是如果沒有，也沒有關系。這里的主要內容是將多項式理解為一個數學工具，用于將大量的值封裝到一個對象中。通常，我們認為多項式的“系數形式”，這是一個表達式，如:

現場丨V神：對以太坊可以有的多個期待:金色財經現場報道，在9月18日的2019第五屆區塊鏈全球峰會上，以太坊創始人Vitalik Buterin介紹了未來對以太坊可以有的期待：更好、更可信的數據來源，讓應用更好更便捷地與真實世界連接；以太坊上的PoS和分片擴容技術；更多智能錢包、智能融資合約等等；現有的交易所可用零知識證明提高自身的安全性；去中心化應用會比中心化的應用更友好。[2019/9/18]

但我們也可以在“求值表”中查看多項式。例如，我們可以把上面的看成是在坐標(0,1,2,3)處分別求值(-2,1,0,1)的<4次多項式。

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

讓我們定義四個多項式的求值形式:

L(x)是在坐標(0,1,2)處取值為(2,1,8)的次數<3多項式。在相同的坐標下，M(x)的值為(-1，4，1)，R(w)為(3，-5，-1)和O(x)為(8，5，-2)(這樣直接定義多項式是可以的，可以使用拉格朗日定理將其轉換為系數形式)。現在，考慮這個等式:

這里，Z(x)是(x)*(x-1)*(x-2)的縮寫——-在計算域(0,1,2)上返回0的最小(非平凡)多項式。這個方程(x1=1,x2=6,x3=4H(x)=0)的解也是原方程組的解，只是原方程組不需要H(x)。

還要注意，在這種情況下，H(x)很方便地為零，但在更復雜的情況下，H可能需要非零。

現在我們知道，我們可以用一小部分數學對象(多項式)來表示大量的約束條件。但是在我們上面用來表示門約束的方程中，每個方程的x1,x2,x3變量是不同的。我們可以通過使變量本身多項式而不是常數來處理這個問題。所以我們得到:

和以前一樣，每個Q多項式都是一個參數，可以從正在驗證的程序中生成，而a、b、c多項式是用戶提供的輸入。

復制約束

現在，讓我們回到“連接”電路。到目前為止，我們所擁有的只是一堆關于不相交值的不相交方程，它們很容易獨立滿足:常數門可以通過將值設置為常數來滿足，加法和乘法門可以通過將所有線設置為零來滿足！為了使問題真正具有挑戰性(并實際表示在原始電路中編碼的問題)，我們需要添加一個驗證“復制約束”的方程:約束如a(5)=c(7)，c(10)=c(12)，等等。這需要一些巧妙的技巧。

聲音 | V神：Serenity將分四個階段推出:據Coindesk報道，V神透露，Serenity將分四個階段推出。第一階段被稱為零階段，將引入“信標鏈”，新的基于股權證明的區塊鏈將與以太坊本身共存，并允許卡斯珀驗證員參與。這是測試網和主網之間的一半，第二階段是Serenity本身的“簡化版本”，其特色是“分片作為數據鏈”，能夠應對數據存儲，但無法將智能合約或資金從一個碎片轉移到另一個碎片。在此之后，第三階段將啟用跨分片通信，意味著用戶通過不同的分片向彼此發送消息和資金。第四個也是最后一個階段只會進行一些調整和優化。[2018/11/1]

我們的策略是設計一個“坐標對累加器”，一個多項式p(x)，其工作原理如下：

首先，設X(X)和Y(X)是兩個多項式，表示一組點的X和Y坐標(例如：要表示集合((0,2)，(1,1)，(2,0)，(3,1))，可以令X(X)=X,Y(X)=x3-5x27x-2))。我們的目標是讓p(x)表示到(但不包括)給定位置的所有點，因此p(0)從1開始，p(1)表示第一個點，p(2)表示第一個和第二個點，我們將通過“隨機”選擇兩個常數，v1和v2，利用約束條件p(0)=1和p(x1)=p(x)*(v1x(x)v2*Y(x))構造p(x)，至少在定義域(0,1,2,3)內。例如，令v1=3,v2=2，得到:

注意(除了第一列)每個p(x)值都等于它左邊的值乘以它左邊和上面的值。

我們關心的結果是p(4)=-240。現在，考慮這樣一種情況，不是X(X)=X，而是X(x)=2?3x3-4x219?3x(即在坐標(0,1,2,3)處取值為(0,3,2,1)的多項式)。如果運行相同的過程，還是會得到p(4)=-240。

這不是巧合(事實上，如果你從一個足夠大的場中隨機選取v1和v2，它幾乎不會碰巧發生)。相反,這是由于Y(1)=Y(3),所以如果你“交換X坐標”的點(1,-1)和(3,1)，你不會改變這些點的集合,因為累加器編碼一個集合(因為乘法不關心順序)，所以最后的值是相同的。

現在我們可以開始學習證明復制約束的基本技術。首先，考慮一個簡單的例子，我們只想證明一組連接中的復制約束(例如：我們要證明a(1)=a(3)。

我們將創建兩個坐標累加器:一個是X(X)=X和Y(X)=a(X)，另一個是Y(X)=a(X)。但X'(X)是一個多項式，它的計算結果是每個復制約束中翻轉(或重新排列)值的排列。在a(1)=a(3)的情況下，這意味著置換將從03214開始…第一個累加器是壓縮），），），），）…第二個），），），），）……只有當a=a時，兩者才能給出相同的結果。

V神：以太坊分區路線圖的第一部分已經快完成:以太坊創始人V神（Vitalik Buterin）近日在一次開發者會議上表示，以太坊部署網絡擴展的新技術已經接近完成。他說，現在第一階段的第一部分幾乎完成了。這項技術被稱為分區（sharding），試圖將以太坊區塊鏈的數據分割成更易管理的幾部分。以太坊正承受著平臺上日益增加的流量，這導致減慢交易速度，交易費增加。會議上，V神還反思了目前正在測試的以太坊的新協議。[2018/1/27]

為了證明a、b和c之間的約束條件，我們使用相同的過程，將三個多項式的點“累加”在一起。我們給a、b、c各指定一個X坐標范圍(例如。a得到Xa(x)=xie.0...n-1,b得到Xb(x)=nx,ie.n...2n-1，c得到Xc(x)=2nx,ie.2n...3n-1。為了證明在不同的連接集之間跳轉的復制約束，“備用”X坐標將是跨所有三個集合排列的切片。例如，如果我們想用n=5證明a(2)=b(4)，那么X’a(x)的值為01934,以及X’b(x)的值為56782(注意2和9翻轉了，其中9對應于b4導線)。

然后，我們將不再在一個過程的運行中檢查等式(即檢查p(4)=p'(4)。如前所述，我們將檢查每邊三種不同運行的乘積:

每邊的三個p(n)值的乘積累加了a、b和c中所有的坐標對，因此，這允許我們像以前一樣進行相同的檢查，除了我們現在可以檢查復制約束，不僅在三組導線a、b或c中的一組內的位置之間，而且在一組導線和另一組導線之間。就像在a(2)=b(4)中一樣。

就是這樣!

把它們放在一起

實際上，所有這些數學運算不是針對整數，而是針對一個素數字段。也不是用x=0...n-1表示電路的指數。

我們將使用ω的能力:1、ω,ω2….ωn-1。其中ω是一個高階root-of-unity。這不會改變數學，除了坐標對累加器約束檢查方程發生了變化。從p(x1)=p(x)*(v1X(x)v2*Y(x))top(ω*x)=p(x)*(v1X(x)v2*Y(x)),而不是使用0..n-1,n..2n-1,2n..3n-1作為坐標，我們使用ωig*ωi和g2*ωig可以是一些隨機的高階元素。。

現在我們把需要檢查的方程都寫出來。首先，主要的門約束滿意度檢查:

然后多項式累加器轉換約束(注意:把“=Z(x)*H(x)”理解為“在我們關心的某個特定域中的所有坐標都等于零，但不一定在它之外”):

然后多項式累加器的啟動和結束約束:

用戶提供的多項式為：

電路分配：a(x)，b(x)，c(x)

累積坐標：Pa(x)，Pb(x)，Pc(x)，Pa(x)，Pb(x)，Pc(x)

Thequotients：H(x)和H1(x)..H6(x)

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

QL(x)、QR(x)、QO(x)、QM(x)、QC(x)，它們一起表示電路中的門(注意QC(x)編碼公共輸入，因此可能需要在運行時計算或修改)

“置換多項式”在a、b和c電線之間，σa(x),σb(x)andσc(x)的編碼復制約束。

注意，驗證器只需要存儲對這些多項式的承諾。唯一剩下的多項式在上面的方程Z(x)=(x-1)*(x-ω)*…*(x-ωn-1)旨在評估所有這些點為零。幸運的是,ω可以選擇把這個多項式很容易評估:通常的方法是選擇滿足ωn=1,在這種情況下,Z(x)=xn-1。

v1和v2的唯一約束是，當v1和v2已知后，用戶不能選擇a(x)、b(x)或c(x)，所以我們可以通過計算從a(x)、b(x)和c(x)的承諾哈希值計算v1和v2來滿足這一點。

現在我們已經把程序滿足問題變成了一個簡單的用多項式來滿足幾個方程的問題，PLONK中有一些優化可以讓我們去掉上面方程中的許多多項式，為了保持簡單，我就不講了。但是多項式本身，包括特定于程序的參數和用戶輸入，都很大。下一個問題是，我們要怎么做才能讓證明更簡短?

多項式承諾

多項式承諾是一個簡短的對象，它“表示”一個多項式，并允許你驗證該多項式的計算結果，而不需要實際包含該多項式中的所有數據。

也就是說，如果有人給你一個代表P(x)的承諾c，他們可以給你一個證明來說服你，對于某個特定的z,P(z)的值是多少。

還有一個進一步的數學結果表明，在一個足夠大的域中，如果關于多項式的某些類型的方程(在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)的開放。一個例子是FRI，另一個例子是Katecommitment，我將在下面描述。為了證明一個開頭，有一個簡單的通用“減法除法”技巧:要證明P(z)=a，需要證明

這也是一個多項式(使用另一個多項式承諾)。這是因為如果quotients是一個多項式，那么x-z是P(x)-a的一個因子，所以(P(x)-a)(z)=0，所以P(z)=a。

用多項式試試，例如：P(x)=x32*x25加上(z=6,a=293)試試(z=6,a=292)看看它是如何失敗的。

還請注意一個泛型優化:為了同時證明多個多項式的多個開口，在提交到輸出之后，對多項式和輸出的隨機線性組合執行減法和除法技巧。

那么承諾本身是如何起作用的呢?幸運的是，Kate承諾比FRI簡單得多。一個可信的設置程序生成一組橢圓曲線點G,G*s,G*s2….G*sn。和G2*s一樣，其中G和G2是兩個橢圓曲線群的生成器，而s是一個秘密，一旦這個過程完成，就會被忘記。(注意，這個設置有一個多方版本，只要至少有一個參與者忘記了他們的秘密，這個設置就是安全的)。

這些要點被公布，并被認為是本計劃的“證明重點”。任何需要做出多項式承諾的人都需要用到這些點。對d次多項式的承諾是將證明鍵的前d1個點乘以多項式中相應的系數，并將結果相加。

注意，這提供了一個多項式在s處的“求值”，而不需要知道s。例如,x32x25可以用(G*s3)2*(G*s2)5*G表示。我們可以使用符號來表示以這種方式編碼的P(即。G*P(s))。做加減乘除運算的技巧時,你實際上可以證明兩個多項式滿足的關系,利用橢圓曲線組合:檢查e(-G*,G2)=e(,-G2*z)作為檢查代理P(x)-a=Q(x)*(x-z)。

但是最近也出現了其他類型的多項式承諾。一種稱為DARK的新方案(“Diophantineknowledgearguments”)使用“隱藏的有序組”來實現另一種多項式承諾。隱藏順序組是唯一的，因為它們允許您將任意大的數字壓縮為組元素，甚至比組元素大得多的偶數，以一種不能“欺騙”的方式;從VDFs到累加器，從范圍證明到多項式承諾，都可以建立在此基礎上。

另一種選擇是使用防彈證明，使用規則橢圓曲線組，代價是證明花費的時間要長得多。由于多項式承諾比完全的零知識證明方案要簡單得多，我們可以期待在未來會產生更多這樣的方案。

回顧

最后，讓我們再看一遍這個計劃。給定一個程序P，你把它轉換成一個電路，然后生成一組這樣的方程:

然后將這組方程轉換成一個多項式方程:

您還可以從電路中生成一個復制約束列表。從這些副本約束生成三個代表交換電路指數多項式:σa(x)，σb(x)，σc(x)。要生成一個證明，需要計算所有這些電路的值并將它們轉換成三個多項式:a(x)，b(x)，c(x)。您還可以計算6個“坐標對累加器”多項式，作為置換檢查參數的一部分。最后計算Hi(x)。

多項式之間有一組方程需要檢查，你可以通過對多項式做出承諾，在任意z點打開它們(并證明這些開口是正確的)，然后在這些計算上運行方程，而不是在原始多項式上運行。證明本身只是一些承諾和開始，可以用幾個方程來檢驗。就是這樣!

原文鏈接：

https://vitalik.ca/general/2019/09/22/plonk.html

作者：VitalikButerin

編譯：共享財經Neo

Tags：LONPLO以太坊DEFELONPLOT以太坊官網公告DeFi11

火必下載