a16z：論「無狀態區塊鏈」的不可能性

2023-08-26 00:08:15

原文作者：Miranda Christ、Joseph Bonneau

原文編譯：深潮 TechFlow

隨着區塊鏈支持更多用戶和更頻繁的交易，驗證者存儲以驗證交易的信息（即“狀態”）的數量也在增加。例如，在比特幣中，狀態由一組未花費的交易輸出（UTXO）組成。在以太坊中，狀態由每個账戶的账戶余額以及每個智能合約的代碼和存儲組成。

隨着账戶或 UTXO 足夠支持人口中相當一部分真正日常交易的區塊鏈增長，這種存儲負擔將變得難以控制，使得成為驗證者變得困難，並對去中心化構成威脅。誘人的解決方案是轉向密碼學，其中諸如 Merkle 樹和零知識證明等工具幫助我們實現了以前難以想象的事情。

這正是“無狀態區塊鏈”的目標。但盡管對它們進行了大量研究，它們仍然遠未實用。但事實證明，這種進展滯後是固有的 ——這些構建與實用性之間的差距將永遠無法彌合。我們最近的工作表明，如果沒有額外的措施來管理狀態，任何無狀態區塊鏈方案，無論多么聰明，都是不可行的。然而，正如我們在本文末尾所展示的那樣，這種不可能性結果不應該讓人灰心。

無狀態

如今，狀態是龐大但可管理的。例如，比特幣節點存儲約 7 GB 的數據，以太坊節點存儲約 650 GB 的數據。但是，完整節點的存儲負擔與鏈的吞吐量（每秒交易數或 TPS）大致呈线性增長，而當今的吞吐量仍然不可接受。根據當前的設計，真正支持日常交易所需的狀態（每秒交易數為數萬到數十萬）將變得難以控制，需要使用千兆字節甚至拍字節的存儲空間。

這促使人們尋找技術方法，以顯著減少驗證者所需的狀態量。至關重要的是實現無狀態區塊鏈，這將要求驗證者僅需存儲恆定大小的狀態，而不管交易吞吐量如何（實際上，這個術語是一個誤稱：仍然存在狀態，只是足夠小，以便在任何未來的吞吐量下都能實用——通常是恆定大小的）。這種輕量級存儲要求將使得運行驗證者節點變得更加容易；樂觀地說，每個人都可以在他們的手機上運行一個節點。由於增加驗證者的數量會增加鏈的安全性，降低驗證者的准入門檻非常重要。

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

與存儲私鑰不同，它永遠不需要更改，這些見證經常更改，即使對於不活躍交易的用戶也是如此，給用戶帶來了不切實際的負擔。類似地，想象一下，如果您不斷監視全球所有其他信用卡交易並相應地更新一些本地數據以使用您自己的信用卡。為了使區塊鏈實用，用戶必須能夠離线並僅在提交交易時與區塊鏈交互。在許多情況下，例如硬件錢包，更新見證不僅僅是不方便，而且是不可能的。

這引導我們提出一個自然的研究問題：我們能否構建一個不需要頻繁更新見證的無狀態區塊鏈（或者僅需要很少更新見證的區塊鏈）？為了回答這個問題，我們开發了一個新穎的理論框架（可撤銷的證明系統），它概括了無狀態區塊鏈。利用這個框架，我們證明了一個不可能性結果：簡潔的全局狀態和頻繁的見證更新之間的權衡在本質上很難調和。我們的證明技術是信息論的，這意味着未來的計算機將沒有足夠的能力來解決這個問題：無狀態區塊鏈構建與實用性之間的差距將永遠無法彌合。

我們研究的背景

為了幫助理解我們的不可能性結果，我們首先描述了一種自然但效率低下的使用 Merkle 樹構建無狀態區塊鏈的方法。我們的目標是使驗證者能夠確定用戶提交的交易是否有效 ——例如，用戶是否具有足夠的账戶余額來進行交易。在無狀態區塊鏈方案中，驗證者存儲一個恆定大小的狀態。當用戶進行交易時，他們必須在交易中包含一個見證。驗證者可以使用當前狀態和用戶提交的（交易，見證）對來驗證該用戶是否具有足夠的账戶余額來進行交易。

