嵌套股份授权证明机制（NDPoS）

梦里梦外; 2022-05-25 14:27 129阅读 0赞

*摘要：物联网区块链的超流体架构，主要包含几大特性：一、NDPOS共识算法；二、非对称账本结构；三、点对点加密通讯。*

*其中，NDPoS主要解决在多链架构中，如何在区块链体系中保证跨链原子交易操作的实时性与可靠性；非对称账本结构则解决所有账本数据相同所带来大量无效存储、数据冗余、与带宽占用的问题；而点对点加密通讯则聚焦在物联网设备间通讯时的安全可靠机制。  
本文从NDPoS共识算法的设计目的以及解决方案，描述了如何在区块链的跨链交易中保障多链之间原子操作的实时性与可靠性。*

## 前言 ##

近年来，随着区块链技术社区的不断增大，对于共识算法的研究也日益深入。从中本聪率先提出的PoW开始，人们对大规模分布式对等网络节点的数据一致性问题做出了深度思考和创新。

不论是PoW还是PoS，都可以被归结为同步共识算法的范畴。PoW与PoS的初衷都是通过某些机制定期在全部对等网络节点中，选举出一个“幸运儿”作为日志（即账务）的基准节点，并由该节点将自己记录的交易写入日志文件（账本）后发送给其他节点。这种机制将传统数据库的主从架构拓展到多节点对等结构（多活），整个集群能够保障写入账本并得到多方确认的账务强一致性。

但是，这种机制在集群网络中节点数量大幅度增加时会面临很多问题。例如，比特币平均十分钟出1MB数据块的频率使得整体吞吐量极为有限；而不论是增大数据块尺寸还是缩短出块时间，都会从带宽或分叉等多个层面引入更多更复杂的问题。

因此，除了通过利用一系列附加手段增强集群能力以外，另一种典型的思路就在于通过减少参与共识协议节点数量，以达到提升集群整体性能、吞吐量以及响应速度的需求。

## 股份授权证明机制（DPOS） ##

DPoS就是一种典型的架构。其通过账本间的投票选举出一定数量的代理账本，这些账本之间形成一个共识网络，而其他没有被选举出来的账本则通过与代理账本之间进行主从同步，从而满足减少共识节点参与量的需求。

![1][]

但是，不论任何形式的共识算法，其整个集群总体吞吐量依然受限于参与共识节点之间的网络带宽。例如，在一个典型公有网环境中，两台通用设备之间的上下行带宽往往最多达到5-10MB/s（百兆带宽），假设每条记录为100字节，则两节点参与共识的最小网络，其吞吐量受到物理限制不超过10MB/100/2=5万/s（由于需要发送账本与实时交易数据，所以需要两倍数据传输）。当参与共识的节点数量增加时，假设平均每个账本通过P2P协议与10个账本相连，则吞吐量基本不超过5千/s。

每秒数千笔的全网交易吞吐量对于私链甚至联盟链可能都是足够的，但是对于一个典型的公链来说则远远无法满足需求。因此，对基本任何公链项目来说，采用单链DPoS架构都是无法满足未来业务扩展需求的。

## 分片（Sharding） ##

而该问题的解决思路则在于分片。分片（Sharding）最早最通用的场景来源于分布式数据库，其前身叫做分区（Partitioning）。在引入DHT（分布式哈希表，一种一致性散列算法）后，每一个基本散列单位可以称作分片。

而在区块链的世界中，基本上分片与分区概念类似，也就是在构建多个独立的区块链基础上，使用某种机制将多个区块链之间的通讯打通，从而做到不同链之间的节点间相互通讯，从而提升整体全网整体吞吐量。

![2][]

正如同一个设计良好的数据库分区机制必须确保分区间通讯尽可能减小一样，区块链分片机制也必须确保从业务逻辑上尽可能减少分片与分片之间的通讯需求。

而当跨链间业务真正发生时，也必须存在一种可靠可信的机制，确保跨链通讯的交易能够保证其原子性与一致性。

## ACID ##

在传统关系型数据库中，任何成熟的商业数据库产品必须满足ACID的特性。

A（Atomic）：原子性，事务中所有操作必须全部成功或全部失败，不能成功一部分失败一部分；

C（Consistency）：一致性，数据读写必须强一致，不能出现写入成功但是查询不到，或者破坏主键外键一致性等问题；

I（Isolation）：隔离性，即同时发生的交易从交易结果来说互不影响。例如包含100元钱的账户在同一时间点从两地分别取走10元，最后账户结果应当为80元而非90元；

D（Durability）：持久性，任何确认完成的事务在任何情况下一定保持完成状态。即使由于数据库故障重启也不能丢失已经被确认完成的交易。

关系型数据库经过了30年的发展和大量的行业应用，当前业界几乎所有银行、金融机构、保险公司或证券公司的交易与结算业务必须基于ACID原则，同时从业务特性来说任何无法保证ACID原则的系统不应当被用来进行金融交易。

