这是我学习北京大学肖臻老师《区块链技术与应用》公开课的学习笔记
课程地址:北京大学肖臻老师《区块链技术与应用》公开课

比特币

比特币中的密码学原理

  • 比特币被称为加密货币,但加密货币实际上是不加密的,区块链上所有的交易内容都是公开的
  • 比特币主要用到了密码学中的两个功能:哈希、签名
  • 哈希函数的性质
    • collision resistance(难以人为制造哈希碰撞)
      • 哈希碰撞:x≠y,但有H(x)=H(y)
      • 目前已经知道对于MD5算法制作哈希函数的方法
    • hiding(哈希不可逆):给定x->H(x),但无法从H(x)反推出x
      • 成立的前提:输入空间足够大且输入分布均匀
      • 能够和collision resistance结合起来构成digital commitment
    • puzzle friendly(哈希值不可预测,只能枚举尝试,故挖矿需要大量算力)
    • difficult to solve, but easy to verify
  • 比特币中用的哈希函数是SHA-256(Secure Hash Algorithm),输出空间有2的256次方种可能
  • 比特币的开户方式:在本地产生一对公私钥(生成公私钥对的过程是随机的,故生成公私钥对需要好的随机源),比特币中的公私钥对就是一个账户,公钥相当于银行账户,私钥相当于账户的密码
  • 加密用公钥,解密用私钥;签名用私钥,验证签名用公钥(签名同样需要好的随机源,如果随机源不好,可能会泄露私钥)

比特币中的数据结构

  • 哈希指针:存储结构体的地址和该结构体的哈希值,故可以检测该结构体是否被篡改。区块链中,每一个区块都包含前一个区块头的哈希值

  • Merkle tree:用哈希指针代替了普通指针的完全二叉树
    Merkle tree

  • 每个区块分为两部分:区块头、区块身,区块头储存了该区块的根哈希值,区块身存储了交易数据

  • 比特币中的节点包括全节点和轻节点,全节点保存了所有区块的内容,轻节点(如手机上的比特币钱包)只保存区块头

  • Merkle proof:用于证明该交易存在,时间复杂度为O(log(n))
    Merkle proof

  • 证明某个交易不存在

    • 不排序:枚举,时间复杂度为O(n)
    • 排序:按哈希值从左到右,从小到大排序,时间复杂度为O(log(n)),排序后就会变为sorted Merkle tree。但比特币中没有排序,因为比特币中不需要做不存在证明
  • 只要是无环的链式结构都能采用哈希指针,但有环的链式结构无法使用,因为每一个区块都依赖前一个区块的哈希值,这样哪个区块都无法确定下来

比特币的共识协议

  • double spending attack(双花攻击)
  • 比特币中第一类哈希函数是连接区块的,第二类哈希函数是连接交易记录的,用于说明比特币来源和防止双花攻击
    第二类哈希函数
  • A要向B转账,A的公钥要和A的比特币来源的公钥的哈希值相符
  • 每个交易包括输入和输出两部分
    • 输入:币的来源,支付方的公钥
    • 输出:收款方公钥的哈希
    • 每个交易可以有多个输入和多个输出,但总输入一定等于总输出(除开交易费)
  • 区块头:比特币哪个版本的协议,指向前一个区块的指针,默克尔树的根哈希值,挖矿的难度目标阈值,随机数
  • distributed consensus(分布式共识)
    • distributed hash table(分布式哈希表)
    • impossibility result(不可能结论)
      • FLP:在一个异步的系统里,只要有一个成员有问题,就没法达成共识
      • CAP(consistency,availability,partition tolerance) Theorem:三个性质无法同时满足
  • 比特币中的共识协议
    • 优先计算出目标哈希值的节点能够获得打包区块的权力
    • 接受的区块应该链在最长合法链上
    • forking attack(分叉攻击):通过往区块链中插入区块来回滚已经发生的交易
    • 如果两个节点同时计算出目标哈希值并打包区块然后发布,则会产生区块链分叉,但最终其中一个会胜出,成为最终的最长合法链
    • block reward(区块奖励):打包了区块的节点会获得新发行的比特币,最初节点能获得50BTC,每产生21万BTC之后,每次打包所获得的BTC会减半

