区块链的数学层面认知

一、数学是科学之母

    牛顿通过数学计算预见了发射人造天体的可能性。

    爱因斯坦相对论的质能公式从数学论证的角度预示了原子能时代的来临。

    中本聪基于简单的应用数学原理发明了比特币

    不管人们如何评价区块链，区块链几乎成为数学与应用相结合最为密切的信息技术之一。

二、数学是区块链的DNA

    区块链包含了多种关键技术，但其底层都是数学，可以说数学是区块链的DNA。

三、哈希

    哈希（hash)函数、散列函数--密码学中的一种编码方法。

输入一个任意长度的字符x，输出一个固定长度的字符H(x)。

比特币采用SHA256，输出64位字符，由10个阿拉伯数字和6个英语字母(abcdef)组成。总量是16*64,=2*256

输入相同的字符，输出的哈希值必然相同

只要输入的字符有所改变，输出的哈希值就变了

无法根据输出的哈希值，推算输入的字符

    Hash函数也称为杂凑函数或散列函数，其输入为一可变长度x，返回一固定长度串y，该串被称为输入x的Hash值（消息摘要）要求给定一个Hash值，求其逆是比较难的，但给定的输入计算Hash值必须是很容易的，因此也称Hash函数为单向Hash函数。

密码学Hash函数是一个压缩函数Hashk:X->Y

Hashk(x)=y

Hash函数的安全要求：

单向性：已知y，找出x，使得Hashk(x)=y困难

弱碰撞：已知x，找出x’≠ x，使得Hashk(x’)=y困难

强碰撞：找出任意x’≠ x，使得Hashk(x’)=y困难

困难性具有递增关系：强碰撞必然是弱碰撞，弱碰撞必然单向性

四、非对称加密

    非对称加密是一种保证区块链安全的基础技术。该技术含有两个密钥：公钥和私钥，首先，系统按照某种密钥生成算法，将输入经过计算得出私钥，然后，采用另一个算法根据私钥生成公钥，公钥的生成过程不可逆。由于在现有的计算能力条件下难以通过公钥来穷举出私钥（即计算上不可行），因此可以认为是数据是安全的，从而能够保证区块链的数据安全。

    常用的非对称加密算法有：RSA、Elgamal、背包算法、Rabin、D-H、ECC（椭圆曲线加密算法）。

RSA算法：

