Harmoney

[TOC]

概述

Harmony包含一个信标链和多个分片链。信标链充当随机信标和身份寄存器，而分片链存储单独的区块链状态并同时处理交易。Harmony通过结合可验证随机函数（VRF）和可验证延迟函数（VDF）提出了一种有效的随机性生成算法。Harmony还在分片过程中加入了PoS，这将分片的安全性考虑从最小节点数更改为最小投票份额数。

DRG（分布式随机生成）

融合VRF和VDF

Algorand利用基于VRF（可验证随机函数）的加密分类来选择共识验证组；以太坊2.0提出VDF（可验证延迟函数）用于延迟实际随机数的揭示，防止最后揭示者的攻击--这个总结不错

协议步骤：

1. leader发送带上一个区块链的哈希值的初始化信息给所有验证节点
2. 验证者受到初始化信息，使用VRF生成随机数r和证明p，(r, p) = VRF(ski, H(B<sub>n−1</sub>, v),v为当前视图，验证者将(r,p)发送给leader
3. 验证者受到至少f+1个有效的随机数后，对所有随机数做XOR运算得到最终的随机数pRND的preimage原像
4. 领导者允许BFT在所有验证者节点达成对pRND的共识，完成提交至B<sub>n</sub>
5. pRnd成功提交后，leader运行VDF计算当前actual随机数Rnd = VDF (pRnd, T )，随机数将会延迟k个区块计算出
6. Rnd被计算出后，leader发起BFT验证Rnd，最终提交上B<sub>n+k</sub>

分片方式

分片链和信标链

分片链是处理和验证其自身交易并存储其自身状态的区块链。分片仅处理与其自身相关的交易。尽管分片链相对独立，但是它将通过跨分片通信与其他分片链通信。

跨片交易

主链驱动：zillqa，跨片交易依赖于主链驱动
客户端驱动：Omniledger，客户端驱动的跨分片事务处理机制，其中分片之间的消息由客户端收集并发送到分片
分片链驱动：RapidChain，分片之间的消息是由分片中的节点直接发送

Harmony采用分片驱动的方法，使用Kademlia路由协议将分片驱动的通信复杂性O（N）降低到O（log（N））。另外，将使用擦除码（erasure code）对正在通信的数据进行编码，以确保跨分片通信的鲁棒性。

信标链

信标链也是一条分片链，除了执行分片链的处理交易的功能外，另外还负责生成随机数额接受stakes,意味着信标链是stakers将其令牌存入成为验证节点的链。

信标链通过包含每个分片链中的块头来帮助增强分片链状态的安全性和一致性。具体来说，在将新块提交到分片链之后，其块头将（通过基于Kademlia的分片间通信）发送到信标链。信标链上已提交的块头将被广播到整个网络，每个分片都会为所有其他分片保留一串有效的块头，这将用于检查来自其他分片的交易的有效性（即简单的付款验证SPV）。

1. 增加了攻击单个碎片的难度。
2. 减少在分片之间广播块头的网络成本。 如果我们让每个分片分别广播其标头，则将进行O（N²）网络通信。以信标链作为中央中继，复杂度降低为O（N）。

保证一致性

• 原子锁定机制确保跨分片交易的一致性

• 采用Kademlia路由实现跨分片交易

状态分片

• 账户模型
• 一个用户帐户可以在不同的分片上拥有多个余额
• 用户帐户可以通过发出跨分片交易在分片之间移动其余额
• 合约账户限制在创建合约的那个分片，同时开发者可以在其他分片上创建多个实例，实例间不共享状态但是可以通过跨片通信进行交流

POS入口

— 基于staking的分片方式

harmony的验证者注册是通过POS入口防女巫攻击（zilliqa和quarkchain是通过POW），即成为验证者节点需要质押代币，投入的代币数量决定验证者的投票份额

Resharding

网络加速方案

基于Kademlia的路由方案

kademlia算法

​ kad算法是DHT的一种实现。kad算法给每个节点分配了一个节点id，根据节点id之间的异或距离建立路由表。给资源设置了一个key，根据key与节点id的异或距离查找资源。

• 节点维护的信息

  • 储存的资源，key-value对，文件名-文件

  • 路由表–K桶

    • 概念:对于位于[0,160) 中的每个 i ，每个节点都保存有一些 <IP地址， UDP 端口，节点 ID>三元组列表，三元组中的节点 ID 为那些和其距离位于 2 ⁱ 和 2 ⁱ⁺¹ 之间的节点的 ID

      K是一个平衡系统性能和网络负载的参数，设定一个三元组列表的最大容量为k，保证网络中k个节点同时失效的可能性很小

    • k桶内节点排序：每个 k-bucket 都按照节点最近联系时间排序——最近未联系的节点放在表头，最近联系的节点放在表尾

    • K桶的生成

      • 主要是根据于节点的XOR距离，距离位于 2 ⁱ 和 2 ⁱ⁺¹ 之间的节点在同一个k桶
      • 在i较小时，可能k桶是空的，节点数目比较小

      • 当i比较大时，此时可能节点数目会超过k。当节点接收到任何节点信息时，会进行k桶的更新：1. 如果节点已经存在k桶内，则将节点移到k桶尾部；

        1. 如果节点不再k桶内，当k桶未满时，则将其加入到k桶尾部

           1. 如果节点不再k桶内，当k桶已满时，则节点ping k桶表头节点（最近未联系），如果ping通则将该表头节点移至表尾并抛弃发送者节点的联系信息，否则舍弃表头节点并将发送者节点加入到表尾

    

• XOR 度量

  • 两节点间距离是 nodeid1 $\bigoplus$ nodeid2

• Kademlia协议

  • 4 个 RPCs
    • PING
      • 探测节点是否在线
    • STORE
      • 节点存储一个 <key ,value> 对
    • FIND_NODE
      • 输入参数为一个160位的节点ID
      • 输出距离目标 ID 最近的 k 个节点的三元组<IP地址， UDP 端口，节点 ID> 列表
    • FIND_VALUE
      • 输入参数为一个160位的keyID
      • 输出和find_node是一样的，当请求者存有对应key时发回value

• 路由算法

  1. 发起者计算自身到目标节点（T)的异或距离cpl,根据cpl找到对应的k桶,再从该k桶中寻找与L具有最长公共前缀的K个节点（cpl最小），然后对这些节点 发起查询请求
  2. X节点收到查询请求，从自身查找并返回距离T更近的K个节点给发起者，如果是自身则返回自身
  3. 节点发起者收到响应后再次对着K个节点发起查询请求，重复2

  最终查询结果是收到一批距离目标节点很近的节点列表

