高质量区块链论文分享

实验室区块链论文被顶刊 IEEE/ACM ToN 接收

Huawei Huang, May 11, 2023

研究组近三年专注于区块链底层关键技术的研究，旨在提升区块链系统的运行性能。经过三年多的摸索，我们的技术路线逐渐发展为：以分片机制为特色，通过设计新型区块链底层协议与机制，让区块链系统运行得更高效、更健壮、更安全。

研究组一篇区块链分片机制的论文今日被IEEE/ACM Transactions on Networking (ToN/TNet) 接收为长文。IEEE/ACM ToN/TNet 是 CCF-A 类推荐期刊，是计算机网络方向三大顶刊（ToN, JSAC, TMC）之一，它要求每一篇能被接收的论文必须具备以下几个条件：足够新颖的研究选题，严谨的问题描述，有性能边界保证的算法设计，对提出的机制有充足的理论分析，以及无可挑剔的实验结果。

接下来介绍一下这篇论文。

Huawei Huang, Xiaowen Peng, Yue Lin, Miaoyong Xu, Guang Ye, Zibin Zheng, Song Guo, “Scheduling Most Valuable Committees for the Sharded Blockchain,” IEEE/ACM Transactions on Networking (ToN/TNet), 2023, pp. 1-15. To appear. [PDF]

论文简介

近年来，源自传统数据库领域的分片技术被应对到区块链，试图解决区块链系统的扩容问题 [1]。在分片区块链中，交易池中的交易可以由多个并行委员会并行处理。以这种并发的模式，分片区块链的交易吞吐量理论上可以被较大程度地提高。但是，分片区块链仍然面临一些技术挑战。其中，有个明显的系统层面的技术问题简述如下。例如图1所示的Elastico [2]方案中，当区块链节点组成若干委员会之后，在各个委员会的共识阶段，天然地存在不同的委员会对交易达成共识的速度不一致的问题。这个问题就是分布式并行计算系统中经典的 straggler “拖后腿”问题。这是因为不同的区块链分片委员会的异构处理能力导致了不均衡的共识延迟。这种不平衡的延迟给分片区块链系统的“最终委员会”带来了很大的累积等待时延。因此，区块链交易的确认时延会被大大增加，区块链系统的吞吐量会被显著降低。

图1 Elastico协议 [2] 中每轮共识的主要流程，其中 C1-C4为并行工作的分片委员会，C5为“最终委员会”，只有最终委员会产生的区块才会上链存储。

本文认为一个好的委员会调度策略可以减少在“最终委员会”造成的累积等待时延，从而有利于区块链的系统吞吐量。但我们经过调研发现，目前相关文献尚未提出一个针对这个问题的委员会调度方案。本文首先定义分片区块链中交易吞吐量与累积时延之间的动态权衡问题，然后将这个权衡问题表述为一个效用最大化问题。为了解决这一问题，我们提出了一种在线分布式随机探索算法，英文叫做 online distributed Stochastic Exploration (SE) algorithm。该算法可以为分片区块链在每一轮共识挑选出最有价值的分片委员会优先参与最终委员会的共识，旨在让每一轮共识尽量多地打包交易、并且尽量地缩短交易在并行工作分片内的等待时延。该算法还可以处理分片委员会的动态加入和失效事件。本文还对提出的算法的收敛时间和委员会失效带来的性能扰动进行了严格的理论分析。实验环节，本文使用了真实区块链历史交易数据集进行模拟仿真。结果表明，提出的算法可以选择最有价值的部分分片委员会参与最终共识，加速区块的上链。

实验平台

本文的实验工具是实验室自行开发的区块链底层协议验证平台，名为 BlockEmulator。除了本文之外，该实验平台还被其他几篇论文所采用，例如 BrokerChain [3], tMPT [4], MVCom [5], 以及分片账户图划分算法 [6]。

我们即将把 BlockEmulator 开源给外界使用，敬请关注！

参考文献

[1] Zibin Zheng, Wuhui Chen, Huawei Huang [Book] “Blockchain Scalability,” Springer, 1^st edition, 2023.

[2] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in Proc. of ACM CCS, 2016, pp. 17–30.

[3] Huawei Huang, X. Peng, J. Zhan, S. Zhang, Y. Lin, Z. Zheng, S. Guo, “BrokerChain: A Cross-Shard Blockchain Protocol for Account/Balance-based State Sharding,” in Proc. of INFOCOM, May 2022.

[4] Huawei Huang, Yetong Zhao, Zibin Zheng, “tMPT: Reconfiguration across Blockchain Shards via Trimmed Merkle Patricia Trie,” IEEE/ACM International Symposium on Quality of Service (IWQoS), 2023.

[5] Huawei Huang, Zhenyi Huang, Xiaowen Peng, Zibin Zheng, Song Guo, “MVCom: Scheduling Most Valuable Committees for the Large-Scale Sharded Blockchain”, ICDCS, July 2021.

[6] C. Li, Huawei Huang, Y. Zhao, X. Peng, R. Yang, Z. Zheng, and S. Guo, “Achieving scalability and load balance across blockchain shards for state sharding,” in Proc. of 2022 41st International Symposium on Reliable Distributed Systems (SRDS’22), 2022, pp. 284–294.

针对 PoW 区块链的自适应双花攻击 (TDSC’23)

Jian Zheng, Huawei Huang*, Zibin Zheng, Song Guo, “Adaptive Double-Spending Attacks on PoW-based Blockchains”, IEEE Transactions on Dependable and Secure Computing (TDSC), 2023.

近日，HuangLab 一篇区块链新型“双花攻击”的论文被期刊 IEEE Transactions on Dependable and Secure Computing (TDSC) 接收，该期刊是网络与信息安全领域 CCF-A 类期刊。

论文下载地址：https://www.researchgate.net/publication/369982091_Adaptive_Double-Spending_Attacks_on_PoW-based_Blockchains

本论文简介如下。

一、研究背景与动机

