区块链上的交易证明

作者: 南边的小麦 | 来源:发表于2020-06-07 22:24 被阅读0次

一秒钟回顾区块链特征

经过这几年的快速发展，区块链已经是家喻户晓的技术和应用了，结合分布式网络、共识机制和密码学三大核心技术，区块链通过链式记账的方式（此处不考虑DAG结构的区块链架构），构建了一个不可篡改的分布式账本。

image.png

区块链所谓不可篡改，本质上是因为基于哈希连接的区块链账本，分布在网络中各个节点，想要单方面篡改某个历史状态，需要获得足够多节点的认可，而这需要很大成本，例如要超过50%的算力，或者要联合大多数节点协助作恶。

平民使用区块链的断舍离

众所周知，区块链有公有链和联盟链之分，公有链的应用依托数字货币，最大的场景还是资产转移和交换，联盟链则在金融、政务、溯源等众多场景有广泛应用。那么，从C端用户的角度，尤其是作为一个平民百姓，是如何使用区块链的呢？

在公有链领域，用户接触最多的是交易所和钱包，通过这两个东西进行资产的保管和交易。在联盟链领域，用户一般是通过B端提供的客户端来访问区块链服务，例如APP或者小程序等。

不管是公有链还是联盟链，目前这种用户体验设计，都是有原因的。这里面涉及一个很重要的设计哲学——「安全」与「便捷」的博弈权衡。

image.png

从安全角度来讲，需要拥有全量的区块链账本，即所谓的全节点（Full Node）才能进行完整的安全确认。但是全节点需要占用大量资源，包括计算、网络以及存储开销，特别是存储开销，全量账本的大小是几百GB、TB级别的，而且还在持续增长。对于普通平民用户，他们的终端设备无法承载如此巨大的开销，他们的技术能力不足以维护全节点，甚至不足以管理私钥，他们需要足够便捷的用户体验。

为了得到足够便捷的体验，自然而然发展出“托管”服务，把一切复杂的任务托管给第三方。托管服务以牺牲安全保障来换取体验的便捷，它斩断了用户对账本的全量存储，舍弃了用户对私钥的绝对管控，背离了用户对交易的安全确认。

于是，用户把资产托管给交易所，把私钥托管给钱包，把信任托管给APP…

然后，我们不断看到，某某交易所被盗，某某钱包被黑，用户数以亿计资产惨遭损失…

鱼和熊掌是否可以兼得

追求安全，就需要付出资源消耗的巨大代价，追求便捷，就需要牺牲用户的核心利益，难道安全与便捷是鱼和熊掌不可兼得？

答案与否，我们尚未可知。但是业界从来没有放弃过追求鱼和熊掌兼得，我们来看看有哪方面的尝试。

（1）轻节点

首先要从「创始块」——中本聪的论文说起，他在文中提到SPV（Simplified Payment Verification），SPV借助Merkle Proof机制，只需要保存最长区块链的所有块头的情况下，就能够验证对一笔支付交易是否在存在。相比较于全节点，实现SPV的客户端称为轻节点（Light Node）。

image.png

轻节点可以实现安全的交易确认，而且还大大减小了存储开销，看起来是实现了鱼和熊掌兼得的效果。然而事实并非如此，区块头的存储也是不小的负担，例如以太坊历史块头已经超过4GB（块高9638224），而且还在持续增长，不适合让普通平民设备承载如此负重。

在安全与便捷的天平两端，轻节点侧重于安全。

（2）超轻节点

轻节点需要保存历史所有区块头，存储开销和块高成线性关系，随着区块不断增加，存储压力线性增加。熟悉算法复杂度的同学应该很清楚，线性复杂度大于对数复杂度，对数复杂度大于常量复杂度。

image.png

轻节点是O(N)复杂度，安全但是不够便捷，「托管」模式大部分是O(1)复杂度，便捷但不够安全。寻求安全与便捷的最佳平衡，从工程角度，很容易想到要往O(logN)算法方向优化，而从「线性」往「对数」优化的常规路径就是从「列表」的数据结构往「树」的数据结构转移，这就是所谓的「套路」。

O(N)复杂度的轻节点拥有所有区块头，很容易验证最长链是哪个，但如果是O(logN)复杂度的情况，由于缺乏从创世块到最新块的完整链路，如何识别最长链是一个难题。因此在设计比轻节点更轻的超轻节点时面临最重要的问题就是「如何确保超轻节点可靠识别出最长链」。

超轻节点的基本模型是这样的，超轻节点V连接了多个全节点P，其中至少有一个是非作恶的全节点，V向P请求验证「某个交易是否真实存在链上」，P返回相关证明，V根据P返回结果做判断。判断的第一步是确定非作恶全节点，第二步是根据该节点返回的数据验证「某个交易是否真实存在链上」。

image.png

基于这个套路，2018年出现了NiPoPOW，2019年出现了FlyClient，下面我们简要介绍一下这两种技术。

（3）NiPoPOW

