区块链技术与应用(一)

北京大学肖臻老师《区块链技术与应用》笔记 - BTC篇

BTC 密码学原理

• Hash

  • hash碰撞不易发生
    • 特点:
      • 存在两个输入 x, y, 使得 hash(x) == hash(y); 通常来讲hash碰撞是不可避免的, 因为输入空间 >> 输出空间
      • 不存在一个好的方法, 主动制造hash碰撞, 唯一的方法就是暴力枚举.
      • 对于一个hash结果是256位的结果来说, 通过暴力枚举, 根据输出求输入, 理论上是可行的, 但是实际上是不可以行的, 因为工作量太大了.
    • 作用:
      • 可用来计算某个输入是否被修改, 先 hash(input) = r0并将r0保存, 再次使用input时候不确定input是否被修改, 先计算hash(input) = r1, 然后通过判断 r0 == r1 是否成立来确定input是否被修改.
  • 函数计算过程单向, 不可逆
    • 特点
      • 已知输入x, 输出y = hash(x), 无法通过y计算出x的值.
    • 作用
      • 配合hash碰撞的特点可以实现密封信封的结果, 比如hash(预测结果) = r0, 当结果出来之后, hash(结果) = r1, 然后判断 r0 == r1 是否成立来判断预测结果是否准确.
  • hash值的结果, 事先不可预测.
    • 特点
      • 无法通过观察, 直接计算出某个输入的hash运算后的结果在某个区间内, 只能通过暴力枚举一个一个的去试.

• 签名
  - 比特币开户, 只需要生成一对公私钥. 使用私钥签名, 使用公钥验证签名.
  - 非对称加密解决了对称加密秘钥在网络传输中的不安全的问题.
  - 想通过自己不断生成公私钥, 然后对比某个用户的公钥, 当公钥相同时候, 就有了对方的公私钥, 理论上方法可行, 但是概率太小, 小到忽略不计.

BTC 数据结构

• hash指针
  • 特点
    • 区块链是一个使用hash指针的链表, 只需要保存最新的区块的hash指针, 如果中间的区块发生改变, 就可以检测到.
    • 保存结构体的地址的同时保存这个结构体的hash值, 这样可以判断这个结构体是否被修改过. 当修改了区块链中某个块的内容, 那么这个块中的hash值就会改变, 那么下一个块的指向这个块的hash指针就会变化, 然后后边的每个块的hash指针都会变化.
    • 可以只保存最近的1000个区块, 当用到某个区块时候, 直接问别的区块索要本地保存的最早的区块的上一个区块, 然后通过判断本地保存的区块的上一个区块的hash指针和上一个区块的hash值是否相等来判断索要的区块是不是一个恶意区块.
• Merkle tree
  • 特点
    • 使用hash指针代替普通指针
    • 只需要保存最新的root hash, 如果其他的区块发生改变, 就可以检测到.
    • 比特币中每个区块之间使用hash指针连接, 每个区块内交易组织成Merkle tree的形式.
  • 用途

    • 提供 merkle proof 如下图: 可以验证某个交易在这区块中 复杂度是log(n), 但是如果验证某个交易不在这个块中 复杂度是n, 为了解决复杂度的问题, 可以使用布隆过滤器(布隆过滤器如果验证不存在, 就一定不存在 ,如果验证存在, 有可能存在.).

      
      8b7fb9b7eb5b42329bc041e9134c4723.png

• block
  • block header : 本区块所包含的所有交易组成的 Merkle tree的root hash 保存在block header中.
  • block body : 保存所有交易的列表.
  • 轻节点只包含 block header; 全节点同时包含 block header 和 block body;

BTC 协议

• 货币的发行
  • 通过挖矿发行货币
• 双花问题
  • 每笔交易都用hash指针指向btc的input和output 其中input是(btc的来源交易和来源交易中接收方的公钥)和output(本次交易的收款方的公钥的hash). 通过判断广播时候发送方的公钥 == input中的公钥相等判断是否是合法的交易.
• 区块的验证
  • 区块的验证其实就是每个节点收到区块的时候, 验证这个新的区块是不是一个合法的区块, 如果认为这个区块是合法的, 就会接着这个区块后边继续拼接, 如果认为这个区块不是合法的就会放弃这个区块, 等待一个合法的区块, 然后再合法的区块后边继续拼接.
