PoK信誉证明：一种新的共识联盟链机制

PoK信誉证明：一种新的共识联盟链机制

摘要

在基于区块链的系统中，参与者可能是恶意的。因此，这项⼯作⾸先描述了系统中预期的⼏个属性，其中相关⽅的诚实⾏为对成功起着重要作⽤。考虑到这些特性，基于节点的信誉（动作）提出了⼀种新的共识机制，即信誉证明（PoK）。 PoK 结合了基于信誉得分的⾃稳定领导⼈选举算法，以确保系统的⼀致性。在 PoK 中，新节点和现有节点都有公平的机会通过成为领导者并向区块链添加有效区块来赚取利润。

PoK 给予激励并施加惩罚以⿎励和阻⽌节点的诚实和恶意⾏为。 PoK 是根据 CAP 定理分析的。这项⼯作提供了安全分析，以证明 PoK 对各种区块链特定攻击和信誉特定攻击的抵抗⼒。

引言

1. 区块链确保透明度和数据完整性，减少欺诈和数据篡改，并促进业务审计，通过消除中间人和数据守门人，可以快速的追踪产品和交易。
2. 区块链
   1. 点对点分布式账本
   2. 每个块包含前一个块的不可逆哈希（通过哈希指针连接）
   3. 每个网络节点维护一个账本副本
3. 区块链共识步骤
   1. 根据某些标准或规则选择一个节点作为领导者或矿工
   2. 领导者或者矿工验证交易，合法交易打包在区块中并发布到网络
   3. 其他节点验证该区块
   4. 流行的共识机制
      1. 工作证明（PoW）
      2. 堆栈证明（PoS）
      3. 实用拜占庭容错（PBFT）
      4. 权威证明（PoA）
4. 概率共识机制
   1. PoW和PoS，不保证系统的完全一致性
      1. 提供一定概率的最终一致性
   2. 选择领导者时
      1. 只考虑瞬时计算能力或参与者的股份数量
      2. 没有考虑到参与者的恶意行为
   3. 恶意矿工可能会引入很多问题
      1. 不一致、延迟问题
      2. 包括除了交易吞吐量低、能耗高、一致性弱、可扩展性低这些和PoW相关的其他重要问题
   4. 概率共识机制通常用于公共和无需许可的区块链
      1. 这引起了公共和无许可区块链中的治理、隐私和可扩展等几个问题
      2. 使得有上述问题的区块链不适合构建联盟业务模型这样的系统
5. 拜占庭容错的共识机制(BFT)
   1. 未经当局许可任何人不得进入系统
   2. 大多数BFT的共识机制用循环方式选择领导者（矿工）
      1. 无论过去行为如何
      2. 都会有平等的机会成为领导者
      3. 不激励领导者
6. 基于行为的共识机制
   1. 根据节点的行为选择节点作为领导者或矿工
   2. 当节点在系统中表现出预期行为，就认为是诚实的
   3. 最常用的诚实行为的方法是通过信任和声誉
      1. 大多基于信誉的共识机制建立在概率共识机制上
      2. 选择缺乏公平性
         1. 先选出一批声誉最高的参与者作为共识组的一部分
         2. 然后从组中选择一个作为矿工
         3. 限制了新参与者成为矿工的机会，导致不公平竞争
            1. 削弱了去中心化特性
7. 我们提出的共识机制
   1. 各方的诚实行为对于取得成功至关重要
   2. 引入了基于行动的共识机制（信誉证明）
   3. 信誉
      1. 好的或坏的行为决定个人未来生存模式的普遍因果法则
   4. 给予每个节点成为领导者的公平机会
      1. 降低其信誉惩罚恶意节点
      2. 增加诚实节点的信誉分数
   5. 引入了部分块和完整块的概念
      1. 维护一致和正确的区块链状态，跟踪有效交易
   6. 创新
      1. 描述了此类系统中共识机制中预期的十个属性
      2. PoK结合了基于信誉得分的自稳定领导人选举算法，确保系统的一致性
      3. 实现了共识的最终性、去中心化和公平性，优于现有工作

理想属性

代表参与者诚实行为的最常用方法之一是通过区块链中的信任和声誉管理模型

在我们的工作中，声誉似乎不是代表系统中参与者的行动、行为的恰当术语

