内容

复习的书是《区块链：技术驱动金融》。还得配合着PPT，有点麻烦。

第1章密码学及加密货币概述

码学中的哈希算法（Hash）和数字签名（digital signature）技术

1.1 密码学哈希函数

哈希函数是一个数学函数，具有以下三个特性：

其输入可为任意大小的字符串。
它产生固定大小的输出。
它能进行有效计算，简单来说就是对于特定的输入字符串，在合理时间内，我们可以算出哈希函数的输出。更准确地说，对应n位的字符串，其哈希值计算的复杂度为 $ O(n) $ 。

使哈希函数达到密码安全，我们要求其具有以下三个附加特性：

碰撞阻力（collision-resistance）；
隐秘性（hiding）；
谜题友好（puzzle-friendliness）其中，谜题友好并非加密的hash函数的一般要求，但是对数字货币却是

碰撞阻力

加密的哈希函数的第一个特性是它要具有碰撞阻力。这里的碰撞指对于两个不同的输入，产生相同的输出。如果对于哈希函数H(·)，没有人能够找到碰撞，我们则称该函数具有碰撞阻力

如果无法找到两个值，x和y，x≠y，而H(x)=H(y)，则称哈希函数H具有碰撞阻力。

根据鸽巢原理（Pigeonhole Principle），我们可以得出，必然会有大量可能的输入被映射到任意特定输出.。生日悖论（birthday paradox）对于某些哈希函数，存在有效的测试碰撞的方法。但对于某些哈希函数，我们无法确认识别碰撞的有效方法是否存在，我们只是怀疑这些函数具有防碰撞特性，但是我们已经证明，世界上没有哈希函数具有防碰撞特性。

用处

哈希输出作为信息摘要（message digest）

隐秘性

哈希函数H具有隐秘性，如果：当其输入r选自一个高阶最小熵（high min-entroy）的概率分布，在给定H（r‖x）条件下来确定x是不可行的。

应用：承诺

承诺协议一个承诺协议方案由两个算法构成： ● com:=commit(msg, nonce)，承诺函数将信息（msg）和一个临时随机数（nonce）作为输入，输出就是一个“承诺”。 ● verify(com, msg, nonce)，验证函数将某个承诺输出（com）、临时随机数（nonce）及信息（msg）作为输入，如果com：=commit(msg, nonce)，则返回“真”（true）；反之则返回“假”（false）。我们要求以下两个安全特性要成立： ● 隐秘性：已知com，没有可行的方法找到msg。 ● 约束性：没有可行的办法找到两组(msg, nonce)和(msg’, nonce’)， msg≠msg’，而commit(msg, nonce)：=commit(msg’, nonce’)。

对于每次的承诺值，你都需要选择新的随机值，这一点很重要。在密码学中，术语nonce是指，该取值只能使用一次。

commit(msg, nonce):=H(nonceǁmsg)

隐秘性：已知H(nonce‖msg)，没有可行方法找到 msg。
约束性：没有可行方法找到两对(msg, nonce)和(msg’, nonce’)， msg≠msg’，而H(nonce‖msg):=H(nonce’‖msg’)。

谜题友好

解释：如果有一个人想找到y值所对应的输入，假定在输入集合中，有一部分是非常随机的，那么他将非常难以求得y值对应的输入。

如果对于任意n位输出值y，假定k选自高阶最小熵分布，如果无法找到一个可行的方法，在比 $ 2^n $ 小很多时间内找到x，保证H(k‖x)=y成立，那么我们称哈希函数H为谜题友好。

应用

如果一个哈希函数具备谜题友好特性，这就意味着对于这个谜题没有一个解决策略，比只是随机地尝试x取值会更好。因此，如果我们要把谜题做成很难解决是可以的，只要我们能用适合的随机方式生成谜题ID。当我们讨论比特币采矿（是一种搜索谜题）时会采用这一思路。

安全哈希算法（Secure Hash Algorithm 256，简称SHA-256）

将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数，我们称这个转换过程为MD （Merkle-Damgard）变换

可用于固定长度，具备碰撞阻力的哈希函数被称为是压缩函数（compression function）

哈希指针及数据结构

哈希指针是一个指向数据存储位置及其位置数据的哈希值的指针。一个普通的指针可以告诉你数据存储的位置，哈希指针不但可以告诉你数据存储的位置，并且还可以给你一种方式，让你验证数据没有被篡改过。

我们通过哈希指针构建一个链表，我们将这个数据结构称为区块链（block chain）。在普通链表中有一系列区块，每个a区块既有数据也有一个指向上一个区块的指针。而在区块链中，上一个区块指针被置换为哈希指针。因此，每个区块不仅能告诉我们上一个区块的值在哪里，还包含了该值的摘要，使我们能够验证那个值没有改变。我们存储链表头部（the head of list），即一个普通的哈希指针指向最近使用的数据区块

如果对手想要篡改区块链中任意地方的数据，为了保证整个内容一致，他需要篡改所有的哈希指针直至最开始的地方。他最终将碰到障碍，因为他不能篡改链表头部的指针。这样，我们便知道，仅通过记住一个哈希指针，我们就基本记住了整个链表的防篡改哈希值。因此，我们可以搭建一个包含很多区块的区块链网络，链表头部的哈希指针被称作创世区块（genesis block）

Merkle Tree 梅克尔树，默克尔树

使用哈希指针的二叉树也叫作梅克尔树 (Merkle trees)，以其发明者拉尔夫·梅克尔（Ralph Merkle）的名字命名。
挺显然的，不写了

在梅克尔树的数据结构中，所有的数据区块都被两两分组，指向这些数据区块的指针被存储在上一层的父节点（parent node）中，而这些父节点再次被两两分组，并且指向父节点的指针被存储在上一层的父节点中，一直持续这个过程，直到最后我们到达树的根节点。

隶属证明

（这个问题应该是还需要堂兄弟节点进行证明）
比如这个树的其他节点被换了

非隶属证明

通过展示被验证区块之前的区块路径，以及被验证区块之后的区块路径，就可以达到目的。如果之前、之后两个区块在树上是连续的，那么这说明了被验证区块与该梅克尔树之间是非隶属关系。因为被验证区块确实隶属于梅克尔树，它需要在两个条目之间，而如果两个条目是连续的话，二者之间则并没有空间。

1.3 数字签名

数字签名（digital signatures）

第一，只有你可以制作你自己的签名，但任何看到它的人都可以验证其有效性；第二，我们希望签名只与某一特定文件发生联系，因此该签名不能用于表明你同意或支持另一份不同的文件。对于手写签名来说，第二条就如同确保别人不能将你的签名从一份文件上剪下来，贴到另一份文件的末尾那样。

第一个特性很直接，那就是有效的签名必须通过验证。如果我用我的密钥sk签署了一条消息，之后有人试图通过使用我的公钥pk验证关于同一条消息的签名，该签名必须证实为正确。这个特性是对签名有效的最基本要求。不可伪造性。第二个要求计算上不可能伪造签名。也就是说，知道你公钥并看到你在某些信息上签名的对手，不能伪造他还未见过的你在其他信息上的签名。这一不可伪造特性类似于我们与对手之间在进行一场游戏，游戏的使用在密码安全证明中很常见。

