Skip to content

Latest commit

 

History

History
254 lines (168 loc) · 7.3 KB

Week1-BTC.md

File metadata and controls

254 lines (168 loc) · 7.3 KB

Week 2: Introduction & BTC

Distributed Ledger

Types

  • Permissioned: 只有可信的用户可以加入和创建 Tx
  • Permissionless：对加入和创建 Tx 没有 Authorisation

Blockchain

Components

  • State (Data Storage): Blocks BTC 中块由
    • Block Header 80byte <version><prev_block_header_hash><merkle_root_hash><time>...<nBits><nonce>
    • Transaction 数量: txn_count
    • Transactions: txns
  • Ensuring Immutability: 密码学技术
    • Hash
    • Merkle Tree
  • Confirming State Updates: Consensus Algorithm
    • Proof of Work
  • Sending State Updating: Transactions

Cryptography

Hash

对于 Hash 函数 $H$:

  1. Preimage Resistance (hiding): 对于给定哈希 $h$，很难找到其输入 $x$ 使 $H(x)=h$​ $$ x\to H(x)\ \text{Given } H(x):\ x\cancel{\rightarrow}H(x) $$

  2. 2nd preimage resistance: 对于给定输入 $x$ 哈希函数 $H$，很难找到另一个输入 $x'$ 使得 $H(x)=H(x')$​
    本质上是防止攻击者通过已知的消息-哈希对找到另一个具有相同哈希值的不同消息。 $$ x\to H(x)\ \text{Given }x, H:\x'\cancel{\to} H(x)\ \text{where } x'\neq x, $$

  3. Collision resistant: 对于一个哈希函数 $H$，很难找到两个不同的输入 $x$ 和 $x'$ 使得 $H(x)=H(x')$​
    防止攻击者找到任何哈希值相同的两个不同消息 $$ \text{Given }H:\ x \to H(x), x'\to H(x')\ H(x) \neq H(x')\ \text{where } x \neq x' $$

Public Key Cryptography

flowchart LR
  W[Wallet]
  SK[Digital Keys]
  W --Stores--> SK
  Addr[Unique Address]
  SK --Associate/Owns--> Addr
Loading

公钥密码学包含 $(sk, pk)$。BTC 使用 ECDSA (Elliptic Curve) 作为基础。

$sk$ 是 $1-2^{256}$ 的随机数 + $pk$

flowchart LR
  sk --Derives--> pk
  pk --Derives--> Addr[BTC Address]
  sk --Sign Message--> sign[Signature]
  pk --Verify--> sign
Loading

在比特币中签名信息：

Pseudorandom Number Generator (PRNG) & Generate Address

伪随机数生成器允许生成一系列看上去随机的数字。其需要 Seed 值用于生成随机。相同 Seed 给出相同随机数 series。

flowchart LR
  sk[Private Key] --EC Multiplicationh<br>Irreversibl--> pk[Public Key]
  pk --Hash<br>Irreversible--> Address
Loading
  • 通常使用 Seed Phrase（一个随机单词List），生成 Seed。
  • Seed + PRNG = sk
  • sk 生成不同 pk
  • address = hash(pk)

PoW

PoW 是比特币的 consense 算法。节点通过生成有效的 PoW 解判断新的 Tx 是否应该被 Appened 到 blockchain 里。 $$ \text{PoW} \Rightarrow \text{SHA256}(\text{SHA256()}) \leq \text{Target} $$ Candidate Solution 是一个 block 头的哈希，即矿工需要通过构建新的块，使得块头的双重 Hash 落到 Target 的范围内。

Target 是怎么调整难度的

我们考虑 SHA256，即搜索空间为 $2^{256}$，考虑目标空间为 $[0, \text{Target}]$，即有找到的概率为： $$ p=\frac{\text{Target}}{2^{256}} $$ 对于一个独立事件，我们对尝试的期望为 $1/P$ 此才能找到有效解，即 $$ \mathbb{E}(\text{期望尝试 hash 的次数}) = \frac{1}{p} =\frac{2^{256}}{\text{Target}} $$ 块解密事件遵循泊松分布（Poisson Distribution），Mean=10min。我们可以调整 $Target$ 来调整解密时间

Difficulty 表示有多难找到一个有效的 PoW 解，即其可以调整 PoW 的 Target 值。越小的 Target 值意味着越难找到一个有效的 PoW 解。

Target 是位于 Block Header 的一个名为 nBits 的参数。区块链会自动更新。

对区块头做SHA256运算，如果结果小于等于一个目标值（target），则新块构建成功，广播到全网，随后开始下一次算力竞赛 否则，调整区块头部分字段的值（修改 Nonce 或者通过调整交易来修改 Merkle Root Hash），重新做计算

Partial pre-image attack (Puzzle Friendly): 生成有效解很难，使用 pre-image 验证 Hash 很容易。

Mining 挖矿

矿工挖矿选择交易是因为

  • Transaction Fee（$\text{TX}\text{output} - \text{TX}\text{input}$）
  • Block Reward 出块奖励（新增块会奖励的 coin）
    • 奖励大约每4年 halves

Transaction

flowchart LR
  C[Create<br>创建]
  S[Signed<br>签名]
  P[Propagated<br>传播]
  V[Validated<br>验证]
  A[Added to blockchain<br>添加到区块链]
  C ---> S ---> P---> V ---> A
Loading

300-400byte的数据

<version><input_counter><inputs><output_counter><outputs><lock_time>

type Transaction {
	Version       string
    InputCounter  int              = len(Inputs)
    Inputs        []UTXO.Address
    OutputCounter int              = len(Outputs)
    Outputs       []UTXO.Address
    Locktime      time.Date
}

UTXO (Unspand Transaction Output)

BTC 全节点在内存会维护 UTXO 表。

BTC 的额度（amount）被链接到一些地址，无论谁收到BTC都会被记录为 UTXO。

一个交易消耗一个或多个 UTXO。且 UTXO 必须被完整消耗。 例如 我有一个地址 0x0001 有 10 BTC，我想给 0x0002 5 BTC，那么我需要创建两个 UTXO，一个有 5 BTC，另一个有 5 BTC。

消费 BTC = 创建一个属于recipient 的 UTXO

Transaction Inputs:

  • 用于消耗 UTXO 的交易（Tx Hash + Sequence No)
  • 达到 Speeding Conditions 的解锁脚本（e.g., 用于证明所有人的签名）

