BTC区块链的经典算法(POW 篇/上)

本帖仅做科普向，不推荐任何人参与挖矿/区块链交易等行为

在正式做介绍之前先来科普一下，在分布式领域中的一个不可能三角(CAP定理):

在一个分布式系统中，一致性（Consistency）、可用性（Availability） 和 分区容错性（Partition Tolerance） 这三个核心特性，最多只能同时强满足其中两项，无法三者兼顾

解释一下:

1. 一致性: 要求所有节点在同一时刻看到的数据完全相同。任何读操作都必须返回最近一次写操作的结果，或者返回错误。（这与数据库事务 ACID 中的“一致性”（指数据满足业务约束）是两个不同的概念。）

2. 可用性(实时可用性): 指系统中的每一个非故障节点，对于收到的每一个请求，都必须在有限时间内返回一个非错误的响应。它不保证返回的数据是最新的，只保证服务是响应的。（≠“系统永不宕机”，而是指在部分节点故障时，剩余节点仍能提供有效响应。）

3. 分区容错性: 指当网络发生分区（即节点间通信中断，集群被分割成多个无法互通的子集）时，系统仍能继续运行并按预定策略提供服务。

那么问题来了，你们觉得BTC是强满足了上面的哪两条内容呢

答案是CP类型，也就是BTC其实对于一致性和分区容错性要求是十分严格的，至于可用性的优先级实际上是靠后的(稍微熟悉一点的朋友都知道，BTC十分钟左右才出一个块，在对交易请求服务响应这方面也确实很慢了)

OK，现在知道了类型之后，我们再来详细讲讲其中的分布式算法吧,打算从下面几点开始:

POW类算法

POW，全称是 proof of work，工作量证明。简单理解就是，为了完成某些操作，你需要在完成之前向别人提交一个证明，证明你为了完成这个操作。对于这类算法有个很显著的要求: 1. 计算得到result的结果会很难 2. 别人反推结果运算量极低。举个简单的例子可以类比为，两个一元二次方程组，证明者需要解出xy分别是多少，但验算者只需要把证明者的结果反向带入两个方程看左右两边是否相等就能知道结果是否正确了

这里我用POW类算法来代表BTC这种经典CP系统的分布式算法，因为他们都是通过工作量证明来维护整个网络的一致性的，虽然底层具体的实现不一样，但其实实现方式都大差不差，都是worker计算困难，但是验证简单的类型

思考一下，如果让你选择一款算法，正向简单，逆向困难，只允许单向计算，你最先想到的是什么？

bingo，摘要算法: 把任意长度的数据通过一个固定算法压缩成固定长度的“指纹字符串”，这个过程是单向不可逆的——你无法从指纹反推出原始数据，但只要输入数据哪怕改动一个标点，生成的指纹就会完全不同

SHA类型的算法其实属于典型的只允许单向计算，逆向运算困难，所以引入一些规则就可以作为一个简单的POW算法雏形了: 比如你可以规定，输入一串数据，输出当前的证明内容，只要(数据+证明内容) 进行摘要计算 满足前面有n个0，则视作有效工作

恭喜你，成功发明了邮件时代最常见的防垃圾邮件的算法，Hashcash(下一期我们来细看这个算法怎么支撑起全球多节点参与"计算"的)