Vitalik：以太坊狀態爆炸問題，多項式承諾方案可解決 | 火星技術帖

免責聲明：本文旨在傳遞更多市場信息，不構成任何投資建議。文章僅代表作者觀點，不代表火星財經官方立場。

小編：記得關注哦

來源：巴比特

原文標題：Vitalik：以太坊狀態爆炸問題，多項式承諾方案可解決

作者：Vitalik Buterin

翻譯：洒脫喜

寫在前面：為了應對以太坊的狀態爆炸問題，以太坊聯合創始人Vitalik提出了新的解決方案，其提議使用多項式承諾（polynomial commitments）方案來替代默克爾樹（Merkle tree），以此大大減少無狀態以太坊客戶端的見證數據（witnesses）。

（圖：以太坊聯合創始人Vitalik Buterin）

（提示：文章有很多公式，譯文僅供參考，以原文為準）

以下為譯文：

關於這一研究，這裡要感謝很多人提供的幫助，尤其是（1）AZTEC團隊向我介紹了複製約束（ copy constraint）參數、排序參數以及有效的批範圍證明方法； （2）Datery Khovratovich和Justin Drake在Kate 承諾部分提供的方案，（3）Eli ben Sasson關於FRI提供的反饋，以及（4）Justin Drake進行的審查工作。這篇文章只是第一次嘗試，如果有進一步的重要思考，我確實希望該方案能夠被類似但更好的計劃所取代。

太煩不看版總結：

我們建議用稱為「多項式承諾」（polynomial commitments）的神奇數學來替代默克爾樹（Merkle tree）來累積區塊鏈狀態。好處包括：將無狀態客戶端的見證內容（witnesses）的大小減少到接近於零。這篇文章提出了利用多項式承諾進行狀態累積所存在的挑戰，並提出了具體的構建方法。

什麼是多項式承諾（polynomial commitments）？

多項式承諾是多項式P（x）的一種『哈希』，其具有可對哈希執行算術檢查的屬性。

例如，在三個多項式P（x），Q（x），R（x）上，給定三個多項式承諾h_P = commit(P(x)), h_Q = commit(Q(x)),h_R = commit(R(x))，然後：

1. 如果P(x) + Q(x) = R(x)，你可以生成一個證明（proof），證明它和h_P, h_Q, h_R的關係（在某些構造中，你可以簡單地檢查h_P + h_Q = h_R）；
2. 如果P(x) * Q(x) = R(x)，你可以生成一個證明（proof），證明它和h_P, h_Q, h_R的關係；
3. 如果P(z) = a ，你可以針對h_P生產一個證明（稱為開放證明opening proof或簡稱opening）

你可以將多項式承諾用作vector承諾，類似於默克爾樹（Merkle tree）。多項式承諾的一個主要優點是，由於其數學結構的原因，其生成複雜證明要容易得多。

有哪些流行的多項式承諾方案？

當前有兩個領跑者，它們分別是Kate承諾（在這篇文章中搜索 「Kate」）以及基於FRI的承諾。你可能還聽說過防彈證明（Bulletproofs）和DARKs算法，這些是替代型多項式承諾方案。而要了解有關多項式承諾的更多信息，YouTube上有相關的內容（part 1，part 2，part 3，以及幻燈片）。

多項式承諾在以太坊中有哪些容易應用的場景？

我們可以用多項式承諾來替換目前區塊數據的默克爾根（例如以太坊2.0的分片區塊），並用開放證明替換默克爾分支（Merkle branches）。這給我們帶來了兩個很大的優勢。首先，數據可用性檢查會變得容易，並且不會存在欺詐，因為你可以簡單地以隨機方式（例如一個N次多項式的2N個坐標中的40個）請求開放。非交互式的託管證明也可能變得更容易。

其次，說服多數據片段的輕客戶端也變得更加容易，因為你可以製造一個同時涵蓋多個索引的有效證明。對於任何集{(x_1, y_1), ..., (x_k, y_k)}，定義三個多項式：

1. 通過所有這些點的插值多項式I(x)；
2. 在x_1，...，x_k等於0的零多項式Z（x）=（x-x_1）* ... *（x-x_k）；
3. 商多項式Q（x）=（P（x）-I（x））/Z（x）；

商多項式 Q（x）的存在，意味着P(x) - I(x)是Z（x）的倍數，因此P（x）-I（x）為零，其中Z(x) 為零。這意味着對於所有i，我們都有P(x_i) - y_i = 0，即P(x_i) = y_i。驗證者（verifier）可以生成插值多項式和零多項式。證明（proof）由對商的承諾，加上隨機點z上的開放證明組成，因此，我們可以對任意多個點擁有一個常數大小的見證內容（witness）。

