转载请微信联系：huangdiezi，更多DAO、Web3、NFT、Metaverse资讯请关注老雅痞

介绍

本文档的目的是为任何希望了解分片提案的细节并实施它的人提供一个相当完整的规范和介绍。本文档仅描述了二次分片的“阶段 1”；阶段 2、3 和 4在这一点上超出了范围，超二次分片（“以太坊 3.0”）也超出了范围。

假设变量c表示一个节点可用的计算能力水平。在简单的区块链中，交易容量以 O(c) 为界，因为每个节点都必须处理每笔交易。二次分片的目标是通过两层设计来增加容量。第 1 阶段不需要硬分叉；主链保持原样。然而，一个合约被发布到主链，称为验证器管理器合约（VMC），它维护着分片系统。有 O(c)个分片（目前是 100 个），其中每个分片就像一个单独的“星系”：它有自己的账户空间，交易需要指定要在哪个分片里面发布，分片之间的通信非常有限（事实上，在第一阶段，它是不存在的）。

分片在一个简单的最长链规则权益证明系统上运行，其中权益在主链上（特别是在 VMC 内部）。所有分片共享一个共同的验证者池；这也意味着任何在 VMC 上注册为验证者的人，理论上都可以在任何时候被分配在任何分片上创建块的权利。每个分片的块大小/gas限制为 O(c)，因此系统的总容量为 O(c^2)。

分片系统的大多数用户将在主链上同时运行（i）完整（O（c）资源需求）或轻型（O（log（c））资源需求）节点，以及（ii）“分片客户端” " 它通过 RPC 与主链节点通信（假定该客户端是受信任的，因为它也在用户的计算机上运行），它也可以用作任何分片的轻客户端，作为任何特定分片的完整客户端（用户必须指定他们正在“监视”特定的分片）或作为验证节点。在所有情况下，分片客户端的存储和计算要求也不会超过 O(c)（除非用户选择指定他们正在监视每个分片；区块浏览器和大型交易所可能想要这样做）。

在本文档中，该术语Collation用于区分，Block因为 (i) 它们是不同的 RLP 对象：事务是 0 级对象，归类是封装事务的 1 级对象，块是封装归类（标头）的 2 级对象；(ii) 在分片的背景下更清楚。基本上，Collation必须由CollationHeader和组成TransactionList；Witness详细格式Collation将在无状态客户端的部分被定义。是主链中Validator Manager Contract函数Collator采样的collation提议者；该机制将在以下章节中介绍。getEligibleProposer

主链	分片链
堵塞	整理
块头	排序标头
Block Proposer（或Miner在 PoW 链中）	整理者

二次分片

常数

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

验证人经理合同 (VMC)

我们假设在地址VALIDATOR_MANAGER_ADDRESS（在现有的“主分片”上）存在 VMC，它支持以下功能：

deposit() returns uint256: 在验证器集合中添加一个验证器，验证器的大小是msg.value函数调用中的（即存入的 ETH 数量）。此函数返回验证器索引。
withdraw(uint256 validator_index) returns bool: 验证msg.sender == validators[validator_index].addr。如果是，则从验证人集中删除验证人并退还存入的 ETH。
get_eligible_proposer(uint256 shard_id, uint256 period) returns address：使用区块哈希作为种子，从验证者集中伪随机选择签名者。被选中的机会应该与验证者的存款成正比。该函数应该能够返回当前时期或任何未来时期的值LOOKAHEAD_PERIODS。
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: 尝试处理排序规则标头，成功时返回 True，失败时恢复。
get_shard_head(uint256 shard_id) returns bytes32：返回作为经理合约感知的给定分片的头部的头部哈希。

还有一种日志类型：

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

注意：coinbaseandnumber被重命名为collation_coinbaseand collation_number，因为它们是 vyper 中的保留关键字。

整理header

我们首先将“collation header”定义为具有以下值的 RLP 列表：

在哪里：

