譯者序

本文最初是我應(yīng)以太坊中文社區(qū)（Ethfans.org）之邀做的翻譯稿，原文取自以太坊社區(qū)的 sharding 項(xiàng)目。初始版本完成于 2018 年 1 月，首發(fā)于【以太坊愛好者】公眾號。

目前的中文版本是我根據(jù)最新版原文修訂之后的版本，對應(yīng)的原文更新時間為 2018/5/16。本文的源碼在我個人 fork 的 repo 上。

2017 年 8 月，比特幣網(wǎng)絡(luò)進(jìn)行了硬分叉，產(chǎn)生了比特幣現(xiàn)金（Bitcoin Cash），這個硬分叉的技術(shù)解釋就是對比特幣網(wǎng)絡(luò)進(jìn)行“擴(kuò)容”。比特幣現(xiàn)金網(wǎng)絡(luò)中的區(qū)塊大小為 8 M，是比特幣網(wǎng)絡(luò)區(qū)塊大小的 8 倍（比特幣網(wǎng)絡(luò)區(qū)塊大小為 1 M），從而提高了每個區(qū)塊的交易容量，反映為網(wǎng)絡(luò)整體吞吐量的提高。而其他使用了與比特幣網(wǎng)絡(luò)類似的數(shù)據(jù)存儲形式的加密貨幣網(wǎng)絡(luò)，也必將伴隨交易量的增加逐漸開始需要面對“擴(kuò)容”的問題?！胺制保⊿harding）就是以太坊網(wǎng)絡(luò)為了解決擴(kuò)容問題而設(shè)計(jì)的一種技術(shù)方案。

“分片”的大致設(shè)計(jì)思路是：將區(qū)塊鏈網(wǎng)絡(luò)中的每個區(qū)塊變?yōu)橐粋€子區(qū)塊鏈，子區(qū)塊鏈中可以容納若干（目前為 100 個）打包了交易數(shù)據(jù)的 Collation（大概可以稱為“校驗(yàn)塊”，為了在分片的情景中將其與區(qū)塊的概念區(qū)分開），這些 Collation 最終組成一個在主鏈上區(qū)塊；因?yàn)檫@些 Collation 是整體作為區(qū)塊存在的，所以其數(shù)據(jù)必定是全部由某個特定的礦工所打包生成，本質(zhì)上和現(xiàn)有協(xié)議中的區(qū)塊沒有區(qū)別，所以不再需要增加額外的網(wǎng)絡(luò)確認(rèn)。這樣，每個區(qū)塊的交易容量就大概擴(kuò)大了 100 倍；而且這種設(shè)計(jì)還有利于未來的繼續(xù)擴(kuò)展。整個擴(kuò)展計(jì)劃目前也被大致分為 4 個階段；本文所介紹的僅僅是第一階段的相關(guān)實(shí)現(xiàn)細(xì)節(jié)。

這是一篇關(guān)于以太坊的“分片”技術(shù)改進(jìn)的細(xì)節(jié)說明文檔，供以太坊開發(fā)者和有興趣的技術(shù)同行參考。

序言

本文的目的是為那些希望理解分片建議詳情，乃至去實(shí)現(xiàn)它的朋友提供一份相對完整的細(xì)節(jié)說明和介紹。本文僅作為二次方分片（quadratic sharding）的第一階段的描述；第二、三、四階段目前不在討論范圍，同樣，超級二次方分片（super-quadratic sharding）（“Ethereum 3.0”） 也不在討論范圍。

假設(shè)用變量 c 來表示一個節(jié)點(diǎn)的有效計(jì)算能力，那么在一個普通的區(qū)塊鏈里，交易容量就被限定為 O(c)，因?yàn)槊總€節(jié)點(diǎn)都必須處理所有的交易。二次方分片的目的，就是通過一種雙層的設(shè)計(jì)來增加交易容量。第一層不需要硬分叉，主鏈就保持原樣。不過，一個叫做 校驗(yàn)器管理和約 （validator manager contract，VMC）的合約需要被發(fā)布到主鏈上，它用來維持分片系統(tǒng)。這個合約中會存在 O(c) 個 分片 （目前為 100），每個分片都像是個獨(dú)立的“銀河”：它具有自己的賬戶空間，交易需要指定它們自己應(yīng)該被發(fā)布到哪個分片中，并且分片間的通信是受限的（事實(shí)上，在第一階段，不存在這種通信能力）。