• 区块的结构

  • block heder

    • nVersion 版本号: 区块的版本号
    • hashPrevBlock上一个block header的 hash : 前一个区块的hash值, SHA256(SHA256(preview block header));
    • hashMerkleRoot merkle tree的root hash : 所有交易组成的merkle tree的根节点的hash值, SHA256(SHA256(根节点));
    • nTime 时间戳 : 区块产生的时间
    • nBits 难度目标 : 工作量证明的算法的难度目标. hash(block header) <= target;
    • nNonce 随机数 : 为了找到满足条件的目标所设定的随机数. 现在因为挖矿难度变大, nonce的4字节算出的结果无法满足难度目标, 所以开始使用coinbase域的前8个字节当做extra-nonce来使用, 所以真正挖矿的时候, 会有两层循环, 外层循环调整coinbase域的extra-nonce，算出block header里的根Hash值之后，内层循环再调整block header里的nonce。

    • 通常在块时, 出块奖励的那个交易的input是没有输入的, 通常这个input的字段的被称为coinBase域, 通常改变coinbase域, 会改变header中的hashMerkleRoot 从而改变 header的hash.

      
      image.png

  • block body

    • 交易列表
• 节点分类
  • 全节点: 通常是挖矿即争夺记账权,打包区块的时候使用.
    • 一直在线
    • 从本地硬盘上维护完整的区块链信息
    • 从内存里维护UTXO集合, 以便快速检验交易的正确性
    • 监听比特币网络上的交易信息, 验证每个交易的合法性
      • 有没有合法的签名
      • 是不是double spending
    • 决定那些交易会被打包到区块中
      • 合法的交易
      • 交易费符合要求
    • 监听别的矿工挖出来的区块, 验证其合法性
      • 区块中的每个交易都必须合法, 包括铸币交易.
      • 有没有篡改 block reward, 发布的区块是否符合难度要求, block header中的难度目标阈值设置是不是正确的
      • 区块是在延伸最长合法链.
    • 每两周按照比特币协议的要去调整挖矿难度
    • 挖矿
      • 缺省情况下沿着最长合法链挖下去.
      • 当出现等长的分叉的时候, 缺省情况下是沿着最先接收到的分叉继续挖下去的.
  • 轻节点 : 通常只转账, 不挖矿时候用轻节点.
    • 不是一直在线
    • 不用保存整个区块链, 只要保存每个区块的块头.
    • 不用保存全部交易, 只保存与自己相关的交易.
    • 无法验证大多数交易的合法性(因为没有保存完整的交易信息, 无法检测double spending), 只能检测与自己相关的那些交易的合法性.
    • 无法检测网上发布的区块的正确性(无法检测区块中所包含的交易的合法性)
    • 可以验证挖矿的难度
    • 只能检测哪个是最长链, 不知道那个是最长合法链.
• 账本的内容要取得分布式共识
  • pow(工作量证明)机制, 通过算力(并且通过验证, 即 1. 有合法的签名; 2. 没有双花问题)决定谁有权利写入下一个区块.
  • 通常新生成的区块是拼接在尾部的, 如果一个新生成了区块是接在中间位置的, 通常这个区块是不会别接受的.
    • 区块链能接受的区块应该是在扩展最长的合法链;
    • 所谓接受这个区块, 是指的沿着这个区块继续往下扩展, 就视为接受了这个区块.
• 最长链原则
  • 当同时有两个区块同时生成并将自己广播出去, 那么其他用户可能有的用户先收到block1, 有的用户先收到block2, 这时候会分叉成两个链, 直到其中一个链领先又提交了下一个区块. 这时候就以先提交区块的链作为最长合法链.

BTC 实现

• 记账方式
  • UTXO(还没有被花出去的交易的输出, 比特币中使用, 可以有效的抵御双花问题) : 比特币的全节点需要在内存中维护UTXO的数据结构, 以便快速检测双花问题. UTXO集合中的每个元素需要给出产生输出的这个交易的hash值以及他在这个交易中是第几个输出,通过这两个信息可以定位出一个UTXO的输出, 每个要花出去的币必须是在这个集合中才是合法的, 如果不在这个集合中就是不合法的. 通过这个集合可以找出每个币的来源. 每个交易会消耗一些输出同时也会产生新的输出.
  • 基于账户的记账方式(以太坊中使用)
• 比特币激励机制
  • 打包奖励 : 将交易打包到区块中的奖励. 这样可以让每个节点去打包更多的交易.
  • 出块奖励 : 打包出区块的奖励. 让更多人去参与挖矿.
• 交易确认
  • 在比特币协议中，默认在包含该交易的区块后有6个新增的区块，这时才能认为交易成功。以平均10分钟的出块时间记，需要在交易发起一小时后才能确认交易。

BTC 网络

