Perigee: Efficient Peer-to-Peer Network Design for Blockchains

Perigee：区块链的高效点对点网络设计

作者：The Ohio State University && University ofWashington Seattle

Author：Yifan Mao, Soubhik Deb,Shaileshh, Bojja Venkatakrishnan, Sreeram Kannan, Kannan Srinivasan

论文摘要原文：A key performance metric in blockchains is the latency between when a transaction is broadcast and when it is confirmed (the so-called, confirmation latency). While improvements in consensus techniques can lead to lower confirmation latency, a fundamental lower bound on confirmation latency is the propagation latency of messages through the underlying peer-to-peer (p2p) network (in Bitcoin, the propagation latency is several tens ofseconds). The de facto p2p protocol used by Bitcoin and other blockchains is based on random connectivity: each node connects to a random subset of nodes. The induced p2p network topology can be highly suboptimal since it neglects geographical distance, differences in bandwidth, hash-power and computational abilities across peers. We present Perigee, a decentralized algorithm that automatically learns an efficient p2p topology tuned to the aforementioned network hetero-geneities, purely based on peers’ interactions with their neighbors.Motivated by the literature on the multi-armed bandit problem,Perigee optimally balances the tradeoffbetween retaining connections to knownwell-connected neighbors, and exploring new connections to previously-unseen neighbors. Experimental evaluations show that Perigee reduces the latency to broadcast by 33%. Lastly Perigee is simple, computationally lightweight, adversary-resistant, and compatible with the selfish interests ofpeers, making it an at tractive p2p protocol for blockchains.

论文摘要中文：区块链中的一个关键性能指标是广播交易和确认交易之间的延迟（所谓的确认延迟）。虽然共识技术的改进可以降低确认延迟，但确认延迟的一个基本下限是消息通过底层点对点（p2p）网络的传播延迟（在比特币中，传播延迟为几十秒）。比特币和其他区块链使用的事实上的p2p协议是基于随机连接的：每个节点连接到一个随机的节点子集。诱导的p2p网络拓扑结构可能是高度次优的，因为它忽略了地理距离，带宽，散列功率和计算能力的差异。我们提出了Perigee，这是一种去中心化算法，它纯粹基于对等点与邻居的交互，自动学习针对上述网络异质性的高效p2p拓扑。受多臂强盗问题文献的启发，近地点最佳地平衡了保留与已知连接良好的邻居的连接和探索与以前未见过的邻居的新连接之间的权衡。实验评估表明，近地点减少延迟广播的33%。最后，Perigee简单，计算量小，抗攻击，并且与对等点的自私利益兼容，使其成为区块链上有吸引力的P2P协议。

研究问题、关键问题：本文的研究问题是如何设计一个高效的 P2P 网络拓扑结构，以降低区块链中区块的传播延迟。区块的传播延迟是区块链性能的关键指标之一，它直接影响交易吞吐量、交易确认延迟和安全性能。

具体而言，研究问题包含以下三个方面：

1.随机连接的局限性： 当前区块链（如比特币）使用的随机连接策略导致 P2P 网络拓扑结构高度低效，因为它忽略了节点间的地理距离、带宽差异、算力差异等因素。

2.已有方法的不足： 基于地理位置的连接策略和结构化 P2P 拓扑结构虽然有所改进，但仍然无法完全解决传播延迟问题，并且容易受到攻击。

3.自适应邻居选择： 如何设计一个自适应的邻居选择算法，让节点根据自身与邻居的交互情况动态调整连接，以实现高效的区块传播。

研究动机：

1. 区块传播延迟是性能瓶颈： 尽管共识机制有所改进，但区块传播延迟仍然是区块链性能的关键瓶颈，它直接影响交易吞吐量、确认延迟和安全性能。
2. 随机连接策略的局限性： 当前区块链使用的随机连接策略导致 P2P 网络拓扑结构高度低效，因为它忽略了节点间的地理距离、带宽差异、算力差异等因素，导致区块传播路径迂回，延迟增加。
3. 自适应邻居选择的必要性： 需要设计一个自适应的邻居选择算法，让节点根据自身与邻居的交互情况动态调整连接，以实现高效的区块传播，并适应网络异构性和动态变化。

研究意义：

