BTC-4-比特币系统的实现

UTXO, block header, block body, probabilistic and safety analysis of mining process.

区块链是去中心化的账本，比特币使用的是基于交易的账本模式( transaction-based ledger )

UTXO

比特币系统中并不会显示每个账户有多少钱，这实际上需要通过交易记录推算才能得知。在比特币系统中，全节点需要维护一个名为 UTXO( Unspent Transaction Output )的数据结构。

区块链上有很多交易，有些交易的输出已经被花掉，有些还没有被花掉。所有没有被花掉的交易输出的集合就叫做UTXO.
UTXO集合中的每个元素要给出产生这个输出的交易的哈希值，以及它在这个交易中是第几个输出。通过这两个信息，便可以定位到UTXO中的输出。

维护UTXO集合有什么作用？
为了检测double spending，即检测新发布的交易是否合法。新的交易中的输入若不在UTXO中，说明这笔钱要么不存在要么已经被花掉了，是不合法的。

假如有人收到一笔BTC转账后一直不花，那这个输出信息会一直保存在UTXO中，他可能是不想花(如：中本聪)，也有可能是忘了私钥(→_→)导致这笔钱成为死钱。所以UTXO集合是逐渐增大的，但就目前的数据来说，一个普通的服务器硬盘是完全可以保存这些数据的。

扩展：
比特币是基于交易的账本模式，与之对应还有基于账户的账本模式( account-based legder )，比如以太坊。这种模式中，系统要显式的记录账户余额，也就是说可以直接查询当前账户的余额情况。
可见比特币的这种模式，隐私性较好，但但缺陷是比特币中的转账交易必须说明币的来源(防止double spending)，而基于账户的模式天然的避免了这个问题，因为该模式下的转账交易就是对一个(多个)账户余额的数字做减法，对另一个(多个)账户余额做加法。

BTC系统区块具体信息

以上信息均为块头的信息，块身是交易列表，未在图中给出
Difficulty每隔2016个区块调整，目的是保持出块时间在十分钟左右
挖矿其实就是尝试各种nonce，使得当前打包区块的hash值小于目标阈值，所以hash前面有一长串的0

下为block header的数据结构代码。

#ifndef BITCOIN_PRIMITIVES_BLOCK_H
#define BITCOIN_PRIMITIVES_BLOCK_H

#include <primitives/transaction.h>
#include <serialize.h>
#include <uint256.h>

/** Nodes collect new transactions into a block, hash them into a hash tree,
 * and scan through nonce values to make the block\'s hash satisfy proof-of-work
 * requirements.  When they solve the proof-of-work, they broadcast the block
 * to everyone and the block is added to the block chain.  The first transaction
 * in the block is a special one that creates a new coin owned by the creator
 * of the block.
 */
class CBlockHeader
{
public:
    // header
    int32_t nVersion;
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    uint32_t nTime;
    uint32_t nBits;
    uint32_t nNonce;

    CBlockHeader()
    {
        SetNull();
    }

    SERIALIZE_METHODS(CBlockHeader, obj) { READWRITE(obj.nVersion, obj.hashPrevBlock, obj.hashMerkleRoot, obj.nTime, obj.nBits, obj.nNonce); }

    void SetNull()
    {
        nVersion = 0;
        hashPrevBlock.SetNull();
        hashMerkleRoot.SetNull();
        nTime = 0;
        nBits = 0;
        nNonce = 0;
    }

    bool IsNull() const
    {
        return (nBits == 0);
    }

    uint256 GetHash() const;

    int64_t GetBlockTime() const
    {
        return (int64_t)nTime;
    }
};

可以看到，nonce是一个32位的无符号整型数据，故nonce只有2的32次方个可能的取值，按比特币现在的挖矿难度来说(由于近些年来，全网算力指数式增长，挖矿难度已经比较大了)，可能遍历nonce的所有取值，仍然找不到符合要求的nonce。2的32次方的搜索空间太小，要找到符合要求的值，我们还需要调整block header中其他域的值。

下面来看看block header 各个域的具体含义

由此，在挖矿时，除了改变nonce值，我们还可以更改根哈希值。

