0%

区块链技术与应用-比特币系统

Posted on Edited on In

密码学原理

密码学哈希函数

性质：

  1. collision resistance 很难产生哈希碰撞
    很难找到一个值 m’ 使得 H(m’) = h(m)

  2. hiding 单向
    x -> H(x)
    从哈希值h(x)不能反推出x
    成立前提:输入空间足够大，概率分布较均匀

这两个性质结合可以应用于
digital commitment
digital equivalent of a sealed envelope

  1. puzzle friendly 比特币中的哈希函数性质
    SHA-256
    difficult to solve,but easy to verify
    H(block header) <= target

签名：

(public key, private key) 非对称加密体系
签名使用私钥，验证使用公钥
成立前提：拥有一个好的随机源

数据结构

哈希指针

1
2
3
4
5
p -> ____ <- h()
    |    |
    |    |
    |____|
h() 结构体的哈希值

Block chain is a linked list using hash pointers.

1
2
3
4
5
6
7
8
区块链示意图
     ____    ____    ____    ____ 
    |    |  |    |  |    |  |    |
    |    |<-|    |<-|    |<-|h() | 
    |____|  |____|  |____|  |____|
    创世纪块                  最近产生的区块

根据前一个区块取哈希，若前面的区块发生变化，则哈希值不能对应上，可以发现篡改

Merkle tree

使用哈希指针的二叉树

最下面一层是数据块（交易块），上面的节点都是哈希指针。只需保存root hash的值，就可以判断整棵树是否被篡改。

每个区块分为两部分： block header ,block body
block header:记录root hash
block body:记录交易列表
轻节点：只保存block header

merkle tree

作用：提供merkle proof
merkle proof

某个轻节点想证明交易tx是否在merkle tree中，需要向某个全节点发送请求，全节点将标为红色的哈希值告诉轻节点，轻节点即可验证。

proof of membership

当节点按哈希值大小排序时(sorted merkle tree)，是可以证明 nonmembership 的

数字货币的问题：

  1. doble spending attack
    如果数字货币只有签名，那么货币可能被复制

    中心化的解决方法，央行记录货币的拥有者，交易时验证货币拥有者的信息

去中心化的数字货币要解决的问题：

  1. 数字货币的发行
  2. 验证交易的有效性

trans

交易分为输入和输出：输入包括a的公钥和币的来源，输出部分为接收者的公钥
在铸币交易时公布了a的公钥 

1
2
3
4
5
6
7
8
9
block header
 version
 hash of previous block header
 merkle root hash
 target
 nonce

block body
 transaction list

Consensus in BitCoin

比特币系统的实现

基于交易的账本

比特币系统是基于交易的账本，transaction-based ledger

比特币的全节点要维护一个utxo的数据结构：Unspent Transaction Output(未花掉的交易的输出的集合)，可以快速检测double spending

total inputs = total outputs

基于账户的账本

以太坊采用这种模式
account-based ledger

挖矿

不断尝试nonce来求解puzzle

每次尝试可以看做是一个bernoulli trial:a random experiment with binary outcome

berboulli process: a sequence of independent Bernoulli trails

性质： memoryless

每次的成功概率很小，可以用泊松近似（Poisson process）

出块时间服从指数分布 x^(-1)

比特币的总数为 

1
2
21万*50 + 21万*25 + ....
= 21万 * 50 * (1+1/2+1/4+...) = 2100万

比特币的稀有性是人为造成的

挖矿提供了一种依靠算力投票的有效机制，bitcoin is secured by mining

比特币网络工作原理

应用层： bitCoin Block chain
网络层： P2P Overlay Network

设计原则： simple, robust, but not efficient
传播方式： flooding
使用 TCP

比特币系统挖矿难度的调整

H(block header) <= target

SHA-256 2^256

挖矿难度与target成反比
difficulty = difficulty_1_target / target

比特币系统中规定每隔10分钟出一个区块，每隔2016个区块调整一次难度

target = target * [(actual time) / (expected time)]

总结

全节点

一直在线
在本地硬盘上维护完整的区块链信息
在内存中维护UTXO集合，以便快速验证交易的正确性
监听比特币网络上的交易信息，验证每个交易的合法性
决定哪些交易会被打包到区块里
监听别的矿工挖出来的区块，验证其合法性
挖矿

  • 决定沿着哪条链挖下去
  • 当出现等长的分叉的时候，选择哪一个分叉

轻节点

不是一直在线
不用保存整个区块链，只保存每个区块的块头
不用保存全部交易，只保存与自己相关的交易
无法检验大多数交易的合法性，只能检验与自己相关的交易的合法性
无法检验网上发布的区块的正确性
可以验证挖矿的难度
只能检测哪个是最长链，不知道哪个是最长合法链

挖矿芯片：

CPU -> GPU -> ASIC(Applicition Specific Integrated Circuit)

一种ASIC只能为一种加密货币挖矿，除非mining puzzle相同（merge mining）

矿池：

一般有两种组织方式

  1. 集中式（属于同一个机构）
  2. 分布式（属于不同机构）

一个矿池可以拥有多个矿工，解决收入不稳定的问题，根据工作量进行收入分配

工作量证明： 每尝试一次nonce生成一个share（almost vaild block)

优点：

  • 解决收入不稳定的问题

缺点：
可能会产生51%攻击

  • 分叉攻击
  • Boycott(A账户发起交易，立刻分叉)

比特币脚本

script

先执行input script再执行output script，如果过程中出现任何错误都认为交易非法。

输入输出脚本类型：

P2PK(Pay to Public Key)

input script:
PUSHDATA(sig)

