区块链技术与应用

学习课程为北京大学肖臻老师《区块链技术与应用》公开课

加密货币

比特币被称为加密货币(Crypto-currency)，但并没有加密 ，区块链上的所有内容都是公开的,包括账户地址，交易信息等。区块链中的密码学有哈希和签名

• 哈希：

  密码学中的哈希函数被称为Cryptographic hash function,他有两个重要性质

  • collision resistance：直译为碰撞抗性，碰撞是指哈希碰撞，也就是两个不同输入，有同一个哈希值，一般来说哈希碰撞无可避免，因为输入空间远远大于输出空间。collision resistance是指无法人为制造哈希碰撞，唯一的办法只能是brute-force(暴力破解)。这个性质使得数据一旦被串改，哈希值就会变化，因为无法找到另一个数据的哈希值与原数据相等。

    没有任何一个哈希函数可以被数学证明collision resistance，只能靠实践中经验，有的哈希函数以前被认为是collision resistance，但后来找到了人为制造哈希碰撞的方法，著名的例子就是MD5

  • hiding:直译为隐藏，就是说哈希运算是不可逆的，没法从哈希值倒推出原始数据，哈希值不会泄露数据的任何信息

    hiding成立的条件是，输入空间足够大，且哈希值分布均匀

    这两个性质结合，可以组成一个digital commitment（电子承诺）或者说是digital equivalent of sealed envelope（密封信件的电子等效物），举个例子，假设有人可以预测股市，但是提前发布预测会对结果产生影响，有结果后再发布预测则无法证明是否是提前预测的，解决方法就是使用sealed envelope密封信封把预测内容装起来，交给一个机构保管。两个性质的结合就能在电子世界产生同样的结果，将预测通过哈希发布出去，由于collision resistance我无法修改预测，由于hiding大家不知道我预测了什么。但是两种性质的前提是输入空间够大，输出均匀，对于股票，股票种类是有限的，所以可以通过暴力求解。对于这种，我们可以取一个nonce（随机数），一起进行哈希。

  • puzzle friendly:除了密码学的两个性质以外，比特币用到的哈希函数还要求第三个性质，该性质要求哈希值计算事先不可预测，仅仅根据输入很难预测出输出，例如，我要使一个哈希值存在某个范围内，只能通过不停运算试出来。

    比特币中使用的哈希函数是SHA256：secure hash algorithm,安全哈希算法，满足以上三个性质

• 签名：

  讲签名先讲下比特币中的账户管理，开户不需要任何人的批准，只需要创立一个public key公钥和private key私钥的对，公私钥的概念来源于非对称加密，将公钥发布出去，大家使用我的公钥加密，发送给我后，我用自己的私钥解密。比特币系统中，公钥就相当于账号，私钥相当于密码，但是比特币系统是不加密的，信息公开，实际上公私钥是用来签名的。当我们发布一个交易的时候，用自己的私钥进行签名，其他人收到这个交易之后，再用我的公钥去验证这个签名的正确性。

  账户都是本地独立的生成公私钥对，不需要任何人的批准，那么有没有可能生成两个一样的密钥呢？理论可行，实际不可行，如果是256位的哈希值，产生相同公私钥的可能性是微乎其微的，前提是产生公私钥的时候有个好的随机源，而且之后每一次签名也要有好的随机源，非则会有私钥泄露的风险

比特币中的数据结构

• 哈希指针：

  区块链和普通链表的区别，有个不同就是用哈希指针代替了普通指针，除了创世区块，每个区块里都有个哈希指针指向前一个区块，做哈希运算时，会把前一个区块的全部内容包括里面的哈希指针一起做哈希运算，得到哈希指针。指向最后一个块的哈希指针存在了系统里，这样，只要任意一个块被篡改，后面全部哈希指针全都对不上，就算改了一路，也无法改变存在系统里的指向最后一个块的哈希值。

• Merkle tree:梅克尔树，还有一种叫binary tree二叉树，两者的不同就是，Merkle tree用哈希指针代替了普通指针，用于快速查找更改。每个数据块哈希一次，每两个哈希值再合起来进行哈希，一步步往上，形成树形结构，最后得出根哈希值。Merkle tree的用途可以提供Merkle proof，梅克尔证明。

  比特币中的节点分为全节点（保存整个区块，block header block body的内容）和轻节点（只保存block header）,如果要向一个轻节点证明，某个交易已经写入到区块链的：找到交易所在位置，从该位置一直往上直到根节点的路径，这条路劲就是Merkle proof，如果最下面的节点是奇数个，该单生节点重复一次和自己组成一对进行哈希。

  