Transaction Outputs:

  • Transaction 构建的 UTXOs (Amount + Locking Script)

Transaction Fee: Inputs - Outputs

Forks

Longest Chain Rule

Block Tree 区块树：所有有效区块，其先前链接的区块已知（直到创世区块）。

Active Chain 活动链：从 Genesis Block 到区块树叶节点的单一路径（每条路径都是有效路径），但是，节点会选择执行“工作”最多的一条路径（难度总和）

Soft Fork

协议变更有对老协议有 Backward Compatible：老协议承认新协议，但是新协议可能不承认老协议

本质：增加限制

例如将区块大小调整为原来的一半。老协议承认小块，但是新协议不再承认新的小块。

超过半数矿工更新，就不会产生永久性分支。

Hard Fork

协议变更产生（incur）区块链的 permanent spilt （无向后兼容）：老协议不承认新协议

本质：放宽限制

例如增加区块大小。

通常需要全部参与者接受更新。

Merkle Tree

对于编码 Transaction 和其他通用状态，我们期望编码：

  • Compact: Input 的编码必须是固定大小 Merkle 树从叶节点通过 Hash 构建。

  • Tamper Proof: 修改输入必须导致输出编码变更

  • Efficient Encoding & Lookup: 编码必须是线性时间，且存储，lookup/inclusion verification 必须尽可能块

    允许在对数时间内构建 Inclusion Proof 允许在对数时间、存储验证 Inclusion Proof

Merkle Proof

Pseudoanonymity / 伪匿名性

Anonymity: Tx 和 活动不能被链接到任何 actor

Pseudoanonymity: Tx 和 活动可以被连接到特定 Actor。但是 Actor 的真实世界 Identity 是不知道的。地址是 Pseudonym（假名）