【楊鎮(zhèn)】【中譯修訂版】以太坊的分片技術(shù)官方介紹

楊鎮(zhèn)，資深軟件架構(gòu)師，資深開(kāi)發(fā)工程師。以太坊技術(shù)愛(ài)好者與布道者。

是Solidity官方文檔中譯項(xiàng)目的重要貢獻(xiàn)者，以太坊Homestead官方文檔中文版譯者，并對(duì)以太坊黃皮書(shū)中文版、Thunder共識(shí)白皮書(shū)中文版進(jìn)行了獨(dú)立校訂。目前致力于以太坊技術(shù)推廣及智能合約開(kāi)發(fā)、安全審計(jì)方向。

原文鏈接:    https://github.com/ethereum/sharding/blob/develop/docs/doc.md

作者: Vitalik

序言

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

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

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

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

在本文中，術(shù)語(yǔ) Collation 被用來(lái)與 Block（區(qū)塊）相區(qū)別，因?yàn)椋?(i) 它們是不同的 RLP（Recursive Length Prefix）對(duì)象：交易是第 0 層的對(duì)象，collation 是用來(lái)打包交易的第一層的對(duì)象，而 block 則是用來(lái)打包 collation（header）的第二層的對(duì)象； (ii) 在分片的情景中這更加清晰。通常，Collation 必須由 CollationHeader 和 TransactionList（交易列表）組成；Collation 的詳細(xì)格式和 Witness（見(jiàn)證人）會(huì)在 無(wú)狀態(tài)客戶端 那節(jié)定義。Collator（即用來(lái)打包 transaction 生成 collation 的某個(gè)地址，譯者注）是由主鏈上 驗(yàn)證器管理合約 的 getEligibleProposer 函數(shù)所生成的示例。算法會(huì)在隨后的章節(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：添加一個(gè)驗(yàn)證器到驗(yàn)證器集合中，驗(yàn)證器的大小就是函數(shù)調(diào)用時(shí)的 msg.value（也就是存入的以太幣數(shù)量）。這個(gè)函數(shù)會(huì)返回驗(yàn)證器的索引序號(hào)。

• withdraw(uint256 validator_index) returns bool：驗(yàn)證 msg.sender == validators[validator_index].addr，如果相等，它會(huì)將驗(yàn)證器從驗(yàn)證器集合中移除，并退還存入的以太幣。

• get_eligible_proposer(uint256 shard_id, uint256 period) returns address：使用一個(gè)區(qū)塊哈希（block hash）作為種子，基于預(yù)設(shè)的算法從驗(yàn)證器集合中選擇一個(gè)簽名者（signer）。驗(yàn)證器被選中幾率應(yīng)該與其存款數(shù)量成正比。這個(gè)函數(shù)應(yīng)該可以返回一個(gè)當(dāng)前周期內(nèi)的值或者以 LOOKAHEAD_PERIODS 為上限的任意未來(lái)周期內(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：嘗試處理一個(gè) collation header，成功時(shí)返回 true，失敗時(shí)返回 false。

• get_shard_head(uint256 shard_id) returns bytes32：返回驗(yàn)證器管理合約內(nèi)由參數(shù)所指定的分片的 header 哈希。

這里也有一個(gè)日志類型：

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

其中的 collation_header_bytes 可以用 vyper 語(yǔ)言來(lái)構(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)?nbsp;coinbase 和 number 在 vyper 語(yǔ)言中是保留字，所以它們被重命名為 collation_coinbase 和collation_number。

Collation Header

我們首先以一個(gè)有下列內(nèi)容的 RLP 列表來(lái)定義一個(gè)“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)的周期序號(hào)，這是由 period_number = floor(block.number / PERIOD_LENGTH) 計(jì)算出來(lái)的；

• period_start_prevhash 前一區(qū)塊，即區(qū)塊 PERIOD_LENGTH * expected_period_number - 1 的區(qū)塊哈希（這其實(shí)就是希望被包含進(jìn)的周期起始區(qū)塊之前的最后一個(gè)區(qū)塊的哈希）。分片中使用區(qū)塊數(shù)據(jù)的操作碼（例如 NUMBER 和 DIFFICULTY）會(huì)使用這個(gè)區(qū)塊的數(shù)據(jù)；只有 COINBASE 操作碼會(huì)使用分片的 coinbase；

• parent_hash 是父 collation 的哈希；

• transaction_root 是包含了當(dāng)前 collation 中的所有交易數(shù)據(jù)的樹(shù)（trie）的根哈希；

• state_root 是分片中當(dāng)前 collation 之后的新?tīng)顟B(tài)根；（也就是當(dāng)前 collation 中包含的所有交易執(zhí)行之后，且記賬收益分配之后得到的狀態(tài)樹(shù)根節(jié)點(diǎn)哈希，譯者注）

• receipt_root 是收據(jù)樹(shù)（receipt trie）根哈希；

• number 是 collation 編號(hào)，現(xiàn)在也是分叉選擇規(guī)則中的分值；且

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

• shard_id 是 0 到 SHARD_COUNT 之間的數(shù)值；

• expected_period_number 與當(dāng)前周期號(hào)相等（即 floor(block.number / PERIOD_LENGTH)）

• 在相同的分片中，一個(gè)具有 parent_hash 的 collation 已經(jīng)被接受；（即當(dāng)前 collation 的父 collation 已經(jīng)被接受，譯者注）

• 在相同分片中，當(dāng)前周期內(nèi)還沒(méi)有一個(gè)同樣的 collation 被提交；（也就是檢查要添加的 collation 是否已經(jīng)添加過(guò)了，譯者注）