shard_id是分片的分片ID；
expected_period_number是此排序规则预期包含的期间编号；这计算为period_number = floor(block.number / PERIOD_LENGTH);
period_start_prevhash是块的块哈希PERIOD_LENGTH * expected_period_number - 1（即，它是预期周期开始之前的最后一个块的哈希）。分片中引用区块数据的操作码（例如 NUMBER 和 DIFFICULTY）将引用该区块的数据，但 COINBASE 除外，它将引用分片 coinbase；
parent_hash是父排序规则的哈希；
transaction_root是包含在此排序规则中的交易的树的根哈希；
state_root是排序后分片的新状态根；
receipt_root是收据树的根哈希；
number是排序规则的编号，也是现在分叉选择规则的分数；和

如果调用返回 true，则排序规则标头有效。add_header(shard_id, expected_period_number, period_start_prevhash, parent_hash, transaction_root, coinbase, state_root, receipt_root, number)在以下情况下，验证器管理器合约应该这样做：

至少为shard_id0，且小于SHARD_COUNT；
等于实际的expected_period_number当前周期数（即floor(block.number / PERIOD_LENGTH)）
parent_hash已接受具有相同分片的哈希的排序规则；
当前期间尚未提交同一分片的排序规则；
发送者的add_header地址等于返回的地址get_eligible_proposer(shard_id, expected_period_number)。

一个排序规则是有效的，如果：(i) 它的排序规则header是有效的；(ii) 在给定andparent_hash的state_root结果之上执行排序规则；(iii) 使用的总气体小于或等于。
state_rootreceipt_rootCOLLATION_GASLIMIT

排序状态转换函数

执行排序规则的状态转换过程如下：

transaction_root按顺序执行所指向的树中的每个事务；和
将奖励分配给COLLATOR_REWARDcoinbase。

getEligibleProposer的细节

这是 Viper 中的一个简单实现：

无状态客户端

LOOKAHEAD_PERIODS * PERIOD_LENGTH当验证者被要求在给定的分片上创建一个块时，他们只会收到几分钟的通知（准确地说，是值得通知的块）。在以太坊 1.0 中，创建区块需要访问整个状态才能验证交易。在这里，我们的目标是避免要求验证器存储整个系统的状态（因为这将是 O(c^2) 的计算资源要求）。相反，我们允许验证者创建只知道状态根的排序规则，将责任推给交易发送者以提供“见证数据”（即 Merkle 分支），以证明交易影响的账户的预状态，并提供足够的信息来计算执行事务后的状态后根。

（请注意，理论上可以在非无状态范式中实现分片；但是，这需要：（i）存储租金以保持存储大小有界；以及（ii）分配验证器以在单个分片中创建块 O( c) 时间。这个方案避免了这些牺牲的需要。）

数据格式

我们修改事务的格式，以便事务必须指定一个访问列表，枚举它可以访问的状态部分（我们稍后会更准确地描述这一点；现在将其非正式地视为地址列表）。在 VM 执行期间，任何尝试读取或写入事务指定访问列表之外的任何状态都会返回错误。这可以防止有人发送一个在随机执行上花费 500 万个 gas 周期的交易，然后尝试访问一个交易发送者和收集者没有见证的随机帐户，从而防止收集者包含交易并因此浪费整理者的时间。

在交易的签名主体之外，但与交易一起打包，交易发送者必须指定一个“见证人”，一个 RLP 编码的 Merkle 树节点列表，提供交易在其访问列表中指定的状态部分. 这允许整理者仅使用状态根来处理事务。发布整理时，整理者还为整个整理发送了见证人。

交易包格式

[

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

[node1, node2, node3....] # witness

]

整理格式

[

[shard_id, ... , sig], # header

[tx1, tx2 ...], # transaction list

[node1, node2, node3...] # witness

]

另请参阅无状态客户端概念上的ethresearch 线程。

无状态客户端状态转换函数

