一. 简介

Bitcoin是基于区块链的一种货币

参考:以太坊白皮书、黄皮书、源代码 / Solidity文档

二. 密码学原理

哈希函数指将哈希表中元素的关键值映射为元素存储位置的函数。

Collision resistance(拒绝碰撞)

哈希碰撞指x不等于y,但是H(x) = H(y)。

可以利用上述性质,对文件计算哈希值,然后校验是否篡改。

但是这个性质并不能在数学上证明,例如对于MD5来说,曾经大家认为它很安全,但现在已经找到了人为制造碰撞的方法。

Hiding

指计算过程是单向的,能通过x得到H(x),但不能通过H(x)得到x。

破解方法有:蛮力求解,即遍历x,要确保x的输入空间足够大,数据分布较均匀。

digital commitment

digital equivalent of a sealed envelope:

在现实世界中,如果一个很有名气的股神提前一天预测某股票涨停,可能会影响真实结果。但是如果不提前公布预测结果,就不知道预测内容是否被篡改。所以要由第三方公正机构(就是这个envelope)来证明。

在电子世界中,我们利用Hash的Hiding性质,将H(x)公布出去,然后再公布x。如果输入空间不够大,可以拼接一个随机数,例如H(x || nonce)。

puzzle friendly

指要得到某个区间的哈希值,只能一个个去试x的输入(没有捷径),可以作为工作量证明(proof of work)。

以挖矿为例,H(block header) 要小于等于 target。区块链是由一个个区块组成的链表,每个区块都有个header,header中有很多域,其中有个随机数,挖矿就是要不断寻找随机数,使得上述表达式成立。

比特币中用的Hash函数是SHA-256 (Secure Hash Algorithm)。

总的来说,就是:difficult to solve, but easy to verify。

公钥和私钥

对于比特币系统来说,开户就是在本地创建一对公钥和私钥的过程。

对称加密体系:使用密钥先加密发送,然后再用该密钥解密(前提是有安全渠道分发给通讯双方)。

非对称加密体系:加密用公钥,解密用私钥。公钥相当于比特币账户,私钥相当于比特币密码。签名用私钥,验证签名用公钥(先对message取一个哈希,然后再对哈希值签名)。

公私钥虽然在本地产生,重复的可能性十分小(要求选取一个好的随机源 a good source of randness)。

三. 比特币的数据结构

哈希指针不仅要保存地址,还要保存结构体的哈希值。通过哈希指针不仅能找到数据的位置,还能检测出数据有没有被篡改(因为保存了哈希值)。

区块链

区块链就是一个个区块(block)组成的链表。和普通链表的区别是:用哈希指针代替了普通的指针

区块链表

取哈希的时候是把整个区块的内容(包括其保存的指向下一个区块的哈希指针)一起取哈希。

使用这种数据结构可以实现tamper-evident log(防篡改日志),即如果某个区块被篡改,会导致最后与系统保存的的哈希值对应不上。

用户可以只保存最近的一些区块,如果要用到以前的区块,可以找别的节点要,然后通过上述性质去验证别人给的块是否正确。

Merkle tree

用哈希指针代替了普通二叉树中的普通指针,最底下的一层叶子结点是数据块,其上的若干层非叶子结点都是存储哈希指针的。

Merkle tree

只需要记住根哈希值,可以检测出data block是否被修改。在比特币系统中,每个data块相当于一次交易

结点

在区块链中,每个区块分为两部分,块头(block header)和块身(block body)。在块头中存储了这个区块所包含的所有交易组成的Merkle Tree的根哈希值。只在块身中存储了交易列表

全结点:既有块头又有块身的区块,保存了交易的具体信息。

轻结点:只保存了块头,没有保存块身。例如手机上的比特币钱包就使用的是轻结点。

如何向轻结点证明某个交易是写入了区块链的?

Merkle proof

交易的data块到根结点的路径,时间复杂度是θ(logn)。

Merkle proof

要证明某个交易不存在,先对data block的哈希进行排序,然后二分查找,但是比特币中不需要证明交易不存在。

只要数据结构是无环的,都可以用哈希指针替代普通指针,否则会出现循环依赖。

四. 协议

数字货币与纸质货币

直接为货币的面额等信息,用央行的私钥签名,然后使用的时候,用户直接拿央行的公钥验证签名。

问题:虽然保证货币的真实性,但是会遇到 花两次攻击(double spending attack),不像纸质货币,花出去了就没了。

解决方法:中心化方法,再维护一个数据库保存数字化货币对应的用户。那么去中心化的方法呢?

去中心化

数字货币举例

BTC系统中每个交易都分为输入部分和输出部分,输入部分要给出这笔交易的BTC的来源以及付款方的公钥,输出部分要给出收款人的公钥的哈希值。比如A要转给B钱,就需要给出B的哈希。

这里涉及两种哈希指针,将各个区块串起来的哈希指针;另一种是为了说明币的来源是从哪个交易来的。

收款地址:通过 收款人的公钥取哈希再经过一些转换 得到。

A转账给B,收款的时候,B要知道A的公钥,因为要验证A的签名。

区块结构

