区块链——OmniLedger算法介绍

OmniLedger目标是实现区块链设计中的不可能三角的平衡，是基于分片设计的区块链：

本文详细描述OmniLedger的设计细节以及介绍实验数据。

1）OmniLedger整体架构

OmniLedger由一条身份链（identity blockchain）以及多条子链（shard）构成。OmniLedger使用RandHound协议，将所有的Validator分成不同组，并随机的将这些组分配到不同的分片子链，验证以及共识区块（如上图中的（1）Sharding）。OmniLedger的总体架构以及设计的重点如下图：

ByzCoinX是OmniLedger在ByzCoin基础上的增强。每个分片子链使用PBFT共识算法形成共识，OmniLedger将这个共识算法取名ByzCoinX（如上图的（2）Consensus）。OmniLedger使用UXTO的账户模型，对于跨子链的交易，OmniLedger设计了Atomix的跨链原子操作，如上图中的（3）TX Commit。

2）Validator的随机分组和分配

RandHound协议实现Validator的随机分组。假设，总共m个Valiator，n个分片，RandHound协议将m个Validator随机分配到n个分片。每个区块生成前，所有的Validator都需要重新分组。注意，RandHound协议需要一个Leader”。OmniLedger算法使用VRF算法确定Leader。在每个区块生成前，所有Validator都需要在identity blockchain上注册。每个Validator使用VRF计算自己的Ticket，计算方法如下图：

其中config是注册在identity blockchain上的所有Validator的信息，v是当前的轮数。对于同一高度的区块，可能需要多轮共识才能确定。

在一定时间内，所有Validator交换Ticket。Ticket值最小的Validator作为当前的Leader。在确定了Leader”的基础上，RandHound协议实现所有Validator的分组，并将这些Validator划分到不同的分片上。

3） Atomix跨 链原子操作

为了支持分片间的交易，Omniledger设计了Atomix的跨链协议- Byzazantine ShardAtomic Commit。Omnil edger使用UTXO的账户模型。Atomix 协议的大体流程如下图：

1） Initialize 初始化阶段-假设用户从shard1以及shard2 （输入）转账到shard3 （输出），用户向shard1以及shard2发送跨链请求。

2） Lock 锁定阶段- shard1以及shard2锁定请求，确认交易合法，并在shard1以及shard2记录下锁定状态以及合法交易在区块中的Merkle路径证明。

3a） Unlock to Commit阶段-提交跨链确认请求，用户向shared3提交commit交易（包括所有输入的证明），完成跨链交易。

3b） Unlock to Abort阶段-如果在步骤2中，交易不合法（比如shard2中的交 易不合法），则跨链交易需要回滚，用户向shard1发送跨链交易取消。

这样的跨链设计，需要各个分片监控”其他分片的区块生成情况。

4） Trust-but-Verify分 层验证体系

为了更快速的处理大量的小额交易，OmiLedger提出了先信任后验证'的分层处理机制，如下图：

先信任后验证”的体系，包括了两部分共识： 1）分片共识2）分片区块合并。分片共识可以采用较少的Validator,加快分片的共识速度以及区块的确认速度。分片形成的区块，会被较多的Validator进行再次验证。这样的设计在出块速度以及安全性之间形成平衡。

5）其他细节设计

论文中还提及了其他细节设计，比如区块镜像（Snapshot） 以及区块并行处理。在区块镜像前的一些信息可以删除从而较少存储的消耗。区块并行处理指的是，可以并行执行的交易打包在不同的区块中，这些区块可以同时共识生成。

6）实验数据

Omniledger论文中提到，为了验证实验数据，部署了60台机器，每台机器配置是：Intel E5-2420 v2 CPU，24GB内存以及万兆网络。实验数据表明：

TPS性能随着分片数量的增加线性增加，如果是16个分片的情况下，TPS达到5850。论文中甚至指出，25个分片的情况下，TPS达到13000。

总结： Omniledger是基于分片的区块链设计。OmniLedger使用 RoundHound和VRF协议将Validator随机的分配到不同的分片上。每个分片的共识采用PBFT算法。Omniledger能容忍不超过1/3的作恶节点。在实验室的环境下，TPS性能随着分片的数量线性增加，16个分片的情况，TPS达到5850，25个分片的情况，TPS达到13000。