工作量证明（Proof-of-Work，PoW）是当前应用最为广泛的区块链公链共识，双花攻击则是PoW区块链面临的经典安全性挑战 [1]。以比特币为代表的PoW 区块链使用最长链原则判断主链。交易方通过交易上链后等待主链继续生成数个区块，以保证交易的安全性，因为在PoW区块链中以小于50%的算力持续生成一条比主链更长的分叉是非常困难的。而双花攻击的基础步骤是：攻击者首先向受害者发起一笔交易，然后生成并隐藏一条比主链更长的分支；当受害者认为交易已经在主链上完成时，攻击者释放隐藏的分支替代当前主链，实现对受害者交易的回滚，达成一笔交易的“双花”。

尽管已经有很多研究讨论了双花攻击及其它各种分叉攻击变种的威胁和防御手段 [2-4]，我们发现在特定条件下攻击者仍然可以利用双花攻击对 PoW 区块链的安全性产生威胁。

本文展示了我们提出的两种双花攻击的变种——自适应双花攻击（Adaptive DSA）和强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA），旨在帮助 PoW 区块链社区对双花攻击威胁进行更好的分析与防范。

二、本文贡献

本文提出了自适应双花攻击（Adaptive DSA），通过随机动态变化（Stochastic Dynamic Programming）的办法，分析了攻击者对不同目标价值的交易可能采取的收益最大化策略。
本文提出了强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA），考虑了攻击者利用区块链网络特征迷惑误导诚实矿工时，可能采取的收益最大化策略。
本文通过代码模拟上述两种双花攻击，分析攻击者可能采取的攻击策略。实验表明，攻击者在使用本文提出的双花攻击方法可以将发动双花攻击的算力降低到远小于50%，在攻击者最理想的情况下仅需要全网5%的算力就可以保证期望收益为正。

三、提出的新型双花攻击的简介

1. 核心思想

虽然攻击者在算力少于50%时，难以持续生成比主链更长的支链，但受害者往往只会等待数个区块，也就是说攻击者在短时间内生成一条比主链更长的分支即可实现双花攻击。攻击者的收益包括生成受害者交易的金额和区块的出块奖励，那么攻击者可以根据受害者交易金额和当前隐藏分支出块情况进行动态决策，即自适应双花攻击（Adaptive DSA）。攻击者还可以更进一步，通过人为提前释放部分隐藏分支来分散诚实节点算力，即强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA）。

2. 攻击流程

2.1. 自适应双花攻击（Adaptive DSA）

在自适应双花攻击中，攻击者根据目标交易金额b、隐藏分支当前区块数量i、主链当前区块数量j进行动态决策：继续攻击or放弃攻击。

**图2. 隐藏分支当前区块数量 i 为1，主链当前区块数量 j 为5的情况.**

2.2. 强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA）

强化自适应双花攻击是在自适应双花攻击的基础上，进一步考虑攻击者可以利用网络特征分散诚实矿工的算力。如图3所示，当攻击者占据全网算力比例为p，诚实矿工占据全网算力比例为q时，攻击者释放与主链等长分支，将会有部分诚实矿工被误导，选择跟随在攻击者的分支上继续进行挖矿，从而间接地加强了攻击者的算力，使双花攻击的算力比例阈值进一步降低。

**图3. 占据全网算力比例为 p 的攻击者释放与主链等长的分支时可能发生的诚实矿工算力转移.**

四、实验结果

实验设置：本文使用 C++ 语言进行了文中两种双花攻击——自适应双花攻击（Adaptive DSA）和强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA）的simulation实验。我们使用了经典PoW区块链Bitcoin作为实验环境的相关参数设定参照。

主要实验结果：我们首先测试了确认区块数量与攻击者收益的关系。如图4所示，对一笔价值200btc的交易，常规的6个确认区块只能对抗通常的双花攻击，并不能有效防御本文提出的两种双花攻击。图5展示了对于不同交易金额，抵御本文攻击所需要的最小确认区块数量。

如图6所示，随着攻击者算力比例的增加，攻击者可以选择的交易逐渐增多。当攻击者算力比例超过30%时，选择对任意交易发动攻击都可以保证期望收益为正。

图7展示了对于同样的交易金额，攻击者收益随出块奖励的减少而增加。结果表明，除了随着比特币等PoW区块链逐渐降低出块奖励，采用本文攻击方法的攻击者的收益将逐渐提高，这意味着本文提出的自适应双花攻击（Adaptive DSA）和强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA）将会对PoW区块链产生越来越大的威胁。

**图4. 对一笔价值 200 BTC 的交易，验证区块的数量与攻击者收益的关系**.

五、本文总结

本文提出了两种针对PoW区块链的双花攻击——自适应双花攻击（Adaptive DSA）和强化自适应双花攻击（Reinforcement Adaptive DSA，RA-DSA），旨在帮助 PoW 区块链社区对双花攻击威胁进行更好的分析与防范。攻击者在使用本文提出的双花攻击时，会对PoW 区块链的安全性造成严重威胁。实验表明，攻击者在使用本文提出的新型双花攻击的方法可以将发动双花攻击的算力降低到远小于50%。

参考文献

[1] Nakamoto S, Bitcoin A. A peer-to-peer electronic cash system[J]. Bitcoin.–URL: https://bitcoin. org/bitcoin. pdf, 2008, 4(2).

[2] Garay J, Kiayias A, Leonardos N. The bitcoin backbone protocol: Analysis and applications[C]//Advances in Cryptology-EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part II. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015: 281-310.

[3] Eyal I, Sirer E G. Majority is not enough: Bitcoin mining is vulnerable[J]. Communications of the ACM, 2018, 61(7): 95-102.

[4] Nayak K, Kumar S, Miller A, et al. Stubborn mining: Generalizing selfish mining and combining with an eclipse attack[C]//2016 IEEE European Symposium on Security and Privacy (EuroS&P). IEEE, 2016: 305-320.

tMPT: 区块链分片重组实现方案 (IWQoS’23)

Huawei Huang, Yetong Zhao, Zibin Zheng*, “tMPT: Reconfiguration across Blockchain Shards via Trimmed Merkle Patricia Trie”, IEEE/ACM International Symposium on Quality of Service (IWQoS), June 2023.

