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 “拖后腿”问题。这是因为不同的区块链分片委员会的异构处理能力导致了不均衡的共识延迟。这种不平衡的延迟给分片区块链系统的“最终委员会”带来了很大的累积等待时延。因此，区块链交易的确认时延会被大大增加，区块链系统的吞吐量会被显著降低。
本文认为一个好的委员会调度策略可以减少在“最终委员会”造成的累积等待时延，从而有利于区块链的系统吞吐量。但我们经过调研发现，目前相关文献尚未提出一个针对这个问题的委员会调度方案。本文首先定义分片区块链中交易吞吐量与累积时延之间的动态权衡问题，然后将这个权衡问题表述为一个效用最大化问题。为了解决这一问题，我们提出了一种在线分布式随机探索算法，英文叫做 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, 1st 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.