Hash Function

Cryptographic hash function features:

  1. Collision resistance
    • 碰撞必然存在,但没有已知的高效的方法可以人为制造碰撞(根据过往使用经验得出的乐观假设)。
    • 对于任一哈希函数,数学上尚无法证明其满足这一性质。
  2. Hiding
    • 要求前提:
      • 输入空间足够大;若不满足,则需要人工引入随机性(如拼接上随机数)。
      • 输出的结果分布均匀。
  3. Puzzle friendly
    • 无法预测计算结果,只能穷举去试。
    • Difficult to solve but easy to verify.

Bitcoin 采用 SHA-256 算法。

Hash pointer 保存指向所指对象的“地址”以及所指对象的哈希值(用于判断所指对象是否发生过篡改),这样的数据结构可以用来构建 temper-evident log(区块链)。

  • 只需要保存最新区块的区块头的哈希值,就可以用它来判断区块链是否发生了篡改。
  • 有环的情况下不能用 hash pointer,会造成循环依赖。

生成公私钥和签名时都必须有好的随机源。

  • 私钥 本身就是一个随机数。
  • 签名 时需要生成随机数计算 RS

Merkle Tree

Merkle tree 是用 hash pointer 代替普通 pointer 的 binary tree。

  • 叶节点存放 data blocks,每个 data block 是一笔 transaction;非叶节点存放两个子节点的哈希。
  • 保存根节点的哈希值,就能用它来判断叶节点的数据是否发生了篡改。

由区块中包含的所有交易的构建的 Merkle tree 的根哈希值(Merkle root)保存在区块头中。

Merkle proof 指一笔交易在 Merkle tree 中从叶节点开始到根节点为之的路径。

  • 比特币轻节点只保存了区块头,在收到一笔交易的 Merkle proof 后,可以验证该笔交易是否确实包含在区块里(proof of membership)。

    • 轻节点向全节点请求红色的哈希值,同时自己计算图中绿色的哈希值,最后比对计算出来的 Merkle root 和区块头中的 Merkle root 是否相等。
    • 时间复杂度 O(log(n))n 是叶节点数量。
  • Proof of non-membership:

    • 叶节点按哈希值排序,要证明交易 txX(哈希值是 hashX)不在区块中,只需给出最近的包围了 txX 的两个交易的 Merkle proof,就能证明 txX 是否不包含在区块里。
    • 拿到整棵 Merkle tree,校验所有哈希值,都校验通过,且叶节点不包含某条交易,就能证明该交易不在区块中。

BTC 协议

去中心化数字货币面临的问题:

  • 货币发行规则
    • 挖矿(coinbase transaction)
  • Double spending attack
    • UTXO;每个全节点各自维护全量的 UTXO 集合。

FLP impossibility result:在一个异步(网络时延没有上限)系统中,即使系统中只有一个成员是 faulty 的,系统也无法达成共识。

CAP (Consistency, Availability, Partition tolerance) Theorem: 不可能三角。

  • ChatGPT: Partition tolerance refers to the ability of a distributed system to continue operating despite the failure or partitioning of one or more of its components. This means that the system can continue to function and provide services to its users even if some of its nodes or servers are unavailable or disconnected from the network.

比特币共识不能采用简单的投票机制,因为没有 membership 的概念,无法确定谁有投票权,而比特币的账户可以任意创建无数个。

比特币共识协议按照算力进行投票;接受的区块必须是在扩展最长合法链。

  • 比特币采用 implicit consent,矿工沿着某一个区块继续扩展,就表明矿工认可该区块。

比特币协议用 block reward 和交易费来激励矿工将一切合法的交易打包到区块中。

在等待若干个区块确认后(默认等 6 个,约 1 小时),双花攻击难度增大很多,因为诚实节点的算力占大多数,它们只会在最长合法链上扩展区块,而分叉链的区块只有执行双花攻击的恶意节点在挖,恶意节点只挖到下一个区块显然不够,还需持续挖多个。

  • 包含某条交易的区块被挖出后称该交易获得了 one confirmation,以此类推。

