理论介绍（增加并行性）

POA共识

  • POA是权益证明算法的一种，验证者用自己的身份（权威性）作为出块的证明
  • 会因为网络同步问题造成链分叉
    • 最长链式共识
      • 当出现分叉：优先选择具有最多的区块的链作为主链
      • 当一个区块后添加了$n/2$个区块，区块完全被确认
        • 因为每个高度只能投一票。添加了$n/2$个区块，后续有一半的节点选择这条链作为有效链，证明对同一链的其他高度不可能达到$n/2$（节点一半的）票，

区块（节点）功能解耦

将各个节点的功能分割开，比如某些节点专用于挖矿，交易区块则连接在挖矿得出的区块之后

这样做

  1. 保证有序性、增加了并行性
  2. 解放部分非矿工结点的性能（否则他们没有事情干，全是主节点在出块、验证）

Bitcoin-NG

解耦为关键块（挖矿所得）和微型块（存储事物）

  • 领导者生产关键块作为确认leader的标志
    • 关键块包含公钥和难题答案
      • 👎劣势：
        1. 领导者在下一任之前被攻击
        2. 私自挖矿
          • 攻击者首先秘密地挖掘一个新的区块，而不将其立即广播到整个网络上。相反，攻击者继续挖掘下一个区块，形成一个私有分支。
          • 私有分支后面公之于众，其他矿工所挖掘的区块将无效，覆盖公开分支上的区块（如图的B）
        3. 双花攻击
          • 双重花费，一个人可能会发送相同的比特币到两个不同的地址，以使两个接收方都认为交易已经完成。
          • 在这种情况下，如果区块链系统没有有效地检测到这种行为，那这个人就可以从两个接收方那里获得比特币，并且他们都认为交易已经完成。
          • 类似于同时从支付宝和微信转出全部剩下的钱

Prism

  • 分割三个功能：交易提议、交易验证、交易确认
  • 根据区块的哈希值设定不同区块的功能
  • 三个区块
    • 交易区块
      • 只能生成或者携带交易
    • 提议区块
      • 区块提议者打包这些交易区块
      • 根据最长链附上去
    • 投票者区块（比Bitcoin-NG新增的，可以防止私自挖矿）
      • 投票给提议区块
      • 指定leader
  • 交易确认区块领导者确认交易
  • 👍各个结点可以并行，不会等待太久

平行链

一条链效率太低
允许矿工同时扩展并行链以提高区块链吞吐量

典型案例：OHIE

  • k 个并行实例组成的 k 平行链结构
  • 创世块相互独立
  • 以每条链的最后一个区块而作为难题的输入，矿工任选一个难题破解
    • 解决方案的随机哈希值决定了生成的区块附加到哪条链上
  • （Rank,NextRank）：嵌入到所有区块的特殊元组
    • RANK：所在链的索引（这个链的第几个区块）
    • nextrank：下一个区块的引用

      NextRank 被用来平衡平行链的长度，以防止它们之间存在巨大的差距。
      如图第0条链破解谜题太慢了，那么2好的nextrank为4，那么和Chain 1的长度就可以保持一致
      通过调整特殊的 Rank 字段，可以实现完全的线性排序

问题：平行链方案中矿工算力并不恒定
解决：其中一条平行链被用作中心链来动态调整挖矿难度。其他链参考中心链调整难度（只高不降）

多领导共识

领导者执行的工作量要远超其他的节点
缓解单领导者的瓶颈，研究人员引入了多领导者 协议。

RBBC：无领导机制

多个提议者将不同的交易集合合并到一个超级区块中

  • 互相通信，每个提议者都可以平等地广播区块并将其提交到区块链上。
  • 但是验证签名不是每一个都验证，由第𝑡 + 1到2𝑡 + 1的验证者验证的
    🙃效率还是比较低吧

Mir-BFT

不同于[[区块链/基于编码的许可链]]的委员会机制，一起商讨一个区块的公式
这个共识机制一次性共同商讨多个区块。