不同于数据库日志，区块链由于多活架构很难实现高效的全局锁，因此无法直接使用传统数据库事务日志结构进行事务控制。因此大部分的区块链项目在进行账本写入时，每一条事务记录即会包含交易来源也会包含交易对手和金额，而非传统数据库日志中将金额的增加与减少作为多条记录以事务的方式进行串联。

![3][]

区块链账本结构

![4][]

数据库日志结构

因此，区块链账本记录结构使其作为特定的事务模型，能够满足仅为虚拟货币交易设计的特殊场景中原子性的要求。而一致性则使用一些分叉解决的思路进行处理。

隔离性则可以使用UTXO结构（记录变更历史顺序而非最终结果）或递增nonce操作顺序号进行实现，以保证针对同一条记录的并发操作能够进行先后顺序识别，避免双花问题。

最后，不论比特币或以太坊，从单节点来看几乎都忽略了持久性机制，而是在链结构中采用默克尔树的方式支持对已有区块进行自检，从其他正常节点同步损坏区块的方式满足全局持久性（假设不会发生所有节点同时损坏的问题）。

因此，可以看到在单一区块链分片中，无论是以太坊还是比特币能够最基本地保障ACID，最低程度满足金融交易与结算的需求。

然而，单一区块链ACID的满足并不意味着跨链交易同样满足ACID，因此在多链环境中如何满足ACID，则是公链项目能否得到大规模应用的关键所在。

## 分片间原子操作 ##

从MPP数据库时代起，分区间原子操作就是所有技术团队力争解决的问题。从传统的二段提交与三段提交，到新型的Spanner架构，所有的分布式数据库都在苦苦尝试解决分区之间的原子操作问题。

为什么分区间原子操作极难解决？在MPP数据库体系中，每个分区之间逻辑上完全独立，分区间各自的度量指标完全不同，从时间戳到锁机制完全互相独立，使得来自不同分区的进程在执行原子操作时无法拥有统一的参照物。

因此，解决分区间原子操作的唯一策略便是指定一种参照物，使得多个节点可以统一进行协调。

例如，二段提交与三段提交的机制便是引入了协调者。这种机制在数据库领域统称XA，其原理即通过协调者发起原子操作后，由协调者判断跨越多个分区的事务应当最终成功提交，或者中途回退。其具体机制读者可以参见相关文章。

而Google的Spanner架构则需要通过特殊硬件（原子钟）来统一并协调各个节点间时间戳，结合提交操作所记录的全局时间戳来判断各个分区内记录的提交回滚状态。

## NDPoS ##

如前文所述，区块链尝试将一个原子操作中的多个账户的修改，通过日志（账本流水）的方式归并到单一事务操作记录中，同时通过默克尔树的形式保证日志文件的正确性，从而确保在无锁状态下的多账户原子操作。

而NDPoS的核心机制即将多个链之间的原子操作，以一个逻辑上更加高层的链进行抽象，在高层逻辑链中同样使用DPoS算法保障每个成员之间操作的原子性。而高层逻辑链中的成员同时也是真正每个分区链中的一个或多个代理节点，该节点将在高层逻辑链中所达成的共识，筛选出自身所在链中包含的变更数据，作为一条原子操作在链内执行，从而达到跨链间原子操作的目的。

在NDPoS结构中，每一条链中的账本分为代理节点与跟随节点两种角色。其中代理节点负责小范围内的共识协商，而协商结果则通知跟随节点进行记账。当存在嵌套结构时，底层链中的代理节点作为上层虚拟链中的普通记账节点进行投票选举，其中一些节点作为上层虚拟链中的代理节点进行链之间通讯的共识与协商。因此，任何一个账本节点可以同时存在一种或多种状态。其可以作为独立的跟随节点，或者作为底层链的代理节点与上层虚拟链的跟随节点，或作为底层链的代理节点与上层虚拟链的代理节点。

当网络存在三层或更多层嵌套架构时，每个账本节点可能同时拥有若干种角色。

以一个三方交易为例，假设存在于三个分片链的X、Y、Z记录之间进行转账交易，其中记录X来自分片A；记录Y来自分片B；记录Z来自分片C。

![5][]

可以看到，分片链A、B、C之间完全独立，而每个分片的投票节点内存在一个或多个代理节点，构成分片链之间的一个虚拟链。在这个虚拟链中所有节点同样使用DPoS机制进行共识。

当存在一个由X向Y、同时Y向Z转账的交易时，首先该交易由X所在的分片发起。

[![6][]][6]

此时收到转账操作的账本节点根据DPoS规则将操作转发给代理节点进行共识，代理节点如果发现交易中任何记录为跨分片操作，则将该操作转发给上层虚拟链中的代理节点进行跨链共识。

[![7][]][7]

在跨链共识的过程当中，发起分片的代理节点同样依照DPoS原理，在上层虚拟链中将交易转发给上层虚拟链中的上层代理节点，而上层代理节点则首先在上层虚拟链中发起一次共识。

![8][]