不可伪造性游戏是对手（黑客）和挑战者一起玩这样一个游戏：如果黑客可以在一个之前没有见过的消息上进行签名，那么黑客就赢得这个游戏；反之，如果黑客做不到，挑战者就赢得游戏，从而可以证明这个数字签名方案是不可伪造的。

实践中的考量

很多签名算法是随机的（特别是比特币使用的算法），因此我们需要随机性的良好来源。
对信息的哈希值进行签署，而非对信息本身进行签署。
我们后面会用到的另一个技巧是，可以对于哈希指针进行签署。如果你签署了哈希指针，那么该签名覆盖（或者说保护）整个结构——这不仅仅是哈希指针本身，还包括哈希指针指向的整个区块链。

传统签名与数字签名

传统签名：保证信息真实性，验证签名者身份数字签名：又称公钥数字签名。是只有信息发送者才能产生的别人无法伪造的一段数字串，数字串也是对信息真实性的有效证明

加密过程

私钥加密，公钥验证。这时整个加密的信息就是一个数字签名(Digital Signature)

ECDSA算法

是个椭圆曲线算法

个人密钥：256位
公钥（未压缩）：512位
公钥（压缩）：257位
待签名信息：256位
签名：512位

1.4 公钥即身份

将公钥视为身份的一个结果是，你可以随时制定新的身份——你可以简单通过数字签名方案中的generateKeys程序，生成新的密钥对sk和pk。pk是你可以使用的新的公共身份，sk是相应的密钥，只有你自己知道并可以让你代表身份为pk发声。在实践中，你可能会使用pk的哈希作为你的身份，这是因为公钥很大。如果是这样的话，为了验证消息来自你的身份，人们会需要验证：（1）你的身份确实是pk的哈希；（2）信息能经过公钥pk验证。

去中心化身份管理

你可以自己作为用户注册，而无须到一个中央机构注册为系统用户。你不需要别人给你一个用户名，你也不需要告诉任何人你会使用什么名字。事实上，这就是比特币对待身份的方式。这些身份在比特币语言中被称为地址。你可以常常听到地址这个词，用于比特币或加密货币相关的内容中，而地址其实就是公钥的哈希值。作为去中心化身份管理方案的一部分，它就是某人凭空捏造的一个身份而已。

在比特币系统中，你不需要明确地注册或揭露你的真实身份，但是你的行为模式本身可能是可识别的。 人们看到这些声明便知道拥有这个身份的人做出了特定的一系列行为。他们能够开始将细节联系起来，从这一系列的行为推断出你的真实身份。随着时间的推移，一个观察者可以将这些事情联系起来，并推断出这样的结论：“天，这个人的行为好像乔（Joe），可能这个人就是乔。”

1.5 两种简单的加密货币

高飞币

高飞币只有两个规则：

第一个规则是指定高飞可以随时创建新币，且这些新创建的币都属于他。
第二个规则是，拥有此币的人可以将其转给其他人。

高飞币的规则

高飞（ Goofy ）可以签署声明表示他使用唯一的货币编号来创建一个新币
货币的所有人可以通过签署声明表示货币的转让，即"将这个货币转移给 X ( X 为公钥）"
任何人可以追根溯源，验证一枚货币的有效性

高飞币的优缺点

缺点：

1.货币发行权控制在 Goofy 手中
2.双重支付（ Double Spending )

优点：

货币的转让技术

财奴币（ScroogeCoin）

财奴币是以高飞币为基础创建的，但在数据结构方面更复杂。第一个主要概念如下：一个叫财奴的指定实体将负责公布包含所有发生过的交易历史记录的仅增账目（append-only ledger）

每个数据块都包含一次交易（在实践中，一种优化的做法是将多次交易放入同一个区块中，比特币就是这样做的），每个区块包含交易的ID、交易的内容，以及上一个区块的哈希指针。财奴数字签名是针对最后一个哈希指针（它约束整个结构中所有的数据），并将签名与区块链一起发布。在财奴币中，只有在由财奴签名的区块链的交易才算数。

为什么除了让财奴签署每个区块，我们还需要一个带哈希指针的区块链？这样做是保证仅增特性。因为财奴有可能试图增加或移除交易记录，或者改变已有交易，而一旦有了哈希指针，将会影响到后面所有的区块。

两种操作

第一，造币

第二种交易是付币（PayCoins）。这一交易会消耗币，就是说消除它们，并创建具有相同总值的新币。

规则

财奴币（ ScroogeCoin )交易有效当且仅当

被消耗的货币为有效货币，之前的交易中已经创建
本次交易不是双重支付
本次交易产生的币值等于消耗币值
本次交易消耗的所有货币均有其所有者的有效签名

财奴币（ ScroogeCoin ）优缺点

优点

引入了 Ledger 来防止双重支付

缺点：(中心化)

心双可以拒绝公开交易，不提供服务财奴可以随时造币

第2章比特币如何做到去中心化

~~终于破解了suming的pdf权限问题，可以复制了，省事很多~~

2.1 中心化与去中心化

中心化与去中心化也并非水火不容，其实没有一个系统是完全中心化，或者是完全去中心化的。

混合模式

去中心化解决的问题(必考)

谁在维护交易账本？
谁有权利批准哪个交易是正当有效的？
谁在制造新的比特币？
谁在制定系统变化规则？
比特币是如何取得交易价值的？

前三个问题反映了比特币协议的技术细节，我们将在本章重点讨论

2.2 分布式共识（distributed consensus）

分布式键值（key-value）存储库

分布式共识协议

在一个有n个节点的系统中，每一个节点都有一个输入值，其中一些节点具有故障，甚至是恶意的。
一个分布式共识协议有以下两个属性：

输入值的中止须经所有诚实节点来确定。
这个输入值必须由诚实节点来生成。

那么，所有的节点是如何对一个区块达成共识的呢？一个方法是，在一个时间段里，比如说每隔十分钟，每个节点都提议，自己的未被认可的交易成为已经达成共识的区块链后面的下一个区块，然后那些节点会执行一些共识协议，每个节点把自己提议的区块作为输入。

