以太坊Sharding详解

分片背景

Sharding是以太坊提出的一种解决方案，用于解决区块链（如Plasma和Raiden网络）的可扩展性问题。虽然Plasma和Raiden网络是脱链解决方案，但Sharding是一种链上解决方案，它通过改变主链本身的协议来改善主链的性能。

应用链式解决方案需要主网络的硬分叉，而脱链解决方案通过在主链外添加其他系统来消除对硬分叉的需求。

此外，Sharding是基于Proof of Stake（PoS）算法设计的，以支持以太坊假设从工作证明（PoW）到PoS的过渡。

Sharding的发展路线图如下：

Sharding的发展路线图

关于Sharding

首先，Sharding是一种链式解决方案，它将整个网络划分为按部分存储事务。然后并行处理这些事务以解决区块链可伸缩性问题。简而言之，数据被分割并存储到单独的分片中以进行处理。

Sharding结构

“Sharding”这个概念源于数据库领域。在数据库的上下文中，分片是对表进行水平分区以处理和存储大量数据的过程。

同时，以太坊Sharding将主链分为k个分片。每个分片并行处理网络上的整个事务。结果，通过多个分片提高了网络的总吞吐量，这与当前主链的事务处理机制形成对比。例如，假设有100个交易。通过10个分片链，每个分片链可以平均同时处理10个事务。

分片链的特点

为了更好地理解分片，必须注意分片链的组件和关键术语。然而，随着研究的进展，Sharding相关的组件和术语将继续发生变化。但同样，本文基于第1阶段规范。

分片链术语

collation：collation与分片链主链中的块具有相同的作用。排序规则由排序规则标题和事务列表组成。排序规则标题包含构成排序规则的信息，并通过提议者的签名提交给主链。这里，事务列表是排序规则中的事务列表。

collation

proposer：提议器本质上收集数据，建立一个建议，然后提交到的整理。此外，提案是未经验证的整理。

Collator：验证投标人提交的提案。对于每个时段，将一个分类器分配给一个分片，该分片在一段时间之前被随机选择。

Executor：将Collation标头传递给主链中的Sharding Manager Contract（SMC）。这会更改分片链的实际状态。（执行者出现在Sharding阶段3）

Period：分片链的整理标题到主链的提交期。这里的单位是主链中的块数。例如，如果PERIOD_LENGTH = 5，则生成5个块的是1个周期。

Lookahead period：在他们验证分片链中的整理之前，SMC伪随机分配Collator。同样，“Lookahead period”表示在某段时间之前每个整理器分配到哪个分片链。例如，如果LOOKAHEAD_PERIODS = 4，则表示在4个周期之前将collator分配给分片链。然后，Collator可以提前花时间下载分片链的状态信息。

Sharding设计框架

Sharding设计框架

1) Main chain 主链

以太坊2.0的初始部署阶段，是不需要对PoW链进行共识更改的。相反的是，我们会向PoW链添加一个注册合约，以存入ETH。这个注册合约会通过beacon链发出一个带有各种参数的日志。它不会进行验证，而是把注册逻辑发送给beacon链。

2) Beacon chain 信标链

Beacon链是PoS系统的“主链”，beacon链的主要职责是：

1. 存储并维护活跃、列队等待以及退出验证者的集合；

2. 处理交联（交联是beacon链“了解”分片链更新状态的主要手段）；

3. 处理逐块一致性，以及finality gadget；

4. 为每个分片指定所选的区块提议者；

5. 组织验证者进入委员会，对拟议的区块进行投票；

6. 用共识规则对验证者实施奖励和处罚；

7. 作为一个锚点，其中分片会注册它们的状态，以促进跨分片交易；

成为验证者的唯一机制，是往以太坊PoW主链发送一笔包含32 ETH 的交易至一个注册合约。

在注册器合约内质押的是 PoW 以太，获得的收据可以“创造”出PoS 以太。因为注册器合约无法撤销，所以 PoS 以太不能转回 PoW 以太，并且只有在验证者退出系统之时才能被退回到一个分片地址，而且 PoS 以太（在初期阶段）是不能交易的。双生以太并行的状况不会持续太久，除非发生以下情况[3]：

1. 状态转换即将实现，参与者可以选择撤销注册器合约，PoS 以太可以转换成等价值的 PoW 以太。

2. PoW 链变成一个分片或者存储合约，PoW 以太会被逐渐淘汰，并在匹配地址上自动转换为 PoS 以太（向后兼容）。