分片運(yùn)行在一個普通的符合最長鏈規(guī)則的權(quán)益證明系統(tǒng)中，權(quán)益數(shù)據(jù)將保存在主鏈上（具體來說，是在 VMC 中）。所有分片共享一個通用驗(yàn)證器池，這也意味著：任何通過 VMC 注冊的驗(yàn)證器，理論上都可以在任意時間被授權(quán)來在任意分片上創(chuàng)建區(qū)塊。每個分片會有一個 O(c) 的區(qū)塊大小 / gas 上限（block size/gas limit），這樣，系統(tǒng)的整體容量就變成了 O(c^2) 。

分片系統(tǒng)中的大多數(shù)用戶都會運(yùn)行兩部分程序。(i) 一個在主鏈上的全節(jié)點(diǎn)（需要 O(c) 資源）或輕量節(jié)點(diǎn)（需要 O(log(c)) 資源）。 (ii) 一個通過 RPC 與主鏈交互的“分片客戶端”（由于這個客戶端同樣運(yùn)行在當(dāng)前用戶的計(jì)算機(jī)中，所以它被認(rèn)為是可信的）；它也可以作為任意分片的輕客戶端、作為特定分片的全客戶端（用戶需要指定他們正在“監(jiān)視”某個特定的分片），或者作為一個驗(yàn)證器節(jié)點(diǎn)。在這些情況下，一個分片客戶端的存儲和計(jì)算需求也將不會超過 O(c) （除非用戶指定他們正在監(jiān)視 每個 分片；區(qū)塊瀏覽器和大型的交易所可能會這么做）。

在本文中，術(shù)語 Collation 被用來與 Block（區(qū)塊）相區(qū)別，因?yàn)椋?(i) 它們是不同的 RLP（Recursive Length Prefix）對象：交易是第 0 層的對象，collation 是用來打包交易的第一層的對象，而 block 則是用來打包 collation（header）的第二層的對象； (ii) 在分片的情景中這更加清晰。通常，Collation 必須由 CollationHeader 和 TransactionList（交易列表）組成；Collation 的詳細(xì)格式和 Witness（見證人）會在 無狀態(tài)客戶端 那節(jié)定義。Collator（即用來打包 transaction 生成 collation 的某個地址，譯者注）是由主鏈上 驗(yàn)證器管理合約 的 getEligibleProposer 函數(shù)所生成的示例。算法會在隨后的章節(jié)中介紹。

二次方分片（Quadratic Sharding）

常量

• LOOKAHEAD_PERIODS: 4
• PERIOD_LENGTH: 5
• COLLATION_GASLIMIT: 10,000,000 gas
• SHARD_COUNT: 100
• SIG_GASLIMIT: 40000 gas
• COLLATOR_REWARD: 0.001 ETH

驗(yàn)證器管理合約（Validator Manager Contract，VMC）

我們假定 VMC 存在于地址 VALIDATOR_MANAGER_ADDRESS 上（在已有的“主分片”上），它支持下列函數(shù)：

• deposit() returns uint256：添加一個驗(yàn)證器到驗(yàn)證器集合中，驗(yàn)證器的大小就是函數(shù)調(diào)用時的 msg.value（也就是存入的以太幣數(shù)量）。這個函數(shù)會返回驗(yàn)證器的索引序號。
• withdraw(uint256 validator_index) returns bool：驗(yàn)證 msg.sender == validators[validator_index].addr，如果相等，它會將驗(yàn)證器從驗(yàn)證器集合中移除，并退還存入的以太幣。
• get_eligible_proposer(uint256 shard_id, uint256 period) returns address：使用一個區(qū)塊哈希（block hash）作為種子，基于預(yù)設(shè)的算法從驗(yàn)證器集合中選擇一個簽名者（signer）。驗(yàn)證器被選中幾率應(yīng)該與其存款數(shù)量成正比。這個函數(shù)應(yīng)該可以返回一個當(dāng)前周期內(nèi)的值或者以 LOOKAHEAD_PERIODS 為上限的任意未來周期內(nèi)的值。
• add_header(uint256 shard_id, uint256 expected_period_number, bytes32 period_start_prevhash, bytes32 parent_hash, bytes32 transaction_root, address coinbase, bytes32 state_root, bytes32 receipt_root, uint256 number) returns bool：嘗試處理一個 collation header，成功時返回 true，失敗時返回 false。
• get_shard_head(uint256 shard_id) returns bytes32：返回驗(yàn)證器管理合約內(nèi)由參數(shù)所指定的分片的 header 哈希。

