区块链开发：共识机制PoW #C06

分布式一致性与共识

区块链的本质就是一个分布式系统，而分布式系统通常面临了几个问题：一致性问题，可终止性问题、合法性问题。

可终止性可以理解为系统必须在有限的时间内给出一致性结果，合法性是指提案必须是系统内的节点提出。当然其中面对的最重要也是最基础的问题，就是我们常说的一致性问题。

一致性是指在某个分布式系统中，多个服务节点呈现相同的状态和数据。这里面可能是多个相同的服务提供同样的功能，那么这些服务中的状态和数据就应该保持一致，对外就好像一个服务一样；另一种情况是多个不同的服务在提供不同的功能，但他们的数据前后关联，那么这些服务所拥有的数据也应该保持一致。但是很多时候，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2 +1 就超过半数，代表大多数了。所以一致性也分严格一致性、最终一致性。

对应到区块链系统中就可以表示为：任意节点的提案能够在约定的协议下被其他所有节点所认可。因为区块链系统中不分服务端和客户端，所以这里强调任意节点，同时上文所说的一致性在这里就对应为区块链的共识机制。需要提醒你区分的一点是：这里的“认可”表示所有节点对外呈现的信息一致，而不是对信息的内容认可。

常见算法

前文介绍了一些常见的分布式一致性算法，其中paxos和raft协议是较为经典的算法，但是他们无法抵御节点恶意篡改数据的攻击，所以常用于节点能够完全信任的环境，比如各节点服务都是某公司统一部署控制的，节点完全私有。这种情况属于中心化的分布式系统，一般会有leader，系统可以容忍非恶意攻击，例如网络拥堵、数据丢失等等，但不能容忍恶意节点的攻击。

而区块链的应用环境恰恰是其他两种情况，第一种是完全公有的环境，也即公链，任何人都可以部署节点（准入门槛很低），常用PoW、PoS等共识算法；而第二种是属于私有链，只有获得许可的机构或者个人才能部署节点，参与的机构或者个人由于先获得了权限许可，所以可以看作“可信任”。这里的“可信任”是指受信程度高于完全陌生的公有节点，但也不是完全可以信任。这种情况通常用PBFT算法（拜占庭将军问题，在有恶意节点的情况下（精神分裂式投票），如何保证系统状态与数据的一致性）。

CAP定理

CAP 定律（Consistency，Availability，Partition Tolerance），说的是在一个分布式计算机系统中，一致性，可用性和分区容错性这三种保证无法同时得到满足，最多满足两个。其中，分区容错性指的是在网络中断，消息丢失的情况下，系统照样能够工作；一致性说的是分布式系统中，所有节点在同一时刻看到同一个值；可用性说的是每个请求都会收到一个应答，无论该应答是成功还是失败。

对CAP 定律做进一步分析，我们可以更加深入地了解各种公式算法的特性及其适用场景。

• C：一致性决定了不同节点达成共识的时间长短
  这里又分为概率一致性（最终一致性）算法和绝对一致性算法。概率一致性算法指在不同分布式节点之间，有较大概率保证节点间数据达到一致，但仍存在一定概率使得某些节点间数据不一致。对于某一个数据点而言，数据在节点间不一致的概率会随时间的推移逐渐降低至趋近于零，从而最终达到一致性。例如工作量证明算法（Proof of Work, PoW）、股份证明算法（Proof of Stake, PoS）和委托股权证明算法（Delegated Proof of Stake, DPoS）都属于概率一致性算法。而绝对一致性算法则指在任意时间点，不同分布式节点之间的数据都会保持绝对一致，不存在不同节点间数据不一致的情况。例如分布式系统中常用的 PAXOS 算法及其衍生出的 RAFT 算法等，以及拜占庭容错类算法（类 BFT 算法）。一致性决定了分布式系统中不同节点达成共识的时间长短，在区块链中也就是出块时间长短，达成一致性所需的时间越短，系统的TPS越高。