我們首先構建一個 Merkle 樹，其中每個（账戶 ID，余額）對（a，b）作為葉子節點包含在內。驗證者存儲的恆定大小的狀態 V 是這棵樹的根，它作為一組账戶余額對的承諾。每個用戶將其見證作為 Merkle 包含證明維護。一個葉子（a，b）的 Merkle 包含證明由沿着從該葉子到樹根的路徑的夥伴節點（v1，…，vk）組成。給定一個由账戶 a 和聲稱的余額 b 進行的交易，驗證者可以通過檢查（a，b）的證明（v1，…，vk）與其當前狀態 V 來驗證 b 是否確實是账戶 a 的余額。如果是這樣，驗證者執行交易並必須相應地更新账戶的余額。Merkle 樹的一個方便的屬性是，給定一個葉子的 Merkle 包含證明，當該葉子發生變化時，計算結果的根很容易。換句話說，驗證者可以輕松計算出一個更新的狀態 V'，該狀態捕捉了交易執行後账戶 a 的新余額。

這個 Merkle 樹方案有兩個主要缺點。首先，用戶的見證相對較大，隨着系統中账戶總數的對數增長。理想情況下，它們應該是恆定大小的，我們可以使用 RSA 累加器等方案實現這一點。

第二個缺點更難避免：每當其他用戶進行交易時，账戶余額對的證明就會發生變化。回想一下，葉子節點的證明由從該葉子節點到樹根的路徑上的合作夥伴節點組成。如果其他葉子節點發生變化，其中一個節點就會發生變化，從而帶來實際上的問題。大多數區塊鏈用戶希望被動地將他們的硬幣保存在錢包中，只有在想要進行交易時才上线。然而，在這種無狀態的區塊鏈中，用戶必須不斷監視其他人的交易，以保持他們的見證信息最新。盡管第三方可以代表用戶進行此監視，但這偏離了標准的無狀態區塊鏈模型。實際上，這對於無狀態區塊鏈來說是一個無法克服的挑战，給用戶帶來了沉重的負擔。

我們的結論：無狀態是不可能的

這種現象不僅僅適用於這種 Merkle 樹結構——所有已知的無狀態區塊鏈方案都要求用戶頻繁更新他們的見證信息，我們在這裏進行了證明。更准確地說，我們表明，必須更新其見證信息的用戶數量與所有用戶進行的交易總數大致呈线性增長。

這意味着即使用戶 Alice 不進行任何交易，她的見證信息也可能需要隨其他用戶的交易而改變。只要驗證者存儲的簡潔狀態太小而無法捕捉到完整的狀態（即所有账戶余額的集合），增加簡潔狀態的大小幫助甚微。我們根據我們的定理繪制了下面所示的這種關系圖，以及每天對於不同吞吐量的區塊鏈所需的見證信息更改次數。這些圖顯示了最佳無狀態區塊鏈需要更改見證信息的次數。在這裏，數據宇宙指的是账戶模型中的總账戶數或 UTXO 模型中的總 UTXO 數量。

我們的證明核心是一個信息論的論證。信息論的一個核心原理，由 Claude Shannon 形式化，是如果 Alice 從一個大小為 2 n 的集合中隨機選擇一個對象，並希望告訴 Bob 她選擇了哪個對象，她必須發送至少 n 個比特給他。如果存在一個無狀態區塊鏈方案，其中用戶很少更新他們的見證信息，Alice 可以用少於 n 個比特告訴 Bob 她選擇了哪個對象，而這是不可能的，正如 Shannon 所證明的。因此，這樣的無狀態區塊鏈是不存在的。