近日，HuangLab 最新的一篇区块链分片技术的论文，被国际会议 IWQoS 接收，该会议2023年的论文接受率为 62 / 264，竞争颇为激烈。本篇论文简介如下。

一、研究背景与动机

分片技术是提高区块链可扩展性的一种可行的技术路线 [1-4]。通过将所有共识节点划分至多个分片中，分片技术可以帮助区块链实现对交易的并行处理。因此，分片技术可以大大提高区块链网络的吞吐率，适用于交易到达速率高的区块链平台。

然而，分片技术的引入将区块链系统的安全性从整个网络分摊至单个分片，因此需要一定的保护机制来保证每个分片的安全性。而分片重组是一个较为可行的增强分片区块链系统安全的手段。在分片重组的过程中，当共识节点迁移到一个新的分片时，该节点需要同步新分片中的交易或账户的状态等信息，以便能够允许共识节点在新分片中可以进行交易的验证。Elastico [1] 提出定期对各个分片的节点进行定期洗牌，然后将共识节点随机分配给各个分片。RapidChain [2]、Omniledger[3] 等论文则设计了允许分片节点部分同步的方法，以便减少分片重组过程对整个区块链系统的影响。

通过调研现有的区块链分片相关的工作，我们发现对于分片区块链的分片重组的研究尚处于很初始的阶段，尚且缺少一个对分片进行重组的实现方案。本文展示我们提出的一种分片重组方案，旨在减少分片重组所需的时间，同时确保分片区块链系统的安全性。

二、本文贡献

本文提出了一个分片重组协议，在保证分片系统安全性的同时，还可提高分片重组的效率。
我们为分片重组协议设计了 trimmed Merkle Patricia Trie (tMPT) 数据结构，并运用 tMPT 对分片内的状态树进行压缩，旨在提高分片重组的效率。为了进一步减少分片重组过程对区块链系统的影响，我们还进一步提出了一种分片间部分重组的方案。
我们在模拟系统上对分片重组过程进行了原型系统的实现，并将其部署在阿里云服务器中。实验表明，本文提出的方法在分片重组效率上优于现有的数据同步方法，所提出协议的吞吐量比以太坊的“完全同步”（Full Synchronization）的方法高 198%。

三、提出协议的简介

1. 核心思想

根据 Ethanos [5] 的调查结果，以太坊上的交易存在着“时间局部性”，即部分账户在一周内会进行多次交易。这些活跃账户的状态数据也会在短时间内经历多次更新。受此启发，本文提出的方案通过仅在分片重组时才为共识节点同步活跃账户的状态数据，这样可大大减少分片重组时传输的数据量，从而可提高分片重组的效率。

2. 系统简介

2.1. 角色介绍

所提出的协议包括两种类型的节点和对应的两种类型的分片。

验证节点 (Validator node). 验证节点保存其曾参与验证的历史区块的数据和对应的账户状态。通过存储活跃账户状态，验证节点可以进行新区块的交易验证；通过存储历史区块数据，他们可以为用户提供历史区块查询服务。验证者节点组成多个验证分片。
见证节点 (Witness node). 见证节点保存全网的账户状态和节点数据，负责生成重组方案并帮助验证节点进行交易验证。见证节点组成见证分片。

2.2. 系统运行流程

如图2所示，我们将系统运行过程划分为共识阶段与重组阶段。共识阶段中，验证分片执行片内共识，处理交易并出块。重组阶段中，见证分片生成重组方案，协助验证分片进行分片重组，并更新账户状态信息。具体步骤如下：

Stage 1. 每隔一定的出块间隔，见证分片利用VRF随机函数生成一份重组方案，并在分片内对该重组方案进行共识。
Stage 2. 重组方案被广播至全网，各分片在当前区块共识完毕后进入重组阶段。
Stage 3. 重组阶段开始。各工作分片分片遍历当前状态树，删去状态树中最近访问周期小于k的节点，得到epoch k的部分状态树.
Stage 4. Epoch k的部分状态树被发送至重组后该分片的对应的验证节点和见证分片。
Stage 5. 编排状态树信息。验证分片收到各分片发来的状态树，并于该分片的历史状态信息进行合并，得到各分片的全局状态信息。
Stage 6. 验证分片和见证分片均对本分片内更新后的状态信息进行共识。共识完成后，各分片进入共识阶段执行交易验证和出块。

四、实验结果

实验设置：本文使用 Golang 语言在实验室自行开发的区块链模拟器（名为 blockEmulator）上实现了 tMPT 协议。这里顺便提一下，blockEmulator 即将开源！敬请关注。我们收集了以太坊 2018 年 7 月 20 日到 2018 年 7月 24 日的 1,500,000 条转账交易作为实验数据来源，实验中将区块大小和出块间隔分别设置为 1000 笔交易和 4 秒，系统包含四个验证分片和一个见证分片，各分片包含 4 个共识节点。原型代码部署在租用的阿里云服务器。

主要实验结果：我们首先测试了不同重组方法所对应的区块链系统的 TPS。如图3所示，我们提出的 tMPT 和 partial tMPT 方法的 TPS 明显优于其他所有方法，且 TPS 分别为 Ethereum full sync 的 3 倍和 3.4 倍。

如图4所示，随着时间的推移，各 baseline 方法的 TPS 呈下降趋势，而 tMPT 和 partial tMPT 方法的 TPS 维持在一个稳定的水平。

图5 和图6 展示了不同方法下的重组时延和数据量大小。结果表明，除了 tMPT 重组方法外，其余方法重组时传输的数据量都随着交易进行而不断增加，与之对应的重组时间也呈不断上涨的趋势。而由于 tMPT 只传输单个 epoch 对应的活跃账户的状态，因此重组时传输的数据量维持在一个相对稳定的水平，重组时延也保持在一个平稳的趋势。当交易执行到最后一个 epoch时，tMPT 的重组时延和传输数据量大小分别为 Ethereum full sync 的 2.8% 和 13%。

五、本文总结

