美文网首页
Algorand协议

Algorand协议

作者: yipast | 来源:发表于2019-01-30 14:44 被阅读0次

2017 年，MIT 计算机科学与人工智能实验室（CSAIL）的 Yossi Gilad 和 Silvio Micali 等人在论文《Algorand: Scaling Byzantine Agreements for Cryptocurrencies》中针对 PBFT 算法在很多节点情况下性能不佳的问题，提出 先选出少量记账节点，然后再利用可验证随机函数（Verifiable Random Function，VRF）来随机选取领导节点，避免全网直接做共识， 将拜占庭算法扩展到了支持较大规模的应用场景，同时保持较好的性能（1000+ tps）。

一、简介

根据网络中节点的行为表现，可以将节点分为3种类型：

  • 诚实节点：遵守所有的规则；
  • 恶意节点：随意背离规定。
  • 对手(Adversary): 可以随意将任何节点变成恶意节点，但是存在限制：
    • 不会拥有无限的计算力；
    • 不能伪造诚实节点的数字签名；
    • 无法干扰诚实节点间的消息传递；

而Algorand 可以抵抗强大的对手：

1. 对手能腐败任何节点
   解决：系统2/3的钱属于诚实节点 （Honesty Majority of Money，HMM假设）

2. 对手能控制所有被腐败的节点和所有消息的传输 
   解决：保证诚实节点发送的每条消息m都能在固定的一个时间内到达95%的诚实节点 （消息广播假设）

除了能够对抗强大的对手，Algorand 还具有以下属性：

  • 必需的计算量已经最小化：1/1500的节点最多需要几秒钟的计算
  • 新区块产生的时间少于10分钟：测试环境验证一个区块的生成要低于40s
  • Algorand是纯分布式系统，没有类似比特币中的miner角色
  • 节点可以随意加入和退出
  • 不可预测性，出块节点和验证节点在完成自己的工作之前，其他节点都无法提前预测到

简化后的协议流程描述：

  1. 节点从以前的区块获取到种子值，并通过加密抽签判断自己是否是本轮的Leader。若是，则算一个新的种子值，打包出块，并广播到全网。
  2. 所有节点都能收集到提案的区块，通过加密抽签判断自己是否是验证节点，若是，则选出优先级最高的区块哈希值广播到全网。
  3. 投票阶段包含了m个步骤，在每个步骤，节点都需要通过加密抽签判断自己是否是投票节点，若是，则综合收集到的信息，得出投票结果并广播。
  4. 经过n个投票步骤后，最终达成共识。

1.1 预备知识

数字签名

数字签名机制由3个快速算法组成：

  1. G生成概率key：生成一对公钥 pk_i、私钥 sk_i

  2. 签名算法S：使用私钥对消息的哈希进行签名
    sig_i(m) = sig_{pk_i}(m) \triangleq S(H(m), sk_i)

  3. 验证算法V：使用公钥对签名后的数据进行验证
    V(pk_i, m, s), s = sig_i(m)

特性：

  1. 合法的签名永远是可以被验证的

  2. 数字签名很难伪造
    SIG_{pk_i}(m) = (i, m, sig_{pk_i}(m)) \\ SIG_i(m) = (i, m, sig_i(m)), \mbox{if } pk_i \mbox{ is clear}

  1. 公钥、私钥的唯一性

Algorand中使用数字签名的3种场景：

  1. 认证自己的支付；
  2. 生成凭证来证明自己的角色；
  3. 验证节点i在每个角色的过程中发送的消息。

可验证随机函数VRF

1.2 基础概念和符号

支付集合：
第 r 轮的支付集合：\mathcal{P}
第 r 轮所有 \mathcal{P} 的集合：\mathbb{PAY(r)}

\#_i^s(v)，\mbox{ 在步骤 } s \mbox{ 中给节点 } i \mbox{ 发送 } v \mbox{ 的节点数量 }

二、协议

Algorand 协议是一种新的、加密的拜占庭共识协议，简称为BA^*。
简单来讲，BA^*分为两部分：分级共识协议GC和二元拜占庭协议BBA^*

  • 分级共识协议GC：
    让每个节点收集提案区块的哈希值，并选出自己认可的leader。
  • 二元拜占庭协议BBA^*：
    通过三步循环让节点投票，挑选出一个leader达成共识。

