传统挑战

分片技术

分片与不分片的对比

  1. 分片是显著提高区块链交易吞吐量的最有前途的技术之一
  2. 现有区块链分片协议中跨分片交易的比例逐渐接近100 %。
    • 由于跨分片事务消耗的资源是分片内事务的数倍，因此跨分片事务的处理开销已经占到分片系统总开销的大部分。分片系统的交易吞吐量与其理论上限之间存在非常大的差距。

技术基础

用户状态 User state

通常指的是与用户账户相关的数据，这些数据可以包括用户的余额、交易记录、智能合约的状态变量等

状态单元State Unit

状态单元是区块链系统中最小的存储单元。

每个事务至少涉及一个状态单元的更新、删除、查询等操作

典型的状态单元模型为UTXO模型 UTXO即是指的是区块链的最小花费单位，类似人民币的“分”，每个UTXO是一个独立的状态单元。其事务哈希和输出索引标识每个状态单元。

【在传统区块链中，一个账户只对应一个用户状态（其中包括若干个状态单元）】

系统架构

架构

a) 传统的一些分片方案：

1. 将具有频繁事务的用户相关状态单元迁移到同一分片中。但**此后就固定**了。

b) 河口方案：

1. 对每个结点，相当于造一个“镜像”（二级状态）
2. 主结点能发送消息、接收消息；镜像只能被动接收
3. 分片可以周期性地调整

核心：如何分片？如何构造镜像？

如何构造“镜像”？

【再次理解为什么需要构造“镜像”】

在传统的区块链系统中，每个用户的状态（如账户余额、智能合约状态等）通常存储在一个特定的分片（shard）上。当两个用户之间的交易需要更新存储在不同分片上的状态时，就会发生跨分片交易，这通常涉及额外的通信和共识开销。

架构

多状态模型

每个用户的状态被分割成两部分：

  1. 主状态（Main State）/主账户/主钱包：这是用户的主要状态部分，可以处理用户之间的交易。主状态允许用户在单个分片内完成交易，无需跨分片交互。
  2. 次状态（Secondary State）/次账户/二类银行卡：这是用户的辅助状态部分，只能接收来自其他用户的状态转移，或者将状态迁移到具有相同身份的主状态中。

因为具有花费权限的账户只是存在于主状态中，因此，多状态的镜像并不会造成双花攻击。

状态分割与聚合

  • 状态分割（State Splitting）：当用户的主要状态过于集中，或者需要与多个分片中的用户进行交互时，可以将其主状态分割到多个分片中，以提高交易处理效率。

  • 状态聚合（State Aggregation）：当用户的主状态状态数量不足或状态分布过于分散时，可以将其他分片的状态聚合到一个主分片中，以满足未来的交易需求，并减少跨分片操作。

如何分片？

系统模型

  • 划分为两类
    • $N$个共识分片(C-Shard):：处理不同类别的共识事务
    • 1个State分片(S-Shard):：负责优化分片分布+保持数据一致性【本文创新点】

架构架构架构

分片流程

  • 工作流程
    • 初始化
      • 在每个epoch开始时，共识节点使用可验证随机函数（VRF）生成随机数，并解决基于自身公钥、IP地址和epoch随机数的PoW难题。成功解决后，节点获得当前epoch的有效身份编号（随机得）。
      • 其次，平均等分结点，最后一组作为State分片，其余作为共识分片
      • State分片
        • S-Shard节点会根据上一个epoch中确认的交易来更新用户的状态分布。
          • 状态分布是指用户在不同分片中的状态（如资金、智能合约等）的分布 优化分布。（具体优化分布的算法见下方 COPRAS ）
        • 同时，创建一个包含 最新状态分布D 和 需要重新加载的用户间事务 的State块
      • 所有C-Shard同步当前epoch的状态区块
    • 后续共识
      • 分片共识（Shard Consensus）：C-Shard接收用户交易，并将有效交易添加到交易池。在每个epoch中，C-Shard持续进行共识过程，通过PBFT算法完成同分片共识。
      • 数据收集（Data Collection）：S-Shard节点持续收集由C-Shard确认的区块，并记录确认的交易。在epoch结束时，回滚未完成的跨链交易，并将更新后的用户状态和未完成的交易记录在结束区块中。

COPRAS算法

COPRAS的目标是最小化 分片之间的工作负载不平衡指数$ΔD$，
工作负载包括分片之间的交易（inter-user transaction workload）和分片内部交易（intra-user transaction workload）。

COPRAS算法过程|450

  1. 标记流行用户：根据用户相关交易的数量，将用户分类为流行用户（Popular Users）和普通用户（Common Users）。
  2. 计算工作负载：计算每个C-Shard的初始工作负载。
  3. 迭代计算：在每次迭代中，COPRAS算法遍历用户交易网络中的用户，根据邻居的BC和交易特性计算每个用户的BC，并更新C-Shard的工作负载。流行用户可以将所有BC大于阈值τ的C-Shard作为主分片，而普通用户只能选择最多K个BC大于τ的C-Shard作为主分片。
  4. 算法终止：当连续两次迭代的不平衡工作负载指数（Δ(D)）的差异小于预设值ω，或者迭代次数达到最大迭代次数T时，算法终止。
  5. 返回结果：算法返回更新后的用户状态分布D。