Propose-》Consensus 正当的交易可以等待下一次被打进区块的机会`

技术上面临的挑战

达成共识是一个难题：节点会宕机或者存在恶意节点
点对点网络通信不完美
信息传递的延迟

不可能性结论

拜占庭将军问题Byzantine Generals Problem

拜占庭是东罗马帝国的首都，它的军队分成多个师，每个师都由一个将军统领。这些将军通过信使进行交流，来达成一个共同作战方案，有些将军可能是叛徒，想故意破坏这个过程，这会造成那些忠诚的将军也无法达成一个统一的作战计划。解决这个难题的办法就是让那些忠诚的将军在这样的情况下达成统一作战方案，而避免那些叛徒对作战方案的误导。事实证明，如果叛徒数量超过1/3时，这个难题将无法克服，那些忠臣的计划终会被叛徒们破坏。

将军的总数为n，n里面背叛者的数量为t，则只要n > 3t就可以容错。

打破传统上的假设

比特币实际运行情况远比理论的研究结果好的多

比特币到底打破了经典模型里的哪些假设呢？

第一，比特币引进了奖励的理念第二，包含随机性；经过一段时间观点出现分歧的概率按指数下降

比特币到底打破了经典模型里的哪些假设呢？第一，比特币引进了奖励的理念，这对分布式共识协议来说是一个全新的理念，这也只有在比特币里才可能实现，因为比特币也是个货币，所以人们自然而然地会为了金钱奖励而变得诚实起来。所以，比特币并没有真正解决分布式共识问题，它只是在特定货币系统下解决了这个问题而已。第二，比特币体系包含随机性这个概念。在后面两节里我们将会看到，比特币的共识算法很大程度上依赖于随机性。此外，它也不再纠结于规定共识的起点与终点。相反，共识是通过一段较长的时间而达成的，在实际系统中，达成共识大约需要一个小时左右。但即使在一个小时以后，节点们也无法确定哪一个交易块应该进入总账本。但随着时间的流逝，我们对某一个块的认识与最终总体共识相吻合的概率将越来越大，观点出现分歧的概率按指数级下降。比特币在以上方面的不同，让它能够逾越传统理论关于分布式共识不可达成这一鸿沟。

2.3 使用区块链达成没有身份的共识

乱造节点就是所谓的 “女巫攻击”（sybil attack） 现象。女巫就是恶意黑客制造的不同节点，这些节点看起来像是对应不同的身份的人，其实是由一个人在幕后控制。另一个原因是化名制（pseudonymity），也是比特币想达到的一个目标，所以即使可以替所有节点建立唯一真实身份，我们也不想那样做。虽然比特币还是不能保证真正的匿名，一个用户用不同身份做的不同交易还是有办法被最终追踪到，但比特币的特性毕竟没有强迫大家用真实身份来加入。这是比特币的重要特性，也是比特币系统的核心理念。

隐性共识（inplicit consensus）

每一个回合：

一个随机节点被选中，然后这个节点可以提议这个链的下一个区块
其他节点可以通过接龙的方式，隐性的接受或者拒绝

这个算法的简化假设是，可以随意选择一个节点，这些节点都不会受到女巫攻击的影响。

新的交易被广播到所有节点上。
每个节点都将新的交易放进一个区块。
在每个回合，一个随机的节点可以广播它的区块。
其他节点可以选择接受这个区块，前提是如果区块里的交易都是正当的（有真的签名）。
节点们可以把以上区块的哈希值放进自己的区块里，以此来表示它们对那个新区块的认可。

比特币的攻击

窃取比特币—>伪造数字签名
拒绝服务攻击:如果Alice拒绝提供服务给Bob； Bob等到下一个诚实节点发起区块的时候，交易记录会被放进这个区块里
双重支付攻击:Alice给Bob or Alice转到另外一个地址一个交易就是一个数据结构：里面有Alice的数字签名，一个付给Bob的公钥（地址），一个哈希值（指向先前的一笔交易的输出）

双重支付

取决于最后哪一个区块被纳入长期的共识链

从道德角度看，分支截然不同；但从技术角度看，两笔交易都符合规范，形式上有效

另一个就被叫做孤块（orphan block）

零验证交易 (zero confirmation transaction)

诚实大多数原理

算力主要消耗在挖矿、区块链的生成、交易确认中
系统稳定性的缺省信任基础：算力掌握在大多数诚实的用户手中，出于自身利益的考虑，这些用户也愿意维护区块链系统
比特币51%攻击理论：攻击者要创造一条新链条，然后长度超越旧链条，覆盖旧链条。如果现在只有 1次确认，被覆盖的概率稍高，而到了6次确认，被覆盖的概率下降为接近"0"。

诚实链和攻击链的之间比赛的特征是一个二项分布的随机漫步。成功的事件是诚实的节点被一个数据块扩展，它的领先增加一个点，失败的事件是攻击者的链扩展一个数据块，差距减少一个点。

2.4 奖励机制与工作量证明

高明的激励设计

无法判断那笔交易是道义上合法；很难惩罚，因为节点没有身份

给予表现诚实的节点奖励：用比特币来奖励创造区块的节点

区块奖励

每产生210 000个区块（大约4年），区块奖励将被减半。最终一共是21 000 000个比特币。

$$ 50\times6\times24\times365\times4\times(1+0.5+0.25)=2100w $$

创建区块的节点可以在区块中一笔特别的交易：造币交易，指定这笔交易的接收地址

微妙和强大的设计 (Subtle but powerful trick)

奖励只有当区块最终被纳入长期共识链才会兑现
造币交易和其他每一笔交易一样，只有最终被纳入共识链，才会被其他节点接受

注意，这是新比特币被允许创造出来的唯一途径，没有任何其他新增币的机制。

比特币区块奖励迟早会发完（比如2140 年）系统还能继续运行下去吗？可以，因为还有交易费奖励

交易费奖励

随着区块奖励逐渐发完，交易费会变得日益重要：需要通过交易费(小费)来保障合理的服务质量

Challenges

如何随机选取一个节点？
都来争抢奖励，系统是否会变得不稳定？
攻击(Sybil Attack)：创建大量的女巫节点来尝试颠覆整个共识过程

挖矿与工作量证明

工作量证明 (Proof of Work)权益证明（proof of stake）把随机选取节点改为根据节点占有某种资源的比例来选取节点

计算能力—工作量证明系统(PoW)
某种币的拥有量—权益证明(PoS, Proof of Stake)

工作量证明: 算力的竞争比特币：哈希函数谜题：求解nonce

$$ H(nonceǁprev_{hash}ǁtxǁtxǁ…ǁtx) $$

如果一个节点发现一个nonce, 就可以提议创建下一个区块完全去中心化的方式：没有任何人决定谁可以提交下一区块

哈希谜题三大特性

难于计算

2014年底：产生一个区块：平均要做 1020 运算挖矿系统需要消耗大量能源

可参数化成本

成本是通过参数来进行调整的
大约每两个星期（ $ 24\times6\times14=2016 $ 个区块），目标区域的难度会调整一次
期望10分钟出一个区块有一个公式可以很好地描述这一点：任何一个矿工，比如爱丽丝，找到下一区块的概率，就相当于她控制的计算力占整个全球计算力的比例。这意味着，如果爱丽丝的挖矿设备的计算能力占全部计算能力的0.1%，那大概每产生1 000个区块，她就可以找到一个区块。

易于证实

基于哈希函数的单向性：挖矿很难，但容易验证

2.5 总结

如果：

挖矿奖励>挖矿成本

那么：矿工赚钱

条件是：

挖矿奖励=区块奖励+ 交易费

挖矿成本=硬件成本+ 运营成本（电费、空调费等）

系统的安全性不是来自于P2P网络的完美，而是来自于区块链和共识协议。

比特币系统深度使用了分布式共识： 拥有比特币就是其他节点对给定的一方拥有这些比特币的共识

启动加密货币

“自举过程”（bootstrapping）

区块链的安全性、挖矿生态系统的健康程度，货币的价值之间紧密相连

虚拟货币想要成功：初始化的自举 (bootstrapping)过程很关键

51%攻击

不能偷币，不能压制其他交易，不能改变区块奖励

51%攻击主要会摧毁大家对数字货币（比特币）的信心深度影响的是共识：不能改变数字签名的确认，交易信息的广播；仅可以局部‘指鹿为马’

Chapter 3 比特币的运行机制

3.1 比特币的交易

Blockchain----Public Ledger 公开账簿

First Impression: 记账方式

基于帐户的系统：与银行卡的帐户类似

问题？

如果要去确认一笔交易是否真实，就必须追溯每一个帐户的余额

增加一个数据字段，更新每次交易后的账户余额

但实际不可行：分布式网络，延时确认

解决

借鉴了Scroogecoin里面的记账方式
a transaction-based ledger close to Bitcoin

公钥、身份、PKI, CA, 证书

地址转换 (Change Addresses)–处理余额
有效验证 (Efficient Verification)–无需从头核查
资金合并–支持多输入输出
共同支付–多人数字签名

3.2 比特币的脚本

一个比特币交易分成三部分：元数据、一系列的输入和一系列的输出。

最常见的比特币交易：通过某人的签名获得他在前一笔交易中获得的资金

交易输出描述为：凭借哈希值为X的公钥，以及这个公钥所有者的签名，才能获得这笔资金

把交易的输入脚本(scriptSig)，和上一笔交易的输出脚本(scriptPubKey)串联起来。串联脚本必须被成功执行以后，才能获得资金。

比特币脚本语言

Forth: 简单的堆栈式编程语言(stack based)

每个指令只被执行一次，线性的，无法循环执行

非图灵完备

数据指令 pubKey

工作码指令 OP_***

OP_RETURN

销毁证明（proof of burn）脚本，用于销毁比特币（即防止资金被赎回）。

使用 OP_RETURN脚本来抛出错误；不论之前指令的运行结果是什么，OP_RETURN指令总会被执行，并相应抛出一个错误，脚本返回一个“错误”(false)值。

由于OP_RETURN以抛出错误的形式结束脚本，其后的所有指令都不会执行。利用这个特性，我们可以往脚本中植入任意信息，这些信息也将被存储在区块链中。假如你想通过署名或者盖时间戳的方式来证明你在某个时候知道某件事情，就可以发起一笔极小额的比特币交易，在脚本中加入上述信息，并使用销毁证明脚本将币销毁，这样就可以将信息永久地存储在区块链上。

可以随意地为比特币支付设定条件

Pay-to-Script-Hash P2SH

支付给脚本的哈希值

把比特币支付给某个脚本地址，脚本的哈希值是×××

取款的时候，提供上述哈希值对应的脚本，同时提供数据能通过脚本的验证

支付工作简单化：收款方只需告诉付款方一个哈希值即可

P2SH的输出脚本(ScriptPubKey)会变得很小，复杂的事情放在输入脚本(ScriptSig) 里面了

3.3 比特币脚本的应用

第三方支付交易（escrow transaction）

MultiSig （多重签名）

三个人中有两个人签名以后，资金才能被支取

Alice, Bob; Judy（第三方仲裁）

发生纠纷的时候

绿色地址（green addresses）

一个交易确认：延迟第三方银行：
Alice给Bob（传统）
Alice给Bank : （Alice: 支付Bob这些币，能代办吗？） (Bank: 从你的帐户扣钱，然后从(银行)绿色地址转帐给Bob)

不是Bitcoin技术系统的保障, 而是现实世界中银行的声誉保证：不会发生双重支付

高效小额支付（efficient micro-payments）

设想手机流量使用场景：按照分钟计费，但每分钟支付一次不现实
Solutions： MULTISIG

锁定时间（lock_time）

等待t时间之后才能把退款交易计入区块链如果过了t时间Bob还没有在最后一个交易上签名确认；Alice可以通过退款交易收回所有的Bitcoin

智能合约 (Smart Contract)

可以用技术手段来强制执行的合约；可以用脚本、矿工、和交易验证来实现第三方托管协议或者是小额支付；而不是中心化权威机构

比特币的区块

把大量交易组织起来放入一个区块，得到的哈希链会更短；可以提高验证区块链数据结构的效率

区块链把两个基于哈希值的数据结构结合起来：

区块的哈希链
树状结构把所有交易组织起来（Merkle Tree）

区块头部还包含了挖矿谜题 [1] 相关的信息。还记得，区块头部的哈希函数必须以一大堆零开头才有效，此外，区块头部还要包含一个矿工可以修改的“临时随机数”、一个时间戳和一个点数（点数用来表示找到这个区块的难度）。区块头部是挖矿过程中唯一哈希值化的，所以要验证一个区块的链，只要检查区块头部即可。在区块头部唯一的交易数据是交易树的树根——“mrkl_root”。

币基交易 (Coinbase Transaction)

它永远只有一个单一的输入与单一的输出。
这个交易并不消费之前交易输出的比特币，因此，没有指针指向“上一交易”。
这个输出值目前大约是25个币多一点点。这个输出值就是矿工的挖矿收入。它由两部分组成：一部分是奖励的25个比特币（奖励在每生产210 000个区块——大概4年——后减半），另一部分是所有交易的交易手续费。
还有一个特别的地方就是“币基”参数，矿工可以放任何值进去。

创世块是比特币区块链的原始块。也称为块0，它是所有其他块构建的基础。没有创世块，就不能创建新块，也就没有区块链。创世块来自比特币的创始人中本聪（Satoshi Nakamoto）。他是用微软的visual studio和c++编写的，他从2009年1月3日开始开采，持续了六天；中本聪正在彻底测试创世块，以确保它是完美的，因为它将永远被硬连接到系统中。

3.5 比特币网络

所有的节点都是平等的

发起一个交易：泛洪Flooding算法 (八卦gossip协议)

核验新交易信息

对每个前序交易的输出运行核验脚本
校验是否有双重支付
检查这笔交易信息是不是已经被本节点接收过
节点只会接收和传递在白名单上的标准脚本

竞态条件（race condition）

哪一个交易被纳入区块链产生分歧(Race condition)

每个节点默认保留最早接收到的交易（or Replace-by-fee费用替代策略）

自从2013年，矿工的缺省行为变成了“费用替代策略”, 即节点在遇到有冲突的交易时，会把交易手续费更高的交易放进自己的交易池，把手续费更低的替换出去。站在矿工的角度，由于收益更高，因此也是理性的选择——至少在短期看是这样。但是这种费用替代策略却使多重支付攻击变得更容易了。因此，费用替代策略受到了不少争议，这些争议一方面从技术层面讨论在费用替代策略中是否可以真正阻止多重支付；另一方面从哲学层面讨论比特币是不是应该要尽可能支持零验证，或直接放弃费用替代策略。我们这里就不再赘述这些讨论了很久的争议了，但最近比特币核心代码倒选用了“有选择权的”（opt-in）费用替代策略的做法，也就是交易可以标记自己是否适用费用替代策略。

如果两个矛盾的交易或者区块在不同地方发起，向整个网络广播；那么节点接收那个交易取决于它在网络的位置

区块的传播与交易传播类似

竞态条件的限制：哪个区块被纳入长期共识链取决于其他节点选择在哪个区块上扩展区块链

核验一个区块：

确认区块头部；
确定哈希值在给定范围；
确认区块里面的每个交易；
最长的一条区块链进行扩展

存储空间需求

全节点：需要把完整的共识区块链存储下来

2022年10月16日 BTC 链为432 GB

轻量节点(nightweight nodes) 也叫简单付款验证(Simple Payment Verification)

简称SPV客户端只存储他们所关心的，需要进行核验的部分交易

SPV节点只验证相关交易；依赖全节点去验证网络上的其他所有交易

只需要几十MB数据(VS 几十GB or More)

3.6 限制与优化

比特币的总体数量与记账奖励社区内基本达成共识：不应该改变

交易性能： 7笔/秒 (Calculation)

每个区块大小限定在1MB，每个交易大约是 250字节，所以每块最多容纳4 000个交易。平均每隔10分钟，有一个矿工获得记账权利，所以每秒钟只能处理7个交易

Limitation: Visa 2000 笔/秒

Weakness of Crypto Suite

ECDSA & Hash function

担心在一生中，这些算法可能会被攻破

Reference: ABCMint 抗量子攻击

修订协议

修订协议：无法假定所有节点都会更新版

硬分叉

引入新的特性，使得前一版本的协议失效

软分叉

加入新特性，让现有的核验规则更加严格。老的节点依然会接受所有的区块，而新的节点会拒绝

向下兼容–P2SH

MULTISIG的Bug: 推送给堆栈一个无用的值。但修复这个缺陷，会产生硬分叉

如何改变区块大小：难以达成共识

提高（区块链系统）交易处理能力

第4章如何储存和使用比特币

4.1 简单的本地存储

存储比特币其实就是如何保存和管理比特币私钥

可获取性
安全性
便利性

比特币钱包软件

管理比特币和私钥信息并让你方便使用的一个应用软件

编码解码（encoding keys）：Base58编码和二维码

Base58编码
Base64是一种基于64个可打印字符来表示二进制数据的表示方法
包含58个字符的字符集：去掉几个比较容易混淆的字母
相比Base64，Base58不使用数字"0"，字母大写"O"，字母大写"I"，和字母小写"l" ，以及"+“和”/"符号

设计Base58主要的目的：

避免混淆。在某些字体下，数字0和字母大写 O，以及字母大写I和字母小写l会非常相似。
不使用"+“和”/"的原因是非字母或数字的字符串作为帐号较难被接受。
没有标点符号，通常不会被从中间分。
大部分的软件支持双击选择整个字符串。

QR码：帐户交易处理更方便

虚荣地址 (Vanity Address)

How to Generate this type of Address? 只能尝试

How to Speedup?
$$ g^{𝑥+1} = g ∗ g^x $$ 椭圆曲线点乘优

热存储和冷存储

热存储

存放在个人电脑里（像把钱放在钱包里）方便但不安全

冷存储

不联入互联网，封存起来（像保险箱），安全性高但不方便

分层确定性钱包（hierarchical deterministic wallet）

让冷存储端制造很多的地址数量，通过一个短暂的一次性的交换，热存储端就可知晓所有地址 Crypto technique（同步）

对每个i而言，第i个地址和第i个私钥相匹配

一长串配对的公私钥
注：冷储存端生成和保存私钥生成信息和地址生成信息，然后将地址生成信息一次性转给热储存端。当热储存端要给冷储存端转账时，就按次序生成新的地址。冷储存端上线后，也会按顺序生成地址，然后查收相应地址收到的款项，直到某一地址没有收款位置。如果冷储存端需要向热储存端转账，它就会按顺序生成私钥序列。

分层确定性钱包：技术方案

一个ECDSA私钥是一个随机数x，其对应的公钥是 $ g^x $ 。为了生成分层确定性密钥，我们需要另外两个随机数k和y。

私钥生成信息:k,x,y
第i个私钥:x=y+H(k‖i)
地址生成信息:k, $ g^y $
第i个公钥: $ g^{xi}=g H(k‖i) ·g^y $
第i个地址: $ H(g{xi}) $

分层确定性钱包：安全性分析

𝑔𝑔𝑦𝑦 can’t deduce 𝑦𝑦, and also 𝑥𝑥𝑖𝑖 (𝑖𝑖-th private key)
Because of DLP (Discrete Logarithm Problem)

大脑钱包（brain walle）

这种方式下，你通过一个密码就可以支取比特币。

大脑钱包的主要原理是用一个可预测的算法把一个口令变成一对公钥/私钥。

有一种简便的方法可以生成口令：从最常用的10 000英语词汇中，随机选择6个词，从而生成大致80位长度的字节 $ [6×log2 (10 000)大致等于80] $ 。很多人发现这个方法比随机取字母容易记忆，因为这种方法生成的口令通常是下面这样子的： worn till alloy focusing okay reducing earth dutch fake tired dot occasions

让攻击者尝试密钥破解的速度变慢

Key Stretching 密钥延展重复计算SHA256 ( $ 2^{20 } $ Trials)
$$ SHA256^{2{20}} (Password) == OpenValue $$

纸钱包

把密钥印在纸上，然后把纸锁在保险箱里面

防损硬件（tamper-resistant device）

用来保存密钥或者用来生成密钥；
此类设备不会泄漏密钥或者输出密钥；
一旦设备丢失或者被盗，马上能察觉。

4.3 密钥分存和密钥共享

把密钥保存在一个地方：一损俱损

分散风险：密钥分存

密钥被分成N个片段，如果获得其中的K个片段就可以把原密钥重新还原。如果片段数目少于K, 不能知道密钥的任何信息。

不能直接分割密钥！否则每一个片段会透露密钥的部分信息，降低了搜索复杂度

N=2, K=2

Solutions?

R and R XOR S

Extension to N=K case

举个例子，我们设定N=2，K=2，意味着我们把想要加密的密钥（原密钥）转换成两个子密钥，只有同时获得这两个子密钥才能拼出原密钥。我们把原密钥称为S，S是一个很大的数字（比如128位）。然后，我们可以随机产生另一个128位的数字R，让R作为其中的一个子密钥，那么另外一个子密钥就是S⊕R（⊕代表逻辑算符互斥，exclusive OR，或缩写成XOR，也叫异或），我们把S⊕R称为“密文”。然后，我们把子密钥R和密文 S⊕R保存在两个不同的地方。单独根据子密钥R或密文都无法知晓原来密钥的任何信息，但如果我们同时得到R和S⊕R，我们可以通过异或逻辑运算得到原来的密钥。 N和K相等时，我们总是可以这样做：对于之前的K-1个子密钥，我们可以生成N-1不同的随机数，最后一个子密钥就是原密钥与所有其他N-1个子密钥的异或。但如果N大于K 的话，这个技巧就行不通了。我们需要借助其他代数方法。

注：S代表原密钥，被编码成一个大的整数，图中斜线的斜率随机。斜线上的点（主要是它们的Y坐标 S+R，S+2R，…）代表子密钥。连接任何两个点，都可以得到S $ [两点连线，延长，与Y轴的交点就是S（黑点）] $ 。若是只有一个点，又无法确定斜率（斜率随机），就无法得到S。

拉格朗日公式表明，如果要回归一条自由度为k-1的曲线，需要获得至少K 个点。

如果我们将原密钥转换成N个子密钥，除非黑客获得了K-1个子密钥，否则原密钥就是安全的，换个说法，我们最多可以承受N-K个子密钥被泄露。

门限密码（threshold cryptography）

两个子密钥分别保存在个人电脑和手机上；

电脑生成一个签名片段，发送到你手机上；

手机利用它的子密钥完成整个签名。

多重签名（multisignatures）

比如：一个交易需要5个人至少3个人签名才能完成

多重签名可以妥善的管理在冷存储端的数字资产；需要多人参与才能实现

4.4 在线钱包和交易所

在线钱包

在线钱包可以在各种场合应用，但真正的钱包信息存储在云端

Blockchain.info

网站存储着你的密钥，至少能够接触到你的密钥

安全前提：网站服务提供商可以信任

数字货币（比特币）交易所

银行的功能：面向个人存取款

银行会把钱用于投资；储备金

数字货币交易所在交易前后，数字货币并没有真正在区块链中移动，只是你和银行的合约变化了

优缺点

优点：把数字货币（比特币）和法币经济结合，实现自由转换

风险：

挤兑
庞式骗局
黑客入侵

监管

银行监管

政府要求银行有一个最低准备金要求：需要3%-10%的现金应对突发提款需求

政府对银行进行监管，必要时为银行或者储蓄者提供保护

准备金证明

向储户证明留存了一部分储备金，消除投资人的担心

如何证明你(交易所)有 $ 10^6 $ 的数字准备金？

发起一笔转账交易，收款方为本人；利用私钥签名

负债证明（proof of liabilities）

我们需要为每个节点添加一个字段（下文简称为存款金额字段），这个字段显示其最近的两个子节点的存款金额之和。

注：交易所构建这样一棵梅克尔树：每个储户对应一个叶节点，每个叶节点的存款金额字段保存储户存款金额。每个节点的存款金额字段等于与其最相近的两个子节点的存款金额之和，这样，根节点的存款金额字段就代表着存款总规模。每个储户都可以要求交易所证明该储户在梅克尔树上，并且可以核实根节点所显示的总存款规模。

每个客户可以向交易所索要存款证明

子树根节点的哈希指针和存款金额字段，与交易所广播的值一致。
从子树的根节点遍历到叶节点，每个节点对应的哈希值确实是其所指向的子节点的哈希值。
每个叶节点对应的客户账号信息（客户名、账号和存款金额）都是正确无误的。
每个节点的存款金额字段正好等于与其最相近的子节点的存款金额之和。

交易所证明了其至少留存了X数字货币

之后证明其吸收的存款规模至多是Y数字货币

可让所有人能独立审计验证: 准备金下限: X/Y

4.5 支付服务

如何接受数字货币付款

客户可以用数字货币(比如比特币)购物
商户如期收到法定货币(比如美元)
支付服务商获得手续费

支付服务商承担了所有风险

安全风险：好的安全措施来管理数字货币
汇率风险: (比如数字货币与法定货币之间兑换的汇率波动)

另外一方面：如果支付商解决了这些问题，可从每笔交易中收取可观的利润

4.6 交易费

交易费=交易的输入金额-交易的输出金额

比特币网络中，传播你的交易信息需要成本

比如区块中打进一笔你的交易，区块就会变大，也会花费更多的时间传输到其他节点

确认你的交易需要花费代价：交易费用来补偿矿工处理交易付出的代价

通常而言，如果支付了更多的交易费，那么交易会被更快，更可靠的传播和记录

默认的交易费政策

现在大部分矿工所默认的交易费是这样计算的：首先，如果交易满足以下三个条件，那就不需要支付交易费：

交易小于1 000个字节。
所有输出为0.01BTC或更大。
优先权足够高。(所有输入的账龄的总和×输入金额）/交易规模

，当前默认标准是：每1 000个字节需要支付 0.0001BTC，在2015年，这相当于每1 000个字节花费1美分的交易费，一笔交易通常包括：输入通常是148个字节，每个输出通常是34个字节，其他信息10个字节。如果一笔交易有两个输入和两个输出，那么这笔交易的大小是400个字节。

通常需要支付一笔标准的交易费用；大多数矿工强制要求必须包含交易费用

4.7 货币兑换市场

比特币市场中的公允价格是由供给和需求决定的

比特币的需求包括将比特币作为支付中介，以及作为投资需求

一个简单的市场行为模型

根据供需平衡来决定比特币价格：假设P 是比特币对美元的价格

供应侧：D秒内，市场内有S个比特币可以进行交易

需求侧：总共的支付交易规模是T美元

𝑆/𝐷 = 𝑇/𝑃 意味着 P ∝ T

第5章比特币挖矿（bitcoin mining）

5.1 比特币矿工的任务

为了挖矿，加入比特币网络，完成任务

监听交易广播；
维护区块链网络和监听新的区块；
组装一个备选区块；
找到一个有效的随机数；
希望你的区块被全网接受；
利润

第一类任务: 验证交易和区块

比特币网络赖以生存和运转的基础

第二类任务：竞争出块并获得奖励

鼓励矿工去完成第一类任务而设置

寻找有效区块

矿工首先从个人交易池中选出一系列有效的交易->Merkel Tree

矿工：挖矿通常使nonce 从0开始，每次增加1，直到使得区块有效(Consecutive 0s in the front)

nonce : 32 bit

如何满足挖矿难度? (比如72个头部连续的0)

当改变币基里的随机数后，整个梅克尔树上交易的哈希值都会改变（见图5.2），因为币基值的改变会向上传递，所以改变币基的随机数值比改变头部随机数值的代价要大很多。正因为如此，矿工大部分时间只改动头部的随机数，只有在遍历头部2 32 个随机数值且还没有找到一个有效区块时，才改动币基的随机数

如果遍历nonce的取值空间还没有找到一个有效区块时，改动coinbase中的随机数

正确的临时随机数组合：头部随机数 (nonce)+币基随机数(coinbase)

立即宣布：希望得到出块奖励

求解谜题不同 :每个矿工会把数目不同、次序不同的交易放进区块；币基交易里，接收地址通常也不一样
区块难度相同

决定难度

每挖出2 016个区块，挖矿难度会改变一次，这个周期大约是两个星期。难度的改变是根据上2 016个区块的挖矿效率来决定的。用下列公式来表达：
$$ 下一个难度=\frac{上一个难度\times2016\times10分钟}{产生上2016个区块所花费的时间} $$

5.2 挖矿所需硬件

SHA-256的设计来自美国国家安全局（NSA）

CPU挖矿

CPU挖矿个人电脑： 20MH/s 2015年难度水平： 267 大约要几十万年找到一个区块！

GPU

GPU挖矿

图形处理器(GPU) 适合做数据密集型的计算；适合并行

CPU 驱动多个GPU

2015年： 200MH/S
100块显卡集成在一起进行运算

非常耗电

大约要几百年才能找到一个有效区块！

现场可编程门阵列(Field-Programmable Gate Array，简称FPGA)

精心设计： 1GH/s

100块 FPGA 板

100年才能找到一个有效区块

故障和报错；性能功耗比方面不理想

专用集成电路技术挖矿 (ASIC)

应用需求驱动

集成电路芯片：需要专业的知识，设计的芯片寿命十分短暂

运营成本很高(电力、冷却)

如今：专业挖矿的天下

大型专业挖矿中心：专门运营

采购打过折的功效更高的ASIC矿机

建立挖矿中心的三个重要因素：

气候、电费、网络接入速度

格鲁吉亚、冰岛；中国内蒙古

未来

ASIC和专业挖矿中心违反了当时设计的初衷：完全去中心化的系统

另类币的挖矿发展轨迹：也许谜题会变，但是循环周期类似 CPU->GPU->FPGA->ASIC->…

5.3 能源消耗和生态环保

每进行一个不可逆的bit flip（数位）运算就会消耗能源

比特币的挖矿过程必定消耗能源

内涵能源（生产矿机）
电能（挖矿）
冷却（防止矿机出故障）

能耗预估

自上而下

2015
收入用来支付电能

每秒所有的11美元收入购买电费，可以购买367 百万焦耳

MW 数量级（几百万瓦特（megawatt，简称MW））

自下而上

最好的矿机：1W—3G/s

全网算力是350PH/s ----》每秒中全网计算消耗 117 MW

总而言之，比特币挖矿当时（2015）是 MW的数量级

比特币挖矿—浪费能源？

比特币这种“浪费”能源的形式经常被人诟病，因为SHA-256的运算没有其他任何用处。但是我们必须认识到任何一种支付系统都需要能源和电力的消耗。就拿传统的货币来说，纸币印刷、ATM机器的运行、硬币分类机器、点钞机、支付服务系统以及运送现钞和金条的武装押运车，无一不在消耗各种能源。你也可以一样说这些能源的消耗除了维护整个货币体系之外，也没有任何其他用处。所以，如果我们认可比特币作为一个有用的货币体系，那么支持比特币体系的能耗就不能认为是浪费。

能源的循环使用

能源的循环使用—数据火炉(Data Furnace)

将电力转换成现金

5.4 矿池

单个矿工的挖矿风险

发现区块的数目可以用帕松分布(Poisson distribution)来逼近

Binomial distribution can be approximated by the Poisson distribution

比如你用6000 US Dollars买了一台矿机根据矿机性能，平均每14个月找到一个区块𝜆= 6/7

对于一个小矿工而言，挖矿就是赌博游戏

矿池：比特币矿工互相之间的保险

一组矿工可以形成一个矿池共同挖矿，并指定一个币基接收人——矿池管理员

矿工通过输出挖矿工分来证明他的工作量

比如目标值前面有67个0；一个合格的工分需要40-50个0

矿池管理员根据大家的工作量按照比例分配奖励

分红方案

工分分红

矿工发送工分，管理员马上支付奖励

管理员承担了所有风险

按实际比例分红

每次找到一个有效区块，区块奖励按照矿工工作量按比例分配；

降低管理员风险

矿池跳换

投机矿工：挖矿早期(上一个区块刚刚被发现)加入按实际比例分红的矿池；挖矿后期跳到一个按工分分红的矿池。

研究问题：如何设计一个矿池方案，避免矿工的投机？

根据最近若干个工分提交的结果才分配

51%矿池

实际上的算法可能集中在几个大的机构手中，即使‘洗算力’

优缺点

优点

小矿工容易参与，也有一定的收益；
网络管理员负责组装区块，网络更新变得更加容易

缺点

（算力）中心化管理；
整个网络中进行校验交易的全节点数目在下降

5.5 挖矿的激励和策略

我们假设一个运行非默认策略的矿工掌控一定的比特币网络挖掘市场份额，设为α。

在挑选一个区块开挖之前，矿工做策略上的选择：

需要包括哪些交易？ （优先选择交易费高的交易）
对哪一个区块进行挖矿运算？ （优先选择最长的区块链上继续下挖）
在同一高度的多个区块中做选择？ （优先选择被监听到的那一个区块）
什么时候宣布新的区块？ （默认做法是立刻宣布）

分叉攻击(forking attack)

双花：重复支付

一个恶意的矿工给受害者鲍勃发送了一些比特币来购买其服务和货品。然后这个矿工进行了一个分叉攻击，创建了一个包含冲突交易的更长的分叉，在新的共识链中给鲍勃的支付就变成了无效的交易。

51%是必要的吗？

51%会影响大家对‘去中心化’的信任

实际上，稍低算力也可以发起攻击，因为有网络拥塞、延迟等因素

中心化的攻击者能够快速通信从而节省一些算力

贿赂攻击

有别于直接获得算力，攻击者贿赂已经具有算力的人，以分叉出一条最长链

临时保留区块攻击(自私挖矿)（selfish mining）

这里面的关键是你需要运气好到连续发现两个区块

黑名单与惩罚分叉攻击

宣布拒绝在包含来自该地址的交易的区块链上工作；（类似美国制裁伊朗）

羽量级分叉

如果胆敢把来自地址X的交易加入自己的区块，便有 𝛼𝛼2的可能会丧失自己已经发现的区块

其他

目前，区块奖励在矿工收入里面占比超过99%；

但是区块奖励每4年减半，最终出块奖励会变得很低；

从长期来看，比特币奖励将从固定的挖矿奖励为主，转变为交易费为主

第6章比特币和匿名性

6.1 匿名的基础知识

匿名的定义

匿名（Anonymity）：无关联性的化名比特币系统中，使用者不需要使用真实的姓名

需要使用公钥哈希值作为交易标识

一个用户可以随机创建出任意多个比特币地址

比特币具有化名性，但是不能达到绝对隐私

使用数字货币（如比特币）支付时，在真实的物理世界里容易暴露身份，进而关联到地址，以及其他所有的交易

无关联性

同一个用户的不同地址应该不易关联。
同一个用户的不同交易应该不易关联。
一个交易的交易双方应该不易关联。

区块链货币中，所有交易都记录在一个公开账本上，也就是说相关交易信息可以永久追踪

希望能够达到传统银行能够达到的隐私保护级别，降低公共区块链带来的信息暴露风险

超越传统银行给我们的隐私保护级别

匿名化和去中心化

Chaum的电子现金系统，采用了盲签名技术，但还需一个中央权威机构

Zerocoin， Zerocash：匿名化&去中心化的加密数字货币系统

6.2 如何对比特币去匿名化

一个地址簇 (clustering of addresses)。一般来说，如果一个新地址的输出，和该地址簇中的任何一个已知地址被一起花费，那么这个新的地址也将会被加到该地址簇中去。

交易图谱分析（transaction graph analysis）

网络层的去匿名化

“第一个通知交易的节点很有可能就是交易源头”。当有多个节点配合并且对同一个交易源头进行识别的时候，这种方法的实际效果会更加明显。

6.3 混币

混币准则

6.4 分布式混币（Decentralized Mixing）

采用一种用户之间的点对点模式实现混币交易的协议

合币（Coinjoin）

高风险交易流（high-level flows）

为了完成一笔支付，用户通常会组合所拥有的数字货币，这样便有足够数额可以支付到单一接收地址

规避：所有输入地址被关联在一起

合并规避（merge avoidance）

这种合并规避协议通过允许接收方提供多个输出地址的方式（尽可能多的），使得无关联性成为可能。

6.5 零币和零钞

基础币（Basecoin）是一种类似于比特币的另类币，而零币是这种数字货币的一种延伸，其所提供的匿名性的核心特点在于，你可以将基础币和零币进行来回转换，并且当你这么做的时候，就打破了旧的基础币和新的基础币之间的关联。

零知识证明(Zero Knowledge Proof)

证明者(Prover)要让验证者(Verifier)相信自己拥有某种知识，但又不泄漏它

很多场景中有着广泛的应用，比如金融交易中，保护支付方、接收方、交易金额的隐私

Example 1. A Key to a Door

Example 2. Coloring Problem

交互式零知识证明的一般模型

例如，假设你已经做了很多工作解决了一个哈希谜题，并且你想要向其他人证明你做到了。换而言之，你想要证明“我做到了”这个声明。 I know x such that H(xǁ〈other known inputs〉)<〈target〉当然，你可以展示上述公式里的x值来证明你做到了，但是零知识验证可以让你向别人证明你做到了这一点，同时不需要透露x的值，即便在看过你的证明之后。你也可以证明一个如“我知道一个x值，而公式H（x）的结果属于下面这一个集合 {…}”这样的声明。

密码学承诺好比把一个序列号封装到一个信封里。
为了将一个零币置于区块链中，需要创建一个铸币交易，其输出地址是零币序列号的一个密码承诺，而铸币交易的输入则是一个基础币，这个基础币也会在创建零币的过程被消耗掉，整个交易过程并不需要公示这个序列号。

Zerocoin：匿名性

铸币交易或者花费交易中没有展示过r
无人知道序列号对应哪一个具体的零币

零钞

零钞使用的是一种被称为zk-SNARKS的密码学技术(Zeroknowledge Succinct Non-interactive Arguments of Knowledge)

DAP (Decentralized Anonymous Payment Scheme )

Hiding user identities, transaction amounts, and account balances from public view

第10章另类币和加密货币生态系统

另类币的介绍

Limitation of Bitcoin (High Latency, Low TPS)

可以对脚本语言进行扩充以增加交易种类和安全属性

采用与bitcoin不同的挖矿方式以及共识算法

困难的地方在于如何让别人逐步接受你的货币，吸引开发者、矿工、投资者、商家、客户、支付服务商加入货币的生态圈

吸引矿工特别重要：没有足够的算力支撑，双重支付和复制修改代码就容易发生

让一个社区的人相信该另类币的价值

另类币

莱特币（Litecoin）是一种点对点的电子加密货币，也是MIT/X11 许可下的一个开源软件项目。莱特币受到了比特币（BTC）的启发，并且在技术上具有相同的实现原理，莱特币的创造和转让基于一种开源的加密协议，不受到任何中央机构的管理。莱特币旨在改进比特币，与其相比，莱特币具有三种显著差异。第一，莱特币网路大约每2.5分钟（而不是10分钟）就可以处理一个块，因此可以提供更快的交易确认。第二，莱特币网路预期产出8400万个莱特币，是比特币网路发行货币量的四倍之多。第三，莱特币在其工作量证明算法中使用了由Colin Percival首次提出的scrypt加密算法，这使得相比于比特币，在普通计算机上进行莱特币挖掘更为容易（在ASIC矿机诞生之前）

作为一个开放的区块链网络，Conflux 期望通过去中心化理念及一系列技术创新为未来商业赋能，实现资产和数据互通互信，创建一个更具价值的网络世界。 Conflux 致力于利用自主研发的树图高性能共识算法，构建一个无需准入并拥有极高包容性及延展性的区块链网络。

10.5 不可分割的交叉链互换

Atomic Cross-chain Swap (跨链交易)

如果爱丽丝想卖掉a个另类币给鲍勃，换得鲍勃的b个比特币，他们可以把这项交易做成是单一且无法分割的形式吗？

如果其中一个人，假设是爱丽丝，先执行交易，有什么办法可以阻止鲍勃不遵守承诺呢？

有个聪明的办法可以做到，这用到了密码学的承诺和锁定时间存储

以太坊和智能合约

编程语言（Solidity）图灵完备

支持通用的计算功能

不再局限于数字货币的应用场景以太坊：一个开源的有智能合约功能的公共区块链平台，Blockchain 2.0

智能合约（smart contract）：存储在区块链上的程序，由各节点运行，需要运行程序的人支付手续费给节点的矿工或权益人。
代币（tokens）：智能合约可以创造代币供分布式应用程序使用。分布式应用程序的代币化让用户、投资者以及管理者的利益一致。代币也可以用来进行首次代币发行。
权益证明（proof-of-stake）：相较于工作量证明更有效率，可节省大量在挖矿时浪费的电脑资源，并避免特殊应用集成电路造成网络中心化。
燃料（gas）：由交易手续费的概念扩展，在运行各种运算时需计算燃料消耗量，并缴交燃料费，包括发送以太币或者其他代币也被视为一种运算动作。
分布式应用程序：以太坊上的分布式应用程序不会停机，也不能被关掉。
叔块（uncle block）：将因为速度较慢而未及时被收入母链的较短区块链并入，以提升交易量。使用的是有向无环图的相关技术。

以太坊最重要的技术贡献就是智能合约。智能合约是存储在区块链上的程序

交易数据结构

以太坊中存在三种共识算法：

Ethash ：是以太坊 1.0 的工作量证明算法
PoA：权威证明算法，服务于测试网、私有链、联盟链等。
PoS：将在以太坊2.0中需要实现的一套股权证明算法

Solidity
一种静态类型的编程语言，用于开发在 EVM (the runtime environment for smart contracts in Ethereum)上运行的智能合约。 Solidity被编译为可在EVM上运行的字节码

开发平台 Remix，Solidity官方IDE Microsoft Visual Studio

作业

作业1

问题 1：多元 Merkle 树。Alice 可以使用二叉 Merkle 树来提交的一组元素 S = （T1, …, Tn），之后她可以向 Bob 证明 S [i] = Ti，每个证明最多包含⌈log2 n⌉ 个哈希值。对 S 的承诺是单一的哈希值。在这个问题中，请你解释如何使用 k 叉树来做同样的事情，也就是说，每个非叶节点最多可以有 k 个子节点。每个非叶节点的哈希值是其所有子结点的值的哈希值。 a.假设 S ＝（T1,…，T9）。解释 Alice 如何使用三叉 Merkle 树计算对 S 的承诺（即 k = 3）。Alice 如何向 Bob 证明 T4 在 S 中，即哪些值被包含在证明中？ b.假设 S 包含 n 个元素。S [i] = Ti的证明长度是多大？用 n 和 k 的函数表示。 c.对于较大的 n 值，如果我们想最小化证明的大小，最好使用二叉 Merkle 树还是三叉 Merkle 树？为什么？

答案

(2)采用 Merkle tree 的方法，可以知道成员证明需要 Sibling 的集合，因此假设是 k 叉树，那么所需要的 Hash 数目是 $ 1 + (𝑘 − 1)⌈log_{k}(n)⌉ $ ; （包括根节点）

(3) n 在渐进意义下，成员证明大小正比于 (k-1)/log(k)。可以知道 1/log(2)< 2/log(3) (也就是 log(3)<2log(2))，因此还是二叉 Merkle 树更好。