這種技術可以為區塊數據的多次訪問提供一些好處。然而，其對於一種不同的用例而言，存在的優勢就要大得多：證明區塊交易賬戶witness。平均而言，每個區塊會訪問數百個賬戶和存儲密鑰，這導致潛在的無狀態客戶端的見證內容大小會有0.5 MB大小。而多項式承諾多見證（multi-witness），根據方案的不同，可以將區塊witness的大小從數萬位元組減少到幾百位元組。

那我們可以使用多項式承諾來存儲狀態嗎？

大體上，我們是可以的。相比將狀態存儲為默克爾樹（Merkle tree），我們選擇將狀態存儲為兩個多項式S_k(x) 和S_v(x)，其中S_k（1），...，S_k（N）表示鍵（key），而S_v（1），.. 。，S_v（N）表示這些鍵（key）上的值（如果值大於字段大小，則至少表示這些值的哈希值）。

為了證明鍵值對（k_1，v_1），...，（k_k，v_k）是狀態的一部分，我們將提供索引i_1, ..., i_k 並（使用上面提到的插值技術）顯示與索引匹配的鍵和值，即k_1 = S_k(i_1), ..., k_k = S_k(i_k) 和v_1 = S_v(i_1), ..., v_k = S_v(i_k)。

為了證明某些鍵（key）的非成員性，可以嘗試構造一個奇特的證明，證明鍵（key）不在S_k（1），…，S_k（N）中。相反，我們只需對鍵（key）進行排序，以便證明非成員身份就足以證明兩個相鄰key的成員身份，一個小於目標key，一個則大於目標key。

而這和Justin Drake提出的使用SNARKs/STARKs來壓縮witness以及相關的想法有着相似的好處，另外一個好處是，由於證明是累加器密碼學原生的，而不是構建在累加器密碼學上的證明，因此這消除了一個數量級的開銷，並移除了對零知識證明友好哈希函數的需求。

但這裡存在着兩個大問題：

1. 為k個密鑰生成witness需要的時間是O（N），其中N是狀態的大小。而預計N對應的狀態數據會有大約50 GB，因此在單個區塊中生成這樣的證明是不實際的；
2. 2、用k個新值更新S_k(x)和S_v(x)花費的時間也需要O（N）。這在單個區塊中是不切實際的，特別是考慮到諸如witness更新和重新排序之類的複雜性。

下面我們將介紹應對這兩大問題的解決方案。

高效讀取（Efficient reading）

我們提供了兩種解決方案，一種針對Kate承諾而設計，另一種則是針對基於FRI的承諾。不幸的是，這些方案具有不同的優點和缺點，從而會導致不同的屬性。

1、Kate承諾

首先，請注意，對於N次多項式f，有一種方案可生成N個對應於 O(N * log(N))時間中每個q_i(x) = (f(x) - f(i)) / (X - i)的開放證明。

還請注意，我們可以按以下方式合併witness。考慮這樣一個事實，q_i(x)只是一個離開f（x）/（X-i）的子常數（sub-constant）項，通常，已知f/((X - x_1) * ... * (X - x_k))是f /（X-x_1），...，f /（X-x_k）使用部分分式分解（ partial fraction decomposition）的某種線性組合。只需知道x坐標就可以確定具體的線性組合：只需提出一個線性組合c_1 * (x - x_2) * ... * (x - x_k) + c_2 * (x - x_1) * (x - x_3) * ... * (x - x_k) + ... + c_k * (x - x_1) * ... * (x - x_{k-1})，其中不存在非常數項，這是k個未知數中的k方程組。

給定這樣的線性組合，我們得到的東西僅是離開f/((x - x_1) * ... * (x - x_k))的一個子常數項（因為所有原始誤差都是子常數的，所以線性錯誤的組合必然是sub-constant），因此它必然是商 f(x) // ((x - x_1) * ... * (x - x_k))，其等於期望值(f(x) - I(x_1 ... x_k, y_1 ... y_k)) / ((x - x_1) * ... * (x - x_k))。

一個可能的挑戰是，對於大的狀態，一個實際可計算的單一可信設置（例如，100多個獨立參與者，因此只要其中任何一個是誠實的，方案就是安全的）是不夠大的：例如，PLONK設置只能容納約3.2 GB。相反，我們可以有一個由多個Kate承諾組成的狀態。

我們對很多承諾作如下單一witness。為證明

我們將所有我們關心的值存儲在位置 (x, x**sqrt(N))，因此它們都具有唯一的x坐標。（請注意，在很多情況下，這些位置會超出我們承諾求值的4*sqrt(N) by 4*sqrt(N) square，而這無關緊要。）

為了證明在一組點x_1, ..., x_k上的求值，我們構造了一個k次多項式路徑（x），其在x_i處的求值為x_i ** sqrt（N）。

