第四节 比特币的共识协议
今天来讲怎么发行一个加密货币。
数字货币和纸质货币区别是可以复制，叫作双花攻击 即double spending attack。
数字货币所面临的主要的挑战就是怎么防范双花攻击。
如果央行在每个货币上加上编号，用个大数据库来存储这些编号，比如这个货币在谁手中，你除了验证防伪标签，还要验证这个货币以前有没有花过。这样倒是可以防范双花攻击，但是太麻烦了。而且这是个中心化的操作。
去中心化货币要解决两个问题:①数字货币的发行，谁来发行货币怎么发行②怎么验证交易的有效性，防止double spending attack。
答案:①比特币的发行是由挖矿决定的
②依靠区块链的数据结构，维护一个数据结构，不是由央行维护，而是有所有用户共同维护，这个数据结构就是区块链。
比如说比特币的发行者A拥有铸币权(createcoin) 假如发行10个比特币 。
A(10)分别给B和C各五个 → B(5)C(5) 该交易需要有A的签名，证明经A同意。(designed by A)同时还要说明花掉的10个比特币从哪来的。
第二个方框中的钱是从第一个框内铸币交易中来的。
比特币系统中每个交易都包含输入和输出两部分。输入部分要说明币的来源，输出部分要给出收款人公钥的哈希是什么。
有的交易部分比较复杂，如C的货币来源是第二第三个方框，要标识清楚。
上图就构成了一个小型的区块链，**这里有两种哈希指针，一种哈希指针是连接在各个区块之间的，把它们串起来构成一个链表，前面学的就是这种哈希指针。**而在该图中还有第二种哈希指针，是指向前面某个交易的指针，用来指明币的来源。为什么要说明币的来源:证明币不是凭空捏造的是有记录的，同时也是防范double spending。（可以查一下之前这个币花过没有，这样就可以防止双花攻击）
现在来看第二个方框里A向B的转账，该交易需要A的签名和B的地址。比特币系统里收款的地址是通过公钥推算出来的。**比如B的地址就是B的公钥取哈希然后经过一些转换得到的。**地址相当于银行账号。
A如何知道B的地址?
比特币系统中没有查询对方地址的功能，必须通过其他渠道。比如某个电商网站，接受比特币支付，它在它的网站上就可以公开它的地址或公钥。（二维码）
A需要知道B的地址，B需要知道A的什么信息吗?
B其实也要知道A的公钥，这代表A的身份，好知道这钱是从哪儿来的。其实有个更重要的原因，不仅是B，所有节点都需要知道A的公钥，为了验证A的签名，因为这个转账是合法的，得有A的签名。而签名是用私钥签名公钥验证(注意不要跟前面知识弄混了，加密是用接收人的公钥加密私钥解密)，所以区块链上每个节点都要独立验证，因为有的节点可能是有恶意的，你不能依靠别人，作为旁观者也要验证是否合法。
那如何才能知道A的公钥?
A的公钥是A的交易中自己给出来的， A给B转账这个交易，除了要说明币的来源，输入当中还要说明A的公钥是什么。
实际上交易里就包含了。输入时不仅要输入币的来源，还要输入公钥。那就存在了安全漏洞，假如B的同伙伪造了这次交易呢，他用他自己的公钥在输入中说的A的公钥，然后用他的私钥签个名，别的节点收到完之后用这个假造的公钥验证这个签名，肯定是对的，以为这个交易是合法的，怎么避免这个问题呢？
每个交易分为输入和输出两部分，输入部分要说明B的来源，还要说明A的公钥，输出部分说明要给出收款人的公钥的哈希，类似于他的地址。其实第一个方框里铸币交易的输出就有A的公钥的哈希，所以第二个方框交易里A的公钥要跟前面哈希对的上，对的上说明这个币是给你的。这样有个破坏者把它自己的公钥说成是A的公钥，和前面对应不起来。
我给你发送信息，用非对称加密体系，是用你的公钥加密，公开的公钥加密，受到之后用自己的私钥解密。也就是发送方用接收方的公钥(公开的)加密，接收方用自己的私钥解密。发送方用自己的私钥进行签名，接收方用发送方的公钥进行验证。
在比特币系统当中，前面这些验证过程，是通过执行脚本来实现的。每个交易的输入提一段脚本，包括给出公钥的过程，公钥也是在输入的脚本里指定的。每个交易的输出也是一段脚本，验证其的合法性，就需要把当前交易的输入脚本跟前面交易(提供币来源的交易)的输出脚本拼在一起，然后看看能不能顺利执行，如果能执行说明是合法的。比特币脚本(BitCoin Script)。前面交易的输出脚本和A的输入脚本拼接起来，合成一段程序。
那个长的图对交易系统进行了简化，实际上每个区块(对应图中的每个方框)可以有很多交易，这些交易就组成merkle tree。每个区块分为块头和块身。
块头包含的是区块的宏观信息，比如:用的是比特币哪个版本(version)的协议，区块链当中指向前一个区块的指针(hash of previous block header)，整颗merkle tree 的根哈希值(merkle root hash)，还有两个域是跟挖矿相关的，一个是挖矿的难度目标预值(target)，另一个是随机数nonce。
这里的target，就是前面讲到的，整个块头的哈希要小于这个预值，即H(block header)≤target。block header里存的就是这个目标预值的编码(nBits)。**这里需要注意，前一个区块的哈希只算的是前一个区块的块头，所以前面画的，一个区块引出一个剪头指向另一个区块中间，是不正确的，所以有的书箭头是指向一个区块的上面。取哈希时是把块头的所有部分都取哈希。**只有block head才有这种哈希指针串联起来。
块身（block body）里面有交易列表(transaction list)。
里面的merkle root hash 就已经能够保证了block body 里面交易列表没有办法被篡改的。
前面还有一个内容讲的时候简化了假设:每个节点都需要验证所有的交易，实际上系统中的节点分全节点(full node)和轻节点(light node)，全节点是保存区块链所有的信息的，验证每一个交易，所以全节点又叫fully validating node。轻节点只保存block header的信息，一般来说轻节点没法独立验证交易的合法性。（比如这个交易是否是双花攻击，轻节点不知道，查不出来）
系统中大部分节点是轻节点，全节点的数目不是很多
比如一个交易是不是double spending，轻节点没有存以前的交易信息所以它没法验证。系统中大多数节点是轻节点，这节课内容主要针对全节点，因为轻节点没有参与区块链的构造和维护，只是利用了区块链的一些信息做一些查询。
区块链里的内容是如何写到区块链里面的呢？
每个节点，每个账户都可以发布交易，交易是广播给所有节点的。有些交易是合法的，有些是非法的。谁来决定哪些交易应该被写入下一个区块中呢?按照什么顺序写呢?如果每个节点自己决定可以吗?
区块链是什么，是个去中心化的账本，账本里的内容得有个统一的说法。如果每个人在本地维护一个区块链，那区块链的统一性得不到保证，而账本的内容是要取得分布式的共识(distributed consensus)。
分布式的共识一个简单的例子就是分布式的哈希表(distributed hash table)，比如系统里有很多台机器，共同维护一个全局的哈希表。
这里需要取得共识的内容是什么？哈希表中包含了哪些键值对key valve pair。假如有人在自己电脑上插入一个键值对，'xiao’这个key对应的是12345，即’xiao’→12345。那么别人在另一台读的时候也要能把这个读出来，这就叫一个全局的哈希表。
关于分布式系统有很多不可能结论(impossibility result)，其中最著名的是FLP。这三个字母是三个专家的名字缩写，他们的结论是:在一个异步的(asynchronous)系统里，(网络传输迟延没有上限就叫异步系统)，即使只有一个成员是有问题的(faulty)，也不可能取得共识。
还有一个著名结论:CAP Theorem。(CAP是指分布式系统的三个我们想要的性质，Consistency【系统状态的一致性】 Availability【别人都可以用】 Partition tolerance)。该理论内容是:任何一个分布式系统，比如分布式哈希表，这三个性质中，最多只能满足两个，假如想要前两个性质，那么就不会得到第三个性质。
分布式共识一个著名的协议是Paxos，该协议能够保证一致性，即第一个性质。如果该协议打成了共识，那么这个共识一定是一致的，即每个成员所认为的共识都是相同的。但是，某些情况下，该协议可能永远无法达成共识，这种可能性比较小但是客观存在的。
比特币中的共识协议(consensus in BitCoin)
比特币中共识要解决的一个问题是，有些节点可能是有恶意的。我们假设系统中大多数节点是好的，那么该如何取得共识协议?
第一种方案是既然大多数节点是好的，那就直接投票，首先应该确定哪些区块有投票权，有些membership是有严格要求的，不是谁都可以加入的，（比如说联盟链hyperledger，只有某些符合条件的大公司才能加入 hyperledger fabric）这种情况下基于投票的方案是可行的。但是比特币系统不是这样的。
但是比特币系统创建账户是很容易的，就在本地产生一个公钥私钥对就是一个账户，不需要任何人批准，甚至一个人产生了公私钥对别人都无法得知，只有转账时别人才知道。所以有些恶意节点可以不停的创建账户，当超过账户总数的一半时就有了控制权，这种称为女巫攻击(sybil attack)。因此投票方法不可取。
比特币账户巧妙的解决了这个问题，也是投票，不是按照账户数目投票，而是按照计算力来投票。每个节点都可以在本地组装出一个候选区块，把它认为合法的交易放在里面，然后开始尝试各种nonce值(占4 byte)，看哪一个能满足不等式H(block header)≤target的要求。block head里面有一个域叫做nonce。如果某个节点找到了符合要求的nonce，它就获得了记账权。
所谓的记账权，就是往比特币账本里写入下一个区块的权利。只有找到这个nonce，获得记账权的节点才有权利发布下一个区块。其他节点收到这个区块之后，要验证这个区块的合法性。
比如括号里block header的内容填的对不对；block header里面有一个域，叫nBits域，实际上它是目标预值的一个编码，检查一下nBits域设置的是不是符合比特币协议中规定的难度要求；该不等式是否成立。假设都符合要求，然后检查block body 里面的交易列表，验证一下每个交易都是合法的:①要有合法的签名②以前没有被花过。如果有一项不符合要求，这个区块就是不能被接受的。如果所有条件都符合，也不一定接受。如下图
比如最下面这个，它是合法的（这里合法意思是区块的内容合法，没有包含非法的交易，都有合法的签名，没有被花过），那它应不应该接受呢？但是插在中间的。
假如生成了一个新区块，怎么知道新区块插在了哪里呢?
我们之前学过hash of pervious block head，根据前一个区块的指针就知道它是插在这个位置。
插在这个位置有什么问题吗？
根据生成区块的指针。有可能就存在一个问题，这两个交易指A转账给B，以及A转账给自己。
这种情况不是double spending，判断一个交易是不是double spending ，是看这个区块所在的分支上币又没有被花掉。查看是不是double spending是看从当前这个区块到币的来源之间，中间这些区块，这个币有没有花过，这个图没有花过，所以这个交易是合法的。实际上下面这个区块是在上面这个转账交易给回滚了，本来你是给B的写到区块链里面了，后面（下面）再来个区块，把这个钱转给自己了。验证下面这个分叉是不是合法的，不会查到上面这个分叉。
虽然该交易是合法的，但是它不在最长合法链(longest valid chain)上。上面是最长合法链，比特币接受的区块应该是在扩展最长合法链。
这个例子称为分叉攻击(forking attack)，通过往区块链中央位置插入一个区块来回滚某个已经发生了的交易。所以接收的区块应该是扩展最长合法链。
区块链在正常情况下也可能出现分叉，出现在哪些情况下呢？
如果有两个节点同时获得记账权。怎么获得记账权的呢？每个节点在本地自己组装一个它认为合适的区块，然后去试各种nonce，如果两个节点在差不多同一个时间找到了符合要求的nonce，就都可以把区块发布，这时会出现两个等长的分叉。
这两条都是最长合法链，那该接受那条呢?
比特币协议当中，在缺省(默认的意思)情况下，每个节点是接受它最早收到的那个。所以不同节点根据在网络上的位置不同，有的节点先听到新生成的其中一个区块，那就接受这个区块；有些节点先听到另一个区块，那就接受另一个区块。
什么叫做接受一个区块呢？如何判断接收了一个区块?比特币协议中用到了implicit consign，如果沿着这个区块往下继续扩展，就算认可了这个发布的区块。比如在新生成的其中一个区块后面又拓展一个区块，表明就认可了这个新区块。
如果系统中出现两个矿工，两个节点差不多同时发布区块的情况，那么这种等长的临时性的分叉会维持一段时间，直到一个分叉胜出。也就是哪一个链抢先一步生成了新的区块，哪一条就是最长合法链。另一个作废的就叫orphan block，就被丢弃掉了。这两个新区块有可能会各自拉拢，两个区块链看谁的算力强，有时候也是看谁的运气好，就会胜出。
为什么要竞争记账权？或者有记账权的好？
首先获得记账权的节点本身有一定的权力，它可以决定哪些交易写到下一个区块里。但这些不应该把这个设定为竞争记账权的主要动力，我们是希望凡是合法的交易，都应该能写入到区块链里面，所以比特币中巧妙地建立了一个机制：出块奖励(block reward)。
比特币协议中规定获得记账权的节点在发布的区块里可以有一个特殊的交易：铸币交易。在这个交易里可以发布一定数量的比特币。
这里要回到前面的问题①，谁来决定货币的发行?**（铸币交易）coinbase transaction是比特币系统中发行新的比特币的唯一方法，其他所有的交易都是比特币从一个账户转移到另一个账户。**包括用法币来购买比特币，这个也是没有产生新的比特币。
那么能造多少币呢?开始时比特币刚上线的时候，每一个发布的区块可以产生50BTC（出块奖励）(BTC就是比特币的符号)。协议中规定，21万个区块以后，初块奖励就要减半，就变成了25BTC。再过21万个区块，又要减半12.5（18年是一个6000美元，总共8w美元，现在得一个4w美元了）。但是当初的比特币是不值钱的，据说当时有人为了买个比萨，用了2w个BTC。这就是为什么挣破了头也要抢这个记账权。
那些orphan block，因此当一个区块胜出后，另一个作废的区块得到的比特币是没有作用的，大多数诚实的区块是不会承认的。
比特币系统中共识机制要取得什么共识?
我们之前举得例子，分布式哈希表，有很多系统服务器要维护分布式哈希表，这里维护的共识是这个哈希表中的内容，包含那些key-value值。
而比特币系统中取得的共识是去中心化的账本要取得共识。
谁又能决定账本的内容呢?只有获得记账权的节点才能往里面写东西。怎么获得记账权呢?puzzle friendly，保证求解过程没有捷径，只能一个一个去试一下。就是解pow(挖矿)。按照算力记票，算力（hash rate）决定投票的权重，权重越高，概率越大，也就是每秒能试多少nonce。
那这个方法怎样防范女巫攻击（sybil attack）呢?按算力记票，即使创建再多的账户，也没有影响的，也无法使算力增强，不会使尝试的nonce数量增加。
比特币争夺记账权的过程叫作挖矿(mining)，比特币被称为数字黄金(digital gold)，争夺记账权的节点被称为矿工(miner)，一旦找到就能赚大钱。