BTC协议

• double spending attack:双花攻击，花两次攻击。数字货币所面临的一个主要挑战就是如何防范双花攻击，数字货币是一个文件，就算有发行商的签名，别人无法伪造，也可以通过复制，把钱花两次。所以要核实是否被花过，是否真的在对方手里。

  去中心化的数字货币需要解决谁有铸币权和如何验证交易有效性，在比特币中，铸币权由挖矿决定。

  

  如图所示，A铸币得了10元，给了BC各5元， 在A支付货币的交易中，需要有A的私钥签名，A的公钥，其他人用A的公钥验证，还要有A支付货币的来源，和收款方BC的公钥取哈希值。而作为收款人的BC则需要知道A的公钥，用于验证签名，以及是否是A的账户。若交易不合法则不加入区块中。

  如何知道BC的公钥地址呢？公钥是公开的，但比特币并没有提供查询功能，所以需要BC自己告诉A，可以发布公钥到个人网站，张贴二维码等方式。若是有人假装是A，用自己私钥签名和附上自己公钥呢？所以货币来源A(10)也带有A的公钥，除了要验证A的签名还要和货币来源公钥做对比

Block head 和Block body

Block header	Block body
version-版本	transaction list-交易列表
hash of previous-指向前一个区块块头的哈希指针	merkle tree-梅克尔树
Merkle root hash-梅克尔树根哈希
target-挖矿难度，目标阈值，加密后为nBits
nonce-挖矿用的随机数

全节点和轻节点

full node-全节点是保存所有信息的，所以全节点又被称为fully validating node直译为完全验证节点；light node-轻节点只保存block header的内容，一般来说轻节点无法独立验证交易的合法性，轻节点没有参与区块链的维护，大部分节点是轻节点。

每个账户都可以发布交易，这个交易会广播给所有节点，那么谁来决定哪些交易合法非法，能否被写到下一个区块呢？账本的内容需要取得分布式的共识，比特币中的共识协议要解决的问题是小部分节点可能是有恶意的，一种想法是直接投票：一个节点把交易打包后，广播给所有节点，让所有人投票是否合法能否加入，这种方法是不行的，如果一半的节点“行政不作为”不投票，则永远无法通过，而且投票比较耗时还有网络延迟的问题，还有个更大的问题，就是会：投票要决定谁是membership，谁才有投票权，如果是制定一个标准比如联盟链，大多数是公司，那么这种情况投票是可行的，但是在比特币系统中创建账户是很容易的，有恶意的节点可以产生大量账户，当超过一半时，就能操控结果，这就是sybil attack女巫攻击指一个人像女巫一样拥有多个身份伪装，所以简单的直接投票是不行的

Sybil来自于一部电影《Sybil》女主拥有16个人格，扮演着不同角色

比特币系统中确实是使用投票，但不是根据账户数量，而是根据算例来投票：每个节点都可以在本地组装一个区块，把认为合法的交易放入，然后开始尝试各种nonce值，在区块头里有个域H(block header)<=target看哪个节点先找到符合要求的nonce,他就有了记账权，发布区块后，其他节点收到之后，验证区块的合法性和nonce的正确性，假设交易不合法，这个区块就不会被节点接收。所以这是与算力挂钩的，获得记账权的几率就是自身算力在全网算力中的百分比，无论开多少账户，同一台机器的算力是不变的，全网的算力也是不变的。有效的防止了女巫攻击

BTC实现

比特币是基于分布式账本transaction-based ledger的，没有显示余额的信息。想知道一个账户有多少余额就得通过交易记录推算。比特币中的全节点要维护一个叫UTXO的数据结构（Unspent Transaction Output没有被花掉的交易输出），一个交易可以有多个输出和输入，输入就是发款人，输入就是收款人，比如A->B(5BTC)这笔交易中，A给了B钱，B就是输入，A就是输入，也可以有多个输入输出如：A->B(5BTC),A->C(3BTC)这两个可以放在同一笔交易里，输入都是A，输入是BC，若B把钱花了，C没有，UTXO这个集合里的元素会记录这个交易的哈希值以及这个输出是在交易里的第几个输出。这两个信息就可以做到定位。每个交易都会消耗一些输出同时也会产生新的输出。且总输入=总输出，也有不等于的情况，需要给记账节点交易费，防止节点只打包自己的区块，而不帮其他人记账，目前比特币中的交易费都比较小，但随着挖矿奖励的减少，交易费的占比会逐渐增大。

