论文2：Jenga

论文2：Jenga

2.1 题目、时间、期刊/会议名称、等级，发表单位

• 题目：Jenga: Orchestrating Smart Contracts in Sharding-Based Blockchain for Efficient Processing
• 时间：2022年
• 期刊名称：International Conference on Distributed Computing Systems
• 等级：中科院1区
• 发表单位

2.2 摘要部分

在处理智能合约时，现有的分片方案不能很好地实现系统的可扩展性
原因：每个分片存储并执行一个孤立的、不相交的智能合约子集，这样会导致在合约执行时需要复杂的多轮跨分片共识协议，在状态传输时，需要进行大量的跨分片通信。
基于此，我们提出了一种基于分片的高效处理智能合约的方案。一个智能合约交易中涉及的多个合约可以在一轮内由同一个分片一起执行。而且，不同的分片存储不同的状态（即状态分片），基于状态分片建立多个"正交"执行通道（“orthogonal” execution channels），每个执行通道与所有分片重叠（overlap）。每个节点同时属于一个分片和一个"正交"执行通道，不同的执行通道执行不同的合约。因此，通过重叠节点（overlapped nodes），合约的状态在不需要跨分片通信的情况下，直接在状态分片和执行通道之间进行广播。

2.3 引言部分

• 智能合约

  智能合约是一种自我实施、自我执行的程序，管理着互不信任的当事人之间的互动。智能合约可以被部署到区块链中，每个节点存储智能合约的状态（数据）和执行逻辑（函数）。和区块链交互的节点通过发起一笔智能合约交易来调用已部署的智能合约。区块链中的节点获得交易中涉及的账户和合约状态，执行相关的合约逻辑，并更新相应的状态。

• 智能合约交易和转账交易的区别

  1、智能合约拥有复杂的执行逻辑，执行智能合约需要获取来自账户和合约的多个状态；此外，一笔智能合约交易通常会调用多个不同的智能合约。
  2、常规的转账交易包括两个账户状态，只有双方转账这一步；而智能合约交易通常需要在不同合约之间执行多个执行步骤来执行智能合约所调用的整个复杂逻辑

  3、一笔智能合约交易的处理需要更多的状态

• 支持处理智能合约交易的分片区块链方案

  1、[4],[9],[25]需要在一个特定的分片中，执行所有智能合约。在发起一笔智能合约交易前，账户需要将其状态转移到该特定分片中，处理完成后再将状态转移回去
  2、[2],[7],[22]允许在不同的分片中，处理智能合约，但是一部分解决方案只能处理单中间步骤执行的智能合约交易（比如调用一个智能合约里面的一个函数）
  3、[11],[23]支持处理调用多个智能合约的智能合约交易。但是，这些方案使用复杂的、多轮的跨分片共识协议处理智能合约交易，导致吞吐量和延迟方面的性能下降。
  比如，如果智能合约A部署在分片1，那么只有分片1拥有合约A的状态和逻辑，并且合约A只能在分片1中执行。在处理智能合约交易时，每笔交易被拆分成多笔子交易，按照执行顺序在不同的分片执行相关的子交易，并将子交易的执行结果传输到负责执行下一笔子交易的分片中。在所有子交易执行后，则认为这笔合约交易被成功处理，最后被打包到区块中。

  [4] P. Barrett. Zilliqa technical whitepaper, 2017
  [9] Towards scaling blockchain systems via sharding. In Proceedings of the 2019 international conference on management of data, pages 123–140, 2019.
  [25] H. Team. Harmony: Technical whitepaper, 2018
  [2] Chainspace: A sharded smart contracts platform. arXiv preprint arXiv:1708.03778, 2017
  [7] V. Buterin. Ethereum yanking, 2018. https://ethresear.ch/t/cross-shardcontract-yanking/1450
  [22] Practical smart contract sharding with ownership and commutativity analysis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 1327–1341, 2021
  [11] Highly scalable public blockchain via adaptive state sharding and secure proof of stake, 2019
  [23] Ethereum cross-shard function call, 2020. https://ethresear.ch/t/atomic-cross-shard-function-calls-using-systemevents-live-parameter-checking-contract-locking/7114

