分片：QuarkChain技术原理分析

最近听说QuarkChain在韩国热度比较高，于是抽了点时间研究了一下。

QuarkChain是一种“sharding-based blockchain”，即基于分片的区块链。它的主要目标是提高区块链的可扩展性（即TPS），同时还要兼顾不可能三角（安全性、去中心化性、可扩展性）。主要竞争对手：

以太坊分片：由于历史包袱比较重，实际应用时间不确定

OmniLeger：安全性有所妥协，如果要达到100000TPS，则只能容忍1%恶意节点

Zilliqa（ZIL）：ZIL是基于“交易分片”，而QuarkChain是基于“状态分片”。这两者的区别在于：交易分片虽然是多个交易在不同分片并行执行，但是每个节点仍需维护所有分片的完整数据。而状态分片则是每个节点只需要维护它所在的分片的数据，不需要关心其他分片。

1.系统架构

系统采用根链（Rootchain) / 分片（Shard）架构，将记账（Leger）和确认（Confirmation）功能分离，分片负责记账，根链负责确认，避免分片出现双花。

2.共识算法

QuarkChain的共识机制叫做"玻色子（Boson）"共识算法，借用了量子物理中的名词：夸克是最基本的物质，而玻色子是一个由夸克组成的基本粒子，用来传递力。

玻色子共识算法主要包含两个部分：

每个分片都运行一个叫根链优先（root-chain-first）的共识算法，分片向根链提交区块头，当出现分叉时，根链比较长的分叉胜出。这样保证攻击分片需要同时攻击主链，增大了攻击难度。

根链会收每个分片的税，通过调整税率可以使得根链上的算力更加集中

实际上，QuarkChain相当于设置了一个算力分配系数：

如果根链算力达到100%，则变成单链

如果根链算力变为0%，则分片变成多链（平行链）

QuarkChain要求根链必须包含超过50%的哈希算力，这样攻击者需要操纵超过25%的算力才能发动双花攻击，这实际上是在安全性和可扩展性之间的一种折衷。

另外，理论上根链和分片可以选用任意的共识算法（PoW/PoS/dPoS/PBFT etc.），但是目前测试网都是采用PoW。

3.挖矿算法

目前QuarkChain支持3种类型的哈希算法：

Double SHA256

Ethash

Qkchash

其中Double SHA256是比特币使用的哈希算法，而Ethash是以太坊使用的哈希算法。此外，他们在Ethash算法的基础上，提出了一种新哈希算法Qkchash，目的是打破流水线设计，增加很多if-then-else逻辑，使得分支预测失效，将来要执行的指令依赖于当前的状态（经常会变），从而达到抵抗ASIC挖矿的目标。

和Ethash的主要区别：找到第p小的数作为索引，访问后删除，然后插入新的随机数据（树的插入删除，流水线很难优化）。

我们可以看一下Testnet 2.0上根链和各分片使用的哈希算法情况：

另外，每个分片可以有不同的激励和挖矿难度，这为矿工的哈希算力构建了一个开发的市场经济模型。

4.账户系统

先介绍一下QuarkChain地址的生成方式：

其中Shard key一般有下面这几种生成方式，其中第一种最为常见：

源地址中任意选取32位数据，比如0, 5, 10, 15字节

钱包的IP地址

随机数

由于Shard key是随机的，可以保证所有账户均匀分布在不同的分片中，实现负载均衡。另外还有一个Shard id的概念：

对于普通账户，用户只需要保存一个私钥，通过“智能钱包”管理不同分片中的多个地址：

主账户：一个默认分片中的地址

副账户：其他分片中的地址

大多数交易是从主账户发起的，如果要调用另一个分片中的合约，临时切换到一个副账户地址，交易完成后再把余额转回主账户。

合约地址则有所不同，合约只能部署在某一个分片中，调用者必须与合约处于同一分片中（不同分片的智能合约不能相互调用）。因此，如果你的app涉及多个合约，必须部署到同一个分片中。

最后介绍一下重分片（reshard）：把一个分片分裂成2个分片，因此每次重分片都会导致分片数量翻倍。重分片后，Shard id自然也会发生变化，原先的智能合约代码会被替换为REVERT指令。

5.交易

根据上面的描述，交易可以分为以下两种类型：

片内交易：input/output地址都在同一个分片中

跨片交易：input/output地址在不同分片中

这里重点分析一下跨片交易：

分片1执行交易，然后生成一个cross-shard deposit record (R)

一个区块A中可能包含多个跨片交易，打包生成的记录发送给分片2

分片2收到：key=hash(A), value=[R, ...]

根链出块B，广播给分片2

分片2出块C，指向B，从B中得到hash(A)，从数据库中取出对应的R，修改receiver对应的状态

如何控制跨片交易的数量？

1.如果所有分片之间都要互相访问，复杂度是O(N2)

解决方案：Neighbour。每个分片最多有32个邻居，只能和邻居通信，或者通过邻居作为中介。

2.一个根链区块关联了太多跨片交易（Hot Shard问题）

根链中的每个跨片交易需要消耗9000 gas，通过区块油费上限限制包含的跨片交易数：

X

举个例子：

BLOCK_GAS_LIMIT = 10,000,000

DEPOSIT_GAS = 9,000

MAX_NEIGHBORS = 32

MAX_BLOCKS_PER_SHARD = 10

那么区块中包含的跨片交易数量 X 6.节点集群

QuarkChain使用多个诚实节点集群代替超级全节点，集群中的每个节点只验证链的一部分，只要它们重叠的部分能cover根链和所有分片，就可以验证整条链，并且不会出现单点失效问题。

为了激励形成这类集群，系统会提供一些激励，要求矿工回答一些和随机区块信息相关的问题（比如一个随机选择的分片中的一些随机区块的64位异或），这些问题是内存或者存储密集型的，从网络上下载这些随机区块是不现实的（低效）。

每个节点集群包含一个主服务器和多个从服务器，主服务器维护根链，从服务器维护多个分片：

7.测试结果

根据官方公布的Testnet 1.0测试结果：

256分片，50个节点集群（包含6450台服务器），总共向网络中提交了3,000,000笔交易，峰值达到14,000+ TPS。并且随着分片数的增加，这一数值还会继续上升。

8.总结

QuarkChain是区块链分片领域的一次探索，通过状态分片来提高系统的可扩展性，与此同时利用“根链优先”共识算法保证系统的安全性（25%攻击）。此外，在哈希算法、账户系统和节点集群方面都有一定的微创新，形成了自己的特色。当然，最终项目是否能够成功，取决于社区dApp开发者们的选择，让我们拭目以待。

参考：

https://quarkchain.io/QUARK%20CHAIN%20Public%20Version%200.3.4.pdf

https://github.com/QuarkChain/pyquarkchain/wiki