a16z：關於無狀態區塊鏈不可能性的研究

作者：Miranda ChristJoseph Bonneau / 來源：https://a16zcrypto.com/posts/article/on-the-impossibility-of

隨著區塊鏈的發展以支援更多的使用者和更頻繁的交易，驗證體存儲以驗證交易的資訊量（“狀態”）也隨之增加。 例如，在比特幣中，狀態由一組未花費的交易輸出（UTXO）組成。 在以太坊中，狀態由每個帳戶的賬戶餘額以及每個智慧合約的代碼和存儲組成。

對於擁有足夠帳戶或UTXO來支援大部分人口真正日常交易的區塊鏈來說，這種存儲負擔將變得難以處理，從而使其難以成為驗證者、並對去中心化構成威脅。 人們很容易轉向密碼學作為解決方案，默克爾樹和零知識證明等工具已經幫助我們實現了以前難以置信的目標。

而這也是「無狀態區塊鏈」 的目標。 儘管對它們進行了大量工作，但它們仍然未投入實用。 但事實證明，這種進展的滯後是固有的——這些結構與實用性之間的差距永遠無法彌合。 我們最近的工作表明，如果沒有額外的措施來管理狀態，任何無狀態區塊鏈方案，無論多麼聰明，都是不可行的。 不過，正如我們在本文末尾所展示的那樣，這種不可能的結果不應令人沮喪。

1、無狀態區塊鏈狀態

如今，國家規模龐大但易於管理。 例如，比特幣節點存儲約 7 GB的數據，以太坊節點存儲約 650 GB 的數據。 但全節點的存儲負擔隨著鏈的輸送量（每秒交易數或 TPS）大致呈線性增加，而目前該輸送量低得令人無法接受。 根據當前的設計，真正支援日常交易（數萬到數十萬 TPS）所需的狀態將非常笨重，需要 TB 甚至 PB。

這促使人們尋找技術方法來大幅減少驗證者所需的狀態量。 聖杯是無狀態區塊鏈，它要求驗證體僅存儲恆定大小的狀態，而不管事務輸送量如何。 （這個術語實際是一個誤稱：仍然存在一個狀態，它足夠小，足以在任何未來的輸送量下實用 - 通常它是恆定大小的。 ）

這樣的輕存儲要求將使運行驗證器節點變得更加容易; 樂觀的是每個人都可以在他們的手機上運行一個節點。 由於增加驗證者的數量可以提高鏈的安全性，因此降低驗證者的進入門檻非常重要。

儘管對無狀態區塊鏈進行了大量研究（例如，Todd、Buterin、Boneh 等人、Srinivasan 等人），但它們距離實用還很遠，據我們所知，沒有一個被部署。 所有已知的無狀態區塊鏈的根本問題是它們要求使用者存儲稱為見證人的額外數據，以幫助驗證者驗證涉及其帳戶的交易。 例如，該見證人可能是 Merkle 包含證明，表明使用者的帳戶及其餘額包含在全域狀態承諾中。 當用戶進行交易時，他們將這個見證提交給驗證者，表明他們的帳戶有足夠的餘額。

與存儲永遠不需要更改的私鑰不同，這些見證人經常更改，即使對於不積極進行交易的使用者也是如此，這給用戶帶來了很大的負擔。 同樣，想像一下，如果您必須持續監控全球所有其他信用卡交易並相應更新一些本地數據才能使用您自己的信用卡。 為了讓區塊鏈變得實用，用戶必須能夠保持離線狀態，並且只有在提交交易時才能與區塊鏈進行交互。 在許多情況下，就像硬體錢包一樣，更新見證不僅不方便而且不可能。

這給我們帶來了一個自然的研究問題：我們能否構建一個不需要見證人更新（或很少需要見證人更新）的無狀態區塊鏈？ 為了回答這個問題，我們開發了一個新穎的理論框架（可撤銷證明系統）來概括無狀態區塊鏈。 使用這個框架，我們證明瞭一個結論性的不可能結果：簡潔的全域狀態和頻繁的見證更新之間的權衡是根本性的。 我們的證明技術是資訊論的，這意味著未來的計算機都不會強大到足以解決這個問題：無狀態區塊鏈結構和實用性之間的差距永遠無法彌合。

2、我們的研究背景

為了幫助我們對不可能的結果建立直覺，我們將首先描述使用Merkle 樹構建無狀態區塊鏈的自然但低效的構造。 我們的目標是讓驗證者確定使用者提交的交易是否有效——例如，使用者有足夠大的賬戶餘額來進行交易。 在無狀態區塊鏈方案中，驗證體存儲恆定大小的狀態。 當使用者進行交易時，他們必須在交易中包含一個見證人。 驗證器可以使用當前狀態和使用者提交的（交易、見證人）對來驗證該使用者是否有足夠的賬戶餘額來進行交易。