使用擦除码加速广播

使用RaptorQ fountain code替代源Reed-Solomon 擦除码来改善IDA的坚固性

快速状态同步

验证者加入新的分片时，他们将需要快速同步到分片的当前状态，以验证新交易。

• 新块加入时先下载当前分片的当前共识周期的状态信息，方便立刻验证交易

• 然后下载历史的区块头并通过检查签名验证区块头，只要能通过加密路径（hash pointers and signatures）溯源到创世区块则状态可信

• hash pointer：每一个epoch的第一个区块会有一个hash pointer指向上一个epoch的第一个区块，这样可以节省时间 — why接下来n个区块内有效

• 避免重放攻击并且节省状态空间：设定一个数n,在一个交易只在

FBFT共识

F指Fast，主要技术：

• Schnorr多签
  • 相比PBFT，不再通过询问验证节点签名，通信复杂度扩展，每个验证者只需接收一个多重签名，将通信的复杂度从O(n^2)减少到O(n)
• RaptorQ fountain code
  • 加速块广播
• FBFT步骤
  • 1. leader广播新块给验证者，通过RaptorQ fountain code – announce
    2. 验证者验证新块块头然后通过BLS进行签名，返回签名给leader
    3. leader收到超过2f+1个有效签名后，讲签名聚集成BLS多签，广播BLS多签和位图指示（已签名的验证者列表），第三步和第二步合称 prepare
    4. 验证者检查多签是否有至少2f+1个验证者然后签名，返回签名给leader
    5. leader收到超过2f+1份签名，生成BLS多签，同样打包一个位图进新块，提交新块并广播 – broadcast

Harmony的验证者是根据权益证明选举出来的。在某种意义上，具有更多投票份额的验证者具有比其他人更多的投票权，而不是单签名一票的投票权。因此，领导者不等待验证者的至少2f +1个签名，而是等待集体拥有至少2f +1个投票份额的验证者的签名。

Reference

Kademlia：A Peer-to-peer Information System Based on XOR Metric

Kademlia协议的一些具体算法

[Kademlia协议的一个实现]