這里也有一個日志類型：

• CollationAdded(indexed uint256 shard_id, bytes collation_header_bytes, bool is_new_head, uint256 score)

其中的 collation_header_bytes 可以用 vyper 語言來構(gòu)造：

    collation_header_bytes = concat(
        as_bytes32(shard_id),
        as_bytes32(expected_period_number),
        period_start_prevhash,
        parent_hash,
        transaction_root,
        as_bytes32(collation_coinbase),
        state_root,
        receipt_root,
        as_bytes32(collation_number),
    )

注意：因?yàn)?coinbase 和 number 在 vyper 語言中是保留字，所以它們被重命名為 collation_coinbase 和 collation_number。

Collation Header

我們首先以一個有下列內(nèi)容的 RLP 列表來定義一個“collation header”：

[
    shard_id: uint256,
    expected_period_number: uint256,
    period_start_prevhash: bytes32,
    parent_hash: bytes32,
    transaction_root: bytes32,
    coinbase: address,
    state_root: bytes32,
    receipt_root: bytes32,
    number: uint256,
]

這里：

• shard_id 分片的ID；
• expected_period_number 是 collation 希望被包含進(jìn)的周期序號，這是由 period_number = floor(block.number / PERIOD_LENGTH) 計(jì)算出來的；
• period_start_prevhash 前一區(qū)塊，即區(qū)塊 PERIOD_LENGTH * expected_period_number - 1 的區(qū)塊哈希（這其實(shí)就是希望被包含進(jìn)的周期起始區(qū)塊之前的最后一個區(qū)塊的哈希）。分片中使用區(qū)塊數(shù)據(jù)的操作碼（例如 NUMBER 和 DIFFICULTY）會使用這個區(qū)塊的數(shù)據(jù)；只有 COINBASE 操作碼會使用分片的 coinbase；
• parent_hash 是父 collation 的哈希；
• transaction_root 是包含了當(dāng)前 collation 中的所有交易數(shù)據(jù)的樹（trie）的根哈希；
• state_root 是分片中當(dāng)前 collation 之后的新狀態(tài)根；（也就是當(dāng)前 collation 中包含的所有交易執(zhí)行之后，且記賬收益分配之后得到的狀態(tài)樹根節(jié)點(diǎn)哈希，譯者注）
• receipt_root 是收據(jù)樹（receipt trie）根哈希；
• number 是 collation 編號，現(xiàn)在也是分叉選擇規(guī)則中的分值；且

當(dāng) addHeader(header) 的調(diào)用返回 true 時， collation header 有效。驗(yàn)證器管理合約會在滿足下列條件時這么做：

• shard_id 是 0 到 SHARD_COUNT 之間的數(shù)值；
• expected_period_number 與當(dāng)前周期號相等（即 floor(block.number / PERIOD_LENGTH)）
• 在相同的分片中，一個具有 parent_hash 的 collation 已經(jīng)被接受；（即當(dāng)前 collation 的父 collation 已經(jīng)被接受，譯者注）
• 在相同分片中，當(dāng)前周期內(nèi)還沒有一個同樣的 collation 被提交；（也就是檢查要添加的 collation 是否已經(jīng)添加過了，譯者注）
• add_header 函數(shù)調(diào)用者的地址與 get_eligible_proposer(shard_id, expected_period_number) 所返回的地址相同。(即判斷要添加這個 collation 的 proposer 是否是給定分片、給定周期的合法記賬人，譯者注)