一般来说，我们可以将传统的“有状态”客户端描述为执行状态转换函数stf(state, tx) -> state'（或stf(state, block) -> state'）。在无状态客户端模型中，节点不存储状态。函数apply_transaction和apply_block可以改写如下：

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

state_obj包含状态根和其他 O(1) 大小的状态数据（使用的气体、收据、布隆过滤器等）的元组在哪里；witness是证人；并且block是该块的其余部分。返回的输出是：

一个 newstate_obj包含新的状态根和其他变量；
已读取见证人的一组对象（这对于创建块很有用）；和
为形成新状态树而创建的一组新状态对象。

这允许函数是“纯”的，并且只处理小型对象（与现有以太坊中的状态相反，目前为数百 GB），使其便于用于分片。

客户端逻辑

客户端将具有以下形式的配置：

{

validator_address: "0x..." OR null,

watching: [list of shard IDs],

...

}

如果提供了验证者地址，那么它会检查（在主链上）该地址是否是活跃的验证者。如果是，那么每次主链上的新周期开始时（即floor(block.number / PERIOD_LENGTH)变化时），那么它应该调用getEligibleProposer所有分片周期floor(block.number / PERIOD_LENGTH) + LOOKAHEAD_PERIODS。如果它返回某个 shard 的验证器地址i，则它运行算法CREATE_COLLATION(i)（见下文）。

对于列表i中的每个分片watching，每次主链中出现一个新的排序规则头时，它都会从分片网络下载完整的排序规则，并对其进行验证。它在本地跟踪所有有效的标头（有效性是递归定义的，即，要使标头有效，其父项也必须有效），并接受其标头得分最高的分片链作为主分片链，以及在哪里从 genesis 归类到 head 的所有归类都是有效且可用的。请注意，这意味着主链的重组和分片链的重组都可能影响分片头。

以反向排序顺序获取候选头部

为了实现观察分片和创建排序规则的算法，我们需要的第一个原语是以下算法，用于按从高到低的顺序获取候选头。首先，假设存在一个（不纯的，有状态的）方法，该方法获取某个给定分片中尚未getNextLog()获取的最新日志。CollationAdded这可以通过从头开始向后获取最近块中的所有日志，并在每个块内以相反的顺序查看收据。我们定义一个不纯的方法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日志（寻找正确的分片），然后等到你到达一个 where isNewHead = True。首先返回该日志，然后返回所有最近的日志，其分数等于该日志isNewHead = False，按从最早到最近的顺序。然后转到前一个日志isNewHead = True（这保证分数比前一个 NewHead 低 1），然后使用该分数转到所有最近的排序规则，依此类推。

这个想法是，该算法保证按照得分从高到低的排序顺序检查潜在的头部候选者，第二优先级是从最旧到最近。

例如，假设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

如果我们对排序规则 A1..A5、B1..B5、C1..C5 和 D1..D5 进行编号，则精确的返回顺序为：

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

观察碎片

如果客户端正在查看一个分片，它应该尝试下载并验证它可以在该分片中的任何排序规则（只有在其父级已经验证时才检查任何给定的排序规则）。要随时获取头部，请继续调用，fetch_candidate_head()直到它返回已验证的排序规则；该排序规则是头部。在正常情况下，由于延迟或创建一些无效或不可用排序规则的小规模攻击，这将立即或最多在几次尝试后返回有效排序规则。只有在真正长时间运行的 51% 攻击的情况下，该算法才会降级到 O(N) 时间。

创建_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)涉及c从分片网络中获取（包括见证人）的全部数据，并对其进行验证。上述算法相当于“选择最长的有效链，尽可能检查有效性，如果发现无效则切换到你知道的下一个得分最高的有效链”。该算法应该只在验证器用完时间并且是时候创建排序规则时停止。的每次执行fetch_and_verify_collation还应该返回一个“写集”（参见上面的无状态客户端部分）。保存所有这些写入集，并将它们组合在一起；这是recent_trie_nodes_db.