2.1 分级共识协议GC

步骤2：每个节点 i 给所有节点发送 v_i^{'}
步骤3：当且仅当 \#_i^2(x) \geqslant 2t+1 时，每个节点 i 给所有节点发送字符串 x

每个节点 i 的输出对 (v_i,g_i) 的计算如下：
\begin{cases} \#_i^3(x) \geqslant 2t+1, & \mbox{ then } v_i=x, \ g_i=2 \\ \#_i^3(x) \geqslant t+1, & \mbox{ then } v_i=x, \ g_i=1 \\ else, & v_i = \perp, \ g_i=0 \end{cases}
定理：若 n \geqslant 3t+1，则 GC 是一个 (n,t) 分级的广播协议。

2.2 二元拜占庭协议BBA^*

3步循环：节点间不停的交换b值

节点可以在任意时间退出该循环。如果节点 i 在退出前，在某步骤广播了一个值 b，退出后，其它节点就假装从 i 那收到了 b 值

协议有一个计数器 \gamma，标记 3步循环 执行的次数。

3步循环：

  1. 节点 i 发送 b_i:
    b_i = \begin{cases} 0,\quad \#_i^1(0) \geqslant 2t+1,\quad \mbox{输出 } out_i=0, \mbox{ 停止} \\ 1,\quad \#_i^1(1) \geqslant 2t+1 \\ 0,\quad \mbox{other}\\ \end{cases}

  2. 节点 i 发送 b_i:
    b_i = \begin{cases} 1,& \#_i^2(1) \geqslant 2t+1,\quad \mbox{输出 } out_i=1, \mbox{ 停止} \\ 0,& \#_i^2(0) \geqslant 2t+1 \\ 1,& \mbox{other}\\ \end{cases}

  3. 节点 i 发送 b_i 和 SIG_i(r, \gamma):
    b_i = \begin{cases} 0,& \#_i^3(0) \geqslant 2t+1 \\ 1,& \#_i^3(1) \geqslant 2t+1 \\ c \triangleq lsb(min_{j \in S_i} H(SIG_i(r, \gamma))),& \mbox{other}\\ \end{cases}
    other情况下，S_i = \{j \in N，j 为在第3步给节点 i 发送了合适消息的节点，\gamma_i 加1，返回步骤1。

2.3 BA^* 协议

  1. 第一阶段：分级共识协议GC
    步骤1和2：每个节点 i 执行 GC，输入为 v_i^\prime，计算一对 (v_i,g_i)
  2. 第二阶段：二元拜占庭协议 BBA*
    步骤3：每个节点 i 执行 BBA^*，初始输入为0（若 g_i=2，则为1），计算bit位 out_i

输出决定条件：每个节点 i 的输出为 v_i，则 out_i=0，否则为 \perp。
定理：若 n \geqslant 3t+1，则 BA* 是一个 (n,t) 分级的、稳健为1的 BA 协议。

2.4 实例1：Algorand_1^{\prime}

2.4.1 符号

通用符号：

r \geqslant 0：第几轮
s \geqslant 1：第几步
B^r：第r轮生成的区块
PK^r：第r-1轮结束时第r轮开始时的公钥集合
S^r：第r-1轮结束时第r轮开始时的状态
PAY^r：B^r中包含的支付集合
l^r：第r轮的领导者，它选择第r轮的支付集合 PAY^r，并决定种子 Q^r
Q^r：第r轮结束时生成的种子，被用来选择第r+1轮的验证者。独立于区块中的支付集合，且不能被 l^r 操纵。
SV^{r,s}：第r轮第s步选中的验证者集合
SV^r：第r轮选中的验证者集合，是所有步骤的验证者集合的并集，SV^r = \cup_{s\geqslant1}SV^{r,s}
MSV^{r,s}, HSV^{r,s}：SV^{r,s}中的恶意验证者集合和诚实验证者集合，MSV^{r,s} \cup HSV^{r,s} = SV^{r,s}，MSV^{r,s} \cap HSV^{r,s} = \varnothing
n_1 \in \mathbb{Z^+}, n \in \mathbb{Z^+}：在 SV^{r,1} 和 SV^{r,s}(s>1) 中期望的potential leader数量，n_1 << n
h：大于2/3的常量，系统的诚实比率。
F \in (0,1)：指定可允许错误率的参数
p_h \in (0,1)：在第r轮中，领导者是诚实节点的概率
k \in \mathbb{Z^+}：回望参数，第r轮的验证者从第r-k轮的节点中选择，SV^r \subseteq PK^{r-k}
p_1 \in (0,1)：在第r轮的第一步中，在第r-k轮中的节点被选中为验证者的概率 p_1 \triangleq \frac{n_1}{PK^{r-k}}
p \in (0,1)：在第r轮的s(s>1)步中，在第r-k轮中的节点被选中为验证者的概率 p_1 \triangleq \frac{n}{PK^{r-k}}
CERT^r：区块 B^r 的签名。是在第r轮中来自合格验证者的签名 H(B^r) 的集合
\overline{B^r} \triangleq (B^r,CERT^r)：被证明区块。
\tau_i^r：节点i知道 B^r 的本地时间
\alpha_i^{r,s},\beta_i^{r,s}：节点i在第r轮开始和结束步骤s的本地时间
\Lambda,\lambda：执行步骤1和其它步骤所需要的时间上限。Lambda 是广播一个1MB区块所需要的时间上限。假设 \Lambda = O(\lambda)

2.4.2 协议步骤

  1. 提案区块：

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第1步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,1}
    • 若 i \notin SV^{r,1}，i停止
    • 若 i \in SV^{r,1}，即i是potential leader
      • 收集广播给它的第r轮的支付，并且从中得出最大化支付集合 PAY_i^r
      • 计算出它的候选区块 B_i^r = (r,PAY_i^r,SIG_i(Q^{r-1}),H(B^{r-1}))
      • 计算出消息 m_i^{r,1} = (B_i^r,esig_i(H(B_i^r)), \sigma_i^{r,1})
      • 销毁临时私钥 sk_i^{r,1}，广播 m_i^{r,1}

    注：(r,1) 消息是有选择的广播。节点i收到第一条(r,1) 消息并验证成功后，正常广播；随后收到的、并验证成功的 (r,1) 消息，当且仅当它包含的凭证哈希比之前收到的 (r,1) 消息的凭证哈希都要小时才会被广播出去。也可以先让每个potential leader单独广播它们的凭证 \sigma_i^{r,1}，然后让含有较小凭证哈希值的节点广播它们的 m_i^{r,1} 消息

  2. GC协议的第一步：

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第2步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,2}
    • 若 i \notin SV^{r,2}，i停止
    • 若 i \in SV^{r,2}，等待时间 t_2 \triangleq \lambda + \Lambda，i执行以下动作：
      • 节点从收到的所有 (r,1) 消息中为所有的凭证 \sigma_j^{r,1} 计算哈希值，找到领导者 l: \ H(\sigma_l^{r,1}) \leqslant H(\sigma_j^{r,1})
      • 若节点已经从l收到了有效的消息 m_l^{r,1} = (B_l^r, esig_l(H(B_l^r)), \sigma_l^{r,1})，i设置 v_i^\prime \triangleq H(B_l^r)，否则设置 v_i^\prime \triangleq \perp
      • i计算出消息 m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})
      • 销毁临时私钥 sk_i^{r,2}，广播 m_i^{r,2}

  3. GC协议的第二步：

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第3步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,3}
    • 若 i \notin SV^{r,3}，i停止
    • 若 i \in SV^{r,3}，等待时间 t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambda，i执行以下动作：
      • 若存在一个值 v^\prime \neq \perp（即节点收到的所有有效 m_j^{r,2} 消息中，多余2/3的消息格式为 (ESIG_j(v^\prime), \sigma_j^{r,2}) ），i计算出消息 m_i^{r,3} \triangleq (ESIG_i(v^\prime), \sigma_i^{r,3})；否则 m_i^{r,3} \triangleq (ESIG_i(\perp), \sigma_i^{r,3})
      • 销毁临时私钥 sk_i^{r,3}，广播 m_i^{r,3}

  4. 跳出GC协议，BBA*的第一步：

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第4步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,4}
    • 若 i \notin SV^{r,4}，i停止
    • 若 i \in SV^{r,4}，等待时间 t_4 \triangleq t_3 + 2\lambda = 5\lambda + \Lambda，i执行以下动作：
      • 节点按照以下方法计算GC的输出：v_i, g_i
        • 若存在一个值 v^\prime \neq \perp（即节点收到的所有有效 m_j^{r,3} 消息中，多余2/3的消息格式为 (ESIG_j(v^\prime), \sigma_j^{r,3}) ），则 v_i \triangleq v^\prime, g_i \triangleq 2；
        • 若不存在 v^\prime \neq \perp（即节点收到的所有有效 m_j^{r,3} 消息中，多余1/3的消息格式为 (ESIG_j(v^\prime), \sigma_j^{r,3}) ），则 v_i \triangleq v^\prime, g_i \triangleq 1；
        • 否则， v_i \triangleq H(B_\epsilon^r), g_i \triangleq 0；
      • 节点计算BBA^*的输入：b_i \triangleq \begin{cases} 0 &g_i=2 \\ 1 &\mbox{otherwise}\end{cases}
      • 节点计算消息 m_i^{r,4} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,4})
      • 销毁临时私钥 sk_i^{r,4}，广播 m_i^{r,4}

  5. 步骤s，5 \leqslant s \leqslant m+2, s-2 \equiv 0 \ mod \ 3：BBA^*的Coin-Fixed-To-0步

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第s步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,s}
    • 若 i \notin SV^{r,s}，i停止
    • 若 i \in SV^{r,s}，等待时间 t_s \triangleq t_{s-1} + 2\lambda = (2s-3)\lambda + \Lambda，i执行以下动作：
      • 以0结束：在等待时，若存在一个值 v \neq \perp 和步骤 s^\prime，使得：
        • （a）5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 3，即 s^\prime 是Coin-Fixed-To-0步骤
        • （b）i收到至少 t_H = \frac{2n}{3}+1 个有效消息 m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})，同时
        • （c）i收到了一个有效消息 m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1}),v=H(B_j^r)，i停止步骤s，设置 B^r = B_j^r，将子步骤（b）中消息 m_j^{r,s^\prime-1} 的集合设置为它自己的 CERT^r
      • 以1结束：在等待时，若存在一个步骤 s^\prime，使得：
        • （a'）6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 3，即 s^\prime 是Coin-Fixed-To-1步骤
        • （b'）i收到至少 t_H 个有效消息 m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v), \sigma_j^{r,s^\prime-1})，同时
        • （c'）i停止步骤s，设置 B^r = B_\epsilon^r，将子步骤（b'）中消息 m_j^{r,s^\prime-1} 的集合设置为它自己的 CERT^r
      • 其它：在等待结束时，节点i执行以下动作：
        • 在收到的m_j^{r,s-1}中，有超过2/3的m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})，则令b_i=1
        • 否则令b_i=0
        • 节点计算消息 m_i^{r,s}=(ESIG_i(b_i),ESIG_i(v_i),\sigma_i^{r,s})
        • 销毁临时私钥 sk_i^{r,s}，广播 m_i^{r,s}

  6. 步骤s，6 \leqslant s \leqslant m+2, s-2 \equiv 1 \ mod \ 3：BBA^*的Coin-Fixed-To-1步

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第s步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,s}
    • 若 i \notin SV^{r,s}，i停止
    • 若 i \in SV^{r,s}，等待时间 t_s \triangleq t_{s-1} + 2\lambda = (2s-3)\lambda + \Lambda，i执行以下动作：
      • 以0结束：同 Coin-Fixed-To-0 步骤
      • 以1结束：同 Coin-Fixed-To-0 步骤
      • 其它：在等待结束时，节点i执行以下动作：
        • 在收到的m_j^{r,s-1}中，有超过2/3的m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})，则令b_i=0
        • 否则令b_i=1
        • 节点计算消息 m_i^{r,s}=(ESIG_i(b_i),ESIG_i(v_i),\sigma_i^{r,s})
        • 销毁临时私钥 sk_i^{r,s}，广播 m_i^{r,s}

  7. 步骤s，7 \leqslant s \leqslant m+2, s-2 \equiv 2 \ mod \ 3：BBA^*的Coin-Genuinely-Flipped步

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第s步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,s}
    • 若 i \notin SV^{r,s}，i停止
    • 若 i \in SV^{r,s}，等待时间 t_s \triangleq t_{s-1} + 2\lambda = (2s-3)\lambda + \Lambda，i执行以下动作：
      • 以0结束：同 Coin-Fixed-To-0 步骤
      • 以1结束：同 Coin-Fixed-To-0 步骤
      • 其它：在等待结束时，节点i执行以下动作：
        • 在收到的m_j^{r,s-1}中，有超过2/3的m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})，则令b_i=0
        • 在收到的m_j^{r,s-1}中，有超过2/3的m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})，则令b_i=1
        • 否则令b_i \triangleq lsb(min_{j \in SV_i^{r,s-1}}H(\sigma_j^{r,s-1}))，SV_i^{r,s-1} 为收到的有效消息 m_j^{r,s-1} 中获得的 (r,s-1)-验证者
        • 节点计算消息 m_i^{r,s}=(ESIG_i(b_i),ESIG_i(v_i),\sigma_i^{r,s})
        • 销毁临时私钥 sk_i^{r,s}，广播 m_i^{r,s}

  8. 步骤 m + 3：BBA^*的最后一步

    节点 i \in PK^{r-k} 只要知道了 B^{r-1}，就开启了它的第r轮第 m + 3 步

    • 节点从 B^{r-1} 中计算出 Q^{r-1}，并且检测是否 i \in SV^{r,m+3}
    • 若 i \notin SV^{r,m+3}，i停止
    • 若 i \in SV^{r,m+3}，等待时间t_{m+3} \triangleq t_{m+2} + 2\lambda = (2m+3)\lambda + \Lambda，i执行以下动作：
      • 以0结束：同 Coin-Fixed-To-0 步骤
      • 以1结束：同 Coin-Fixed-To-0 步骤
      • 其它：在等待结束时，节点i执行以下动作：
        • 在收到的m_j^{r,s-1}中，有超过2/3的m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})，则令b_i=0
        • 设置 out_i \triangleq 1, B^r \triangleq B_\epsilon^r
        • 节点计算消息 m_i^{r,m+3}=(ESIG_i(out_i),ESIG_i(H(B^r)),\sigma_i^{r,m+3})
        • 销毁临时私钥 sk_i^{r,m+3}，广播 m_i^{r,m+3} 来验证 B^r
  • 非验证者在第r轮的区块重构：节点 i 只要知道了 B^{r-1}，就开启了它的第r轮，并且按以下方法等待区块信息
    • 在等待期间，若存在 v, s^\prime 使得：
      • （a）5 \leqslant s^\prime \leqslant m+3, s^\prime-2 \equiv 0 \ mod \ 3
      • （b）i收到至少 t_H 个有效消息 m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})
      • （c）i收到一个有效消息 m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1}),\ v = H(B_j^r)
      • i停止它的r轮执行，令 B^r=B_j^r，将子步骤（b）中消息 m_j^{r,s^\prime-1} 的集合设置为它自己的 CERT^r
    • 在等待期间，若存在 s^\prime 使得：
      • （a'）6 \leqslant s^\prime \leqslant m+3, s^\prime-2 \equiv 1 \ mod \ 3
      • （b'）i收到至少 t_H 个有效消息 m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})
      • i停止它的r轮执行，令 B^r=B_\epsilon^r，将子步骤（b'）中消息 m_j^{r,s^\prime-1} 的集合设置为它自己的 CERT^r
    • 在等待期间，若i收到至少 t_H 个有效消息 m_j^{r,m+3} = (ESIG_j(1), ESIG_j(H(B_\epsilon^r)), \sigma_j^{r,m+3})
      • i停止它的r轮执行，令 B^r=B_\epsilon^r，将1和 H(B_\epsilon^r) 的消息 m_j^{r,m+3} 的集合设置为它自己的 CERT^r
Algorand1 协议流程

相关文章

网友评论

      本文标题：Algorand协议

      本文链接：https://www.haomeiwen.com/subject/ayqcsqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Algorand协议|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！