基础理论

共识理论

Paxos

传统方案：一个出块（提议）结点，并行性不够

多个提议者

问题——提案可能同时到达，造成顺序混乱
传统问题
解决方案：新增编号字段+接受编号更大的Prepare请求

具体流程实例——

节点1成为leader ，准备发送消息P(1)
- 其他节点会比较1和上一个应答的编号
- 如果上一个应答编号更大，那么不会回复，否则回复ack
节点1接收其他节点的ack后，发送A(1,1)【具体的请求】到acceptor中，但网络问题没有收到。
节点2准备提案P(2)，因为节点1已经接受了A(1,1)，会在P(2)返回的ack中返回1（已经接收节点1了）给节点2。
节点2收到大家的同意确认，发现节点1的返回信息中含有已经接受的提案，但和自己不符合就将其提案内容作为自己的提案
- 即A(2,1)=A(1,1)
此后节点2、3才收accept(1,1)请求，由于这个请求的提案编号1小于自己已经接受的提案编号2，所以不会同意，直接拒绝。【完成同步】
最终，3个节点都是x=1，保持一致。

协议实现复杂，在大型分布式网络中的通信开销和延迟时间不能很好地扩展。

Raft

Raft算法是Paxos算法的一种简化实现。
动画：演示

跟随者：选民
候选者：被提名成为候选者
领导者：处理请求、管理日志
- 以领导者为核心
- 保证顺序不会混乱

领导者选举

心跳机制
- 每个结点设置一个超时时间
- 领导者定期发送心跳信号给所有跟随者
- 如果一段时间没收到信号，就认为没有有效领导者（心跳没了）
选举机制
- 候选结点提出RequestVote请求
- 其他候选结点为其投票
- 达到半数即可认为可以。
投票规则
- 优先投给日志完整性高
- 每个节点对每个任期编号的选举只能投出一票，相同完整度先来先服务。
- 赢得一半以上选票的候选人，即成为新的领导者

C也会发现自己的日志不够，向邻近结点发送请求获取新日志，保证同步

平票机制
- 随机超时机制
- 平票节点随机重新倒计时并重新选举
- 首先发起拉票的节点 （超时时间短） 有机会得到更多的选票

日志复制

严格按照时间序列排序

事务提交流程

A挂了，这种情况优先投给B
未完成的日志复制只能被丢弃（如4、5）。

地理信息

经纬度+时间戳

时间戳保证了地理位置信息的时效性

双线性对的密码学

假设公钥$z$，私钥$x\&y$，且满足$z=xy$
因为$e(g^x,g^y)=e(g,g)^{xy}=e(g,g)^z=e(g,g^z)$
因此可以在不泄露$x、y、z$的前提下完成密码的校验。

系统结构

架构设计
- 三层架构
- 三个角色（leader、candidate、follower）
  - 全局leader：最顶层的leader
角色与共识
- 由candidate和leader参与共识
- 动态选举
局部共识与全局共识
- 为了完成整个树型结构的共识
- 节点在每个子层区块链内部执行局部共识
- 每个子层区块链leader通过使用门限签名方案和本地/全局日志复制方案参与分层共识，以达到全局共识。

选取候选节点

减少通信复杂度
以地理位置+信誉为动态候选群组

数据结构

信誉值

利用图来记录,比以往论文的全局记录更优秀.
因为可能在异步的网络中,两个节点相互的记录可能是不一样的

信誉图$(V,A)$【V个顶点，A条边】
- 无环有向图
Vi分配给Vj的信誉度：$\omega(V_i,V_j)\in[0,R]$
- 基于$Vi$对于$Vj$的记录
- 初始为1
- 不存在自弧(环)
标准化声誉
- $\rho({V}_{i},{V}_{j})=\frac{\omega(V_{i},V_j)}{\sum_ {V_K\in L(V_i)}(\omega(V_{i},V_k))}=\frac{Vi分配给Vj的信誉度}{Vi分配给其他发生交易的节点(包含Vj)的信誉度总和}$
- 排除了各个节点因为信誉值设置的不同而造成的差异
  - 比如:有个恶意节点对其他节点全是1-10,给同伙100