比如：同时收到4个区块，可以由0、1、2、3分别进行一次呢并行的共识，0、1、2、3分别作为这个共识的主节点

  • 具体实现
    • 领导者之间划分请求哈希空间以解决重复攻击的问题
      • 即不同领导者分管不同哈希
        • 轮换 请求哈希空间以解决审查攻击 (恶意节点通过有意篡改或隐藏交易信息)
        • 即分管的哈希不断轮换
        • 批处理
        • 每个领导者独立运行一个PBFT
        • 并行处理事务

多节点并发出块的 PoA：CoPoA

允许节点并发地产生不同类型的区块,以此充分利用每个节点 的资源，从而提高算法性能

传统方案与挑战

传统方案PoA在性能和分区安全上均存在问题

性能

生成区块
每轮仅有一个权威节点会被选中用于生成区块

单个区块包含的事务数量少，不能并发

区块确认
至少n/2轮才能完全确认区块 （因为PoA是最长链共识）

改进：取消了原始 PoA 算法每轮只能产生一个区块的限制，引入事物区块和投票区块

分区安全

网络出现分区时候，不再具备安全性

  • PoA以轮询方式选择leader，可以Ddos攻击leader
  • 两个分区各有一个相同“恶意结点”，可以进行双花攻击

    双重花费，一个人可能会发送相同的比特币到两个不同的地址，以使两个接收方都认为交易已经完成

改进：设计可验证延迟函数的随机信标协议（随机选举领导）+严格的区块确认

算法设计

多链

将单链结构扩展成了多链结构，以期能够承载更多节点产生的区块。

1主干链+n（权威结点）投票链

  • 每条链独立创世区块
  • 主干链由超级区块组成存储最终账本
  • 投票链由投票区块组成，存储投票信息
    • 如果投票区块在其有效负载中包含有对超级区块𝐵的引用链接，则表示其对超级区块𝐵进行了投票

整体流程

  • 提交事务：

    • 防止恶意节点审查攻击 (恶意节点通过有意篡改或隐藏交易信息)，需要向$f+1$个权威结点发送相同事务

      $f+1$刚好比恶意结点多1，以保证至少被一个诚实结点接收

  • 事务区块生成&链接

    • 将这个事务广播给其他权威结点
    • 选举出来的领导结点生成一个超级区块，并广播

  • 投票

    • 权威结点对本轮收到的超级区块投票
    • 投票区块添加到投票链上

  • 统计票数&回复

    • 每个权威节点将会从投票链中为每个超级区块统计票数
    • 权威节点只会在超级 区块被完全确认的情况下才会向客户端做出相应的应答。
      • 如果只是得到了部分确认，那么由权威结点暂存

三类区块

事务区块

同步所有节点之间的待处理事务

为什么需要事物区块？直接发给leader不行吗？

矛盾问题：
一个节点需要在生成一个区块时包含全部它想提交给区块链的事务
区块的大小是受限的，因此一 个区块中只能包含有少量的事务
->因此，不能由客户端直接交给leader来统一生成超级区块，因为事务太多了。需要通过事务区块来缓冲。类似在以患者为中心的细粒度访问控制，通过双区块链安全共享电子病历的一种聚合

💡超级区块链接到事务区块，相当于普通节点（存储事务区块）和主节点（存储超级区块）要重复存储。虽然这样减小了主节点存储压力，但是压力给到了非主节点。不如将区块进行合并同类项，直接存放到超级区块里面，减少存储压力。

利用非领导权威结点的闲置资源，允许他们生成事务区块以同步。
领导结点只需要包含这些事务区块的链接

  • 网络通畅性

    • 每个权威节点每一轮只能生成一次事务区块

  • 流程

    • 广播区块
      • 从事务列表取出一个批次事务
      • 计算merkle树和merkle根
      • 广播区块
      • 将已经处理的事务移除事务列表
    • 接收验证区块
      • 验证本轮是否未接收过发送方的区块
      • 加入事务列表
      • 移除已处理或重复事务

