北京大学肖臻老师《区块链技术与应用》公开课笔记(五)：BTC具体实现

基于交易的账本模式

区块链是一个去中心化的账本，比特币采用了基于交易的账本模式(transaction-based ledger),每个区块里记录的是交易信息，然而，系统中并无显式记录账户包含比特币数，实际上其需要通过交易记录进行推算。在比特币系统中，全节点需要维护一个名为UTXO(Unspent Transaction Output尚未被花掉的交易输出)的数据结构。

如图，A转给B五个BTC，转给C3个BTC，B将5个BTC花掉，则该交易记录不保存在UTXO中，C没有花掉，则该交易记录保存在UTXO中

UTXO集合中的每个元素要给出产生这个输出的交易的hash值以及它在这个交易中是第几个输出，通过这两个信息，便可以定位到UTXO中的输出。

维护UTXO的目的：防范双花攻击

判断一个交易是否合法，要查一下想要花掉的BTC是否在该集合中，只有在集合中才是合法的。如果想要花掉的BTC不在UTXO中，那么说明这个BTC要么根本不存在，要么已经被花过。所以，全节点需要在内存中维护一个UTXO，从而便于快速检测double spending（双花攻击）。

每个交易会消耗输出，但也会产生新的输出。

如图，A转给B5个BTC，之后B将其转给D，则UTXO中会删掉A->B这一交易记录，同时会添加B->D这一交易记录。

假如有人收到BTC转账，但一直不花，那么这个信息会一直保存在UTXO中。这种情况可能是该用户不想花这些BTC(如：中本聪) ，也有可能是忘记了私钥导致无法花掉。所以，UTXO是逐渐增大的，但该数据目前来说，一个普通的服务器硬盘中是可以完全保存这些数据的。

每个交易可以有多个输入，也可以有多个输出，但输入之和要等于输出之和（total inputs = total outputs）

存在一些交易的total inputs 略大于 total outputs，这部分差额便作为交易费，给了获得记账权的节点。在公开课笔记4中最后提及到“区块中保存交易记录，如果仅仅设置出块奖励，那么，会不会存在节点只想发布区块获得出块奖励而不想打包交易？”

因此，BTC系统设计了Tranction fee（交易费），对于获得记账权节点来说，除了出块奖励之外，还可以得到打包交易的交易费。但目前来说，交易费远远小于出块奖励。等到未来出块奖励变少，可能区块链的维护便主要依赖于交易费了。

BTC系统中每21万个区块，BTC出块奖励减半。根据下图计算，基本上出块奖励每4年减半。

基于账户的账本模式

比特币是基于交易的模式，与之对应，还有一种基于账户的模式(account-based ledger)（如：以太坊）。基于账户的模式要求，系统中显示记录账户余额。也就是说，可以直接查询当前账户余额是多少货币。可以看到，比特币这种模式，隐私性较好，但其也付出一定代价。在进行交易时，因为没有账户这一概念，无法知道账户剩余多少BTC,所以必须说明币的来源（防止双花攻击）。而基于账户的模式，则天然地避免了这种缺陷，转账交易就是对一个（多个）账户余额的数字减和另一个（多个）账户余额的数字加

BTC系统中具体的区块信息

如下图所示，为一个区块的信息（取自视频中截图，源自blockchain.info）

什么是挖矿？

可以看到，区块哈希与前一区块哈希都是以一长串0开头的，挖矿本身就是尝试各种nonce，使得产生的区块哈希值小于等于目标阈值。该目标阈值，表示成16进制，就是前面含有一长串的0

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

图片说明

可以看到，nonce是一个32位的无符号整型数据，在挖矿时候是通过不断调整nonce进行的，但可以看到，nonce的取值最多为2^32(2的32次方)种。但并非将这些nonce全部遍历一遍，就一定能找到符合要求的nonce。由于近年来，挖矿人员越来越多，挖矿难度已经调整的比较大了,而2^32这一搜索空间太小，所以仅调整nonce很大可能找不到正确的结果。

那么还有哪些域可以调整呢？

