type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 15, 2023 08:06 AM
Parent item
领域
Flow区块链的特性
- 结合BFT和PoS共识
- PoS的好处：根据权益决定节点影响力，防止女巫攻击，便于实施惩罚，增加链的吞吐量，同时也降低了维护链安全相关的总资金成本
- BFT的好处：在小范围节点内实施拜占庭容错
- 分离共识和计算：交易的收集、排序、执行、验证独立执行，分开后不影响系统安全性和去中心化
- 收集节点、共识节点负责主观问题(共识)，执行节点、验证节点负责客观问题(计算)
- 只对交易顺序达成共识
- 验证者困境问题（第三方节点检查交易执行结果的正确性：吃白食(只批准不计算)；恶意标记(估计批准错误结果)）
- 共识节点不存在验证者困境问题，因为他无需执行验证工作
- 将执行和计算分离，计算的验证者使用机密知识证明 (SPoCKs) 解决验证者困境
- 吞吐量比传统PoS提高56倍
基本算法
数学理论
除共识节点以外，将节点分为操作处理者和操作验证者，并从中随机选出2个小团体，将操作和验证工作委托给小团体，拜占庭节点想通过故意发布或批准错误结果将错误引入系统在经济上是不可行的。
在数学上通过超几何分布证明。从有限的个节点（其中包含个拜占庭节点）中抽出个节点，仅抽到拜占庭节点的概率随着的增加而严格单调下降。
假设存在一些奖励，如果攻击成功，该节点将收到该奖励。但是，如果被发现攻击，节点将被罚没（按照惯例为正数），攻击者攻击系统的统计成本，当时， 随 呈指数增长。
HotStuff
- 拜占庭节点控制的权益不能超过总权益的1/3
- 协议按轮次进行，每一轮只有一个节点作为领导者
- 通过确定性函数选举每一轮的领导者
- 通过准备、预提交和提交的三阶段提交协议推进共识
- 每轮的共识以领导者的提议开始，以就提议达成共识或超时结束
- 有个节点参与共识，HotStuff 的通信复杂度为
DRB
每个种子都无法被任何单个节点预测，种子本身以完全去中心化的方式生成和发布
SPoCK
目的是用来规避验证者困境，防止执行或验证节点偷懒，相互复制执行结果或结果批准。
生成SPoCK的步骤
- 根据交易内容执行状态转换函数，该函数输出一个秘密，代表整个执行轨迹
- 该秘密作为种子，生成公私秘钥对
- 用私钥对节点ID进行签名，把签名结果和公钥一起发布，作为SPoCK
- 验证者必须再次根据交易执行状态转换函数，得到同一个秘密，并得到同一个SPoCK
验证SPoCK
观察者可以确认两个 SPoCK 都来自同一个。
4大角色
4大角色的交互关系：
- 每个角色都是独立抵押、取消抵押和罚没的。
- 单个硬件系统可以通过为每个角色单独放样来承载网络中的多个角色。
- 每个角色中诚实节点的质押股份总量必须占用全部质押股份的2/3以上。
主流程
收集节点: 收集交易
收集器节点被随机分成一组集群
- 特点
- 每个集群包含数量基本相同的收集器节点，误差最多1个
- 系统成熟后，一个集群包含20~80个收集器节点
- 每个epoch都会重新分配一次
- 分配步骤
- 通过分布式随机信标 (DRB) 协议生成一个随机源
- 从随机源派生一个种子
- 收集节点公钥列表， 对公钥列表进行洗牌
- 根据集群数量c和收集器节点数量，计算每个集群的收集节点数量k，并对集群编号
- 前 k 个收集器节点放到编号 0 的集群中，将第二个 k 个收集器节点放到编号 1 的集群中
客户端提交交易
- 交易数据如下
- ：交易的内容。
- ：支付交易费用账户签名。
- ：执行状态所有者的签名。
- ：前一个区块的哈希值，用于提供交易处理的截止日期。
- 对交易数据计算hash，并对集群总数取模，得到本交易需提交到的集群索引
- 用户代理将交易提交到指定集群的1个或多个收集器节点
收集器节点收到交易后，会广播该交易到该节点所在的集群的其他节点
- 收集器节点检查集群索引是否匹配，交易内容是否合法
- 收集器节点广播交易
- 集群内的收集器节点通过名为HotStuff的BFT共识将一批交易打包到一个集合中，叫做保证集合(guaranteed collection)
- 在每一轮共识中，被选中的领导者可以提出新的提议，也可以恢复上一轮未完成或超时的提议
- 提议可以是追加交易到集合中
- 提议也可以是新的空集合
- 其他节点进行投票
- 投票总数需超过节点数的2/3
- 投赞成票的条件
- 提议中的交易hash列表对应的交易都已收到
- 交易格式正确，并且至少有同一集群的一个收集器节点签名
- 列表中没有重复交易
- 交易不能是已打包过的历史交易
- 投票总数超过2/3后，领导者聚合投票签名
- 一旦集合大小达到协议的预定义阈值，领导者就提议关闭集合
- 形成保证集合
- 保证集合的格式
- CollectionHash 是封闭集合的哈希散列。
- ClusterIndex 是已经生成集合并达成共识并关闭它的集群的 id。
- AggregatedCollectorSigs 持有保证集合的收集器节点的聚合签名。
- 参数保证集合签名的节点称为担保人
- 担保人证明集合中的所有交易格式是正确的
- 担保人存储整个集合，包括所有交易的完整脚本
- 领导者将保证集合同步给所有担保人收集器节点，并持久化存储到本地
- 担保人收集器节点将保证集合的哈希引用发给所有共识节点
共识节点: 生成区块
- 共识节点通过名为HotStuff的BFT算法对下一个区块中包含的保证集合集达成一致
- BFT领导者提议一个原型区块ProtoBlock
- 原型区块格式
- previousBlockHash ：指向前一个哈希值。
- height：区块在链中的当前索引。
- guaranteedCollections ：新保证集合。
- blockSeals：先前区块的已验证执行结果的哈希承诺列表。
- slashingChallenges：已提交给共识节点进行裁决的新罚没挑战的列表。
- protocolStateUpdates：对作为执行此区块的结果的系统更新协议状态的密码学承诺。
- aggregatedConsensusSigs ：投票赞成该区块的共识节点的聚合签名。
- 如果没有可用的保证集合，提议一个空的保证集合的原型区块，其他字段正常
- 广播原型区块给其他所有共识节点
- 共识节点仅确认对保证集合中交易hash的顺序，并投票
- 投票的条件
- 领导者节点对原型区块的签名。
- 原型区块是基于最新高度的子块。
- 原型区块包含新的保证集合或为空。
- 投票节点已经收到了所有保证集合。
- 所有保证集合都经过身份验证。
- 投票节点已经收到了所有区块密封。
- 原型区块中所有区块封装是有效的。
- 投票节点已经收到并验证了 中的所有 罚没 挑战。
- 将原型区块中列出的协议状态基于父块的最终协议状态进行更新（由 pb.previousBlockHash 引用）。
- 如果所有这些条件都满足，则投票支持该原型区块
- 签名原型区块的hash，并广播给所有DRB节点
- 每个DRB节点等待收集其他签名，直到达到阈值数量，并从中恢复出随机源
- 创建包含随机源的区块
- 格式
- 广播该区块给所有执行节点
- 在原型区块基础上构建3个区块之后，该区块被最终确定
- 维护协议状态
- 一个节点的协议状态可能会因为 slashing、staking 和 unstaking 而改变
- 维护与节点权益相关的系统状态
- 每个纪元内都需要对下一个纪元的所有新质押请求作为交易提交
- 质押交易一般在下一纪元开始的前一天之前完成提交
- 执行结果封存时，共识节点会相应更新质押节点的协议状态
- 取消质押是在下一纪元生效
- 在至少一个纪元的等待期后，取消质押的股份才会返回到节点
- 接收和裁决罚没挑战
- 任何抵押节点都可以向另一个节点提交 slashing 挑战。
- 罚没故障节点
执行节点: 执行区块
- 收到共识节点广播的区块（可能包含多个保证集合）
- 从各个保证集合相关集群的收集器节点请求保证集合中的交易
- 集合非空：重建集合的哈希值以验证交易数据是否与保证集合一致，恢复所有保证集合
- 空集合：需要提供一个Missing Collection Attestation 证明
- 如果担保人不提供保证集合，则节点可以向担保人发出 Missing Collection Challenge。挑战直接提交给共识节点
- 确定交易顺序
- 从执行节点本身或另一个执行节点获得该区块的前一个区块的执行结果
- 根据最终区块中的规范顺序执行交易
- 执行交易
- 执行输入
- 系统当前执行状态
- 交易文本
- 执行输出
- 执行结果状态
- 计算消耗
- 计算机密知识的专门证明SPoCK
- 证明执行节点确实执行了计算，也可以防止验证节点不验证直接批准
- 根据交易的计算消耗对区块的交易执行平均分成一组分块(chunks)
- 使验证节点能够独立并行地检查分块的执行
- 防止恶意执行节点通过将计算错误注入计算量大的分块来攻击系统的完整性
- 每笔交易执行完后，检查当前分块的总计算消耗是否会超过阈值
- 如果加上本交易的消耗后未达到阈值，那么该交易加入当前分块，并更新该分块的SPoCK
- 如果超过分块的阈值，关闭当前分块，该交易作为下一分块的第一个交易
- 为分块的起始状态生成一个可验证的哈希承诺
- 创建一个新的chunk结构，附加到chunks中
- 把SPoCK附加到Zs中
- 执行完最后一个交易之后，需要关闭最后一个分块
- 交易全部执行完之后，为区块构建执行收据，即对区块执行结果的加密承诺
- 执行收据数据格式
- executorSig：执行节点的签名
- executionResult：执行结果数据格式
- ZsZsZs：一个给验证通过节点使用的SPoCK 密码学承诺列表
- 每个分块都有一个SPoCK 的执行跟踪承诺
- 执行结果数据格式
- blockHash：区块哈希
- previousExecutionResultHash：对上一个计算执行结果的哈希引用
- finalState：执行这个区块后对系统最终执行状态的承诺
- chunks：一个或多个分块信息
- chunks.startStateCommitment：分块执行前对系统执行状态的哈希承诺。
- chunks.startingTransactionCC：分块的第一个交易的计算消耗。
- chunks.startingTransactionIndex：分块的第一个交易的索引。
- chunks.computationConsumption：分块的整体计算消耗。
- 将执行收据广播给验证节点和共识节点
验证节点: 验证执行结果
- 可以配置每个验证节点需要验证的分块数量
- 假设有10个验证节点，1个区块有10个分块，1个验证节点至少需要验证1个分块。如果一个验证节点验证3个分块，那么这个区块将被验证3次。
- 从区块中选择要验证的分块
- 用自己的私钥对区块的执行结果进行签名
- 签名结果作为随机数生成器的种子
- 通过洗牌算法（输入种子），从分块列表中采样选出指定数量的分块
- 洗牌算法是可验证的， 只要种子一样，结果肯定一样
- 洗牌算法在不知道私钥情况下， 结果是不可预测（私钥→签名→种子）
- 洗牌算法保证洗的足够均匀
- 每个节点独立采样，无论先后，采样结果都一样
- 从执行节点请求重新计算它正在检查的分块所需的信息
- 从收集器节点请求交易数据
- 从执行节点请求状态数据
- 为该分块发布结果批准(ResultApproval)
- 遍历交易并执行，累计计算消耗
- 检查计算消耗是否正确
- 检查执行结果状态是否正确
- 构造验证结果的证明和批准
- ResultApproval.attestation：证明 ExecutionResult 的正确性
- CorrectnessAttestation.executionResultHash：执行结果的哈希
- CorrectnessAttestation.AttestationSig：对执行结果哈希的签名
- ResultApproval.verificationProof：证明验证节点完成了分配的验证任务
- ：指定验证者选择的分块索引列表
- ：执行收据中执行结果的签名
- ：包含每个分配的分块的验证证明。形式上，对于每个 ，持有一个分块的计算证明SPoCK
- 将结果批准(ResultApproval)广播给共识节点
共识节点: 封存区块
- 共识节点在收到绝大多数验证者节点批准结果并且没有收到 FaultyComputationChallenge 提交，开始封存 ExecutionResult
- 区块封存数据结构
- blockHash：被密封区块的哈希
- executorSigs：执行节点对执行收据的聚合签名
- attestationSigs：验证节点对执行收据批准的聚合签名
