肖臻区块链b站网课笔记——02-05

视频链接：【北京大学肖臻老师《区块链技术与应用》公开课】 https://www.bilibili.com/video/BV1Vt411X7JF?p=6&;share_source=copy_web&vd_source=33abd457d9415a4317112e8206e5360e

【笔记的内容也结合了评论区里其他同学的笔记】

02-BTC-密码学原理

比特币的本质：crypto-currency

比特币用到密码学中的2个功能：

        ①哈希 cryptographic hash function；

        ②签名（非对称加密）

一、 哈希

3个重要性质：

    ①collision resistance抗碰撞；x≠y，可有H(x)=H(y)

        若有一条信息x，我们希望别人知道我有x但不想让别人知道x具体是什么，就可以通过告诉其Hash(x)。对方可以通过Hash(x)知道你确实知道x这个信息，但他无法（很难）通过Hash(x)反推出x。

    ②hiding单向不可逆；H(x)无法→x

        collision resistance + hiding → digital commitment：

        先公布H(x)，待揭晓后公布x，因为H是可知的，通过求H(x)即可知道x是否被篡改。

    ③puzzle friendly；哈希值的计算是不可预测的，

        如果想要H(x)落在某个范围之内，只能一个个去试。

        该性质保证了比特币系统中，只能通过“挖矿”获得比特币。保证了工作量证明(POW)机制可以运行下去【“挖矿难，但验证易”】。

 

挖矿：找一个随机数nonce，使得H(block header)≤target；

【POW工作量证明 proof of work】

比特币用的哈希函数：SHA-256(Secure Hash Algorithm)

 

一、 签名

（public key，private key）加密用的是公钥，解密用的是私钥

对称的symmetric加密方式：加解密都用密钥（同一把），缺点：密钥分发不方便

非对称的asymmetric encryption algorithm：

    A和C都可用B的公钥对信息加密 → B用私钥解密

公钥相当于“对方的银行账号”，私钥相当于“自己的支付密码”

 

比特币交易的实现：签名（签名用的是私钥，验证签名用的是公钥）

生成公私钥是随机的，一定要用好的随机源

03-BTC-数据结构

比特币的数据结构：①哈希指针Hash Pointers；②默克尔树Merkle Tree

 

一、 哈希指针Hash Pointers

P→□：p存放结构体起始位置；□里是H( )存放结构体哈希值，检验是否被篡改

一、 默克尔树Merkle Tree

好处：只要知道root hash，就能检测出树中的节点是否被修改

 

在比特币系统中，不同区块通过哈希值指针连接，在同一个区块中的多个交易（数据块），则通过Markle Tree的形式组织在一起。

每个区块包含2个部分：

Block header块头：包含根哈希值，没有交易具体内容

Block body块身：包含交易的列表

 

Merkle Tree的作用：提供Merkle Proof

       节点：区块链网络中的计算机，包括手机、服务器……

       全节点full node：保存block header和Block body；

轻节点light node：（手机上的比特币钱包）只保存Block header；轻节点只利用区块链，但并不参与区块链系统维护和构造。

 

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

问题：

1.      Collision resistance保证：若tx被篡改，导致H( )出错，想要修改旁边的H( )，使得两个H( )计算出的上一层H( )保持不变，是不可能实现的。【此行为属于“人为制造哈希碰撞”】

2.      Proof of membership / proof of inclusion ，给我一个轻节点，发给我一个Merkle proof，让我去验证它，时间和空间的复杂度是多少？

3.      Proof of non-membership如何证明？

方法是遍历，复杂度

但是可以对叶节点按哈希值大小进行排序，用二分法，对2个相邻的数据块都分别向上取哈希值，直到root hash并验证，复杂度为

，这种Tree称为Sorted Merkle Tree（比特币没有用）

 

04-BTC-协议

问题：央行CB如何发行数字货币？

方案一：asymmetric encryption algorithm

        支付即复制，是否可以？ → 不可以，Double Spending Attack（双花攻击）

        数字货币本身为带有签名的数据文件，可以进行复制。即：对用户来说，可以将同一货币花费两次。

方案二：每个数字货币上有一个编号，央行要维护一个数据库，有一个表上面记录每个编号在谁的手里。花钱的时候，我把数字货币给你了，你要验证这个数字货币是否有央行的签名，还要和央行核实是否被花出去。【中心化方案】

数字货币发行需要解决的两个问题：

       ①谁来发行？

       ②怎么验证交易有效性，防止双花攻击？

一、 怎么验证交易有效性

1.      比特币如何进行交易

Block chain：有2种哈希指针hash pointer：①块与块之间的；②指向币的来源的

数字货币交易包括：

①input：说明币的来源和支付人的公钥；

②output：说明支付的对象的公钥hash；

 

其他问题：

①转账交易中，A(支付人)需要知道B(收款人)的什么信息？

       A需要知道B的地址（由B的公钥推算出）。

