BTCBasic

区块链基础part1-北大肖臻老师&Chainlink预言机 China学习笔记

1. BTC密码学原理

比特币属于加密货币，可见其中必然会涉及到密码学的知识。而比特币本身开放，其交易记录、交易金额、交易内容甚至源代码都面向全网开放，加密又使用在哪里呢？在比特币中，正是加密确保了信息的不可篡改，保证了区块链本身的优势——不可篡改。

在比特币系统中，加密主要涉及两方面内容

hash(哈希)

在密码学中，采用的哈希函数称为名cryptographic hash function【密码散列函数】，其两个重要性质分别为collision resistance（对哈希碰撞具有抗拒性）和hiding(隐藏性)。

• 哈希碰撞

给定x和y，且有x!=y，但给定一个哈希函数Hash(),可以得到Hash(x)=Hash(y)，则称为hash碰撞。collision resistance保证,如果有Hash(x)!=Hash(y)，必然可以得到x!=y（当然，这是理想状态。有兴趣的可以了解针对哈希碰撞出现后如何处理，如：开放定址法、公共溢出区等）。在实际应用中，哈希碰撞基本上难以避免，我们只要保证给定x，很难找到一个y，能够在x!=y的前提下，使得Hash(x)=Hash(y)就认为其是collision resistance的【目前并不存在一个hash函数可以从数学上证明具有collision resistance的性质】。

• collision resistance的用处

如果我们自己有一条信息x，我们希望别人知道我有x但不想让别人知道x具体是什么，就可以通过告诉其Hash(x)，由于该性质，保证了x!=y时，Hash(x)和Hash(y)是不相等的。我们只需要告诉别人Hash(x)即可，对方可以通过Hash(x)知道你确实知道x这个信息，但他无法（很难）通过Hash(x)反推出x。

• hiding

  我们认为，给定x和Hash(),可以很容易得到Hash(x),但没有办法在已知Hash(x)和Hash()的情况下，反推出x的具体取值，当然这也是一个理想的情况。

• collision resistance和hiding结合实现digital commitment(数据保证)：

在视频中，肖老师提到关于股市预测的案例，某个人对某个股票进行涨停预测，我们如何保证能够知晓其预测是否准确？最简单的是提前公布，等待实际结果出现后验证。但实际中，当提前发布预测后，可能会由于预测者本身对股市实际结果造成影响。所以，应该将提前将其写于纸上并密封，交给第三方机构保管，等到实际结果出现后开启密封与实际对比，这就是digital commitment。而第三方机构需要能够使人信服，在实际生活中，有很多场景并不存在一个这样的第三方机构，而区块链技术正为此提供了一个很好的解决方法。
我们把预测结果看作x，提前公布Hash(x)，等到预测结果发生时间来临后，公布x，如果根据x可以得到公布的Hash(x)，则说明公布的x确实为***的内容。从而，我们可以实际进行判断预测是否准确。实际使用中，为了x足够大，会对x进行“加盐”，对x拼接一个nonce，对其整体取Hash。

• Puzzle friendly

在比特币系统中，还需要第三个性质Puzzle friendly。该性质要求哈希值计算事先不可预测，仅仅根据输入很难预测出输出。例如：我们需要一个哈希值，存在于某一个范围内，只能通过不停运算查找出来。该性质保证了比特币系统中，只能通过“挖矿”获得比特币。也就是说，该性质保证了工作量证明(POW)机制可以运行下去【“挖矿难，但验证易”】。
在比特币系统中采用SHA-256哈希函数。

签名

• 比特币中账户管理
  在第三方中心化系统中，账户开通依赖于第三方。但去中心化的比特币系统中，很明显不能进行“申请账户”。在比特币系统中，申请账户是用户自己来处理的，即自己创建一个公钥-私钥对。（关于公私钥请自行了解非对称加密体系和对称加密体系）
  公钥和私钥的应用保证了“签名”的应用。当在比特币网络中进行转账时，通过“签名”可以明确是由哪个账户转出的，从而防止不良分子对其他账户比特币的盗取。
  在发布交易时，通过自己私钥签名，其他人可以根据公钥进行验证，从而保证该交易由自己发起。也就是说，只有拥有私钥，才能将该账户中的比特币转走。
  【注意：比特币系统中，很难通过生成大量公私钥对来获取他人私钥】

2. BTC数据结构

Hash pointer（哈希指针）

• 指针

  在程序运行过程中，需要用到数据。最简单的是直接获取数据，但当数据本身较大，需要占用较大空间时，明显会造成一定麻烦。因此，可以引入指针这一概念。当需要获取数据时，只需要按照指针所给的地址，去对应的位置读取数据即可，这样大大节省了内存空间。
  在实际中，为了便于程序移植性等原因，指针实际上存储的是逻辑地址而非物理地址。

  区块链结构本身为一条链表，节点为区块。而传统链表实现，便是通过指针将各个节点串联起来而称为最终的链。如下便是我们最常见的一个链表：

  

  但在区块链系统中，并未采用指针，而是使用了哈希指针