我们现在可以定义UPDATE_WITNESS(tx, recent_trie_nodes_db). 在运行GUESS_HEAD时，节点将收到一些事务。当需要（尝试）将事务包含到排序规则中时，需要首先在事务上运行此算法。假设事务有一个访问列表[A1 ... An]和一个见证W。对于每个Ai，使用当前状态树根并获取的 Merkle 分支Ai，使用recent_trie_nodes_db和W作为数据库。如果原件W是正确的，并且交易不是在客户端检查回来的时间之前发送的，那么获取这个 Merkle 分支将始终成功。在将事务包含到排序规则中后，状态更改中的“写入集”也应添加到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)

最后，还有一个额外的步骤，完成整理（给整理者奖励，也就是COLLATOR_REWARD ETH）。这需要向网络询问收集人帐户的 Merkle 分支。当网络对此进行回复时，可以计算应用奖励后的状态后根以及费用。然后整理者可以打包整理，形式为（header, txs, witness），其中见证是所有交易的见证的联合和整理者帐户的分支。

协议变更

交易格式

交易的格式现在变成了（注意这包括帐户抽象和读/写列表）：

[

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)

]

现在申请交易的流程如下：

验证chain_id和shard_id是否正确
start_gas * gasprice从target帐户中减去wei
检查目标account是否有代码。如果不是，请验证sha3(code)[12:] == target
target如果目标账户为空，在code初始化代码处执行合约创建；否则跳过这一步
执行一条消息，剩余gas为startgas，thetarget为to address，0xff...ff为sender，0 value，transactiondata为data
如果两次执行中的任何一个都失败，并且已经消耗了 <= 200000 gas（即start_gas - remaining_gas <= 200000），则交易无效
否则remaining_gas * gasprice退还，并且支付的费用被添加到费用计数器（注意：费用不会立即添加到 coinbase 余额中；相反，费用会在区块完成期间一次性添加）

两层 trie 重新设计

现有的帐户模型被替换为具有单层 trie 的模型，所有帐户余额、代码和存储都包含在 trie 中。具体来说，映射为：

账户 X 余额：sha3(X) ++ 0x00
账户 X 代码：sha3(X) ++ 0x01
账户 X 的存储密钥 K：sha3(X) ++ 0x02 ++ K

另请参阅单层 trie 中的两层帐户 trie上的 ethresearch 线程

此外，trie 现在是一种新的二进制 trie 设计：https
://github.com/ethereum/research/tree/master/trie_research

访问列表

帐户的访问列表如下所示：

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

这基本上意味着“交易可以访问给定账户的余额和代码，以及任何存储密钥，前提是账户列出的至少一个前缀是存储密钥的前缀”。可以将其翻译成“前缀列表形式”，本质上是底层存储树的前缀列表（见上一节）：

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

可以通过获取事务的访问列表，将其转换为前缀列表形式，然后为前缀列表形式中get_witness_for_prefix的每个项目运行算法，并获取这些结果的并集来计算事务的见证。

get_witness_for_prefix返回足以访问以给定前缀开头的任何键的最小 trie 节点集。在此处查看实现：https
://github.com/ethereum/research/blob/b0de8d352f6236c9fa2244fed871546fabb016d1/trie_research/new_bintrie.py#L250

在 EVM 中，任何访问（通过调用或 SLOAD'ing 或通过诸如或之类的操作码BALANCE）EXTCODECOPY访问列表之外的帐户的尝试都将导致进行访问尝试的 EVM 实例立即抛出异常。

另请参阅帐户读/写列表上的 ethresearch 线程。

gas成本

待定。

后续阶段

这允许一种快速而肮脏的中等安全性的权益分片证明形式，通过在块提议者和收集者之间分离关注点来实现二次扩展，从而在不对协议或软件架构进行太多更改的情况下将吞吐量提高约 100 倍. 这旨在作为全面推出二次分片的多阶段计划中的第一阶段，其后面的阶段将在下面描述。