②转账交易中，B(收款人)需要知道A(支付人) )的什么信息？

       B要知道A的公钥（即身份），所有节点都要知道A的公钥（用于验证）。

③如果有B’宣称自己是A，使用A的公钥发起交易，如何防治？

       B’的假的公钥和之前output输出的A的公钥对不上，验证不通过。

 

加密解密：A用B的公钥对信息加密，B用自己的私钥解密。B用A的公钥验证。

       （就像，A给B转账，需要输入B的银行账号，B收到后，检查是否是A的银行账号）

 

H(block header)≤target

 

如何将交易信息写入区块链？

可否各个节点独立完成区块链构建？

        很明显不行，各个节点独立打包交易，形成区块链，必然无法避免区块链内容不一致。从分布式系统角度来说，账本内容需要取得分布式共识（distributed consensus），从而保证区块链内容在不同节点上的一致性。

       分布式哈希表（distributed hash table），系统里许多节点共同维护

 

FLP impossibility result（不可能结论）：

       在一个异步（asynchronous）系统里，网络传输延迟没有上限，哪怕系统中有一个成员是faulty，也无法达成共识。

       FLP给出了一个令人吃惊的结论：在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！

 

CAP Theorem：CAP原则(定理)：

在一个分布式系统中，一致性(Consistency)、可用性(Availability)、分区容错性(Partition tolerance)。CAP原则指的是，这三个要素最多只能同时实现两点，不可能三者兼顾。

 

Consensus in BitCoin 比特币共识协议：POW工作量证明

 

假设系统中大部分的节点是好的，那如何设计一个共识协议？

想法：投票（节点不作为问题；网络等效率问题；※membership投票权问题）

             

Sybil attack 女巫攻击：

       利用社交网络中的少数节点控制多个虚假身份，从而和用这些身份控制或影响网络的大量正常节点的攻击方式。

最早出现于无线通信领域中。Douceur第一次在点对点网络环境中提出这种攻击将破坏分布式存储系统中的冗余机制。Sybil攻击对传感器网络中的路由机制存在威胁。

 

比特币体系的解决方案：算力投票制度。

       H(block header)≤target，一个个寻找nonce满足这个要求，哪个节点找到了nonce，就有了记账权，才有权力发布下一个区块。

其他节点收到后检查区块：

①block header填写是否正确，nBits域是否符合比特币协议中规定的难度要求；②nonce是否符合H(block header)≤target，是否真的有记账权；

③block body中的transaction是否合法：a. 合法签名；b. 未被花过。

分叉攻击 forking attack：下面一行不在最长合法链longest valid chain

若同时挖矿，出现两个等长区块，则维持一段时间，看哪个区块先被接上。

怎么区分是否被接收：若被扩展了，即为接收。

被丢弃的区块为orphan block。

为什么要争夺记账权？为什么要挖矿？

Mining 挖矿 miner矿工

       Block reward出块奖励

       Coinbase transaction 比特币中唯一一个产生新币的途径

       区块链刚上线的时候，每一个发布的区块可以产生50BTC，每隔21万个区块，奖励减半：50BTC → 25BTC → 12.5BTC【目前价值】 → ……

 

05-BTC-实现

区块链是一个去中心化的账本，比特币采用了 基于交易的账本模式 。

另一种模式（eth）：基于账户的模式（account-based ledger），如：以太坊。

比特币这种模式，隐私性较好，但交易时，没有账户这一概念，无法知道账户剩余多少BTC，所以必须说明币的来源（防止双花攻击）。

而基于账户的模式，系统中显示记录账户余额。转账交易就是对一个（多个）账户余额的数字减和另一个（多个）账户余额的数字加。

 

系统中并无显示记录账户包含比特币数，需要通过交易记录进行推算。

 

UTXO(Unspent Transaction Output尚未被花掉的交易输出) ：

在比特币的世界里，并没有一个纪录所有帐户余额的帐本。要确定一个地址现在有多少余额，你要回顾以前所有的交易、并且找到所有寄给你的比特币。再把他们全都加起来。

UTXO集合中每个元素要给出产生这个输出的交易的哈希值，以及其在交易中是第几个输出。通过这两个信息，便可以定位到UTXO中的输出。

 

为什么要维护这样一个数据结构？？？

为了防范“双花攻击”，判断一个交易是否合法，要查一下想要花掉的BTC是否在该集合中，只有在集合中才是合法的。如果想要花掉的BTC不在UTXO中，则要么根本不存在，要么已经被花过。所以，全节点需要在内存中维护一个UTXO，从而便于快速检测double spending（双花攻击）。

 

每个交易会消耗输出，但也会产生新的输出。

每个交易可以有多个输入，也可以有多个输出，总和相抵（total inputs = total outputs）。

