A/B

Btc学习

2022/04/12

BTC 学习笔记

密码学原理

hash 三个特性

  • collision resistance：碰撞抵抗，防止两个不同的输入生成同样的输出
  • hiding：无法通过hash的输出推断出hash的输入，这需要很大的输入集，并且输入集足够分散
  • puzzle friendly：无法预测hash的输出，从而使得挖矿过程没有捷径

设计原则：difficult to slove,easy to verify

比特币使用的 hash 函数为：SHA-256（Secure Hash Algorithm-256 bit）

账户

创建账户的过程不需要中心化的操作，仅需要符合非对称加密的公钥/私钥。

签名

  • 签名使用X的私钥
  • 验证签名使用X的公钥
  • 不仅账户创建是需要随机元，签名的时候也需要随机元

基础数据结构

hash 指针

hash pointer is a pointer with hash degist,avoid tamper-evident problem.

Block chain is a linked list using hash pointers

默克尔树

一种二叉树，叶子结点为数据块，保存交易；非叶子结点则为叶子结点的hash值。用于实现 merkle proof。

轻节点如何判断一个交易是否包含在一个块内？根据任意一个叶子结点，算出其hash，同时向全节点请求（二叉树）另一边的hash，最后算出根hash，和链上的数据进行比对。

同理，存在有序默克尔树，叶子结点按照hash进行排序，在 BTC 中没使用到。

数据结构

Block Header

  • version
  • hash of previous block header
  • merkle root hash
  • target
  • nBits
  • nonce

Block Body

  • transaction list

防范双花问题

在整个链上，除了hash指针指向前面的数据防止整个链被篡改，链上的交易数据还需要一个hash指针指向币的来源。

在交易过程中，A向B发起交易：

  • A 需要知道 B 的公钥（这个过程比特币不实现，可以通过现实的广而告之实现），然后发起一笔交易，交易数据还需要包括自己的钱是从哪里来的
  • B 和其他所有账户都需要知道 A 的公钥（这个会写在交易信息中）
  • 铸币交易（coinbase tx）中也会显示 A 的公钥，所以 A 只能拿自己的钱进行交易，自己的钱一旦交易了就会被记录

分布式共识协议

CAP Theorem

  • 一致性（Consistency） （等同于所有节点访问同一份最新的数据副本）
  • 可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
  • 分区容错性（Partition tolerance）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择）

根据定理，分布式系统只能满足三项中的两项而不可能满足全部三项。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

投票决议

简单的投票是无法防范女巫攻击的。

Proof of Work

节点通过工作量证明（尝试多种nonce，在 puzzle friendly的限制下，获得 target 内的nonce）获得记账权，获得记账权的节点有权利在链上更新区块，同时获得铸币奖励。

如果同时有多个节点获得了记账权，那么此时链就不是一条 longest valid chain，对于其他节点来说先接收到哪个节点就算是在自己视角内的 longest valid chain，但这只是暂时的。在后面的区块公布后，所有节点需要剪除短链，而去修改为最长的合法链，那么在短链上的所有交易都失效，新的计算都在最长链上。

存在一种合法的区块，但是它的 hash of previous block header 比较靠前，此时就会出现分叉攻击，如果它周围的节点获取信息比较慢，还没有更新到最长的链上，那么就会相信这个区块。

实现

比特币使用 transaction-based ledger，就是 UTXO 模型。

UTXO: Unspent Transaction Output 数据结构，尚未花費的區塊鏈交易的輸出。快速判断双花问题。在一笔交易中，可以有多个input，输出至多有两个，輸入 = 輸出。可以参考：什麼是UTXO?

挖矿过程中需要对 block header 求 hash，使得其符合前n为为0（也是通过调整n调整难度）。block header 里的数据一开始可变的就是 nonce，是uint32类型，但当前挖矿机器太多，n已经变得很大，所以即便遍历 nonce 都无法求解，这时候需要改变默克尔树的根hash。但是默克尔树的根hash是根据叶子结点的交易来计算的，除非修改底层的交易信息，否则无法修改该hash。但是有一类交易是特殊的，就是铸币，铸币的时候可以提交一些信息，这些信息可变，当这些信息变化后，对应的默克尔树根hash就变了。通过修改 默克尔树的根hash和nonce，使 block header 的 hash 可以落在 target 内。