• A：可用性是分布式系统必须的
  使用分布式系统的一个重要原因就是为了避免单点系统宕机出现问题，提高系统可用性。而且这也是分布式系统的基础，如果做不到7 X 24 X 365 可用，那么区块链系统的可靠性就会大打折扣。

• P：分区容忍性有两层含义
  第一层是必须保证分区可容忍，也就是一旦出现因为网络分区而导致区块链分叉，必须有一种机制可以合并区块链；第二层含义是 如果我们尽量避免出现网络分区，那么就可以避免 P 的出现，从而提升 C 的性能 。

由以上特点我们可以知道，可用性A必须保证，而C 和 P 是可以相互调整的，又分为三种情况。

1. 如果我们选则调整 C，延长最终一致性的确认时间，那么就可以减弱对分区容忍性 P 的要求，只要区块链能够有足够的时间恢复最终一致性即可。
   这种系统 舍弃了C，而追求A和P ，其特点是抗干扰能力特别强，也即PoW和PoS的特点，适用于在完全公有的环境中抵抗各种干扰，保证区块链的稳定性，可以称之为 去中心化的系统。同时由于此系统降低了C的性能，所以达成共识的时间延长，系统的TPS就很低，这也符合PoW和PoS为代表的比特币和以太坊的特性。

2. 如果我们选则调整 P，限制记账节点的数量，并且对记账节点之间的带宽提出要求，从而降低网络分区出现的可能性，那么就可以减弱对 C 的要求，降低出块时间。
   这种系统的特点是提高了节点的准入门槛来减少系统受到的攻击，同时节点数量也大大减少，所以TPS会大大提高。这种系统兼顾了C和P，可以称之为弱中心化的系统。这也是DPoS和PBFT的特性，这里的代表是EOS和各种联盟链。

3. 而如果完全不考虑拜占庭容错等问题，也就是情况3，我们可以进一步追求 C，这也是 中心化分布式系统的特点，其一致性算法常用PAXOS和RAFT。

下面分析了一些常见共识算法的特性，以及一些区块链项目的共识比较。

	PoW	PoS	DPoS	类PAXOS	类BFT
吞吐量高	★	★★	★★★	★★★	★★★
可用性高	★★★	★★★	★★	★★	★
一致性强	★★	★★	★★	★★★	★★★
计算消耗低	★	★★	★★	★★★	★★★
网络消耗低	★★★	★★	★	★	★

	BTC	ETH	EOS	MIOTA	BTS	Cardano
共识机制	PoW	PoW	DPoS+BFT	MCMC+PoW	DPoS	PoS
每秒事务处理量/TPS	5~7	7~14	1M (理论上)	1000+	3300	unknown
总供应量/Millions	21	可定增	1000	2780	3600	45000

PoW

原理介绍

PoW 全称是 Proof of Work，也即工作量证明。最早于1977年提出，用于抵抗滥用软件服务的场景中，例如验证码的应用（可以是识别数字、文字或者图形），网络用户需要先完成验证，系统才会接收处理其提交的请求。这个完成验证的过程，其实就是在解一个难题，而这个难题通常被设置成不对称性，解这个难题需要花费一定的人力和算力，而验证答案则可以通过计算机很快的完成，这就是PoW的设计思想。

比特币就采用了PoW机制，它的难题设定为：对区块头中的内容求哈希值，如果这个哈希值满足前N位为0，那么这个区块就是有效的。而区块头中包含一个随机数nonce，矿工节点需要求解出这个nonce，使得计算出的哈希值满足要求，这一过程就被称之为“挖矿”。挖矿成功的节点会把这一区块广播出去，而收到新区块的节点需要验证这个区块的有效性，验证过程即为计算区块头的哈希值，看是否满足前N位为0。由于nonce与最终哈希值没有直接关联，所以nonce只能通过枚举的手段来求解，每次枚举都要求解一次哈希值，直到满足要求，而验证过程只需要计算一次哈希值，所以这个过程满足求解困难，验证容易的思想。