超级区块

由leader生成,使用之前轮收到的事务区块生成一个超级区块

事务区块中可能包含矛盾或者重复
在超级区块中需要剔除矛盾，以防止双花攻击

  • 排序
    • 以领导结点ID作为排序起点
    • 对全部事务区块排序
    • 删除重复和矛盾的
  • 链接
    • 将事务区块的地址和事务区块的Merkle 树根添加到超级区块中
  • 广播
    • 广播超级区块

在正常情况下，所有节点都能接收到之前轮产生的所有事务区块， 这意味着所有节点都将拥有一组相同的事务集合。

Q但是如果领导结点没有完整收到全部事务区块？
A没有关系，下一轮更换领导的时候会由其他领导提出。

  • 权威结点验证超级区块
    • 权威结点检查是否受到全部包含的事务区块
    • 如果缺少，向邻居节点请求获得这个事务区块

投票区块

由权威结点生成，是对超级区块的投票

结点每一轮处理所有未提交的超级区块

  • 验证过程
    • 验证唯一性：只能对同一高度的超级区块投一票
    • 验证是否是主链末尾 （防止私自挖矿）
  • 广播投票区块
  • 接收投票区块
    • 验证签名
    • 验证投票的超级区块是否收到
      • 若未收到，从邻居请求

区块提交

主要目的：解决异步网络问题

阈值

一个超级区块的状态分为：完全确认、部分确认

  • 完全确认底线
    • $V_1>(n+f)/2$
    • 在分区网络中，恶意结点可以克隆自己，所以两个分区一共有$n+f$个结点，那么只要拿到一半多一票，就可以保证完全确认，而不会造成冲突
  • 部分确认
    • $V_2>(n-f)/2$
    • 角度一：
      • 因为同一高度只能一个票
      • 如果两个超级区块$B1$ 、$B2$，其中B1已经完全确认
      • 那么B2最多获得$n-(n+f)/2=(n-f)/2$
      • 那么也就是说如果一个区块，获得了$(n-f)/2$张票，他就非常有可能会在最后被完全确认
      • （如果有一个区块被完全确认了，那么另一个区块就不可能获得(n-f)/2+1张票）
    • 角度二：
      • 比诚实结点一半还多，即诚实结点对此高度的区块没有争议
      • 保证某个高度只有一个超级区块被认为合法

链选择

同步的网络：容易收到足够多票数
异步的网络：无法及时接收到票数 （处于部分确认状态），主干链出现多个分叉

依靠每个超级区块的票数选择主分支

三种情况：

  1. 没有一个分支拥有部分确认的超级区块 -> 选择包含自身投票的
  2. 一个分支拥有部分确认的超级区块 -> 选择包含部分确认的
  3. 两个分支…….. -> 选择投票更多的

（ 最后情况仅存在于两个区块有分歧的时候，这个时候，这两个超级区块最终都不可能达到完全确认）

共9个权威

  • (a)图是区块D的领导结点区块链
  • (b) 区块 E 的领导节点区块链视图；
  • (c) 区块 F 的领导节点 的区块链视图
    𝑟 − 1轮到𝑟 + 4轮的领导节点分别为节点 2、3、9、8、4 和 1。
  1. 2生成的超级区块A被完全确认，A 成为主干链上的最后一个已提交区块
  2. 第r时刻和r+1
    1. 3生成了B
    2. 9生成了C
  3. 第r+2
    1. 结点8发现分叉
    2. 符合情况一（因为两个投票数额都没达到下限）->选择自己投票的分支
    3. 创建D
  4. 在r+3
    1. 结点4观察到C投票超过底线，属于部分确认，属于情况2
    2. C后创建区块E
    3. 此时回复同步，E超过阈值，此后都接续到E

BD怎么办？
BD因为没有收集够足够的票数，会被这个leader暂存，暂存后由这个leader再下一次再提交