• 处理智能合约时，低吞吐量和高延迟的原因

  在不同的分片中，部署不同的智能合约，即一个智能合约的状态，逻辑和执行只被一个分片维护，并且由不同分片维护的智能合约彼此隔离。这样会导致两个性能问题。

  1、处理智能合约交易时，需要复杂的多轮共识协议，降低了智能合约执行效率
  一笔智能合约交易通常会调用多个独立的智能合约，并且这些合约的执行逻辑通常会由不同的分片单独维护；此外，为了提交一笔智能合约交易，相关的分片需要执行多轮合约执行，共识和跨分片中间结果传递
  2、由于分片之间的隔离，处理一笔智能合约交易通常需要获取和返回多个相关状态到不同的分片中。这样做，需要大量的跨分片通信，降低了状态获取和返回的效率。

• 高效处理智能合约需要解决的挑战

  1、如何减少在智能合约执行时多轮跨分片共识协议造成的性能损失
  2、如何减少在状态获取和返回时跨分片通信造成的性能损失
  在解决上述挑战的同时，用有限的存储和计算开销维护每个节点，以获得更好的可扩展性

  解决挑战1的方法：
  需要每个分片维护所有合约的执行逻辑，多个智能合约可以在一个多个分片中执行，而不需要多轮跨分片执行，为了减少每个节点的存储负载，一个合约的状态只被一个分片存储。由于逻辑存储负载不是很大，极大地减少了多轮跨分片共识造成的性能损失

  解决挑战2的方法：
  设计多个合约执行通道与存储隔离状态的分片“正交”（“orthogonally”），这种设计下，任何执行通道可以所有的状态分片重叠。因此，在任何状态分片和执行通道之间传输消息，不在需要额外的跨分片通信。每个节点会同时属于一个某个状态分片和一个正交的执行通道。从多个状态分片中获得的状态可以通过某个重叠的节点子群，直接广播到对应的执行通道。在执行完合约后，通道中的节点通过对应的重叠节点子群，将结果直接返回到相关的状态分片中。该设计消除了状态获取和状态返回过程中的跨分片通信，提高了系统效率。

• 总结

  为了简化智能合约执行过程中的多轮跨分片共识，所有智能合约的逻辑被复制到所有分片中。为了减少每个节点存储负载，不同的分片存储不同的状态。为了消除状态获取和状态返回过程中的跨分片通信，不同"正交"信道中的节点执行契约。

2.4 相关工作

• Pyramid

  允许分片进行合并，以便一部分节点存储多个分片的信息（比如状态和逻辑）,并执行多个分片中的交易。对于一部分智能合约交易，在这些合并了的分片中的节点可以直接验证这些交易。在合并了的分片中处理完这些交易后，需要一轮或多轮共识去提交这些交易。由于节点工作在多个分片中，对节点造成了巨大的存储和计算负载；而且，只有部分分片是合并了的，意味着仍然有部分智能交易需要多轮跨分片共识去处理。

• 智能合约交易处理流程

  

2.5 系统模型

N个节点，S个状态分片，S个执行通道，节点之间通过半同步网络进行连接，每个节点有一个唯一的公私钥对，由PKI给定。公钥代表节点的身份，一旦节点加入，公钥将通过网络广播并记录在一个身份链。

使用账户模型表示账本状态，每个账户/智能合约拥有自己的状态，某个账户/智能合约的状态仅由一个分片进行维护。

2.6 威胁模型

有两种类型的节点：诚实节点和恶意节点
假设拜占庭敌手（Byzantine adversaries）是慢适应的（slowly-adaptive），恶意节点和诚实节点的集合在每个纪元（epoch）都是固定的，只能在纪元之间进行改变。

2.7 系统概述