output script:
PUSGDATA(PubKey)
CHECKSIG

脚本执行
PUSHDATA(sig)
PUSHDATA(PubKey)
CHECKSIG

堆栈元素变化：
sig -> PubKey,sig -> true

P2PKH(Pay to Public Key Hash)

input script:
PUSHDATA(sig)
PUSHDATA(PubKey)

output
DUP
HASH160
PUSHDATA(PubKeyHash)
EQUALVERIFY(比较栈顶两个哈希值是否相等)
CHECKSIG

脚本执行
PUSHDATA(sig)
PUSHDATA(PubKey)
DUP
HASH160
PUSHDATA(PubKeyHash)
EQUALVERIFY(比较栈顶两个哈希值是否相等)
CHECKSIG

堆栈元素变化：
sig -> pubKey,sig -> pubKey,PubKey,sig -> PubKeyHash,PubKey,sig -> PubKeyHash,PubKeyHash,PubKey,sig -> PubKey,sig -> True

P2SH(Pay to Script Hash)

采用BIP16的方案：
input script:
…
PUSHDATA(sig)
…
PUSHDATA(serialized redeemScript)

output scrpit:
HASH160
PUSHDATA(redeemScriptHash)
EQUAL

进一步说明

  • input script 要给出一些签名（数目不定）及一段序列化的redeemScript。验证分如下两步：
  1. 验证序列化的redeemScript是否与output script中的哈希值匹配
  2. 反序列话并执行redeemScript，验证input script中给出的签名是否正确
  • redeemScript 的形式
  1. P2PK
  2. P2PKH
  3. 多重签名形式

用P2SH实现P2PK

redeemScript:
PUSHDATA(PubKey)
CHECKSIG

input script
PUSHDATA(sig)
PUSHDATA(serialized redeemScript)

output script
HASH160
PUSHDATA(redeemScriptHash)
EQUAL

第一阶段的验证：
PUSHDATA(sig)
PUSHDATA(serialized redeemScript)
HASH160
PUSHDATA(redeemScriptHash)
EQUAL

第二阶段的验证：
PUSHDATA(PubKey)
CHECKSIG

多重签名

例如有5个人，使用其中3个签名可以对账户进行操作
最早的多重签名，目前已经不推荐使用

input script
× (此处的x是因为代码中的bug，向栈中压入一个空元素)
PUSHDATA(Sig_1)
PUSHDATA(Sig_2)
…
PUSHDATA(Sig_M)

output script
M
PUSHDATA(pubkey_1)
PUSHDATA(pubkey_2)
…
PUSHDATA(pubkey_N)
N
CHECKMULISIG

用P2SH实现多重签名

input script:
×
PUSHDATA(Sig_1)
PUSHDATA(Sig_2)
…
PUSHDATA(Sig_M)
PUSHDATA(serialized RedeemScript)

output script:
HASH160
PUSHDATA(redeemScriptHash)
EQUAL

redeemScript:
M
PUSHDATA(pubkey_1)
PUSHDATA(pubkey_2)
…
PUSHDATA(pubkey_N)
N
CHECKMULISIG

脚本执行过程：

第一阶段： 

1
2
3
4
5
6
7
FALSE 
PUSHDATA(Sig_1)  
PUSHDATA(Sig_2)  
PUSHDATA(seriRS)
HASH160  
PUSHDATA(RSH)  
EQUAL

第二阶段： 

1
2
3
4
5
6
2
PUSHDATA(pubkey_1)  
PUSHDATA(pubkey_2)  
PUSHDATA(pubkey_3)
3
CHECKMULISIG

Proof of Burn

  • output script 
    1
    2
    RETURN 
      [zero or more ops or text]

这种形式的output被称为：
Provably Unspendable/Prunable Outputs

  • 脚本说明：
    假如有一个交易的input指向这个output，不论input里的input script如何设计，执行到RETURN命令之后都会直接返回false，不会执行RETURN后面的其他指令，所以这个outpu无法再花出去，其对应的UTXO也就可以被剪枝了，无需保存。

比特币分叉(fork)

成因：

  • state fork
    挖矿时，两个矿工几乎同时发布区块，就会产生一个临时性的分叉

    • forking attack(deliberate fork)

  • protocal fork
    因为使用不同版本的协议产生的分叉

    • hard fork
    • soft fork

hard fork

对比特币协议内容的分歧，例如区块的大小限制

假设新节点更新了协议，旧节点没有更新，那么新节点挖出来的区块不被旧节点认可，新节点在新分叉1上挖，旧节点在分叉2上挖，会产生永久的分叉。

soft fork

对比特币协议添加一些限制，使得原来合法的交易（区块）在新的协议中不合法。

假设区块大小由1M改为0.5M，新节点更新了协议，旧节点没有更新，新节点挖出的区块被老节点认可，老节点挖出的区块不被认可，会出现暂时的分叉。

实际情况：

  1. 给之没有用到的域添加新的含义，coinbase
  2. P2SH

比特币的匿名性

假如银行使用化名，其匿名性是比比特币好的。

破坏匿名性：

  1. 不同的账户间能建立联系
  2. 线下交易

实现匿名性：

  1. 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)系统中存在基础币和零币，通过基础币和零币的来回转换，消除旧地址和新地址的关联性，其原理类似于混币服务。
  • 零钞(zerocash)系统使用zk-SNARKs协议，不依赖一种基础货币，区块链中只记录交易的存在性和矿工用来验证系统正常运行所需要关键属性的证明。区块链上既不显示交易地址也不显示交易金额，所有交易通过零知识验证的方式进行。