total inputs ＞ total outputs，这部分差额作为交易费，给获得记账权的节点。

 “会不会存在节点只想发布区块获得出块奖励而不想打包交易？”

BTC系统设计了Tranction fee（交易费），对于获得记账权节点来说，除了出块奖励之外，还可以得到打包交易的交易费。但目前来说，交易费远远小于出块奖励。等到未来出块奖励变少，可能区块链的维护便主要依赖于交易费了。

 

BTC系统中每21万个区块，出块奖励减半。根据下图计算，基本上出块奖励每4年减半。

什么是挖矿？

区块哈希与前一区块哈希都是以一长串0开头的，挖矿本身就是尝试各种nonce，使得产生的区块哈希值小于等于目标阈值。该目标阈值，表示成16进制，就是前面含有一长串的0。

nonce是一个32位的无符号整型数据，nonce的取值最多为2^32种。但并非将这些nonce全部遍历一遍，就一定能找到符合要求的nonce。2^32这一搜索空间太小，仅调整nonce很大可能找不到正确的结果。可以通过修改Merkle Tree的根哈希值来进行调整。

 

下图为一个小型的区块链，假定左下角交易为coinbase交易，交易发生改变会逐级向上传递，最终导致Merkle Tree根哈希值发生改变。

在实际的挖矿中，包含两层循环。外层循环调整coinbase域（可以规定只将其中前x个字节作为另一个nonce），算出block header中根哈希值后，内层循环再调整nonce。

如果将输入脚本和输出脚本拼接起来可以顺利执行不出现错误，则说明交易合法。

 

挖矿过程的概率分析：

        每次尝试nonce，可以视为一次伯努利试验。在挖矿过程中，一次伯努利试验，成功的概率极小，失败的概率极大。挖矿便是多次进行伯努利试验，且每次随机。这些伯努利试验便构成了a sequence of independent Bernoulli trials(一系列独立的伯努利试验)。伯努利试验本身具有无记忆性。

        对于挖矿来说，便是多次伯努利试验尝试nonce，最终找到一个符合要求的nonce。在这种情况下，可以采用泊松分布进行近似，由此通过概率论可以推断出，系统出块时间服从指数分布。(需要注意的是，出块时间指的是整个系统出块时间，并非挖矿的个人)

 

系统平均出块时间为10min，该时间为系统本身设计，通过难度调整维护其平均出块时间。指数分布本身也具有无记忆性。将来要挖多久和已经挖多久无关。这才是挖矿公平性的保障。对算力有优势的矿工来说，其之前所做大量工作仍有可能会白费。

也就是说，比特币系统中已经挖出和未挖出的比特币总数便是2100万个。

也就是说，挖矿这一过程并没有实际意义，但对比特币系统的稳定起到重要维护作用。

所以，只要大多数算力掌握在好的节点手中，便能够保障比特币系统的稳定。

 

问题：

1.     比特币越来越难被挖到，且出块奖励越来越少，说明其未来挖矿的动力将越来越低？

答：当出块奖励趋于0时，则整个系统将依赖于交易费运行，届时交易费将成为维护比特币系统运行的重要保障。

 

2.     可否"偷币"？（恶意节点能不能将其他账户上比特币转给自己？）

答：不能。因为恶意节点无法伪造他人签名。加入其获得记账权并硬往区块中写入该交易，大多数用户会认为其是一个非法区块，大多数算力将不认可该区块，从而沿着其他路径挖矿，随着时间推移，拥有大多数算力的诚实的节点将会仍然沿着原来区块挖矿，从而形成一条“最长合法链”，该区块变成孤儿区块。攻击者得不到出块奖励，还浪费了电费等成本。

 

3.     可否将已经花过的币再花一遍？

如下图1，若M已经将钱转给B，再转给自己，为一个非法区块，不被其他节点承认。

M只能选择图2方式，将M转账给B的记录回滚掉。这样就有了两条等长合法链，取决于哪一个会胜出。（如果上面交易产生不可逆的外部效果，下面交易回滚便又拿回钱，从而不当获益）

在挖矿之初便要选择上一个区块是谁。并不是获得记账权后才选择插入到哪一个区块之后。

 

1.     如何防范这种攻击？？？

一种简单防范防范便是多等几个确认区块。比特币协议中，缺省需要等6个确认区块，此时才认为该记录是不可篡改的。平均出块时间10min，六个确认区块便需要1小时，可见等待时间还是相对较长的。

 

2.     可否故意不包含合法交易？

答：可以等待后续区块包含。BTC对区块交易数量有大小限制，最大不超过1M，如果区块写不下，就等下一个区块。

 

3.     selfish mining

答：提前挖到但不发布，继续挖下去，等到想要攻击的交易，等了6次确认，认为安全之后将整条链发布出去，试图回滚原来记录。这种情况，需要恶意节点掌握系统中半数以上算力才行，否则无法成为最长合法链。