比特币笔记
共识算法讨论
在分布式系统中，共识算法被广泛的应用。而共识算法追求的则是实现分布式系统中所有的正确节点对某一个合约达到共识。而区块链中的共识问题就是需要所有的正确节点都认可一条主链并在上面开展工作。
常规的如Paxos和Raft共识机制，在私有的分布式系统或者说中心化的分布式系统中，能够很好的防范Faulty problem (指节点断网，节点崩溃之类的节点出错导致的节点失联的问题)对分布式共识的影响。但是在去中心化的分布式系统中我们需要解决Byzantium problem (拜占庭问题)。所谓的Byzantium problem就是指节点网络中存在恶意的节点，它和Faulty node的区别在于，Faulty node只会掉线，不会在网络中传递虚假的信息，而Byzantium node会在网络中传递虚假信息来阻碍系统达到共识。于是后面有了基于签名机制和三段式提交的PBFT算法。但是虽然PBFT能很好地解决拜占庭问题，但他有两个缺陷:
- 随着网络中节点的数量增加，算法的IO复杂度会剧增，也就是说PBFT无法承载拥有大量节点的网络。
- PBFT的投票机制使其对加入的节点需要进行身份验证，使得节点加入的自由度以及灵活度大大降低。
在联盟链这种去中心化程度略低且需要身份认证的区块链中，PBFT可以很好的发挥作用。但是在比特币这种去中心化程度高，需要容纳百万计节点的公共区块链系统中就不是很适合了，所以对于比特币我们需要设计一种满足以下要求的新的共识算法
- 解决拜占庭问题
- 解决大规模节点问题
- 节点可以自由地加入或者退出
Proof of work
竞争机制
在常规的如PBFT一类的共识算法中，往往需要大规模的IO (信息传递)来对某一个事务达到共识，但是POW设计了一套基于算力的竞争机制来避免了大规模的IO。
因为比特币中每一个区块只允许一个节点来生成，所以如何选出一个被大家都认可的节点来生成并记录当前区块就成了竞争机制需要解决的问题，也就是所谓的记账权争夺。
在竞争机制的设计上，比特币使用到了Hash加密，在之前介绍比特币结构的时候，我们提到了比特币的Hash Pointer是针对Block Header进行求hash值的，而Hash Header中有两个特殊的字段，一个是nBits，一个nonce。Proof of Work即工作量证明的竞争机制其实本质上就是通过改变nonce的值去不断地生成Hash Pointer，直到生成的Hash Pointer满足了nBits的条件。这个过程有点类似与赛跑，满足nBits条件的Hash Pointer就是终点，每个节点都在通过改变nonce的值去不断地生成新的Hash Pointer，直到找到一个能使Hash Pointer满足nBits条件的nonce就将这个nonce发布出去，这样谁先找到合法的nonce，谁就拥有了记账权。在之前的博客中提到过比特币对于Hash算法有一个特殊的要求，也就是Puzzle Friendly，要求Hash算法的加密规律是不可预测的，也就是说不能人为的去控制生成的密文落到某一个范围，密文的生成是需要具备很大的随机性的。所以在这个比赛的过程中，没有捷径可以走，所有节点都必须通过大规模的重复计算去找到合法nonce。而决定谁能胜利的条件则是运气+算力。找nonce的过程就像是抽奖，而算力的多少则代表这你在同一个时间段里能够抽多少次奖。
找nonce的过程需要n次的计算，而这个计算的过程可以看作是单机的，它不需要和其他节点进行交流。他唯一需要的交流则是在找到nonce后，将自己打包好的区块发送给其他节点去验证，而这个IO的复杂度仅仅只是O(n)。在同样高度的情况下，每个节点会认可自己接收到的最早的区块，并以它为head节点继续挖掘新的区块。
临时分叉以及fork rule(分叉规则)
POW设立了一个fork rule，规定了节点会选择高度最高的链作为自己的主链，并以最高的区块作为head进行工作。可是消息在网络中的传播是有延时的，所以很可能会出现两个节点同时找到了nonce或者是在很小的时间差内找到了nonce。那么区块链中就可能出现两条高度一样的分支，这时比特网络中便出现了多个派系，他们都选择了不同的区块作为head进行后续工作。其实不用担心这样的情况，因为一旦其中一条分支的高度超过了其他分支，所有的节点都会认可这个高度最高的分支并转移到这个分支上来工作。通常拥有算力量多的那个分支会胜出。而连续多次的同时出块的概率是微乎其微的。所以区块链可能不能再某一个时间段内达到共识，但是他们最终一定在某一个时刻达到共识，这就是所谓的最终一致性。根据FLP定理，在异步的分布式系统中，一致性是不可达的，但是我们可以保证最终一致性。所以POW的fork rule保障了区块链系统的最终一致性。
分叉攻击(51%攻击)
所谓的51%攻击是指当恶意节点的算力达到了51%以上后，他们可以恶意的在任意一个区块处进行分叉，并使用算力优势使新产生的分支的高度逐渐超过原先的主分支，这样原先的主分支上的交易都会被废弃掉。设想一下，如果A向B支付了100BTC购买了一辆汽车，当这笔交易在区块链上记录成功后，B将汽车给了A。但是A拥有51%的算力，他在记录这个交易之前的一个区块进行分叉攻击，并且很快新分支的高度超过了原有的分支高度，这时候包含有A向B支付了100BTC这笔交易的区块将会变成Orphan Block(孤儿区块)，不再被区块链上的节点所认可。于是B相当于卖出了汽车却没有收到钱。
