区块链学习笔记[持续更新]

资料收集

比特币的密码学原理

cryptographic hash function

collision resitance

因为鸽笼原理，一定存在
(x eq y) and (H(x)=H(y))
使用brute-force找到这样的(x)和(y)但效率低
collision resitance 用来对一个message求digest，用以检测篡改
无法篡改内容而使digest不改变
collision resitance暂未被数学证明，通过大量实践证明一些哈希函数具有这个性质。如MD5曾经流行，但现在已经有方法制造哈希碰撞
应用：上传文件到云空间前取哈希值，若下载后发现digest没变，则没被篡改

hiding

哈希函数的计算是单向的。
(x→H(x))可行
(H(x)→x)不可行（只能使用brute-force，有生之年无法求解）

digital commitment

又叫做digital equipment of sealed envelope
比如说预测股票，提前公布结果，可能会影响结果。把结果封在信封里，交给第三方信用机构保管。结果出现后启封。
密码学实现：将预测结果的哈希值公布，出现结果后再公布预测结果。
因为其hiding和cllision resitance的性质，这就实现了一个sealed envelope。
实操细节：hiding的性质，输入空间足够大，分布均匀。在输入(x)后拼接一个nonce值（随机），输入变为(H(x||nonce))。
挖矿就是计算nonce值。

puzzle friendly

无法预先知道，想要构造的一定范围内哈希值，需要什么样的输入。
挖矿：(H(bock head) leq target)
puzzle friendly 性质表面挖矿只能靠随机猜nonce。因此可以作为工作量证明。挖矿很难，而验证nonce是否符合要求很容易。

difficult to solve, but easy to veryfy

SHA-256

Secure Hash Algorithm
满足collision resistance,hiding,puzzle friendly三个性质。

账户管理

一个账户：(public key,private key)
asymmetric encryption algorithm
~~笔者已经熟悉对称加密和非对称加密，故此部分不作笔记。~~
非对称加密用于签名
很难产生相同的公私钥，概率忽略不计。目前还无通过生成已有公私钥对窃取比特币的先例。
这需要一个a good source of randomness
为了保证效率，比特币系统中通常先对message取hash，然后对hash作签名

数据结构

hash pointers

包含位置和哈希值，检测是否被篡改

Block chain is a linked list using hash pointers.

“表头” 是创世块，genesis block。最新的是most recent block。
把前一个区块的所有内容（包括该区块再前一个区块的哈希值）取哈希，是下一个区块中哈希指针的哈希值。
这样就有tamper-evident log，改变任何一个区块，后面所有区块都得跟着改。这样只需要校对最后一个区块和该区块哈希，就能校验整个区块链是否被篡改。
这样网络中部分结点就可以不保存整条链。

Merkle tree

类似binary tree，但把指针换为哈希指针。

默克尔树只要记住根节点的哈希值，就能检测所有data blocks是否被篡改。
在区块链中，每一个data block都记录了一笔交易tx。
在block header里只有merkle tree的根哈希值，在block body里有交易的具体内容。这样就能实现merkle proof。证明存在某个交易。

merkle proof

proof of membership
区块链网络中，有全结点和轻结点（比如手机的区块链钱包）。轻结点中只存merkle的根哈希就行。
轻结点向全结点发出请求，请求证明一个待证明tx的合法性，只需请求部分哈希值，就能算出根哈希值，与block header里的哈希值比较，就能得到合法性。
被请求的全结点无法伪造，因为collision resistance性质。
时间复杂度是(mathcal{O}(logn))
如果是proof of non-membership
如果传整棵树作验证，那么就是(mathcal{O}(n))

协议

中心化系统数字货币会面临double spending attack
去中心化系统面临：货币发行，如何验证货币有效性。

block header

version
hash of previous block header
merkle root hash
target
nonce

block body

transaction list

distributed consensus

e.g. distributed hash table

FLP impossible result

在一个asynchronous system中，网络传输迟延没有上线，即使只有一个成员是faulty，也不可能达成共识。

CAP Theorem

Consistency 一致性
Availability 可用性
Partition tolerance 分区容错性
最多只能满足两个性质

Consensus in BitCoin

sybil attack

如果某个组织掌握一半的账户，就能控制区块链网络

forking attack

longest valid chain
在正常运行中也可能出现分叉，比如同时挖出矿。
后继链长的合法，另一个就是orphan block。
coinbase transaction

实现细节

transaction-based ledger

UTXO：Unspend Transaction Output
total inputs = total outputs(不考虑手续费)
transaction fee

每隔21w个区块奖励减半。设计平均每10min出一个区块。
每隔4年减半。

account-based ledger

bock header

class CBlockHeader{
public:
    int32_t nVersion;
    char hashPrevBlock[32];//uint256
    char hashMerkleRoot[32];
    uint32_t nTime;
    uint32_t nBits;
    uint32_t nNonce;
}

挖矿

如果挖矿难度过大，可以修改coinbase的extra nonce，进而修改merkle root，增加搜索空间。
每次尝试nonce都可以认为一次Bernoulli trial。
这些Bernoulli trial组成Bernoulli process：a sequence of independent Bernoulli trial.
特点：memoryless
可以近似为Poisson process，推导出出块时间服从exponential distribution。通过调整难度，控制系统出块时间为10min左右。

probability density

progress free，过去的尝试不影响未来的可能时间。期望挖10min，已经挖了10min，如果没挖出，期望还需要挖10min才能挖出。
如果设计出过去的工作能影响将来成功概率，那么算力强的矿工会获得不成比例的优势。

比特币的总量

geometric series

(21万 imes 50 imes （1+frac{1}{2}+frac{1}{4}+...) = 2100万)
比特币的总量一共2100万个。
挖矿求解的puzzle本身无意义，但挖矿的过程对维护比特币系统的安全性至关重要。

安全性

假设大部分算力掌握在诚实的人手里，只能说比较大的概率，记账权在诚实结点。
难以偷币，因为难以伪造签名。
扩展最长合法链

foking attack

解决办法：等六个confirmation，即1h。
最长链原则

zero confirmation

收款方使用全结点，验证交易合法后，就认为交易完成。且商家发货，会有时间延迟。被foking attack的概率极低。

selfish mining

一次性挖到六个区块，然后进行foking attack
成功率极低

网络

application layer: Bitcoin Block chain
network layer: P2P Overlay Network
加入网络需要seed node
通过TCP通信，有利于穿过防火墙
沉默一段时间即表示退出网络
原则：simple,robust but not efficient
flooding:第一次收到某消息，就转发给邻居结点。邻居节点不考虑底层实际拓扑结构，效率低。
区块不大于1MB