区块链技术与应用（一）

一、课程简介

区块链不等于比特币。比特币是基于区块链技术的一种加密货币。

学习参考资料：
１、比特币白皮书中文版
２、以太坊白皮书中文版＋注释
３、以太坊黄皮书
4、Solidity官方文档（v8.0）

二、密码学原理

比特币是一种加密货币（crypto-currency）。区块链上所有的交易内容都是公开的，包括账户地转账金额等。

在比特币系统中，主要运用了密码学中的两个功能，一个是哈希，一个是签名。

1.哈希

密码学中使用的哈希函数有两个重要性质。

①哈希碰撞（cryptographic hash function）

哈希碰撞是指两个输入通过哈希函数计算出来的哈希值相等。哈希碰撞比较常见，比如在哈希表中，不同的输入可能会被映射到同一个哈希位置。

• 哈希碰撞的作用：

低效的解决哈希碰撞的方法：暴力剖解(brute-force),遍历所有输入的可能性，找到哈希碰撞的输入。这种方法工作量太大、低效。 效率太低！！！

注意：哈希碰撞是不可避免的，因为输入空间大于输出空间。哈希碰撞是客观存在的，没有什么高效的方法人为地去制造哈希碰撞。（MD5加密算法已经可以被人为地计算出哈希。）

②不可逆性（hiding）

不可逆性是指哈希函数的过程是单向的，不可逆的。这个性质成立的前提是输入的空间要足够大，使得暴力破解的方法不可行，而且输入的分布要比较均匀，各种取值的可能性都差不多。

• 不可逆性的作用：

可以和哈希碰撞结合在一起，用来实现哈希函数将预测结果加密，实际结果发布后将预测结果和实际结果对比，能够使人信服预测结果是在实际发布前预测的（digital commitment or digital equivalent of sealed envelope）。sealed envelope现实意义是指如果一个人预测结果，但是不能提前公开，因为只要公开，不论预测结果对错，都会影响现实世界的变化。但是可以将预测结果交给第三方公证，待事实结果发布后，公开并比较预测结果与事实结果。【简单理解解释：把预测结果放到一个信箱，待开箱后，判断真实结果和之前预测的结果是否一致。】

③Puzzle Friendly

哈希值的计算事先不可预测，只根据输入很难预测出输出。如果需要找出一个哈希值存在某个范围内，只能通过一个一个运算才能找出。

Puzzle friendly这个性质保证了比特币系统中，只能通过挖矿获得比特币。

挖矿就是找一个随机数nonce，nonce和区块头里其他信息合在一起作为输入，取出一个哈希来，那个哈希值要小于某个指定的目标预值，只能通过一个一个试，才能找出在范围中的值。挖矿的过程没有捷径，只能通过大量的一个一个试nonce，才能找到符合要求的值，这个过程叫做工作量证明（POW，proof of work）。

当有人找到了符合要求的nonce发布出去后，其他人要验算是否符合要求只需要算一次哈希值是否小于目标预值。挖矿很难，验证很容易。这个性质叫做difficult to solve,but easy to verify。

比特币中用的哈希函数叫做SHA-256。SHA是指secure hash algorithm，满足哈希函数的三个性质。

哈希碰撞和puzzle friendly性质有一定联系，但不完全一样。

2.比特币系统中的账户管理

比特币是去中心化的，每个用户可以自己开设账户，不需要任何人批准。开户的过程就是创立一对公钥和私钥。

公私钥概念来源于非对称加密体系（asymmetric encryption algorithm）。

最早的加密体系是对称加密（symmetric encryption algorithm） ，发送方和接收方事先商量好一个密钥（encryption key），发送方将信息加密后发送给接收方，接收方收到后用密钥解密，对称加密的前提是能有个安全的信道，将密钥安全地分发给通讯方。（弱点：密钥分发不方便）

比特币中的公钥私钥作用：用户签名。