如果这个区块被其余矿工节点确认，那么挖矿节点就会获得一定数量的比特币作为奖励。因为哈希值的求解完全随机，导致网络中每个节点挖矿成功的可能性近乎相等，所以按照中本聪的设计，比特币是一个去中心化的电子交易系统。但是这里忽略了一个问题，那就是哈希值的求解虽然随机，但是枚举的过程适合并行执行，枚举速度与算力成正比，算力越高，挖矿速度越快，成功性更高。早期用CPU挖矿，频率高的CPU挖矿速度更快，但是差异并不明显，耗费的电力、设备成本也是个人可以接受的；随后发展为GPU挖矿，FPGA挖矿，挖矿芯片（矿机）挖矿，设备越先进，挖矿成功率越高，但是设备维护、电力消耗远远超出个人承受范围。所以现在比特币发展成了由五大矿池控制的中心化挖矿，当然这里的五大矿池并非一家所有，所以你仍然可以说这是去中心化的，但是这与中本聪设计的去中心化相差甚远。个人用户依然可以用CPU或者GPU来进行挖矿，但是挖出比特币的可能性可以忽略不计，就好比你有选举权，但是没有选举成功的可能性，选举落为形式主义。

参考比特币，PoW的规则可以定义为求解一个随机数nonce，使得区块头的哈希值前N位为0，也即小于某个target

hash (CurBlock(nonce)) ≤ target

而提高N，也即减小target，会使得挖矿难度增大。

代码实现

基本结构

class Pow {
    constructor(blockchain) {
        this.difficulty_ = 10000;
        this.nonce_ = 0;
        this.state_ = "Idle";
        this.block_chain_ = blockchain;
    }
}

这里依然基于之前的代码结构进行设计，Pow类用来实现PoW共识，主要包含difficulty_和nonce_两个成员。difficulty_表示当前区块生成难度，nonce_表示所寻找的工作量证明。由于设计上将共识模块与区块模块分离，所以这里只需要设置每种共识所需要的数据元素即可。
state_表示当前共识模块的工作状态，这里可以用来判断当前是否在挖矿。

工作量证明

工作量证明通过枚举nonce来找到满足哈希值条件的值。由前面的代码可知，prepared和make_consensus是供外部调用的接口。

    prepared() {
        return this.state_ == "Idle";
    }
    calc_difficulty(block) {
        this.difficulty_ = parseInt("0001000000000000000000000000000000000000000000000000000000000000", 16);
    }

    make_consensus(block_data) {
        this.state_ = "Busy";
        this.calc_difficulty(block_data);

        let self = this;
        setImmediate((block) => {
            self.nonce_ = 0;
            while (self.nonce_ < Number.MAX_SAFE_INTEGER) {
                block.set_consensus_data({
                    "difficulty": self.difficulty_,
                    "nonce": self.nonce_
                });

                var hash = block.calc_block_hash();
                if (parseInt(hash, 16) < self.difficulty_) {
                    block.emit('consensus completed');
                    self.state_ = "Idle";
                    break;
                } else
                    self.nonce_ += 1;
            }
            block.emit('consensus failed');
            self.state_ = "Idle";
        }, block_data);

    }

进行工作量证明之前我们要确定当前的挖矿难度，这里先将其固定，也就是要满足哈希值前四位为0。
在进行工作量证明的过程中，共识模块会变为"Busy"状态，当工作量证明完成或者最终失败时，又会转为"Idle"状态。

然后我们用如下的代码进行测试，这里我们生成区块的时候没有装载交易，仅仅测试PoW挖矿的过程，并统计生成区块的时间。

'use strict';

var crypto = require('crypto');
var ed = require('ed25519');
var BlockChain = require("../blockchain");
var Consensus = require("../consensus/pow");

