'CryptoYC'
研究|深度解析公链 —— Flow
🌿

研究|深度解析公链 —— Flow

Flow 通过将加密货币矿工或验证器的工作分成四个不同的角色,每个角色都有自己的特点,在不分片并且确保安全性的前提下实现了速度和吞吐量的显著提高。 解决的问题:不可能三角以及PoW 中的验证者困境。本文分析了Flow为了提高TPS而提出的解决方案,并且对其安全性和高效进行了逐一分析。

一. 术语

  • Blockchain:大部分现有的区块链专注于金融交易过程,在 Flow 里面区块链被认为是一个图灵完备的分布式计算平台。
  • Transactions:计算状态的转换
  • Consensus:线性化的状态转换

二. 架构综述

在介绍架构前,先解释一个名词,关注点分离(separation of concerns),计算机科学中解决复杂问题的一种思维方法,将计算机程序分隔成不同部分的设计原则。只对关注点(特定概念,目标)相关联的软件组成部分进行“标识,封装和操纵”的能力。分离关注点可以将特定领域问题从业务逻辑中独立出来,每个部分也可以独立开发和更新,也可以很好的管理。

Figure 1: Flow 工作流程
Figure 1: Flow 工作流程

Flow 的架构是在“关注点分离”原则的基础上建立的。一般的区块链在双花问题上需要同时解决计算问题并且还要判断哪笔交易正确和哪笔交易是错误的,这就是验证者困境(Verifier’s Dilemma),Flow 可以解决这个问题,将有正确答案的计算问题和需要双方共同选择的共识问题分开解决,所以 flow 网络有专门的两个角色:共识节点和执行节点,核心分别是主观性和客观性。其他的角色分别是收集者,验证者和观察者。

三.角色介绍

Collector: 将格式良好的交易数据收集进集合里,并且进行签名,保证有超过三分之二的人签名,再将摘要传输给共识节点。

Consensus Role: 主要是定义执行顺序,共识节点不用维持计算状态和执行交易,就是前文所说的共识节点执行的是主观性任务。在 signedCollectionhashes 中存储聚合签名,然后再将块广播到全网。

Execution role: 按照共识节点确定的执行顺序,提供确定交易结果所需的原始计算能力。生成加密证明,以“执行收据(execution receipts)”的形式生成加密证明,证明他们的工作(effort)。并且将收据证明广播给共识和验证节点。这就是客观性任务。

Verifier: 对执行节点执行的结果进行验证,生成结果审批(result approval)。

Observer: 将数据发送给协议外部实体,这些实体并不参与协议本身。

SPoCK 协议

标准的区块链转换方程 S’=t(B,S),其中 S′ 是改变后的状态,B 是修改世界 状态的交易块,S 是处理前的状态。SPoCK 协议是为了防止验证节点对执行节点的执行收据进行 copy,Flow 构建一个新的转换函数 t′,存在 (S′ , ξ) = t′(B, S), 其中 S′ 是改变后的状态,B 是修改世界状态的交易块,S 是处理前的状态,ξ 是一个秘密输出,是执行计算时可以得到的确定值。类似于 CPU 存储器在执行步骤时的散列,推导比重新计算的成本要高得多。这就是哈希不可篡改的原理,只能单向计算而不能由结果进行反推。

SPoCK 协议的运行

  • 执行节点 Alice 向某个 Merkel 根 S’ 发送签署认证,同时发布一个自己的 ξ 的 SPoCK
  • 验证节点 Bob 验证 S’ 是 t(B,S)的准确应用,并且也会发布一个自己的 ξ 的 SPoCK
  • 观察者就可以确认两个 SPoCKs 是否来自同一个 ξ

一个 SPoCK 的产生

  • 用 ξ 作为确定密钥产生的种子,生成一个密钥对(pk,sk)
  • 用私钥对你的身份(例如节点 ID)进行签名,并将其与公钥一起发布,即

SPoCK Z = (pk, sign_sk(ID)) (1)

所有的观察者可以通过验证签名来确定 Alice 和 Bob 是否都是知道同一个底层的秘密 ξ

妥协三角

对于不可能三角(去中心化,可扩展性,安全性不能同时满足)存在的问题, Flow 在图二通过调整延迟确定性,开销和节点来进行优化。蓝色圈是执行节点, 低延迟确定性,低开销和少数节点;橙色圈是共识节点,低延迟确定性,高开销和多数节点。