- 标准化后满足总和为1
- $\sum_{V_{j}\in\mathcal{V},\forall j\neq i}\rho(\mathcal{V}_{i},\mathcal{V}_{j})\stackrel{\_}{=}1.$
- 某一结点的总信誉$\tau_i$是其他结点赋予的标准化信誉值的总和.

💡如果有结点与其他结点发生交易较少,那么他的信誉分总是不太够.
在一个系统中,新加入的结点容易被旧结点垄断.

可以用平均值代替总和,参与交易多的适当给予信用值补偿

基于在[[区块链/权威证明共识机制在区块链上的研究和应用]]中的”控制信用分思想”,设定一个S型函数,最初时可以获得较高权重的信用分,随着迭代轮次的增加,信用分增长率逐渐减少.

当成为主节点后,增长率又设定最大

$C_s=\frac{n}{1+e^{-(\lambda k+\phi)}}R$

距离分数

$\sigma_{i}=\frac{\sum_{\mathcal{V}_{i}\in\mathcal{V}}\,d_{\mathcal{V}_{i}}}{\mathcal{V}\times d_{ \mathcal{V}_{i}}}=\frac{所有结点的距离之和}{结点数量\times 这个结点到事件的距离}$

越远分数越小

IP-CGF决策选取候选结点

整数规划——
使得整个组合分数最大化

目标函数

$\mathrm{Maximize}\sum_{\forall i}(\alpha\tau_{i}+\beta\sigma_{i})X_{\mathcal{V}_{i}}$

其中$\alpha 、\beta$是设定的权重
$X_{\mathcal{V}_{i}}$为i结点是否在候选组中

最大化分数

限定条件

$\sum_{\nu_{i}\in\nu}X\nu_{i}=M$：系统可以人为规定选取的总结点数为$M$
$X_{\mathcal{V}_{i}}\in \{0,1\}$：决策变量是二元

Lh-Raft共识构建

过程

启动选举
- 广播 “开始选举”
- 等待$T$时间，期间收集其他结点的CGF-IP分数
  - 如果收集到了N份，继续
  - 否则重新发起
其他结点收到“开始选举”信号：发送CGF-IP分数

🤔这里需要防篡改

排序，选择前M个位候选群体
- 广播候选人组
候选群体确认
选举领导
- 开始投票，如果得票最多，那么成为领导
进入新阶段

安全要求

防篡改

每个结点定期提交自己的信用打分和地理位置
地理位置采用CSC技术（Crypto-Spatial Coordinates）
- 将经纬度打包为哈希值，上链
- 具备可验证、隐私性
其他结点和上级结点周期性地检查候选者节点的地理信息
- 如果节点的地理位置信息在过去的时间t内发生了显著的变化，则将其从候选组中移除。

结点加入和离开

串行
一次性只能进出一个，且进出后必须再达成一次共识

否则会导致门限签名可能失效，达不到门限值

选举限制

领导者必须有一个提交的条目

如果一个候选节点在其日志中没有所有提交的条目，那么该节点永远不会赢得领导人选举

因为子层网络至少会提交一次事务到上层网络，所以必然有一个结点不存在选举限制

领导者突然离开

用心跳消息来检查，如果超时则重新选举

全局一致性

门限签名方案

上层区块链作为验证者网络，只有至少t个共识节点的签名被验证为合法，才会信任下层区块链。

下层节点生成密钥
- 选取随机数私钥$a_i$
- 计算公钥$v_i=g^{a_i}$
下层节点门限签名生成
- 基于MAC地址和地理位置计算哈希$h_i=hash(MAC,LOCATION)$
- 生成签名$\delta_i=h_i^{a_i}$
上层结点验证
- 如果$e(\delta_i,g)=e(h_i^{a_i},g)=e(h_i,g)^{a_i}=e(h_i,g^{a_i})=e(h_i,v_i)$则验证正确
- 如果收集到t个验证正确的签名——达到门限