Alleysira's blog
0%

sharding-blockchain-survey

Posted on Edited on In

Building blocks of sharding blockchain systems: Concepts, approaches,and open problems

继Sharding_Blockchain_Consensus 之后阅读刘老师的综述文章

分片技术是打破区块链去中心化、安全性和可扩展性不可能三角的最流行的方式，分片技术可以广义的理解为将区块链中的节点动态划分为彼此之间没有细粒度同步并且执行存储、计算和通信任务的子集，子集称为分片

现有的分片区块链设计仍有很多可探索的空间，本文从此出发，对现有的分片区块链进行了系统的分析，并将它们的架构概念分解为功能组件，并推导出它们所基于的系统模型和攻击者的假设。推导出的功能组件包括：

  • 节点选择、轮随机数、节点分配、片内共识、跨片交易处理、分片重配置、激励机制

对于每个功能组件，本文描述了接口、功能和性质，给出了组件如何组合成一个分片区块链系统并讨论了每个组件的后续研究方向；同样关注了潜在的安全攻击和性能问题，例如系统吞吐量和延迟

Introduction

传统的区块链系统是一个点对点的分布式自治系统，依赖原子广播协议实现复制状态机

理想的区块链系统努力实现去中心化的控制、对单一状态的共识、防篡改的记录、隐私保护、高可用性

现有的区块链系统在实际应用受限于不可能三角

  • 对于去中心化：区块链需要支持多种假设下的节点（如何加入/离开网络）
  • 对于安全性：需要证明安全，保证区块链协议能够抵抗某一类攻击
  • 对于可扩展性：现有的方案能够分成链下方案和链上方案
    • 链上：采用层次化的架构，核心的区块链系统仅验证少许聚合的资源转移（许多细粒度交易和净效应），概念上类似于一个银行，中央银行就是核心区块链；分片就是一种链上解决方案
      • micropayment
      • payment channel networks
      • virtual payment channels
      • sidechains
    • 链下：避免传统区块链系统的计算开销，避免了所有节点之间就交易顺序达成一致所需的计算成本。

分片希望实现和传统区块链同等的安全性和去中心化，能否实现？

分片技术最初在数据库系统提出，第一个分片区块链工作发表于CCS16的ELASTICO

现有的分片工作主要存在以下问题：

  • 分片区块链系统的结构复杂，包含多个组件
  • 不同的分片区块链采用的模型和假设不同（网络模型、敌手模型、交易模型），不容易理解设计和安全性
  • 现有的分片区块链系统是端到端的描述方式，没有给出整体架构，各组件的功能不够清晰

贡献

  • 将分片区块链拆解为功能组件，给出了每个组件的输入输出、功能和性质；给出了如何讲各组件组合成为完整的分片区块链
  • 对分片区块链系统详尽的分类：从系统模型和功能组件两个方向对分片区块链进行了分类，对于每个组件归类除了解决方案
  • 对组件的深度分析。对每个组件给出基本概念（目的、功能和基本步骤），识别并分析了每个方案在安全、吞吐量、延迟等方面可能存在的问题；给出了未来的研究方向

Preliminaries

Background

讲区块链、区块链共识机制再讲分片区块链

Consensus

介绍区块链的不可篡改性居然加了一句（except for some special redactable blockchains）

区块链的架构

  • 网络层：节点在P2P网络内进行消息同步，节点分布式，不存在中央节点
  • 共识层：具有特定计算和通信能力的节点作为共识节点，通过特定共识算法，承担出块的工作，图中是BFT类共识；共识层决定区块链的一致性和活性
  • 应用层

image-20230806104704355

现有的区块链共识协议可以分为

  • 经典的分布式共识协议：BFT类，采用复制状态机的思想
  • 基于工作量证明机制的共识
  • 基于权益证明的共识
  • 混合共识协议：单一委员会和多委员会共识（分片的一种）

Sharding blockchains

当网络中节点增加时，增加分片数量即可提高处理能力

ELASTICO作为第一篇分片的工作，结合了分片技术提高区块链的交易吞吐率

可以分为三类

  • 通信分片：片内节点大多数时间仅进行片内通信
  • 计算分片：每个分片只负责处理相关的交易，交易的分配是多样化的（根据交易ID进行分片）
  • 存储分片：每个分片的节点仅存储所在分片的数据（交易历史、UTXO），交易历史存在区块链上，UTXO可以为了效率单独存储；实际上减少了节点的存储开销

协调者负责跨片通信和片内共识

image-20230806112006224

分片和其他可扩展性解决方案进行对比，可以分为链上（layer1）和链下（layer2）两类方案

  • 链上方案：分片属于链上方案，还有DAG有向无环图和侧链方案
    • 有向无环图的区块链
      • 采用多条链跟随主链，每个新区块都会链接到若干个之前的区块，可以追溯到创世区块
        • IOTA市值80位，conflux市值69位
      • 参考有向无环图 DAG - 知乎 (zhihu.com)
    • 侧链方案：采用额外的区块链执行交易，可能运行多个共识算法，侧链和主链之间需要一个two-way peg（一般用智能合约实现），用于在主链和侧脸之间资产交换
  • 链下方案：通过channel和主链进行小的交易处理，代表性工作是闪电网络和Perun

