a16z Crypto：無狀態區塊鏈付諸實踐的不可能性探討

原文標題：On the impossibility of stateless blockchains

作者：Miranda Christ，哥倫比亞大學 CS博士，a16z 暑期實習研究員 \& Joseph Bonneau，a16z 研究合夥人

編譯：bayemon.eth，ChainCatcher

隨著區塊鏈技術用戶的增加和以及發生於其上的交易日益頻繁，驗證者為驗證交易而存儲的信息量（"狀態"）也在增加。例如，在比特幣中，狀態由一組未花費的交易輸出（UTXOs）組成。在以太坊中，狀態包括每個賬戶的賬戶餘額以及每個智能合約的代碼和存儲空間。

對於擁有足夠賬戶或UTXOs的區塊鏈來說，這種存儲負擔將變使得區塊鏈難以支持相當一部分人的真正日常交易，從而讓這些用戶無從成為驗證者，並因此對去中心化構成威脅。由於 Merkle Tree 和 ZK等工具已經幫助區塊鏈實現了不可思議的目標，我們因此想要訴諸密碼學尋求相應的解決方案。

這正是 "無狀態區塊鏈 "的目標。但是，儘管在這方面做了大量工作，相應的方案仍然遠未實用化。但事實證明，由於構造與實用之間的無法弥合的差距，這種進展滯後是與生俱來的，這種滯後似乎是任何行業發展過程中天然的障礙。我們的最新研究表明，如果不採取額外的措施來管理"狀態"，那麼無論多麼智能的無狀態區塊鏈方案都是不可行的。不過，正如我們在本文章末尾所說的那樣，即便結果並不實際，我們也不應當因此氣餒。

何為"無狀態"

如今，狀態雖然龐大，但易於管理。例如，比特幣節點存儲約 7 GB 的數據，以太坊節點存儲約 650 GB 的數據。但是，全節點的存儲負擔與鏈的吞吐量（每秒交易量或 TPS）大致呈線性增長，然而目前主鏈的吞吐量屬實低得離譜。就目前的設計而言，真正支持日常交易（數萬到數十萬 TPS）所需的狀態將非常龐大，需要數 TB 甚至數 PB 的存儲空間。