NiPoPOW的全称是Non-Interactive Proofs of Proof-Of-Work，是一种非交互式的工作量证明的证明机制。POW是证明记账者付出了一定工作量的证明，NiPoPOW是对POW的证明，可以简单理解为是对历史所有工作量的证明。顾名思义，NiPoPOW只对采用POW共识机制的区块链有效。

运行POW寻找Nonce时，如果找到前n位为0的Nonce概率为p，那么找到前n+1位为0的Nonce概率为p/2，找到前n+2位为0的Nonce概率为p/4，以此类推，每次概率减半。NiPoPOW基于这个原理，将区块按照Nonce规律进行分层处理，通过interlink连接不同层的父区块，如下图所示。

image.png

在NiPoPOW中，P是如何为V构造证明的呢？论文有详尽的证明和算法介绍，此处摘取最核心的两幅图来简要说明其原理。

image.png

证明内容的第一部分是「证明我是最长链」，根据安全系数（m，k），结合Nonce分布原理，从interlink中构造出当前链的POW证明。从最高层开始往下递归，每层选出最新的m个区块，然后再拼接最新的k个区块，构成证明所需的子链。如上图m=k=3，蓝色标记的区块为证明所需的区块。这一步实现从「线性」复杂度降低到「对数」复杂度。

image.png

证明内容的第二部分是「证明有个区块包含了该笔交易」，首先要找到该交易所在位置（区块），如果在第一步证明获取的区块中已经存在就直接跳过，不存在的话就采用跳表的方式（如上图）将包含该交易的区块囊括进来，然后就采用Merkle Proof机制为该交易构造存在于该区块的证明。

（4）FlyClient

与NiPoPOW中P向V构造「我是最长链」证明的机制不同，FlyClient采用V向P抽样从而发现「谁是作恶节点」，如果说NiPoPOW的方式是「正面进攻」，FlyClient则采用「后路包抄」的策略。

抽样的方式有多种，全局随机抽样是一种朴素的方式，它需要抽样较大数量才能达到一定精度，采用二分查找的抽样可以减少抽样数量，但是需要多轮交互，FlyClient没有采用这两种方法。

image.png

FlyClient采用的抽样方法如上图所示，先从整条链中随机抽取k个区块，然后在更新的一半子链中再抽样k个区块，如此循环直到剩余的子链长度小于k，所有抽样出来的区块集合构成验证集。在这种抽样方式下，一个作恶节点（有无效区块）被发现的概率为1-（（1+c）/2）^k，其中c为作恶节点算力占比（小于1）。论文中对抽样这块有详尽的证明，并且提出了优化的方法，感兴趣的可以阅读论文，此处不再赘述。

抽样只是第一步，得到抽样区块之后还需要快速识别区块的有效性，FlyClient采用MMR（Merkle Mountain Tree）来解决这个问题。MMR是一个比较有趣的数据结构，由Peter Todd提出。有别于Merkle Tree，MMR被设计成append only，数据插入之后不能再改变，支持动态插入。更多MMR的细节可以阅读参考资料「MMR解析」，限于篇幅，本文也不赘述。

image.png

FlyClient在区块头中增加了一个M_i字段记录MMR root，第n个区块头的M_n表示为前n-1个区块构成的MMR root。眼尖的读者看到这里应该已经知道，这是经典的从原来Prev-Hash构成的「列表」数据结构往「树」数据结构进行变换套路。有了MMR，FlyClient就可以快速判断任何一个区块与创世块是否在同一条链上，即可识别任何一个区块的有效性。

FlyClient比NiPoPOW晚一年提出来，解决了NiPoPOW无法解决的问题，体现出明显的优越性。FlyClient可以支持Nonce寻找难度变化的情况，不受「贿赂攻击」影响，证明数据相对较小，还可以扩展适用于POS等场景。因此，NiPoPOW虽然提出更早但落地较难，FlyClient的落地相对较多。

FlyClient采用概率抽样的策略，理论上讲是不具备绝对的安全保障，但是作恶成功的概率已经很低很低。密码学被广泛使用，背后依赖的计算困难问题，也不是绝对的安全。在限定的时代、场景、技术背景下，相对的安全是够用的。从这个角度来讲，FlyClient达到了安全和便捷的有效平衡。

还能比超轻更轻吗？

超轻节点实现O（logn）复杂度开销的情况下获得安全和便捷上的有效平衡，前面也提过O（1）复杂度的「托管」模式存在安全风险，那是不是真的就不存在安全且便捷的O（1）复杂度方案了呢？

把目光转向联盟链，我们发现大部分联盟链采用是类BFT的共识机制。在这种机制下，每个区块会记录参与该区块的共识者的签名，因为签名的不可抵赖性，通过验证签名可以确定该区块是由谁共识产生，区块的有效性由参与共识节点的签名来保证。在这种模式下，只需要拿到区块头和区块的共识签名列表（区块头中一般包含了共识公钥列表），就可以快速验证区块的有效性。因此，在这类场景中就存在安全的O（1）复杂度算法。

当然，类BFT的共识机制下实现这种安全算法也不是非常容易的，考虑到参与共识节点通常会变化、轮换等，如果精准识别这些变化，保证区块检测算法的输入准确性，也是设计中要重点考虑的。