Notations

image-20230808091029311

Definitions

image-20230808091411255

  • 网络模型：分片区块链需要考虑全部区块链网络的网络模型和分片内的网络模型，可以不同
    • 同步：保证消息按照轮传播
    • 部分同步：存在时延上限，但是不能作为协议参数
    • 异步：不存在时延上限，但是最终诚实用户的消息能够到达彼此
      • FLP问题指出异步系统中不存在确定性的共识算法能够保证在有限的时间内达成共识
  • 节点准入模型
    • 许可网络：需要完成身份认证才能加入协议
    • 非许可网络：节点可以在任何时间加入网络；没有身份认证机制；节点数量不可预测
  • 敌手模型
    • 腐化模型：包括腐化时机和腐化速度；密码协议更关心腐化问题。腐化速度对分片区块链更重要，决定了重配置阶段（更新委员会）
      • 根据敌手可以发动腐化的时机，可以分为静态和适应性腐化
        • 静态：协议运行前确定腐化对象
        • 适应性腐化：敌手能够根绝运行时的消息适应性动态腐化目标节点
      • 根据腐化速度，可以分为温和腐化和立即腐化
        • 温和孵化：敌手需要$\tau$时间完成腐化
          • 分片区块链中的轮指所有分片成员不变继续运转的时间，轮的时长和敌手完成腐化的时间强相关
          • image-20230808093516205
        • 立即腐化：$\tau=0$
          • 使用较少，Algorand
    • 全局比例模型：敌手能够控制的算力资源或权益资源
      • $[0,1/3)$
      • $[1/3,1/2)$
    • 片内比例模型：片内的节点数量固定，片内敌手控制的节点数量通过$f$等式表达，由片内共识算法决定；一般全局比例会低于片内比例
      • $u=2f+1$：同步的BFT
      • $u=3f+1$：部分同步
  • 交易模型
    • UTXO模型：最常用，每个UTXO包括公钥地址和交易值，每个交易消耗现有的UTXO生成新的UTXO，UTXO的输入和输出值相同
    • 账户模型：每个用户拥有账户，账户地址用于存储余额
    • 其他
  • 片内共识
    • 弱一致性：存在分叉，但是保证最终一致性
      • 链质量 链增长 链公共前缀
    • 强一致性：存在委员会运行分布式共识算法来确认交易和出块
      • 状态机复制：对于服务器集合，包含一个原始数据和若干备份，对线性增长的账本达成一致，需要满足一致性和活性
      • image-20230808100317670
  • 分片区块链
    • 给出账本的定义
    • image-20230808100551688
    • 安全的分片区块链定义：可视为一类特殊的账本，将一致性拆分为片内公共前缀和跨片无冲突；活性分别定义了片内交易确认时延和跨片交易确认时延
    • image-20230808100842569
    • 交易确认时延，设交易提交时间为$t$，交易出现在诚实节点账本的时间为$t’$，则交易确认时延为$t’-t$
    • 应答性：交易的确认时延仅和实际网络实验$\delta$相关，和上界$\Delta$无关

简单对各种组件排列组合就能得到新的分片区块链，作者给了216种（？

Decomposing sharding blockchains into functional components

依次介绍每个组件的基本内容，组合组件的方法，总结现有的分片区块链

Decomposition of sharding blockchains

分片区块链的整体流程如图所示

image-20230808102927605

  • 节点选择：参数$k$表示每个分片内新的节点的数量，$m$是分片个数
    • image-20230808103202920
    • 在无许可环境中，可能会使用PoW或者PoS进行选择；
    • 在许可环境中，由可信第三方来执行
    • 需要满足公平性和鲁棒性，公平性限制恶意敌手的比例，鲁棒性指在恶意敌手不超过某个比例时snodes仍然会被诚实节点接受
  • 轮随机数：一般是交互式的分布式组件
    • image-20230808103822367
    • bias-resistance 抗偏置性 指敌手的参与不会影响结果的随机性
    • 可用性保证随机数能够产生
    • 轮随机数一般用于 将节点随机分配为分片，作为PoW的puzzle
  • 节点分配：将选择出的节点随机分配到$m$个分片中，每个分片$k$个新节点
    • image-20230808104409602
    • 实际上 $anode$ 和下轮参与协议的节点并不一定相同，不同的分片区块链存在不同的替代旧节点的规则
  • 片内共识：
    • 在普通区块链中，proposal是交易，在分片区块链中 $p$ 可以是交易，交易输入或者其他承诺的值
    • image-20230808104851668
    • 可以划分为强共识和弱一致性共识
    • 异步环境下只能实现活性或者一致性，一致性对分片更重要
  • 跨片交易处理：
    • image-20230808105414053
    • 跨片交易占据分片区块链系统的大部分交易
    • 片内交易可以视为特殊的跨片交易
    • 可划分为2个阶段
      • 输入分片生成的证明，证明交易的输入有效并且将证明发送其他相关分片
      • 所有相关分片验证交易是否有效
  • 分片重配置：决定下轮每个分片内的节点
    • image-20230808110515006
    • 需要设计自举阶段，当新节点加入分片时如何下载历史交易数据
    • 安全性要求每个分片是诚实的
  • 激励机制
    • 包括对诚实节点的奖励和对恶意节点的惩罚
    • image-20230808111215363