當(dāng)滿足以下條件時， collation 有效： (i) 它的“collation header”有效； (ii) 在 parent_hash 的 state_root 上執(zhí)行 collation 的結(jié)果為給定的 state_root 和 receipt_root；并且 (iii) 總共使用的 gas 小于等于 COLLATION_GASLIMIT 。

Collation 狀態(tài)轉(zhuǎn)換函數(shù)

執(zhí)行一個 collation 時的狀態(tài)轉(zhuǎn)換處理如下：

• 按順序執(zhí)行由 transaction_root 所指定的樹上的每個交易；并且
• 將 COLLATOR_REWARD 的獎勵分配給 coinbase。

getEligibleProposer 的細(xì)節(jié)

這里是用Viper寫的一個簡單實(shí)現(xiàn)：

def getEligibleProposer(shardId: num, period: num) -> address:
    assert period >= LOOKAHEAD_PERIODS
    assert (period - LOOKAHEAD_PERIODS) * PERIOD_LENGTH < block.number
    assert self.num_validators > 0

    h = as_num256(
        sha3(
            concat(
                blockhash((period - LOOKAHEAD_PERIODS) * PERIOD_LENGTH),
                as_bytes32(shardId)
            )
        )
    )
    return self.validators[
        as_num128(
            num256_mod(
                h,
                as_num256(self.num_validators)
            )
        )
    ].addr

無狀態(tài)客戶端（Stateless Clients）

當(dāng)驗(yàn)證器被要求在一個給定的分片上創(chuàng)建區(qū)塊時，一個驗(yàn)證器僅會被給予數(shù)分鐘的通知（準(zhǔn)確地說，就是持續(xù) LOOKAHEAD_PERIODS * PERIOD_LENGTH 個區(qū)塊的通知）。在 Ethereum 1.0 中，創(chuàng)建一個區(qū)塊需要為驗(yàn)證交易而訪問全部的狀態(tài)。這里，我們的目標(biāo)是避免需要驗(yàn)證器保留整個系統(tǒng)的狀態(tài)（因?yàn)檫@樣就將使運(yùn)算資源需求變?yōu)?O(c^2) 了）。取而代之，我們允許驗(yàn)證器在僅知曉根狀態(tài)（state root）的情況下創(chuàng)建 collation，而將其他責(zé)任交給交易發(fā)送者，由他們提供“見證數(shù)據(jù)”（witness data）（也就是 Merkle 分支），以此來驗(yàn)證交易對賬戶產(chǎn)生影響的“前狀態(tài)”（pre-state），并提供足夠的信息來計(jì)算交易執(zhí)行后的“后狀態(tài)根”（post-state root）。

（應(yīng)該注意到，使用非無狀態(tài)范式（non-stateless paradigm）來實(shí)現(xiàn)分片，理論上是可能的；然而，這需要： (i) 租用存儲空間來保持存儲的有界性；并且 (ii) 驗(yàn)證器需要使用 O(c) 的時間在一個分片中創(chuàng)建區(qū)塊。上述方案避免了對這些犧牲的需求。）

數(shù)據(jù)格式

我們修改了交易的格式，以使交易必須指定一個 訪問列表 來列舉出它可以訪問的狀態(tài)（后邊我們會更精確的描述這點(diǎn)，這里不妨把它想象為是一個地址列表）。任何在 VM 執(zhí)行過程中試圖讀寫交易所指定的訪問列表以外的狀態(tài)，都會返回一個錯誤。這可以防止這樣的攻擊：某人發(fā)送了一個消耗 500 萬 gas 的隨機(jī)執(zhí)行，然后試圖訪問一個交易發(fā)送者和 collator 都沒有見證人的隨機(jī)賬戶；也可以防止 collator 包含進(jìn)像這樣浪費(fèi) collator 時間的交易。