假设一个简化的区块链网络，其中有4个用户（v1, v2, v3, v4）和3个分片（S1, S2, S3）。用户之间的交易如下：

  • v1与v2之间有大量交易。
  • v3与v4之间也有大量交易。
  • v1和v3之间偶尔有交易。
    在COPRAS算法的第一次迭代中，算法可能会根据用户之间的交易量，为v1和v2分配较高的BC到同一个分片（例如S1），而为v3和v4分配较高的BC到另一个分片（例如S2）。在随后的迭代中，算法可能会根据当前的状态分布和工作负载，进一步调整这些BC，以确保状态分布更加优化。

最终，COPRAS算法会找到一个状态分布，使得跨分片交易的数量最小化，同时各分片的工作负载也相对平衡。例如，v1和v2的主要状态可能在S1，而v3和v4的主要状态在S2，这样他们之间的交易就可以在各自的分片内处理，减少了跨分片交易的需求。

用户状态更新机制

分片状态更新机制-结束块

S-Shard节点（作为总管者） 在每个历元的结束和启动阶段

对所有最新C-Shard区块的哈希值进行累积（⊕操作），并将这个操作的结果哈希值记录在结束区块（Ending block）的头部。——这样就拿到并记录了全部分片的全部结点状态。

合并“镜像”，统计交易事务，准备下一轮次分片。

创新点

  1. 多级状态模型：分割状态单元为主状态和次状态（打造镜像）
  2. 状态分割与聚合机制：允许用户根据需求调整其状态分布，减少了跨分片交易的数量，只有在用户所有主状态的状态数量不足时才需要进行跨分片交易。（合并镜像镜像）
  3. COPRAS算法：基于社区重叠检测的用户状态分布优化算法，它通过定义用户的归属系数来优化状态分布，以减少跨分片交易并平衡分片间的工作负载。（灵活分片）

可扩展性大幅度提升

潜在问题

  1. 状态管理复杂性：需要维护多个结点的状态所在的分片。

原文：在这里

【为什么选这篇文章】区块链分片能一定程度上实现事务共识的并行，提升共识效率。但是，传统的分片方案在处理跨分片的共识时仍然耗费较多性能资源。分片系统的交易吞吐量与其理论上限之间存在非常大的差距。

【这篇文章解决了什么】

  1. 高比例跨分片问题：在传统分片方案下，跨分片事务交易越发增大，如何尽可能减少“跨分片”（可以理解为银行跨行转账），使得事务都集中在各自分片
  2. 状态分布不均，缺乏灵活性：现有分片协议中的状态单元（理解为银行账户）只能基于其身份存储在特定分片，缺乏灵活性，不能精确匹配用户间的交易特性。导致所有分片不能被充分利用，系统吞吐量与理论上限有较大差距。” “
    【如何解决的】
  3. 多状态模型：各个状态被分割为主状态和次状态，次状态仅能接收他人发来的事务（类似于仅能接收他人转账），主状态可接收和发起事务。以避免双花攻击。期间可以进行状态合并和状态拆分。
  4. 社区重叠传播算法（COPRAS）：提出了COPRAS算法，通过计算用户归属值（由用户在本分片发起的交易数量、账户状态（可以理解为在本银行的余额）。在某一银行交易越多、存款越多，那么其归属到这个银行分片的概率越大），优化用户状态在不同分片之间的分布，以更好地匹配用户之间的交易特性，并平衡分片的工作负载。
  5. S-shard分片：即一个总管分片，负责对分片进行划分，并保持数据一致性。在每一轮回期末对各个分片状态和哈希值进行累加，上链，保证各个分片状态同步不可篡改”

【实验指标是什么】

  • “吞吐量提升因子：衡量分片系统相比于单个分片的交易处理能力的提高倍数。吞吐量改进因子等于分片系统的事务吞吐量相对单个分片的事务吞吐量的倍数。
  • 跨分片交易比例：表示系统中跨分片交易占总交易数量的比例。本文旨在通过优化状态分布减少这一比例。
  • 交易确认延迟：指用户发送交易到所有相关子交易被确认的时间间隔。
  • 工作负载平衡：评估不同分片之间的工作负载是否均匀分布。”

【思考】
本文创新之处在于采用了多级状态模型，这种模型通过分割状态单元为主要状态和次要状态，为用户打造了一种状态的“镜像”，极大地提高了交易的灵活性和效率。此外，状态分割与聚合机制的引入，使用户能够根据个人需求调整状态分布，有效减少了跨分片交易的发生，除非在所有主状态的状态数量均不足时，否则无需进行跨分片交易。同时，文章借鉴推荐系统中COPRAS算法的运用，通过定义用户的归属系数优化了状态分布，这不仅减少了跨分片交易，还平衡了分片间的工作负载，从而显著提升了系统的可扩展性。然而，这种多状态的管理方式可能会增加状态管理的复杂性，尤其是在维护多个节点状态所在的分片时。

【老师】
COPRAS算法可以进一步改进，因为他的主要是静态的，而非动态自适应的。