假設有大量對象可供用戶發送,所有對象(如果有效)都需要廣播,以便最終的構建節點能夠發現幷包含它們。假設有效性條件可以用 STARK 表示,並且我們處於後量子環境中,橢圓曲線 SNARK 將無法工作。
這至少適用於以太坊的三種用例:
- 後量子執行層簽名聚合,尤其是在用戶使用隱私協議的情況下
- 後量子共識層簽名聚合,用於處理大量驗證者
- 在分佈式塊構建模型中,我們假設塊的總數過大,構建者無法完全下載,因此構建者必須從塊提交者處下載根,然後使用分佈式應用服務(DAS)驗證其可用性。STARK 驗證糾刪碼的計算是否正確。
問題在於:STARK 開銷巨大,即使在高度優化的實現中,也需要 128 kB 的空間。如果用戶發送的每個對象都連同全部 128 kB 的 STARK 開銷一起廣播給所有人,那麼帶寬需求(包括中間內存池節點和構建器的帶寬)將非常高。
以下是解決這個問題的方法。
當用戶將對象發送到內存池時,他們可以將該對象與有效性的直接證明(例如,一個或多個簽名、通過某些驗證函數的 EVM 調用數據)或 STARK 有效性證明一起發送。
內存池節點遵循以下算法:
- 它們被動地等待並接收用戶發送的物品。當它們看到物品時,會驗證其證明。如果證明有效,它們就會接受該物品。
- 每週期(例如 500 毫秒),它們都會生成一個遞歸的 STARK 驗證,證明所有已知仍然有效的對象。它們會將此驗證轉發給其他節點,同時還會將尚未發送給該節點的任何對象(不帶驗證)發送給其他節點。
遞歸 STARK 的邏輯如下。公共輸入可以是位域或哈希列表,表示證明所驗證的對象集合。證明過程需要:
- 0 個或多個對象,及其有效性證明(直接證明或 STARK 證明)
- 0 個或多個其他相同類型的遞歸 STARK 函數
- 一個包含待丟棄對象哈希列表的位域(這允許丟棄過期對象)。
該證明證明了所有對象和所有遞歸 stark 公共輸入的並集的有效性,減去被丟棄的對象。
以圖表形式表示(此處以執行層簽名聚合用例為例):
在這個例子中,第一個內存池節點看到交易 Tx 1 和 Tx 2(帶有直接證明),並創建一個遞歸 STARK 證明,證明{Tx 1, Tx 2}有效。第二個內存池節點看到來自第一個節點的消息,該消息包含交易 Tx 1 和 Tx 2(沒有直接證明)以及 STARK 證明,並且它還看到交易 Tx 3(帶有直接證明),於是它創建一個遞歸 STARK 證明,證明{Tx 1, Tx 2, Tx 3}有效。它將此證明發送給它的對等節點,其中一個是構建節點,該構建節點接收幷包含此證明。
如果構建器收到多條包含非完全重疊對象集的消息,並且構建器想要同時包含這些對象集,則構建器可以自行創建一個遞歸的 STARK 合併器來合併它們。構建器還可以丟棄任何它認為不再有效的對象(此處指交易)。
該方案的總開銷為:
- 每個對象,如果沒有簽名,都會被廣播到每個節點。這與目前的現狀帶寬相同,區別在於我們可以去除簽名。
- 每個節點都擁有額外的入站和出站帶寬,其大小等於每個時間刻一個 STARK 的數據量乘以其對等節點的數量(例如,8 個對等節點,時間刻為 500 毫秒,則帶寬為 128 kB * 8 / 0.5 = 2 MB/秒)。該帶寬是恆定的,不會隨著用戶發送的對象數量的增加而增加。