交易發(fā)送者必須指定“見證人”（witness），這在被簽名的交易體 之外 ，但也被打包進(jìn)交易。這里的見證人是一個 Merkle 樹節(jié)點(diǎn)的 RLP 編碼的列表（RLP-encoded list），它是由交易在其訪問列表中所指定的狀態(tài)的組成部分。這使 collator 僅使用狀態(tài)根就可以處理交易。在發(fā)布 collation 的時候，collator 也會發(fā)送整個 collation 的見證人。

交易打包格式

    [
        [nonce, acct, data....],    # transaction body (see below for specification)
        [node1, node2, node3....]   # witness
    ]

Collation格式

    [
        [shard_id, ... , sig],   # header
        [tx1, tx2 ...],          # transaction list
        [node1, node2, node3...] # witness
    ]

也請參考 ethresearch 上的帖子 無狀態(tài)客戶端的概念 。

無狀態(tài)客戶端狀態(tài)轉(zhuǎn)換函數(shù)

通常，我們可以將傳統(tǒng)的“有狀態(tài)”客戶端執(zhí)行狀態(tài)轉(zhuǎn)換的函數(shù)描述為： stf(state, tx) -> state'（或 stf(state, block) -> state'）。在無狀態(tài)客戶端模型中，節(jié)點(diǎn)不保存狀態(tài)，所以 apply_transaction 和 apply_block 可以寫為：

apply_block(state_obj, witness, block) -> state_obj', reads, writes

這里，state_obj 是一個數(shù)據(jù)元組，包含了狀態(tài)根和其他 O(1) 大小的狀態(tài)數(shù)據(jù)（已使用的 gas、receipts、bloom filter 等等）；witness 就是見證人；block 就是區(qū)塊的余下部分。其返回的輸出是：

• 一個新的 state_obj 包含了新的狀態(tài)根和其他變量；
• 從見證人那里讀取的對象集合（用于區(qū)塊創(chuàng)建）；和
• 為了組成新的狀態(tài)樹（state trie）而被創(chuàng)建的一組新的狀態(tài)對象。

這使得函數(shù)是“單純性的”（pure），僅處理小尺寸對象（small-sized objects）（相反的例子就是現(xiàn)行的以太坊狀態(tài)數(shù)據(jù)，現(xiàn)在已經(jīng) 數(shù)百G字節(jié) ），從而使他們可以方便地在分片中使用。

客戶端邏輯

一個客戶端應(yīng)該有一個如下格式的配置：

{
    validator_address: "0x..." OR null,
    watching: [list of shard IDs],
    ...
}

如果指定了 validator 地址，那么客戶端會在主鏈上檢查這個地址是否是有效的 validator。如果是，那么在每次在主鏈上開始一個新周期時（例如，當(dāng) floor(block.number / PERIOD_LENGTH) 變化的時候），客戶端將為所有分片的周期 floor(block.number / PERIOD_LENGTH) + LOOKAHEAD_PERIODS 調(diào)用 getEligibleProposer。如果這個調(diào)用返回了某個分片 i 的驗(yàn)證器地址，客戶端會運(yùn)行算法 CREATE_COLLATION(i)（參考下文）。

對于 watching 列表中的每個分片 i，每當(dāng)一個新 collation header 出現(xiàn)在主鏈上，它就會從分片網(wǎng)絡(luò)中下載完整的 collation，并對其進(jìn)行校驗(yàn)。它將內(nèi)部保持追蹤所有有效的 header（這里的有效性是回溯的，也就是說，一個 header 如果是有效的，那么他的父 header 也應(yīng)該是有效的），并且將 head 具有最高得分的分片鏈接受為主分片鏈，同時從創(chuàng)世（genesis）collation 到 head 的所有 collation 都是有效的和可用的。注意，這表示主鏈的重組 和 分片鏈的重組都將影響分片的 head。

逆向匹配候選 head

為了實(shí)現(xiàn)監(jiān)視分片的算法和創(chuàng)建 collation，我們要做的第一件事就是使用下面的算法來按由高到低的順序匹配候選 head。首先，假設(shè)存在一個（非單純的、有狀態(tài)的）方法 getNextLog()，它可以取得某個還沒有被匹配的給定分片的最新的 CollationAdded 日志。這可以通過逆向匹配最新的區(qū)塊的所有日志來達(dá)成，即從 head 開始，反方向掃描 receipt 中的每個區(qū)塊。我們定義一個有狀態(tài)的方法 fetch_candidate_head：

