作者：Tia，Techub News
區塊鏈因其去中心化的設計而犧牲了效率，因此提升執行速度一直是急需解決的問題之一。區塊鏈的「執行層」是處理每一筆交易並將其加入鏈中的關鍵部分。為了加速處理能力，在執行層進行提升成為核心策略之一，而並行執行正是這一方面的重要突破。
傳統的區塊鏈通常採用串行方式逐筆處理交易，這使得交易速度受到很大限制，尤其在交易密集的網路中會引發擁塞。然而，透過並行執行，多個交易可以同時處理，從而大幅提高執行效率並減輕鏈上壓力。
為了更了解什麼是並行，我們將先從執行開始介紹，並以Merge 後PBS 模式下的以太坊為例，來解釋一下什麼是執行，同時展示執行在整個交易生命週期中所處的位置。
交易執行的具體環節
- 交易進入記憶體池並被篩選和排序：這是交易被提交後的預處理階段，包含了Mempool、Searcher 和Builder 的交互，完成交易的篩選和排序。
- Builder 建立區塊（但不執行）：Builder 將有利可圖的交易排列成一個區塊，以完成對交易的打包和排序。
- Proposer 驗證並提交區塊：區塊建置完成後，Builder 會將區塊的提案發送給Proposer。 Proposer 對區塊的結構和交易內容進行驗證，然後正式將區塊提交到網路上，以開始執行。
- 執行交易：區塊提交後，節點逐筆執行區塊內的交易。這是狀態更新的關鍵階段，每筆交易都會觸發智慧合約呼叫、帳戶餘額變更或狀態變更。
- 見證者見證：驗證者對區塊的執行結果和狀態根進行見證，並將其作為最終確認。這確保了區塊在執行層的真實性和有效性，並防止不一致性。
- 狀態同步：每個節點會將區塊的執行結果（如帳戶餘額、合約狀態更新等）同步到自己的本地狀態，執行每筆交易後，節點計算並儲存一個新的狀態根，用以在下一個區塊中作為初始狀態。
當然，這只是以區塊為單位的交易的狀態同步，為了保持最新的鏈上狀態，通常情況下，節點會逐個區塊同步數據，並持續驗證區塊和狀態。但如果要達到POS 機制下的最終性，還需要聚合者將每個Slot 中的見證者簽名聚合成一個完整的簽名，並將其傳遞到下一個Slot 的提議者處，並且驗證者需要在經過一個Epoch 後，基於投票數量確認該Epoch 內的所有區塊的狀態，形成臨時的共識狀態檢查點。當連續兩個Epoch 獲得大多數驗證者的見證支持後，區塊和交易才會達成最終性。
從交易的整個生命週期來看，執行發生在Proposer 對Builder 發送來的區塊的結構和交易內容進行驗證後。實際執行過程需要將交易逐筆處理，並對對應的帳戶或合約狀態進行更新。所有交易執行完畢後，Proposer 會計算出一個新的狀態根（梅克爾根），這是對當前區塊所有交易的執行結果和最終全局狀態的總結。通俗來說，完整的區塊執行過程包括把以太坊從前一個狀態變成下一個狀態的過程中需要完成的一系列計算，從每個交易的執行到默克爾根的計算。
順序執行
與並行相對的是順序執行，也就是目前區塊鏈較為通用的執行方式。通常，交易會依照順序逐步執行。當一筆交易完成執行後，以太坊會將帳戶狀態及相關資訊（例如餘額、合約儲存資料）更新至帳戶狀態樹中，新的帳戶狀態雜湊被產生。所有帳戶狀態樹完成更新後，就會形成被稱為狀態默克爾根的狀態樹的根節點雜湊。在完成狀態默克爾根、交易默克爾根和收據默克爾根後，區塊頭就會進行哈希計算，產生該區塊的區塊哈希。
而在這其中，交易的執行順序至關重要。由於默克爾樹是哈希值的二元樹，不同順序下形成的默克爾根值會不同。
平行執行
在並行執行的環境下，節點會嘗試對區塊中的交易進行並行處理。並不是按照順序一筆一筆地執行交易，而是將交易分配到不同的「執行路徑」上，使它們能同時執行。透過並行執行，系統能夠更有效率地處理區塊中的交易，提高吞吐量。
所有交易執行完成後，節點會將執行結果（即交易影響的狀態更新）加總，形成一個新的區塊狀態。這個狀態會被加到區塊鏈上，代表鏈上最新的全域狀態。
狀態衝突
由於並行會在不同路徑同時處理交易，因此並行的一大難點就是狀態衝突。即可能存在多個交易在同一時間段內對區塊鏈上的相同部分資料（狀態）進行讀取或寫入操作的情況。這種情況如果處理不當，會導致執行結果不確定。因為狀態的更新順序不同，最終的計算結果也會不同。舉個例子，
假設有兩個交易，交易A 和交易B，它們都試圖對同一個帳戶的餘額進行更新操作：
- 交易A：增加帳戶餘額10。
- 交易B：增加帳戶餘額20。
帳戶初始餘額為100。
如果我們串行執行，執行順序的結果是確定的：
1. 先執行交易A，再執行交易B：
- 帳戶餘額先增加10，變成110。
- 再增加20，最終變成130。
2. 先執行交易B，再執行交易A：
- 帳戶餘額先增加20，變成120。
- 再增加10，最終變成130。
在這兩種順序中，最終餘額都是130，因為系統確保了交易執行的順序一致性。
但在並行執行環境下，交易A 和交易B 可能同時讀取初始餘額100 並進行各自的運算：
- 交易A 讀取到餘額為100，計算後更新餘額為110。
- 交易B 也讀取到餘額為100，計算後更新餘額為120。
在這種情況下，由於交易同時執行，導致最終餘額只更新為120，而不是130，因為交易A 和交易B 的操作「覆蓋」了對方的結果，產生了狀態衝突。
這類狀態衝突問題通常被稱為「資料覆蓋」，即當交易試圖同時修改相同的資料時，可能會相互覆蓋對方的計算結果，導致最終狀態不正確。另外一種狀態衝突可能會導致的問題是無法保證執行順序。由於多個交易在不同的時間段完成操作，會造成不同的執行順序。順序不同，可能會導致不同的計算結果，使結果不確定。
為了避免這種不確定性，區塊鏈並行執行系統通常會引入一些衝突偵測和回溯機制，或事先對交易進行依賴性分析，確保它們在不影響最終狀態一致性的情況下並行執行。
樂觀並行與確定性並行
有兩種方法方式來處理可能的狀態衝突問題：確定性並行和樂觀並行。這兩種模式在效率和設計複雜性上各有權衡。
確定性並行需要提前聲明狀態訪問，驗證者或sequencer 會在交易排序時檢查聲明的狀態訪問。如果有多個交易試圖寫入相同狀態，會將這些交易標記為衝突，避免同時執行。不同的鏈具體實現提前聲明狀態存取的形式不同，但一般包括以下幾種方式：
- 透過合約規範約束：開發者在智慧合約中直接規定狀態存取範圍。例如，ERC-20 代幣轉帳需要存取發送方和接收方的餘額欄位。
- 透過交易結構化資料聲明：交易中新增專門欄位來標註狀態存取。
- 透過編譯器分析：高階語言的編譯器可以靜態分析合約程式碼，自動產生狀態存取集合。
- 透過框架強制聲明：某些框架要求開發者在呼叫函數時明確指定需要存取的狀態
樂觀並行則會樂觀地先處理交易，等到衝突發生時，再將受影響的交易依序重新執行。為了盡可能避免衝突情況的發生，樂觀並行設計的核心是透過歷史資料、靜態分析等對狀態進行快速預判與假設。即係統在不完全驗證的情況下，假設某些操作或狀態更新是有效的，盡量避免等待所有驗證過程，以此提高效能和吞吐量。
雖然樂觀並行能透過一些對狀態的快速預判和假設來盡可能避免衝突發生，但還是會有一些無法避免的挑戰，特別是涉及合約執行或跨鏈交易，如果衝突頻繁發生，重新執行可能顯著拖慢系統效能，並增加計算資源消耗。
確定性並行則透過在交易前進行狀態依賴性檢查以避免樂觀並行可能出現的衝突情況，但由於需要在交易提交前準確聲明狀態依賴，這對開發者提出更高要求，從而增加了實現的複雜性。
EVM 平行困境
對待狀態衝突不僅有確定性和樂觀之分，在實現並行的具體過程中，還需要從鏈資料庫架構的角度來考慮。並行中的狀態衝突問題在梅克爾樹架構下的EVM 中就特別困難。梅克爾樹是一個分層哈希結構，在每次交易修改某個狀態資料後，梅克爾樹的根哈希值也需要更新。這個更新過程是遞歸的，從葉子節點向上逐層計算直到根節點。由於哈希是不可逆的，即只有當下層的資料變更完成後才能計算上層，這種特性導致它很難並行更新。
如果兩個交易並行執行並存取同一個狀態（如帳戶餘額），就會造成默克爾樹節點的衝突。而解決這種衝突通常需要額外的事務管理機制，確保在多個分支中都能得到一致的根雜湊值。這對EVM 來說並不容易實現，因為它需要在並行化與狀態一致性間做取捨。
非EVM 平行解決方案
Solana
不同於以太坊的全域狀態樹，Solana 採用了帳戶模型。每個帳戶是獨立的儲存空間，儲存在帳本中，因此避免了路徑衝突問題。
Solana 是確定性並行。在Solana 中，每筆交易需要在提交時明確聲明將存取的帳戶和所需的存取權限（唯讀或讀寫）。這種設計讓區塊鏈節點可以在交易執行之前，提前分析每筆交易需要存取的資源。因為交易在開始執行前已明確所有的帳戶依賴關係，節點可以判斷哪些交易會存取相同的帳戶，哪些交易可以安全地並行執行，從而實現智慧調度，避免衝突，從而實現並行調度的基礎。
由於每筆交易在執行前就已聲明了需要存取的帳戶和權限，Solana 可以檢查交易之間是否存在帳戶依賴關係（Sealevel 模型）。交易之間如果沒有共享的讀寫帳戶，系統就可以把它們分配到不同的處理器上並行執行。
Aptos
Aptos 的平行執行設計與以太坊有很大的不同，它在架構和機制上做出了一些關鍵創新，主要體現在帳戶模型和狀態儲存。
以太坊在執行交易時需要經常更新全域狀態樹（MPT）。所有帳戶、合約的狀態都儲存在一個共享的狀態樹中，任何交易都需要存取和更新這棵狀態樹的一部分。而Aptos 則透過將帳戶劃分為獨立的狀態單元，每個物件都是獨立的鍵值對，物件之間可以獨立存在，彼此互不影響，只有明確引用關係時才會關聯。物件之間沒有公共的樹路徑，不會出現鎖定競爭，可以完全並行。
Aptos 的底層資料結構為Jellyfish Merkle Tree。每個物件的狀態最終儲存在JMT 中，作為獨立的鍵值對。不同於以太坊的MPT，Jellyfish Merkle Tree 以一種完全二叉樹結構的形式，這種形式使得節點的儲存路徑和查詢路徑被簡化，大幅降低了驗證時間。並且，每個帳戶在樹中的位置是固定的，且樹中的節點是獨立儲存的，允許多個帳戶的更新和查找並行進行。
Aptos 是樂觀並行，它不需要預先提供聲明的所有帳戶的依賴關係。為此，Aptos 使用Block-STM，Block-STM 會利用預設的交易順序來估計依賴性，進而減少中止次數。
並行EVM
與非EVM 並行相比，平行EVM 在處理狀態依賴性、衝突偵測、Gas 管理和回溯機制等問題時，面臨的技術難度較高。為了更好地理解這一點，我們可以參考一些平行EVM 專案（如Sui、Monad、Canto）如何解決這些問題。
Sui
Sui 和Aptos 一樣，也是使用物件模型來處理狀態，採用每個物件（例如帳戶、智慧合約狀態）作為獨立的資源，這些物件透過物件唯一識別碼來區分。當交易涉及不同的物件時，這些交易可以並行處理，因為它們對不同的狀態進行操作，不會產生直接的衝突。
雖然Sui 使用物件模型來管理狀態，然而，為了相容於EVM，Sui 的架構透過額外的適配層或抽象機制，來橋接物件模型和EVM 的帳戶模型。
在Sui 中，事務的調度使用樂觀並行策略，假設事務之間沒有衝突。如果衝突發生，系統會使用回滾機制來恢復狀態。
Sui 使用了物件模型和狀態隔離技術，能有效避免狀態依賴性問題。每個物件作為獨立的資源，不同的交易可以並行執行，從而提高了吞吐量和效率。但這種方法的trade-off 是物件模型的複雜性和回溯機制的開銷。如果交易之間發生衝突，需要對部分狀態進行回滾，這會增加系統的負擔，並可能影響並行處理的效率。相較於非EVM 平行系統（如Solana），Sui 需要更多的運算和儲存資源來維持高效率的平行性。
Monad
與Sui 一樣，Monad 採用的也是樂觀並行。但Monad 的樂觀並行在具體交易執行前還是會對一些具有依賴關係的交易進行預測，預測主要透過Monad 的靜態程式碼分析器來完成。預測需要對狀態進行訪問，而以太坊資料庫中儲存狀態的方式使得存取狀態非常困難，為了使得並行在狀態讀取的過程更具效率，Monad 還重構了資料庫。
Monad 狀態樹依分割區劃分，每個分割區維護自己的狀態子樹。更新時只需修改相關分片，無需重建整個狀態樹。透過狀態索引表快速定位分區中的狀態，減少分區間的互動。
小結
並行的核心是以多路徑執行的方式提高執行層執行效率，而為了實現多路徑執行，鏈則需要進行一系列如衝突檢測和回滾機制以確保它們在不影響最終狀態一致性的情況下並行執行，並對資料庫進行一定程度的改良。
當然，執行層效率的提高不限於並行這種方式，執行環節的最佳化還可以透過降低一筆交易對資料庫所需的讀寫操作來完成。而整個鏈速度提升涉及的範圍則更為廣泛，也包括了共識層效率的提升。
每個技術背後都有屬於其特定的限制條件。並行僅是提升效率的方式之一，最終決定是否使用該技術還需要考慮對於開發者是否友好，是否能夠以不犧牲去中心化的方式完成等等。科技的堆疊並非越多越好，至少，對於以太坊而言，並行並沒有那麼具有吸引力，如果單從提升效率的角度出發，加入並行對於以太坊而言並非是最優解，無論是從簡潔性考慮還是以以太坊目前Rollup 為中心的路線圖來考慮。
