關於這一研究，這裡要感謝很多人提供的幫助，尤其是（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))，然後：
- 如果
p(x) + q(x) = r(x)，你可以生成一個證明（proof），證明它和h_p, h_q, h_r的關係（在某些構造中，你可以簡單地檢查h_p + h_q = h_r）； - 如果
p(x) * q(x) = r(x)，你可以生成一個證明（proof），證明它和h_p, h_q, h_r的關係； - 如果
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)}，定義三個多項式：
- 透過所有這些點的插值多項式
i(x)； - 在
x_1，...，x_k等於0的零多項式z（x）=（x-x_1）* ... *（x-x_k）； - 商多項式
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以及相關的想法有著相似的好處，另外一個好處是，由於證明是累加器密碼學原生的，而不是構建在累加器密碼學上的證明，因此這消除了一個數量級的開銷，並移除了對零知識證明友好雜湊函式的需求。
但這裡存在著兩個大問題：
- 為k個金鑰生成witness需要的時間是
o（n），其中n是狀態的大小。而預計n對應的狀態資料會有大約50 gb，因此在單個區塊中生成這樣的證明是不實際的； - 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。為證明
2、基於fri的承諾
我們將狀態儲存在一個二維多項式f（x，y）的求值中（每個變數的階數為sqrt（n）），並致力於對4*sqrt(n) by 4*sqrt(n) square求值f。
我們將所有我們關心的值儲存在位置 (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）
我們透過一系列的承諾，來解決與更新包含整個狀態的單個承諾相關的挑戰，較大的承諾，其更新頻率也就較低：
- 區塊本身，具有“讀取見證”
(r_k(x),r_v(x))和“寫入見證”（w_k（x），w_v（x）），表示要寫入狀態的值。注意，我們可以設定w_k = r_k，並在執行時計算w_v。 - 第一個快取
c1 =（c1_k（x），c1_v（x））儲存最近一天的更新內容； - 第二個快取c2等於前一天的最後一個c1；
- 滿狀態
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），否則不使用累加器值）。
小結：
- 我們可以證明a和b之間的p（x）求值，是a和b（或某些不同的c和d）之間q（x）求值的置換；
- 我們可以證明a和b之間的p（x）求值，是a和b（或一些不同的c和d）之間q（x）求值置換的子集；
- 我們可以證明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））以便：
c_k中的鍵被分類；- 對於0 <= i < size(b)，(b_k(i), b_v(i)) 在c中；
- 對於0 <= i < size(a)，僅當 a_k(i)不在b的求值集之內時，(a_k(i), a_v(i))在c中；
我們用一系列複製約束引數來實現這一點。首先，我們生成兩個輔助多項式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），並驗證：
- 在
0...size(b)的(u, u_v)等於在0...size(b)的(b_k, b_v)； - 在
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個區塊。
- 如果
block.number % blocks_per_day != 0，我們驗證(c1_k, c1_v) = merge((w_k, w_v), (c1_old_k, c1_old_v))（將區塊合併到c1）； - 如果
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）大小，同時也可以帶來一些好處，比如讓我們有能力對資料可用性進行檢查，以及實現關於狀態的託管證明。