主鏈有限的性能促使人們尋找技術方法，以大幅減少驗證者所需的狀態量。最好的技術方法就是構建無狀態區塊鏈，即無論交易吞吐量如何，驗證器只需存儲一個恆定大小的狀態。(這個術語實際上是個誤解：狀態仍然以恆定大小存在，只是小到足以在未來任何吞吐量下都能夠正常運行）。無狀態區塊鏈可以大幅降低對於硬件的存儲要求，使得運行驗證器節點變得更加容易，樂觀地說，每個人都能在手機上運行一個節點。而由於驗證器數量的增加會提高鏈的安全性，因此降低驗證器的準入門檻非常重要。

儘管 Todd, Buterin, Boneh與Srinivasan等人對無狀態區塊鏈進行了大量研究，但距離完全實現還有一定距離，據我們目前所知，還沒有任何一個無狀態區塊鏈被成功部署。所有已知無狀態區塊鏈的根本問題在於，它們要求用戶存儲額外的數據（稱為 "見證 Witness"），以幫助驗證者驗證涉及其賬戶的交易。例如，這種見證可能是Merkle 包含性證明，表明用戶的賬戶及其餘額包含在全局狀態承諾中。當用戶進行交易時，他們會向驗證者提交該證明，表明其賬戶有足夠的餘額。

與永不更改的私鑰不同的是，這些見證會經常變化，即使對沒有積極交易的用戶來說也是如此，這會給用戶帶來了難以想象的負擔。想象一下，如果你必須持續監控全球所有其他信用卡交易，並相應地更新一些本地數據，才能使用自己的信用卡，確實會引發不必要的麻煩。因此，要使區塊鏈切實可行，用戶必須能夠保持離線狀態，且只有在提交交易時才與區塊鏈互動。這也就意味著對於硬件錢包在內的多種情況下，見證是完全無從更新的。

這讓我們自然而然地想到了一个研究問題：我們能否建立一個不需要（或很少需要）更新見證的無狀態區塊鏈？為了回答這個問題，我們開發了一個新穎的理論框架（可撤銷證明系統），對無狀態區塊鏈進行了概括。利用這個框架，我們證明了一個確鑿的不可能事件：在簡潔的全局狀態和頻繁的見證更新之間的是幾乎無法平衡的。我們的證明技術是信息理論性的，這意味著未來的計算機不會強大到足以解決這個問題：無狀態區塊鏈構造與實用性之間的鴻溝將永遠無法弥合。

研究背景

為了進一步直觀認識上文中提到的"不可能事件"，我們將首先使用 Merkle Tree 描述無狀態區塊鏈的自然方法（儘管基於 Merkle Tree 的解決方案效率並不高）。我們的目標是讓驗證者確定用戶提交的交易是否有效------例如，用戶擁有足夠的賬戶餘額可用於交易。在無狀態區塊鏈方案中，驗證器存儲一個恆定大小的狀態，當用戶進行交易時，他們的交易必須包含一個見證。驗證器可以使用當前狀態和用戶提交的（交易、見證）對來驗證該用戶是否有足夠的賬戶餘額來進行交易。

我們首先構建一棵 Merkle Tree，其中每對（賬戶 ID，餘額）鍵值對（a,b）都是樹上的葉子。驗證者存儲的恆定大小的狀態 V 是這棵樹的根，並充當賬戶-餘額鍵值對的承諾。每個用戶都必須通過 Merkle 包含證明維護其（賬戶ID，餘額）信息。葉子（a,b）的 Merkle 包含證明由其通向樹根的路徑上的節點集（v1, …, vk）組成。驗證者可以通過檢查 (a,b) 的證明（v1, …, vk）與其當前狀態 V 來檢查 b 是否確實是賬戶 a 的餘額。Merkle Tree 的一個特性是，如果給定了葉子的 Merkle 包含證明，那麼當葉子發生變化時，就很容易計算出結果根。換句話說，驗證者可以很容易地計算出更新的狀態 V'，該狀態可以捕捉到交易執行後賬戶 a 的新餘額。

然而Merkle Tree有兩個主要缺點 ，首先，用戶見證相對較大，隨系統中賬戶總數的對數增長而增長。理想情況下，它們應該是恆定大小的，可以使用 RSA 累加器等方案來實現（Boneh 等人在無狀態區塊鏈中對此進行了研究）。

第二個缺點更難避免：只要有其他用戶進行交易，賬戶-餘額鍵值對的證明就會發生變化。回想一下，葉子的證明由從葉子到樹根的路徑上的節點集組成。如果任何其他葉子發生變化，這些節點中的一個也會發生變化，這就帶來了一個實際問題。大多數區塊鏈用戶都希望被動地將他們的幣保存在錢包中，只有當他們想進行交易時才上線。然而，在這種無狀態區塊鏈的實際應用中，用戶必須不斷監控其他人的交易，以保證自己的見證人是最新的。(雖然第三方可以代表用戶進行監控，但這偏離了標準的無狀態區塊鏈模式。我們將在本篇文章的最後對此進行討論）。實際上，這對無狀態區塊鏈來說是一個難以克服的挑戰，給用戶帶來了沉重的負擔。

結論：無狀態區塊鏈是不可能實現的

這種現象並不是 Merkle Tree 獨有的缺陷------當前所有已知的無狀態區塊鏈方案都要求用戶經常更新他們的對應的見證信息。更準確地說，必須更新見證信息的用戶數量與所有用戶的交易總量大致呈線性關係，並單調遞增。

這意味著，即使用戶 Alice 沒有進行任何交易，她的見證信息也可能需要隨著其他用戶的交易而改變。 只要驗證者存儲的簡潔狀態太小，無法捕捉到完整狀態（即所有賬戶餘額的集合），那麼簡潔狀態存儲的規模增加就沒有什麼幫助。我們在將這種隱含關係可視化，同時也輸出了不同吞吐量的區塊鏈每天所需的驗證人變更次數。這些圖顯示了最佳無狀態區塊鏈所需的見證變更次數。其中，data universes 指的是賬戶模型下的賬戶總數或UTXO模型下的UTXO總數。

我們證明的核心是信息論的論證。Claude Shannon 正式提出的信息論核心原則是：如果 Alice 從大小為 2n 的集合中隨機選擇一個對象，並想要告知 Bob 她的選擇，則必須向鮑勃發送至少 n 個比特。如果存在一種無狀態區塊鏈方案，且用戶無需更新他們的見證，愛麗絲就可以用少於 n 個比特的花費告訴Bob她的具體選擇------然而 Shannon 證明這是不可能的。因此，我們同樣認為不可能存在這樣的無狀態區塊鏈。

簡單起見，我們先作一個弱化的證明，即不可能存在用戶永遠不需要更新其見證的無狀態區塊鏈。證明的關鍵過程涉及，Alice 使用無狀態區塊鏈方案將她的信息編碼傳輸給 Bob。起初，假設Alice和Bob都知道所有 n 個用戶的全部賬戶-餘額對，同時每個賬戶餘額至少為1。此外，Alice和Bob還知道無狀態區塊鏈簡介狀態 V以及所有賬戶餘額對（ai，bi）的見證 wi， 兩人商定了信息與賬戶集之間的映射。Alice將選擇一組與她的信息相對應的賬戶 A，並使用賬戶餘額進行消費，最終使用無狀態區塊鏈向 Bob 傳達她選擇的賬戶集，而Bob可以從這個賬戶集中了解到她的信息是什麼。

編碼：Alice 使用無狀態區塊鏈方案計算出更新後的狀態 V'，並將 V' 發送給 Bob。

解碼：對於每一個 i，Bob 會檢查 Verify(wi,(ai,bi))。Bob輸出賬戶集合 B，使得 Verify(wi, (ai, bi)) = false。

最終，Bob成功輸出了與Alice所選的同一集合，即 B = A。首先，請注意，如果 Alice 花掉了賬戶 ai 中的一枚硬幣，則其舊餘額的見證不應再被接受------否則，愛麗絲就可以重複消費。因此，對於 A 中的每一個賬戶 ai，Verify(wi, (ai, bi)) = false，Bob將把這個賬戶包含在 B 中。另一方面，Bob不會把沒有餘額不變的賬戶包含在 B 中，因為這些賬戶的餘額保持不變，而且（回想一下我們要證明的"弱化"聲明）它們的見證人永遠不會改變。因此，B 恰好等於 A。

最後，我們通過計算 Alice 本應發送給鮑勃的比特數來得出矛盾。她可以選擇的賬戶子集有 2n 個，因此根據 Shannon 定律，她應該至少發送 n 個比特給 Bob。然而，她只發送了恆定大小的狀態 V'，比 n 比特短得多。

(熟悉密碼學的讀者可能會注意到，我們在這裡忽略了一些細節；例如，解碼失敗概率可以忽略不計。我们的论文包括完整的证明）。

雖然我們用無狀態區塊鏈來描述我們的證明，但愛麗絲和鮑勃也可以使用其他各種認證數據結構（包括累加器 Accumulators、向量承諾 Vector Commitments 和授權字典 Authenticated dictionaries）執行類似的高效通信。我們使用一個新的抽象概念將這一類數據結構形式化，我們稱之為可撤銷證明系統(revocable proof system)。

結論的含義

以上結果表明，我們無法"用加密技術完全消除狀態"，因此也並沒有易總方案能夠將建立無狀態區塊鏈變為現實，使得用戶永遠無需更新見證。狀態不會消失，而是會從驗證者處轉移，以頻繁更新見證的形式推送給用戶。

目前確實存在幾種偏離嚴格無狀態區塊鏈模型的其他有合理的解決方案。對這種模式的一種自然放寬是允許第三方（既不是用戶也不是驗證者）負責存儲全部狀態。這一方被稱為證明服務節點（Srinivasan 等人對其進行了最嚴格的研究），它使用完整狀態代表用戶生成最新的見證。然後，用戶可以使用這些見證進行交易，就像在普通的無狀態區塊鏈中一樣，驗證者仍然只存儲簡潔的狀態。該系統的激勵機制，尤其是用戶如何補償證明服務節點，是一個有趣的開放研究方向。

雖然迄今為止的討論主要集中在 L1 區塊鏈上，但我們的結果也會對 roll up等 L2 系統產生影響。無論是 Optimistic 或是 zk rollup，通常情況下都是生成一個較大的狀態值，並通過相應手段向L1提交一個小值並存儲。我們希望這些用戶在無需L2伺服器的配合，通過直接向發布賬戶餘額見證，直接在 L1 上提取資金。在我們的模型中，這種設置也是可撤銷證明系統的一個實例。事實上，可以說無狀態區塊鏈已經在實踐中以 L2 rollup的形式實現了。

但遺憾的是，我們的"不可能事件"無法直接投入應用。用戶的rollup撤回見證必須時常變更與同步，否則幾乎整個L2層狀態都要全部寫入L1。因此，如今的rollup解決方案通常會設置一個數據可用性委員會（有時稱為 "validium"），其功能類似於 "證明服務節點"，即在用戶準備退出時幫助他們計算新的見證。我們的研究結果表明，如果無法訪問交易數據，用戶就無法計算證明資金所有權和執行提現所需的 Merkle Tree，這也正是以太坊文件中對用戶而言始終適用的警告。

隨著區塊鏈系統的發展，開發更有效的區塊鏈狀態管理方法將變得越來越重要。雖然我們的研究認為無狀態區塊鏈不可能投入應用的結果，看起來是負面的，但這一結論仍然對區塊鏈設計者來說是有意義的。因為它們告訴我們要把研究重點放在其他地方，最好能幫助我們更快地找到可行的解決方案。