本文提出了一种基于 tMPT 的分片重组方案，旨在保证分片区块链安全性的同时提高分片重组效率。tMPT 状态树可以将重组时节点同步的状态信息进行压缩，并引入见证分片协助完成重组过程以及对非活跃账户交易的验证。此外，我们也对重组过程中系统安全性进行了理论证明。实验结果表明，本文所提出的基于 tMPT 的重组方案在交易吞吐量和重组时延等方面显著优于其他方法。

六、提出的机制应用到工业界的前景分析

分片区块链底层技术仍处于研究探索阶段，还面临诸多问题和挑战需要解决。制约分片区块链技术大规模应用的关键因素在于提高吞吐量的同时还需要确保区块链网络的安全性。本文提出的基于tMPT 的协议为分片区块链技术路线的分片重组环节提供了一个安全高效的实现方案。

参考文献

[1] Luu L, Narayanan V, Zheng C, et al. A secure sharding protocol for open blockchains[C]//Proc.of ACM SIGSAC Conference on Computer and Communications Security (CCS’16). ACM,2016:17-30.

[2] Zamani M, Movahedi M, Raykova M. Rapidchain: Scaling blockchain via full sharding[C]//Proceedings of the 2018 ACM SIGSAC conference on computer and communications security. 2018: 931-948.

[3] Kokoris-Kogias E, Jovanovic P, Gasser L, et al. Omniledger: A secure, scale-out, decentralized ledger via sharding[C]//2018 IEEE Symposium on Security and Privacy (SP). IEEE, 2018: 583-598.

[4] Wang J, Wang H. Monoxide: Scale out blockchains with asynchronous consensus zones[C]// Proc. of 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI’19). 2019:95-112.

[5] Kim J Y, Lee J, Koo Y, et al. Ethanos: efficient bootstrapping for full nodes on account-based blockchain[C]//Proceedings of the Sixteenth European Conference on Computer Systems. 2021: 99-113.

(HuangLab出品，必属精品)

基于“做市商账户”的区块链跨分片协议 —— BrokerChain

彭肖文，黄华威，2022年5月

论文信息：Huawei Huang, Xiaowen Peng, Jianzhou Zhan, Shenyang Zhang, Yue Lin, Zibin Zheng, Song Guo, “BrokerChain: A Cross-Shard Blockchain Protocol for Account/Balance-based State Sharding”, INFOCOM, May 5, 2022.

一、研究背景与动机

区块链是比特币、以太币等加密数字货币的底层基础技术，它综合利用了点对点（P2P）底层网络、分布式数据存储、密码学、分布式一致性共识机制、以及智能合约等计算机技术，构建出一个分布式存储的链式账本 [1][2]。区块链的底层架构为上层应用提供了存储、传输、计算等服务，具有去中心化、难以篡改、协同操作和匿名隐私等典型特征，有着较大的发展和应用前景。区块链主要应用于金融结算、商品溯源、版权保护、数据确权等业务场景 [3]。

然而，区块链底层技术仍处于初期探索阶段，还面临诸多问题和挑战 [4][5]。具体来讲，现有的区块链技术难以解决共识效率问题。例如，比特币的吞吐量为每秒 7 条交易、以太坊的吞吐量也仅为每秒 14 条交易，远低于商用级别所需的吞吐量要求。只有提高了区块链的可扩展性，才能扩大其适用场景，从而赋能数字经济、金融保险、政务等多个领域与行业。

针对区块链的可扩展性，研究人员提出了多种不同的技术方案，如闪电网络[6]、DAG技术[7]、状态通道[8]和分片机制[9]等。其中，分片（Sharding）是一种可提高区块链可扩展性的链上扩容技术。分片机制将完整的账本数据切分为多个互不相交的子账本，再让不同的区块链节点群（也称为分片）管理不同的子账本，多个分片可以并行验证交易，以此线性提升区块链系统的事务处理能力。

但是，区块链分片技术仍面临诸多挑战。如图1所示，基于账户模型的分片机制存在两个问题：第一个问题是跨分片交易比例过高，几乎所有交易均为跨分片交易。过高的跨分片交易率不仅给系统增加了额外的交易负载，而且会造成大量的跨分片通信开销。第二个问题是分片间的交易负载严重失衡，存在冷热不均的现象。我们分别称需要处理过量和少量交易的分片为热分片（Hot Shard）和冷分片（Cold Shard）。热分片由于被持续注入大量的交易，产生了交易拥挤的现象，这会增加交易的确认延迟。而冷分片内只有少量交易可以处理，所产生的区块的交易填充率不高，造成了算力、带宽等资源的浪费。面对如上两个问题，一个难题是如何保证跨分片交易比例较低的同时保证分片间的交易负载均衡。

另一方面，在基于状态分片的区块链系统中，跨分片交易的验证和处理策略是至关重要的。系统需要支持分片间的通信，来保证跨分片交易执行的“原子性”。目前已有的比较高效的跨分片交易方案主要通过如图2所示的消息传递方式进行。首先，交易在源分片上链后，源分片的节点会向目标分片发送一个包含 Merkle Path 证明的中继消息。目标分片的节点接收到中继消息后，通过 Merkle Path 验证对应交易的正确上链情况，再在目标分片将关联交易上链，从而实现对相关区块链状态的更新。因为跨分片验证的存在，跨分片交易的延迟在理论上至少是片内交易时延的两倍。当位于目标分片内的关联交易迟迟无法上链时，跨分片交易的共识延迟有可能无限大。

为了减少跨分片交易比例、实现分片之间的负载均衡、并且保证跨分片交易的原子性，本文旨在提出一种新的跨分片协议来提高分片区块链的吞吐量和降低交易的平均确认延迟。

二、本文贡献

本文提出了一套新的跨分片交易处理协议，通过引入“做市商账户”来减少跨分片交易的数量和加速跨分片交易的上链。而且，通过引入“双Nonce”机制和“部分时间状态锁”机制来防止双花交易，并保证跨分片交易的原子性。
本文还提出了状态划分方案，代替分片区块链原本使用的静态状态划分策略。该分片划分方案根据一定时间内的历史交易信息构建一个账户交易状态图，并对其进行图划分。图划分的目标是平衡各个分片的交易量的同时最小化跨分片交易的数量。通过划分的结果，对每个分片内的账户状态进行动态的调整，从而缓解系统的单分片过热和跨分片交易比例过高的问题。