let blockchain = new BlockChain(Consensus);

// console.log(blockchain.get_last_block().hash);

var password = 'I am tester!';

var hash = crypto.createHash('sha256').update(password).digest();
var keypair = ed.MakeKeypair(hash);

async function create_block(prev_time) {
    return new Promise((resolve, reject) => {
        blockchain.generate_block(keypair, () => {
            console.log(`|${blockchain.get_last_block().hash}|${blockchain.get_last_block().timestamp - prev_time}|`);
            resolve();
        });
    });
}

(async () => {
    for (var i = 0; i < 20; ++i) {
        let prev_time = blockchain.get_last_block().timestamp;
        await create_block(prev_time);
    }
})();

从运行结果可以看出，挖矿所得区块的哈希值前四位均为0，满足我们设置的工作量证明条件，而挖矿时间间隔波动较大。

Block hash	Mine time
d611edb9fd86ee234cdc08d9bf382330d6ccc721cd5e59cf2a01b0a2a8decfff
000043e5b3d91162976eddb358b89ff587a4ad812158bf643ea804b04a3e9d03
000097278c9f1f43bc676d1ee5800bfc3008e181b24a8f784758f4ad5a85c773	266
000040e22b5cd0aa3f8600e6c273e80cca52b0431daa430985f9db5834254525	148
0000c052c1edcd94cc6be19e9acffb22c65ccab6e7bce7f4450ae976a53f25f6	144
0000d0548f585b5ab3a205d7555de6eda1819d85b7e613b00bb77a357522b0f2	227
000007ac9ce0db3c87a6559d63a30139ff5b04f9b75c7dc285374e6afc62a099	84
0000ab3d1dad9bfd673a77f7b304aae0feaf804ae82bba4efb3d1e7b225184ba	1122
0000a8e63a464bd4daeb5bfcbcb2e932194085e86e95811108efb30829e98e01	561
0000e5fb0b0b6c2d9dcc0fac76eb8a5877b543a144276ad7ede34c88aab2242f	18
000018962d879c5cd3604ed14e3d858e9baa5771f8beba5915eb909707104243	207
000079e7d3e02bd2d0369b539af2fbfcf213bb6520e88a718ee22ba3f3e701e6	49
00009e253a45da3cb31f414c09dea4828e9c229e29668306ae2450eb85217654	712
0000cceae0a6caee22ed79ba49d03ff97d7f677c68093aaed19f9f57791f0932	292
00006ee9b819b77e66795c974091bc62cbfb98d2d1d5689e52fd3ceac8f046a3	150
0000e6b9cc2f9b970cdc6fcbe0065a8f0b6ccfb113b53b4a65bff9b9eca0634f	11
00002fab36ed9de7ee2c4c6426738bef956973942aaa1154206a9f4ef6847a28	792
00005a9af033eb95da9b6670573d78081ce1f94eed54eec36370e3a27f560f81	228
00009d88808ba0d5ddaf0438d4e14a77160e55d7864e10d869d285618e735e2d	363
00009ba29ae75f7505c15ef5b59fde35bf42289f8f69c0bbafcb3d4331a5792e	460
00005736d95dafb929c68933546d4125bc2f5d6cb4f6aca8276da827f3b76b33	5

将难度加大，调整为5个0时，可以看到挖矿时间有所提升，但是波动仍然较大，不容易控制。