C、E怎么办？
看似在r+3的时候，CE因为网络没有收集足够的票数，但是F收集到了足够的票数，那么其祖先CE也会被提交。

随机领导

具备随机性和不可预测性

正常情况

权威结点互换公钥$Pk$,保留私钥$sk$

  • 领导者=（$R_{r-1} \quad mod\quad n$）+1

    这里$R_{r-1}$是上一个信标值，也就说这次的领导者的选取依赖于上一次选取领导所用的信标值
    初始化时，信标值依赖于创世块的哈希值

  • 被选为领导者后，他会负责生成本轮次的随机信标$R_r$

  • 领导者利用$(y_r,\pi_r)=trapdoor_{sk}(x_r,T)$生成一组元组。
    • 注意：这个过程是领导者用私钥$sk$生成的，$x_r$为上一的随机信标值$R_{r-1}$
  • 广播元组$(y_r,\pi_r)$，其他结点可以通过公钥验证$VERIFY_{pk}(x_r,y_r,\pi_r,T)$生成的正确性
  • 用哈希函数$R_r=hash(y_r)$即可得到本轮的信标

攻击情况/宕机情况

有时无法在一轮中输出有效的随机信标值,但是仍然需要信标值

因为VDF（延迟可验证函数）的特性，拥有私钥$sk$的领导者总比只能访问公钥$pk$的其他结点更快生成$y_r$ （利用公钥生成的时间为刚刚输入的$T$）

如果领导者无法生成$y_r$，其他结点也可生成一个唯一的相同的$R_r$，并进行下一领导的选举。

Q为什么需要考虑攻击的情况？如果超时直接进行下一轮选举不可以吗？
A不可以，因为选举的过程严格依赖于$R_r$,如果使用的上一轮的$R_r$那么实际上选出的结点是相同的。

VDF相关论文:点击这里

安全分析

  • 恶意结点控制了领导者
    • 情况1：拿到私钥$sk$，不公布$y_r$
      • 其他结点仍然可以在$T$时间内获取$R_r$，本轮结束后领导权切换，即其不能继续控制
      • 恶意结点可通过这种办法提前获取$R_r$，但无法改变$R_r$，只能提前预知下一个是谁，而不能将下一个指定为其同伙。
    • 情况2：拿到私钥$sk$，公布$y_r$
      • 恶意节点仍然无法改变$R_r$

动态出块节点集合的 PoA ：DyPoA

将系统中所有参与共识的 节点划分为了不同的角色，每个角色的节点通过执行不同的工作来完成的区块上 链的整个过程。

问题提出

PoA 算法去中心化程度低的主要原因在于其将区块生成和验证的过程全部交由权威节点来完成

目标：提高去中心化程度，提高全民参与度。

方案：对区块的生成和验证功能解耦，更多结点参与进来

方案设计

第一阶段（初期）：区块产生数量少+普通结点信誉积分低->权威结点生成超级区块和投票区块

第二阶段（信誉值超过阈值）：具体化为四种角色

角色

  • 权威结点：经过身份证认证，负责区块生成和验证

  • 提议结点：收集客户端的事务，打包为事务区块

    • 候选结点：高贡献值的提议节点

  • 验证结点：生成超级区块和投票区块

    • 由权威结点+候选结点抽签组成

内存池设计

处理事务区块

  • 存在问题
    • 恶意结点无故创建大量无效区块——浪费验证性能
    • 恶意结点只会向部分结点发送事务区块——同步耗费大
    • 通过提议节点的先行验证解决这一部分问题，减少验证节点验证的压力。
  • 方案：基于BFT的
    • 准备阶段广播事务区块
    • 投票阶段对区块验证，如果通过那么返回证书
    • 收集到$2f+1$个证书后，可以认为达成共识。
      • 将这个事务广播给验证结点用于生成超级区块
        （注：这里的验证结点不再验证事务区块的正确性了，只需要验证事务区块是否收到$2f+1$个证书）
        $n-f>f$
  • 如何解决问题的
    • 如果无故创建大量无效区块->规定了每一轮每一个结点只生成一个区块，如果超额生成，投票阶段不再对其投票（避免重复攻击）
      • 如果收到两个相同元数据的事务区块，，那么先来先得。
      • 至多也只会有一个事务 区块拥有足够的可用性证书并发送给验证节点。
    • 如果只向部分结点发送区块->无法收集到足够的证书