• add_header 函數(shù)調(diào)用者的地址與 get_eligible_proposer(shard_id, expected_period_number) 所返回的地址相同。(即判斷要添加這個(gè) collation 的 proposer 是否是給定分片、給定周期的合法記賬人，譯者注)

當(dāng)滿足以下條件時(shí)， 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í)行一個(gè) collation 時(shí)的狀態(tài)轉(zhuǎn)換處理如下：

• 按順序執(zhí)行由 transaction_root 所指定的樹(shù)上的每個(gè)交易；并且

• 將 COLLATOR_REWARD 的獎(jiǎng)勵(lì)分配給 coinbase。

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

這里是用Viper寫(xiě)的一個(gè)簡(jiǎn)單實(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

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

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

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

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

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

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

交易打包格式

    [
        [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
    ]

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

無(wú)狀態(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'）。在無(wú)狀態(tài)客戶端模型中，節(jié)點(diǎn)不保存狀態(tài)，所以 apply_transaction 和 apply_block 可以寫(xiě)為：

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

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

• 一個(gè)新的 state_obj 包含了新的狀態(tài)根和其他變量；

• 從見(jiàn)證人那里讀取的對(duì)象集合（用于區(qū)塊創(chuàng)建）；和

• 為了組成新的狀態(tài)樹(shù)（state trie）而被創(chuàng)建的一組新的狀態(tài)對(duì)象。

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

客戶端邏輯

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

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

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

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

逆向匹配候選 head

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

unchecked_logs = []
current_checking_score = Nonedef 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

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

這就是說(shuō)這個(gè)算法確保了首先按照分值的由高到低、然后按照從老到新的順序檢查潛在的候選 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)視一個(gè)分片

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

CREATE_COLLATION

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

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

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

# Sort by descending order of gaspricetxpool = 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)

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

協(xié)議變動(dòng)

交易的格式

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

    [
        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)
    ]

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

• 校驗(yàn) chain_id 和 shard_id 是正確的；

• 從 target 賬戶中減去 start_gas * gasprice wei；

• 檢查目標(biāo) account 是否有代碼，如果沒(méi)有，校驗(yàn) sha3(code)[12:] == target ；

• 如果目標(biāo)賬戶為空，使用 code 作為初始代碼，在 target 中執(zhí)行一個(gè)合約的創(chuàng)建；否則，跳過(guò)這個(gè)步驟；

• 執(zhí)行一個(gè)消息，使用：剩余的氣作為 startgas，target 作為地址，0xff...ff 作為發(fā)送者，0 作為 value，以及當(dāng)前交易的data 作為 data；

• 如果上述任何一個(gè)執(zhí)行失敗，并且消耗了 <= 200000 的 gas（即 start_gas - remaining_gas <= 200000），那么這個(gè)交易是無(wú)效的；

• 否則，remaining_gas * gasprice 將被退還，已支付的交易費(fèi)將被添加到一個(gè)交易費(fèi)計(jì)數(shù)（注意：交易費(fèi) 不會(huì) 被直接加入 coinbase 余額，而是在區(qū)塊最終確認(rèn)時(shí)立即添加）。

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

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

• 賬戶 X 的余額：sha3(X) ++ 0x00

• 賬戶 X 的代碼：sha3(X) ++ 0x01

• 賬戶 X 的存儲(chǔ)鍵值 K：sha3(X) ++ 0x02 ++ K

請(qǐng)參考 ethresearch 上的帖子 單層樹(shù)中的雙層賬戶樹(shù) 。

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

訪問(wèn)列表

一個(gè)賬號(hào)的訪問(wèn)列表看起來(lái)大概像這樣：

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

從根本上說(shuō)，這意味著：“這個(gè)交易可以訪問(wèn)這里給定的所有賬戶的余額和代碼，并且賬戶列表中給出的每個(gè)賬戶的前綴中至少有一個(gè)是該賬戶存儲(chǔ)的一個(gè)鍵的前綴”。我們可以將其轉(zhuǎn)換為“前綴列表格式”，基本上就是一個(gè)賬戶的內(nèi)部存儲(chǔ)樹(shù)（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

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

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

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

請(qǐng)參考 ethresearch 上的帖子 賬戶讀/寫(xiě)列表 。

Gas 的消耗

待定。

后續(xù)的階段

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

• 第二階段（two-way pegging，即雙向限定） ：參考 USED_RECEIPT_STORE 章節(jié)，仍在撰寫(xiě)；

• 第三階段，選項(xiàng)a ：將 collation header 作為 uncle 加入，而不是交易；

• 第三階段，選項(xiàng)b ：將 collation header 加入一個(gè)數(shù)組，數(shù)組中的元素 i 必須為分片 i 的 collation header 或者空字符串，并且額外的數(shù)據(jù)必須為這個(gè)數(shù)組的哈希（軟分叉）；

• 第四階段（tight coupling，即緊耦合） ：如果區(qū)塊指向無(wú)效或不可用的 collation，那么區(qū)塊也將變?yōu)闊o(wú)效；增加數(shù)據(jù)可用性證明。

翻譯后記

本文最初是我應(yīng)以太坊中文社區(qū)（Ethfans.org）之邀做的翻譯稿，譯文于 2018/1/14 首發(fā)于【以太坊愛(ài)好者】公眾號(hào)：干貨 | V神·以太坊上的分片 。此版本對(duì)應(yīng)的原文 github commit 版本：0d0c74d41dec9ca55d1ff077400229ad524ce10a，更新時(shí)間 2018/1/5。

以上正文是我根據(jù)最新版原文修訂之后的版本，對(duì)應(yīng)的原文 github commit 版本：8a8fbe298e0490e3acbe20f496fb2aeba59b8a41，更新時(shí)間 2018/5/16。