下图为block header中对各个域的描述。而仅仅调整nonce是不够的，所以这里可以通过修改Merkle Tree的根哈希值来进行调整。

在公开课笔记4中提及，每个发布区块者可以得到出块奖励，也就是可以在区块中发布一个铸币交易(coinbase交易),这也是BTC系统中产生新比特币的唯一方式。下为一个铸币交易的内容：

图片说明

可以看到，有一个CoinBase域，其中可以写入任何内容，在这里写什么都没有影响，内容也是自己定义的。所以可以在这里添加一些任意信息，便可以实现无法篡改（也无法删除）。（例如：提前写入股票预测结果的哈希值、写入人生感谢，写入爱情誓言（无法删除））

所以，只要我们改变了写入内容，便可以改变Merkle Tree 的根哈希值。

下图为一个小型的区块链，假定左下角交易为coinbase交易，可以看到，该交易发生改变会逐级向上传递，最终导致Merkle Tree根哈希值发生改变。

图片说明

所以，在实际的挖矿中，包含两层循环。外层循环调整coinbase域（可以规定只将其中前x个字节作为另一个nonce），算出block header中根哈希值后，内层循环再调整nonce。

普通转账交易

图片说明

如果将输入脚本和输出脚本拼接起来可以顺利执行不出现错误，则说明交易合法。

注意：这里的输入脚本和输出脚本拼接指的是，上一个提供币的交易来源的输出脚本和该订单的输入脚本拼接，执行不出现错误，图中的输入脚本和输出脚本是一个订单的输入脚本和输出脚本

下面这张图实际上概括了挖矿过程要干的事：找到一个nonce并且拼接前一个区块的hash值和merkle tree的根哈希值(就是图中的|| tx || tx,实际商并上merkle tree的根哈希值就已经确保了整个区块里的交易是无法篡改的)，然后对这个拼接的值取哈希，使得H()小于traget(表现形式就是前面一堆0)

挖矿过程的概率分析

Bernoulli trial： a random experiment with binary outcome

伯努利试验（Bernoulli experiment）是在同样的条件下重复地、相互独立地进行的一种随机试验，其特点是该随机试验只有两种可能结果：发生或者不发生。比如掷硬币

很多的Bernoulli trial组成一个Bernoulli process(a sequence of independent Bernoulli trials),最大的特点：无记忆性，也就是说前面的结果不会对后面的结果产生影响。

对于挖矿来说，成功的概率很小，实验的次数很多，需要大量的实验才能找到符合要求的，这种情况下，Bernoulli process可以用Poisson process来近似。由此通过概率论可以推断出，系统出块时间服从指数分布。(需要注意的是，出块时间指的是整个系统出块时间，并非挖矿的个人)

系统平均出块时间为10min，该时间为系统本身设计，通过难度调整维护其平均出块时间。
指数分布本身也具有无记忆性(memoryless)。也就是说，对整个系统而言，已经过去10min，仍然没有人挖到区块，那么平均仍然还需要等10min（虽然不符合人的直觉），也就是说，将来要挖多久和已经挖多久无关。我们也可以从图像看出，从任何一个位置截取，剩下的图像的形状跟原来图像形状是一样的。所以无记忆性这个性质有时也被称为progress free

这个性质看起来过去的工作可能都会白做，很无情，但是这恰恰是挖矿公平性的保证。对算力有优势的矿工来说，比如系统只有两个矿工：矿工A、矿工B，A的算力是B的10倍，那么A挖到矿的概率也应该是B的10倍才合理，而如果挖矿概率不满足memoryless，那么A挖到矿的概率是B的10倍多，因为A因为算力大，必然能进行比B更多的尝试，也就是积累经验，就会更容易挖出矿，这是不公平的，不满足puzzle friendly

比特币总量计算

也就是说，比特币系统中已经挖出和未挖出的比特币总数便是2100万个。