💡改进：投票阶段网络通信量过于复杂

引入门限签名，在投票阶段，收到别人的事物区块后，加入自己的签名，然后直接发给主节点
主节点收集到事物区块后，只需验证门限签名是否正确，无需验证区块内容。

  • 门限区块保证只有收到门限个签名才能验证正确。
  • 把网状通信优化为星形通信

选取验证结点

  • 问题
    • 连续连任可能导致被控制
    • 轮询方案可以预测一下节点，恶意节点可以通过预测来采取行动
  • 目的
    • 采用减少连任的方法，防止某个节点连续成为出块节点；
    • 增加随机值
      • 防止节点串通
      • 防止节点预测自己当选时机

数据结构

权重值

当选权重值：

与上一轮的权重和本次是否验证节点挂钩

减少连任：当被选为验证节点后，权重值重新初始化为1

如果一个节点长时间没有被抽签为验证节点，其下一次当选的概率会大大增加

贡献值
静态奖励
  • 初始贡献值
  • 参数超级区块生成均可获得贡献
    • 通过超级区块是否包含节点证书来决定是否得到贡献
    • 提议节点——完成正确的事务提交获得$C_t$
    • 投票的验证节点——正确投票获得$C_v$
    • 生成超级区块的验证节点——$C_s=\frac{n}{1+e^{-(\lambda k+\phi)}}R$
      • n节点数量
      • k超级区块链接的事务区块数量
        • 防止审查攻击（故意忽略某些提议节点生成 的事务区块，如果忽略，贡献值变低）
      • R超级区块只包含一个事务区块时所能够获得的分数（基础分值）
      • $\lambda \phi$控制增长速度

恶意节点会通过阻挠生成各种类型的区块，积分低，得到控制

动态奖励

静态问题：积分一直增加，会导致部分节点由于拥有大量贡献值积分而被多次选为验证节点
主要是验证节点本身的贡献值很高，每次生成又能得到贡献，可以遥遥领先
解决方案：验证节点的得分不能固定，不能太多，根据系统中每个节点拥有的贡献值积分来设置区块奖励

  • 计算拥有积分比例$q_i=\frac{当前积分}{所有节点总积分}$

  • 生成超级区块的验证节点的积分$=min(1,(\frac{阈值}{全部候选节点的贡献总积分总量})^{\delta})*C_s$

    • 全部候选节点的贡献积分总量小于阈值Q，那么只能获得1单位贡献值

    • 超过阈值，说明积分太多了，则获得小于1单位的贡献值

      Q为什么这里分母是候选节点而不是验证节点？不是要减少验证节点的所得吗？
      A因为候选节点最终会变成验证节点，但是如果用验证节点算做分母，很容易达到阈值（因为验证节点都是分高的），且选择候选节点更好的反应全局

    • 小于Q的时候

      • 由$\delta$控制奖励衰减速度
        1. =0：静态
        2. 0<$\delta$<1：缓慢降低（如分式原本为0.16，会变为0.4倍）
          • 因此，为了维持系统的 稳定性，DyPoA 算法将𝛿的值设置为 0 到 1 之间。
        3. $\delta$>1:显著降低（如分式原本为0.4，变为0.16）