Composing separate components into sharding blockchain systems

实际的分片区块链系统是上一节提到的组件的组合

image-20230808111557856

  • NS NA ER SR可以视为阶段一，对分片成员列表的确认
  • Isc CSTp可以视为阶段二，负责交易处理

根据片内共识，sharding blockchains could be divided into instant sharding blockchains and eventual sharding blockchains

以下是对现有分片区块链拆解后进行分类的结果

image-20230808112726370

表2对当前的分片区块链系统进行了总结与对比

image-20230808113640210

Node Selection

困难点：

  • 所有节点对选择结果的视图应该一致
  • 需要满足诚实节点的比例足够高
  • 给出安全证明

许可链中由CA完成，主要讨论无许可链中的情况，采用PoW或PoS，需要考虑难度的设计

节点选择过程一般会导致诚实节点的比例降低，为了量化这个降低的程度，给出了诚实部分下降程度的定义

image-20230809181503587

为了防止诚实节点的比例下降太多，给出了公平选择的定义

image-20230809181956036

现有方案

基于PoW的节点选择

两类，依赖底层的区块链或参考委员会reference committee

首先是依赖底层区块链的方法

image-20230809182522545

image-20230809182702543

  • $str$是上一个区块的哈希值
  • $pub_i$包含节点的若干公开信息，用于证明节点的身份，一般包含公钥
  • $D=p\cdot2^\lambda$，有$Pr[H(str,nonce,pk_i)<D]=p$，即$p$是节点发现解的概率

发现解的节点作为新分片的成员，当足够数量的分片成员出现后，进行分片重配置

Omniledger的具体实现是在轮$e$，想要成为$e+1$轮分片成员的节点在identity blockchain上进行挖矿

其次是依赖参考委员会的方法

image-20230809183412616

包含两步

  • 挖矿。节点在当前轮针对特定puzzle进行挖矿，同样是PoW，求解后发送给委员会
    • 和之前的区别是同一轮内所有人求解的难题相同，即不出块；
    • 同一个节点多次计算，不影响安全性，敌手的算力有限？
  • 新节点列表确认。数量足够后进行片内共识，确认后广播list
    • RapidChain利用参考委员会来选择节点，难题是VSS生成的

依赖底层区块链存在的问题：敌手可能进行自私挖矿、固执挖矿、扣快攻击

  • 自私挖矿：敌手出块后不公开，等待私链更长后再公开，浪费诚实节点算力
  • 固执挖矿：类似于自私挖矿，但是挖一个并行的私链，导致分叉
  • 扣块攻击
  • 日蚀攻击
  • 网络分片攻击

这些介绍和节点选择理论上没关系

backbone protocol给出了理论上敌手能够控制的区块比例上界为$t/(n-t)$,t是敌手的算力，n是全网的算力

基于委员会方法的问题：包含两方面，敌手挖矿时的时间优势，新节点列表的确认

  • 时间优势指敌手可以恶意延迟诚实节点发送的消息，敌手可以提前获得挖矿的puzzle，可以恶意延迟诚实节点的解;敌手可能给出多个解，需要解的数量超过某个下界（有详细的文章讨论这个问题
  • 发现了足够多解后，委员会运行片内共识算法进行新节点的确认，BFT类共识片内有leader负责propose新节点的列表，恶意的leader可能censor这个列表
    • 普通节点投票时不检查有效性，导致恶意节点数量过多
    • 如果检查了有效性不予投票，影响活性
    • 可能通过门限投票机制解决

未来的研究方向：

  • 设计更公平的节点选择机制，HFDD尽可能小
  • 分析各种攻击
  • 采用严格的分析方法分析挖矿过程的安全性

基于PoS的节点选择

节点本身的币越多，被选择的概率就越高，需要将系统内的币分成小的单元，每个单元均有参与节点选择的权利；用VRF判断单元是否被选中，同样有两类方法，依赖底层区块链或不依赖

  • 依赖底层区块链：节点同样根据PoS出块，某一时间段内的出块者作为分片成员
  • 不依赖底层区块链：需要先选委员会
    • CCS19这篇工作的选委员会机制为 $H(v’s\ address||H(b)) \bmod k$,其中$v$是节点，$b$是上轮的最后一个区块，$k$是分片数量
    • ？哪里有PoS
    • D.R. Lee, Y. Jang, H. Kim, Poster: A proof-of-stake (PoS) blockchain
      protocol using fair and dynamic sharding management, in: Proceedings
      of the 2019 ACM SIGSAC Conference on Computer and Communications
      Security, CCS 2019, London, UK, November 11-15, 2019, 2019, pp.
      2553–2555.