还有一种余额查询方式是基于账户account-based ledger的模式，如以太坊，这种模式显式地记录每个账户上有多少个币

下面是比特币块头数据和数据大小、类型

挖矿就是不断尝试各种nonce，目前挖矿难度极高，nonce是32位无符号整型，而target是256位，所以可能这2^32个数里找不到一个满足条件的，而块头唯三能修改的就merkle root hash、time和nonce，其中time时间戳只能小范围的改动，影响不大。在每个区块里的第一个交易是铸币交易，是矿工给自己的输入为coinbase输入为自己地址的交易，coinbase可以随便写内容，所以可以通过修coinbase来修改merkle root hash

如何防止回滚交易：在比特币中，如果有分叉的链，则最长合法链为有效链，若在商品交易中，写入交易后，又从前一个区块写入另一笔交易，将原本支付给商家的比特币转给自己，接着沿着新链往下挖，则使交易回滚，白嫖了商品，所以在商家在交易被写入后，等待6个区块（10分钟一个区块，大约一小时）才开始给买家发货。这样回滚难度就会大幅度增加。

比特币网络

应用层：BitCoin Blocck chain

网络层：P2P Overlay Network

比特币网络的设计原则是简单、鲁棒而不是高效（鲁棒性是系统的健壮性，是系统异常和危险情况下生存的关键），每个节点维护一个邻居节点的集合，消息传播在网络中采取叫flooding（洪水，淹没，泛滥）的方式：节点第一次听到消息的时候，传播给其他所有的邻居节点，同时记录下，下次再收到这个消息的时候不再转发。

邻居节点的选取

邻居节点的选取是随机的，没有考虑底层的拓扑结构，这样设计的好处是增强鲁棒性，但牺牲了效率，向身边人转账和向美国转账速度其实是差不多的。

交易池

比特币中的每个节点要维护一个等待上链的交易的集合：第一次听到某个合法交易的时候，把交易加入集合，并转发给邻居节点，若两个冲突交易（如双花）同时发布，每个节点由于位置不同，先收到的交易也不同，会取先接收到的交易放入集合，把后收到的冲突交易认为是非法的，不接收它。当节点听到新区块发布且包含池中的交易时，节点就会把集合内的对应交易删掉，如果新区块内的交易和池中的交易冲突，那么节点也会把对应交易从集合里删除，防止double spending

BTC挖矿难度

挖矿就是不断改变尝试block header里的nonce，使得H(Block Header)<=target即：块头的哈希值小于等于目标阈值，target越小，difficult挖矿难度越大

• 为什么要调整挖矿难度：
  为了控制出块的时间，随着设备的改进、挖矿人员的增加，算力在不断增加，所以要增大难度，否则出块速度会不断增加。而出块时间过短可能会引起区块链经常性的分叉，而这种分叉会让恶意节点更容易发动分叉攻击，存在多条同长分叉时，算力会被分散，这时恶意节点专注于自己的分叉，即使没有51%的算力也可以很容易发起攻击。

• 如何调整挖矿难度：

  比特币中设定，每2016个区块（大约2个星期）就调整一次挖矿难度，target=target*actual time/expected time,即：本次的难度=上次难度 （实际出矿时间 / 预期出矿时间），实际代码当中，调整都有四倍的限度，比如实际时间超过8个星期（正常2星期，24=8），也只会算8星期，主要避免系统出现意外情况而导致难度出现大幅度变动；若实际时间不足半个星期（正常2星期，2的四分之一为0.5）也只会算为半个星期，所以实际时间最大值为8星期，最小值为0.5星期。

