前言
设计到的链：Harmony、Elrond、Cosmos、ETH 2.0、Polkadot、Near Protocol
一. 主流链所用的分片技术对比
1.0 Harmony
Harmony 是一个基于状态分片和 PoS 的高性能公链项目，它的分片架构由一条信标链和多条分片链组成，信标链提供包括去中心化的随机数，分片链 Header 的验证，接受验证节点的权益抵押等服务。
Harmony 怎么保证分片系统的安全性？
为了抵抗1%攻击，Harmony 采用了 EPoS(Effective Proof-of-Stake)的有效抵押机制和安全的随机分片技术(Random Sharding)，靠协议的规定把大户抵押的代币打散成许多细小的部分，并随机分配到多个分片里，这样任何人就无法把他抵押的代币集中到单一分片内，从而无法攻击单一分片。如下所示。
Harmony 如何防止节点被贿赂？
为了避免贿赂攻击，Harmony 引入了基于 Cuckoo Rule 的随机再分片机制（Resharding)，系统会每隔一天时间重新随机打散验证者的权利，并再分片，让攻击者很难锁定要贿赂的目标，没法成功攻击单一分片。Harmony 采用了独创的分布式随机数生成（DRG, distributed randomness generation）协议产生安全不可预测的随机数。见下图。
Harmony 如何优化跨片通信？
Harmony 采用了「Kademlia 跨片路由技术」，来控制跨片间通信的网络开销，并且利用「纠删码」对区块广播过程进行优化，使广播者的网络压力更小，避免发送者的网络瓶颈问题，从而实现高效的横向分片扩展。
1.1 Elrond
Elrond是一个自适应状态分片的高吞吐量公链，提出了一种改良的权益证明机制，称之为安全权益证明（SPoS）的共识机制，引入随机选择的共识组，抵押加评级的方式。 与 Harmony 类似，Elrond 也有一条主链，称之为公证链或元链（Notarization (Meta) chain）。
Elrond 如何跨分片通信？
Elrond 执行跨分片通信的策略是使用异步模型。Elrond 的每个块结构由一个区块头表示，它包含块随机数、轮次、提议节点、验证节点时间戳等信息，以及包含交易信息的微块（Miniblock），每个微块都包含所有事务。 在这个网络中，交易的验证和执行会先在发送方的分片中完成，然后在元链中进行公证并提供执行证明，之后再到接收方的分片中完成并更新余额等。
Elrond 如何保证跨分片通信时数据安全？
Elrond 使用了随机数来保证安全性，例如将区块提议者和验证者随机采样到共识组中，并在一个轮次结束后对分片之间的节点进行改组。
1.2 Cosmos
Cosmos 如何跨链交易？
Cosmos的区块链间通信协议（IBC）将不同区块链连接起来，达到价值（cosmos只能跨链传递币而不能传递其他信息）转移的目的。依赖节点对 relayer的信任。
Cosmos 如何保证链间交易数据安全？
Cosmos 没有解决分区安全性的问题，或者说 Cosmos 避开了安全性的问题，一旦某个分区被恶意节点攻陷，该分区可以任意向 Hub 提交伪造的交易，而 Cosmos Hub 不会去验证交易本身的合法性，是否信任该分区则完全是其他分区或者用户决定的，也就是说最终的安全性仅由该分区的验证者节点负责。
1.3 ETH 2.0
ETH 2.0 跨分片通信原理
借助信标链完成交易过程：1. 交易包含在某个分片的分片块中；2. 随机分配给该分片的权益委托节点验证并签名该区块；3. 被签名区块被包含在下一个信标块中；4. 下一个信标块通过Casper FFG共识生成；5. 每个分片块与下一个信标块通过哈希连接起来，通过哈希证明彼此的Merkle根，从而能够验证彼此的证据。更多解释参考此处。
ETH 2.0 如何进行跨分片通信？
以太坊的分片链和主链上都部署了一个分片管理智能合约（SMC），SMC由三个组件构成：
1. Proposer：维护交易池；收集交易为提案做准备（作为收集头部信息）；提交收集内容；
2. Collator：在指定时间段内，从所有分片的收集者池中为特定的分片随机选择收集者；收集提案并排序；
3. Executor：执行交易状态转换函数；提案者有可能成为执行者，执行者会优先选择手续费高的交易来执行；
SMC通过这三个组件处理来自共识节点、普通用户、分片链的交易，若是跨分片交易，主键在处理完交易后会使用SMC监听器通知分片链，从而做到跨分片交易，见下图。更多解释见此处。
ETH 2.0 如何保证跨分片数据的有效性？
ETH 2.0 使用纠删码结合Merkle证明数据的有效性。欺诈证明仅由 M 个Merkle 证明组成，证明检查算法验证证明，然后使用这 M 个块计算剩余的块，并检查完整的块集的默克尔根是否等于原始默克尔根。更多解释参考此处。
1.4 Polkadot
Polkadot 如何进行跨链通信？
转接桥（Bridge）桥在波卡的链间通信中有着重要作用，有三种不同的含义：
- 转接桥合约(Bridge Contracts)：通过在 Polkadot 的平行链和外部的区块链（如：Ethereum）上部署智能合约来达到桥的效果，以实现跨链的价值转移。
- 跨链通信(Cross-Parachain Communication)：由于平行链之间是可以通过 ICMP 进行链间通信的，而无需智能合约承担桥接的功能。ICMP 是 Polkadot 网络中的一个协议，它定义了在平行链或中继链之间无需额外信任的消息传递的方式。它非常依赖 Polkadot 网络中的中继链存在，若没有了中继链 ICMP 也就无任何意义。同样，ICMP 并不是一种消息或者格式的标准。
- 内置桥接模块(In-built Bridging Modules)：在 Polkadot 网络中，从非平行链中接收平行链上的消息很可能会在 Polkadot 的内置模块中完成，不需要在非平行链中部署智能合约扮演“虚拟平行链”，收集人可以直接收集整理该区块链上的交易，并提交给中继链，就像对平行链所做的那样。当前内置的桥接模块可能会考虑基于特定的链进行开发（例如：比特币、以太坊），这就意味着只要是内置交接模块支持的区块链就都可以直接桥接到 Polkadot 网络中，而无需通过智能合约进行桥接。
1和3是针对异构跨链通信，2是针对同构跨链通信。
Polkadot 如何保证跨链通信的数据可用性？
验证者会在网络中广播纠删码片段，至少 1/3 + 1 个验证者必须报告他们拥有的纠删码，一旦达到验证者的这个阈值，网络就通过消息根来验证平行链的 PoV块是否可用。
在 PoV 区块中有一个哈希链，从中继链状态根开始，该哈希链由3部分组成：1. 中继链轻客户端中的消息根证明；2. 哈希链头的 Merkle 证明；3. 哈希链扩展到前一个水印（由中继链区块号和平行链ID组成的散列表）的前一个区块号之前的区块。英版见此处。
在Polkadot中，对平行链的区块共识需要进行以下三个级别的有效性验证，更多解释见此处：
第一级有效性验证由平行链的验证人实现，可以防止收集人作恶。
第二级有效性验证由钓鱼人保证，可以防止平行链验证人作恶以及平行链验证人和收集人联合作恶。
第三级有效性检查是非平行链验证人执行的。
1.5 Near Protocol
Near 是基于全状态分片、对开发者友好的可拓展性公链。Near 与其他分片公链不同的是，它的技术架构并不是由一个信标链和多个分片链组成的，而是把系统建模成一个单独的区块链，在区块级别进行了分片，每个分片中有很多“段”。简单来说，Near分片是在同一个账本块里，之后进行细分，整个账本块保持不变。
Near Protocol 实现区块级别的分片以及重新分片
NEAR不是以交易数量来分割区块的，创世区块没有分割，就是1个[chunk]，见代码
pub fn genesis_chunks(
state_roots: Vec<StateRoot>,
num_shards: NumShards,
initial_gas_limit: Gas,
genesis_height: BlockHeight,
genesis_protocol_version: ProtocolVersion,
) -> Vec<ShardChunk> {
assert!(state_roots.len() == 1 || state_roots.len() == (num_shards as usize));
let mut rs = ReedSolomonWrapper::new(1, 2);
(0..num_shards)
.map(|i| {
let (encoded_chunk, _) = EncodedShardChunk::new(
CryptoHash::default(),
state_roots[i as usize % state_roots.len()].clone(),
CryptoHash::default(),
genesis_height,
i,
&mut rs,
0,
initial_gas_limit,
0,
CryptoHash::default(),
vec![],
vec![],
&vec![],
CryptoHash::default(),
&EmptyValidatorSigner::default(),
genesis_protocol_version,
)
.expect("Failed to decode genesis chunk");
// 创世chunk解码
let mut chunk = encoded_chunk.decode_chunk(1).expect("Failed to decode genesis chunk");
chunk.set_height_included(genesis_height);
chunk
})
.collect()
}
后面生成的区块依据区块生产者数量进行分割，若该数量不大于3，则区块被分割成1个[chunk]，否则被分隔成 (total_parts - 1) / 3 个，其中total_parts为区块生成者（或者隐藏验证者）数量，由创世文件配置，见代码：
pub fn decode_and_persist_encoded_chunk(
&mut self,
encoded_chunk: EncodedShardChunk,
chain_store: &mut ChainStore,
merkle_paths: Vec<MerklePath>,
) -> Result<(), Error> {
let chunk_hash = encoded_chunk.chunk_hash();
let mut store_update = chain_store.store_update();
if let Ok(shard_chunk) = encoded_chunk
//对chunk解码
.decode_chunk(self.runtime_adapter.num_data_parts())
.map_err(|err| Error::from(err))
.and_then(|shard_chunk| {
if !validate_chunk_proofs(&shard_chunk, &*self.runtime_adapter)? {
return Err(Error::InvalidChunk);
}
Ok(shard_chunk)
})
......
}
fn num_total_parts(&self) -> usize {
let seats = self.genesis_config.num_block_producer_seats;
if seats > 1 {
seats as usize
} else {
2
}
}
fn num_data_parts(&self) -> usize {
let total_parts = self.num_total_parts();
if total_parts <= 3 {
1
} else {
(total_parts - 1) / 3
}
}
NEAR中账户和合约都会分配一个分片，由于账户和合约的存储使用量不相等，因此某些分片的使用量或者大小可能会远超过其他分片的使用量或者大小，为了避免这种情况，NEAR根据特定条件定期重新平衡分片，最终是一组具有合理且平衡的交易量和存储使用量的分片。
如果每个分片的交易使用量的限制（比如Gas）或者每个节点的预期存储量超过特定阈值（比如大量块超过一半），则会新增分片数量并平衡每个节点的预期用量。
Near 如何跨链通信？
NEAR协议像传统的区块链一样，每个区块都包含所有分片的所有交易，但是此数据并不存在于单个物理区块中；因此，每个节点不用存储所有数据。相反，验证人仅存储其特定分片的交易，而且该区块中所有交易的列表是物理的存储在该网络的各验证人的「chunk」中。这一模式可以在不牺牲高吞吐量的同时，确保 NEAR 不会在跨分片交易中出现双花。「chunk」设计和资源的不断重新分配，使 NEAR 可以实现更高效的跨分片通信。
对于 NEAR 上的一个跨分片交易，上一个区块处理完之后，会生成一个带有需要与之交互的各分片的收据。在下一个区块中，chunk 生产者收集其负责的分片中的常规交易以及跨分片交易的交易收据。
Near 如何保证数据的可用性？
Near 也是通过「纠删码」来解决分片的数据的可用性问题，因为分片的存在，并不是所有的节点都有所有分片的状态，如果一些节点没有某些分片的状态，就难以保证某些数据的可用性。 Near 的解决思路是，一旦特定的块生产者创建了一个块，他们就会使用 (n, f+1) 个Code创建一个纠删码版本，其中 n=3f+1是块生产者的总数。然后，块生产者将纠删码部分分发给其他块生产者。这样，只要 f+1 个区块生产者在线并合作，任何块都可以重建。通过BLS 多重签名来证明纠删码状态的特定部分是否可用。
Near 状态有效性证明
NEAR通过”渔夫“来确保状态的有效性，在每个epoch开始时运行VRF将每个渔夫随机分配到指定数量的分片上，每创建一个块，渔夫都会下载分配给她们分片的所有块，然后通过纠删码重建，最后验证所有块。
为了证明状态转换的正确性，渔夫需要提供两个连续的状态哈希、中间的交易以及受Merkle证明影响的100MB数据。
Near 实现验证分片数据的有效性
pub fn validate_partial_encoded_chunk_forward(
&mut self,
forward: &PartialEncodedChunkForwardMsg,
) -> Result<(), Error> {
// 首先检查上一个chunk的哈希是否有效
let valid_hash = forward.is_valid_hash(); // check hash
if !valid_hash {
return Err(Error::InvalidPartMessage);
}
// check part merkle proofs
// 检查部分数据的merkle证明
let num_total_parts = self.runtime_adapter.num_total_parts();
for part_info in forward.parts.iter() {
self.validate_part(forward.merkle_root, part_info, num_total_parts)?;
}
// check signature
// 校验分片chunk的签名
let epoch_id =
self.runtime_adapter.get_epoch_id_from_prev_block(&forward.prev_block_hash)?;
let valid_signature = self.runtime_adapter.verify_chunk_signature_with_header_parts(
&forward.chunk_hash,
&forward.signature,
&epoch_id,
&forward.prev_block_hash,
forward.height_created,
forward.shard_id,
)?;
if !valid_signature {
return Err(Error::InvalidChunkSignature);
}
Ok(())
}
二. 各主流链所用的共识算法对比
在看下面内容之前，应该先对POW，POS，BFT这三种基础共识算法有所了解。
2.0 Harmony 共识
EPoS（有效权益抵押） + FBFT
使用EPoS进行节点身份确认，优化PBFT共识实现效率更高的FBFT共识
优点：
1. EPoS 不仅有效解决了抵押代币中心化的问题，同时支持抵押复利和抵押委托。
2. FBFT：基于BLS签名的快速拜占庭容错机制，可以提升共识的效率、出块的速度、每个块的容量。
2.1 Elrond 共识
SPoS（安全权益证明）+ PBFT
Elrond 通过随机选择共识组，与抵押和评级这些维度相结合的方式来达成共识，它与传统 PoS 不同的是，加入了对每个参与打包节点进行评级这个维度，以及共识组内通过 pBFT 进行签名确认。SPoS改进PBFT的leader-follower模型，使得leader和follower的选择具有随机性。SPoS优点是保持PoS机制的能耗友好性又不牺牲网络安全性。
PBFT的优点:
PBFT算法具有高交易通量和吞吐量，高可用性，易于理解。
PBFT的缺点:
1. 计算效率依赖于参与协议的节点数量，由于每个副本节点都需要和其它节点进行P2P的共识同步，因此随着节点的增多，性能会下降的很快，
但在较少节点的情况下可以有不错的性能，并且分叉的几率很低，不适用于节点数量过大的区块链，扩展性差。
2. 系统节点是固定的，无法应对公有链的开放环境，无法动态添加或删除，只适用于联盟链或私有链环境。
3. PBFT算法要求总节点数n>=3f+1(其中，f代表作恶节点数)，系统的失效节点数量不得超过全网节点的1/3，容错率相对较低。
2.2 ETH 共识
Casper FFG+CBC
FFG （Fridenly Finality Gadget）在工作量证明（如以太的 ethash PoW 链）的基础上，使用了权益证明。块链继续用 ethash PoW 算法增加区块，但是每50个块有一个 PoS “检查点”，通过网络验证者来评估区块的最终有效性（Finality）。
CBC（ Correct by Construction）协议在开始阶段是部分确定的，其余部分协议以证明能够满足所需属性的方式得到（通常协议被完全定义，然后被测试以满足所述属性）。
优点：
1. 权益证明减缓了中心化算力
2. 高能效
3. 权益证明（尤其是Casper）的最大优势是它的经济安全性
4. 提高扩展性（分片）
2.3 Polkadot 共识
NPOS（提名股权证明） + BABE + GRANDPA
波卡使用NPOS主要是为了选取共识节点，BABE和GRANDPA通过混合来高效的进行区块链的出块和确认。这样的混合共识比传统的PBFT共识速度更快，并且在速度更快的基础上并没有丢失掉安全性。将出块和确认区块两个阶段分开并且使用不同的算法是在区块链共识中值得学习的地方。通过这三种算法，Polkadot可以说在一定程度上高效的实现了Polkadot上区块链的共识算法。更多解释见此处。
2.4 Near Protocol 共识
Doomslug + Nightshade Finality Gadget
Near 采用了独创的 Doomslug 的共识机制，该共识机制允许一组权重最高的区块生产者只需要一轮通信就可以创建区块，区块的权重是所有验证者和区块生产者签名的累加，从而使得每个区块都不可逆。而且即使有 50% 的区块生产者不在线，也依然可以完成。 同时他们还推出了一种最终确定性工具，结合了以太坊 2.0 中使用的Casper FFG、Casper CBC和Polkadot 中使用的 GRANDPA ，称之为 Nightshade Finality Gadget（夜影确定性工具），它可以保证区块在不超过 1/3 恶意攻击者的情况下会被最终确定，进而增强了网络安全性。
优点：
虽然 Doomslug 使用确定性工具与其他BFT算法在单个区块上达到最终确定性需要相同的时间，但它最终确定的区块数量是 Tendermint 或 Hotstuff 的两倍，即它提高了两倍的吞吐量。
缺点：
Doomslug 最终确定块的速度比它产生区块的速度慢，因此在块被最终确定之前，有分叉的可能。
2.5 共识算法对比
PBFT、Tendermint 和 Hotstuff
相同点：PBFT、Tendermint 和 Hotstuff 都以非常相似的方式工作
共识协议发生在多个视图上,在一个视图中是乐观的，在每一个视图中，都有一个特定的领导者被分配去执行共识，领导者提出一个特定的结果。参与者等到有 ? 人对结果进行预投票，然后每个参与者发送对结果的预提交，一旦有来自 ? 参与者的预提交消息，就达成了共识。
不同点：
- 参与者交换消息的方式
在 Tendermint 中，参与者使用 gossip 协议，每个参与者在本地积累预投票和预提交消息；而在 Hotstuff 中，领导者积累消息并将它们发送，整个过程只需线性量的网络开销即可完成，唯一的二次开销是发送累积的预投票和预提交。 - 视图切换（View-Change）
在 PBFT 中，每个参与者都有一个计时器，用于测量自视图开始以来已经过去了多长时间，一旦计时器超过某个阈值，他们就会向下一个领导者发送视图更改消息。下一个领导者需要累积 ? 参与者的视图更改消息，并将新视图消息发送给他们。整个过程至少需要三次网络开销，而且也很难正确实现。在Tendermint中，每个阶段（pre-vote 和 pre-commit）都有超时，每当这样的超时被触发时，参与者发送相应空的 pre-vote 或 pre-commit，并移动到下一个阶段或视图。 Hotstuff 是流水线的，这意味着一个视图的预提交就是对下一个视图的预投票，非流水线版本所需的时间几乎是它的两倍。
三. 参考
https://near.org/blog/doomslug-comparison/
https://zhuanlan.zhihu.com/p/102152143