我們首先構建一棵 Merkle 樹，其中每個（帳戶 ID，餘額）對（a，b）都作為葉子包含在內。 驗證體存儲的恆定大小的狀態V是該樹的根，它充當對帳戶餘額對集的承諾。 每個使用者都維護其（帳戶 ID、餘額）對的 Merkle 包含證明作為其見證人。 葉子 （ a ， b ） 的 Merkle 包含證明由沿著其到樹根的路徑上的夥伴節點 （ v 1 ， ...， v k ） 組成。 給定使用者使用帳戶a進行的交易並聲明餘額b，驗證器可以檢查b通過檢查 （ a ， b ）的證明 （ v 1 ， ...， v k ）與其當前狀態V ，確實是帳戶a的餘額。 如果是這樣，驗證器將執行交易並必須相應地更新帳戶餘額。 Merkle 樹的一個便利屬性是，給定葉子的 Merkle 包含證明，當該葉子發生更改時，很容易計算生成的根。 換句話說，驗證者可以輕鬆計算更新后的狀態V' ，該狀態V'在交易執行后捕獲帳戶 a 的新餘額。

這種默克爾樹方案有兩個主要缺點。 首先，用戶的見證人規模較大，在系統賬戶總數中呈對數增長。 理想情況下，它們應該是恆定大小的，我們可以使用RSA 累加器等方案來實現（ Boneh 等人在無狀態區塊鏈的背景下進行了研究）。

第二個缺點更難以避免：賬戶餘額對的證明只要發生任何變化其他使用者交易。 回想一下，葉子的證明由從該葉子到樹根的路徑上的夥伴節點組成。 如果任何其他葉子發生變化，這些節點之一就會發生變化，這在實踐中會出現問題。 大多數區塊鏈使用者希望被動地將他們的硬幣保存在錢包中，並且僅在想要進行交易時才上網。 然而，在這種無狀態區塊鏈的實踐中，用戶必須不斷監控其他人的交易，以使他們的見證人保持最新狀態。 （雖然第三方可以代表用戶進行此監控，但這偏離了標準的無狀態區塊鏈模型。 我們將在本文末尾討論這一點。 ）實際上，這對於無狀態區塊鏈來說是一個難以克服的挑戰，給無狀態區塊鏈帶來了沉重的負擔。 用戶的負擔。

3、我們的結果：無狀態區塊鏈是不可能的

這種現象並不是默克爾樹結構特有的——所有已知的無狀態區塊鏈方案都要求用戶頻繁更新他們的見證人，我們在這裡演示了這一點。 更準確地說，我們表明必須更新見證的用戶數量與所有用戶進行的交易總數大致呈線性增長。

這意味著即使使用者 Alice沒有進行任何交易，她的見證人也可能需要隨著其他使用者的交易而改變。 只要驗證體存儲的簡潔狀態太小而無法捕獲完整狀態（即所有帳戶餘額的集合），增加簡潔狀態大小就沒有什麼説明。 我們按照下面的定理所暗示的那樣繪製了這種關係，以及不同輸送量的區塊鏈每天所需的見證人更改數量。 這些圖顯示了見證人需要更改以獲得最佳無狀態區塊鏈的次數。 這裡，數據宇宙是指賬戶總數（在帳戶模型中）或UTXO（在UTXO模型中）。

我們證明的核心是資訊論論證。 由克勞德·香農 （Claude Shannon）形式化的資訊論核心原理是，如果Alice 從大小為2 n的集合中隨機選擇一個物件，並希望告訴Bob她選擇了哪個物件，她必須向他發送至少n位。 如果存在一個無狀態的區塊鏈方案，其中使用者很少更新他們的見證人，那麼愛麗絲可以使用少於n位告訴鮑勃她選擇了哪個物件。 但是香農證明這是不可能的。 因此，這樣的無狀態區塊鏈不可能存在。

為了簡單起見，我們將在這裡描述一個稍弱的陳述的證明：不可能存在用戶永遠不需要更新其見證人的無狀態區塊鏈。 關鍵思想是愛麗絲使用無狀態區塊鏈方案將她的消息編碼給鮑勃。 最初，Alice 和 Bob 都知道所有n 個使用者的完整帳戶餘額對。 假設每個帳戶至少有一枚幣。 Alice 和Bob也都知道無狀態區塊鏈的簡潔狀態V和所有賬戶餘額對（ a i ， b i ）的見證人 w i。 Alice 和 Bob 還就消息和帳戶集之間的映射達成了一致。 Alice會選擇與她的消息對應的一組A帳戶，然後她會從這些帳戶中花費硬幣。 她將使用無狀態區塊鏈與鮑勃溝通她選擇的集合，而他可以從該集合中瞭解她的消息是什麼。