• 目标

  设计一个高效处理智能合约交易的分片区块链系统，不仅支持单步骤的智能合约交易，也能高效处理更复杂的智能合约交易。从编排智能合约的角度打破分片之间的隔离，简化了智能合约处理过程中的跨分片通信和多轮共识，提高了系统的性能；此外，不会给节点带来过多的存储和计算开销，以确保分片的可扩展性。

• 编排逻辑存储（Orchestrating Logic Storage）

  要求所有的智能合约的执行逻辑被存储到所有分片中，任何一个分片都可以在一轮内，在本地执行交易相关的所有智能合约
  编排逻辑存储的原因：
  1、一个智能合约部署在一个分片中，不同的智能合约部署在不同的分片中。因此，分片不会知道其他分片中智能合约的任何信息。这样会导致一笔智能合约交易需要根据不同分片持有的智能合约信息拆分成多笔子交易。相关分片需要执行所有子交易，进行多轮共识，并在多轮中传递中间结果来提交智能合约交易，效率低下。
  2、如果要求一个分片s1维护所有其他分片的信息，在一定程度上，打破了分片之间的隔离，但是，分片s1维护n个分片的信息，分片s1内的节点的存储和计算负载增加了n倍，降低了分片的可扩展性。
  基于上述原因，我们将智能合约视为一个可分解的实体，将智能合约分解成状态存储，逻辑存储和执行三部分。在智能合约部署时，一个节点存储智能合约的逻辑（函数和代码）和状态（数据）。
  直观感受：
  1、随着时间，每个节点维护的逻辑存储会远小于该节点的总的维护存储。这是因为节点需要记录大量的智能合约交易和频繁的记录状态的变化，而智能合约的逻辑信息只在合约部署的时候需要存储。
  2、如果分片s1拥有一个智能合约的逻辑信息，那么分片s1可以执行这个智能合约。
  为此，我们提出了全网逻辑存储（Network-Wide Logic Storage）

  • 全网逻辑存储（Network-Wide Logic Storage）

    在部署智能合约时，所有分片存储全部智能合约的逻辑，但智能合约的状态信息通过随机的方式，被分片s1存储。在客户端发送一笔智能合约交易时，与智能合约交易有关联的分片锁定这笔交易所需的状态，并将状态传输到分片s1中用于执行智能合约。由于每个分片维护着全部合约的逻辑，在获得来自全部相关的分片的状态后，执行分片可以直接执行这笔合约交易相关的智能合约，并将执行结果（状态更新）返回到相关分片中。最后，相关分片获得执行结果后，将之前锁定的状态解锁，并将这笔合约交易打包进区块中。

• 编排状态存储和执行（Orchestrating State Storage and Execution）

  我们将每个分片的状态存储和执行"正交化"，任何一个状态分片可以通过一个重叠的节点子群和执行通道直接相连接，因此，状态信息可以通过片内广播在状态分片和执行通道之间进行传输，不需要额外的跨分片通信。

  编排状态存储和执行的原因：
  1、一笔智能合约交易通常需要获取位于多个分片的合约状态，在分片s1处理智能合约交易时，要从其他分片中，通过跨分片通信将相关状态st传到分片s1，然后状态st在分片s1中广播，并在分片s1对状态st进行共识。
  一个可能的解决方法：
  我们发现，如果执行智能合约的分片s1与存储智能合约状态的其他分片other，是重叠的，那么其他分片other中的信息可以通过片内广播直接传到执行分片s1中。基于此发现，我们提出了正交晶格结构（Orthogonal Lattice Structure）。

  • 正交晶格结构

    我们正交地架设(erect)了相应数量的执行通道。每个执行通道和全部分片重叠，其中状态分片存储合约的状态，执行通道执行智能合约。在合约部署时，合约的状态信息随机分配给一个分片进行存储。一笔智能合约交易内部所有智能合约的执行由一个执行通道随机处理。节点既属于一个状态分片，又属于与之重叠的执行通道。属于同一个重叠部分的节点构成一个子群（subgroup）。
    在处理一笔智能合约交易时，状态分片中的状态通过部分重叠的子群节点直接广播到一个特定的执行通道中，在执行通道执行完合约后，更新的状态通过子群返回到状态分片中。这种设计消除了状态获取/返回时的跨分片通信，并且不会对节点施加额外的存储和计算开销。