unchecked_logs = []
current_checking_score = None

def fetch_candidate_head():
    # Try to return a log that has the score that we are checking for,
    # checking in order of oldest to most recent.
    for i in range(len(unchecked_logs)-1, -1, -1):
        if unchecked_logs[i].score == current_checking_score:
            return unchecked_logs.pop(i)
    # If no further recorded but unchecked logs exist, go to the next
    # isNewHead = true log
    while 1:
        unchecked_logs.append(getNextLog())
        if unchecked_logs[-1].isNewHead is True:
            break
    o = unchecked_logs.pop()
    current_checking_score = o.score
    return o

用普通的語言重新表述，這里就是反向掃描 CollationAdded 日志（對正確的分片），直到獲得一個 isNewHead = True 的日志。首先返回那個日志，然后用從老到新的順序返回所有與那個日志分值相同的且 isNewHead = False 的所有最新日志。隨后到前一個 isNewHead = True 的日志（即確保分值會比前一個 NewHead 低，但比其他人高），再到這個日志之后的所有具有該分值的最新 collation，而后到第四個。

這就是說這個算法確保了首先按照分值的由高到低、然后按照從老到新的順序檢查潛在的候選 head。

例如，假定 CollationAdded 日志具有以下哈希和分值：

... 10 11 12 11 13   14 15 11 12 13   14 12 13 14 15   16 17 18 19 16

那么，isNewHead 將被按如下賦值：

... T  T  T  F  T    T  T  F  F  F    F  F  F  F  F    T  T  T  T  F

如果我們將 collation 命名為 A1..A5、 B1..B5、 C1..C5 和 D1..D5 ，那么精確的返回順序?qū)⑹牵?/p>

D4 D3 D2 D1 D5 B2 C5 B1 C1 C4 A5 B5 C3 A3 B4 C2 A2 A4 B3 A1

監(jiān)視一個分片

如果一個客戶端在監(jiān)視一個分片，它應(yīng)該去嘗試下載和校驗(yàn)?zāi)莻€分片中的所有 collation（檢查任何給定的 collation，僅當(dāng)其父 collation 已經(jīng)被校驗(yàn)過）。要取得 head，需要持續(xù)調(diào)用 fetch_candidate_head()，直到它返回一個被校驗(yàn)過的 collation，也就是 head。通常情況下它會立即返回一個有效的 collation，或者最多因?yàn)榫W(wǎng)絡(luò)延遲或小規(guī)模的攻擊導(dǎo)致生成過幾個無效或者不可用的 collation，而需要稍微嘗試幾次。只有在遭遇一個真正長時間運(yùn)行的 51% 攻擊時，這個算法會惡化到 O(N) 的時間。

CREATE_COLLATION

這個處理由三部分組成，第一部分可以被叫做 GUESS_HEAD(shard_id)，其示意代碼如下：

# Download a single collation and check if it is valid or invalid (memoized)
validity_cache = {}
def memoized_fetch_and_verify_collation(c):
    if c.hash not in validity_cache:
        validity_cache[c.hash] = fetch_and_verify_collation(c)
    return validity_cache[c.hash]


def main(shard_id):
    head = None
    while 1:
        head = fetch_candidate_head(shard_id)
        c = head
        while 1:
            if not memoized_fetch_and_verify_collation(c):
                break
            c = get_parent(c)

fetch_and_verify_collation(c) 包含了從分片網(wǎng)絡(luò)取得 c 的所有數(shù)據(jù)（包括見證人信息）并校驗(yàn)它們的處理。上述算法等價于“選取最長有效鏈，盡可能的檢查有效性，如果其數(shù)據(jù)無效，則轉(zhuǎn)而處理已知的次長鏈”。這個算法應(yīng)該僅當(dāng)校驗(yàn)器執(zhí)行超時時才會停止，這就是該創(chuàng)建 collation 的時候了。每個 fetch_and_verify_collation 的執(zhí)行都應(yīng)該返回一個“寫集合”（參考上文的“無狀態(tài)客戶端”那節(jié)）。保存所有這些“寫集合”，把它們組合在一起，就構(gòu)成了 recent_trie_nodes_db 。