实际上，挖矿这一操作并非在解决数学难题，而是单纯的算力比拼。也就是说，挖矿这一过程并没有实际意义，但挖矿这一过程，却是对比特币系统的稳定起到重要维护作用，因为挖矿这一过程实际上能让恶意节点变成少数，大多数算力集中在好的节点手里，从而维护比特币系统的稳定。

比特币越来越难被挖到，且出块奖励越来越少，是否说明其未来挖矿的动力将越来越低呢？
实际上，恰恰相反。在早期比特币很容易挖到的时候，比特币并不被人们所看好，而后，比特币估值上涨，吸引其他人参与挖矿，又进一步促进了比特币价值上涨，进而又吸引更多人参与进来。
当出块奖励趋于0时，则整个系统将依赖于交易费运行，届时交易费将成为维护比特币系统运行的重要保障。

比特币系统安全性分析

大多数算力掌握在好的用户手中，能否保障不良交易记录不会被写入区块链？
需要注意的是，算力低的用户并非完全不能获得记账权，仅仅是概率上较低的问题。但实际上，即使拥有少量算力的恶意节点，也有一定概率获得某个区块的记账权。

那么可能出现一些问题：

能否从其他账户上偷币

也就是恶意节点能不能将其他账户上比特币转给自己？

答案是否定的，因为转账交易需要签名，恶意节点无法伪造他人签名。加入其获得记账权并硬往区块中写入该交易，大多数用户会认为其是一个非法区块，大多数算力将不认可该区块，从而沿着其他路径挖矿，随着时间推移，拥有大多数算力的诚实的节点将会仍然沿着原来区块挖矿，从而形成一条“最长合法链”，该区块变成孤儿区块。对于攻击者来说，不仅不能偷到其他人的比特币，而且得不到出块奖励，还浪费了挖矿花费的电费等成本。

可否将已经花过的币再花一遍

如下图1，若M已经将钱转给B，现在想再转给自己，假设其获得记账权，若按照图1方式，很明显为一个非法区块，不会被其他节点承认。
所以，M只能选择图2方式，将M转账给B的记录回滚掉。这样就有了两条等长合法链，取决于哪一个会胜出，那么是可能发生篡改交易的。（如果上面交易产生不可逆的外部效果，下面交易回滚便又拿回钱，从而不当获益）

注意：在挖矿之初便要选择上一个区块是谁，因为挖矿时设置的block header里包含上一个区块的哈希值。也就是说，并不是获得记账权之后才选择插入到哪一个区块之后。

如何防范这种攻击？

如果再M->A这个交易之后还延续有几个区块，如下图所示，则大多数诚实节点不会承认下面的链。所以，便变成了恶意节点挖下面的链，其他节点挖上面的链的算力比拼。由于区块链中大多数节点为诚实节点，则最终上面链会胜出，而恶意节点的链会不被认可，从而导致投入成本白费。

所以，一种简单防范防范便是多等几个确认区块。比特币协议中，缺省需要等6个确认区块，此时才认为该记录是不可篡改的。平均出块时间10min，六个确认区块便需要1小时，可见等待时间还是相对较长的。

可否故意不包含合法交易？

可以，但是可以等待后续区块包含，所以问题不大。实际运行中，可能由于某段时间实际交易数太多，而一个区块包含交易数存在最大值，导致某些合法交易并未被写入区块链（等待后续区块写入）。

自私的矿工

selfish mining

提前挖到但不发布，继续挖下去，等到想要攻击的交易等了6次确认认为安全之后将整条链发布出去，试图回滚原来记录。这种情况，需要恶意节点掌握系统中半数以上算力才行，否则无法成为最长合法链，等于出块奖励都不要了。

selfish mining有好处吗？

如图所示，假使挖到B时候先不发布，则其他人仍然需要挖A区块，若其算力足够强，能保证别人挖出A之前挖出C.可以此时将B和C一起发布，从而将A区块所在链最长合法链挤掉（减少了别人和自己竞争挖C号区块）。
但这样存在风险，如果别人已经挖出A，自己还没挖出C，则需要尽快发布B和别人竞争最长合法链地位,否则白白浪费了出块奖励。