数据结构 - 机器学习

密码哈希函数是一类数学函数，可以在有限合理的时间内，将任意长度的消息压缩为固定长度的二进制串，其输出值称为哈希值，也称为散列值。以哈希函数为基础构造的哈希算法，在现代密码学中扮演着重要的角色，常用于实现数据完整性和实体认证，同时也构成多种密码体制和协议的安全保障。碰撞是与哈希函数相关的重要概念，体现着哈希函数的安全性，所谓碰撞是指两个不同的消息在同一个哈希函数作用下，具有相同的哈希值。哈希函数的安全性是指在现有的计算资源（包括时间、空间、资金等）下，找到一个碰撞是不可行的。在比特币系统中使用了两个密码学哈希函数，一个是SHA256，另一个是RIPEMD160。RIPEMD160主要用于生成比特币地址，我们着重分析比特币中用得最多的SHA256算法。SHA256属于著名的SHA家族一员

Merkle哈希树是一类基于哈希值的二叉树或多叉树，其叶子节点上的值通常为数据块的哈希值，而非叶子节点上的值是将该节点的所有子节点的组合结果的哈希值。如图4-4所示为一个Merkle哈希树，节点A的值必须通过节点C、D上的值计算而得到。叶子节点C、D分别存储数据块001和002的哈希值，而非叶子节点A存储的是其子节点C、D的组合的哈希值，这类非叶子节点的哈希值被称作路径哈希值，而叶子节点的哈希值是实际数据的哈希值。在计算机领域，Merkle树大多用来进行完整性验证处理。在处理完整性验证的应用场景中，特别是在分布式环境下进行这样的验证时，Merkle树会大大减少数据的传输量以及计算的复杂度。例如，以图4-4为例，若C、D、E和F存储了一组数据块的哈希值，当把这些数据从Ali

公钥密码算法是现代密码学发展过程中的一个里程碑。这类密码算法需要两个密钥：公开密钥和私有密钥。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法也可叫作非对称密码算法。区块链中所使用的公钥密码算法是椭圆曲线算法，每个用户都拥有一对密钥，一个公开，另一个私有。利用椭圆曲线密码算法，用户可以用自己的私钥对交易信息进行签名，同时别的用户可以利用签名用户的公钥对签名进行验证。在比特币系统中，用户的公钥也被用来识别不同的用户，构造用户的比特币地址。下面我们将介绍区块链中所涉及的椭圆曲线算法以及所采用的椭圆曲线。4.3.1　椭圆曲线密码算法

在本书第3章我们提到，区块链架构是一种分布式的架构。其部署模式有公共链、联盟链、私有链三种，对应的是去中心化分布式系统、部分去中心化分布式系统和弱中心分布式系统。分布式系统中，多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。然而，异步系统中，可能出现无法通信的故障主机，而主机的性能可能下降，网络可能拥塞，这些可能导致错误信息在系统内传播。因此需要在默认不可靠的异步网络中定义容错协议，以确保各主机达成安全可靠的状态共识。利用区块链构造基于互联网的去中心化账本，需要解决的首要问题是如何实现不同账本节点上的账本数据的一致性和正确性。这就需要借鉴已有的在分布式系统中实现状态共识的算法，确定网络中选择记账节点的机制，以及

拜占庭容错技术（ByzantineFaultTolerance，BFT）是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。5.1.1　拜占庭将军问题拜占庭容错技术来源于拜占庭将军问题。拜占庭将军问题是LeslieLamport在20世纪80年代提出的一个假象问题[1]。拜占庭是东罗马帝国的首都，由于当时拜占庭罗马帝国国土辽阔，每支军队的驻地分隔很远，将军们只能靠信使传递消息。发生战争时，将军们必须制订统一的行动计划。然而，这些将军中有叛徒，叛徒希望通过影响统一行动计划的制定与传播，破坏忠诚的将军