三、提出的跨分片协议简介

1. 提出协议的概述

本文提出的区块链动态分片协议的整体框架如图3所示。和传统的分片协议一样，所提出的动态分片协议以“时期 (Epoch)”为单位来运行。时期的定义为固定的片内交易共识轮次或者固定长度的时间。我们采用BFT类共识协议作为片内共识协议。在所提出的协议中，根据职能的不同，存在两种不同类型的分片：工作分片（Mining shard, M-shard）和划分分片（Partition shard, P-shard）。它们分别负责处理不同的事务，具体分工描述如下：

工作分片。工作分片中的节点负责接收、验证和转发交易，并将通过片内共识协议，将合法的交易进行打包上链。工作分片所产生的包含交易的区块，称为交易区块（Transaction Block）。
划分分片。划分分片中的节点负责同步工作分片中待确认的交易，并根据收集到的交易，执行给定的账户划分算法，并且维护更新后全局的账本状态。划分分片通过产生状态区块（State Block）来引导工作分片安全可靠地进行账户状态的转移和分片账本状态的更新。

图3展示了本文所提出的跨分片协议的整体框架，包括4个关键步骤，具体描述如下：

工作分片持续接收、验证和转发客户端发送的交易信息，维护一个待上链确认的分片交易池。工作分片内的节点会通过共识协议，进行交易的验证和上链确认，产生相应的交易区块。同时，这些交易区块和待确认的交易池会被同步到划分分片中。
划分分片持续监听所有工作分片中的交易信息，构造账户交易网络并且执行Metis划分算法，对账户进行分片划分。
划分分片根据账户划分的结果，生成最新全局的分片区块链的状态信息。然后，主分片通过共识协议，记录相应的状态信息到区块中，生成相应的状态区块并且对该区块做上链共识。该状态区块会被同步到所有工作分片中。
工作分片根据状态区块中所记录的划分结果来更新自身分片的账本状态。区块链分片系统准备进入下一个时期。

2. 保障跨分片交易处理的有效性

如图4所示，针对跨分片交易延迟高的问题，本文基于状态划分算法拟提出一种新的跨分片协议来缓解跨分片交易处理的效率问题。该协议的基本思路阐述如下：在进行状态划分的过程中，系统会同时招募一些特殊的充当中间人的账户，我们称这些特殊的账户为“做市商账户”。系统允许一部分普通用户通过自愿抵押一定的资产，选择充当做市商账户。做市商账户的状态会被系统分割成两部分或多个部分，分别存储在两个或多个分片中，从而参与到若干个跨分片交易的协调当中。做市商账户的协调机制可以减少基于转账类型的交易的跨分片通信，因此可以减少跨分片交易的延迟，从而提高跨分片交易执行的效率。

图5展示了本文提出的跨分片协议对跨分片交易的执行原理与流程。本文在交易的数据结构中通过引入“部分状态时间锁”，从而实现跨分片交易的原子性执行。假设处于分片1的账户A给处于分片2的账户B发送一笔交易 $\Theta_raw$（如步骤1所示），中间做市商账户 C 会将原交易打包成另一个交易 $\Theta_1$，并广播到分片1（如步骤2所示）。分片1对交易 $\Theta_1$ 执行“A给C转账并锁一定时间”操作并上链（如步骤3所示）。当中间商账户C 在一定时间内观察到交易 $\Theta_1$ 在分片1成功上链后，会向分片2广播交易 $\Theta_2$（如步骤4所示）。最后，步骤5中，分片2对交易 $\Theta_2$ 执行 “C给B转账” 的操作并上链，从而最终实现一笔跨分片交易的执行。如果交易过程中因为某一方作恶或者超时，则执行中断操作：分片2会对 $\Theta_1$ 进行上链，并向分片1发送证明 $\gamma$，从而中断对跨分片交易的执行。

四、实验结果

实验设置：本文使用 python 搭建了一个分片区块链的仿真实验环境，实现了基于Metis图划分的分片调整和“做市商账户”跨分片交易机制。关于数据集，本文使用了以太坊从2015年8月7日至2016年2月13日的1,600,000条真实历史交易。在实验过程中，交易以一定的交易到达率被注入到各个分片中。每个分片的出块时间间隔设置为8秒，每个区块打包交易数量上限为2000条，分片数量为32个。实验测试了不同交易到达率和不同分片数量下的系统吞吐量和平均交易延迟。

主要实验结果：如图6所示，本文提出的分片协议与 Monoxide [13] 采取的分片机制相比，吞吐量最大提升150%，平均交易延迟降低70%；与基于负载均衡优先（Load Balance First，LBF）的动态分片调整协议相比，吞吐量最大提升10%，平均交易延迟降低40%。可见，与 Monoxide [13]提出的“中继交易”协议相比，本文提出的 BrokerChain 协议能够保证跨分片交易在较短的时间内完成，从而降低跨分片交易的交易延迟。

如图7所示，与基于Metis图划分方法相比，本文提出的机制可以将跨分片交易的比例进一步降低10%。

五、提出的机制应用到工业界的前景分析

1. 区块链分片机制的应用前景

如今，区块链技术已经被诸多国家认可，各国加大了对区块链产业发展的布局，并争抢产业的制高点。我国也不断布局推动区块链产业的发展，2021 年我国发布了《指导意见》，进一步明确了区块链的发展目标，推动相关应用落地。近年来，国内头部企业纷纷推出自己的联盟链平台，如国产开源联盟链底层平台 FISCO BCOS [10]、蚂蚁链（AntChain）[11] 和华为云区块链 [12] 等。

联盟链的底层基础设施平台为上层应用提供了分布式存储、高效价值传输、分布式计算等服务，其发展状况已经成为推动区块链业务是否繁荣的关键因素。虽然联盟链技术已经有相关的落地场景，但大多局限于小规模的共识场景。现有的联盟链技术难以解决大规模共识节点和拥有大量交易的场景下的共识问题。只有提高了联盟链的可扩展性，才能更好地支撑其适用的大规模应用场景，从而赋能数字经济、数字政务等领域与行业。