然後，我們創建一個多項式 h(t) = F(t, path(t))，其中包含對(x_i, y_i)的所有期望求值，並且具有k*（1+sqrt（N））次。

我們在求值域中選擇隨機的30列c_1 ... c_k，對於每列查詢30個隨機行。我們承諾於h（使用FRI證明它實際上是一個多項式），為z_i = h(c_i)提供一個多開口（multi-opening），並對列商 (R_i - z_i) / (X - path(c_i))進行FRI隨機線性組合，以驗證h（c_i）的聲明值是正確的，因此h(t) 實際上等於F(t, path(t))。

使用二維多項式的原因是，這確保了我們不必對所有F進行任何計算；相反，我們只需要對我們選擇的隨機30行F進行計算（即30*sqrt（N）），加上階為 p * (sqrt(N) + 1)的h，創建FRI進行的計算大約為p * sqrt(N) 。可以將此技術擴展到二維以上的多項式，以將sqrt因子降低到更低的指數。

高效寫入（Efficient writing）

我們通過一系列的承諾，來解決與更新包含整個狀態的單個承諾相關的挑戰，較大的承諾，其更新頻率也就較低：

1. 區塊本身，具有「讀取見證」(R_k(x),R_v(x))和「寫入見證」（W_k（x），W_v（x）），表示要寫入狀態的值。注意，我們可以設置W_k = R_k，並在運行時計算W_v。
2. 第一個緩存C1 =（C1_k（x），C1_v（x））存儲最近一天的更新內容；
3. 第二個緩存C2等於前一天的最後一個C1；
4. 滿狀態S = （S_k（x），S_v（x））包含時間超過1-2天的值；

我們將使用的方法如下。為了從狀態中讀取一些鍵k，我們將依次讀取 C1,C2,S。如果鍵位於某C1_k（x）處，則對應的值C1_v（x）存儲該值，如果鍵位於C2_k（x），則C2_v（x）存儲該值，依此類推，如果鍵位於S_k（x），則S_v（x）存儲該值。如果這些檢查都沒有返回鍵，則該值為0。

複製約束（copy constraint）參數的簡介

複製約束參數，是我們將使用的witness更新證明的關鍵組成部分；有關複製約束參數如何工作的詳細信息，請參見此處。簡而言之，該想法是選擇一個隨機r，並生成一個「累加」多項式ACC（x），其中ACC（0）= 1 且ACC（x + 1）= ACC（x）*（r + P（x））。你可以通過開放讀取ACC(y) / ACC(x)，來讀取x .... y-1範圍內的點累加器。你可以使用這些累加器值，將這些求值與其他求值集（作為多集）進行比較，而無需考慮排列。

你還可以通過設置 ACC(x+1) = ACC(x) * (r + P_1(x) + r2 * P_2(x))來證明某些隨機r和r2的求值元組（即多集{(P_1(0), P_2(0)), (P_1(1), P_2(1)), ...}）的等價性。多項式承諾可有效用於證明有關ACC的主張。

為了證明子集，我們可以做相同的事情，除了我們還要提供一個指標多項式ind（x），證明該ind(x)在整個範圍內等於0或1，並設置ACC（x + 1）= ACC（x ）*（ind（x）*（r + P（x））+（1-ind（x）））（即，如果指標為1，則在每一步乘以r + P（x），否則不使用累加器值）。

小結：

1. 我們可以證明a和b之間的P（x）求值，是a和b（或某些不同的c和d）之間Q（x）求值的置換；
2. 我們可以證明a和b之間的P（x）求值，是a和b（或一些不同的c和d）之間Q（x）求值置換的子集；
3. 我們可以證明P（x）和Q（x）的求值，是R（x）和S（x）置換，其中P-> Q和R-> S是相同的置換；

在下面的內容中，除非明確說明，否則我們將偷懶地表述為「P是Q的置換」，意思是「P在0和k之間的求值，是Q在0和k之間對適當k求值的置換」。請注意，下面的內容中，我們還會涉及到每個witness的「大小」，以確定我們接受的任何 C_k中的坐標，而超出範圍的C_k（x）值當然不計算在內。

映射合併參數（Map merging argument）

為了更新緩存，我們使用了「映射合併參數」。給定兩個映射A=（A_k（x），A_v（x））和B=（B_k（x），B_v（x）），生成合併映射C=（C_k（x），C_v（x））以便：

1. C_k中的鍵被分類；
2. 對於0
3. 對於0

我們用一系列複製約束參數來實現這一點。首先，我們生成兩個輔助多項式 U（x），I（x），它們分別表示A_k和B_k的「並集」和「交集」。將A_k，B_k，C_k，U，I視為集合，我們首先需要展示：

1、A_k ⊆ U；

2、B_k ⊆ U；

3、I ⊆ A_k；

4、I ⊆ B_k；