我們現(xiàn)在可以來定義 UPDATE_WITNESS(tx, recent_trie_nodes_db) 了。在運(yùn)行 GUESS_HEAD 的過程中，某節(jié)點(diǎn)會接收到一些交易。當(dāng)它要把交易（嘗試）包含進(jìn) collation 的時候，這個算法需要先運(yùn)行交易。假定交易有一個訪問列表 [A1 ... An] 和一個見證人 W，對于每個 Ai 使用當(dāng)前狀態(tài)樹的根取得 Ai 的 Merkle 分支，使用 recent_trie_nodes_db 和 W 一起作為數(shù)據(jù)庫。如果原始的 W 正確，并且交易不是在客戶端做這些檢查之前就已經(jīng)發(fā)出的話，那么這個取得 Merkle 分支的操作總是會成功的。在將交易包含進(jìn) collation 之后，狀態(tài)變動的“寫集合”也應(yīng)該被添加到 recent_trie_nodes_db 中。

下面我們就要來 CREATE_COLLATION 了。作為例證，這里是這個方法中可能的、收集交易信息處理的完整示意代碼。

# Sort by descending order of gasprice
txpool = sorted(copy(available_transactions), key=-tx.gasprice)
collation = new Collation(...)
while len(txpool) > 0:
    # Remove txs that ask for too much gas
    i = 0
    while i < len(txpool):
        if txpool[i].startgas > GASLIMIT - collation.gasused:
            txpool.pop(i)
        else:
            i += 1
    tx = copy.deepcopy(txpool[0])
    tx.witness = UPDATE_WITNESS(tx.witness, recent_trie_nodes_db)
    # Try to add the transaction, discard if it fails
    success, reads, writes = add_transaction(collation, tx)
    recent_trie_nodes_db = union(recent_trie_nodes_db, writes)
    txpool.pop(0)

最后，有一個額外的步驟，最終確定collation（給 collator 發(fā)放獎勵，也就是 COLLATOR_REWARD 的 ETH）。這需要詢問網(wǎng)絡(luò)以獲得 collator 賬戶的 Merkle 分支。當(dāng)?shù)玫骄W(wǎng)絡(luò)對此的回應(yīng)之后，發(fā)放獎勵之后的“后狀態(tài)根”（post-state root）就可以被計(jì)算出來了。Collator 就可以用 (header, txs, witness) 的形式打包這個 collation 了。這里，見證人（witness）就是由所有交易的見證和 collator 賬戶的 Merkle 分支組成的。

協(xié)議變動

交易的格式

交易的格式現(xiàn)在將變?yōu)椋ㄗ⒁膺@里包含了 賬戶抽象 和 讀/寫列表 ）：

    [
        chain_id,      # 1 on mainnet
        shard_id,      # the shard the transaction goes onto
        target,        # account the tx goes to
        data,          # transaction data
        start_gas,     # starting gas
        gasprice,      # gasprice
        access_list,   # access list (see below for specification)
        code           # initcode of the target (for account creation)
    ]

完成交易的處理過程也將變?yōu)椋?/p>

• 校驗(yàn) chain_id 和 shard_id 是正確的；
• 從 target 賬戶中減去 start_gas * gasprice wei；
• 檢查目標(biāo) account 是否有代碼，如果沒有，校驗(yàn) sha3(code)[12:] == target ；
• 如果目標(biāo)賬戶為空，使用 code 作為初始代碼，在 target 中執(zhí)行一個合約的創(chuàng)建；否則，跳過這個步驟；
• 執(zhí)行一個消息，使用：剩余的氣作為 startgas，target 作為地址，0xff...ff 作為發(fā)送者，0 作為 value，以及當(dāng)前交易的 data 作為 data；
• 如果上述任何一個執(zhí)行失敗，并且消耗了 <= 200000 的 gas（即 start_gas - remaining_gas <= 200000），那么這個交易是無效的；
• 否則，remaining_gas * gasprice 將被退還，已支付的交易費(fèi)將被添加到一個交易費(fèi)計(jì)數(shù)（注意：交易費(fèi) 不會 被直接加入 coinbase 余額，而是在區(qū)塊最終確認(rèn)時立即添加）。