本文提出的机制，针对面向广域网的大规模联盟链基础设施，采用分片技术实现提升区块链的可扩展性能。基于分片机制的联盟区块链是一个充满潜力的研究与应用方向。

2. 区块链跨分片协议的应用前景分析

2021年初国家发布“十四五规划纲要”，指出区块链是赋能数字经济的重要基础设施。目前国内区块链领域是多链共存的现状，因此跨区块链平台实现数据与业务的高效交互十分必要。本文提出的基于做市商账户的跨分片协议，理论上可以扩展为跨链协议，它能为多个链之间提供一种简单、高效的跨链交易的服务。在跨链交易能够执行成功的情况下，可以大大减少跨链通信；在跨链交易执行失败的情况下，通过生成交易的失败证明，并执行资产回滚操作，来维护跨链交易的原子性和数字资产的全局状态一致性。

参考文献

[1] Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[J]. Decentralized Business Review, 2008: 21260

[2] Wood G. Ethereum: A secure decentralised generalised transaction ledger[J]. Ethereum project yellow paper, 2014, 151(2014): 1-32

[3]中国工商银行金融科技研究院. 区块链金融应用发展白皮书[R/OL]. 2020. http://pdf.dfcfw.com/pdf/H3_AP202004261378665796_1.pdf

[4] Zheng Z, Xie S, Dai H N, et al. Blockchain challenges and opportunities: A survey[J]. International Journal of Web and Grid Services, 2018, 14(4):352-375

[5] 韩璇, 袁勇, 王飞跃, 等. 区块链安全问题: 研究现状与展望[J]. 自动化学报, 2019, 45(1):206-225

[6] Poon J, Dryja T. The bitcoin lightning network: Scalable off-chain instant payments[EB/OL].2022. https://www.bitcoinlightning.com/wp-content/uploads/2018/03/lightning-network-paper.pdf

[7] Pervez H, Muneeb M, Irfan M U, et al. A comparative analysis of dag-based blockchain architectures[C]//2018 12th International conference on open source systems and technologies(ICOSST). IEEE, 2018:27-34

[8] Dziembowski S, Faust S, Hostáková K. General state channel networks[C]//Proceedings of the2018 ACM SIGSAC Conference on Computer and Communications Security (CCS’18). ACM,2018:949-966

[9] Luu L, Narayanan V, Zheng C, et al. A secure sharding protocol for open blockchains[C]//Proc.of ACM SIGSAC Conference on Computer and Communications Security (CCS’16). ACM,2016:17-30

[10] Li H, Li C, Li H, et al. An overview on practice of fisco bcos technology and application[J].Information and Communications Technology and Policy, 2020, 46(1):52-60

[11] 蚂蚁链. https://antchain.antgroup.com/docs/11/101801

[12] 华为区块链白皮书2021，建设融合开放的数字经济基础设施 [R/OL]. 2021. https:// res-static.hc-cdn.cn/cloudbu-site/china/zh-cn/BCS/BCS__2.0.pdf

[13] J. Wang and H. Wang, “Monoxide: Scale-out blockchains with asynchronous consensus zones,” in Proc. of 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI’19). Boston, MA: USENIX Association, Feb. 2019, pp. 95–112

区块链论文分享 | Bidl [SOSP’21] | 2022年2月16日

By 彭肖文, 2022年2月16日

论文题目：Bidl: A High-throughput, Low-latency Permissioned Blockchain Framework for Datacenter Networks

这篇论文发表在CCF-A类会议-ACM Symposium on Operating Systems Principles 2021(SOSP 2021)。

1、论文作者简介

Ji Qi (The University of Hong Kong), Xusheng Chen (The University of Hong Kong), Yunpeng Jiang (The University of Hong Kong), Jianyu Jiang (The University of Hong Kong), Tianxiang Shen (The University of Hong Kong), Shixiong Zhao (The University of Hong Kong), Sen Wang (Huawei Technologies Co., Ltd.), Gong Zhang (Huawei Technologies Co., Ltd.), Li Chen (Huawei Technologies Co., Ltd.), Man Ho Au (The University of Hong Kong), Heming Cui (The University of Hong Kong)

本文来自香港的崔鹤鸣团队，崔鹤鸣的导师是哥伦比亚大学的 Junfeng Yang。

2、论文背景

时下热门的通用许可链框架——Hyperledger Fabric (HLF)，使用了 Execute-then-Order的工作流程。如图1所示，每笔交易首先并发执行，然后利用排序保证上链数据的一致性，从而容忍非确定性（non-deterministic）交易^[1]。EO流程存在2点不足：当交易存在大量竞争时，这些冲突的交易会被标记为abort，从而导致HLF的吞吐率受到极大影响，此外排序阶段会导致最终确认的时延增加。

注1：定义 Non-determinism (e.g., caused by data races): given the same state and input, correct nodes may produce different execution results on the same transaction.

另一类工作如Quorum，使用了Order-then-Execute的工作流程：首先用BFT协商次序，然后依次执行事务。OE流程在竞争条件下的吞吐量表现极佳，而且不会出现交易冲突的情况。但是OE流程无法容忍非确定性交易，且交易顺序执行的效率低下。

本文希望能兼得二者的优势：既能高效处理交易，又能允许非确定性交易的存在。本文的观察是：数据中心网络可以为许可链提供高效排序，方法是将部分逻辑下放到路由层中，借助sequencer节点排序。因此，本文基于数据中心网络提出高吞吐，低延时的BIDL(Blockchain-powered In-Datacenter Ledger) 许可链框架。

3、系统模型

BIDL的工作流程如下图2所示。

