[INFOCOM'23] Prophet：无冲突的区块链跨分片交易处理
[INFOCOM'23] Prophet：无冲突的区块链跨分片交易处理
《Prophet: Conflict-Free Sharding Blockchain via Byzantine-Tolerant Deterministic Ordering》论文笔记
转载自华东师范大学DaSE实验室微信公众号（id为DaSE Starchain，推荐关注）文章，作者为阙琦峰，仅作学习使用
研究背景
在区块链技术中，扩展性一直是一个重大挑战，尤其是在像比特币和以太坊这样的系统中，其吞吐量分别仅为7 TPS和15-45 TPS，难以满足去中心化应用（dApps）和智能合约日益增长的需求。随着去中心化金融（DeFi）和非同质化代币（NFT）等新兴应用的快速发展，区块链的扩展性问题变得尤为突出。为了提高扩展性，分片技术被提出作为一种有效的解决方案，它通过将区块链网络划分为多个独立的分片，每个分片只处理部分交易和存储，从而实现并行处理，提高吞吐量。分片技术理论上可以使区块链系统处理更多的交易，缓解传统单链系统的负载压力。然而，分片也引入了新的问题，尤其是在处理跨分片交易时。跨分片交易是指涉及多个分片的交易，这种交易需要访问多个分片的状态，由于不同分片之间的状态是独立的，交易的执行顺序和一致性难以保证，导致不同分片之间可能出现数据冲突和执行顺序不一致的情况，这不仅影响了交易的正确性，还可能导致事务回滚（abort），降低系统的整体吞吐量。
研究动机
然而，分片技术的实际应用面临着许多挑战，尤其是在处理跨分片交易时。跨分片交易是指涉及多个分片的交易，在这种交易中，多个分片的状态需要被修改或访问，这样的交易必然引入复杂的协调和冲突问题。当前的分片系统大多依赖于两阶段锁定（2PL） 或 乐观并发控制（OCC） 等机制来解决跨分片交易的冲突问题，但这些机制在实际应用中常常表现不佳，尤其是在处理高度并发和复杂的智能合约交互时。这些系统通常面临 高回滚率 和 低吞吐量，因为它们无法有效解决因竞争条件（race conditions）导致的交易冲突。
因此，PROPHET系统的研究动机在于提出一种新的分片区块链架构，能够通过拜占庭容错的确定性排序来解决跨分片交易的冲突问题，避免交易回滚，显著提高区块链系统的吞吐量和可扩展性。PROPHET不仅解决了现有分片系统中的交易冲突和性能瓶颈问题，还通过创新的设计理念，减少了分片之间的协调和通信开销，从而使区块链系统能够支持大规模去中心化应用的高效运行。
Prophet系统设计
系统总览
图1所示，PROPHET 系统的核心架构旨在解决区块链分片中的跨分片交易冲突问题，并提高系统的吞吐量和可扩展性。该系统通过引入排序分片 和全局交易顺序 来实现这一目标。在PROPHET 中，每个分片独立处理自己的交易和状态，分片之间通过全局交易顺序进行协调。排序分片 负责生成一个确定性全局顺序，确保所有交易按照预定顺序执行，从而避免了交易冲突和回滚。排序分片基于预执行阶段收集的读/写集合数据来构建交易顺序，同时保证跨分片交易的依赖关系得到正确处理。系统通过四个主要阶段——预执行、排序、执行 和验证，有效地减少了跨分片交易的冲突，提升了吞吐量。PROPHET 还通过无状态排序分片和并行化处理，优化了性能，使得系统能够高效地支持大规模去中心化应用
预执行阶段
预执行阶段（Pre-execution Phase）是PROPHET系统中的一个关键环节，主要目的是提前模拟交易的执行过程，收集交易的依赖信息，并为后续的交易排序和执行提供支持。具体来说，预执行阶段通过模拟每个待处理交易的执行，记录交易对区块链状态的读写操作，生成交易的 读/写集合，并识别可能存在的 跨分片依赖关系。当交易涉及多个分片时，预执行阶段能够识别哪些交易之间有依赖，确保跨分片交易能够按照正确的顺序执行，并减少冲突和回滚的发生。同时，预执行阶段还会识别并模拟可能需要交换的 跨分片消息，即一个分片的交易可能依赖于另一个分片的状态，这些消息在后续的执行阶段将被正确传递和处理。通过这种方式，预执行阶段为 排序分片 提供了必须的 读/写集合 和依赖关系信息，使得排序分片能够根据这些数据生成全局交易顺序，确保交易能够无冲突地执行。因此，预执行阶段不仅有助于识别潜在的交易冲突，还为整个系统的高效运行和吞吐量提升奠定了基础。
排序阶段
排序阶段（Sequence Phase）是PROPHET系统中的核心组成部分，负责根据预执行阶段收集到的信息生成全局交易顺序。这个阶段的主要任务是确保所有交易按照一个统一的顺序执行，以避免跨分片交易之间的冲突，并保证系统的一致性和正确性。排序分片（Sequence Shard）在此阶段起着至关重要的作用，它通过从预执行阶段获取的 读/写集合 和 跨分片依赖关系 信息，确定交易的全局顺序，并为后续的交易执行提供清晰的指引。
在排序阶段，排序分片会基于来自预执行阶段的数据，计算并生成一个确定性的全局交易顺序。这一顺序确保了所有的交易都按照正确的依赖关系执行，避免了因为竞争条件或事务冲突而导致的回滚或错误。例如，如果交易A修改了某个合约的状态，而交易B依赖于该状态，那么交易A必须先于交易B执行。排序分片通过对这些交易之间的依赖关系进行分析，保证交易顺序的合理性。排序分片不存储区块链的实际状态或数据，它的任务仅仅是基于预执行阶段的结果生成一个全局的、符合依赖关系的交易执行顺序。通过这种方式，排序阶段为后续的执行阶段提供了一个一致的、没有冲突的交易顺序，确保了跨分片交易在执行时能够按照正确的顺序进行，从而避免了回滚和状态不一致的问题。总之，排序阶段通过确保全局交易顺序的确定性和一致性，解决了跨分片交易的执行顺序问题，为系统的高效运行和吞吐量的提升提供了必要保障。
执行阶段
执行阶段（Execution Phase）是PROPHET系统中的关键环节，负责按照排序阶段生成的全局交易顺序执行交易，并对区块链状态进行更新。在这个阶段，分片根据排序分片提供的全局交易顺序依次处理每笔交易，并执行相应的状态修改操作。执行阶段的目标是确保所有交易都能根据预定的顺序进行处理，并且每个分片只修改与其相关的局部状态，从而避免跨分片的数据冲突和不一致。
在执行阶段，分片根据排序阶段提供的全局交易顺序逐个执行交易。每个分片独立处理自己负责的交易，并更新本地的区块链状态。在执行时，分片需要验证每笔交易的有效性，确保交易所依赖的状态信息是准确的。执行阶段的一个重要任务是与之前的预执行阶段进行一致性对比，确保预执行阶段记录的读/写集合 和实际执行结果一致。如果执行过程中发现与预执行阶段的记录不符，交易将被标记为无效，并且相关的状态更新会被撤销。这种验证机制有助于确保跨分片交易的正确性，防止由于状态更新的不一致导致的错误。
对于涉及多个分片的跨分片交易，执行阶段需要在本地执行完交易后，向其他相关分片发送跨分片消息，获取其他分片的状态更新信息。这一过程通过全局顺序的协调确保了跨分片交易的原子性，避免了数据冲突和不一致。
总之，执行阶段通过确保每个分片根据全局交易顺序执行交易并更新本地状态，确保了系统的一致性和正确性。通过与预执行阶段的对比和与其他分片的协调，执行阶段有效避免了冲突和回滚，提高了系统的吞吐量和可靠性。
验证阶段
校正阶段是PROPHET系统中至关重要的一步，负责确保在执行阶段完成的跨分片交易符合系统的一致性和原子性要求。在执行阶段，每个分片根据排序分片提供的全局交易顺序执行交易，然而，执行过程中可能会出现冲突或依赖问题，导致某些交易无法正确执行。在这种情况下，校正阶段会介入，通过与其他分片的验证信息对比，确保交易结果的一致性。如果某个交易的执行状态与预期不符，或者跨分片交易中的某个分片因状态冲突或依赖错误而未能成功执行，校正阶段将标记该交易为无效，并撤销相关的状态更新。这一过程通过回滚机制确保交易的原子性——即要么所有相关分片的交易都成功，要么都失败，避免了部分成功、部分失败的情况。校正阶段不仅对每笔交易进行检查，还确保跨分片交易在全局状态上的一致性，确保系统最终的全局状态是正确和一致的，避免因并发执行而带来的不一致或数据冲突问题
设计优化
PROPHET 系统提出了多种优化策略，旨在解决分片区块链系统中普遍存在的跨分片交易冲突、高回滚率、低吞吐量和延迟等问题。这些优化策略不仅提升了系统的性能，还增强了其在大规模去中心化应用中的可扩展性和稳定性。下面我将详细展开讨论PROPHET 系统的几项主要优化策略：
并行化排序和执行
在传统的分片区块链中，排序和执行通常是串行进行的，即一个分片在排序和执行交易时需要按顺序等待其他分片的确认或处理。这种串行处理方式容易造成系统吞吐量的瓶颈，特别是在大规模的分片系统中。
PROPHET 通过并行化排序和执行过程来提高系统性能。排序分片生成全局交易顺序后，执行分片可以开始处理自己的本地交易，而不必等待所有分片的同步。这种并行化不仅减少了等待时间，还提高了交易的吞吐量，尤其是在系统负载较高的情况下，能够显著提升性能。
精细化排序
在传统的分片系统中，冲突判定通常是基于合约地址 或合约实例 来进行的，这样会导致很多交易被误判为冲突，即使它们实际上并不相互影响。例如，两个交易可能访问同一个合约，但访问的是该合约的不同字段或变量，它们实际上是可以并行执行的。
PROPHET 引入了精细化排序 的机制，即通过细化交易的读/写集合，不仅依赖合约地址，还基于合约的字段级别（例如，合约中的特定变量）来进行排序。这样，系统可以识别哪些交易是无冲突的，并允许它们并行执行，从而减少了不必要的排序和冲突判定。
异步校正
传统的分片系统在执行交易时，可能会遇到因为慢速分片或跨分片消息延迟导致的整体性能下降。在PROPHET 中，校正阶段 是一个关键的优化点，主要用于在交易执行后检查交易的有效性，并在必要时进行回滚。然而，传统的同步校正方法会导致所有分片必须等待其他分片的确认才能继续，增加了延迟。
PROPHET 通过引入异步校正 机制，显著减少了等待时间。执行分片在执行交易时，并不需要等待其他分片的验证结果。即使某些分片的处理较慢，其他分片也可以继续执行自己的交易，直到所有分片的结果都可用时才进行校正。这种机制让分片能够在处理交易时异步进行，不受其他分片延迟的影响，从而提高了整体吞吐量和系统响应速度。
并行预执行
PROPHET 的并行预执行策略通过并行计算 来加速预执行过程：侦察联盟（Reconnaissance Coalitions）内部的节点可以并行地执行多个交易，每个节点负责不同的交易，减少了串行处理带来的时间消耗。并行预执行还可以通过多个线程同时处理多个交易，即使某些交易涉及跨分片的依赖关系，节点仍然可以在等待跨分片消息时执行其他交易，进一步提升系统吞吐量。这种并行预执行不仅优化了计算资源的利用率，还提高了跨分片交易的处理速度，尤其是在高负载情况下，能够显著提升系统的整体性能。
实验
实验在一个由16台机器组成的集群上进行，每台机器2个CPU和64G内存。此外，PROPHET系统基于Go编程语言实现，底层使用Geth（以太坊的Go实现）来提供区块链的基本功能，包括交易执行、区块生成和状态更新。
图2展示了PROPHET系统与传统分片系统在吞吐量和可扩展性方面的对比。所有三个分片系统都表现出线性可扩展性，但相比于传统分片系统，PROPHET在分片数量较多时展现了显著的性能提升。然而，当分片数量较少时，分片系统的吞吐量甚至低于非分片系统，这主要是因为跨分片交易需要将交易分割为多个子交易并在多个共识轮次中处理，且跨分片交易的竞争导致交易频繁失败，从而浪费了大量吞吐量。PROPHET通过优化跨分片交易的执行和减少失败率，能够在大规模分片环境下显著提高吞吐量和系统性能。
图3展示了随着分片数量的增加，基于OCC的传统分片系统在处理复杂的跨合约调用时，交易中止率显著上升，尤其是当交易涉及多个跨合约调用时，回滚率接近50%。这种现象的原因在于，跨分片交易的竞争和依赖关系导致交易频繁失败，尤其是在多个分片同时试图修改相同数据时，系统无法高效协调和同步，造成大量交易的中止。这限制了需要复杂智能合约交互的去中心化应用。相比之下，PROPHET系统通过全局交易顺序和精细化排序，能够有效避免跨分片交易中的冲突和回滚，无论交易包含多少跨分片合约调用，都能保持0%的回滚率，确保复杂交易的顺利执行，显著提高了系统的稳定性和可扩展性。
图4显示了在非确定性系统中，随着分片数量的增加，延迟也呈上升趋势。这是因为更多的分片引入了更多的跨分片事务，这些事务需要经历更多轮共识才能提交，导致确认延迟增加。相比之下，PROPHET系统的延迟较低且保持相对稳定，因为PROPHET能够在一轮共识内提交任何跨分片事务，避免了多轮共识带来的延迟，提高了系统的响应速度和效率。
图5显示了预执行吞吐量随着每个节点线程数的增加而增加。当PROPHET系统中的分片数量增加时，侦察联盟中的节点数也会相应增加，并且每个节点都分配了一个线程。通过提高并行性，吞吐量得到了提升，这种提升超过了跨分片事务数量的增加。此外，侦察联盟通过5个线程就达到了334 TPS，这表明通过增加线程数，系统的吞吐量能够显著提高。结合图5a中的数据，我们可以得出结论，当侦察联盟节点数量超过10个时，预执行阶段的吞吐量可能会接近或超过PROPHET系统的最大吞吐量（图5中显示为1203 TPS）。因此，瓶颈并不在预执行阶段，而可能出现在其他阶段，如执行阶段或排序阶段。
图6展示了预执行阶段中通信时间占总时间的比例，并评估了如何通过优化通信来提高系统性能。需要注意的是，当通信与计算过程重叠时，图中的通信时间不会被计算在内，这意味着如果计算过程和通信过程同时进行，通信时间的影响会被减小。图中的结果表明，随着每个节点线程数的增加，通信时间在总时间中所占的比例逐渐减小。这表明通过增加并行处理的线程数，PROPHET系统能够更有效地利用计算资源，减少通信延迟的影响，从而提升整体性能.
图7（左）显示了PROPHET系统在不同恶意节点比例下的 无效比率，具体评估了恶意节点占比为1%、5%、12.5%和25%时的影响。尽管恶意节点无法通过校正阶段提交无效交易，但它们仍然能够占用系统的吞吐量，导致有效交易的吞吐量受到一定影响。然而，结果表明，恶意节点对PROPHET吞吐量的影响非常有限，最高不超过2%。
图7（右）进一步展示了随着时间推移，无效比率逐渐降低，这是因为随着诚实节点的逐步建立，恶意节点的影响被削弱。如 第IV-C节 所述，诚实节点倾向于通过组建并留在由其他诚实节点参与的侦察联盟中，而会离开由恶意节点主导的联盟，从而提高了系统的整体吞吐量和稳定性。
总结
PROPHET系统是一种创新的分片区块链设计，旨在解决传统分片系统中的交易冲突问题。通过引入第二层分片架构，PROPHET实现了无冲突交易的执行，这一架构依赖于侦查联盟、排序分片和执行分片之间的合作与监督。为了提高排序效率，该系统还采用了多项优化设计，如 细粒度排序、异步校正和并行执行技术。实验评估结果表明，与现有区块链分片系统相比，PROPHET在延迟上降低了62.9%，几乎没有交易中止，吞吐量提高了3.11倍，达到了1203 TPS。