存在的问题：

  • 无利害攻击：在各个分叉上挖矿，成本较小；增加自己成功的概率：需要惩罚机制
  • grinding attack：攻击者遍历区块链，在不同的分叉上尝试出块，提高自己成为下一个leader的概率，因为有的链e+1轮的出块者是根据前一轮的出块者决定的；可以用无偏的随机性来解决
  • 长程攻击：新节点加入时用虚假的链骗他。PoW的链可以通过比较挖矿难度来判断主链，而PoS可以获得曾经有很高权益的节点的私钥，以较低的成本实现这样的攻击；采用检查点机制可以防御
  • 权益流失攻击：长程攻击成功后敌手可以在新的链上发动双花，交易也会在新的链上记录，导致了诚实链权益损失

未来的研究方向：

  • 实际应用密码工具的通信和计算开销需要考虑

基于CA的节点选择

首先在CA处进行身份认证，CA在节点数量足够或当前轮最后公布节点列表

Epoch randomness

首先给出轮随机数相关的基本概念，再给出现有的生成随机数的方案（VRF、PVSS)，再比较现有的DRB，分析未来的研究方向

Basic Concepts

可以用做puzzle，作为节点随机分配的种子

需要解决的问题：

  • 确定参加轮随机数协议的节点
  • 每轮调用 随机数协议的时间点需要确定
  • 随机数生成协议的时间 系统开销和失败概率需要仔细考虑
  • 生成的随机数的性质需要满足分片区块链的要求

当节点互不信任时，如何公平地产生随机数：密码学工具，如DRB，满足

  • 公开可验证性：任何不直接参与协议的第三方同样能利用公开的信息验证产生的随机数
  • 不可预测性：任何节点不能预测未来的随机值
  • 抗偏置性：节点甚至合谋的节点也不能将随机数影响为对自己有利的
  • 可用性/活性：节点甚至合谋的节点也不影响协议进程

Existing approaches

主要包括VRF、PVSS、门限签名、Hash和VDF

  • VRF：所有节点用私钥作为输入生成随机数，输出的随机数带有零知识证明，节点将VRF的输出和轮随机数结合后签名，最小的作为leader或者委员会成员
    • 目的：本地生成可验证和不可预测随机数
    • Algorand, Ouroboros Praos, and DVRFs

  • 门限签名：签名算法需要门限个参与者才行执行，验证算法任何人都可以执行

    • 在随机数生成中的具体使用：所有参与者提供对共同消息的签名份额，验证收到的签名份额具体并输出随机数
    • 密钥分发
      • 可信的dealer
      • DKG

  • PVSS：分发阶段dealer计算加密的份额，并发送非交互式零知识证明

    • 节点秘密生成一个随机值
    • 广播随机值的承诺和份额
    • 验证后揭露秘密，节点未能揭露则执行秘密分享的恢复算法

  • Hash：PoW

  • VDF：计算必然缓慢，验证高效
  • 同态加密、MACPABE多Authority的

现有DRB方案的比较

image-20230811112615922

通信复杂度指所有节点每轮发送的bit，计算复杂度指每个节点每轮的操作数，验证复杂度指外部验证者每轮的操作数

  • 基于PoW和PoS的方案更适合大规模和动态参与者

  • RandRunner 受网络延迟和网络崩溃的影响非常小

  • Ouroboros , RandShare, Scrape and HydRand 通信复杂度过高，适合小集合参与者

Problems and future directions

  • 安全性：
    • 随机性的三个属性
    • VDF方案的安全性依赖于具体过程的时间复杂度，实际中难以设置参数
  • 性能：参与节点越多，系统一般越安全
    • 完美安全性的协议计算和通信复杂度都非常高，如Ouroboros
    • 基于门限密码的方案需要执行DKG
    • 大多数协议不支持频繁的节点集合更新
  • 形式化的安全性分析
    • 形式化定义：协议的可组合性
    • 精确的假设：大多数方案是同步模型
    • 安全性证明

Node assignment

将新节点随机分配到不同的分片中，否则敌手可能在特定分片内可能获得控制权

  • 需要确保分配过程的随机性
  • 合理设置参数，每个分片内诚实大多数：需要采用特定数学模型来严格分析最终的分布

现有方案

$n,m,u$ 分别是节点总数，分片个数和每个分片内节点数

二项分布

节点分配过程视作随机采样问题，分配前的节点看做无限池，每次从池中取一个节点，该节点诚实和恶意的概率不变（不够合理）

当选择出的委员会为恶意，则称该分布失败

设$Q_0$表示目标的诚实节点比例，$X$表示取的次数，敌手的算力占比为$\rho$，则敌手在分片内占比为$1-Q_0$的概率为

因此失败的概率可以记作

Omniledger采用了二项分布

超几何分布

不再是无限池，每次选择节点后不再放回，节点的诚实和恶意的概率发生变化

失败的概率为

根据其他参数来选择 $\rho$ 使得失败概率足够小，如$10^{-5}$

RapidChain和SGX sharding采用了超几何分布对轮的安全性进行分析

其他分布