Phase 1：客户端通过TLS-enabled链接将签名交易提交给共识节点的Leader。
Phase 2：Leader通过运行一个测序线程来充当sequencer。Leader将接收到的交易分配连续的序列号，并将其多播到所有一致和正常节点。为了提高性能，Leader不在多播消息上签名。
Phase 3：共识节点运行BFT类协议对“交易哈希序列的顺序”进行共识。
Phase 4：和Phase 3 并行执行。Normal节点根据序列号顺序，推测性地顺序执行（speculative execution）客户端事务。为了确保存在非确定性交易时系统的状态一致性，系统采用了multi-write协议^[2]，以使Normal节点遵循相同的执行结果。如果节点产生了不一致的执行结果，则中止交易。
Phase 5：
- 情况①：如果Normal节点接收到来自Phase 3的匹配的约定交易，则提交交易。
- 情况②：如果存在攻击者作恶，则Phase 4中推测执行的交易顺序与Phase 3 共识的交易顺序会不同。此时Normal节点会根据共识的交易顺序重新执行，相当于BIDL回退到顺序工作流（sequential workflow）。

4、性能分析

（1）系统的吞吐量：BIDL的Normal节点是顺序执行竞争交易（定义为并发访问同一密钥的交易），可以消除交易依赖性导致的事务中止，并提高系统在竞争工作负载上的吞吐量性能。

（2）系统的交易延迟：论文的共识节点（Phase 3）和Normal节点（Phase 4）的工作是并行执行，与HyperLedger Fabric等框架的顺序工作流程相比，可以极大降低交易延迟。论文指出该协议的延迟通常被BFT共识掩盖（Phase 3）。

5、安全性分析

（1）防止DoS攻击：

Leader不在多播消息上签名，一方面可以减少共识节点和Normal节点的验证签名时间，提高性能。另一方面，还可以防止攻击者伪装成 Leader node, 发送签名无效的资源耗尽型DoS攻击。
如果客户端发送格式错误的交易（例如，带有无效签名），则Leader会断开连接，以避免客户端对Leader发起DoS攻击。

（2） Leader作恶：如果Leader作恶（例如给不同的 Consensus 节点和 Normal 节点发送不一样的交易顺序），则系统可以使用视图切换 (view changes) 来更换leader。本文采用的视图切换不是round-robin轮询方式，而是unpredictable的。系统以the hash of the last committed block 作为随机种子，从共识节点中随机选取一个来替换作恶的Leader。

（3）攻击者 𝓐 伪装leader作恶：攻击者会企图伪装成leader，使用客户端 c 签名的交易来向共识节点和 Normal 节点发送不一致的交易顺序。

本文指出，攻击者必然是自己制造一个恶意客户端 c （或者和恶意的客户端 c 合谋），生成并发送malformed交易，从而制造出交易顺序不一致的冲突情况。因为基于triangle inequality定理可知，共识节点和 Normal 节点会率先接受到来自Leader广播的正确交易，因此攻击者无法利用正确交易发动“交易不一致”攻击。

考虑到在许可链的环境下，攻击者 A 无法制造大量的恶意客户端，所以可以设置一个 denylist 将攻击者拉入黑名单。

6、论文实验

作者基于 HyperLedger Fabric 开发 BIDL 框架，并开源了 BIDL 框架的代码：github.com/hku-systems/bidl。交易大小设置为 1KB，默认区块大小设置为500条交易。如果图3所示，实验对比了 BIDL 和 HLF (HyperLedger Fabric), FastFabric (FF) 和 StreamChain 的性能。实验设置 4 个共识节点（为了配合 FF 的 VFT 环境，没有设置恶意节点）和 50 个 Normal 节点。

与HLF和FF相比，BIDL的延迟降低了60.2%，吞吐量平均提高了3.3倍。
BIDL在有竞争交易环境下的性能最好：当交易竞争率从0%增加到50%时，BIDL的吞吐量（40.1k TXN/s）比FF高出2.2倍，中止率为零，而FF的中止率为37.7%。

7、创新点总结

本文提出了BIDL许可链框架，既能高效的处理交易，又能允许非确定性交易的存在。

BIDL利用数据中心网络，可以引入sequencer节点在路由层中进行高效排序。
现有数据中心网络模型仅针对crash fault tolerance (CFT)，而非BFT。为此，BIDL通过节点共识和视图切换来处理作恶的Leader节点。
BIDL引入Normal节点，通过预测执行（speculative execution）来提高并行性能。
为了避免恶意节点通过广播错误事件发动性能攻击，BIDL引入denylist protocol，将恶意节点添加到黑名单中。

8、个人启发

作者能够从 Execute-then-Order 和 Order-then-Execute 两种工作流程总结出各自的优点和不足，并能结合两种工作流程的优势，提出高吞吐，低延迟的 BIDL 许可链架构。这种思路值得我们学习。

另一方面，即使取消了 Leader 对交易序列号的签名，系统通过引入很简单的 denylist 机制来防止攻击者 𝓐 伪装成 leader 作恶。这里的逻辑有理有据，是一个很大的创新。

9、参考资料

[1]. Yamashita K , Nomura Y , Zhou E , et al. Potential Risks of Hyperledger Fabric Smart Contracts[C]// 2019 IEEE International Workshop on Blockchain Oriented Software Engineering (IWBOSE). IEEE, 2019.

[2]. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, et.al. Dynamo: Amazon’s highly available key-value store. ACM SIGOPS operating systems review, 41(6):205–220, 2007.

[3]. https://zhuanlan.zhihu.com/p/436271693

区块链论文分享 | DispersedLedger [NSDI’22] | 2022年2月12日

By 林岳, 2022年2月12日

论文题目：DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks

这篇论文发表在 NSDI’2022。

论文全文下载

论文作者简介

论文一作是Lei Yang，正在MIT攻读Ph.D；二作是Seo Jin Park，在MIT做博士后；三作是Mohammad Alizadeh副教授，是前两位作者的导师；四作是华盛顿大学的副教授 Sreeram Kannan；五作为斯坦福大学的教授（The Thomas Kailath and Guanghan Xu professor）David Tse。

论文简介

区块链中各个节点网络带宽不同，因此下载（收到）区块的速度差异较大，而传统BFT中，每个节点都要收到了区块才能够进行投票（如下图所示），即带宽大的节点收到pre-prepare（包含整个区块，消息量大）后，广播 prepare（消息量小）。但是此时带宽小的节点可能还没收到完整区块，无法广播prepare消息，而节点需要收集够 2f+1个prepare消息才能够进入到commit阶段。因此小带宽节点会拖慢共识的速度。