比特币系统的重要概念是一个基于互联网的去中心化账本，即区块链，每个区块相当于账本页，区块中记录的信息主体，即为相应的交易内容。账本内容的唯一性要求记账行为是中心化的行为，然而，中心化所引发的单点失败，可能导致整个系统面临危机甚至崩溃。去中心记账可以克服中心化账本的弱点，但同时也会带来记账行为的一致性问题。从去中心化账本系统的角度看，每个加入这个系统的节点都要保存一份完整的账本，但每个节点却不能同时记账，因为节点处于不同的环境，接收到不同的信息，如果同时记账的话，必然会导致账本的不一致，造成混乱。因此，需要有共识来达成哪个节点有权记账。比特币区块链通过竞争记账的方式解决去中心化的记账系统的一致性问题。比特币系统设计了以每个节点的计算能力即“算力”来竞争记账权的机制。在比特币系统

PoW背后的基本概念很简单：工作端提交已知难于计算但易于验证的计算结果，而其他任何人都能够通过验证这个答案就确信工作端为了求得结果已经完成了量相当大的计算工作。然而PoW机制存在明显的弊端。一方面，PoW的前提是，节点和算力是均匀分布的，因为通过CPU的计算能力来进行投票，拥有钱包（节点）数和算力值应该是大致匹配的，然而随着人们将CPU挖矿逐渐升级到GPU、FPGA，直至ASIC矿机挖矿，节点数和算力值也渐渐失配。另一方面，PoW太浪费了。比特币网络每秒可完成数百万亿次SHA256计算，但这些计算除了使恶意攻击者不能轻易地伪装成几百万个节点和打垮比特币网络，并没有更多实际或科学价值。当然，相对于允许世界上任何一个人在瞬间就能通过去中心化和半匿名的全球货币网络，给其他人几乎没有

PoW机制和PoS机制虽然都能有效地解决记账行为的一致性共识问题，但是现有的比特币PoW机制纯粹依赖算力，导致专业从事挖矿的矿工群体似乎已和比特币社区完全分隔，某些矿池的巨大算力俨然成为另一个中心，这与比特币的去中心化思想相冲突。PoS机制虽然考虑到了PoW的不足，但依据权益结余来选择，会导致首富账户的权力更大，有可能支配记账权。股份授权证明机制（DelegatedProofofStake，DPoS）的出现正是基于解决PoW机制和PoS机制的这类不足。比特股（Bitshare）是一类采用DPoS机制的密码货币，它期望通过引入一个技术民主层来减少中心化的负面影响。比特股引入了见证人这个概念，见证人可以生成区块，每一个持有比特股的人都可以投票选举见证人。得到总同意票数中的前N个

1.Ripple的网络结构Ripple（瑞波）是一种基于互联网的开源支付协议，可以实现去中心化的货币兑换、支付与清算功能。在Ripple的网络中，交易由客户端（应用）发起，经过追踪节点（trackingnode）或验证节点（validatingnode）把交易广播到整个网络中。追踪节点的主要功能是分发交易信息以及响应客户端的账本请求。验证节点除包含追踪节点的所有功能外，还能够通过共识协议，在账本中增加新的账本实例数据。如图5-5所示是Ripple的共识过程中节点交互示意图。2.Ripple共识算法Ripple的共识达成发生在验证节点之间，每个验证节点都预先配置了一份可信任节点名单，称为UNL（UniqueNodeList）。在名单上的节点可对交易达成进行投票。每隔几秒，R

小蚁是基于区块链技术，将实体世界的资产和权益进行数字化，通过点对点网络进行登记发行、转让交易、清算交割等金融业务的去中心化网络协议[1]。小蚁可以被用于股权众筹、P2P网贷、数字资产管理、智能合约等领域。小蚁共识机制使得运行小蚁协议的各节点能够对当前区块链状态达成一致意见。通过股权持有人投票选举，来决定记账人及其数量；被选出的记账人完成每个区块内容的共识，决定其中所应包含的交易。小蚁的记账机制被称为中性记账。PoW/PoS/DPoS解决谁有记账权的问题，而中性记账则侧重于解决如何限制记账人权力的问题。在中性记账的共识机制下，记账人只有选择是否参与的权力，而不能改变交易数据，不能人为排除某笔交易，也不能人为对交易进行排序。小蚁的中性记账区块链可以做到：1）每15s产生一个区块，优化后有望