第2章 区块链的灵魂：从哈希算法到共识机制
针对区块链的算法，目前国内有两种理解方式：一种是指具体的哈希算法，另一种是指共识机制。两者属于不同的概念范畴，显然不能混为一谈，但是两者均为区块链体系中的重要组成部分，是区块链技术的基石。
针对区块链的算法，目前国内有两种理解方式：一种是指具体的哈希算法，比如SHA256；另一种是指共识机制，比如工作量证明机制、权益证明机制等。之所以存在两种不同的理解方式，是因为最初从国外引进文献资料时，对概念的翻译比较模糊。很明显，两者属于不同的概念范畴，显然不能混为一谈，但是两者均为区块链体系中的重要组成部分，是区块链技术的基石。
1.哈希算法
哈希（Hash）这个词对大多数计算机从业者来说并不陌生。哈希函数是一种数学函数，可以将任意长度的字符串，在有限的时间内，压缩为一个较短的、固定长度的二进制值，这个输出值我们称之为哈希值或者散列值。
哈希算法以哈希函数为基础，在现代密码学中扮演了非常重要的角色。它常常用于实体认证和实现数据完整性，是多密码体制和协议的安全保障。
哈希算法在区块链中有着广泛的应用。比如，既可以表示数据的实际内容又能够指示数据存储位置的哈希指针（Hash Pointer）、可进行快速查找的布隆过滤器（Bloom Filter）、用于区块头和简单支付验证（SPV）的默克尔树（Merkle Tree）、工作量证明等。可以说，哈希算法贯穿区块链系统的方方面面。
那么，哈希算法该如何鉴定呢？在密码学上，哈希算法拥有以下性质：第一，函数的输入可以是任意长的字符串；第二，函数的输出是固定长度的字符串；第三，函数的计算过程是有效率的。综合来说，哈希算法就是通过一个方法，将输入的任意字符串转换成一个固定长度的值，这个值相当于一个新的身份证号，通过哈希算法计算出的结果，无法通过任何算法，还原出原始的数据，即它具有单向性，因此，哈希值能被当作“身份证号”，适用于需要进行身份验证的场合。同时，它的高灵敏度，也可以用于判断数据是否完整，只要数据发生变化，哪怕变化十分微小，重新计算后的哈希值也会与之前的不一样。
为了保证密码学上的安全性，哈希函数一般都必须满足以下两个条件。
抗碰撞性
哈希函数的抗碰撞性是指寻找两个能够产生碰撞的消息在计算上是不可行的。简单来说，如果输入值不同，输出结果也不同。这就好比我们买火车票，理论上，购买同一趟列车时，不同身份证号买到的座位号是不一样的。必须说明的是，找到两个碰撞的消息在计算上不可行，并不意味着不存在两个碰撞的消息。哈希函数是把大空间上的消息压缩到小空间上，碰撞肯定存在，只是计算上是不可行的。
可隐藏性
哈希算法是一种单向密码体制，只有加密过程，没有解密过程，也就是说，即便有人事先知道了哈希函数的输出结果，想要伪造，也不可能在足够的时间内破解其输入值。这个特性可以应用在防伪方面。比如，有人想伪造公园门票，因为门票是公开的，大家都看得到摸得着，传统的制票技术很容易让人钻空子，而哈希函数相当于给制票增加了一道隐匿的工艺，让造假者明知道输出的样子，却无法造出一模一样的票来。
哈希算法固定的输出值与多种多样的原始数据，注定了存在不同原始数据输出同一个哈希值的可能。理论上，当原始数据的数量极其庞大时，就有可能出现这样的情况。以邮件系统的抗垃圾邮件算法为例，全世界的邮件地址多如牛毛，格式也千变万化，针对这一情况，通常会对邮件地址进行多种哈希计算，将计算出来的多个哈希值联合起来，综合判断是否存在相同的邮件地址，这也是布隆过滤器的基本原理。
在哈希算法中，这两类算法最为常用，一个是RIPEMD160，另一个是SHA256。RIPEMD160主要用于比特币地址的生成，而SHA256是区块链中应用最广泛的算法。
SHA256是安全哈希算法，即SHA（Secure Hash Algorithm）系列算法之一，其消息摘要的长度为256位，故称为SHA256。SHA系列算法是由美国国家安全局设计，美国国家标准与技术研究院发布的一系列密码散列函数。第一个SHA算法发布于1993年，之后变体相继发布，包括SHA1、SHA224、SHA256、SHA384和SHA512，后面四者也被称作SHA2算法。SHA256算法是SHA2算法簇中的一类。对于任意长度的消息，SHA256都会产生一个32字节（即256位长度）的数据，称作消息摘要。在传输的过程中，数据很可能会发生改变，这时候就会产生不同的消息摘要。当接收消息时，我们就可以用消息摘要来验证数据的完整性，检查是否发生变动。
SHA256是构造区块链的主要哈希函数。为保证数据的完整性，无论是区块的头部信息还是交易数据，都使用SHA256去计算相关数据的哈希值。同时，基于寻找给定前缀的SHA256哈希值，区块链系统中设计了工作量证明的共识机制；SHA256也被用于构造比特币地址，以识别不同的用户。
SHA256是一个迭代结构的哈希函数，其计算过程分为两个阶段：预处理和主循环。预处理阶段，主要完成消息的扩展和填充，将所有原始消息转化为n个512位的消息块，之后进入主循环阶段，利用SHA256对每个消息块进行压缩处理，当最后1个消息块（第n块）处理完毕后，输出最终值，即所输入原始消息的SHA256哈希值。
2.默克尔树
默克尔树（Merkle Tree）是区块链的基本组成部分。虽然从理论上来讲，我们只需要创建一个包含每一笔交易的巨大的区块头，就可以不使用默克尔树，但是这显然是不现实的，它无论对应用的扩展性还是计算机的运行性能都有着非常大的挑战。默克尔树的存在，让以太坊的节点可以建立并运行在所有的计算机、智能手机，甚至是物联网设备之上。那么，默克尔树究竟是什么，它又能提供什么价值呢？
默克尔树，通常也被称作哈希树（Hash Tree），顾名思义，就是存储哈希值的一棵“树”。默克尔树的“叶子”是数据块（例如，文件或者文件集合）的哈希值，非“叶子”节点上的值是其对应子节点的串联字符串的哈希值。也就是说，默克尔树是对大量聚集在一起的数据块进行哈希计算的一种方式，它将这些数据块分裂成较小单位的数据块，然后取每个较小单位的数据块再次进行哈希计算，重复同样的过程，直至产生根哈希值。
默克尔树最为常见和最简单的形式，是二叉默克尔树，其中一个较小单位的数据块总是包含了两个相邻的块。虽然，在不同的区块链系统中，默克尔树的细节不同，但其本质都是一样的。我们以比特币中的默克尔树为例，比特币中的默克尔树是二叉树，每一个区块都存在默克尔树。首先，将区块中的交易事务分别计算出哈希值，不同的哈希值两两结对，算出新的哈希值，然后再将新的哈希值两两结对，进行哈希计算，递归循环，直到计算出最后一个根哈希值，这样的结构树就是默克尔树。
那么，这种奇怪的哈希算法有什么好处呢？为什么不直接将这些数据块串接成一个单独的大块，用常规的哈希算法运行呢？答案在于，它创造了默克尔证明。一个默克尔证明包含了一个数据块、这棵默克尔树的根哈希值，以及所有沿数据块到根路径的分支。有人认为，这种证明可以验证哈希计算的过程。应用也很简单：假设有一个大数据库，而该数据库的全部内容都存储在默克尔树中，并且这棵默克尔树的根是公开并且可信的，那么，假如有个用户想在数据库中查找一个数值，他就可以利用默克尔证明，获得特定的数值。默克尔证明既可以验证少量的数据，也可以验证大型甚至是无限的数据库。
默克尔树一般用作处理完整性验证，因其结构的显著优势，默克尔树能够大大减少数据的传输数量及计算的复杂程度。如今，默克尔树的树形结构已经被广泛应用到了信息安全的各个领域，比如证书撤销、源组播认证、群密钥协商等。
基于默克尔树的数字签名方案不需要太多的理论假设，仅依赖哈希函数的安全性即可，这使得基于默克尔树的数字签名更加安全、实用。
举一个生活中常见的例子。当我们签订一份n页的合同时，通常会在每页合同上签名。但是因为每一页上的签名都一模一样，很容易被人仿造。如果我们利用默克尔树进行数字签名，即在每一页合同上盖一个数字印章，并且每一页上的数字印章是前一页数字印章和本页内容一起使用哈希算法生成的哈希值，那么签名的安全性就大大增加了。具体来说：
①合同第一页的数字印章是本页内容的哈希值；
②合同第二页的数字印章是第一页的数字印章及第二页内容加在一起后再运行哈希函数产生的值；
③合同第三页的数字印章是第二页的数字印章及第三页内容加在一起后再运行哈希函数产生的值；
④上述过程以此类推。
这样，若篡改了第一页合同，必然会使其哈希值与第一页上的数字印章不符，其后的第2、3、4、5……n页也是如此。
这就是默克尔树的优势——我们不仅能知道信息是否被篡改，还能知道是哪一块信息被篡改了。
3.公钥密码算法
公钥密码算法是现代密码学发展过程中的一个里程碑。公钥密码算法中的密钥分为公开密钥和私有密钥。公开密钥与私有密钥是用户或系统产生的一对密钥，其中的一个公开，称为公钥，另一个自己保留，称为私钥。如果用公开密钥对数据进行加密，那么只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。由于公钥与私钥之间存在依存关系，所以只有用户本身才能解密信息，而加密和解密使用的是两个不同的密钥，所以这种算法也被叫作非对称密码算法。举例来说，如果A要使用公钥密码算法向B传输机密信息，则A首先要获得B的公钥，并使用B的公钥加密原文，然后将密文传给B,B使用自己的私钥才能解开密文。
公钥密码算法有两个重要原则：第一，要求在加密算法和公钥都公开的前提下，其加密的密文必须是安全的；第二，要求所有加密的人和掌握密钥的解密人的计算或处理比较简单，而其他不掌握密钥的人，破译极其困难。
在公钥密码算法的研究中，其安全性都是基于数学上难解的可计算问题，如：大数分解问题、计算有限域的离散对数问题、平方剩余问题、椭圆曲线的对数问题等。基于这些问题，公钥密码算法生成了各种公钥密码体制，椭圆曲线密码算法和RSA加密算法是其中的两个重要方面。
椭圆曲线密码算法
椭圆曲线是满足一个特殊方程的点集，注意，不要跟标准椭圆方程混淆，那根本就是两回事，椭圆曲线方程是这样的：y²=x³+ax+b。
在几何意义上，一个椭圆曲线通常是满足一个变量为2阶，另一个变量为3阶的二元方。按照这样的定义，椭圆曲线有很多种，而椭圆曲线密码算法是基于椭圆曲线数学的一种公钥密码算法，其主要的安全性在于利用了椭圆曲线离散对数难题。
椭圆曲线密码算法实现了数据加解密、数字签名和身份认证等功能，该技术具有安全性高、生成公私钥方便、处理速度快和存储空间小等方面的优势。相对于其他公钥密码算法，椭圆曲线密码算法在实际开发中运用得更广泛，比如，比特币就是使用了椭圆曲线中的SECP256k1算法，为比特币系统提供128位的安全保护。
RSA加密算法
RSA加密算法是以它的三个发明者罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）的名字首字母命名。RSA加密算法是一种常见的非对称加密算法，是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被国际标准化组织推荐为公钥数据加密标准。RSA的安全性基于一个十分简单的数论事实：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积作为加密密钥。RSA的公钥和私钥是一对大数，将一个公钥和密文恢复成明文，等价于分解两个大素数之积，这是公认的数学难题。
RSA的安全性基于大数因数分解难题，但并没有从理论上证明破译RSA的难度与大数因数分解难度等价，无法从理论上把握它的保密性是RSA的重大缺陷。不过，RSA从提出到现在三十多年，经历了各种攻击考验，被认为是当下最安全的公钥方案之一。当然，RSA也存在其他的缺点，比如产生密钥很麻烦、受限于素数产生的技术、分组长度太大、运算代价高、速度慢等。
与对称密码技术相比较，利用非对称密码技术进行安全通信，通信双方事先不需要通过保密信道交换密钥，安全性高，密钥持有量大大减少，易于管理，同时还能够提供对称密码技术很难提供的服务，比如与杂凑函数联合运用可生成数字签名等。
4.共识算法
区块链共识算法的核心之一是拜占庭协定。拜占庭将军的故事大概是这样的：拜占庭是东罗马帝国的首都，拥有巨大的财富，周围有十个邻邦，对首都的财富垂涎已久。但拜占庭高墙耸立，固若金汤，任何一个邻邦入侵都会失败，同时自身也有可能被其他邻邦入侵。拜占庭帝国的防御能力非常强，至少要十个邻邦一半以上同时进攻，才有可能攻破。如果其中一个或者几个原本答应一起进攻的邻邦在行动时发生叛变，那么入侵者可能都会被歼灭。于是，每一方都小心行事，彼此不敢轻易相信。这就是拜占庭将军问题。
拜占庭将军问题的实质就是要寻找一个方法，使得将军们能在一个有叛徒的非信任环境中建立对战斗计划的共识。与拜占庭将军问题的环境类似，在去中心化系统中，特别是在区块链网络环境中，每个将军都有一份与其他将军实时同步的消息账本。账本里有每个将军的签名，从而可以验证将军的身份。一旦出现签名不一致的情况，我们就可以知道是哪些将军发生了叛变。尽管叛变的拜占庭将军可以任意地进行破坏，比如不响应消息、发送错误信息、对不同节点发送不同决定等，但是，只要超过半数的将军同意进攻，那么少数服从多数，就完全有可能实现共识。
在去中心化系统中，要达成共识，必须寻找一个共同算法和协议并且满足以下属性：
一致性——所有的非缺陷进程都必须同意一个值；
正确性——如果所有的非缺陷进程有相同的初始值，那么所有非缺陷进程所同意的值必须是同一个初始值；
可结束性——每个非缺陷进程必须最终确定一个值。
要想最终实现共识算法，一般需要采用工作量证明机制（POW算法）或权益证明机制（POS算法）。
工作量证明机制（POW）
区块链是一个基于互联网的去中心化账本，每个区块相当于账本页，交易内容是区块中记录的信息主体。账本内容的唯一性，要求记账行为必须是一个中心化的行为。然而，一旦中心化的系统中某个单点出现错误，就可能令整个系统面临危机甚至崩溃。去中心化记账可以克服中心化账本的弱点，但同时也会带来记账行为不一致的问题。在去中心化记账系统中，每个节点都会保留一份完整的记账本，但是大家不能同时记账，否则会导致每个节点收到不同的信息，失去记账的一致性，从而产生混乱。因此，到底谁有权记账，我们需要有一个共识机制来决定。
比特币系统设计了以每个节点的计算能力（即“算力”）来实现去中心化系统记账的一致性问题。
那么，如何来判定谁的记账算力最优秀呢？这就需要一个考量的标准——工作量证明。简单地说，工作量证明就是一份确认工作端做过一定量工作的证明。工作量证明机制的主要特征是计算的不对称性。工作端通过一定难度的工作得出一个结果，而验证方通过结果可以很容易地检查工作端是不是做了相应的工作。
工作量证明机制下的共识记账是通过一个什么流程来完成的呢？
在客户端产生新交易的时候，客户端会主动向全网进行广播，要求各个节点对交易进行记账，每个记账节点一旦收到该请求，就会将交易信息纳入一个区块中，通过工作量证明机制，尝试在自己的区块中，找到一个具有足够准确度的工作量证明。当某个节点找到了一个工作量证明，它就会向全网进行广播，当且仅当包含在该区块中的所有交易都有效且之前从未存在过时，其他节点才认同该区块的有效性，表示它们能够接受该区块，跟随该区块的末端，制造新的区块，从而延长整个区块的链条。
权益证明机制（POS）
人们在记账过程中发现，工作量证明算法存在不少明显的弊端，因为其机制决定了谁的算力强，谁就能拥有更大的记账权，获取更多的收益，所以在记账过程中造成了巨大的能源浪费。
为了解决这个问题，工作量证明机制的替代者——权益证明机制被提了出来。
权益证明机制（Proof of Stake）直译过来就是股权证明机制，通过计算你持有的币数占总币数的百分比以及占有币数的时间来决定记账权。类似于股票，股票持有量多的，拥有更多的投票权和收益权。点点币（Peercoin）是率先采用权益证明机制的数字货币。
那么，权益证明机制如何应用呢？
点点币引入了币龄的概念，使得SHA256的哈希运算的难度与交易的币龄成反比。在点点币中，币龄被定义为拥有币的天数与币数量的乘积，这使得币龄能够反映交易时刻用户所拥有的权益数量。简单来说，权益证明机制就是根据持有货币的量和时间来发放利息。在权益证明机制下，每个币每天产生1币龄，如你持有100个币，总共持有了30天，那么，你的币龄就为3000，这个时候，如果你发现了一个POS区块并签名，你的币龄就会被清空为0。你每被清空365币龄，你将会从区块中获得0.05个币的利息（假定利息可理解为年利率5%），那么在这个案例中，利息=3000×5%÷365=0.41个币，这下就很有意思了，持币可以产生利息。
实际上，点点币的权益证明机制结合了随机化与币龄的概念，至少30天未使用的币可以参与下一区块的竞争，持有时间越久和数量越大的币集成功签名下一区块的可能性更大。然而，一旦签名一个区块，币龄就将被清零，必须重新等待至少30天才能签另一区块。为防止非常老或非常大的币集控制区块链，成功找到下一区块的概率将在90天后达到最大值。这一过程既保护了网络，又可以避免在生成新币的过程中消耗大量的计算能力。
点点币的开发者声称，由于没有中心化的挖矿池需求，且购买半数以上币的开销超过获得51%工作量证明所需的哈希计算能力，所以这一机制将使恶意攻击变得非常困难。