2.8 系统设计

• 全网逻辑存储（Network-Wide Logic Storage）

  创建合约的客户端发起一笔合约部署交易到网络中，才能部署合约，合约部署交易广播到整个网络，每个分片内部通过片内共识来验证合约部署交易，并提交到区块中。每个分片需要存储智能合约的逻辑信息，但只有其中一个分片存储合约的状态信息。

• 正交晶格结构（Orthogonal Lattice Structure）

  每个执行通道与所有的分片都重叠，当部署合约时，智能合约的状态信息被随机分配给分片s1来维护，但分片s1不负责执行这个智能合约；这是因为所有分片都存储着智能合约的逻辑信息，如果分片s2拥有智能合约的状态，则分片s2可以执行这个智能合约。因此，我们把执行智能合约的任务分配给一个与状态分片正交的执行通道。任意两个状态分片和执行通道通过节点子群进行连接，即任意一个节点既属于状态分片st，也属于与状态分片st正交的执行通道，并连接到状态分片st/通道中的节点。通过特定的子群，状态分片和执行通道之间的任何信息都可以通过分片内广播直接传输；而不是首先通过跨分片通信将消息从一个分片传递到另一个分片，然后在该分片中广播。

  存在问题要去解决
  1、如何确定节点属于哪个执行通道?

  2、如何确定智能合约由哪个执行通道来执行？

  • 确定执行通道

    为了确定节点属于哪个执行通道，我们使用了无偏（unbiased）分布式随机数，比如VRF，VDF和可信执行环境来生成分布式随机数，分布式随机数确定了节点所属的状态分片和执行通道。
    具体来说，每个节点i将其公钥与分布式随机数进行异或操作，得到新的随机数$r_i$，$r_i$%N得到另一个随机数$r_i^N$。每个节点通过每个分片内部应该包含的节点数（比如N/S）来除以$r_i^N$,即使用(N/s) / $r_i^N$来表示节点所属分片；用随机数$r_i^N$除以分片数S得到的余数，即使用$r_i^N $ % S表示节点所属的执行通道。这种分配方法实现了状态分片与执行通道正交的结构；同时，确保了分片数和执行通道数相同，以及每个状态分片中节点数与每个执行通道中节点数相同。

  • 确定智能合约由哪个执行通道来执行

    由于每个分片存储着全部合约的逻辑信息，因此，任何执行通道都可以执行任意的智能合约。最后，我们的系统不再使用基于智能合约的哈希值去确定智能合约所属的执行通道；我们使用智能合约交易的哈希值来确定这笔交易中涉及的所有智能合约的执行位置，并且该交易内部的所有智能合约都由相同的执行通道执行。由于交易哈希值的随机性，能更好的平衡每个执行通道的计算负载。

• 跨分片共识协议

  在分片区块链系统，是需要一种跨分片共识协议的，这是因为处理一笔智能合约交易通常会涉及到多个分片。协议消除了智能合约执行期间复杂的多轮共识，以及状态获取或返回期间大量的跨分片通信。我们的跨分片共识协议由预准备阶段、准备阶段和提交阶段共三个阶段。流程图如下

  