公钥：PK=(e,N）

私钥：SK=(d,N)

其中，N=p*q（p、q是两个大素数）

e、N公开，d保密，e、d、N保持一定的关系，破译者想从e、N算出D是十分困难的。

    ECC算法：

    选择椭圆曲线E和生成元G 

    保证其DL问题是安全的

    用户选择私钥：整数 nA<n

    用户计算公钥：PA=[nA]G

    加密Pm : Cm={[k]G, Pm+[k]PA}, k随机整数

    解密Cm: (Pm+[k]PA)–[nA]([k]G) 

         = Pm+[k*nA]G–[nA*k]G= Pm

五、零知识证明

    零知识证明/ Zero-Knowledge Proof：证明者和验证者之间进行交互，证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

六、同态加密

    同态加密/

Homomorphic

Encryption：同态加密是一种特殊的加密方法，允许对密文根据特定的代数运算方式进行处理后得到的仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果是一样的。即“对密文直接进行处理”与“对明文进行处理后并加密”其结果是一样的，这项技术可以在加密的数据中进行诸如检索、比较等操作而无需对数据先进行解密，从根本上解决将数据委托给第三方时的保密问题。

七、盲签名、群签名、环签名、多重签名

盲签名：盲签名（blind signature）是在1982年由David Chaum在论文《Blind Signatures for Untraceable Payment》中提出。签名者需要在无法看到原始内容的前提下对信息进行签名。盲签名可以实现对所签名内容的保护，防止签名者看到原始内容；另一方面，盲签名还可以实现防止追踪（unlinkability），签名者无法将签名内容和签名结果进行对应。典型的实现包括RSA盲签名算法等。

群签名：群签名（group signature）即某个群组内一个成员可以代表群组进行匿名签名。签名可以验证来自于该群组，却无法准确追踪到签名的是哪个成员。群签名需要存在一个群管理员来添加新的群成员，因此存在群管理员可能追踪到签名成员身份的风险。群签名最早于1991年由David Chaum和Eugene van Heyst提出。

环签名：环签名（ring signature），由Rivest、Shamir和Tauman三位密码学家在2001年首次提出。环签名属于一种简化的群签名。签名者首先选定一个临时的签名者集合，集合中包括签名者自身。然后签名者利用自己的私钥和签名集合中其他人的公钥就可以独立地产生签名，而无需他人的帮助。签名者集合中的其他成员可能并不知道自己被包含在最终的签名中。环签名在保护匿名性方面有很多的用途。

多重签名：多重签名（multiple signature）即n个签名者中，收集到至少m个（n>=m>=1）的签名，即认为合法。其中，n是提供的公钥个数，m是需要匹配公钥的最少的签名个数。多重签名可以有效地被应用在多人投票共同决策的场景中。例如双方进行协商，第三方作为审核方。三方中任何两方达成一致即可完成协商。比特币交易中就支持多重签名，可以实现多个人共同管理某个账户的比特币交易。

八、链表结构

区块链由两种带密码机制的数据结构构成：

哈希链表：所有区块之间按照时间先后顺序链接而成一个完整的链条，被称为哈希链表。 通过该单向链条既可以逐渐增加区块，当一个新的区块创建后，就补充在最后 一个区块后面，同时该单向链表也可以回溯发生的所有的交易信息；

默克尔树：是对所有块内交易信息采用二叉树结构生成一个压缩后的密码学摘要（被称为本区块Hash值），将交易记录紧密的联系在一起。

    如图所示，区块链的这种存储方式提供了对交易数据“一致性检验”和“完整性验证”的支持。

九、交易结构

上一次交易的SHA256计算得到的Hash值被作为交易ID（TXID）

上一次交易的输入段存储“消费者”对TXID和“接收者”公钥Pubkey的签名

上一次交易的输入段存储“接收者”的公钥

下一次交易中的“消费者”就是上一次交易中的“接收者”

下一次交易中的“消费者”的签名由上一次交易中的“接收者”公钥Pubkey进行验证

每个区块链交易中包含两个段：

输入段：输入资产账单

输出段：输出资产账单

十、DAG（有向无环图）

传统区块链技术存在的几个问题：

效率问题：传统区块链技术基于Block区块，比特币的效率一直比较低，由于BlockChain链式的存储结构，整个网络同时只能有一条单链，基于POW共识机制出块无法并发执行；例如比特币每十分钟出一个块，6个出块才能确认，大约需要一个小时；以太坊大幅改善，出块速度也要十几秒。

确定性问题：比特币和以太坊存在51%算力攻击问题，基于POW共识的最大问题隐患，就是没有一个确定的不可更改的最终状态；如果某群体控制51%算力，并发起攻击，比特币体系一定会崩溃；考虑到现实世界中的矿工集团，以及正在快速发展量子计算机的逆天算力，这种危险现实存在。

中心化问题：基于区块的POW共识中，矿工一方面可以形成集中化的矿场集团，另一方面，获得打包交易权的矿工拥有巨大权力，可以选择哪些交易进入区块，哪些交易不被处理，甚至可以只打包符合自己利益的交易，这样的风险目前已经是事实存在。

能耗问题：由于传统区块链基于POW算力工作量证明，达成共识机制，比特币的挖矿能耗已经与阿根廷一个国家耗电量持平，IMF和多国政府对虚拟货币挖矿能源消耗持批评态度。

    有向无环图/Database

Availability Group / DAG：最早由Rootstock开发者Sergio Demian

Lerner于2015年9月发表的《DAGCoin

Draft》中提出，是计算机领域的常用数据存储结构。因为其独特的拓扑结构，DAG技术通常用于处理动态规划问题，比如在导航中寻找最短路径、数据压缩等场景。

传统区块链和DAG的区别：

单元：区块链组成单元是Block，DAG组成单元是TX（交易）； 

拓扑：区块链是由Block区块组成的单链，只能按出块时间同步依次写入，好像单核单线程CPU；DAG是由交易单元组成的网络，可以异步并发写入交易，好像多核多线程CPU；

粒度：区块链每个区块单元记录多个用户的多笔交易，DAG每个单元记录单个用户交易。

十一、UTXO VS ACCOUNT

UTXO

可扩展性 - 由于可以同时处理多个UTXO，因此可以实现并行事务并鼓励可伸缩性创新。

隐私 - 甚至比特币也不是一个完全匿名的系统，但只要用户为每笔交易使用新地址，UTXO就可以提供更高级别的隐私。 如果需要增强隐私性，可以考虑更复杂的方案，例如环签名。

ACCOUNT

简单性

- 以太坊选择了一种更直观的模式，以便为复杂智能合约的开发人员带来益处，尤其是那些需要国家信息或涉及多方的开发人员。

一个例子是一个智能合约，跟踪各国根据它们执行不同的任务。 UTXO的无状态模型会迫使交易包含状态信息，这不必要地使合约的设计复杂化。

效率 - 除了简单之外，账户/余额模型更加高效，因为每笔交易只需要验证发送账户是否有足够的余额来支付交易。

十二、共识机制

共识机制（Consensus Protocol）是指在多方协同环境下对任务执行结果所有方达成一致(共识)的机制。在区块链中引入共识机制则是为了解决新交易块加入哈希链表中可能出现的“块冲突”问题，也就是同时多个块被不同的块创建者加入到哈希链表中而引起的链表分叉（Forking）问题。

十三、POW共识机制、挖矿

设定目标数，找一个比目标数小的比较数

目标数和比较数均是一个64位的十六进制数

通过难度系数来调节目标数，使得全网平均10分钟找出这样一个比较数，生成一个区块链

将交易、时间戳、随机数等进行哈希运算得到比较数

计算能力越强的节点，找到这样一个比较数的概率越大

几乎同一时间内找到这样一个比较数的区块链，会导致区块链分叉，6个区块之后，有超过99%的概率基本能够确定主分叉

    优点：完全去中心化，节点自由进出；

    缺点：目前bitcoin已经吸引全球大部分的算力，其它再用Pow共识机制的区块链应用很难获得相同的算力来保障自身的安全；挖矿造成大量的资源浪费；共识达成的周期较长，不适合商业应用

十四、POS和DPOS

权益证明/ Proof of Stake / PoS：主要思想是节点记账权的获得难度与节点持有的权益成反比，相对于PoW，一定程度减少了数学运算带来的资源消耗，性能也得到了相应的提升，但依然是基于哈希运算竞争获取记账权的方式，可监管性弱。该共识机制容错性和PoW相同。它是Pow的一种升级共识机制，根据每个节点所占代币的比例和时间，等比例的降低挖矿难度，从而加快找随机数的速度。

优点：在一定程度上缩短了共识达成的时间；不再需要大量消耗能源挖矿。

缺点：还是需要挖矿，本质上没有解决商业应用的痛点；所有的确认都只是一个概率上的表达，而不是一个确定性的事情，理论上有可能存在其他攻击影响。例如，以太坊的DAO攻击事件造成以太坊硬分叉，而ETC由此事件出现，事实上证明了此次硬分叉的失败。

权益授权证明/ Delegated Proof of Stake / DPoS：DPoS 是一种类似董事会的授权共识机制，该机制让每一个持币人对整个系统的节点进行投票，决定哪些节点可以被信任并代理他们进行验证和记账，同时生成少量的对应奖励。每个股东按其持股比例拥有影响力，51%股东投票的结果将是不可逆且有约束力的。其挑战是通过及时而高效的方法达到51%批准。一般情况下，用户不会创建特别以投票为目的的交易，因为那将耗费他们一笔交易费。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一个新代表。

优点：大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。

缺点：整个共识机制还是依赖于代币，很多商业应用是不需要代币存在的。

十五、拜占庭将军问题

Generals = Computer Components

The abstract problem…

Each division of Byzantine army is directed by its own general. 

There are n Generals, some of which are traitors.

All armies are camped outside enemy castle, observing enemy.

Communicate with each other by messengers.

Requirements: 

G1: All loyal generals decide upon the same plan of action

G2: A small number of traitors cannot cause the loyal generals to adopt a bad plan

Note: We do not have to identify the traitors.

十六、PBFT（实用拜占庭容错）

    这是一种基于消息传递的一致性算法，算法经过三个阶段达成一致性，这些阶段可能因为失败而重复进行。

    假设节点总数为3f+1，f为拜占庭错误节点：

当节点发现leader作恶时，通过算法选举其他的replica为leader。

leader通过pre-prepare （第一个协议阶段）消息把它选择的 value广播给其他replica节点，其他的replica节点如果接受则发送 prepare（第二个协议阶段），如果失败则不发送。

一旦2f个节点接受prepare消息，则节点发送commit（第三个协议阶段）消息。

当2f+1个节点接受commit消息后，代表该value值被确定

如下图表示了4个节点，0为leader，同时节点3为fault节点，该节点不响应和发出任何消息。最终节点状态达到commited时，表示该轮共识成功达成。

注：预准备阶段（pre-prepare）：

主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息的格式为<<PRE-PREPARE,v,n,d>,m>，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。

准备阶段（prepare）：

如果备份节点i接受了预准备消息<<PRE-PREPARE,v,n,d>,m>，则进入准备阶段。在准备阶段的同时，该节点向所有副本节点发送准备消息<PREPARE,v,n,d,i>，并且将预准备消息和准备消息写入自己的消息日志。如果看预准备消息不顺眼，就什么都不做。

确认阶段（commit）：

当(m,v,n,i)条件为真的时候，副本i将<COMMIT,v,n,D(m),i>向其他副本节点广播，于是就进入了确认阶段。

    优点：共识效率高，可实现高频交易。

    缺点：当系统只剩下33%的节点运行时，系统会停止运行。

十七、dBFT（授权拜占庭容错）

    采用的dBFT机制，是由权益来选出记账人，然后记账人之间通过拜占庭容错算法来达成共识。

在PBFT基础上进行了以下改进：

将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式；

将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点；

为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节点（记账节点）；

在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。

优点：

专业化的记账人；

可以容忍任何类型的错误；

记账由多人协同完成，每一个区块都有最终性，不会分叉；

算法的可靠性有严格的数学证明；

缺点：

当有1/3或以上记账人停止工作后，系统将无法提供服务；

当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据；

    以上总结来说，dBFT机制最核心的一点，就是最大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。

十八、典型共识机制的比较 & 现存的主要问题

十九、P2P网络

    第一代混合式P2P网络：实际上是C/S模式与P2P思想结合的产物，由一台或多台服务器来记录节点索引表，网络中各节点从索引服务上查询目标节点的地址之后，直接与目标节点建立联系。

第二代无结构P2P网络：取消了索引服务器，各节点随机接入网络，地位相同，与邻居节点构成逻辑覆盖网络，通过邻居节点的接力来找到目标节点，并记录路径，防止环路。

第三代结构化P2P网络：为解决快速定位问题，采用DHT（Distributed Hash Table）技术来构建P2P网络，每个节点只需要记录有限节点信息，取消了洪泛算法，有效减少消息发送量，从而提高了目标节点的查找效率和准确性。

区块链网络服从小世界模型（Small World Model）网络。如图所示，该模型具有特征路径长度较小、聚合系数较大的特点，在这样的网络中，数据只需要经过较少的节点（6度原则）就可以达到目的节点。区块链网络拓扑的“高聚集度”和“短链”特征使得区块链可以支撑世界各地的海量用户进行大规模、并发的交易，及时地将交易数据通过记账节点实现区块的生成，并实现全网内的数据同步，为保证了区块链数据的健壮性、完整性和一致性奠定了安全运行的网络运行基础。

二十、链网结构

主链/ 主网/ Main net：通常区块链，尤其是公有链都有主网和测试网。主网是区块链社区公认的可信区块链网络，其交易信息被全体成员所认可。有效的区块在经过区块链网络的共识后会被追加到主网的区块账本中。

互联链/ InterChains：针对特定领域的应用可能会形成各自垂直领域的区块链，互联链就是一种通过跨链技术连接不同区块链的基础设施：包括数据结构和通信协议，其本身通常也是区块链。各种不同的区块链通过互联链互联互通并形成更大的区块链生态。与互联网一样，互联链的建立将形成区块链的全球网络。

侧链/ Side Chain：侧链是主链外的另一个区块链，锚定主链中的某一个节点，通过主链上的计算力来维护侧链的真实性，实现公共区块链上价值与其他账簿上价值在多个区块链间的转移。最具代表性的实现有Blockstream。这种主链和侧链协同的区块链架构中的主链有时也被称为母链（Parent chain）

二十一、跨链技术

    跨链技术是实现区块链之间互联互通的技术，若对标互联网则可理解为“去中心化网络的结合”，区块链技术的特性使得跨链技术的落地，以及对于链外信息的获取都非常困难，早期跨链技术包括以Interledger

Protocal 和BTC Relay 为代表，更多是关注资产的转移；现有跨链技术以Aion、Kyber

Network、Bletchley、Polkadot、Cosmos 主要着重的是跨链基础设施。

原子互换/ Atomic Swap：原子互换是一种正在开发中的去中心化、无需第三方的新技术，允许在不同类型的数字资产之间实现无需信任的点对点交易，任何一方在瞬间完成的点对点交易中都遵守协议，且之后若有一方退出，资金会在规定的时间返回各方账户。

见证人机制/ Notary Schemes：见证人模式是一种中心化的结构，通过选定一批见证人并在见证人之间采用拜占庭容错结构，监听目标链上的事件和状态并签名进行资产的转移，如Ripple 的Interledger Protocal 的早期版本。

侧链/ Side Chain：侧链是主链外的另一个区块链，锚定主链中的某一个节点，通过主链上的计算力来维护侧链的真实性，实现公共区块链上价值与其他账簿上价值在多个区块链间的转移。最具代表性的实现有Blockstream。这种主链和侧链协同的区块链架构中的主链有时也被称为母链（Parent chain）。

    侧链协议/ Sidechain Protocol：侧链协议是一种实现双向锚定（Two-way Peg）的协议，通过侧链协议实现资产在主链和其它链之间互相转换，或是以独立的、隔离系统的形式，降低核心区块链上发生交易的次数。

中继技术/ Relays：中继技术是通过在两个链中加入一个数据结构，使得两个链可以通过该数据结构进行数据交互，并通过在一个链上调用数据结构的API，实现监听并验证另一个链上的交易，而若该数据结构是一个链式结构，则具备侧链的形式并称作中继链。

哈希时间锁定合约/ Hashed TimeLock Contract / HTLC：哈希时间锁定合约包含哈希锁定（Hashlock）以及时间锁定（Timelock）两个部分，哈希时间锁定合约最典型的代表就是比特币的闪电网络，闪电网络提供一个可扩展的微支付通，用以提升链外的交易处理能力，使用哈希锁定将发起方的交易代币进行锁定，并通过时间锁定让接收方在某个约定的时刻前生成支付的密码学证明，并与先前约定的哈希值一致，则可完成交易。

二十二、扩容技术

分片/ Sharding：分片是区块容量的一种解决方案。通常情况下，每个节点和区块链网络都包含区块链的完整副本，分片是一种允许节点具有完整的区块链的部分副本的技术，以提高整体性能和稳定速度。

隔离见证/ Segregated Witness / SW：隔离见证是一种技术，通过把占用大量存储空间的区块的数字签名重新放置到不同的记录（也称为隔离），使每个区块能进行更多的交易，以达到扩容的目的。区块链上不仅记载了每笔转账的具体信息，还包括了每笔交易的数字签名以核实交易的合法性。矿工在打包区块的时候需要用数字签名来验证每笔交易，确认无误之后才会将该笔交易记录在区块里。但对于用户不需要验证信息，且每个比特币记录大小被限制在1 兆字节（MB），每10 分钟记录一次新的记录，所以通过隔离见证转移签名以扩大区块空间。

闪电网络/ Lightning Network：闪电网络是一种允许加密货币的交易即时发生和成本降低的技术，它使一般在比特币网络中需要等待区块确认的交易瞬间完成。闪电网络基于一个可扩展的微支付通道网络，通过序列到期可撤销合约RSMC，使交易双方在区块链上的预先设置的支付通道进行的多次高频的双向交易瞬间完成。同时，它通过哈希时间锁定合约HTLC 在没有直接点对点支付信道的交易双方之间连接一条由多个支付通道构成的支付路径，实现资金的转移。

雷电网络/ Raiden Network：雷电网络是一种以太坊链下扩容解决方案，它使得使用以太坊技术的加密货币能够即时和低成本交易。交易双方只要在链上存在交易信道，就能在链下根据被锁定的余额进行高频、双向的即时确认交易，将这样多个通道形成的支付路径构成“雷电网络”。

二十三、智能合约

    智能合约（SC：Smart

Contract）最初由尼克·萨博（Nick

Szabo）提出来，一个智能合约是一套以数字形式定义的承诺（promises），包括合约参与方可以在上面执行这些承诺的协议。一套承诺指的是合约参与方同意的（经常是相互的）权利和义务。这些承诺定义了合约的本质和目的。数字形式意味着合约不得不写入计算机可读的代码中，只要参与方达成协定，智能合约建立的权利和义务就由一台计算机或者计算机网络执行。本质上，智能合约就是一段实现合约逻辑的程序代码或者脚本，接受外界输入（I：input），按照既定规则（R：Rule），结合合约现有状态（S：State）进行处理（P：Process）之后，然后对外输出（O：output）。

    智能合约需要遵循图灵完备性

    图灵完备/ Turing Complete：在可计算理论中，当一组数据操作的规则（一组指令集、编程语言或元胞自动机）满足任意数据按照一定的顺序可以计算出结果，则称为图灵完备。

二十四、智能合约形式化验证

    智能合约面临的问题：1）可信安全；2）双方认可的模板框架；3）合约验证问题；4）合约的定制问题；5）一致性问题；6） 可控性和可调度性。

    采用模型检测方法验证实时和混成系统。

演绎验证。演绎验证是早期采用的主要验证技术，它基于定理证明的基本思想，采用逻辑公式描述系统及其性质，通过一些公理或推理规则来证明系统具有某些性质。

模型检测（算法验证）。模型检测是对有穷状态系统的一种形式化确认方法，它基于状态搜索的基本思想，是模拟和测试方法的自然延伸，搜索的可穷尽性有赖于为合约建立有穷状态的模型，这为建模造成一定的难度，但能保证搜索过程终止。

声明：本文汇聚网络公开资料，融入个人思考编写而成，不代表任何单位或者机构。

说明：深入实践、点滴思考、原创不易、持续分享，欢迎关注转发，接受批评指正。

扫码关注个人公众号“Forest的账本”