Figure 2: 优化的 Vlad Zamfir 妥协三角
Figure 2: 优化的 Vlad Zamfir 妥协三角

四. 安全性分析

有总体节点为 N,其中拜占庭节点 M 最多有 M < N/3 个,从 N 中随机选取一 个子集合有 n 个子节点,并且每个节点是平等质押(权重相等)无放回的取 n 个元素放入样本中,那么 m ≤ n 的拜占庭节点将符合超几何分布(1):

image

当取的 n 个节点全部为拜占庭节点时,即 m=n,样本中不存在诚实节点时, 公式(1)的概率达到最大值,那么攻击成功的概率 P(successful attack) 就是 (2)

image

为了判断分布的性质,我们将取 n 个节点概率和在 n+1 时的概率做个比值, 通过(4)得到概率分布满足当 n 增加,函数单调递减。

image

假设当攻击节点攻击成功时会获得奖励 r,但一旦攻击节点被发现,那么节点将被削减 ξ 个数量,一般来说是正值,那么(5)满足攻击网络的预期收入 revenue = P(成功)×r - P(失败) ×ξ

image
image

如果攻击在经济上可行,那么就有 revenue ≥ 0,不等式(6)变为(7),并且结合(4)的结论,可以得到随着 n 的增加,r/ξ 严格单调递增。有文献表明当 n 满足 n ≤ N/2 时,r/ξ 呈指数增长

image

白皮书中进行了举例说明:给 N,M,n 赋值,N=1000,M=333,n=10 时, 为了计算简单,假设错误节点的 stake 全部被削减掉,那么在经济可行的条件 下,r 需要达到 stake 的大约 65k 倍(如果验证者质押 1000,攻击者就要花 6500 万来支付被削减掉的成本)。如果将 n 增加到 20,那么 r 就要达到 ξ 的 52 亿倍, 错误才可以通过绝大多数诚实节点。所以通过上面可以推出,在实际情况下,恶意节点想要通过诚实节点在经济上是无法实现的。共识节点需要做的就是检查有足够多的节点参与了执行操作,而并不需要检查结果本身。

五. 吞吐量

了解了安全性,下面来看白皮书对于 Flow 吞吐量的研究。去中心化算法中较为有名的是 gossip 算法,又被称为反熵,就是在杂乱无章中寻求一致。一个周期的开始是由种子节点发起,当一个种子节点有状态需要更新到网络中的其他节点时,它会随机的选择周围几个节点散播消息,收到消息的节点也会重复该过程,知道最终网络中所有的节点都收到了消息,这个过程可能需要一定的事件,由于不能保证某个时刻所有节点都收到消息,但是理论上最重所有节点都会收到消息,因此它是一个最终一致性协议。但是有个缺点就是速度较慢且消耗较大。在 2015 年的比特币算力研究显示,比特币 75% 的算力由大约 2% 的节点提供,这代表算力非常集中,Flow 的模拟实验中,将中心化指标设置为比特币的一般,即大概 38% 的算力有 6% 的快节点提供,对于剩下的 62% 算力,应用一个不那么极端的比例:2/3 的节点(慢节点)提供的 算力占剩下算力(62%)的 1/3,则剩下的就是中等节点。所以三类节点数量的比值大约为 1:5:10。接下来设置了三组实验进行比较:

image

第一组是 flow 的共识计算分离,将算力强的节点作为执行节点,剩下的作为共识节点;第二组是传统 PoS 的,有各种速度的节点,第三组只有慢节点。通过实验证明 Flow 结构的网络吞吐量显著提高。采用共识和计算相结合的网络架构,吞吐量提高了 56 倍。

F
Figure 3: 三组实验对比

六. 总结

Flow 链架构建立在“关注点分离”的原则基础上,将节点分成不同的部分,利用网络生态中的资源不平衡,根据节点的算力快慢进行区分,快节点用来做计算,其他节点用来做共识节点,解决验证者困境,并且在保证了安全性的前提下,提高了吞吐量。但同时也存在一个问题,就是在白皮书中,所有定理的假设前提都是存在少于 1/3 的拜占庭节点,所以出现错误和被攻击的概率都会很低( 即安全性高)。所以真实情况如何,还有待观察。