Block hash	Mine time
d611edb9fd86ee234cdc08d9bf382330d6ccc721cd5e59cf2a01b0a2a8decfff
0000054765f277ee0ce011ef939b4e59412a5c12ecf2991d5fc500f0e9713be3
00000b9acab5d3650784f0f49d7562d7ab1b51075b13fefdc310c457aec709cf	1479
0000044730408c7e581828733ba888fb6901b649f6cf6c56228c6cd1f058ee77	8411
0000027e383562bb658aeb6a9abf6ef4f6f912f7799288de77b64c0f251d57c5	9039
00000062389c8b62e72ef7f70342a3dac79c593f2ed738e768eb01daf0776c48	6187
000001bc873095709aade05bd932b0dea2f2417c8ea8850ec0947249b470e808	27384
00000a5f9503d53f361a2c0c3af6d1eb85bf9202bef3880c3e891b0e314c7aaa	1046
00000d9119c630419069399e737427c00ec5d2361931762ee8bd5d2de88e2dd9	5073
00000032ed942c01f5e3ae2f9a9d3458c2bb739d07f5ef387085cc9dcd2b44dd	11046
00000709e1c26064e2a2181add8fc5a0e556124fe5b15c0899c66fd290fe19c3	5367
000002f23488b9a01ec08042d556d01135830f6d543f3c494e78cd5ac3f8dd0c	8851
00000b16f65a7d98f3377c35ed7b0600c2019f219d8ed92fee46f301b0f290b3	4845
00000adf3a6742bbcaa6cfb7f4475fb2594bcc968f3bd9e5c1547907b886f85f	16567
000007bc06588166cdd821345f4eca641641d82ecd498f47c34641016b7a6707	919
00000c7833bb612c78d90847c193d3f3679b669612d419712bac0bb8d0e4a8cf	199
000003f6f9250c7cc649c251ab6c99f96ebeb1f2d401db890f6479a496878ce5	956
000003d432830d269a7fe65683b3b914af0f677a9c720a3dbc8e97f46285a2a2	16061
00000477bf337bd5a9e0a6e7d2560093a4bb29607a6234ef78c9d52cdf6e6481	5278
000007bfe98d7173f56db907cd728ad2d872b65f913e9d21665929135a460edf	876
00000876ce2c76eab5b44b59ebdfe3bea9aaa9163f1bc1a4a20d15d602cd18e6	429

难度调整

上述代码仅仅是为了演示PoW的过程，让你更好地理解其原理。但是在实际应用中，目标难度的设定会随着时间而变化。例如在比特币中，挖矿难度的调整是在每个完整节点中独立完成的，每过2016个区块（约2周）所有节点会检查并调整一次难度，各节点会将2016个区块的总出块时间与20160分钟比较，如果大于20160分钟则降低难度，如果小于则提升难度。

难度调整的公式为：

New Target = Old Target * (Actual Time of Last 2016 Blocks / 20160 minutes)

为防止难度变化过大，每个周期的调整幅度不能超过4倍，如果算力变化超过4倍，多余的部分将在下一个周期调整。

这里将这一过程简化并加入代码，根据两个区块生成时间的差异来调整目标难度。

    calc_difficulty(block) {
        // adaption
        let prev = this.block_chain_.get_last_block();
        if (!prev.difficulty) {
            this.difficulty_ = 10000;
            return;
        }
        var time_period = block.get_timestamp() - prev.timestamp;
        if (time_period < 3000) {
            this.difficulty_ = prev.difficulty + 9000;
        } else if (prev.difficulty < 3000) {
            this.difficulty_ = prev.difficulty + 9000;
        } else {
            this.difficulty_ = prev.difficulty - 3000;
        }
    }
    make_consensus(block_data) {
        this.state_ = "Busy";
        this.calc_difficulty(block_data);

        let self = this;
        setImmediate((block) => {
            self.nonce_ = 0;
            let target = Number.MAX_SAFE_INTEGER / self.difficulty_ * 100;
            while (self.nonce_ < Number.MAX_SAFE_INTEGER) {
                block.set_consensus_data({
                    "difficulty": self.difficulty_,
                    "nonce": self.nonce_
                });

                var hash = block.calc_block_hash();
                hash = hash.toString('utf8').substring(0, 16);
                if (parseInt(hash, 16) < target) {
                    block.emit('consensus completed');
                    self.state_ = "Idle";
                    break;
                } else
                    self.nonce_ += 1;
            }
            block.emit('consensus failed');
            self.state_ = "Idle";
        }, block_data);

    }

