区块链学习笔记（一）

区块链学习笔记（一）

• 区块链技术的简要介绍

• 密码学原理

• • 哈希
  • 签名

• 数据结构

• • 区块链
  • Merkle tree

区块链技术的简要介绍

区块链可作为数据库，但效率低。
Bitcoin：基于区块链技术的一种加密货币
2015年出现以太坊，一种主流加密货币
以太坊的主要参考书籍：白皮书，黄皮书
开发语言solidity

密码学原理

bitcoin主要用到密码学中的两个功能：哈希和签名

哈希

密码学中用到的哈希函数称为cryptographic hash function，有两个重要性质:

1.collision(哈希碰撞) resistance
哈希碰撞: x!=y,H(x)=H(y) 两个不同的输入算出的值相等
哈希表存在哈希碰撞，哈希碰撞不可避免，因为输入空间远远大于输出空间。
Collision resistance并不是说不会出现哈希碰撞。意思并不是Collision free 而是说没有高效的方法人为制造碰撞。

Collision resistance的作用：找不到M，使得H（M）=H（m），即不能篡改内容且不被检测到。
对一个message求digest，Message=m ， H（m）求哈希值，这个哈希值可以认为是digest可以用来检测消息是否被篡改。
所有哈希函数Collision resistance数学上不能证明，只能实践证明。

PS.MD5可以人为制造哈希碰撞

2.hiding：哈希函数的计算过程是单向的，不可逆的。
得到哈希值后，只可以使用蛮力方法对比输入，从而确定输入。
Hiding前提：输入空间足够大，输入分布比较均匀
Hiding作用：与Collision resistance结合实现digital commitment亦可称为digital equivalent of a sealed envelope

这里以一个例子来说明什么是保密信封：如果有人表示自己能够预测股市。怎么才能证明这个人有其声称的能力（直接将预测结果公开可能会影响股市）

sealed envelope（保密信封）：预测股市的例子中,预测结果提前公布肯能会影响股市。把预测结果写到纸上，封在信封里，信封交给第三方公证机构保管。

计算机的实现方法，H（x）公布，因为哈希有hiding性质并不知道x，之后再公布x。其他人可以通过计算H(x)来验证

注：当输入不满足足够大时，常常在输入后面拼接一个随机数，一起去哈希H（x||nonce）

以上为密码学中的哈希函数，bitcoin中用到的哈希函数还需要满足第三个性质：puzzle friendly

有这样的哈希值：00000…00000XXX…XXX 。必须以k个0开始。并不知道什么样的输入可以算出这样的哈希值。puzzle friendly不知道那个输入更有可能算出这样的哈希值，没有捷径。

简单来说：没有办法通过hash函数的输出结果总结规律推测输入

puzzle friendly和collision resistance有点像但有区别

接下来简要介绍一下btc系统中的挖矿：
挖矿就是找一个nonce，即找一个随机数。将nonce和区块的块头中的其他信息合在一起作为输入，取hash，hash值要小于等于某个指定的目标阈值。
H（block header）<=target
比特币是区块链着的，区块链就是一个一个区块组成的链表。每个区块有一个链头block header。block header中有很多域，其中有一个域是用户可以设置的随机数nonce。
挖矿的过程是不停的取nonce，使得整个block header取哈希后可以落在target中。
puzzle friendly在btc系统中的理解为：挖矿没有捷径，只能不停的试nonce。

挖矿难验证容易。称为difficult to solve，but easy to verify

签名

比特币去中心化，使得比特币开户不需要在一个类似银行的中心化机构完成。btc账户在本地创建公钥和私钥对，这在比特币中就代表一个账户。公钥加密私钥解密，公钥相当于银行账号，转账只需要公钥，取款需要私钥。当btc的私钥丢失后钱包里的钱再也取不出来。且转账时需要签名，10个比特币的转账，A转给B。A用自己的私钥对交易签名，其他人用A公钥验证签名。

这就要求
产生公钥私钥有好的随机源;
比特币签名也需要好的随机源;
先hash在签名;

数据结构

BTC的数据结构采用 区块链+merkle tree

区块链

区块链之间的连接使用：Hash pointers 哈希指针。普通指针存放内存地址
Hash pointers 存放地址和结构体的哈希值

比特币中一个最基本的数据结构是区块链。
区块链：一个一个区块组成的链表。
区块链和普通链表的区别：用哈希指针代替普通指针，block chain is a linked list using hash pointers
被所有区块指向的区块叫做传世区块（genesis block），第一个区块，每个区块都有指向前一个区块的哈希指针。

most recent block（最新区块）前一个区块的哈希指针中的哈希值计算方法为：前面整个区块（不是区块链）的内容，包括哈希指针合在一起取哈希。这种数据结构可以实现tamper-evident log。当有人篡改某个block时，需要改所有指向这个block的hash pointers。只需记住最后一个hash值可以检验对区块链中任意部位的修改。

Merkle tree

将binary tree（二叉树）的普通指针代替为hash pointers
叶子节点存放data 非叶子结点都存放其 letf child和right child的hash值。根节点也存放其左右孩子节点的hash。对根节点取hash，即树的根hash。
只需记住根hash值，可以保护整个树。
比特币中每个区块的交易组织成merkle tree的形式，即在bitcoin中每个数据块是一个交易

Block header中有根hash值，block body中有交易的列表。

比特币中节点分为两类:全节点（保存整个区块的内容Block header+block body），轻节点（只有Block header）

Merkle proof能向一个轻节点证明某项交易写入了区块链中。Merkle proof：从Merkle tree的根节点到交易所在的叶子节点的路径，若该路径上的hash值正确说明交易无误。假设某个新节点（轻节点）想要知道某个交易是否在树中。轻节点知道的信息只有一个根hash值。
验证过程：轻节点向某个全节点发出请求，请求一个能够证明这个交易被包含在这个merkle tree里面的merkle proof。全节点收到请求后，只要把proof路径上的节点保存的另一个hash值发给轻节点（每个节点保存两个hash值）。轻节点在本地可以计算出路径上节点的其中一个hash值。两个hash值拼接后可以验证上一层父节点的hash值。如此这般可以向上计算至根节点。与block header里的根hash比较即可。

这也使得轻节点只能查询和自己相关交易的证明。

Proof of membership
当最下层有n个节点时，Merkle proof 的时间复杂度log（n）

Proof of non-membership证明不包含某个交易
当叶节点不排序时只能整个树都遍历。
当叶节点排序有要求，对叶节点取hash，将hash值从小到大排序。
某交易计算hash后，在tree中找到比其大和比其小的两个节点。向上计算hash。若验证通过，说明交易不存在。时间复杂度log（n）
按hash排好的叫sorted merkle tree（比特币中没有用到，因为不需要做不存在证明）