1. 提升区块链性能： Perigee 可以显著降低区块的传播延迟，从而提高交易吞吐量和确认速度，提升区块链的性能。
2. 增强区块链安全性： 更快的区块传播可以降低分叉的概率，并使双花攻击和区块持有攻击更难实施，增强区块链的安全性。
3. 促进区块链发展： 通过提升性能和安全性，Perigee 可以促进区块链技术的进一步发展，使其能够支持更多应用场景，例如大规模支付系统、智能合约等。

研究内容（算法、方法、技术、模型）：

1. 现有连接策略的不足

随机连接策略的局限性： 指出当前区块链使用的随机连接策略导致 P2P 网络拓扑结构低效，忽略了节点间的差异，导致区块传播延迟过高。

基于地理位置的连接策略： 分析了基于地理位置的连接策略的优缺点，认为其仍然无法完全解决传播延迟问题，并且容易受到攻击。

结构化 P2P 拓扑结构： 分析了结构化 P2P 拓扑结构的优缺点，认为其性能提升有限，并且增加了复杂性。

2.Perigee 算法

Perigee 提出了一个基于多臂老虎机问题的自适应邻居选择算法，节点根据自身接收区块的时间戳来评估邻居的连接质量，并根据评分选择最佳邻居集合。节点在保留连接良好的邻居的同时，也会定期连接随机节点，以发现潜在更好的连接。Perigee 不依赖于节点的任何特定属性，因此具有更好的鲁棒性和适应性，能够适应网络异构性和动态变化。

Vanilla Scoring:

记录每个邻居发送区块的时间，并计算最早到达时间。将所有时间相对于最早到达时间进行归一化。取归一化时间的 90% 分位数作为邻居评分，分数越低越好。

UCB Scoring (Upper Confidence Bound Scoring):

记录每个邻居发送区块的时间，并计算最早到达时间。将所有时间相对于最早到达时间进行归一化。使用 UCB 算法计算每个邻居的传播延迟置信区间。如果所有邻居的置信区间有交集，则保留当前邻居；否则，断开置信区间下限最大的邻居，并连接新的随机邻居。

主要贡献

1. 延迟的基本界限。我们提出了一个理论模型，用于分析块传播延迟在比特币，明确模型异构性的通信延迟之间的同行。我们的模型基于网络系统中的一系列工作，该模型提出可以通过将主机嵌入到度量空间中来准确预测互联网上主机之间的延迟。在这个模型中，我们发现，与对等点之间的点对点延迟相比，对等点之间的互连随机导致传播延迟更严重。相反，我们还表明，对等节点选择具有较小往返时间延迟的邻居的拓扑结构，提供了渐进的最佳可能传播延迟。
2. 最优算法。我们提出了近地点（Perigee），一个分散的邻居选择协议，它完全基于对等体与其邻居之间的交互来自适应地决定连接到哪些邻居。近地点是由经典的多臂强盗问题激发的，在该问题中，一个代理人面临着在许多选项中选择一个选项的决定，这些选项具有先验未知的奖励-自适应地尝试不同的选项并在最佳选择上归零。解决多臂强盗问题的算法的核心原则是平衡探索（尝试以前未探索的选项）和利用（选择以前已经尝试过的选项）。

创新点、创新性：

Perigee 是一种去中心化的算法，通过将 p2p 拓扑设计问题视为多臂老虎机问题，并基于区块到达时间评估邻居连接质量，从而自动学习并形成高效的节点连接拓扑，有效减少区块链网络中区块广播的延迟。

技术难点：

1. 处理节点异构性： 区块链网络中节点的计算能力、带宽和地理位置各不相同，需要有效处理这种异构性，确保每个节点都能连接到最佳邻居集。
2. 算法收敛性和安全性： Perigee 需要在有限时间内收敛到最优拓扑，并防止恶意节点进行攻击，例如日蚀攻击或提供虚假区块信息。

进一步研究思路 (Future Work)：

加强理论分析： 对算法的收敛性、性能和安全性进行更深入的理论分析，以提供更坚实的理论基础。

优化算法设计： 研究更高效的评分方法、邻居选择策略和拓扑结构，以提高算法的性能和鲁棒性。

拓展应用场景： 将 Perigee 算法应用于其他区块链协议和网络场景，以拓展其应用范围。

个人总结：

该篇论文提出了Perigee，这是一种受多臂强盗问题启发的自适应算法，它可以找到有效的p2p拓扑结构来减少区块链网络中的块传播时间。虽然我们已经从经验上说明了近地点的有效性，我们相信我们的工作只是第一步，重要的问题，无论是理论问题和实际解释，需要解决一个更透彻的理解问题。