• 哈希指针

  如下图对于该节点，我们可以看到有两个指针指向这个节点（实际上为一个），其中P为该节点的地址，H()为该节点的哈希值，该值与节点中内容有关。当节点（区块）中内容发生改变，该哈希值也会发生改变，从而保证了区块内容不能被篡改。

  

  在比特币中，其最基本的数据结构便是一个个区块形成的区块链。

• 区块链与链表区别1：哈希指针代替普通指针

  如图为一个简单的区块链。其中，每个区块根据自己的区块内容生成自己的哈希值，此外，每个区块（除创世纪块）都保存有前一个区块的哈希值。需要注意的是，本区块哈希生成依赖于本区块内容，而本区块内容中又包含有前一个区块的哈希值。从而保证了区块内容不被篡改。

  如图中所示，如果我们想要破坏区块链完整性。篡改B的内容，而C中保存有B的哈希值，所以C也得进行修改。而同样C后区块也得修改。而用户只需要记住最后一个区块链的哈希地址，就可以检测区块链上内容是否被篡改。
  在实际应用中，一整条链可能会被切断分开保存在多个地方。若用户仅仅具有其中一段，当用到前面部分区块数据时，直接问系统中其他节点要即可，当要到之后，仅仅通过计算要到的最后一个哈希值和自己保存哈希值是否一致可以判断所给内容是否确实为区块链上真实的内容。

  

  Merkle Tree

  merkle Tree是比特币系统中又一个重要的数据结构
  首先，回顾一下Binary Tree(如果不懂请自行复习数据结构)。merkle Tree和Binary Tree的区别有哪些？

1. merkle Tree用哈希指针代替了普通指针

   

   上图即为一个简单的merkle Tree，其中A、B、C、D为数据块。可见，A和B各有一个哈希值，将其合并放在一个节点中，C和D同样操作，而后，针对得到的两个节点分别取哈希，又可以得到两个新的哈希值，即为图中根节点。实际中，在区块块头中存储的是根节点的哈希值（对其再取一次哈希）。

   如视频中图片：

   

   该数据结构的优点在于：只需要记住Root Hash（根哈希值），便可以检测出对树中任何部位的修改。

   例如，所绘制merkle Tree中节点B发生了改变，则对应的第二层第一个节点中第二个哈希值便也会发生改变，进而根节点中第一个哈希值也会发生改变，从而导致根哈希值也发生了改变。

   在比特币系统中，不同区块通过哈希值指针连接，在同一个区块中的多个交易（数据块），则通过merkle Tree的形式组织在一起。区块本身分为两部分（块头和块身），在块头中存在有根哈希值（没有交易的具体信息），块身中存在交易列表。

2. Merkle Tree的实际用途

   Merkle Tree可以用于提供Merkle Proof。关于Merkle proof，需要先了解比特币系统中节点。比特币中节点分为轻节点和全节点。全节点保存整个区块的所有内容，而轻节点仅仅保存区块的块头信息。

   为什么要分轻节点和全节点？
   因为硬件的局限。一个区块大小为1MB，对于移动便携设备来说，如果存储区块的所有内容，则所需空间过大，而这是不现实的。所以轻节点只需要存储区块块头信息，全节点存储区块所有内容即可。

当需要向轻节点证明某条交易是否被写入区块链，便需要用到merkle proof。我们将交易到根节点这一条路径称为merkle proof，全节点将整个merkle proof发送给轻节点（如下图所示），轻节点即可根据其算出根哈希值，和自己保存的对比，从而验证该交易是否被写入区块链。只要沿着该路径，所有哈希值都正确，说明内容没有被修改过。

思考：是否存在不安全的情况？如下图我们要验证B，但是H(1)和H(4)都是全节点提供的。全节点可否修改B，通过H(1)调整，使得修改过后的H(1)和轻节点计算出的H(2)一起取得哈希仍然为H(3)？

实际上，这种情况为人为制造哈希碰撞。而由于公开课笔记2中可知，由于哈希函数的collision resistance性质，这种情况是不会发生的。从而，保证了系统的不可篡改性。同时，这样一个merkle Proof的事件复杂度为O(log n),非常高效【证明交易存在】。如果要证明交易不存在，如果不对叶节点规定排序顺序，没有一个效率较高的方法证明不存在。
在比特币系统中，没有相应的需求，所以在比特币系统中并没有对merkle Tree进行排序。

一般来说，一般的链表我们都可以改造为使用哈希指针的链表，但当链表中存在环时，哈希指针便不能再使用。