为了解决上述问题，本篇论文提出新的思路：先对区块进行共识，共识完成后节点再下载区块。这种做法的好处为：进行共识所需的带宽小，小带宽节点不会拖慢共识过程。共识完成后会进入下一个epoch，进行共识的同时节点可以下载（恢复）之前epoch的区块，这样就不会浪费大带宽节点的带宽。

一个epoch中可以有多个节点提出区块，在vote阶段通过二元共识（Binary Agreement，BA）决定将哪些区块上链。

关键技术剖析

(1) Verifiable Information Dispersal (VID)

VID 就是使用纠删码(erasure code)将信息进行编码分成N份消息（chunk），每个chunk发给对应的一个节点，最终各个节点可用少于N份的chunk解码出整条信息（Retrieval）。在这篇论文中，VID阶段各个节点的操作如下图所示：

(2) Binary Agreement (BA)

由于一个epoch中，可以有多个节点提出区块，要是等到所有dispersal完成，要等待很久（甚至可能等不到，因为有拜占庭节点的存在），并且各个dispersal在不同节点完成的时间或顺序不同，因此需要通过二元共识决定最终上链哪些区块。在VID阶段完成的每一个dispersal都将会进入vote阶段，在这个阶段，节点通过二元共识最终决定这个dispersal对应的块是否上链。这里就不详述二元共识的过程，只说结果：一轮中通过二元共识最终会决定N-f个区块能够上链。

(3) Retrieval

Vote 阶段结束后，各个节点就可以进入下一个epoch了，但是同时节点也要通过Retrieval去恢复之前epoch达成共识的块。也就是说共识与恢复区块是并行的，只不过共识的是以后的区块，恢复的是之前的区块。Retrieval阶段各个节点的操作如下：

(4) Inter-node Linking (IL)

注意到二元共识只会决定N-f个区块能够上链，但是未上链的区块，其dispersal可能在VID阶段已经被大部分节点完成，若在此epoch没有上链，里面的交易就要重新打包成区块在下个epoch被提出，这样做会浪费带宽。因此作者提出IL机制解决这个问题。

每个节点都会维护一个大小为N（节点数量）的数组V，V[i]标识该节点本地完成了的节点i的最大的dispersal。节点在提出块B时，会把数组V也放进区块B中。用下图举例会更容易理解。

图中VID表示节点2在epoch3提出的块在VID阶段已经完成了dispersal，不过没有在vote阶段被决定上链。在当前epoch，节点4提出的块中包含了V=(4,2,3,3)，说明当前节点4已经完成了节点1在epoch4的dispersal，节点2在epoch2的dispersal，节点3在epoch3的dispersal，以及自己在epoch3的dispersal，别的节点同理。在之后的Retrieval阶段，恢复出该epoch的区块后，节点4会比对各个V数组，对于V[i]，取第f+1大的来更新自己的V数组（四个节点时，f=1，所以取第二大的），这样节点4就知道大部分节点都完成了图中VID所对应的dispersal，因此会去恢复图中VID所对应的区块，V数组也变成(4,4,4,3)。取第f+1大的V[i]是为了防止f个拜占庭节点作恶。

创新点总结
1. 作者提议将共识过程与块的下载过程分开，使得各个节点都能充分利用自己的带宽，从而加快共识过程。
2. 通过 IL 机制来保证正确的块都能上链，而无需重新打包出块。

论文的 major contribution
1. 提出的VID协议比别的VID协议通信开销更小。
2. 基于HoneyBadger提出的DispersedLedger，将共识与块的下载分开，使得各个节点都能充分利用自己的带宽，同时一个epoch中能够上链的块也比HoneyBadger多。
3. 实验结果表明DispersedLedger吞吐量比HoneyBadger提高了105%，延迟降低了74%。

自己（林岳同学）的启发
1. 作者是从带宽角度发现传统BFT的不足，这是我之前比较少见到的。无论多熟悉的东西，从不同点角度去看，总会有新的一些发现。
2. 作者将原本被捆绑在一起的过程（下载-共识）巧妙分开并使之能够并行，这也是值得学习的。有些东西看多了就会认为其中的过程和顺序是定死的，还是得多思考，勇于思考，不要被限制住。

[Paper Sharing] OptChain: Optimal Transactions Placement for Scalable Blockchain Sharding

今天分享一篇刚刚读的关于区块链分片理论的论文，题目是 OptChain: Optimal Transactions Placement for Scalable Blockchain Sharding，发表在 IEEE ICDCS 2019，属于分布式并行计算的顶会之一。

这篇论文的出发点是：分片区块链网络中大部分的交易 (trasactions) 都是跨片 (cross-shard) 的，这些 cross-shard trasactions 既降低了系统吞吐量 (throughput)，而且增加了交易的跨片确认时间 (confirmation time)。那么是否可以通过合理地部署这些跨片的交易，使得 cross-shard transactions 的数量降低从而既可以提高系统吞吐量又可以降低跨片确认时延呢？答案是肯定的，详情请细读这篇 OptChain，它提出了一种轻量级的实时的交易放置策略，可以将已经产生关联或者即将产生关联的交易部署到相同的分片中。此外，OptChain 还可以维护分片之间的负载平衡来保障分片机制的并发性。

PS: 如果想了解更多的类似于这篇以提升区块链本身性能为目标的研究论文，请参照综述 “A Survey of State-of-the-Art on Blockchains: Theories, Modelings, and Tools” [ arXiv Page: https://arxiv.org/abs/2007.03520 ].

Category: 高质量区块链论文分享

实验室区块链论文被顶刊 IEEE/ACM ToN 接收

针对 PoW 区块链的自适应双花攻击 (TDSC’23)

tMPT: 区块链分片重组实现方案 (IWQoS’23)

基于“做市商账户”的区块链跨分片协议 —— BrokerChain

区块链论文分享 | Bidl [SOSP’21] | 2022年2月16日

区块链论文分享 | DispersedLedger [NSDI’22] | 2022年2月12日

最新区块链分片系统论文被 INFOCOM 2022 接收

[Paper Sharing] OptChain: Optimal Transactions Placement for Scalable Blockchain Sharding