• 预准备阶段（pre-prepare）

  状态分片通过共识将一笔智能合约交易涉及的相关状态，并通过子群将相关状态广播到执行通道中。
  跨分片共识从客户端发起一笔智能合约交易开始。在客户端发起交易之前，客户端在本地确定（即决策）智能合约交易中的合约、账户和状态。这个决策可以通过动态程序分析（代码模拟器）来实现，这个动态程序分析与[23]相似。这些信息（指合约、账户和状态）随后被记录在智能合约交易内部。
  [23] Ethereum cross-shard function call, 2020. https://ethresear.ch/t/atomic-cross-shard-function-calls-using-systemevents-live-parameter-checking-contract-locking/7114

  在客户端发送交易时，需要支付一定的交易费来防止恶意行为，然后，将交易发送存储相关状态的分片中。由于存储智能合约状态信息的分片是根据智能合约交易的哈希值来确定的，所以任何一个分片可以很容易地验证自己是否要处理这笔智能合约交易。相关分片通过片内共识验证这笔交易，确定其自身分片相对于该交易所维护的状态。

  • 片内共识

    使用BFT共识作为片内（无论是在状态分片还是执行通道）共识算法，为了提供共识（片内和片间）效率，使用BLS聚合签名。

  • 状态判定（state determination）

    两种判定结果：1、状态是可用的(available) 2、状态是不可用的(not available)
    1、状态是可用的
    状态是可用的。在这种情况下，状态分片达成分片内共识，将可用状态设置为不可用，并使用交易的哈希来决定将状态发送到哪个执行通道。然后，状态及其交易哈希通过与执行通道重叠的状态分片的子群（group）直接在执行通道中广播。

    2、状态是不可用的
    在这种情况下，状态分片达成分片内共识，通过子组向执行通道广播AbortRequest消息和交易哈希。

    由于执行交易的执行通道是根据交易的哈希值确定的，因此，对于一笔交易，在不同状态分片上的所有状态信息将通过不同的子组广播到同一执行通道

• 准备阶段（prepare）

  执行通道执行一笔交易相关的全部智能合约，达成片内共识，并通过不同的子组将执行结果返回到状态分片。
  执行通道接收到与交易相关联的第一个状态判定结果后，执行通道为该交易启动一个计数器c，其中c表示与这笔交易相关联的状态个数，可以通过解析智能合约交易得到。对于成功获得的每个有效状态，计数器减去一。当c=0时，执行通道开始执行这笔交易内的全部智能合约，达成片内共识，并通过不同的子群将执行结果和交易哈希直接返回给相应的状态分片中。如果由于超时或无效的状态，那么执行通道在达成共识后，通过子组将Abort信息和交易哈希直接返回给所有相关的状态分片。

• 提交阶段（commit）

  状态分片通过子群从执行通道得到执行结果，并通过共识进行状态更新，以及提交智能合约交易。每个相关的状态分片从相应的子组获得执行通道上的反馈信息。这些反馈信息是通过子群直接广播到分片中。如果收到有效的状态更新，分片内部通过分片内共识将交易提交给区块，并将区块添加到区块链中。同时，分片会更新存储状态，并将状态恢复为可用状态。如果收到有效的Abort消息，则中止交易。

2.9 安全性分析（待补充）

• 分片失败的概率
• 子组（subgroup）失效概率
• 纪元安全性
• 协议安全性

2.10 实验部分（待补充）

• 实现

• 评价体系（Evaluation Setup）

• 分片大小的选择

  我们应该调整分片大小，以限制系统失效概率为可忽略。选择分片大小的规则：失败概率小于$2^{-17}$约等于$7.6\ast 10^{-6}$[13]。这个失效概率保证了如果分片系统在一天的时间内重新洗牌，那么大约359年就会发生一次失效。表1展示了不同分片数量下分片大小的选择以及对应的失效概率
  

  [13] Pyramid: A layered sharding blockchain system. In IEEE INFOCOM 2021-IEEE Conference on Computer Communications. IEEE, 2021

  结果表明我们对分片尺寸的选择使得在任何规模下发生故障的概率都小于$7.6\ast 10^{-6}$，保证了系统的安全性。