实际上二项分布和超几何分布都基于 节点的分配时随机的，然而现有方案可能依赖特定规则

如Polyshard在编码后的分片上进行计算以及分片异构的Pyramid

Problems and future directions

节点选择和节点分配是相互联系的

image-20230811153629981

  • 现有方案忽略了A到B的安全性，事实上B中的敌手比例比A中的更高($>\rho$)，因为
    • 敌手可能在消息发送中占优，即能够更早开始挖矿
    • 如果参考委员会当中的leader是恶意的，可能会进行censor，增加被控制节点的比例
  • 无限池假设不够准确
  • 累计超几何分布的失败率不够精确
    • 仅第一个委员会的概率是正确的，后续的委员会选择受前一个委员会的影响

Intra-shard consensus

片内共识是分片区块链的关键模块，本章首先给出片内共识的基本概念，再划分为立即和最终分片，给出了状态机复制算法，总结了片内共识算法存在的问题

Basic concepts

片内共识算法的目的是高效地处理片内的交易以及和其他分片合作处理跨片交易，需要片内共识算法给出对相关交易输入的可用性证明，证明是签名的形式

除此之外，在某些采用参考委员会的分片区块链中，片内共识算法用于确认新委员的名单，片内共识算法影响具体的效率，需要考虑的问题包括：

  • 片内共识算法的可扩展性：与通信和计算复杂度相关
  • 需要处理分片区块链特有的不同提案
  • 片内的网络环境和整个区块链的网络之间的关系

片内共识算法可以分为两类

  • 强一致性共识算法：每个分片均有委员会，委员会作为出块者，委员会运行BFT类共识，对应立即分片区块链
  • 弱一致性共识算法：分片内采用PoW或者PoS，对应最终分片区块链

现有的方案

Strong consistency

经典的分布式共识算法，实现状态机复制

对节点的假设不同：宕机、拜占庭节点；一般认为拜占庭节点包括宕机，能够容忍拜占庭节点的协议具有更强的适应性和鲁棒性，主要介绍BFT类的共识

同步网络

分布式共识协议

拜占庭将军问题首先提出了法定人数问题，防止恶意的leader模棱两可，即同一轮向不同的诚实节点发送不同的提案

在部分同步网络中，若敌手模型为$u=3f+1$，则法定人数为$2f+1$

设恶意的leader同一轮向不同节点发送了不同的提案$p,p’$，则如果两者投票分别为$x$，$2x-(3f+1)$就是该轮同时对两个提案投票的节点个数，则需要满足$2x-(3f+1)< f+1$，即$x< 2f+1$，因此设置投票法定人数为$2f+1$即可

同步的HotStuff采用了流水线的技术来改善提案效率，采用两阶段的基于领导者的方法来处理交易，交易的确认时延为$2\Delta$

image-20230811164850841

和分片区块链结合

在分片区块链当中，片内和全局的消息传播模型可能不同

Rapidchain采用了实用同步BFT共识协议，敌手模型为$u=2f+1$，利用参考委员会生成的随机数选举leader，片内共识主要包括四轮

  • propose：领导者广播消息和哈希值
  • echo：节点收到消息后广播哈希值，确保每个诚实节点都能收到leader发送的消息
  • pending：如果恶意leader发送了多条消息，诚实节点能够检查到，将冲突消息标记为pending（待定）并广播，恶意leader将会被取代
  • accept：诚实节点收到f+1个有效的echo后认为提案是有效的，广播带有accept的哈希值

Rapidchain允许leader利用pending的区块，即可以提出新的区块时重新提案pending区块的区块头

采用同步网络模型，因此容忍委员会的敌手为$50\%$，牺牲了交易处理的效率

每个节点需要每轮等待$\Delta$时间，导致了交易确认时间和实际的网络时延无关，不满足响应性。在半同步网络和异步网络中无法直接使用$\Delta$

部分同步

部分同步网络是大多数区块链采用的网络模型，首先给出经典方案再和分片区块链结合