• 如何保证所有人都调整：

  难度调整是写在代码中的，虽然因为区块链的开源的，恶意节点也许可以不调整或修改挖矿难度，但是修改了挖矿难度就会target改变目标阈值，而算出满足阈值的nonce之后，要给链上的所有人验证，这时候验证是不一定能通过的，因为别人的阈值不一样。而且就算满足target，因为修改了难度，城市的矿工也不会认同这个非法区块，block header里有个nBits，它 是target编码后的版本，只有四个字节，target有32个字节，所以本身并不在块头中，

BTC挖矿

全节点和轻节点详细

• 全节点：
  • 一直在线
  • 在本地硬盘上维护完整的区块链信息
  • 在内存里维护UTXO集合，以便快速检验交易的正确性
  • 监听比特币网络上的交易信息，验证每个交易的合法性
  • 决定哪些交易会被打包到区块里
  • 监听别的矿工挖出来的区块，验证其合法性
  • 挖矿：
    • 决定沿着哪条链挖下去？缺省情况下沿着最长合法链挖矿
    • 当出现等长的分叉时，选择哪个分叉？缺省情况下选择最先听到的分叉
• 轻节点：
  • 不是一直在线
  • 不用保存整个区块链，只要保存每个区块的块头
  • 不用保存全部交易，只保存与自己相关的交易
  • 无法检验大多数交易的合法性，只能检验与自己相关的交易的合法性
  • 无法检测网上发布的区块的合法性，但能验证难度，因为只用到块头
  • 可以验证挖矿的难度
  • 只能检测哪个是最长链，不知道哪个是最长合法链，轻节点假设矿工是理智的，不会沿着非法区块挖下去

比特币网络中大多数节点是轻节点，如果只是转账而不挖矿的话，只使用轻节点就可以了

随着时代的发展，挖矿设备也在不断变化，第一代使用的是CPU挖矿，第二代使用GPU挖矿，GPU的并行计算能力比CPU强，CPU主要用于控制，所以GPU挖矿增加了算了又减少了对性能的浪费，但仍然有部分功能使用不到，比如关系到浮点数计算的元件。到了第三代，使用的是ASIC芯片application-specific integrated circuit专用集成电路挖矿，这是专门为挖矿设计的芯片，它上面没有多余的电路，整个芯片就是为了比特币计算哈希值而设计的，是性价比最高的。而且为一种加密货币设计的Asics芯片就只能挖这种货币，不能挖其他的加密货币，除非这两种币使用同一个mining puzzle。ASIC芯片的研发周期很长，如比特币的芯片可能需要一年，且比特币的竞争越来越激烈，定制的ASIC芯片可能用不了几个月就过时了，又得买更新的强大的芯片。所以购买ASIC矿机的时机非常重要。

整个趋势由通用设备转向专用设备，实际上这种趋势与比特币最初的去中心化是违背的，所以现在有的货币采用了ASIC resistance 抗ASIC化，目的是让通用计算机也能够参与挖矿的过程。

挖矿的另一个趋势，就是大型矿池的出现，单个矿工就算用了ASIC芯片，收入也是不稳定的，对于所有人每10分钟挖出一个区块，但是对于个人，挖出区块可能得一年。矿池就是将矿工集合起来，一个节点驱动着许多矿机：

一个矿池一般有一个pool manager矿主下面连着许多miner矿工，矿工只负责计算哈希值，其他的全节点的功能交给矿主如监听交易，打包区块等。收益分配用工作量证明分配：矿工计算时会得到部分share和most valid block 几乎有效的区块哈希值与实际哈希值相似，把这个share提交给矿主，矿主记录起来作为工作量证明，除此外没有其他用途，没有功劳也有苦劳啊，一个矿工尝试的nonce越多，它得到的share就越多，那么矿工挖到矿之后能不能提交呢？答案是不能，因为哈希值除了nonce还有其他值共同决定，而打包区块是矿主，收款人也是矿主的地址，如果改了地址，哈希值也会改变。

大型矿池的弊端：大型矿池使算力更加集中，GHASH矿池有段时间甚至占据了全网近50%的算力，好在矿主主动配合减低比例，而现在虽然没出现这种情况，但仍然有51%攻击的风险，一个组织可以有多个矿池，而且通过降低管理费等亏本方法吸引群众入池，使自己组织占据大量算力，而且矿工只负责计算哈希值，由矿主分配工作，他们可能并不知道自己在发动攻击。

BTC-比特币脚本