• 比特币协议工作在应用层, 它的底层是一个P2P网络,
• 各个网络节点之间使用tcp通信(穿透防火墙), 当某个节点离开时候, 无需通知其他节点, 其他节点在长时间收不到某个节点的消息时候, 会将这个节点自动删除.
• 每个节点都会维护一个交易池, 存放未确认的交易, 当节点第一次收到某个交易时, 先确认这是一个合法的交易, 然后会将这个交易放入交易池中, 并将这个消息转发给邻居节点(邻居节点选取是随机的, 可能一个在自己家楼下, 另一个在邻居节点在另一个国家) , 之后在收到这个交易就不会转发了, 避免交易在网络上无限传输.
• 比特币协议对区块的大小限制在1M字节大小

BTC 挖矿难度

• 比特币使用SHA-256的hash算法, 产生的hash值是256位的. 比特币通过调整目标空间占输出空间的比例(hash值的前多少位是0)来调整挖矿难度; 比如对于256位的hash值来说, 要求前边至少有70个0;
• 挖矿难度和目标阈值成反比, difficulty = difficulty_1_target/target, difficulty_1_target指挖矿难度为1时的目标阈值位target，也就是说挖矿难度的最小值是1;
• 为什么需要调整挖矿难度
  • 随着系统总算力越来越强, 不调整难度, 出块时间就会越来越短, 如果出块时间 >> 块在网络上发布的传输时间(>>表示远远大于), 别的节点在收到这个块之前还会继续沿着已有的区块链继续扩展, 如果同一时间出现多个节点, 就会分叉, 而分叉过多是不利于分布共识的, 而且还会分散矿工算力(系统中的矿工分散在多个节点上), 这样恶意节点攻击的成本会降低(原本恶意节点攻击成功的要求是掌握51%的算例, 现在只要多个恶意节点同时攻击某一条链可能只要15%的算力就可以了).
  • 在比特币中, 每隔2016个区块(2个星期), 就会调整一次挖矿难度. 公式 : newTarget = lastTarget∗(最近的2016个区块挖出的耗时(单位是min)/2016 * 10) . 实际上，上调和下调都有四倍的限制，即实际时间超过8个星期，也只能按4倍算，目标阈值增大最多只能增大4倍。
  • 如果恶意节点不调整target, 检查不通过，其它节点就不会接受该区块. nBits是target编码后的版本，在blocke header里没有直接存储target的域。因为target的域是256位，直接存储的话要32个字节，nBits只有4个字节，所以可以认为nBits是target编码后的。如果有恶意节点在该调的时候不调，它生成的区块在发布到网络上时，其它节点会先检查该区块的合法性。检查的内容就包括nBits，检查不通过，其它节点就不会接受该区块.

BTC 挖矿

• 如何保证安全性
  • 密码学的保证
    • 别人没有私钥就无法伪造签名,就无法将账上的前转走.
  • 共识机制
    • 系统中拥有大多数算力的矿工是诚实矿工.不会接受没有合法签名的交易.
• 挖矿设备
  • CPU -> GPU -> ASIC
• 矿池
  • 职责划分
    • 矿主: 实现除了挖矿以外的全节点的其他功能.
    • 矿工: 只实现挖矿的功能. 只计算hash值.
  • 奖励分配
    • 按照贡献率分配奖励, 矿工的贡献采用的也是POW的方式, 通常挖矿的难度是70个0, 矿池要求的难度会降低, 例如计算贡献的难度是60个0, 每个矿工挖矿的时候如果产生60个0就将这个计算结果提交给矿主, 然后矿主统计贡献率.
  • 好处
    • 加入矿池之前, 矿工之后挖出区块才会有收益, 但是通过加入矿池, 矿工收入的稳定性提高了, 因为如果有人挖出区块, 就会按照贡献率分配给矿工.
  • 超大矿池产生的问题
    • 很多矿池开始通过降低管理费吸引大量矿工, 这就导致了超大矿池的出现, 超大矿池的出现可能会出现某些矿池的算力 > 全网算力的51%, 这使得分叉攻击变得容易, 还可以拒绝将某个账户的的交易上链, 但是还是无法都去他人的账户的比特币.
      • 分叉攻击: 当一个块已经产生后已经有6个确认块了, 这时候很多人认为这个交易已经安全了, 但是如果这时候大型恶意矿池生成一个新的块并将这个新的块添加到区块的前一个区块, 就会产生分叉, 而此时恶意矿池的算力 > 51%, 随着时间的推移这个新产生的分叉的长度最终终会>之前产生分叉的长度, 这时候新产生的分叉就成了最长合法链.
      • 拒绝将某个账户的的交易上链: 每当有人把包含某个人账户的交易的区块发布到区块链上, 恶意矿池马上进行分叉(不需要等待6个确认区块). 产生一个不包含这个交易的区块. 所有和这个交易有关的区块/和这个账户有关的交易都不包含在区块中.
    • 恶意竞争
      • 当矿工挖到了区块，但是不将这个结果发送给矿池，矿池就不会得到出块奖励。矿池之间是竞争关系，可能将自己的节点加入对手的矿池，搞一些破坏，分散对手的算力。