抽签过程

  • 每个节点自行计算$(hash,\pi)←VRF(sk,\alpha||role||epoch)$
    • $sk$私钥
    • $\alpha$随机种子（随机数）
      • 由VDF生成
        • $(y_r,\pi_r)=trapdoor_{sk}(x_r,T)$
        • 其中$x_r$为本次的轮数或者信标$R_r$，$y_r$即是随机种子
        • VDF生成的内容其他成员也可验证得到
      • 当且仅当新 的轮次即将开始时，节点才能够接收到 VDF 函数的输出，在此之前均无法获得该 输出值。因此无法预测
    • $role$执行函数的节点的角色
      • 再次增加随机性
    • $epoch$处于的纪元
  • hash值归一化为[0,1]区间数字
    • $d=hash/2^{hashlen}$
  • 构造二项式
    • $C=\sum c_i$即是所有节点的贡献积分总和
    • $p=\tau/C=\frac{选择的节点个数}{系统整个贡献值积分总和}$
    • 二项分布
    • 目标找到$f(j)\leq d < f(j+1)$
      • 遍历$j$(从0到c)
      • 基础概率即为$j$
      • 信誉值越高，那么j越大
  • 最终概率$prob=j×w/W=基础概率*权重比例$

验证过程

收到抽签结果后，使用验证函数$VRF_{VER}(pk,role,\pi,\alpha||role)$验证抽签正确性
重新计算$j$是否正确

等待全部节点验证完毕，前n个最小概率值的节点成为验证节点

安全分析

  • 抵挡女巫攻击（克隆多个相同节点作为验证节点）
    • 即使恶意节点控制了多个提议节点，但它也无法控制每个提 议节点被选择成为验证节点的机会
    • 成为验证节点的消耗很大（需要高信用值）
    • 验证一轮后会因为权重归零重新选举
  • 抵挡双花攻击
    • 只会对同一高度进行一次投票
    • 相同事务不会投票两次

去中心化评价指标

区块生成的随机性

香农熵

$S=-\sum^N_{i=1}x_ilog(x_i)$
xi是第 i 个用户产生的区块数量的百分比

度量矿工开采区块数量分布的随机性和无序程度

  • 这里所有节点都有希望成为验证节点开采，而不是集中在权威节点内

基尼系数

$G={\frac{1}{2N}}\Sigma_{i=1}^{N}\Sigma_{j=1}^{N}\left|x_{i}-x_{j}\right|$

基尼系数可以用来表示各节点之间产生区块数量的不平等

  • 这里所有节点都有希望成为验证节点开采区块，而不是集中在权威节点内

控制网络资源的节点数目

中本聪系数

$K={min}\{n\in\mathbb{N};\sum_{i=1}^{n}x_{i}>\frac{1}{2}\sum_{i=1}^{N}x_{i}\}$

计算控制一半以上的网络资源的最小数量

  • 这里所有节点都有希望成为验证节点开采区块，不存在只有有限个节点控制网络资源

选举制度对比

  • 都认为是动态leader
对比项目 PBFT hotstuff [[区块链/基于编码的许可链]] 本文 备注
选举个数 1 1 N（委员会） N（验证节点）
角色 1领导 1领导 1委员会领导+n委员会成员+非委员会成员 四个角色（事务、验证、权威、候选） 本文角色多样，非权威节点参与度高
领导选举制度 轮询 轮询为主 信誉值 信誉值+权重 本文最安全(避免多次当选)
参与出块的节点 1领导 1领导 1委员会领导 验证节点中的一个
参与投票节点 全部 全部 委员会 验证节点 参与投票越多通信开销大
参与解码节点 点对点，一个请求一个发送 点对点，一个请求一个发送 委员会 点对点，一个请求一个发送 第三个用了分片存储
去中心化程度 低 低 中 高
非委员会节点作用 参与投票 参与投票 无，仅辅助存储 参与事务并发生成 本文的非权威节点参与事物区块生成，主节点无需在出块时取事物，增加并行性
  • 👍论文的并行性、去中心化程度很高
  • 👍对于委员会的选举随机性强、安全性高
  • 👎但是事务区块是否有点浪费和重复？