3) Shard chain 分片链

分片链只有一小部分的证明必须记录在主链上。 分片链上的交易处于自己独立的空间中，分片验证人只需要验证他们所关注的分片。 分片链也通过 POS 机制依附于主链，以获得更高层次的共识（higher level ofconsensus）。

跨分片通信。利用 UTXO 模型，并通过在主链上进行交易和创建一个receipt，用户可以将以太存入一个指定分片。分片链上的用户可以给定 receipt ID 创建一个消费 receipt的交易，来花费该 receipt。

交易的执行流程

交易的执行流程

以太坊主链每个时间段新生成的区块，都会将在此时间点之前的五个区块打包在内。这也被成为“LookAhead”。每个validator都会借由LookAhead来确认在未来他们将负责验证的是哪个分片。也就是验证者是先得知会被划分到哪个分片的。在指定时间段内，每个区块的验证者都会面临新一轮的随机选择（共5个区块，共五个validator）。当到达主链出块时间，所有validator都会将已校验的交易发送到交易池中。检验发起者需要向交验者支付激励。交验者下载潜在的分片提案。验证者验证数据的有效性，并挑选当前分片中最新区块，然后将collation header提交给主链。由矿工负责挖矿生成新的主链的区块。

SMC

可以简单地这么认为，分片中的交易都会被装入“校对块” （collation）。 与侧链类似，校对器（collator）只有一小部分会被记录到主链

以太坊2.0将以太网络分为两层，上层为现有的以太坊（也叫主链），基本保持不变；下层为各个分片，他们相互独立，拥有不同的账户空间。各个分片延生属于自己的链，并将最新区块头发给主链。主链收集各个分片的区块头，然后生成主链区块。值得注意的是，在主链上只保存各个分片的区块头，具体交易并不在主链上保存。

网络分层

Sharding Manager Contract（SMC）

SMC是一个智能合约，在分片链中发挥重要作用。SMC连接主链和分片链，管理整理器，提议器和整理树。SMC的作用对于分拆链参与主链是至关重要的。SMC的主要作用如下:

SMC

1. PoS系统：SMC管理整理者的存款。如果整理者在分片链中做错了什么，那么SMC就会削减一个人的存款。

2. 伪随机抽样：SMC伪随机地将整理器分配给整理池中的分片链。通过防止collator知道将分配哪个分片，可以降低整理器攻击特定分片的可能性。

伪随机抽样

3. 归类头验证：验证分片链提交的归类头。SMC通过addHeader函数进行验证，并且必须在启用排序规则之前进行验证。

4. 交叉分片通信：对于分片到分片的事务传输，必须在主链中创建一个收据。并且SMC管理此收据。当分片链中的用户创建收据时，收据将通过SMC传递到另一个分片链，并用于传输分片事务。这将在Sharding阶段4中实施。

5. 链式治理： SMC在链式治理中发挥着核心作用。Collators的投票通过SMC处理，以便这些投票可以在链上进行。

分片链机制过程

现在让我们看看分片链实际上是如何工作的。我希望您能够了解分片链的组件和术语，以了解分片链的机制过程。

分片链的机制过程

（1）首先，想要成为提议者的网络参与者通过SMC存入余额。

（2）同样，希望成为整理者的网络参与者通过SMC存款。

（3）Collators定期检查SMC状态，看它们是否被选为collator。

（4）SMC将伪随机分配给每个分片链。他们在前瞻期间下载了分片的先前状态。每个整理者都会从提议者那里收到提议的投标书。

（5）然后，Proposer将提案提交给整理者，其中包括交易。（提案是指尚未验证的整理。当Collator选择提案时，提议者从交易发起人处收取交易费。

（6）整理者进行投票以核实每个提案中的交易是否有效。

（7）如果超过2/3的整理者批准该提案的交易有效，则该提议是有效的整理。

Collator调用add_header函数，并在投票后将新创建的校对头发送给SMC。通过SMC上传的校对标题连接到主链。

Sharding将在阶段过程中添加执行程序和跨分片事务等功能。首先，我们研究了最基本的分片链操作流程和激励结构。让我们看一下分片链的fork-choice规则。

分片链的分叉选择规则

与主链一样，选择在分片链中分支的链是一个问题。当前主链具有fork-choice规则，当分支出现时选择最长边。但是，分片链中的Fork-choice规则更复杂。

在分片的情况下，主链和分片链基本上都很长。也就是说，1）选择最长的分片链，2）主链需要较长的分片链。让我们仔细看看下图。