比特币系统的实现

  • 比特币采用的是基于交易的账本(transaction-based ledger)

  • 全节点需要维护一个叫UTXO(Unspent Transaction Output)的数据结构

    • UTXO集合中的每一个元素需要给出产生这个输出的交易的哈希值,以及他在这个交易里是第几个输出,通过这两个信息就能定位到UTXO中的输出
    • UTXO只保存没有花掉的输出,已经花掉的输出会被删除
  • 比特币设计平均每隔十分钟会产生一个新的区块,大约每隔4年区块奖励会减半,所以到了后期,打包区块中的交易费会成为主要的工作动力

    21×10分钟60分钟×24小时×3654\frac{21万 \times 10分钟}{60分钟 \times 24小时 \times 365天}\approx 4年

  • 以太坊采用的是基于账户的账本(account-based ledger)

  • 除了区块头的nouce可以调整以外,还能够调整每个交易的CoinBase,调整了CoinBase,进而默克尔树的根哈希值就会产生变化,从而产生更多可以用来尝试挖矿的输入。故真正挖矿只有两层循环,外层循环调整CoinBase,内层循环调整Nonce

  • 比特币中验证交易的合法性是通过每次交易的输入脚本和提供币的来源的交易的输出脚本配对,如果拼接在一起能够顺利执行,便说明该交易是合法的

  • 挖矿中的每次尝试可以看作伯努利试验,这些伯努利试验构成了伯努利过程,伯努利过程具有无记忆性,这个过程也近似泊松过程

  • 区块的出块时间服从指数分布,由于指数分布仍然是无记忆性的,所以过去的工作是无效的,但这恰恰是挖矿公平性的保证

  • 比特币的总量约是2100万

    21×50+21×25+21×12.5+...=21×50×(1+12+14+...)=21×50×2=210021万 \times 50 + 21万 \times 25 + 21万 \times 12.5 + ... = 21万 \times 50 \times \left (1 + \frac{1}{2} +\frac{1}{4} + ... \right ) = 21万 \times 50 \times 2 = 2100万

  • 挖矿使得比特币的安全性得到了保证

  • 多等几个区块就能防止分叉攻击,比特币设置为了6个区块

  • zero confirmation:交易已经发出,但并没有写到区块链里,尽管看上去不太安全,但实际应用是十分广泛的

  • 区块链在正常的情况,也会出现合法的交易没有被打包到区块的情况,比如这段时间交易数目太多了,而比特币规定了每个区块的大小为1MB,所以每个区块能写入的交易是有限的

  • selfish mining:正常情况是挖到区块马上发布,但这里是挖到区块先不发布,先藏好一条链,等到合适的时机发布出去

比特币网络

  • 比特币工作在应用层,它的底层是P2P Overlay Network
  • 比特币网络中所有节点都是平等的
  • 比特币中有着种子节点,和种子节点联系就能知道它所知道的网络中的其他节点
  • 节点之间是通过TCP来通信的,这样有利于穿透防火墙
  • 比特币网络的设计原则是简单,鲁棒而非高效
  • 每个节点维护一个凝聚节点的集合,消息传播采取flooding的方式,节点第一次听到某个消息时,会传播给所有凝聚节点,同时记录该消息已经收到,下次收到同样的消息时便不再重复传播
  • 凝聚节点的选取是随机的,这样设计的好处是增强了鲁棒性
  • 节点收到两个矛盾的交易时,只会保存先收到的交易
  • 新发布的区块和新发布的交易在网络上的传播方式是类似的
  • 每个节点除了要检查区块内容的合法性之外,还要检查该区块是否在最长合法链上

比特币的挖矿难度调整

  • 挖矿目标

    H(blockheader)targetH(block header) \le target

  • 挖矿难度与target成反比

  • 调整挖矿难度是为了将出块时间维持在一个稳定的区间。出块时间太短的话,分叉就会频繁地发生,并且分叉数量会增加;分叉越多,系统达成共识就越难,同时网络中的算力就被分散了,有恶意的节点就更容易集中算力将自己维护的区块扩展成最长合法链

  • 比特币设计每产生2016个区块,也就是大约每14天调整一次target

    2016×10分钟60分钟×24小时=14\frac{2016 \times 10分钟}{60分钟 \times 24小时}= 14天

  • target的调整方案

    target=target×actual time(系统最近产生的2016个区块实际花费的时间)expected time2016×10分钟)target = target \times \frac{actual \ time(系统最近产生的2016个区块实际花费的时间)}{expected \ time(2016 \times 10分钟)}

  • 实际代码中target调整的上限和下限是原来的4倍和4分之1

比特币挖矿