为什么根哈希值可以更改呢？打包的交易和顺序确定了，根哈希值不就确定了吗？
- 其实打包的交易顺序也可以改变，因为比特币使用的Merkle Tree是不排序的，但是这个改变的空间太小了，很不实用。
- 注意Merkle Tree中有一个交易是铸币交易(coinbase transaction)，该交易是矿工发布的(是交易列表的第一笔交易)，而且该交易的币是没有“输入”的，没有来源，是凭空发行的。
- 说了这么多，到底哪里可以由矿工更改以便挖矿呢？其实铸币交易中还有一个coinbase域，原文档解释为：
  - The first transaction in a block, called the coinbase transaction, must have exactly one input, called a coinbase. The coinbase script is arbitrary(随意的) data.
  - 在这个coinbase script中可以写入任何内容，没人会去检查，矿工可以提前写入预测结果的哈希、写入人生感想（挖矿不容易，且挖且珍惜(￣▽￣)”）、写爱情誓言······
由于铸币交易也参与merkle tree的构造，修改coinbase域，可以沿着merkle tree的结构往上传递，导致root hash发生变化。若矿工把coinbase域中的前八个字节当extra nonce用，那么搜索空间就增大到了2的96次方
Coinbase script：
The coinbase field: Arbitrary data not exceeding 100 bytes minus the (4) height bytes. Miners commonly place an extra nonce in this field to update the block header merkle root during hashing.

所以，在实际挖矿中，包含两层循环。外层循环调整coinbase域的extra nonce，算出Merkle Tree的root hash后，内层循环再调整nonce

普通的转账交易

比特币系统验证交易的合法性：

付款人要转账的币的Output script(币的来源)与当前转账交易的Input script合并验证，若输入脚本和输出脚本拼接起来可以顺利执行不出现错误，说明交易合法。

挖矿过程概率分析

挖矿本质上是不断尝试nonce，来求解puzzle。每次尝试一个nonce可以看作一个伯努利试验( Bernoulli trial )

挖矿过程中，一次伯努利试验成功的概率极小。
挖矿便是进行多次伯努利试验，且每次随机，这些试验构成了一系列独立的伯努利试验，又叫伯努利过程(Bernoulli process: a sequence of independent Bernoulli trials)，它的一个性质是：无记忆性(memoryless).
所谓无记忆性，就是说无论之前做了多少的试验，对后续试验没有任何影响。

因为挖矿进行的伯努利试验成功概论极小，而且要进行大量的试验，由概率论的知识，此时该过程可以用泊松过程(Poisson process)来近似。我们现在来看系统出块时间，出块时间服从指数分布(exponential distribution)，指数分布也具有无记忆性(从概率曲线上说，从任意地方截断曲线，剩下的曲线和原来的是一样的)。也就是说，对整个系统而言，距上一个区块产生已过去10min，还没有人挖到区块，那么接下来要等待是时间平均还是10min，即将来还要挖多长时间，跟过去已经挖了多久是没有关系的(可能不太符合常识)，这个过程叫做：progress free.

具体到每一个矿工，他能挖到下一个区块的时间取决于矿工算力展全网算力的百分比。假如一个人的算力斩全网的1%，那么系统出100个区块，就有一个区块是这个人挖的。
progress free看似很”无情“，但其实正是这个性质保证了比特币系统挖矿的公平性，如果没有progress free，算力强的矿工会有不成比例的优势，因为算力更强的矿工过去做的工作是更多的，过去尝试了更多的不成功的nonce后，以后挖矿nonce的成功概率会增大，这种优势比特币系统是不希望看到的。
比特币求解的puzzle，除了工作量证明以外，没有其他的实际意义，只是单纯的算力比拼。虽然没有实际意义，但挖矿的过程对维护比特币系统的安全性是至关重要的，挖矿提供一种凭借算力投票的有效手段，只有大多数算力掌握在诚实的节点手里，系统的安全性就能够得到保证。

比特币挖矿的难度越来越大，出块奖励每21万个区块减半，但这几年挖矿的竞争却越来越激烈，因为比特币的价格是飙升的。那当出块奖励为0时，人们是不是就没有动力挖矿了呢？
还记得之前说过，矿工打包区块除了出块奖励外，还能获得一笔交易费，当出块奖励趋于0时，整个系统将依赖与交易费运行，届时交易费会成为维护比特币系统运行的重要保障。

挖矿过程安全性分析

假设大部分算力掌握在诚实矿工手里，能否保证写入区块链的交易都是合法的？挖矿给出的只是概率上的保证，只能说下一个区块有比较大的概率是由诚实矿工发布的，但不能保证记账权不会落入恶意节点手里。假如记账权落入恶意节点之手，会出现什么情况？