為了簡單起見，我們在這裏描述一個稍微弱一些的陳述的證明：不存在一個無狀態區塊鏈，用戶永遠不需要更新他們的見證信息。關鍵是 Alice 使用無狀態區塊鏈方案來對她的消息進行編碼，發送給 Bob。最初，Alice 和 Bob 都知道所有 n 個用戶的完整的账戶余額對集合。假設每個账戶至少有一個幣。Alice 和 Bob 也都知道無狀態區塊鏈的簡潔狀態 V 和所有账戶余額對（ai， bi）的見證 wi。Alice 和 Bob 還商定了消息和账戶集合之間的映射關系。Alice 將選擇一個與她的消息對應的账戶集合 A，然後她將從這些账戶中花費幣。她將使用無狀態區塊鏈向 Bob 傳達她選擇的集合，他可以從這個集合中了解她的消息。

編碼：Alice 從 A 中的每個账戶中花費一個幣。使用無狀態區塊鏈方案，Alice 計算出更新後的狀態 V'並將其發送給 Bob。

解碼：對於每個 i，Bob 檢查 Verify （wi，（ai， bi））是否為真。Bob 輸出账戶集合 B，使得 Verify（wi，（ai， bi）） = false。

Bob 成功地輸出了 Alice 選擇的相同集合：B = A。首先，觀察到如果 Alice 從账戶 ai 中花費了一個幣，其舊余額的見證不應再被接受——否則，Alice 將能夠進行雙重支付。因此，對於 A 中的每個账戶 ai，Verify（wi，（ai， bi）） = false，Bob 將把這個账戶包括在 B 中。另一方面，Bob 永遠不會將 Alice 沒有從中花費幣的账戶包括在 B 中，因為這些账戶的余額保持不變，並且（回想一下我們要證明的放寬的陳述）它們的見證永遠不會改變。因此，B 恰好等於 A。

最後，我們通過計算 Alice 應該發送給 Bob 的位數來解決我們的矛盾。她可以選擇的子集有 2 的 n 次方個，所以根據香農的定律，她應該至少發送 n 位個比特給 Bob。然而，她只發送了常數大小的狀態 V'，它比 n 位短得多。

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

結果的影響

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

還存在一些其他有前途的解決方案，它們偏離了嚴格的無狀態區塊鏈模型。這個模型的一個自然放寬是允許第三方（既不是用戶也不是驗證者）負責存儲完整的狀態。這個稱為證明服務節點的第三方使用完整的狀態為用戶生成最新的見證信息。然後用戶可以像在常規的無狀態區塊鏈中一樣使用這些見證信息進行交易，其中驗證者仍然只存儲簡潔狀態。這個系統的激勵機制，特別是用戶如何補償證明服務節點，是一個有趣的开放研究方向。

雖然我們迄今為止的討論集中在 L1 區塊鏈上，但我們的結果也對 L2 系統（如 Rollup 服務器）產生影響。Rollup（無論是 Optimistic 還是 ZK）通常使用一個小值在 L1 上存儲一個大狀態的承諾。這個狀態包括 L2 上每個用戶的账戶。我們希望這些用戶能夠直接在 L1 上提取資金（無需 L2 服務器的合作），通過發布對他們當前账戶余額的見證來實現。這個設置在我們的模型中也是可撤銷證明系統的一個實例。事實上，可以說無狀態區塊鏈已經在實踐中得到了實現，以 L2 Rollup 的形式。

然而，不幸的是，這意味着我們的不可能性結果直接適用。用戶的 Rollup 提取見證必須經常更改，否則幾乎整個 L2 狀態都必須寫入 L1。因此，如今的 Rollup 通常假設存在一個數據可用性委員會（有時稱為“validium”），類似於“證明服務節點”，幫助用戶在准備提取時計算新的見證信息。我們的結果表明，以太坊文檔中對用戶的警告：“如果沒有交易數據，用戶無法計算 Merkle 證明以證明對資金的所有權並執行提取。”將始終適用。