交易发起方用自己的私钥对交易进行签名，其他人收到交易后用发起方的公钥去验证签名是否正确。产生两个相同公私钥的账户的可能性微乎其微。生成公私钥的过程是随机源。（a good source of randomness）

非对称加密使用接收方的公钥和私钥，公钥加密，私钥解密。

好处：加密公钥不需要保密，私钥保存在本地，解决了对称加密中密钥分发不方便的问题。

比特币中使用的签名算法，不光是生成私钥的时候要有好的随机源，之后每一次签名的时候也要有好的随机源。只要有一个签名的过程中的随机源不好，就有可能泄漏私钥。

三、比特币中的数据结构

1.哈希指针（hash pointers）

普通的指针存储的是某个结构体在指针中的地址，哈希指针要存储地址和哈希值。

比特币中最基本的数据结构就是区块链。区块链是一个个区块组成的链表。

区块链与其他普通链表的区别：

• 区块链用哈希指针代替了普通指针。
• 区块链的一个哈希指针改变会影响到其他哈希指针，普通指针变化不会影响其他的指针。【多米诺效应】
• 每一个区块都保留了指向前一个区块的哈希指针

哈希指针的内容是把整个区块的内容取哈希。

区块链数据结构的好处：

通过这种数据结构可以实现 tamper-evident log（防篡改log,后一个区块保存了前一个区块的哈希值，前一个区块修改了区块的内容，哈希值会改变，后一个区块会找不到前一个区块的哈希指针，所以就要修改后一个区块的哈希指针，以此类推，系统保留的哈希指针也需要修改，就只需要记住系统中保留的哈希，就可以检测任何一个部位的修改。系统中任意一个区块的哈希值发生改动，最终保存的这个区块的哈希值也会发生改动。即“牵一发而动全身”=>多米诺骨牌效应）

比特币可以根据这个性质，只保存最近的几个区块哈希。如果需要找之前的区块，可以使用哈希指针找到正确的区块。

2.默克尔树(merkle tree)

Merkle tree 和 binary tree 的区别：
用哈希指针代替了普通的指针

B树的特点：数据值存放在叶子结点

Merkle tree的好处：只要记住根哈希就可以检测出对树中任何部位的修改。

比特币当中各个区块用哈希指针连接在一起，每个区块所包含的交易是组织成Merkle tree的形式。每层数据块是一个交易->叶子节点。每个区块分为两部分，块头（block header）和块体（block body），根据哈希值存储在块头中，即这个区块所包含的所有交易组成的Merkle tree的根哈希值是存储在这个区块的块头中，但是块头中没有交易的具体内容，只有根哈希值。块体中有交易的列表。

Merkle tree的用途：提供Merkle proof

比特币中的节点分为两类：

全节点：保存整个区块的内容，包括块头和块体，有交易的具体信息

轻节点：只保存块头，如手机上的比特币钱包。

如何向轻节点证明某个交易是写入到区块链中？

使用Merkle proof,找到交易所在的位置。（从交易一直往根节点的路径就是Merkle proof。）

轻节点向某个全节点发出请求，请求一个能够证明交易被包含在这个Merkle tree的Merkle proof,全节点收到请求后，只要全节点请求的哈希值(红色的)发给轻节点即可，轻节点可以通过这些哈希值在本地计算出SPV本地计算哈希值（绿色的），首先算出交易的哈希值，再和旁边红色哈希值拼接可以算出上一层哈希，依次类推出整棵树的根哈希值。轻节点把根哈希值和块头的哈希值比较就可以知道交易是不是在Merkle tree里。轻节点收到Merkle proof后只要从下往上验证，沿途的哈希值都是正确的，即可证明。

注意:查询哈希值只能查询某个交易的从下往上分支的哈希，不能查询其他分支的哈希。这种证明叫做proof of membership或者proof of inclusion,即可证明Merkle tree包含了某个交易。时间复杂度是O(logn)