他们正在参与实现共同目标而不是出于自生利益,因此我们创造了一个新词“信誉值”

这个值决定他们在联盟区块链中的存在和角色。

1. 信誉分数必须反应参与者的行为
   1. 共识机制应该计算联盟中每个节点的信誉值，它必须反映节点的行为
   2. 由于多方对业务的成功负责，因此应考虑参与者的意见来计算分数
   3. 高分数应当表明诚实的行为和获得奖励的更好机会
2. 信誉分数必须反映过去和现在的动作/行为
   1. 应该随着节点的行为对分数做出相应的修改
3. 信誉分数变化的速度必须是敏感的
   1. 参与节点的信誉应该对其行为敏感
   2. 敏感度代表分数的变化
   3. 如果参与节点不诚实行事，分数会呈指数下降
4. 必须惩罚恶意行为
   1. 必须通过强制执行一些惩罚来强烈组织节点的恶意行为
      1. 降低分数
      2. 金钱惩罚
5. 诚实行为必须得到奖励
   1. 鼓励参与者提高他们的信誉分数
   2. 奖励包括
      1. 信誉分数增加
      2. 货币奖励
6. 默认信誉分数不得优先/惩罚新参与者
   1. 给新参与者一个默认的分数
7. 系统应该区分参与者的寿命
   1. 参与节点可能会呈系统中移除自己
   2. 在执行不良行为之后以新身份重新进入系统
   3. 不允许隐瞒过去的不良行为
8. 系统应确保去中心化
   1. 是区块链技术的重要预期特性之一
      1. 这就是为什么共识机制应该设计为以去中心化的方式控制系统
      2. 这意味着共识机制有助于维护系统的去中心化属性
9. 领导者选举算法应该是公平的
   1. 系统公平性
      1. 系统的权利和责任应该分布在所有实体之间，使得没有一个实体可以控制整个系统并且民主运行
   2. 算法公平性
      1. 节点都诚实的完成自己的工作，并且每个节点有相同的概率被选为领导者
      2. 否则成为领导者的可能性取决于信誉
10. 领导者选举算法应该是自稳定的
    1. 保证在有限的时间内只选举一个节点作为领导者
    2. 有利于提高系统一致性，提高系统效率

系统模型

1. 由n个节点组成
   $P_i$
   代表的是第i个节点
   $i{d}_i$
   代表第i个节点的id

交易

1. 我们给出以下交易模型
   $T{X}_i^{App}=<a_i,t{a}_i,d{s}_i(a_i,t{a}_i)>$
   1. 都是与第i个a相关的信息
   2. 是应用程序的时间戳
      $t{a}_i$
   3. 是数字签名
      $d{s}_i$
   4. 交易费用将与每个应用程序交易相关联。领导者赚取与应用程序交易相关的交易费用，作为将其纳入有效区块的奖励
