作者：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 證明” 將永遠適用。

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