雙層樹（two-layer trie）重新設(shè)計(jì)

現(xiàn)存的賬戶模型將被替換為：在一個單層樹中收錄進(jìn)所有賬戶的余額、代碼和存儲。具體來講，這個映射為：

• 賬戶 X 的余額：sha3(X) ++ 0x00
• 賬戶 X 的代碼：sha3(X) ++ 0x01
• 賬戶 X 的存儲鍵值 K：sha3(X) ++ 0x02 ++ K

請參考 ethresearch 上的帖子 單層樹中的雙層賬戶樹 。

此外，這個樹現(xiàn)在有了一個新的二進(jìn)制設(shè)計(jì)： https://github.com/ethereum/research/tree/master/trie_research 。

訪問列表

一個賬號的訪問列表看起來大概像這樣：

[[address, prefix1, prefix2...], [address, prefix1, prefix2...], ...]

從根本上說，這意味著：“這個交易可以訪問這里給定的所有賬戶的余額和代碼，并且賬戶列表中給出的每個賬戶的前綴中至少有一個是該賬戶存儲的一個鍵的前綴”。我們可以將其轉(zhuǎn)換為“前綴列表格式”，基本上就是一個賬戶的內(nèi)部存儲樹（storage trie）的前綴列表（參考前面的章節(jié)）：

def to_prefix_list_form(access_list):
    o = []
    for obj in access_list:
        addr, storage_prefixes = obj[0], obj[1:]
        o.append(sha3(addr) + b'\x00')
        o.append(sha3(addr) + b'\x01')
        for prefix in storage_prefixes:
            o.append(sha3(addr) + b'\x02' + prefix)
    return o

我們可以通過取得交易的訪問列表，將其變換為前綴列表格式，然后對前綴列表中的每個前綴執(zhí)行 get_witness_for_prefix，并將這些調(diào)用結(jié)果組成一個集合；以此來計(jì)算某個交易見證人。

get_witness_for_prefix 會返回樹節(jié)點(diǎn)中可以訪問以指定前綴開始的所有鍵值的一個最小集合。參考這里的實(shí)現(xiàn)： https://github.com/ethereum/research/blob/b0de8d352f6236c9fa2244fed871546fabb016d1/trie_research/new_bintrie.py#L250 。

在 EVM 中，任何嘗試對訪問列表以外的賬戶的訪問（直接調(diào)用、SLOAD 或者通過類似 BALANCE 或 EXTCODECOPY 的 opcode 的操作）都會導(dǎo)致運(yùn)行這種代碼的 EVM 實(shí)例拋出異常。

請參考 ethresearch 上的帖子 賬戶讀/寫列表 。

Gas 的消耗

待定。

后續(xù)的階段

通過分離區(qū)塊 proposer 和 collator，我們實(shí)現(xiàn)了二次方擴(kuò)展，這是一種快速、不徹底的中等安全權(quán)益證明分片，以此在不對協(xié)議或軟件架構(gòu)做太多更改的情況下增加了大約 100 倍的吞吐量。這也被用來作為一個完整的二次方分片多階段計(jì)劃的第一階段，后續(xù)階段大致如下：

• 第二階段（two-way pegging，即雙向限定） ：參考 USED_RECEIPT_STORE 章節(jié)，仍在撰寫；
• 第三階段，選項(xiàng)a ：將 collation header 作為 uncle 加入，而不是交易；
• 第三階段，選項(xiàng)b ：將 collation header 加入一個數(shù)組，數(shù)組中的元素 i 必須為分片 i 的 collation header 或者空字符串，并且額外的數(shù)據(jù)必須為這個數(shù)組的哈希（軟分叉）；
• 第四階段（tight coupling，即緊耦合） ：如果區(qū)塊指向無效或不可用的 collation，那么區(qū)塊也將變?yōu)闊o效；增加數(shù)據(jù)可用性證明。