BTC 挖矿脚本

BTC 分叉

• 硬分叉 : 协议升级, 未升级协议的节点不认可特性, 认为节点特性是非法的. 而升级协议的节点认特性.
  • 区块大小变为4M, 这时候未升级的节点认为这是非法区块, 而系统中拥有多数算力的节点更新了协议, 认可这个节点特性. 这时候系统运行起来, 只要旧的节点不升级, 那么这个分叉就会永久存在. 不会消失.
  • 必须系统中所有的节点都节点都升级, 系统才不会出现永久性的分叉. 如果系统中少部分的节点一直不更新, 系统就会分成两条链.
• 软分叉: 协议加一些限制, 未升级的协议的节点认为这个节点特性是合法的, 而升级的协议认为这个节点特性是非法的.
  • 区块大小限制为0.5M, 这时候未升级的节点认为这个是合法的区块, 而系统中拥有多数算力的节点更新了新的协议, 不认可这个节点特性, 这时候系统运行起来, 因为新节点不认可旧的节点, 旧的节点认可新的节点, 这时候, 新节点就会成为最长合法链, 旧的节点挖出了区块只能也不会被认可, 这种分叉不是永久保留的.
  • 只要系统中拥有半数以上算力的节点更新了软件,系统就不会出现永久性的分叉, 可能有一些临时性的分叉, 但是不会有永久性的分叉.

BTC 匿名性

• 网络层的匿名性
  • BTC 本身具有匿名性, 但是如果BTC和现实世界产生交互(购物, 提现) 匿名性就会遭到破坏.
• 匿名性的实现方案
  • 使用多路径转发, 消息不是由发出者直接发送给接收者, 中间经过多次转发, 中间的每个节点只知道上一个节点是谁, 但并不知道最早发出消息的人.
  • 应用层的匿名性
    • 把不同的人的币混在一起(coin mixing). 用户将币发给做coin mixing的网站, 网站内进行重组, 然后再把币取回来, 这时取出的bi不再是发布到网络上的币, 而是随机抽取的币.
    • 还可以通过交易所实现应用层的加密, 交易所天然具有coin mixing的特性.
• 零知识证明
  • 证明者向验证者证明一个陈述是正确的, 而无需透漏该陈述是正确的外的任何信息.
• 同态隐藏
  • 加密数值E不会出现碰撞, 反过来说就是 如果E(x) == E(y), 那么 x== y;
  • 加密函数不可逆, y = E(x), 可以通过 E(x) 计算出y, 但是无法通过 y 计算出x;
  • 加密后的函数进行某些代数运算 == 输入进行代数运算后直接进行加密
    • 同态加法: 加密值的和 == 和的加密
    • 同态乘法: 加密值的积 == 积的加密

BTC 零碎知识

• hash指针
  • 实际上所谓的hash指针知识一个形象的说法, 时机系统中用的时候, 只有hash, 没有指针, 通常全节点会把这些区块保存在key-value的数据库(levelDB)中, hash值作为key, 区块作为value, 所谓的区块链这种链表的结构实际上是在levelDB里面用hash值计算出来的. 只要有最后一个区块的hash值, 就可以通过levelDB查找到对应的区块, 然后找到这个区块, 在这个区块头中就可以找到上一个区块的hash, 通过这个hash就可以找到上一个区块.
  • hash指针保存的是本地的内存地址, 这种地址只有在本地计算机上才有意义, 发送到其他计算机上市没有意义的, 那么在发布区块的时候hash指针是怎么通过网络传输的呢?
• 不可以将一个私钥分成多断, 然后每个人保存一部分,
  • 因为私钥是256位的, 如果两人保存, 那么每个人就是 128位, 如果四个人保存, 每人64位, 这样私钥猜出的难度就会指数级的下降.
• 加密和hash是不同的, 是两回事, 加密是为了将来还能解密, 取hash是无法解密的 是有数据丢失的
  知识改变命运, 但是对知识的一知半解有可能是你的命运变得更差