分布式共识算法

  • Paxos：本来是为分布式数据库维护设计的算法，支持$u=2f+1$个宕机节点，不支持拜占庭节点，实际上在区块链中的应用很少

    • 主节点向超过50%的备份节点发送prepare消息
    • 备份节点验证消息的合法性，向主节点返回承诺后的消息；
    • 主节点在收到足够多的承诺消息后构造承诺证明，向备份节点发送包括承诺证明的确认消息；
    • 备份节点收到确认消息后验证合法性，向主节点返回确认消息的确认消息

  • PBFT：大多数分片区块链或基于委员会的共识协议均采用PBFT类的共识，非常重要，敌手模型为$u=3f+1$，采用消息验证码进行身份认证；实现了一致性和活性

    • 共识部分具体流程如图所示，复杂度$O(n^3)$image-20230811175214951
    • 在propose阶段，client给所有节点上传提案$p$
    • pre-prepare阶段：主节点给所有节点发送构造的pre-prepare消息$(pre-prepare,H(m),s,v)$，$s$是序列号，$v$是视图，记录主节点的更替，视图转换后值+1
    • prepare阶段：备份节点确认对于当前的$(s,v)$没有冲突的准备消息，然后广播prepare消息$(prepare,H(p),s,v)$
    • commit阶段：收到$2f+1$个有效的prepare消息后，备份节点认为$p$是已经准备好了，广播commit消息$(commit,H(p),s,v)$
    • reply阶段：收到$2f+1$个有效的commit消息后，备份节点认为$p$已经被承诺了，将承诺后的提案和签名发送给client

    PBFT包括以上的共识部分和视图转换部分，当主节点不能及时处理数据时，备份节点发起视图转换，换主后新的主节点开始工作，采用round robin的方式进行更换，检查点机制用于协助视图转换，所有commited的提案中最大的序列号被认为是稳定的checkpoint

    • 视图转换复杂度为$O(n^4)$，视图转换的具体协议如下所示：
      • view-change message broadcast阶段，节点$i$广播视图转换消息$vc_i:(view-change,v+1,S^,C,U,i)$，其中$S^$​代表当前稳定的检查点的序列号，$C$是$S^$的$2f+1$个commit投票，$U$包含节点$i$当前视图下, 序列号大于$S^$, 且已经形成prepared的消息集合
      • view-change acknowledgment阶段，备份节点验证vc消息并且构造对应的ack消息$vca_i:(view-change-ack,v+1,i,j,H(vc_j))$，直接发送给新视图的主节点（轮转决定）
      • new-view broadcast阶段，对每个视图转换消息$vc_j$，当主节点收到$2f-1$个ack后，$vc_j$就认为有效放入集合S中，新的主节点构造新视图消息$nv:(new-view,v+1,S,U^)$，其中$U^$包括当前稳定的检查点和检查点之后的序列号最小的pre-prepare消息，节点根据nv更新自己本地的状态，进入视图v+1

  • Hotstuff是对PBFT的改进，同样是部分同步网络，$u=3f+1$，特点包括：

    • 采用流水线处理提案，每轮的消息包括前一轮的法定证明和当前轮的新天
    • 采用BLS签名聚合$2f+1$个投票为1个签名，降低了通信复杂度
    • 每轮负责收集投票和发送提案的主节点都要更换
    • image-20230811182751759
    • 观察到第4轮没有填仍然进行，考虑到活性
    • 现有其他的BFT类共识，scalable Byzantine fault tolerance，Pala
和分片区块链结合

Paxos和分片区块链结合的工作很少，现在的工作都基于PBFT类共识

  • ELASTICO直接使用PBFT，无法处理跨片交易，效率较低
  • Omniledger基于Byzcoin设计了Omnicon
    • Byzcoin将MAC替换为数字签名，利用了树型的通信结构和CoSi协议，结合了CoSi和PBFT
    • 指出CoSi容易受到错误，通信树的深度太大了，进行了改进
  • ZILLIQA利用EC-Schnorr multi-signature protocol提高了PBFT的效率
  • Chainspace采用MOD-SMART的PBFT作为片内共识

异步网络

共识算法

FLP不可能定义给出了在异步网络下不存在确定性共识算法能够解决一致性问题

HoneyBadger BFT是异步下BFT共识的代表，敌手模型为$u=3f+1$

异步BFT依赖于可靠广播RBC和异步二进制协议ABA

  • 交易收集阶段，u个参与节点同时收集交易
  • 交易门限加密阶段对收集到的交易进行B/U加密
  • RBC广播阶段，每个节点依赖于RBC广播并收集信息，RBC包括echo和ready两轮
  • ABA共识阶段，leader负责收集所有加密的值并且初始化ABA算法
  • 交易门限解密阶段，如果加密的交易集有效，每个节点运行门限解密算法

其他异步网络下的分布式共识协议还有：MinBFT、Dumbo-MVBA、BEAT等

目前没有分片区块链采用异步共识作为片内共识算法，可能是跨片交易依赖于共识协议在每个分片内的活性，当分片区块链处理跨分片交易时，多个分片需要合作并在一定时间内响应，然而异步网络下的共识机制牺牲了活性来保证安全性

weak consistency

最终分片区块链一般使用 PoW PoS或者其他弱一致性方法在每个分片内生成区块，不存在委员会

  • Monoxide提出了楚弩挖矿来实现PoW的片内共识算法，能够防御1%攻击，矿工需要在多个链上进行挖矿，m个不同链上的区块的区块头形成merkle树，树根和nonce作为hash的输入，然而矿工需要收集并验证m个区块链上所有的信息，实际上并没有实现可扩展性

  • Parallel Chains将VRF和PoS结合起来在每个分片内生成区块

问题和未来的研究方向

分别从立即分片区块链和最终分片区块链的角度进行总结