self mining：

  • 恶意节点在某个（比较早发布的）区块下算出了另一个区块，并在这个区块下继续挖，假设恶意节点的算力可以大于50%，那么在某个时间后突然公布这条新链，就会挤掉另一条链，做交易回滚，但一般操作性不大
  • 另一种情况是，某个恶意节点算出了新的区块，但是不公布，此时其他节点还在基于前一个区块进行挖掘，而恶意节点根据自己算出的新的区块进行计算，这是会出现两个结果：
    • 区块提前被其他节点挖出来了，而恶意节点更新的区块还没找到，只能立刻发布，此时就属于抢夺过程，看两个块在网络上的接受度。但恶意节点已经进行了一段时间的计算，理论上说优势会大点，等于拿丢块的风险换下一个块的计算时间
    • 恶意节点连续挖出了两个块，此时链上只出现了一个块，此时公布出来就可以挤掉另一个链，和上述情况类似

网络

P2P Overlay Network。

新的节点需要先联系 Seed node 然后和其他节点获得对等连接。

  • 简单
  • 高容错
  • 不高效

为了上述的实现，使用 flooding 方式进行数据传输。传输成本太高，所以限制每个块的大小小于1MB，这也意味着块内的交易数据是有限的。

挖矿难度

H(block header) <= target

挖矿难度是和 target 成反比。挖矿难度是需要保证的，维持出块时间的稳定，减少分叉的出现，从而更难达成共识。

  • target 指的是一个 256 位的数，需要保证 H(block header) <= target，简单的理解就是限制hash值开头的 0 的数量
  • 正常出块时间为10分钟
  • 每2016个区块调整难度，约14天

tartget = target * ((actual time)/(expected time))

  • actual time 为实际上的最近 2016 个块花费的时间
  • expected time 为预期的最近 2016 个块花费的时间
  • 如果实际时间大于预期时间，意味着挖矿变难了，那么 target 就会变大，对于前 n 个0的这个 n 就会减小，反之同理
  • 但在真实的系统中还有有个四倍的上限设计或者1/4的下限设计，即实际花费时间最大为56天，最小为3.5天，因为会出现特殊情况，例如全球网络波动、全球电力波动、全球矿工波动等等，难度的调整也不会是一蹴而就的，而是多个 2016 个块的时间内实现的。
  • 通过 block header 的 nBits 作为难度记录，防止难度没有进行同步

挖矿

  • 全节点挖矿
  • 矿池挖矿

对于全节点挖矿，比较容易理解，就是独立的节点进行挖矿，但现在挖掘的难度很大，全节点挖矿的收益非常不稳定，因为 progress free/memoryless 的特性，当前块的挖掘消耗但没产生收益并不会使下个块更好挖，所以现在更多的是用矿池的模式进行挖矿。

对于矿池来说，需要解决两个问题：

  • 矿工的收益如何确定？矿主通过一些协议，降低挖矿的难度，假设当前的难度为 n，那么设计的难度为 n/100，此时产生的结果对于整个区块链来说是没有意义的，但可以证明该矿工确实做了运算，这个结果也叫做 almost valid block
  • 矿主的收益如何确定？这里其实也会分两个问题，一个问题是矿工挖到了会不会私吞？一个问题是矿工挖到了会不会恶意瞒报，直接丢弃？
    • 对于第一个问题是不会私吞，因为私吞没有意义，block header 的 默克尔树根hash 是确定的，这意味着铸币交易的地址就是矿主的，即便是矿工挖到了直接发布，收益也是矿主的；矿工也无法修改铸币交易的地址，一旦修改了，默克尔树根hash就会变化，返回给矿主的 almost valid block 也不会作数
    • 恶意瞒报这个情况是无法避免的，对于该矿池内的矿工是损人不利己，但该矿工可能是内奸，从另一个矿池获取收益。对于这类问题可以在任务分配的过程中进行设计，比如说同样的nonce分配给多个矿工计算

但是矿池的出现，使得分布式程度降低，链更容易被攻击。

  • 分叉攻击：矿池的算力达到一定规模即可发动。矿工全程无感知，只负责计算很无辜
  • Boycott：池内对某个账户的恶意攻击，在某个账户进行交易后直接进行分叉

