1. 作者简介
本文发表在SIGMOD 2021会议上，一作Mohammad Javad Amiri目前是宾夕法尼亚大学博后，在加州大学圣塔芭芭拉分校获博士学位，二作和三作都来自加州大学圣塔芭芭拉分校（都是ACM/IEEE Fellow）。
2. 背景介绍
可拓展性是区块链的一个重要性能指标，是指随着区块链网络中节点数目增加，系统对交易的处理性能也随之增长。分片技术是分布式数据库中常用来提升性能的技术方案，例如Google的Spanner。目前有许多工作研究将区块链分片来提高吞吐，但是都没能很好的处理跨片交易性能低下问题。
分片技术目前在公链和联盟链中都有运用，目的使区块链吞吐随着分片数目的增加线性增长。研究公链下分片问题的工作有Elastico，OmniLedger和Rapidchain。每个分片由节点随机组合产生，以通过概率来保障所有恶意节点均匀的分配到不同分片中。研究联盟链下分片问题的工作有Fabric，Cosmos，RSCoin，AHL，AHL是本文主要对比的一个方法，其依靠可信硬件允许片内拥有更少的节点同时满足PBFT的1/3安全假设。另外，AHL片间共识需要依赖协调者节点，片与协调者以及协调者内部通信开销大，不支持多个跨片交易并行共识。
当前分片工作对于片的安全性假设有两种，预先确定的错误节点数目和概率性的错误假设。例如Spanner，基于真实世界中的物理情况（例如现代的数据中心），假设每个分片中的大部分节点都是安全的（Paxos情况下恶意节点数目不会超过1/2，PBFT共识算法下恶意节点数据不超过1/3）。即一种预先确定的片内安全假设。其他例子还有ResilientDB和Blockplane。若没有这种假设，Sharper假设网络中所有好节点的数目远大于恶意节点数目，保证分片后每个片的绝大多数节点也是安全的，因此Sharper能够提供一种确定性的安全保障（这一点感觉很扯，自己做一个假设，然后论文将此作为了贡献点）。Elastico，OmniLedger和Rapidchain旨在为更加广域的公链网络提供分片服务，通过随机将节点组织成多个分片，将恶意节点均匀的分配到多个分片中，获得概率性的片安全保证。
3. 贡献点
文章工作致力于提高当前联盟链分片架构的交易吞吐，贡献点如下：
1) 将区块链节点和数据进行分片，每个片都是一个排序实例，在片内共识的基础上，支持对跨不同分片的交易并发共识（纯CFT或BFT）。
2) 解决对跨不同分片的交易并发共识时候出现的交易冲突、死锁（冲突和死锁出现在两个跨片共识涉及的分片存在交集时）、主节点故障问题。
4. Sharper架构
假设前提：
1. 网络中的所有节点存在于异步环境网络环境。（根据FLP定理，异步网络下只能保证一致性协议的安全性，若要同时满足活性异步网络是不够的，需要弱同步网络）；
2. 网络中的所有节点分成P个分片P={p1, p2,…, pN}，每个分片维护区块链的部分视图数据D={d1, d2,…, dP}，片中所有节点存储一个视图中的所有数据，如图1所示。对于运行Paxos或者PBFT共识协议时，每个分片中节点数目都满足2f+1或者3f+1安全条件，f为故障阶段或拜占庭阶段数目。并且同一个片中的节点是由地理上距离比较相近的一批节点组成，互相通信延迟较低。
3. 假设片中可能中存在强大节点能够与恶意节点串谋并增加通信延迟，破坏服务质量。另外，网络中的消息经过签名认证，恶意节点无法锻造诚实节点的消息。
图1 Sharper分片架构示例
Sharper架构示例如图1所示，根据workload或者数据分布，图中整条链被分成4个分片，t10,t11是片1的第一个和第二个执行的交易，它们都是片内交易。t12,22是片1和片2需要共同执行的跨片交易，并且都是片内的第三个执行的交易。跨片交易需要确定在相关片中执行的序号确保结果的正确性。对于那些所涉及的分片不存在交集的跨片交易，Shaper支持并行处理这些交易。例如交易t12,22和交易t32,42。
5. 共识机制
区块链中的共识机制负责让所有节点对请求按照某个相同的处理顺序达成共识，需协议要满足以下四个性质：
约同性（Agreement）, 所有诚实节点对相同的请求达成commit意见，且编号相同；
有效性（Validity），一个好节点commit的值也是某一个好节点的输入值；
一致性（Consistency），所有好节点按照相同的顺序commit相同的值
可终止性（Termination），最终所有节点都会commit一个值。
其中，前三个总结为协议安全性（Safety），最后一个总结为活性（Liveness）。
对单个分片而言，让片中所有节点对一笔交易保持一致的技术已经很成熟。然而对于跨片交易而言，交易需要在多个排序实例的节点之间保持保持一致，这给共识算法带来了新的挑战。本文分别研究了CFT和BFT网络节点错误环境下的跨片共识机制，值得一提的是，虽然现在区块链很多时候都在BFT假设下讨论共识问题，但研究CFT下的跨片共识的重要性作者也给予了解释，认为在存在准入机制的联盟链场景中，CFT共识可能就已经足够了，例如有名的Hyperledger Fabric项目中也只支持CFT下的共识。另外，先介绍CFT假设下的方案利于读者对BFT假设下方案的理解。
5.1 CFT网络假设
这一节讨论CFT假设下片内共识和跨片共识，以及需要解决的问题。
5.1.1 片内CFT共识
对于只涉及到一个分片的交易只要走片内共识（Intra-shard consensus）就可以了，Sharper在CFT网络中的片内共识采用Multi-Paxos算法，该算法由Lamport 1998年提出，选择一个稳定的节点长期作为主节点，协议相比原始Paxos吞吐高延迟低。
图2 Multi-Paxos
流程如下（因为网络中只有故障停节点，因此片内节点之间通信不需要对消息进行签名。只有在客户端发送交易、主节点广播commit消息以及回复客户端的时候需要签名，用于其他节点和客户端作为交易提交的证明）：
1. 客户端向分片的主节点发送签名后的交易，主节点收到交易后，为交易分配一个消息序号。
2. 主节点向片内所有从节点广播Accept信息并带上客户端发送的交易（附加交易编号，交易哈希）。
3. 从节点收到主节点发来的有效消息后，返回主节点Accept信息。
4. 主节点收齐f个accept消息后（加上自己的一共f+1个），向所有从节点广播交易和commit信息，返回客户端处理结果（交易哈希，commit信息，签名）。
5. 从节点收到主节点发送的commit信息与交易后，将交易打包成区块，并带上主节点签名的commit请求提交给各个区块链节点验签、执行。（假设交易在所有节点上都是确定性执行，这样最后所有节点状态一定一致）
5.1.2 跨片CFT共识
图3 跨片共识示例
跨片共识算法流程如下：
1. 客户端c向跨片交易所涉及的其中一个分片主节点π(pi)发送交易m=<REQUEST, op, tc, c>δc，op表示交易执行内容，tc表示交易时间戳（用于抵御重放攻击），c表示客户端c，δc表示客户端签名。
2. 分片主节点π(pi)给消息m分配编号hi，向交易所涉及分片的所有节点广播消息<PROPOSE, hi, d, m>，m是客户端给主节点发送的交易，d是交易哈希（6-7行）。
3. 所有从节点（片内/片外）接受到来自π(pi)的PROPOSE消息后，验证序号hi和消息内容：假如交易m的所有分片从节点正在等待前一笔跨片交易m’的COMMIT消息（交易m和m’涉及的分片有重合）。为了保证片间COMMIT顺序一致，节点将交易m存入缓存，等m’交易commit之后再处理m。否则，从节点直接向主节点π(pi)返回ACCEPT消息<ACCEPT, hi, hj, d, r>，其中hj表示片内从节点r给消息m分配的消息编号（8-10行）。（注：由于网络存在延迟，分片pj和分片pi收到交易m和m’的顺序也会不同，为了保证两个片的一致性，现在这种处理策略会造成死锁，后面会针对由于网络、并发带来的一系列问题继续优化协议）
图4 交易涉及的分片存在重合的场景示意
4. 主节点π(pi)收齐来自每个分片的f+1个ACCEPT消息，验证hj、hi和d，收集来自所有分片的从节点分配的消息编号集合(h1, h2, …, hk)，验证通过后向交易涉及的所有分片的节点广播COMMIT消息<COMMIT, [h1, h2, …, hk], d>δπ(pi)。δπ(pi)表示主节点签名，作为从节点向区块链COMMIT交易的证明，主节点π(pi)向客户端返回结果。如果客户端长时间没收到回复主节点，则向所有相关分片节点广播。如果分片节点判断该请求已经被处理，则向客户端返回结果，否则，从节点将消息转发给主节点，如果主节点不广播消息，判断主已经故障（9-13行）。
5. 分片的从节点接受到COMMIT消息后确认编号hj之前的所有交易都已经COMMIT（即使之前没有ACCEPT，因为之前可能宕机了没收到），然后向区块链提交交易，执行，改变状态（14-15行）。
5.1.3 协议可能出现问题：
若两个分片（Shard#1和Shard#2）的主节点同时向分片Shard pj的节点广播PROPOSE消息，如下图。由于网络存在延迟，分片Shard pj中不同节点收到分别来自两个分片的交易次序可能不同，既而不同节点赋予相同消息的编号不同，Shard#1和Shard#2主节点无法收齐f+1个编号一致的ACCEPT消息，主节点只能尝试重新广播，但仍然问题可能继续发生。
图5 交易冲突示例
此外，在特殊情况下，网络延迟还会让跨片共识出现死锁。例如前面图3中描述的场景，前面假设shard pj和shard pk中的节点先收到了交易m，后收到了交易m’。但是实际情况可能Shard#1与Shard#2同时发起跨片交易m和m’的共识。Shard pj收到的交易顺序是m、m’， Shard pk收到的交易顺序是m’、m。根据前面设置的处理方法，shard pj只有收到m的commit消息后才会处理交易m’，shard pk只有收到m’的commit消息后才会处理交易m。此时任何交易都无法达到COMMIT状态，协议陷入死锁。作者随后通过非常Naïve的方法解决这几个问题，最后还处理了主节点故障问题。
a) 处理交易冲突(主节点π(pi)收到的交易编号冲突)
主节点首先判断发生交易冲突的分片（图4中是Shard pj，没有发生交易冲突的分片不再需要处理），向这些分片重新发起跨片共识请求。为了避免继续发生冲突，Sharper调整策略，主节点π(pi)首先向分片Shard pj的主节点发送SUPER-PROPOSE消息（1-2行），然后主节点π(pj)为消息分配一个编号，并向自己的从节点和主节点π(pi)广播这条消息（3-4行）。从节点和主节点π(pi)删除之前收到的ACCEPT信息，从节点收到SUPER-PROPOSE消息后向主节点π(pi)回复交易序号一致的ACCEPT消息，主节点π(pi)收到f+1个ACCEPT消息后继续按照协议流程处理（5-6行）。
我们知道，造成交易冲突的原因是可能存在多个主节点同时向片内节点广播交易（同时网络延迟也是一个因素），每个从节点各自为交易编号，在跨片交易较多的情况下很容易造成上述的交易冲突问题。这时通过分片主节点π(pi)统一分配编号然后再向从节点广播可以避免这种问题发生，但是相比之前需要额外一次通信。在跨片交易比例较多的workload下sharper可以通过这种方法减少跨片共识冲突问题。
b) 处理交易死锁(主节点π(pi)收不齐f+1个票)
(1)
(2)
图5 交易死锁示意图
以上两种情景都可能造成交易死锁，方法与解决交易冲突时候类似：发起交易m和m’的分片主节点都向Shard pj和Shard pk的主节点发送SUPER-PROPOSE消息，然后Shard pj和Shard pk对交易m和m’的达成一致的COMMIT顺序，具体流程如下：
1）Shard pj和Shard pk的主节点相互比较交易m和m’在两个片内的顺序是否一致，若不一致则主节点之间确定一个相同的顺序。如果之前某个片已经发送过ACCEPT消息，则此时主节点发送SUPER- ACCEPT消息将之前的ACCEPT消息删除。
2）若交易m和m’由不相同的分片发起，那么不需要互相协调一个顺序，可以直接根据发起交易m和m’的分片ID确定m和m’的处理顺序。同样，如果之前某个片已经发送过ACCEPT消息，则此时主节点发送SUPER- ACCEPT消息将之前的ACCEPT消息删除。
c) 主节点故障（交易涉及到所有分片的主节点都可能）
从节点通过超时机制检测主节点故障，当Shard pj的一个节点收到来自主节点的一个PROPOSE消息后（片内交易/跨片交易）开始计时，时间阈值设为τf。跨片交易的τf大于片内交易的τf。如果τf到达后节点未收到COMMIT消息，怀疑主节点发生故障，解决方案分以下3种情况（按照从节点r与主节点π(pi)是否在同一个分片，不在同一个分片时候从分片主节点可能故障分类）：
i. 跨片交易，发起跨片交易主节点π(pi)故障，从节点r与主节点π(pi)不在同一个分片（例如主节点不发送COMMIT，发生冲突时不发送SUPER-PROPOSE）。
ii. 跨片交易，从节点r所在的分片的主节点π(pj)故障（例如交易冲突时候主节点不发送SUPER-ACCEPT）。
iii. 跨片/不跨片交易，主节点π(pi)故障，从节点r与发起跨片交易的主节点π(pi)在同一个分片（例如主节点不发送PROPOSE、SUPER-PROPOSE、SUPER- ACCEPT、COMMIT）。
对于第一种情况，从节点r向主节点π(pi)所在分片所有节点广播<COMMIT-QUERY, hi, hj, d, r>，随后可能出现三种情形：
Case 1:主节点已经发送COMMIT但是从节点r没有收到，这时候主节点向r重发COMMIT
Case 2:其他分片发生了交易冲突，主节点发送SUPER-PROPOSE后在等待SUPER-ACCEPT
Case 3:主节点已经宕机，分片主节点π(pi)所在分片所有节点重新选举主节点。
对于第二种情况，首先也是从节点r向主节点π(pi)所在分片所有节点广播<COMMIT-QUERY, hi, hj, d, r>（因为这时候节点r无法确认是主节点π(pi)故障还是自己的主节点π(pj)故障，因此先排除π(pi)），主节点π(pi)收到COMMIT-QUERY消息后向节点r所在分片所有节点广播SUPER-PROPOSE，这样从节点r怀疑自己的主节点π(pj)已经坏了。其实这种情况很少会发生，因为片内交易就可以检测出（即第三种情况），而且片内交易触发检查主节点的时间τf小于跨片交易设置的时限。其实，跨片交易由主节点π(pi)发起，若长时间未收到从节点的消息最先到达时间阈值τf，随后就可以率先检查π(pj)是否宕机（先向主节点π(pj)发送SUPER-PROPOSE，若没反应，向π(pj)所在分片的所有节点广播SUPER-PROPOSE）。
对于第三种情况，走传统Paxos协议的换主流程即可。
5.1.4 协议正确性证明（跨片）
这里主要证明跨片交易下几个性质，片内交易正确性由Paxos那样的协议保证，不做证明。回顾一下四个性质，假设节点r是诚实的。
约同性（Agreement）, 若节点r以编号h COMMIT交易m，那么其他正常节点也会以编号h COMMIT交易m（即不会以编号h COMMIT其他交易m’）。
证明：只有当节点收到来自每个分片的f+1个一致的ACCEPT消息后才会COMMIT，由于总节点个数是2f+1，片中不存在恶意节点，节点不会发送两个不同消息，所以分片中不会发出两组不一致的f+1个投票。
有效性（Validity），一个正常节点commit的值也是某一个正常节点的输入值；
证明：CFT环境下不存在恶意节点，节点只会宕机，自然成立。
一致性（Consistency），所有正常节点按照相同的顺序commit相同的值，例如前面提到的场景（图5（2），如何保证Shard pj和Shard pk按照相同的顺序提交m和m’，用前面的策略就可以解决）；
可终止性（Termination），客户端发起的一个请求最终所有节点都会处理完。
证明：交易冲突，交易死锁，主节点故障都已经被证明协议可以运行
5.2 BFT网络假设
这一节讨论BFT假设下片内共识和跨片共识，以及需要解决的问题。
5.2.1 片内BFT共识
片内可以选择现有的容拜占庭错误的一些方法，Sharper的片内共识使用PBFT，流程如下：
1.客户端发送向主节点发送消息m=<REQUEST, op, tc, c>δc，op是操作内容，tc是时间戳（用于抵御重放攻击），c是客户端。
2.主节点收到有效的客户端请求后，开始初始化此轮共识，为m分配一个编号，向片内所有节点广播PROPOSE消息（PBFT的pre-prepare阶段），带上自己的签名，包括消息m。
3.从节点收到来自主节点有效的PROPOSE消息后，其向所有节点广播ACCEPT消息（PBFT的prepare阶段）。
4.每个节点收齐2f+1个ACCEPT消息后，再向所有节点广播COMMIT消息。
5.当每个节点收齐2f+1个COMMIT消息后，将交易m与这2f+1个COMMIT消息一同发送给区块链节点，节点验证、执行。随后向客户端返回执行成功信息REPLY。
6.客户端收齐f+1个相同的REPLY消息后即可确认消息已经被处理。
图6 PBFT共识协议流程
5.2.2 跨片BFT共识
相比CFT场景下的跨片共识，由于BFT场景下主节点可能作恶，因此所有相关节点都需要相互广播ACCEPT消息和COMMIT消息。
图7 BFT跨片共识示例
协议的流程如下：
1. 首先客户端向主节点π(pi)发送签名的跨片交易请求，π(pi)收到请求后为请求分配编号hi，向跨片交易涉及的所有分片的节点广播PROPOSE消息<<PROPOSE, hi, d>δπ(pi), m>，d表示交易m的哈希（6-7行）。
2. 从节点r收到消息m的PROPOSE请求后，验证消息签名和交易哈希（如果此时从节点在等待前面一个跨片交易m’的COMMIT消息和前面CFT下场景一样，交易m与交易m’相关的分片有重合，并且r在其中的一个分片中，为了保证m和m’在两个片中COMMIT顺序一致），节点r暂不处理交易m’。）随后，从节点r为交易分配片内编号hj，向所有相关分片的节点广播ACCEPT消息<ACCEPT, hi, hj, d, r>δr，d表示交易哈希（8-10行）。
3. 从节点r收齐来自分片pj的2f+1个一致的ACCEPT投票，ACCEPT-LOCALpj(m,hi,hj,r)状态成立，若r收齐与交易m相关的所有分片的2f+1个一致的投票，ACCEPT(m,h,r)成立。从节点r向与交易m相关的所有节点广播<COMMIT, [hi,hj,…,hk], d, r>δr（11-12行）。
4. 从节点r收齐来自分片pj的2f+1个一致的COMMIT投票，COMMIT-LOCALpj(m,hi,hj,r)成立，从节点r向与交易m相关的所有节点广播<COMMIT, [hi,hj,…,hk], d, r>δr（13-14行）。
5. 从节点r执行交易，改变状态。返回客户端执行结果<REPLY, tc, c, o, r>δr，tc是交易m的时间戳，r是执行结果。客户端等待从每个分片收齐f+1个相同的REPLY结果。如果从节点r长时间没有收齐足够的来自某个片的f+1条COMMIT消息，节点r向片内广播请求。如果之前片内节点已经发过COMMIT，收到请求后重新发送。如果之前片内节点没有处理过这个消息，转发给主节点广播，若主节点没反应，怀疑主节点已经宕机。
5.2.3 协议可能出现的问题
a) 处理交易冲突
经分析，在上述跨片BFT共识问题中，从节r收到来自某个片的ACCEPT消息冲突可能由于以下两个原因造成：①发起共识的主节点π(pi)作恶，π(pi)发送给分片内不同节点交易m的编号hi不同，这个问题留在主节点故障部分介绍；②前面CFT环境下引起交易冲突的原因一样，分片同时参与多个跨片共识导致节点之间交易编号不一致，这里先介绍这个问题的解决方案，即假设主节点π(pj)没有作恶，从节点收到的2f+1个ACCEPT消息中hi和d是正确的。
解决方案：
与CFT网络下不同的是，由于在BFT网络下，片内节点也会互相广播ACCEPT消息。因此，当主节点收齐不了2f+1个一致的ACCEPT后，由片内主节点π(pj)向从节点广播SUPER-ACCEPT消息<SUPER-ACCEPT, hi, hj, d, π(pj)> δπ(pj)（1-2行）
从节点r收到SUPER-ACCEPT消息后，验证消息是否合法，验证主节点π(pj)是否诚实（根据大家这轮收到的hi），向交易相关的所有节点广播相同编号的SUPER- ACCCEPT消息<SUPER-ACCEPT, hi, hj, d, r>δr。（3-5行）
（注：在跨片交易比例较大的workload下，为了降低处理交易冲突带来的性能损失，与CFT类似，跨片共识多一次通信，由每个分片主节点分配编号转发交易）
b) 处理交易死锁
跟前面CFT场景下处理死锁的方式一样，不再赘述。
c) 主节点故障
与CFT下的情况相同，主节点故障分成3个场景处理：
i. 跨片交易，主节点π(pi)故障，从节点r与发起跨片交易的主节点π(pi)不在同一个分片（主节点发送的哈希值或者签名都是匹配的，但是从节点收到了f+1个hi不一致的ACCEPT消息）。
ii. 跨片交易，从节点r所在的分片的主节点π(pj)故障，发起跨片交易的主节点π(p i)没有作恶（发送给片内交易的hi一致，但是跨片交易hj不一致）。
iii. 跨片/不跨片交易，主节点π(pi)故障，从节点r与发起跨片交易的主节点π(pi)在同一个分片（例如主节点不发送PROPOSE、SUPER-PROPOSE、SUPER- ACCEPT、COMMIT）。
对于第一种情况，如果主节点π(pi)发给从节点r的消息哈希值或者签名不匹配，从节点可以验证出来，但是如果不是这个问题，而是主节点π(pi)发送给节点r分片的编号不统一，导致收齐不了2f+1个一致的ACCEPT消息。解决办法是节点r向主节点π(pi)所在分片中的所有节点广播<ACCEPT-QUERY, hi, d, r>δπ(r)，若主节点π(pi)所在的分片节点收到2f+1个相同d的ACCEPT-QUERY信息，则π(pi)所在的分片节点怀疑主节点作恶，启动换主。
对于第二种情况，从节点收到hj不一致的SUPER-ACCETP消息后启动换主流程。
对于第三种情况，从节点可以根据接受到的ACCEPT、ACCEPT-QUERY、COMMIT消息怀疑主节点作恶，随后利用类似PBFT的处理流程换主即可。
5.2.4 协议正确性证明（跨片）
约同性（Agreement）, 若节点r以编号h COMMIT交易m，那么其他好节点也会以编号h COMMIT交易m（即不会以编号h COMMIT其他交易m’）。
证明：由于节点之间会相互广播ACCEPT消息，如果已经从2f+1个消息判断出ACCEPT(m,h,r)了，如果还有ACCEPT(m’,h,r)，那么一定有至少一个节点发了两个不同的消息。
2. 有效性（Validity），一个正常节点commit的值也是某一个好节点的输入值；
证明：与PBFT类似，通过对消息签名以及2f+1个投票机制，确保消息不会被伪造，所有好节点最终都会COMMIT相同的值。
3. 一致性（Consistency），所有正常节点按照相同的顺序commit相同的值，例如前面提到的场景（图5（2），如何保证Shard pj和Shard pk按照相同的顺序提交m和m’，用前面的策略就可以解决）；
证明：与CFT下的证明思路相似（不同的只是在BFT跨片交易中从节点需要收齐2f+1个投票不只是f+1个），不再赘述。
4. 可终止性（Termination），客户端发起的一个请求最终所有节点都会处理完。
证明：交易冲突，交易死锁，主节点故障情况下都已经被证明协议可以运行
6 实验
实验测试延迟和吞吐
6.1实验环境
Amazon EC2 platform, each VM : 8vCPUs，15GB RAM，Intel Xeon E5-2666v3 3.50GHz
6.2实验设置
1. 测试CFT和BFT环境中不同workload下的吞吐，节点总数12，分片数目4，发现Sharper在跨片事务比例较小的时候性能表现最好。
2. 分片中节点数目增加，系统整体吞吐变化，节点越多延迟越高，主要是共识开销（90%跨片交易,10%片内交易）。
发文时比特币价格：$45,301.30