能不能偷币？(把其他账户的比特币转给自己)
- 不能，转账交易需要用付款人的私钥签名，恶意节点不知道付款人的私钥是无法伪造其他人签名的。这种攻击其实是很不明智的，倘若在不知道付款人私钥的情况下伪造签名还将此非法交易打包进区块发布，诚实节点是不会接受这个区块的，他们还是会在原来区块的基础上往下挖，随时间推移，此区块就会成为 orphan block，被作废。对恶意节点来说，不仅没有偷到钱，还得不到出块奖励，还浪费了挖矿的电费等成本。
能不能把已经花过的币再花一遍？
- 如图，A已经把币转账给B，现在想把这笔币转给自己，假设A获得记账权
  - 若按①的方式发布区块，这很明显是double spending，诚实节点是不会接受这个区块的，他们会在A→B那个区块的基础上继续挖
  - 只能按②的方式发布区块，要将A转账给B的交易记录回滚掉。这样就是两条最长合法链的竞争的情况了。
  - 需要注意的是在挖矿之初就要决定上一区块是谁，因为打包区块时block header里要填前一个区块block header的哈希。所以他想要插入在哪个区块之后，挖矿之前就要认定，而不是等获得记账权后再认定。
如何防范这种攻击？
- 如果A→B的交易所在区块不是最后一个区块，那么这种攻击的难度会大大增加。因为此时恶意节点需要使A→A所在区块的分叉成为最长合法链，然而此时最长合法链已经是主链了，区块链中大多数节点都会在最长合法链的基础上扩展，那么恶意节点想要胜出就要在与全网算力的竞争中胜出。
- 因此防范这种攻击的方法就是多等几个区块，或者叫多等几个确认 confirmation，A→B交易写入区块时，我们把它叫做one confirmation，这时后面加上的区块叫two confirmation、three confirmation······比特币协议中，缺省条件下，需要等6个确认区块，此时才认为该记录是不可篡改的。平均出块时间10min，六个确认区块便要等一个小时，可见等待时间还是很长的，转一笔账要等一个小时对方才能确定收款，在实际中其实很少会等那么久。
  - 下面介绍实际中更实用的零确认，意思是说这个转账交易发布出去了，但还没被写入区块链。
  - 这个概念相当于在电商购物的例子中，在支付时你发布一个转账交易，告诉电商自己已经转过钱了。电商运行一个全节点或委托一个全节点监听区块链上的交易，他收到转账交易之后要验证该交易的合法性(有合法的签名，以前没有被花过)，甚至不用等到该交易写入区块链里。这种操作听起来风险很大，交易刚发布出去，都没往区块链里写呢。其实，零确认在实际当中，用的还是比较普遍的。为什么呢?
  原因：
  ①比特币协议缺省的设置是节点接收最先听到的那个交易。所以在零确认的位置，A→B的交易节点收到后，再发A→A的交易，有比较大的概率诚实的节点是不会接收的。
  ②很多购物网站，从支付成功，到发货，是有一定的时间间隔的，即有一定的处理时间。(就算被回滚了，商家及时发现后只要不发货，攻击还是失败的)
能否故意不打包某些合法交易？
- 这是可以的，比特币协议没有规定获得记账权的节点一定要把哪些交易打包到区块中发布。就算出现这些情况，问题也不大，因为总会有诚实的节点会愿意打包这些交易的。其实在实际中，诚实节点也会出现这种情况，比特币协议中规定每个区块的大小是有限制的，上限在1M左右，若某时间段的交易数目太多了，有些交易可能要等到下一个区块才能发布。
selfish mining
- 包含A→A交易的区块挖到后继续往下挖，等到收款人确认收款后(等待确认区块)，一次性发布所有挖到的区块，使之成为最长合法链，以此回滚付款记录。这种情况的成功概率很小，因为有恶意的节点算力占比本来就不高，而且还要以一己之力挖矿超过全网算力，这需要恶意节点掌握全网算力半数以上的算力。
- 以上是selfish mining的一个目的，它还有另外一个目的。
  假如A挖了两个区块都没有发布，在B挖到一个区块公布后马上发布这两个区块，那么B挖的区块就会成为orphan block，这样的好处是减少竞争，因为A在挖第二个区块的时候，别人还在挖第一个(前提是A算力足够强)
  不过也有坏处，假如A挖出一个区块后不公布然后着手去挖第二个，在没有挖到第二个的时候，有人挖出了第一个区块并公布，那么A就要别人发布后马上发布自己挖到的区块，去竞争出块奖励。