上层虚拟链中的协调节点达成共识后，会在上层虚拟链中按照DPoS原则通知上层虚拟链中的其他跟随节点，即分片链中的普通代理节点。

[![9][]][9]

之后在每个分片链中则按照各自的DPoS规则向自身的跟随节点广播，从而达到跨链间共识。

可以看到，NDPoS的核心思想在于先在顶层虚拟链中达成共识，然后将结果传达给底层分片链。当存在超过两层虚拟链时，该模式以递归的方式由顶层向下传递。

举例来说，该模式比较类似于公司管理体系中，将部门作为基础单位，首先在每个部门中选举出管理层代表部门员工进行决策。而这些部门级管理层同时又是事业部代表，其中选举出若干事业部级管理层参与该事业部的决策，并将决策结果通知其他事业部代表（也就是该事业部中所有部门管理层）。而事业部级管理层同时又是分公司代表，其中选举出若干人作为分公司级管理层进行决策……以此类推。在该模式下，一个参与者可以同时为分公司管理层、事业部管理层与部门管理层，或可以为事业部代表与部门管理层。

当发生业务交涉时，如果交涉的多方均处于同一个部门中，则所有协商仅需在部门内部管理层中达成共识即可。而如果需要协商的双方处于同一个事业部的不同部门，则所有的协商需要在事业部管理层团队之间进行，协商结果则通知受到影响的若干部门即可。而如果协商的多方位于分公司的不同事业部下的部门之间，则首先决策必须在分公司管理团队之间做出，然后通知各自的事业部，由事业部通知底层部门执行。

## 选举策略 ##

选举策略可以根据各个项目自身的业务特点实现，但是其核心必须保证每个底层链一定存在一个或以上的代理节点作为上层虚拟链的节点参与跨链共识，否则涉及到该底链的通讯无法被传达到该链中其他跟随节点。

因此，每次上层虚拟链共识发生时，必须首先计算数据块所涉及的全部底链是否存在至少一个成员，而共识的发起者必须在得到超2/3的成员赞同（以BPFT举例），且该数据块所涉及的全部底链中，每个底链的代理节点间均达成赞同共识后，才能认为本次共识成功。

在NDPoS多层架构中，其总账本支持数量与吞吐量随着层数的增多可无限弹性扩张。例如，假设一个典型的单链DPoS最大账本支持数量为10,000，代理账本数量为101，单链设计理想吞吐量为5000/s，那么两层结构则可以支持约10,000\*(10,000/101)~=1,000,000节点，理论理想吞吐量则为5,000\*(10000/101)~=500,000/s。而三层结构则可以达到10,000\*(10,000/101)^2~=1,000,000,000节点，理论理想吞吐量为5,000\*(10000/101)^2~=500,000,000/s。

## 跨链查询与检索 ##

与任何分布式数据库的分片机制类似，NDPoS的分片机制基于DHT模式，根据分区键的散列值进行切分。在这种模式下，指定分区键的精确查询操作性能极高，同时一般来说针对均匀分布的分区键能够做到整个集群的数据均匀分布。但是，如果查询条件中并不包含分区键，查询必须向所有分片中进行广播以得到全部分区中符合条件的记录。

因此，NDPoS所基于的DHT分片算法必须得到优化，以满足非主键查询检索的实时高效。

一个较为简单直观的方式即引入全局索引的概念。在分布式数据库的领域中，所谓全局索引即一个二级索引，但是该索引的分区键使用索引键，而非表分区键。在这种模式中，用户可以使用散列分区或范围分区对索引键字段进行分区，使查询者能够在仅访问有限数量分区的前提下得到符合查询条件的记录。

但这种模式的一大弊端则在于一致性。由于全局索引的分区键与数据表分区键不同，一条记录所对应的索引往往并不在一个分片中，因此强一致全局索引的引入往往会带来大量的分布式事务开销，因此一般来说不会被传统数据库所大规模采用。

但是，对于一些满足最终一致性的场景来说，使用非强一致的全局索引往往能够得到意想不到的效果。NDPoS的核心本质在于对主数据以DHT分片的方式进行切分，但是可以针对需要检索的其他属性建立最终一致性全局索引。

这种机制对于每个账本节点需要实现数据库“表”与“索引”等类似的机制，将不同业务属性的数据分别存放。

## 总结 ##

NDPoS在DPoS的基础之上满足了准实时跨分片的强一致性数据通讯。不同于DAG结构对交易确认时间无法预测的最终一致性，NDPoS通过区块链的对等多活机制，提供了跨链间交易的强一致性。同时，NDPoS通过分层代理的机制，实现了整个网络分片数量的无限弹性扩张，从根本上解决了单链账本数量无法过多的性能与扩展性问题。

原文链接：http://www.8btc.com/2345688

[1]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090617561196.png
[2]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618046693.png
[3]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618109438.png
[4]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618156469.png
[5]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618194046.png
[6]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618247186.png
[7]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618291102.png
[8]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618344002.png
[9]: http://cdn.8btc.com/wp-content/uploads/2018/03/201803090618394225.png