Block header :

  1. Version
  2. 指向前一个区块的哈希指针,这里的哈希值是通过计算前一个区块的块头得到的
  3. Merkle root hash:整颗Merkle Tree的根哈希值
  4. Target:挖矿难度目标阈值
  5. Nonce:挖矿用的随机数,目标是H(BlockHeader)小于等于target

Block body :

  1. 交易列表

分布式共识 distributed consensus

区块链可以看成去中心化的账本,如何保证写入区块后的一致性?账本的内容要取得分布式的共识

分布式系统的不可能结论 impossibility result

  • FLP impoossibility result

    在一个异步的系统中,网络传输时延没有上限,即使只有一个成员有问题(faulty),也不能取得共识。

  • CAP Theorem

    任何一个分布式系统,Consistency一致性、Availability可用性、Partition tolerance分区容忍性,只能满足其中两个。

BTC共识机制

投票方式(按照账户数量):

将所有交易写入一个候选区块,然后发给所有结点,大家验证这个区块中的交易是不是都是合法的,然后投赞成和反对票,按一定投票比通过后将候选区块写入区块链中。

但是存在membership问题,即谁有投票权,例如hyperledger(联盟链)只有一些大公司可以加入。

还可以进行sybil attack(女巫攻击),只要不断产生账户,就可以取得大量投票权并控制区块链。

比特币投票方式(按照计算力):

每个结点在本地组装一个候选区块,把认为合法的区块放进去,尝试各种nonce值,使得H(BlockHeader)小于等于target。如果找到了nonce,就获得了记账权,其他结点收到这个区块后要验证合法性。

分叉攻击

候选区块如果合法就接收吗?检查有没有double spending是看一条链上有没有花过两次,如果有分叉呢?

分叉攻击

上面转账给自己的区块是合法的,但是不应当被接受(以最长合法链为准)。

如果一个结点收到一个区块后,沿着这个区块继续往下扩展,那么就算该结点接受了这个区块

如果两个结点同时获得记账权,都能插入候选区块,会维持多条最长合法链的情况,直到某个分支找到了下一个合法区块,另一个区块就会变成orphan block。

出块奖励

为什么要去竞争记账权?BTC系统设计来希望所有交易都能被公平写入账本。出块奖励机制解决了这个问题。

根据BTC协议,获得记账权的结点,在发布的区块可以进行铸币交易,可以发布一定数量的BTC(产生新BTC的唯一方法),不用指定币的来源。最早的时候,BTC出块奖励是50个,规定每21万个区块后奖励减半。

如今(2022.11),1 BTC 的价值大约在2万美元左右,比最开始的时候值钱了很多,所以虽然现在奖励少了,但是依然会有很多结点去竞争记账权(挖矿)。

五. 实现

BTC采用的是基于交易的账本模式(transaction-based ledger),只记录了转账交易和铸币交易,并没有直接记录每个账户上有多少钱。如果想知道某个BTC账户上有多少钱,要通过交易记录来推算。

相反,以太坊采用的是基于账户的账本模式(account-based ledger)

UTXO(Unspent Transaction Output):没有被花出去的交易的输出

UTXO举例

UTXO集合中的每个元素要给出产生这个输出的交易的哈希值,以及它在这个交易中是第几个输出。用这两个信息就可以定位到一个确定的交易中确定的输出。

使用UTXO可以用来快速检测双花攻击,想知道新发布的交易是不是合法的,要查一下全结点存在内存中的UTXO。要花掉的币只有在这个UTXO这个集合里才是合法的,否则要么是不存在的,要么是已经花过了的。

如果一个人拥有比特币一直不花,那么这个记录会永久存储在UTXO中。

交易费(transaction fee)

有些交易的总输入可能略微大于总输出(total inputs > total outputs),

例如总输入是1BTC,总输出是0.99BTC,其中的差额作为记账费给了获得记账权的结点(为了激励别人去记账)。

有些简单的交易可能没有交易费。

区块举例

区块举例

块头结构

1
2
3
4
5
6
7
8
9
10
class CBlockHeader
{
public:
int32_t nVersion;//BTC版本号,没法改
uint256 hashPrevBlock;//前一个区块块头哈希值(32字节):不能改
uint256 hashMerkleRoot;//通过修改Merkle Tree中铸币交易的CoinBase域来调整其根哈希值
uint32_t nTime;//区块产生时间,有一定的调整余地,BTC系统并不要求非常精确的时间,这个域可以在一定范围内调整
uint32_t nBits;//挖矿目标阈值编码后的版本,只能按照协议中的要求定期进行调整,不能随便改
uint32_t nNonce;
}

实际挖矿时,一般也是为此设计了两层循环,外层循环调整铸币交易的CoinBase域的extra nonce,然后算出Merkle Tree的根哈希值;内层循环调整块头的nonce,计算整个块头的哈希值。

交易举例

交易举例

概率分析

伯努利实验,由于n(次数)很大,p(概率)很小,近似泊松分布。

公平性保证(progress free)

出块时间服从的指数分布也是无记忆性的, 也就是说从任何一个位置将其截断,剩下的部分仍然是服从指数分布的。“将来还要挖多少时间”和“过去已经挖了多少时间”没有关系