立即分片区块链

  • 降低分片成员间的通信复杂度：片内分布式共识算法一般依赖多轮投票来达成一致，在投票阶段如果每个成员均发送签名、收集和验证签名，通信量很大；而且每个分片内为了保证安全性，分片成员个数需要达到安全门限
  • 恶意委员检测和恢复机制：多个分片运行分布式共识算法，可能会有特定的委员会被敌手掌握，如何检测通过其他诚实分片检测恶意分片的委员会并且设计特定的机制来取代恶意委员会是未来的研究方向
  • 片内和跨片的高效的视图转换机制：降低分片成员的通信复杂度，如何降低leader的负担、公平合理地选择新的leader；处理跨片交易时可能不同分片委员会之间的视图不一致，如何处理（leader诚实执行片内工作，丢弃跨片交易）
  • 和分片区块链更好的结合：片内共识算法还需要处理跨片交易，需要多个分片运行多轮片内共识；输入可能多样化，不只是交易

最终分片区块链

  • 1%攻击问题。以PoW为例，敌手可以集中他的算力在某个分片上进行挖矿，安全性要求是敌手不能超过该分片51%的算力。假设存在m个分片，则敌手成功的所需要的算力降低为51%/m，当m足够大时，51%/m近似等于1%。因此在最终分片区块链上如何解决1%攻击非常重要
  • 复杂的跨片交易处理。分片内产生的区块不能被立即确认，区块需要达到一定深度时才能保证稳定，因此跨片交易处理在最终分片区块链中更加复杂。

Cross-shard transaction processing

基本概念

分片区块链中交易是跨片交易的概率非常高，概率随分片数量增加而增加

Rapidchain当分片为16时，跨片交易的占比为99.8%，处理跨片交易的机制对分片区块链的性能影响很大

跨片交易处理过程中需要解决2个问题

  • 跨片通信和处理机制的设计，一个交易的输入可能被多个分片控制，多个分片需要协作判断交易的有效性
  • 防止双花攻击的机制。防止交易输入被双花

现有方案

  • 立即分片区块链：2阶段承诺和交易拆分

  • 最终分片区块链：中继交易解决方案

两阶段承诺(2PC) 方案

大多数跨片交易处理方案基于2PC进行设计，包括准备阶段和承诺阶段

存在一个协调者负责收集输入的可用性证明并在相关分片内进行发送

  • 在准备阶段，协调者收集证据来证明交易的输入的可用性，证据一般是片内节点运行BFT共识输出的，一般是多个签名或单个聚合签名的形式，同时该输入应该被锁定
  • 承诺阶段，协调者将所有输入的可用证明发送给所有相关的分片，包括输入分片和输出分片，如果所有输入有效，交易就被认为是有效的，在相关分片内进行了承诺，输入会被花费，输出将会被创建

根据协调者的角色，可以将2PC方案分为客户端驱动的2PC和分片驱动的2PC

  • 客户端驱动的2PC：客户端负责在准备阶段收集证明并在承诺阶段发送给相关分片
    • image-20230812170637555
    • Omniledger采用了客户端驱动的2PC方案，每个分片内由leader签名是否accept
  • 分片驱动的2PC：1个或2个分片承担协调者的作用。准备阶段输入分配生成输入的可用性证明，承诺阶段一个有效的交易会在所有输入和输出分片中被接受。和客户端驱动的2PC相比，客户端的压力被减轻了，只需要提交交易等待回复
    • image-20230812171601751
    • 图a中所有的输入分片都是协调者，图b中一个输入分片负责进行协调，两类的通信复杂度相同
    • Chainspace RSTB Fleetchain采用了分片驱动的跨片交易处理机制

交易拆分方案

RapidChain提出的，将多输入多输出的跨片交易拆分为多个单输入单输出的交易

如图所示，由输出分片的委员会对交易进行拆分，如果两个输入委员会分别对$tx_1,tx_2$通过，则输出委员会会正确执行$tx_3$

image-20230812172946353

Instachain采用了交易拆分方案，如果一个交易输入有效，另一个交易输入无效，则有效输入对应的子交易会直接发送给输出分片（？

交易中继方案

一般在最终分片区块链中使用，，每个委员会内不运行BFT，交易或可用性证明不会立即确认，无法采用2PC方法。

核心思想：保证在每个输入分片内输入相关的交易未得到足够确认前，输出分片不会把交易作为有效交易

基本步骤

  • 输入分片的矿工收集跨片交易$tx$，验证账户的余额是否大于交易额，如果满足则认为合法
  • 矿工发现PoW的解后，构造包含$tx$的区块，其他矿工验证区块，生成对应的中继交易$\psi$，发送给输出分片的矿工
  • 输出分片的矿工收到中继交易后验证合法性，如果中继交易$\psi$已经达到了对应安全的深度$\lambda$，确定交易成功

Monoxide采用了中继交易的形式

问题和未来的研究方向

给出3类方案对应的问题

2PC

  • 客户端驱动的方案（使用不广泛）
    • leader恶意：准备阶段leader可能给出错误的证明或无法回复，如果恶意的leader对不合法的输入进行保证，其他分片可能会通过
    • 如果客户端在commit阶段未能发送对应的证明，可能导致交易被永远锁定
      • 客户端恶意或者离线
    • 客户端负担加重：客户端需要记录分片的状态和参与节点的IP地址，为了和leader通信
  • 分片驱动的
    • 运行多次BFT，设计流水线处理的片内共识处理机制
    • 可能的攻击：
      • 重放攻击，利用之前交易的可用性证明伪造出新的交易的可用性证明，添加标识符即可防御；
      • 交易泛洪攻击：敌手可能伪造大量由特定分片进行处理的交易，破坏活性；将交易分配给不同分片进行防御
    • 恶意的协调者：特定输入或输出分片的领导者作恶，延迟可用性证明得到处理等行为