全节点 轻节点
一直在线 不是一直在线
在本地硬盘上维护完整的区块链信息 不用保存整个区块链,只保存每个区块的块头
在内存里维护UTXO集合,以便快速检验交易的正确性 不用保存全部交易,只保存与自己相关的交易
监听比特币网络上的交易信息,验证每个交易的合法性 无法检验大多数交易的合法性,只能检验与自己相关的那些交易的合法性
决定哪些交易会被打包到区块里 无法检测网上发布的区块的正确性
监听别的矿工挖出来的区块,验证其合法性 可以验证挖矿的难度
挖矿 只能检测哪个是最长链,但不知道哪个是最长合法链
  • 挖矿设备:第一代为CPU,第二代为GPU,第三代(目前)为ASIC芯片
  • ASIC芯片只能专用于某一种加密货币的挖矿,除非两种币的mining puzzle是一样,并且ASIC芯片除了挖矿别无他用
  • 有些新的加密货币设计了Alternative mining puzzle,以便达到ASIC resistance的效果,目的是让通用计算机也能参与挖矿
  • 矿池:有一个矿主,下面有大量矿工,一个矿池能驱动大量矿机,矿工只负责计算哈希值,全节点的其它职责都由矿主负责
  • 矿池的两者组织形式:大型数据中心和分布式
  • 分布式矿池的收益分配:矿主将挖矿难度降低,每个矿工可以提交share给矿主,以此证明自己的工作量,最后按照各自提交的share数量分配收益
  • 矿池的出现,使得比特币的安全性受到了一定程度上的威胁,譬如:分叉攻击、封锁某个账户

比特币脚本

  • P2PKH(Pay to Public Key Hash)
    • input script
      • PUSHDATA(Sig)
      • PUSHDATA(PubKey)
    • output script
      • DUP
      • HASH160
      • PUSHDATA(PubKeyHash)
      • EQUALVERIFY
      • CHECKSIG

比特币分叉

  • state fork:对比特币当前的状态产生分歧的分叉
  • protocol fork:对比特币的协议产生分歧的分叉
    • hard fork
      • 新旧节点会沿着不同的区块挖下去,并且产生的链会永久存在
      • 必须所有节点都更新软件,否则才不会出现永久性的分叉
    • soft fork
      • 新旧节点会沿着不同的区块挖下去,但旧节点挖出的区块往往只是暂时存在,很快便会被舍弃
      • 只要半数以上的节点更新了软件,就不会出现永久性的分叉
    • 区分硬软分叉主要看新旧节点能否有一方认可另一方,如果认可往往是软分叉

比特币问答

  • 转账交易时,如果收款方不在线怎么办?

    • 转账交易不需要收款方在线
  • 假设某个全节点收到了一个转账交易,有没有可能接收者的收款地址是该全节点以前从来没有听说过的?

    • 可能。比特币创建账户时无须通知其他节点
  • 如果账户私钥丢失了,该怎么办?

    • 凉拌
  • 如果账户私钥泄露了,该怎么办?

    • 赶紧把账户上的钱转走
  • 如果转账时写错了地址怎么办?

    • 凉拌
  • 如何确定是哪个矿工先找到Nonce?

    • 每个矿工挖到的Nonce是和自己的收款地址绑定的,故无法偷答案
  • 交易费如何确定给谁?

    • 不需要事先知道给谁,等谁挖出矿再给谁

比特币的匿名性

  • 比特币的匿名性和银行存款相比如何?
    • 银行账户需要实名,自然比特币更好。但早期银行可以使用化名,它的匿名性比比特币要好,因为比特币账本公布在区块链中,任何人都可以查
  • 什么情况下会破坏比特币中的匿名性?
    • 比特币常用的钱包只有几种,只要搞清楚这几种钱包生产交易的方式,区块链上绝大部分的转账交易都能分析出来
    • 同一个交易中可以产生多个输入和多个输出,同时产生的多个输入地址很有可能都是同一个人的账户
  • 什么情况下别人会知道比特币中的账户对应现实世界中的某个人?
    • 只要比特币与实体世界发生联系时,都有可能泄露身份
  • 使用比特币交易时,只要周边有人,别人就很容易通过区块链找到你的地址并对应上你
  • 比特币的匿名性并没有想象中的那么好,如果你想用它来干坏事几乎是不可能的
  • 如果尽可能地提高你的账户的匿名性?
    • 网络层:洋葱路由
    • 应用层:Coin mixing(把不同人的币混在一起)
  • 零知识证明:一方(证明者)向另一方(验证者)证明一个陈述是正确的,而无需透露除该陈述是正确的外的任何信息
  • 同态隐藏
    • 如果x,y不同,那么它们的加密函数值E(x)和E(y)也不相同;其逆否命题为:如果E(x)和E(y)相同,那么x和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=7,同时不想让Bob知道x和y的具体值
    1. Alice把E(x)和E(y)的值发给Bob
    2. Bob通过收到的E(x)和E(y)计算出E(x+y)的值(利用性质3)
    3. Bob同时计算E(7)的值,如果E(x+y)=E(7),那么验证通过,否则验证失败
  • 盲签
    1. 用户A提供SerialNum,银行在不知道SerialNum的情况下返回签名Token,减少A的存款
    2. 用户A把SerialNum和Token交给B完成交易
    3. 用户B拿SerialNum和Token给银行验证,银行验证通过,增加B的存款
    4. 银行无法把A和B联系起来
    5. 中心化
  • 零币和零钞
    • 零币和零钞在协议层就融合了匿名化处理,其匿名属性来自密码学保证
    • 零币(zerocoin)系统中存在基础币和零币,通过基础币和零币的来回转换,消除旧地址和新地址的关联性,其原理类似于混币服务
    • 零钞(zerocash)系统使用zk-SNARKs协议,不依赖一种基础币,区块链中只记录交易的存在性和矿工用来验证系统正常运行所需要关键属性的证明。区块链上既不显示交易地址也不显示交易金额,所有交易通过零知识验证的方式进行