脚本

P2PK：Pay to Public Key

input script:
    PUSHDATA(Sig)

output script:
    PUSHDATA(PubKey)
    CHECKSIG

exec:

PUSHDATA(Sig) # 签名入栈
PUSHDATA(PubKey) # 公钥入栈
CHECKSIG # 弹出两个元素，检验签名

P2PKH: Pay to Public Key Hash

input script:
    PUSHDATA(Sig)
    PUSHDATA(PubKey)

output script:
    DUP
    HASH160
    PUSHDATA(PubKeyHash)
    EQUALVERIFY
    CHECKSIG

exec:

PUSHDATA(Sig) # 签名入栈
PUSHDATA(PubKey) # 公钥入栈
DUP # 栈内复制公钥
HASH160 # 栈内弹出公钥取hash后再入栈
PUSHDATA(PubKeyHash) # 把输出脚本里提供的 PubKeyHash 压入栈
EQUALVERIFY # 弹出栈内两个元素，对 PubKeyHash 验证相等
CHECKSIG # 弹出两个元素，检验签名

P2SH: Pay to Script Hash

采用 BIP16 方案

input script:
    ...
    PUSHDATA(Sig)
    ...
    PUSHDATA(serialized redeemScript)

output script:
    HASH160
    PUSHDATA(redeemScriptHash)
    EQUAL

exec:

- input script 给出的一些签名（数目不定）及一段序列化的RedeemScript
  - 验证序列化的redeemScript是否与output script中的hash值匹配
  - 反序列化并执行 redeemScript，验证input script中给出的签名是否正确

- RedeemScript 的形式 
  - P2PK 形式
  - P2PKH 形式
  - 多重签名形式

exec:

phase1:check redeemScript
FALSE # 压入无用数据
PUSHDATA(Sig_1) # 压入签名1
PUSHDATA(Sig_2) # 压入签名2
PUSHDATA(seri RedeemScript) # 压入序列化的 RedeemScript
HASH160 # 对上一步的 RedeemScript 进行 hash
PUSHDATA(RSH) # 压入 Hash 后的 RedeemScript，该值直接被提供，不是临时计算出来的
EQUAL # 栈上弹出两个元素，进行相等计算，true则进入阶段2

phase2:check sign
2 # 压入m，即签名数
PUSHDATA(pubkey_1) # 压入公钥1
PUSHDATA(pubkey_2) # 压入公钥2
PUSHDATA(pubkey_3) # 压入公钥3
3 # 压入n，即公钥数
CHECKMULTISIG # 内部实现的多签检测

Proof of Burn
销毁脚本，即 output script 直接 return xxx，定义为否，交易永远无法完成，但币可以被销毁或者被支付费率，作用是证明。

fork

state fork：临时性的分叉。同时多个节点发布了新的区块，也都是合法的，此时链就处在分叉状态。 protocal fork：由于协议不同导致的分叉。 hard fork：硬分叉，就是分叉后的两条链没法剪枝，一个明确的例子就是 block size limit 的修改，这也是协议升级后的一个新的特性。部分节点升级后支持大容量的块，然后形成了链；但是没升级的节点永远都无法认可另一条链，而在自己的链上一直走下去。在没有解决措施前，两个链都是合理的，但这会带来一些问题，两条链上的账单需要独立，但是有同样的头，这样的情况下双花就可以普遍存在。 soft fork：软分叉，不会造成永久性的分叉，这可以体现在协议更新后的兼容问题，新节点不认旧节点提供的区块，而旧节点又必须承认新节点提供的区块，所以会一直出现软分叉，过段时间分叉消失。

匿名性

隐私保护。比特币可以说是匿名的，但匿名性是有限度的。

匿名是因为交易的地址（账户）是随时可生成的公私钥，而公私钥和现实中的个体很难产生联系。

但是比特币上的所有交易都是公开可查的，通过一些分析手段可以把部分账户归集为现实中的一个实体。当比特币的交易从链上和现实产生了交互，场内场外皆可能泄漏身份。包括但不限于：资金的转入转出，比特币支付。

作为用户如何提升匿名性？

  • 网络层匿名：多路径转发
  • 应用层匿名：coin mixing

零知识证明