2. 量化交易的行动
   1. 领导人
      1. 验证应用程序事务
      2. 通过包括合法事务创建部分块
      3. 网络中发布部分块
   2. 其他节点
      1. 创建验证事务，验证部分块
      2. 创建评级事务，对节点评级
   3. 交易格式
      1. 格式如下
         $T{X}_i^{Val}=<v_i,i{d}_i,d{s}_i(v_i,p_i)>$
      2. 验证位
         $v_i$
      3. 节点执行的评级事务如下
         $T{X}_i^{Rate}=<r_{i0},r_{i1},...,r_{i(n-1)},i{d}_i,d{s}_i(r_{i0},r_{i1},...,r_{i(n-1)},p_i)>$
      4. r代表n-1个节点的评级，有一个节点无法评级，因为不能对自己评级
   4. 事务处理池
      1. 在系统中，每个节点维护两种类型的事务池
         1. 应用程序事务池(ATP)
         2. 验证和评级事务池(VRTP)
      2. ATP用于存储应用程序事务
      3. VRTP用于存储验证和评级事务
      4. 节点需要将区块提交到区块链时，会删除最近提交的区块的所有验证和评级事务来使VRTP为空
   5. 区块
      1. 创建和提交区块会选举新领导者
         1. 在此过程中提出了部分块（PB）和完整块（CB）的概念
      2. 领导节点通过从ATP中包含合法的应用程序事务来创建部分块
      3. 部分块包含四个东西
         1. 领导者的id
         2. 一定数量的合法应用程序事务
            $T{X}^{App}$
         3. 创建时间戳
         4. 领导者的数字签名
         5. 领导者通过数字签名验证上面四个东西
      4. 完整块
         1. 节点从领导者处接收到部分块
         2. 从其他节点处接收到该部分块的所有验证和评级事务
         3. 用以上东西创建一个完整的块
         4. 完整块包含
            1. 块ID
            2. 部分块
            3. 部分块的类型typePB
         5. 按照节点id递增对节点进行验证事务
            $T{X}^{Val}$
         6. 按照节点id递增顺序对节点评级交易
            $T{X}^{Rate}$
         7. 更新所有节点的信誉分数
            1. Ks
         8. 上一块的哈希hprevB
         9. 上一个有效块的哈希hprevVB
            
   6. 区块创建和承诺
      1. 创建一个完整的块流程
         1. 首先创建一个部分块，在网络中传播它然后等待2个最远节点发送消息所需时间
            $2T_{max}$
         2. 节点收到部分块，验证存储在部分块中的事务的合法性
            1. 节点创建验证事务通过设置验证位
         3. 如果部分块有效,给第i个v设置1，否则设置为0
            $v_i$
         4. 节点创建评级交易，对其他节点进行评级
         5. 节点在网络中广播这两个事务
            1. 节点无权对自己评级
         6. 广播之后等待两个Tmax来获取其他节点创建的验证和评级事务
            1. 每个节点都应该得到网络中所有节点创建的验证事务和评级事务
            2. 没有得到全部的事务，会要求节点发送未获得的事务
         7. 当节点获得全部事务时合成完整块需要
            1. 部分块
            2. 所有的评级事务和所有的验证事务
            3. 更新过的信誉分数
            4. 前一个块的哈希（hprevB）和前一个合法块的哈希（hprevVB）
         8. 有效的部分块
            1. 当满足以下共识，节点认为是有效部分块
               $({\sum }_{i=1}^n{v}_i)\ge (\lfloor n/2\rfloor +1)$
               1. 这意味着大部分的验证事务第i个v等于1
               2. 把typePB设置为1
            2. 否则节点认为是无效的块，将typePB设置为0
            3. 由于部分块有可能有效有可能无效，所有我们存储两个哈希值，hprevB和hprevVB
            4. 有效块具有有效部分块，无效块具有无效部分块
         9. 无效区块用来维护与信誉分数相关的历史，这在商业模式中是必要的
            
         10. 为了防止恶意节点提交
             1. 创建一个完整块后，节点使用SHA256算法找到块的哈希值
             2. 广播哈希值，并等待从其他节点获得完整块的哈希值，获取所有哈希之后，比较它们
             3. 如果至少[n/2]+1节点创建相同的哈希，所有节点提交块
             4. 如果提交的CB包含有效PB
                1. 则每个节点从其本地ATP中删除PB中添加的应用程序事务
                2. 每个节点还删除VRTP中关于所提交块的夙愿评级和验证事务
   7. 信誉评分计算
      1. 更新的信誉分数是通过使用其他节点的评级及其当前信誉分数计算的
         1. 只考虑决定了typePB节点的评级
         2. 在集合M中有x个节点（x > n - x）对typePB做出了相同想决定
         3. 评级的权重基于节点信誉分数来计量的
         4. 临时信誉分数和当前信誉分数
            $K{s}_i^{current}$
            $K{s}_i^{temp}$
         5. 计算临时信誉分数公式
            $K{s}_i^{\text{temp }}={\sum }_{\forall j\in M\&j\ne i}\left(\frac{K{s}_j}{{\Sigma }_{\forall j\in N\&j\ne i}K{s}_j}\times \frac{r_{ij}}{10}\right)$
         6. 更新的信誉分数公式
            $K{s}_i^{\text{updated }}=\{\begin{array}{l}\min \left(K{s}_i^{\text{current }}+\Delta r,1\right)\text{ if }K{s}_i^{\text{temp }}\ge Th\\ \frac{\min \left(K{s}_i^{\text{current }},K{s}_i^{\text{temp }}\right)}{2}\text{ if }K{s}_i^{\text{temp }}<Th\end{array}$
            1. △r代表信誉分数的增量
            2. Th代表信誉得分阈值，决定了何时奖励、惩罚
            3. 信誉分数下降很快，获得很慢
            4. 由于领导者恶意行为危害更大，领导者的信誉得分阈值要单独考虑
               1. 前导节点的阈值
                  $T{h}_l$
               2. 非前导节点的阈值
                  $T{h}_{nl}$
            5. 前导节点阈值>非前导节点
   8. 领导人选举
      1. 选举算法中运用到的一些术语和变量

         1. Frequency Table(FT):一个二维数组，第一行按递增顺序保存节点id，第二行保存节点对应频率值

            1. 频率值
               $f{r}_i$
            2. 频率值计算公式
               $f{r}_i=\left[\frac{K{s}_i}{{\sum }_{k=0}^{n-1}K{s}_k}\times n\times 100\right]$

         2. Frequency-based Array of IDs(FA):长度为S的一维数组

            1. S计算方式
               $S={\sum }_{i=0}^{n-1}f{r}_i$
            2. 数组中每个节点ID被放置的次数与频率一样多
            3. 表示节点的ID的基于频率的阵列
               

         3. 创建源区块时，需要手动设置选择一个节点设置为领导者

         4. 节点的三种状态

            1. Null
               1. 选举期间，每个节点都将状态设置为Null
            2. Leader
               1. 领导者状态为Leader
            3. Non-Leader
               1. 其余没被选上的节点状态为Non-Leader

         5. 流程

            1. 刚开始有一个节点设置状态为Null
            2. 它根据每个节点的信誉分数计算每个节点ID的频率，放入节点i的FT
            3. 基于FT创建节点i的FA，之后查找最近提交块的哈希（hashLCB）using SHA256
            4. 将哈希转换为十进制并存储在变量中
               $va{r}_i$
            5. 然后节点获取索引值
               $id{x}_i$
               1. 索引值为变量mod S
            6. 最后id位于节点i的FA中的索引中的变量被选为领导者
            7. 选举过程是在提交区块链的CB之后开始的，因此每个节点都在相同的数据上本地执行选举，并将相同的节点标识为Leader
            8. 最后本地计算的Leader的ID相同的节点创建一个当选节点声明消息Endmsg（El）
            9. 其中El是领导者的id，并发送给所有节点，确认是否统一
               1. 统一就存储在各自的Lid中
               2. 如果不统一就创建投诉消息，发送给所有节点调查不一致性
               3. 不一致性以两种方式发生
                  1. 一个节点谎称自己是领导者
                  2. 一个节点创建针对另一个节点的虚假投诉消息
               4. 投诉消息
                  1. 包括被投诉人的ID、投诉位、投诉消息发送者的数字签名
                     1. 需要投诉投诉位就设为1
                  2. 所有接收到投诉消息的节点，创建一条保留ID的投诉消息
                     1. 如果接受el作为leader将投诉位设置为0
                     2. 如果不接受，每个节点发送一个针对El的投诉消息
                     3. 每个节点可以通过消息中的投诉位观察其他节点意见
                     4. 来识别恶意节点，并在下一轮中减少信誉分
                     5. 领导者选举算法
                        

         6. 复杂性分析

            1. ID与本地匹配的节点创建一个选定的节点声明消息，发送给所有节点
               1. 需要O(n)交换消息
               2. 需要O(d)的时间，d是网络时间
            2. 之后，领导者创建一个部分块，并发送到所有节点
               1. 需要O(n)交换消息
               2. 需要O(d)的时间
            3. 节点获得部分块，创建验证事务和评级事务，发给所有其他节点
               1. O(n²)的消息交换
               2. O(d)的时间
            4. 最后每个节点在本地创建完整块，与其他节点共享完整的哈希
               1. 通过交换实现哈希共享，时间O(n²)
               2. O(d)时间

         7. 论点：选举算法每次只选举一个Leader

            1. 证明
               1. Sel表示一组选定的节点，只需要证明选举结束|Sel| = 1
               2. 每当一个块被提交，每个节点都会开始选举并设置状态为NULL
                  1. 所以|Sel|刚开始为0
               3. 由于每个节点对相同的数据进行操作，因此他们的FA都相同
               4. 因为SHA256的确定性特性，哈希值相同，因此索引值也相同idx
               5. 所以FA[idx]相同，被选为Leader的节点将状态从Null改为Leader成为Sel的一个元素
               6. 并广播El，其他节点都改为Non-leader，因此选举结束后只有一个元素

         8. 论点：每次选举，所有节点都会了解所选节点，并与所选节点达成一致

            1. 证明
               1. 每当节点收到El消息，比较本地计算的Leader ID
               2. 如果相同，节点会通过将El存储到Lid来接受Leader
               3. 如果不同，创建一条投诉消息，发送给其他节点调查不一致性

         9. 论点：领导人选举算法在有限的时间内终止

            1. 选举开始时，每个节点使用存储在最近提交的块的信誉分数构造FT和FA
               1. 需要O(n)+O(100n)的时间
            2. 之后每个节点使用SHA256找到最新提交块的哈希值，在FA中保留所选节点ID
               1. 都在有限时间内
            3. 假设网络直径d，单位时间c(常量),需要从一个节点向相邻节点发送选举消息
               1. 最大时间为O(cd)
               2. 最差情况下d = n - 1,所以d < n，n是有限的，所以时间有限

         10. 定理1：领导人选举算法是自稳定的选举算法

             1. 论点1证明了定理1的唯一性
             2. 论点2证明了定理1的一致性
             3. 论点3证明了定理1的终止性

         11. 定理2：所提出的算法是一个公平的领导人选举算法

             1. 如果成为系统领导者的概率和它的信誉分数成正比这个算法就是公平的
             2. prob代表选为领导者节点的概率
                ${\mathrm{prob}}_i=\frac{f{r}_i}{{\sum }_{x=0}^{n-1}f{r}_x};pro{b}_i=\frac{\frac{K{s}_i}{{\sum }_{k=0}^{n-1}K{s}_k}\times n\times 100}{{\sum }_{x=0}^{n-1}\left(\frac{K{s}_{\chi }}{{\sum }_{k=0}^{n-1}K{s}_k}\times n\times 100\right)};$

         12. 定理3：如果一个系统由n个节点组成，所提出的共识机制可以忍受[(n-1)/2]拜占庭节点故障

             1. 在提出的共识机制中，基于最近提交节点的信息
             2. 领导者创建一个PB，基于验证事务决定PB的类型
                1. 系统有n个节点，需要（n/2 + 1）个节点相同的选择来决定
                2. 意味着系统至少需要这么多个非恶意节点
             3. 最后每个节点本地创建CB，共享完整hash
   9. 基于CAP定理的POK分析的证明
      1. CAP定理代表三个属性
         1. 一致性C
         2. 可用性A
         3. 分区容限P
      2. CAP定理指出一个分布式数据存储系统最多确保两个属性
      3. 区块链是基于对等网络（分布式数据存储）
      4. 论点4：如果所考虑的网络没有被分割，POK的证明满足一致性
         1. 证明
            1. 当避免分叉时，可以保证一致性
               1. 分叉：多个节点同时获得创建块的权限
            2. 系统中只有领导者可以创建块，直到提交之前其他节点都不能创建块
      5. 论点5：如果考虑的网络没有被划分，那么POK证明满足可用性属性
         1. 证明
            1. 根据系统模型节点总数是有限的，所以网络的直径也是有限的
            2. 因此系统中的事务以块的形式永久添加到链中
      6. 定理3：如果网络没有分区，信誉证明满足CAP定理的一致性和可用性性质
         1. 如果没有划分，论点4证明POK满足一致性，论点5证明POK满足可用性
      7. 定理4：如果网络分区，POK满足一致性，不满足可用性性质
         1. 如果从t1时间开始划分，则从论点4得知在t1之前都是满足一致性，每个节点包含相同的链块
         2. t1之后，POK中一个节点获得来自其他所有节点的事务和哈希会添加一个新块，
         3. 如果网络被分区，则节点拥有不会从所有节点得到完整块的哈希，这就是为什么一个节点无法在网络分区后的链中添加新块
         4. 一致性得到满足，可用性得不到满足
         5. 在本次工作我们考虑有n节点组成的分布式联盟系统，网络不是很大，在这种系统中一致性和可用性比分区容差属性更关键