比特币引发的思考

  • 哈希指针
    • 指针指向的地址只有在本地才有意义,传播起来并不现实
    • 哈希指针只是一个形象的描述,在实际应用当中,只有哈希,没有指针
    • 全节点是用key,value来存储区块链的,key是区块的哈希,value是区块的内容
    • levelDB是一个常用的key,value数据库
  • 区块恋
    • 一对情侣买比特币,分别存储私钥的一半,如果分手了,钱就再也无法取出来
    • 截断私钥会降低账户的安全性,截断为原来的一半则会使破解的难度大幅降低
    • 多人共享账户勿用截断私钥,用多重签名
  • 分布式共识
    • 为什么比特币系统能够绕过分布式共识中的那些不可能结论?
    • 事实上,比特币并没有绕过,也并没有取得真正意义上的共识
    • 理论和现实是有区别的,某些理论上的不可能,在现实中能够成为可能
  • 比特币的稀缺性
    • 比特币总量是有限的,但是总量有限的东西其实并不适合作为货币
    • 好的货币应该有一定程度的通货膨胀
  • 量子计算
    • 量子计算机的出现是否会让以密码学作为根基的加密货币变得不安全?
    • 这个担心是不必要的,量子计算离实际应用还早,在比特币的有生之年产生不了威胁;如果有一天量子计算发展到能够威胁加密货币的话,首先受到冲击的是传统金融业;而且将来还会出现量子加密算法
    • 比特币中并没有把公钥直接暴露出来,而是对公钥取哈希得到一个地址,比特币中可以从私钥推导出公钥,只要私钥保管好,公钥丢了也没关系。假设量子计算能够从公钥推出私钥了,但比特币用的是公钥的哈希,所以如果有人想窃取账户的钱,需要先对地址推出公钥,这个事情即使是量子计算机也无法完成
    • 如果你担心量子计算所带来的威胁,那么即使是公钥也不要随便泄露

以太坊

以太坊概述

  • 以太坊设计的memory hard mining puzzle对内存的要求较高,它在一定程度上限制了ASIC芯片的使用
  • 以太坊未来将使用权益证明(proof of stake)来取代工作量证明
  • 以太坊增加了去中心化的智能合约(smart contract)的支持
  • 比特币最小的单位是聪(Satoshi),以太坊最小的单位是Wei

以太坊的账户

  • 以太坊账户采用的是基于账户的模型,即系统会显式地记录每个账户的余额
  • 这种模型对于双花攻击有天然的防御作用,因为这种模式不用说明币的来源,花的钱就会从账户中扣除
  • 对于以太坊而已,还有一种攻击叫replay attack,就是某个节点把某个交易重新广播一遍
  • 通过对交易添加交易次数可以防范replay attack
  • 以太坊中有两个账户
    • 外部账户(externally owned account):由公私钥对控制,包含有账户余额balance和交易次数nonce
    • 合约账户(smart contract account):并非由公私钥对控制,同样包含balance和nonce,还拥有代码code以及状态storage,一个合约可以调用另一个合约。合约账户不能发起交易,所有交易只能由外部账户发起

以太坊中的状态树

  • 以太坊中的账户地址是160bit,一般表示为40个16进制的数
  • 以太坊实现从账户地址到账户状态的映射,采用的是