分片在阶段1中，分片链中的分叉选择规则取决于最长的主链。也就是说，当分支发生时，分片链的选择不应该只是最长的分片链，而应该是最长主链中最长的分片链。

包含块B3的主链是最长链。因此，可以看出块B3有效并且核对C3有效。得分是块或整理的高度。

当添加块B3'时，上述链和下面的链连接在一起。在这种情况下，根据主链中的fork选择规则，随机确定相切时的有效块。

此时，块B3被选择为有效块，并且属于B3的核对C3是有效核对。

新的块B4'被添加到底链。现在底链是最长的主链。在这种情况下，当我们比较整理C3和整理C2的分数时，整理C3分数>整理C2分数。这意味着具有排序规则C3的分片链是较长的分片链。但是，分片链的选择取决于主链。包括在最长主链中的核对是核对C2，而不是核对C3。因此，尽管核对C2的分数较低，但核对C2变为有效核对并被选择为有效的分片链。这是分片链的Fork-choice规则。

分片状态存储

当一个验证器被要求在给定的分片上创建一个块时，它只会被提前几分钟通知。

在Ethereum 1.0中，创建块需要访问整个状态才能验证事务。在这里，我们的目标是避免要求验证器存储整个系统的状态。相反，我们允许验证器创建块只需要知道状态根的排序规则，将责任推送到事务发送者以提供“见证数据”（即Merkle分支），以证明事务影响的帐户的预先状态，并提供在执行事务后计算后状态根的足够信息。

在无状态模型中，节点永远不需要存储数据（无论该数据是历史，状态还是其他）。实际上，提供数据的责任由离线链（例如由交易发送方）承担。
使用非无状态范式（non-stateless paradigm）来实现分片，理论上是可能的；然而，这需要： (i) 租用存储空间来保持存储的有界性；并且 (ii) 验证器需要使用 O(c) 的时间在一个分片中创建区块。

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

通常，我们可以将传统的“有状态”客户端执行状态转换的函数描述为： 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) 大小的状态数据（已使用的 gas、receipts、bloom filter 等等）；witness 就是见证人；block 就是区块的余下部分。其返回的输出是：

• 一个新的 state_obj 包含了新的状态根和其他变量；
• 从见证人那里读取的对象集合（用于区块创建）；和
• 为了组成新的状态树（state trie）而被创建的一组新的状态对象。

这使得函数是“单纯性的”（pure），仅处理小尺寸对象（small-sized objects）（相反的例子就是现行的以太坊状态数据，现在已经 数百G字节 ），从而使他们可以方便地在分片中使用。

详细说明：https://ethresear.ch/t/state-minimised-executions/748

什么是跨分片通信以及如何实现不同分片之间的事务传输？

在以太网上实现分片时，分片之间以及分片内将存在事务请求。分片之间的事务称为交叉分片通信。交叉分片通信也称为基于收据的通信，因为它是基于事务产生的收据实现的。这里的关键是收据中的merkle证明通过主链从一个分片移动到另一个分片。

让我们在下图中了解交叉分片通信的具体过程。首先，假设有两个分片（分片M，分片N），并且它从分片M的帐户A向分片N的帐户B发送交易。

跨分片通信

1）通过将分片M的帐户A的余额减去100个硬币来制作收据。生成包含收据的merkle证明。

2）等待事务包含在排序规则中并包含在主链的块中。

3）当交易包含在主链的块中时，SMC将收据转移到分片N。分片N收到Receipt，确保收据未用过，并且将分片N的账户B的余额增加100个硬币。 然后花费收据。

4）分片N消耗收据并通过主链将其传递给分片M。分片M删除它持有的交易的收据。这样就完成了整个交易。

分片的当前状态是什么？[代码审查]

代码审查将分为六个部分。为了理解它们中的每一个，除核心部分外，其中一些被省略，检查以太坊github以获取详细代码。

下面描述运行分片链的过程。

已注册（Register_notary）

• Proposer / Collator在特定时间段内分配给分片（get_member_of_committee ）

• Collator在由提议者生成的提案上进行投票。

• 当收到一个三分之二表决归类创建（submitvote）

• 发送到SMC归类头（AddHeader）

• 投标/分页器关闭（Deregister_notary）

• 投标/分页器返回到存款（Release_notary）

代码审查将遵循上面的分片链操作流程。

分片链注册和伪随机抽样过程