• 吞吐量

  Jenga在12个分片的规模下实现了高达14.3倍于Single Shard的吞吐量，由于Single Shard不具有可伸缩性，因此随着分片数量的增加，Jenga的性能有望超过Single Shard。此外，Jenga最多达到CX Func吞吐量的2.3倍，在12个分片的规模下，达到Pyramid吞吐量的1.5倍。主要是因为Jenga不需要多轮跨分片共识和大量的跨分片通信。

  Jenga性能优于Pyramid有两个原因:

  1、Jenga不需要跨分片通信
  2、Pyramid中，合并后的分片无法覆盖所有的交易，仍有大量的交易需要通过多轮跨分片共识进行处理
  全网逻辑存储的设计贡献了更大的吞吐量增益。这是因为Jenga将智能合约的逻辑部署在全网范围内，在处理交易时将多轮跨分片执行压缩为单步执行。
  

• 确认延迟

  与CX Func和Pyramid相比，Jenga在12个分片的规模上分别减少了高达55.6 %和33.8 %的延迟。
  随着分片数量的增加，确认延迟也随之增加的两个原因：
  1、随着分片数量的增加，每个分片内的节点数也会增加，导致片内共识需要花费更长的时间完成
  2、随着分片数量的增加，交易的处理涉及更多的分片，造成更多的跨分片通信
  在12个分片的规模下，全网逻辑存储设计将交易确认延迟降低了51.5 %，原因如下：
  全网逻辑存储的设计减少了执行过程中多轮跨分片共识造成的延迟
  正交格型结构消除了状态取回过程中的跨分片通信，使得确认延迟降低了15.8 %
  与全网逻辑存储提供了显著的性能增益(无论是吞吐量还是延迟)相比，正交格型结构带来的性能增益并不十分显著。一个可能的原因：为了简化实现，我们使用客户端在基线中进行中继跨分片通信。这种实现方式减少了基线系统中的跨分片通信[ 9 ]，提高了基线性能。然而，它是不够安全的，因为客户端可能是恶意的[ 9 ]，[ 27 ]，[ 29 ]。我们假设，如果基线系统使用更安全的方案（跨分片广播[15]、[17]，通过节点进行路由 [18]、 [25]、[29]）进行跨分片通信，Jenga将获得更多的性能增益
  

  [9] Towards scaling blockchain systems via sharding. In Proceedings of the 2019 international conference on management of data, pages 123–140, 2019
  [27] Monoxide: Scale out blockchains with asynchronous consensus zones. In 16th {USENIX} Symposium on Networked Systems Design and Implementation ({NSDI} 19), pages 95–112, 2019
  [29] Rapidchain: Scaling blockchain via full sharding. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 931–948, 2018
  [15] Omniledger: A secure, scale-out, decentralized ledger via sharding. In 2018 IEEE Symposium on Security and Privacy (SP), pages 583–598. IEEE, 2018
  [17] A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 17–30, 2016
  [18] Kademlia: A peer-to-peer information system based on the xor metric. In International Workshop on Peer-toPeer Systems, pages 53–65. Springer, 2002
  [25] H. Team. Harmony: Technical whitepaper, 2018

• 存储负载

  随着分片数量的增加，Jenga和CX Func的平均单个节点存储开销逐渐减小。原因如下：
  这种好处是由分片的存储可扩展性带来的
  而Pyramid中每个节点的存储开销增加，这是因为随着分片数量的增加，Pyramid需要更多的节点工作在更大的合并分片上。因此，每个节点的平均存储和计算负载也会增加。
  在12分片的规模下，Jenga比Pyramid平均每个节点的存储开销减少了65.2 %，并且随着系统规模的增大，Jenga可以减少更多的存储开销。此外，Jenga中每个节点的平均存储开销仅比CX Func (小于200MB)多一点。这部分存储开销是由于Jenga中每个节点共享所有的合约逻辑。
  1、逻辑存储量占总存储量的比例很小；

  2、逻辑存储的百分比随着时间的推移而减少
  原因如下：合约被频繁地调用(即,记录区块链中的状态变化)，但没有被频繁地部署(即,记录逻辑)。因此，每个节点存储全部逻辑存储的设计是合理的，其节省存储开销的优势会随着时间的推移而增加。

  

2.11 结论（待补充）