編碼： Alice 從A的每個賬戶中花費一枚硬幣。 使用無狀態區塊鏈方案，Alice 計算更新后的狀態V『並將V』發送給 Bob。

解碼：對於每個i， Bob 檢查是否Verify（ w i ， （ a i , b i )) 。 Bob 輸出帳戶集合B，使得Verify（ w i ， （ a i ，b i )) = false。

鮑勃成功地輸出了與愛麗絲選擇的相同的集合：B = A。 首先，觀察到如果愛麗絲從帳戶a i中花費了一枚硬幣，則不應再接受其舊餘額的見證人 - 否則，愛麗絲將能夠加倍花費。 因此，對於A中的每個帳戶a i，Verify（ w i , ( a i , b i )) = false，並且 Bob 會將該帳戶包含在B中。 另一方面，Bob 絕不會在B中包含Alice 所識別的帳戶。 沒有_花一枚硬幣，因為這些帳戶的餘額保持不變，並且（回想一下我們要證明的寬鬆聲明）他們的見證人永遠不會改變。 因此，B完全等於A。 

最後，我們通過計算 Alice 應該發送給 Bob 的位數來解決我們的矛盾。 她可以選擇2 n 個可能的帳戶子集，因此根據香農定律，她應該必須向鮑勃發送至少n位。 然而，她只發送了恆定大小的狀態V'，它比n位短得多。

（熟悉密碼學的讀者可能會注意到，我們在這裡掩蓋了一些細節; 例如，鮑勃的解碼可能會失敗，概率可以忽略不計。 我們的論文包括完整的證明。 ）

雖然我們用無狀態區塊鏈描述了我們的證明，但Alice和Bob可以使用各種其他經過身份驗證的數據結構（包括累加器、向量承諾和經過身份驗證的字典）執行類似的高效通信。 我們使用稱為可撤銷證明系統的新抽象來形式化此類數據結構。

3、結論

我們的結果表明，你不能“將狀態加密”——沒有哪個承諾方案允許我們構建一個用戶永遠不必更新他們的見證的無狀態區塊鏈。 狀態並沒有消失，而是從驗證者手中轉移出來，並以頻繁更新見證人的形式推送給使用者。

確實存在其他幾種偏離嚴格無狀態區塊鏈模型的有前途的解決方案。 該模型的一個特點是允許第三方（既不是使用者也不是驗證者）負責存儲完整狀態。 該方稱為證明服務節點（並由Srinivasan 等人進行了最嚴格的檢查），使用完整狀態代表使用者生成最新的見證人。 然後，使用者可以像在常規無狀態區塊鏈中一樣使用這些見證人進行交易，其中驗證器仍然僅存儲簡潔的狀態。 這個系統的激勵，特別是使用者如何補償證明服務節點，是一個有趣的開放研究方向。

雖然到目前為止我們的討論主要集中在 L1 區塊鏈上，但我們的結果也對 Rollup 伺服器等 L2 系統產生了影響。 Rollup（無論是樂觀的還是 ZK）通常採用一個大的狀態並使用存儲在 L1 上的一個小值來提交它。 此狀態包括 L2 上每個使用者的帳戶。 我們希望這些用戶能夠通過發佈其當前賬戶餘額的見證來直接在 L1 上提取資金（無需 L2 伺服器的配合）。 此設置也是我們模型中可撤銷證明系統的一個實例。 事實上，有人可能會說無狀態區塊鏈已經以 L2 匯總的形式在實踐中得到了實施。

但不幸的是，這意味著我們的不可能性結果直接適用。 使用者的Rollup提現見證必須經常更改，否則幾乎整個 L2 狀態都必須寫入 L1。 因此，今天的Rollup通常假設有一個數據可用性委員會（有時稱為“validium”），其功能類似於“證明服務節點”，幫助使用者在準備退出時計算新的見證人。 我們的結果表明，以太坊文檔中對使用者的警告 「如果無法訪問交易數據，使用者就無法計算證明資金擁有權和執行提款所需的 Merkle 證明」 將永遠適用。

隨著區塊鏈系統的發展，開發更有效的方法來管理區塊鏈狀態將變得更加重要。 儘管我們排除無狀態區塊鏈的結果可能看起來是否定的，但不可能性的結果對區塊鏈設計者來說是有用的，因為它們告訴我們將研究重點放在其他地方，理想情況下可以幫助我們更快地找到可行的解決方案。