加入自动调节难度后，如果前一次挖矿时间较短，则下一次会增加难度，提高挖矿时间；而当前一次挖矿时间过高时，则会降低难度，挖矿时间有明显的下降。

这里只是一个简单的调节策略，调节力度也比较粗，但从实验结果来看已经可以一定程度上自动调节挖矿时间。

Block hash	Mine time
d611edb9fd86ee234cdc08d9bf382330d6ccc721cd5e59cf2a01b0a2a8decfff
00004f589430423c205e2067696947debb20bc896eaab6a22dc4950f684bb8ea
000047f3539f3f4638dcf554ff38983febc6289129d53eca88c15772d54f970f	2309
000039e19862e24b62a09ddd93378a966b0a111a3da602b04ae2b7b4f379463b	111
00001ccba89e3de31904a8c55e54de096d03cdeeec84752e6272f94523b2b89f	787
000008137d3a57f74f7de1a0e19ac7e0b4547dff5a0bb2fbb7ad633fde885c50	182
00001530f625f9547357038b7d36d6d466ea5ca2f75c270fb195529ee6b70a7f	141
00001c7cc87a99c338a3cd1d280eaadc19a2f43c9f6c1b76974a81786d8803ba	44
000046519401689f2f50590a425677db8b87e9c432379685e00e9300d4d9ec35	410
00001348880607f6b2865a2a38850fea08730211f1c4a711f7a7bb22943a3399	149
00002dd7f5fa76c8379263e9810b2b8873879ae4eefd2359320cb18a8a6e7615	904
00001025b9fd89364b8b2415716fadcbdbdbd187a2ab95440d479a9cd0a22ac0	3325
0000037ec0b7ebff4b7ab7896e72093b8b765edde23eeb5b865a6b6204a2a9eb	2017
0000166cc0d4805dccb8a4960cc5388986af2ff0560368627908d202cd368fad	438
00004b12af158c9a19953583c6dde2d8a6fe88ba8427cbda0f6972701efe2e10	1561
00002b94a6c301e35c55346545153945ab8434431977fbb8e7c10f265bb7581e	215
0000180c0dabbde5eadf6aa915ec921ae0bb92654a4d03050207f1a186c6f530	237
000031c4d5af040a8b4e0b8355c36aeebc3c417c53c6d36bfdc61de04f3d34b9	1054
0000031beb6bc517e76fa7c536979631712158dba0404eb17761dee5cb2bfe6e	321
0000279fbeeb054cb629a3b78548246be27b58669a7ef51bab7db4a74da55795	101
0000169b81b755610f38c294c5ee2b04447bdd3dd4150449f625933cdeca6f61	1292

优缺点

PoW共识最大的优点是简单可靠，不要求高质量的P2P网络资源，并且充分经过实践验证。然而PoW也有些显著的缺点：

1. 电力耗费严重
   这也是中本聪引入的经济博弈的关键，提高作恶成本让作恶行为得不偿失。即使攻击者拥有超过50%的算力，虽然从技术角度讲可以篡改比特币，但是其经济收益反而不如正常挖矿来得高，从而避免51%攻击。但是对于其他链来说，不一定具有比特币这么高的全网算力，所以作恶成本会大大降低；而且当数字货币行情下跌时，逐利矿工挖矿热情减少，也会影响全网算力，让攻击者有机可乘。
2. 自私挖矿
   自私挖矿是指矿工挖出区块时先不广播，而是继续挖下一个区块，然后等别人广播一个区块的时候，自己广播两个或者更多的区块，这样自己就有100%的挖矿率，别人一直处在被分叉的状态。当然这要依靠较大的算力优势来实现，往往最后会形成矿霸。