5、A_k + B_k = U + I；

我們預先假設在A_k和B_k中沒有重複，這意味着A_k（i）！= A_j（j）對於範圍內的i！= j與B_k相同（因為在之前使用此算法時已對此進行了驗證）。由於I是A_k和B_k的子集，所以我們已經知道I也沒有重複的值。通過使用另一個複製約束參數來證明U和C_k之間的等價關係，證明了U中沒有重複項，並證明C_k是已排序且無重複的。我們用一個簡單的複製約束參數證明A_k + B_k = U + I聲明。

為了證明C_k已排序且沒有重複，我們證明C_k（x + 1）> C_k（x）的範圍為0 ... size（C_k）。我們通過生成多項式D_1（x），...，D_16（x），並證明C（x + 1）-C（x）= 1 + D_1（x）+ 2 ** 16 * D_2（x）+ 2 ** 32 * D_3（x）+...來做到這一點。本質上，D_1（z），...，D_16（z）將差異存儲在基2**16中。然後，我們生成一個多項式E（x），其滿足所有D_1，...，D_16的複製約束以及f（x）= x，並且滿足 E(x+1) - E(x) = {0, 1}限制（對E的2次約束）。我們還檢查了E（0）= 0以及E（size（C_k）* 16 + 65536）= 65535。

關於E的約束表明，E中的所有值都夾在0和65535（包括0和65535）之間。對 D_i的複製約束，證明D_i（x）中的所有值都在0到65535（含）之間，這證明了它是一個正確的16進制表示，從而證明了C_k（x+1）-C_k（x）實際上是一個正數。

現在，我們需要證明value（值）。我們添加另一個多項式U_v（x），並驗證：

1. 在0...size(B)的(U, U_v)等於在0...size(B)的(B_k, B_v)；
2. 在size(B) ... size(A)+size(B) 的(U, U_v)，是（A_k，A_v）在0...size(A)的一個子集；

目標是在 U中，我們先放置來自B的所有值，然後再放置來自A的值，並使用相同的置換參數來確保鍵（key）和值（value）被正確複製。然後我們驗證（C_k，C_v）是（U，U v）的一個置換。

使用映射合併參數

我們按照下面的方式使用映射合併參數，假設每天有BLOCKS_PER_DAY個區塊。

1. 如果block.number % BLOCKS_PER_DAY != 0，我們驗證(C1_k, C1_v) = merge((W_k, W_v), (C1_old_k, C1_old_v))（將區塊合併到C1）；
2. 如果block.number % BLOCKS_PER_DAY == 0，我們驗證(C1_k, C1_v) = (W_k, W_v)以及(C2_k, C2_v) = (C1_old_k, C1_old_v) （也就是說，我們「清除」 C1並將其內容移入C2）；

請注意，C2具有一整天的時間，在此期間它保持不變。我們為任何人產生 （S_k，S_v）= merge（（S_old_k，S_old_v），（C2_k，C2_v））的證明提供獎勵；提供此證明後，我們將承諾（S_k，S_v）更新為新值，並將（C2_k，C2_v）重置為空。如果S在當天沒有更新，則我們將C1-> C2傳輸延遲到更新為止；請注意，該協議確實取決於S的更新速度是否足夠快。如果這不可能發生，那麼我們可以通過添加更多層緩存的層次結構來解決這個問題。

從糟糕的FRI中恢復

對於FRI的情況，注意，有可能會出現有人生成的FRI在某些位置無效，但這不足以阻止驗證。這不會立即造成安全風險，但可能會阻止下一個更新者生成witness。

我們通過以下幾種方法來解決這個問題。首先，注意到某些FRI生成錯誤的人，可提供自己的FRI。如果通過相同的檢查，它將被添加到可構建下一次更新的有效FRI列表中。然後，我們可以使用交互式計算遊戲來檢測和懲罰不良FRI的創建者。其次，他們可提供自己的FRI以及STARK來證明其有效，從而立即罰沒了無效FRI的創建者。通過FRI生成STARK是非常昂貴的，尤其是在較大規模時，但這樣做是值得的，因為這可以賺取很大一部分無效提議者的保證金獎勵。

因此，我們有了一種機制來使用多項式承諾，以此作為一個有效讀取和寫入witness來存儲狀態。這使我們能夠大幅度減少見證內容（witness）大小，同時也可以帶來一些好處，比如讓我們有能力對數據可用性進行檢查，以及實現關於狀態的託管證明。

今後的工作

1. 提出FRI證明，要求少於900次查詢（更正式地講，安全參數小於平方）；
2. 從理論上講，如果你預先計算並存儲拉格朗日基（Lagrange basis），理論上可以快速更新 Kate承諾。這是否可以擴展到（i）快速更新所有witness，以及（2）為鍵值映射而不是一個vector工作？