首先，我将在全面的代码审查之前介绍一些概念。在这篇评论中，公证人的概念出现了。公证人意味着分片的参与者，并且是提议者和整理者的组合。公证人必须在池和注册表中注册才能履行其职责。

池和注册表是您应该了解的概念。池和注册表管理公证人的数据。池管理公证人的地址，并且Registry管理三个数据：Deregistered，pool_index和deposit。Deregistered是公证人被释放的期间，pool_index是公证人的索引，deposit是公证人的存款。公证人只能在取消注册期间的一段锁定期后收回押金。

最后，委员会是一组在特定时期放置在分片上的公证人。委员会注册通过SMC的伪随机抽样进行。公证人必须在委员会注册才能参与整理验证。

1. Register_notary

分片的公证登记从两次检查开始。首先，一个呼叫者的消息应该比指定存款（msg.value）（msg.sender）发送（NOTARY_DEPOSIT）和（2）其次，需要检查Msg.sender未在注册表中注册的值越大。（3 ）

2. Get_member_of_committee

现在注册了公证人，必须配置委员会以执行实际的整理验证。

Get_member_of_committee选择公证人在特定时间段对分片进行整理验证。Get_member_of_committee开始通过检查Shard_id的条件（6）的期间委员会的数目等于正确分片链的数目。

以下创建Sampled_index，它是SMC的伪随机采样。ethereum的智能合约没有随机功能。所以我们通过这个过程制作随机值。Sampled_index由三个值组成（Entropy_block_number，shard_id，index）。Entropy_block_number是前一时段的最后一个块。这三个值根据周期，分片和公证指数连续变化，从而实现伪随机抽样。（19〜30）

合并三个值后，使用sha3创建一个哈希值并除以sample_size。结果，选择与sampled_index相对应的值作为公证人委员会的成员。（32）

3. Submit_vote

Submitvote在委员会中对公证人进行投票，表明提案中包含的交易和数据有效。提出法定人数超过三分之二的提案作为整理，其标题提交给SMC。

Submitvote首先检查几个条件。重要的是检查Msg.sender是否是委员会成员（16）并确认Notary尚未投票（21）。公证人必须是委员会成员，不得重复投票。测试结束后，更新公证人的投票数。（24）这意味着公证人的投票得到反映。

每次调用Submitvote时，投票计数都会增加一。如果投票计数增加并且大于或等于法定人数（QUORUM_SIZE，委员会的三分之二或更多），则采用排序规则。（27~31）采用校对意味着准备好将校对头发送给SMC。

然后将整理期间更新为当前期间。最后，我们将处理并完成Submitvote事件（34-41）。

4. Add_header

Add_header将投票后生成的排序规则标头发送到主链中的SMC。公证人投票所采用的整理必须经过SMC验证才能通过验证。Add_header首先检查分片ID，句点和第一个提交的标题（7-12）

每个句点只能在一个分片中提交一个归类头。（12）

排序记录包含三个排序规则信息（chunk_root，proposer，is_elected）。（14-17）Chunk_root与块的transaction_root概念相同。Chunk_root包含有关排序规则中的事务的信息。

Records_updated_period记录当前时段。现在您已经提交了Collation标头，初始化current_vote（24）最后，您通过处理Addheader事件（27-30）完成

5. Deregister_notary

如果要停止排序规则验证，公证人会调用deregister_notary。Deregister_notary首先检查msg.sender是否在注册表中注册为公证人（2）

然后从公证人池中删除公证人。在公证池中，将索引值更改为none，并将公证池的大小减去1.（6到8）Notary注册表通过注销记录取消注册发生的时间段。

取消注册记录已在当前期间取消注册（10）最后，处理DeregisterNotary事件（12-13）

6. Release_notary

取消注册公证人后，可以通过调用release_notary来检索其实际存款。通过检查三个条件来启动Release_notary。最重要的是检查Msg.sender是否已经取消注册（3）只有已经取消注册的公证人才可以发布。在取消注册期间（4到5）的至少LOCKUP_LENGTH之后允许释放。

发布后，msg.sender中的所有信息都将从注册表中删除。已取消注册，pool_index和Msg.sender的存款均初始化为0（10-13）

记录了Msg.sender已从注册表中删除，并将存款返回给msg.sender（17）最后，通过处理ReleaseNotary事件（19-21）结束

参考资料

[1]V神相关twitter
[2]Beacon chain协议规范
[3]以太坊2.0分片链的详细概述
[4]区块链可扩展性解决方案4-1
[5]区块链可扩展性解决方案4-2
[6]Sharding doc
[7]其他资料