拆分交易

没有给出具体的实现细节，需要进一步研究

  • 产生$c_{out}$分片公钥的方法不明确，一般决定输入分片的方法是利用公钥的哈希值来确定输入分片，然而在交易拆分阶段，需要生成多个公钥地址，具体的方式没有给出
  • 新生成的输出可能被非法地花费：其中一个有效一个无效；或者输出分片的leader知道新交易的私钥
  • 处理多输出交易的方法没有给出，比较复杂
  • 交易数量增加，增加计算和存储开销

中继交易

  • 交易确认延迟比较长：每个输出分片先确认，输出分片再确认
  • 处理多输入消息比较困难：基于账户模型比较少，UTXO比较多，open problem
  • 一旦出现分叉，链的安全性受到影响

Shard reconfiguration

Basic concepts

为什么需要重配置：敌手可能发动腐化攻击控制节点，影响共识安全性

关键问题：

  • 确保每个人分片内的诚实节点数量超过门限
  • 重配置阶段系统能够正常处理交易
  • 腐化攻击不会成功

基本步骤：

  • 在轮$e$，轮$e+1$的节点已经经过节点选择机制确认了
  • 轮$e$末尾，节点替换已经达成一致
  • 分片的新成员和旧成员协商，获得对应的账户、交易数据
  • 旧成员不再工作，新节点开始处理交易，进入轮$e+1$

目前的重配置仅部分委员会节点会被替换，原因是时间成本太高（历史交易数据

Existing approaches

  • 随机分配：每个旧节点被替换的概率相同，利用$PRG(H(c||\xi_e))$决定置换

  • 特定规则

    • 时间顺序：类似于滑动窗口，取代时间最长的节点
    • 有界布谷鸟：根据节点每轮处理的交易数量进行排序
      • image-20230812185632818

Problems and future directions

  • 对腐化参数的定量分析：$\tau$ 表示敌手完成腐化需要的时间，PoW需要满足$\tau >2T_e$,目前的文献缺少对这个参数的分析

  • 新加入节点的自举：下载历史数据的过程，潜在的问题

    • 敌手可能提供假数据，如何验证正确性
    • 性能：需要时间很长

  • 对新委员的安全性分析：对于随机替换方案，现有的分析假设了替换所有委员会节点；时间序列替换存在 敌手可能针对性攻击新加入节点的问题，导致安全性降低；对于有界布谷鸟规则，没有给出如何踢出I中的节点，实际上每个分片内节点处理的交易数量差不多

  • 初始化阶段：如何安全的初始化创世区块，目前假设是可信第三方，可以考虑MPC

Motivaition mechanism

基本概念

需要激励机制的原因

  • 节点越多，链越安全
  • 节点消耗了计算资源和带宽，需要补偿或激励

难点是奖励公平，作恶受到惩罚

一般假设节点是理性的，为了获得最大化的收益

包括incentive和penalty，研究很少

现有方案

  • 对出块者和leader的奖励：可能是一个节点获得奖励；也可能是运行BFT的委员会所有成员，再进行公平的分配
    • Lever Manshaei等人的工作基于博弈论进行了分析
  • 对负面行为的惩罚：需要先缴纳保证金
    • 捣乱sabotage：不投票、leader不出块、块内包含无效的交易
    • 恶意行为：leader发两个冲突的提案，委员会成员投多次
  • 基于声誉的奖励：idea来自P2P系统，基于历史的行为打分，包括响应时间、处理的交易、节点相关的恶意行为数量，声誉越高的节点获得的奖励越多

问题和未来研究方向

  • 结合分片区块链：
    • 片内共识算法决定了需要更公平的奖励，所有人都想当leader，可能发起恶意的视图转换协议，敌手可能发起攻击，导致当前leader渎职然后换主，Hotstuff这种固定换主的共识协议更容易进行激励机制的设计
    • 跨片交易处理的协调者如何奖励
  • 详细的分析，目前没有过对分片区块链激励机制的理论研究，需要经济学的基础

Related Work

  • 分片共识综述

    • [AFT19] 73分类比较抽象，组件分析不够明确
    • [IEEE Access]216对每个方案进行了介绍，没有宏观的分类和分析
    • [arxiv19]116提供了更形式化的分析以及评价指标
    • [FC21] 72分析了跨片通信
    • [AFT22] 217主要分析了分片区块链的节点分配协议

  • 区块链共识

  • 可扩展性

Conclusion

本文将分片区块链解构为若干组件，分析了每个组件的基本概念，现有的解决方案和存在的问题以及未来的研究方向。简化了分片区块链的设计，每个组件可以单独改善，给出的未来研究方向具有一定意义