比特币每 2016 个区块(2 周)进行一次难度调整;每 210,000 个区块($$210,000*10/60/24/365 \approx 4 年$$)奖励减半。

比特币总量:$$210,000 \times 50 + 210,000 \times 50/2 + 210,000 \times 50/4 + … = 210,000 \times 50 \times 2 = 21,000,000$$

比特币接收到两个冲突的交易时,默认接受首先收到的那笔交易。

区块大小最大为 1M,约能容纳 4000 条交易。

SubsidyReductionInterval: 210000,
TargetTimespan:           time.Hour * 24 * 14, // 14 days
TargetTimePerBlock:       time.Minute * 10,    // 10 minutes
RetargetAdjustmentFactor: 4,                   // 25% less, 400% more
// TargetTimespan / TargetTimePerBlock == 2016

const CheckpointConfirmations = 2016

比特币地址采用公钥哈希是考虑了抗量子安全性,即使能从公钥推到出私钥,由于地址是公钥的哈希,损失了一部分原始信息,即使是量子计算也无法还原。

// https://github.com/btcsuite/btcwallet/blob/v0.16.5/internal/legacy/keystore/keystore.go#L2148

func newBtcAddress(wallet *Store, privkey, iv []byte, bs *BlockStamp, compressed bool) (addr *btcAddress, err error) {

addr, err = newBtcAddressWithoutPrivkey(wallet,
	pubkeyFromPrivkey(privkey, compressed), iv, bs)

address, err := btcutil.NewAddressPubKeyHash(btcutil.Hash160(pubkey), s.netParams())

// Hash160 calculates the hash ripemd160(sha256(b)).
func Hash160(buf []byte) []byte {
	return calcHash(calcHash(buf, sha256.New()), ripemd160.New())
}

区块头

// https://developer.bitcoin.org/reference/block_chain.html#block-headers

// https://github.com/btcsuite/btcd/blob/v0.23.3/wire/blockheader.go#L20

type BlockHeader struct {
	// Version of the block.  This is not the same as the protocol version.
    // This indicates which set of block validation rules to follow.
	Version int32
	// Hash of the previous block header in the block chain.
	PrevBlock chainhash.Hash
	// Merkle tree reference to hash of all transactions for the block.
	MerkleRoot chainhash.Hash
	// Time the block was created.  This is, unfortunately, encoded as a
	// uint32 on the wire and therefore is limited to 2106.
	Timestamp time.Time
	// Difficulty target for the block.
	Bits uint32
	// Nonce used to generate the block.
	Nonce uint32
}
  • The target threshold is a 256-bit unsigned integer which a header hash must be equal to or below in order for that header to be a valid part of the block chain. However, the header field nBits provides only 32 bits of space, so the target number uses a less precise format called “compact” which works like a base-256 version of scientific notation.

交易

coinbase 交易包含一条交易输入,该条交易输入的 SignatureScript 字段用于提供额外的 nonce。

// https://github.com/btcsuite/btcd/blob/v0.23.3/blockchain/validate.go#L81

// A coinbase is a special transaction created by miners that has no inputs.  This is
// represented in the block chain by a transaction with a single input that has
// a previous output transaction index set to the maximum value along with a
// zero hash.
//
// This function only differs from IsCoinBase in that it works with a raw wire
// transaction as opposed to a higher level util transaction.
func IsCoinBaseTx(msgTx *wire.MsgTx) bool {
	// A coin base must only have one transaction input.
	if len(msgTx.TxIn) != 1 {
		return false
	}
	// The previous output of a coin base must have a max value index and
	// a zero hash.
	prevOut := &msgTx.TxIn[0].PreviousOutPoint
	if prevOut.Index != math.MaxUint32 || prevOut.Hash != zeroHash {
		return false
	}
	return true
}

// https://github.com/btcsuite/btcd/blob/v0.23.3/btcjson/chainsvrresults.go#L710

// TxRawResult models the data from the getrawtransaction command.
type TxRawResult struct {
	Hex           string `json:"hex"`
	Txid          string `json:"txid"`
	Hash          string `json:"hash,omitempty"`
	Size          int32  `json:"size,omitempty"`
	Vsize         int32  `json:"vsize,omitempty"`
	Weight        int32  `json:"weight,omitempty"`
	Version       uint32 `json:"version"`	// 比特币协议版本号
	LockTime      uint32 `json:"locktime"`
	Vin           []Vin  `json:"vin"`
	Vout          []Vout `json:"vout"`
	BlockHash     string `json:"blockhash,omitempty"`
	Confirmations uint64 `json:"confirmations,omitempty"`
	Time          int64  `json:"time,omitempty"`
	Blocktime     int64  `json:"blocktime,omitempty"`
}

UTXO 结构:

// https://github.com/btcsuite/btcd/blob/v0.23.3/wire/msgtx.go#L236

// TxIn defines a bitcoin transaction input.
type TxIn struct {
	PreviousOutPoint OutPoint
	SignatureScript  []byte
	Witness          TxWitness
	Sequence         uint32
}
    // OutPoint defines a bitcoin data type that is used to track previous
    // transaction outputs.
    type OutPoint struct {
        Hash  chainhash.Hash	// tx id
        Index uint32
    }
    // TxWitness defines the witness for a TxIn. A witness is to be interpreted as
    // a slice of byte slices, or a stack with one or many elements.
    type TxWitness [][]byte

// TxOut defines a bitcoin transaction output.
type TxOut struct {
	Value    int64
	PkScript []byte
}

对于 a 给 b 转账的交易 txX,它的输入中,要给出币的来源和 a(转账方)的公钥;它的输出中,要给出 b(收款方)的公钥的哈希。

  • txX 交易的输入中,币的来源是另一笔交易 txY 的输出,里面同样给出了收款方(也就是 a)的公钥哈希。
  • 公钥哈希和对应的公钥唯一绑定,公钥和私钥唯一绑定,签名分别和私钥(生成签名)和公钥(验证签名)唯一绑定。

挖矿

每次挖矿的尝试都是一个 Bernoulli trial:a random experiment with binary outcome。

多次 Bernoulli trial 构成 Bernoulli process:a sequence of independent Bernoulli trials。

Bernoulli process 具有无记忆性(memoryless)的性质。

对于实验次数很多、每次实验成功概率很小的 Bernoulli process,可以用 Poisson process 来近似。

整个系统的出块时间服从指数分布。

  • 比特币设计的平均出块时间是 10 分钟。
  • 概率密度曲线在 y 轴方向上的任意位置截断,剩下曲线的形状仍和原来一样、仍然服从指数分布,这就是 memoryless 性质的来源。
  • 10 分钟过去后合法区块未找到,平均还是要等 10 分钟才能找到合法区块,即将来还要挖多少时间和过去已经挖了多少时间没有关系(progress free)。
    • 如果 puzzle 不具备 progress free 的性质,则算力强的矿工将获得不成比例(先前累积)的优势。

Selfish mining:算力强的矿工挖到一个 heightA 的区块后先不发布,接着继续挖到 heightA+1 区块(此处没人与之竞争),等到监听到其它节点挖到另一个 heightA 的区块时,再同时把已经挖到的 2 个区块发布出去,让其它矿工做无用功,减少竞争。

出块时间需要保持稳定,如果越来越短,分叉会成为常态。过多分叉不利于系统达成共识,也会导致合法节点的算力分散,更有利于恶意节点进行分叉攻击。

用通用计算机挖矿时,大部分内存处于闲置状态,CPU 中的大部分部件也闲置,挖矿计算哈希值的操作只用到通用 CPU 中的很少一部分指令。用 GPU(主要用于通用大规模并行计算)挖矿也有类似问题,比如没有用到浮点数部件,比特币挖矿只用到整数操作。ASIC 芯片只能计算哈希值,不能承担全节点的其它职责。

矿池的矿工只会做哈希计算,接受矿主的任务分配。矿工挖到 almost valid block(称为一个 share)后就获得了工作量证明,等到矿池真正挖到区块后,再根据各个矿工的 share 进行利益分配。

新币为解决冷启动问题采用已有币的 mining puzzle,称为 merge mining。

// https://github.com/btcsuite/btcd/blob/v0.23.3/mining/cpuminer/cpuminer.go#L198

func (m *CPUMiner) solveBlock(msgBlock *wire.MsgBlock, blockHeight int32,
        ticker *time.Ticker, quit chan struct{}) bool {
    // Choose a random extra nonce offset for this block template and
	// worker.
	enOffset, err := wire.RandomUint64()

    header := &msgBlock.Header
	targetDifficulty := blockchain.CompactToBig(header.Bits)

    // Note that the entire extra nonce range is iterated and the offset is
	// added relying on the fact that overflow will wrap around 0 as
	// provided by the Go spec.
	for extraNonce := uint64(0); extraNonce < maxExtraNonce; extraNonce++ {
		// Update the extra nonce in the block template with the
		// new value by regenerating the coinbase script and
		// setting the merkle root to the new value.
		m.g.UpdateExtraNonce(msgBlock, blockHeight, extraNonce+enOffset)

		// Search through the entire nonce range for a solution while
		// periodically checking for early quit and stale block
		// conditions along with updates to the speed monitor.
		for i := uint32(0); i <= maxNonce; i++ {
        }
}

const (
	// maxNonce is the maximum value a nonce can be in a block header.
	maxNonce = ^uint32(0) // 2^32 - 1
	// maxExtraNonce is the maximum value an extra nonce used in a coinbase
	// transaction can be.
	maxExtraNonce = ^uint64(0) // 2^64 - 1
)

// https://github.com/btcsuite/btcd/blob/v0.23.3/mining/mining.go#L381

func (g *BlkTmplGenerator) NewBlockTemplate(payToAddress btcutil.Address) (*BlockTemplate, error) {}
  • 外层循环更新 coinbase,使 BlockHeader.MerkleRoot 被更新;
    • 区块内的第一笔交易是 coinbase。
  • 内层循环更新 BlockHeader.Nonce
func (b *BlockChain) calcNextRequiredDifficulty(lastNode *blockNode, newBlockTime time.Time) (uint32, error) {
	// newTarget = currentDifficulty * (actualTimespan / targetTimespan)
}

比特币网络

比特币网络是一种 P2P Overlay Network;节点加入网络至少需要知道一个种子节点(seed node);节点之间通过 TCP 通信,有利于穿透防火墙。

每个节点维护一个邻居节点的集合。节点退出网络后,其它节点会将其从邻居节点列表中删除。邻居节点的选取是随机的,没有考虑网络的拓扑结构。

消息在网络中采取 flooding 的方式传播,节点第一次收到消息时将消息传播给所有邻居节点。

消息在网络中传播的特点是 best effort。

Simple, robust, but not efficient.

分叉

分叉分为 state fork 和 protocol fork。

  • state fork 是由于节点之间对当前区块链的状态有分歧而产生的临时性分叉。
  • protocol fork 分为软分叉和硬分叉。

软分叉是临时性分叉。

  • 区块大小减半,大部分节点更新软件。更新了软件的节点挖小区块,形成最长合法链;未更新软件的节点同时认可大区块和小区块,所以也会在最长合法链上继续挖,但挖出的大区块不会被认可,导致做无用功。

硬分叉是永久性分叉,除非所有节点都更新才不会分叉成两条链。

  • 区块大小加倍,大部分节点更新软件。更新了软件的节点挖大区块,同时也认可小区块,形成最长合法链;未更新软件的节点只认可小区块,无法在最长合法链上继续挖,除非升级软件,否则就会永久性分叉成两条链。

References