零知识证明是指一方（证明者）向另一方（验证者）证明一个陈述是正确的，而无需透露除该陈述是正确外的任何信息。

同态隐藏

  • 如果x，y不同，那么它们的加密函数值E(x)和E(y)也不相同
  • 给定 E(x)，难以反推 x 的值
  • 给定 E(x) 和 E(y) 的值，我们可以很容易的计算出某些关于x，y的加密函数值
    • 同态加法：通过 E(x) 和 E(y) 计算出 E(x+y) 的值
    • 同态乘法：通过 E(x) 和 E(y) 计算出 E(xy) 的值
    • 扩展到多项式
Alice 想要向 Bob 证明她知道一组数 x 和 y 使得 x+y=7，同时不让Bob知道x和y的具体值。

简单实现：
- Alice 把 E(x) 和 E(y) 的数值发给 Bob
- Bob 通过收到的 E(x) 和 E(y) 计算出 E(x+y) 的值
- Bob 同时计算 E(7) 的值，如果 E(x+y) = E(7)，那么验证成功

盲签方法

- 用户 A 提供 SerialNum，银行在不知道 SerialNum 的情况下返回签名 Token，减少 A 的存款
- 用户 A 把 SerialNum 和 Token 交给 B 完成交易
- 用户 B 拿 SerialNum 和 Token 给银行验证，银行验证通过，增加 B 的存款
- 银行无法把 A 和 B 联系起来

通过零知识证明，实现零币和零钞，从而减少加密货币的直接使用，增加隐私性。

  • 零币和零钞在协议层面就融合了匿名化处理，其匿名属性来自密码学保证
  • 零币（zerocoin）系统中存在基础币和零币，通过基础币和零币的来回转换，消除旧地址和新地址的关联性，类似于coin mixing
  • 零钞（zerocash）系统使用 zk-SNARKs 协议，不依赖一种基础币，区块链中只记录交易的存在性和矿工用来验证系统正常运行所需要关键属性的证明。区块链上既不显示交易地址也不显示交易金额，所有交易通过零知识证明的方式进行

思考

哈希指针如何实现？

指针在普通程序上经常会遇到，但只是本地的内存地址，在分布式系统中并不存在指针。哈希指针指示一种形象化的说法，因为 hash 值本身的复杂性以及 hiding 特性，使得 hash 值本身就是独一无二的。在实际的系统中，区块链的数据保存使用的是kv数据库，常用的为 levelDB，key为hash，value为区块。

区块恋

指的是将账户的私钥一分为二，两人各自保存一段，合则账户无忧，分则钱包丢失。但这是不可取的方案。区块链的安全性很大一部分来自于密码学的保证，而密码学也需要足够长的数据进行数据保护。将 256 位的密钥一分为二，对于任何一方来说破解难度并不是一分为二，而是大幅度指数级别的难度降低。同时容错性比较差，假设一方粗心大意丢失了密钥片段，那也比较麻烦。对于多个实体共同持有一个用户的方案，一般使用多签实现。

分布式共识

比特币并没有达成真正意义的分布式共识，临时达成的共识是会被推翻的。但是理论上的不可能并不意味着现实中的不可能。理论上的不可能是建立在一些状态下的（需要基础状态支撑），现实中可以通过一些方法破坏基础状态。所以不能被学术上的不可能击垮，在学术无法解决的问题上可以使用工程的方法去解决。

比特币的稀缺性

比特币的发行机制决定了总量是在 2100 万枚。但在实际货币中这不是个好的实践。随着时代的发展，财富总量是增长的，而货币是定量的，这一定会导致货币的价值提升，但这同样也会减低财富的流通性。早期持有比特币的人不需要再进行财富创造，只依赖货币的价值增长即可，而后来者的奋斗就没有意义了。（建立在货币存在交易属性）

量子计算

量子计算对于现有的密码学来说确实是冲击性的，很多密码学理论都会被推翻。第一，量子计算实用没那么迅速；第二，量子计算对于所有金融行业都是冲击，加密货币仅仅是金融行业里的一个小店；第三，比特币用于接收的暴露的地址，用的是公钥经过hash算法做的摘要，这个算法本身就会丢失数据，所以是不可逆的（假设散列算法可逆，那这就是逆天的压缩算法，全世界所有的数据全部压缩到256位）。

Search

    Table of Contents