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

法定货币，类似央行的机构控制货币供给+实体货币上加防伪标识。但是仍然可以伪造。
加密数字货币需采取安全措施以及防止混淆。
二者不同在于：后者安全规则需要完全通过技术手段，前者则是依赖于中央机构。
本章主要介绍密码学中的哈希算法（Hash）和数字签名（digital signature)技术。两者对构建一个加密数字货币系统非常关键。后面章节介绍：零知识验证。

1.1 密码学哈希函数

哈希函数
哈希函数是一个数学函数，有以下三个特性：
①输入可为任意大小的字符串
②产生固定大小的输出。本章假设输出大小为256位。
③能进行有效计算即对于特定的输入字符串，在合理时间内，可以计算出哈希函数的输出。对应n位的字符串，其哈希值计算的复杂度为O(n)。
哈希表
基于哈希函数，创建的数据结构。
由于专注加密的哈希函数，要使哈希函数达到密码安全，需满足：
①碰撞阻力 collision-resistance
②隐秘性 hiding
③谜题友好 puzzle-friendliness

特性1 碰撞阻力

碰撞☞：对于两个不同的输入，产生相同的输出。
对于哈希函数H(·)，没人能找到碰撞（不表示不存在碰撞），则称该函数具有碰撞阻力。
x,y是两个不同输入，但有H(x) = H(y)，说明这个函数是哈希碰撞的
注：通过计数论证可证明碰撞的确存在。哈希函数输入空间无限（包含所有长度的任意字符串），输出空间有限（只包含特定固定长度的字符串），因此一定会有输入字符串映射到相同的输出字符串。实际上根据歌巢原理可知必然会有大量可能的输入被映射到任意特定输出。对于加密的哈希函数，有些方法是能保证找到碰撞的。
输出256位大小的哈希函数，选择2^256 + 1个不同数值，因为输入大于输出，必将产生碰撞。
生日悖论是仅仅通过检验可能输出数量的平方根次数，便能答题找到碰撞。
优点：这个碰撞检测算法对于每个哈希函数都有效。
缺点：计算需要花费很长很长时间。

但是：我们已经证明，世界上没有哈希函数具有防碰撞特性。我们实践中所依赖的加密的哈希函数仅仅是暂未成功找到碰撞的函数，暂且选择相信这些具有哈希阻力。比如MD5哈希函数找到了碰撞，已经逐渐被淘汰。
应用：信息摘要部分
基于前提：哈希函数H具有碰撞阻力，x,y是两个不同输入，则可以假设输出不同。
该论证可以将哈希输出作为信息摘要。
例子是：爱丽丝上传了很大的文件，如何能在之后下载确定她下载的文件和她上传的文件相同。
ⅰ整个文件本地存储，再对比。麻烦且上传无意义。
ⅱ无碰撞哈希函数解决这个问题，爱丽丝只需要记住原文件哈希值，下载文件后，计算下载文件的哈希值与之相比。相同，则是。
此处：哈希函数对于一个信息生成固定长度的摘要或生成了总结。

特性2 隐秘性

隐秘性保证：若只知哈希函数的y=H(x)，没有可行的办法算出输入值x。
为实现隐秘性：x的取值需来自一个非常广泛的集合。避免被反解出。
隐秘性哈希函数H具有隐秘性。如果：当其输入r选自一个高阶最小熵的概率分布，在给定H（r||x）条件下来确定x是不可行的。（双竖线||为连接符号，代表把一系列事件、事情联系起来）
信息论中最小熵是用户测试结果可预见性的手段。高阶最小熵比较直观的描述了分布的分散程度。
应用：承诺
想做的事情称为承诺。
该处承诺是个数字化过程：选定一个数字，装进信封，放到人人可见桌上，这样则说明你对信封里数字做出了承诺，打开信封前对他人是秘密，打开之后，来展示承诺数值。

承诺协议：一个承诺协议方案由两个算法构成。
①承诺函数将信息和一个临时随机数作为输入，输出就是一个承诺。
②验证函数将某个承诺输出、临时随机数及信息作为输入。对比。
需要由两个安全特性：隐秘性和约束性。
此处书中第10页有具体介绍。
如何执行承诺方案，通过加密的哈希函数：生成一个256位的临时随机数等。详情参见书。

特性3 谜题友好

谜题友好：如果对于任意n位输出值y,假定k选自高阶最小熵分布，如果无法找到一个可行的方法，在2^n小很多时间内找到x，保证H（k||x)=y成立，那么我们称哈希函数H为谜题友好。
应用：搜索谜题
搜索谜题构成：
一个哈希函数H。
从高阶最小熵分布选出的一个取值，id（称为谜题ID）
目标集合Y。
该谜题的解决方法为一个解，x，满足以下公式：
H(id||x) ∈ Y

安全哈希算法
安全哈希算法Secure Hash Algorithm 256 简称 SHA-256
SHA-256主要被比特币世界采用。
要求哈希函数可以任意长度输入，只要我们建立一个用于固定长度输入的哈希函数，通过一般方法，可以将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数。该过程称为MD变换。SHA-256是采用这种变换方法的常用哈希函数之一。
压缩函数：通用术语中，这种基础型，可用于固定长度，具备碰撞阻力的哈希函数被称为压缩函数。
经验证：如果基本压缩函数具有碰撞阻力的特性，那通过转换而生成的哈希函数也具有碰撞阻力。
MD变换
压缩函数带入长度为m的输入值，产生长度短一些为n的输出值。哈希函数的输入（可为任意大小）被分为长度为m-n的区块。
MD转换过程：将每个区块与之前区块的输出一起带入压缩函数，输出长度变为(m-n)+n=m=压缩函数的输入长度。对于第一个区块而言，需选取一个初始向量。每次调用哈希函数，这个数字都会被再次使用，实践中可直接在标准文档中找到它。最后一个区块的输出就是返回的结果。
SHA-256利用压缩函数，把768位的输入压缩成一个256位的输出，每一个区块的大小是256位。

SHA-256工作原理

未完待续。2018.5.21 22：50
接着。2018.5.22 7：17
哈希函数建模
事实证明，要确定一系列哈希函数特性以全面达成可证安全极度困难，本书中主要是选出在比特币和其他加密数字货币中，对哈希函数使用方式很重要的三个特性。即使在这个范围内，并不是所有这些特性对哈希函数的每一次使用都有必要。比如：谜题友好旨在比特币采矿中具有重要性

1.2 哈希指针及数据结构

哈希指针hash pointer：一种数据结构。即一个指向数据存储位置及其位置数据的哈希值的指针。
哈希与普通指针相比：普通指针只能告诉数据存储的位置，哈希指针可以告诉数据存储的位置+给你一种方式来验证数据没有被篡改过。

哈希指针

1.2.1 区块链

区块链block chain：通过哈希指针构建一个链表的数据结构。
普通链表：有一系列区块，每个a区块既有数据也有一个指向上一个区块的指针。
区块链中，上一个区块指针被置换为哈希指针（因此每个区块能告诉上一个区块的的值在哪里+该值的摘要=验证那个值没有改变）

区块链

防篡改日志

1.2.3 梅克尔树

梅克尔树 Merkle trees：使用哈希指针的二叉树。
数据结构：
①所有的数据区块被两两分组，指向这些数据区块的指针被存储在上一层的父节点中。
②这些父节点再次被两两分组，指向父节点的指针被存储在上一层的父节点中。
③持续反复。
④最后达到树的根节点。

梅克尔树

应用：隶属证明
梅克尔树的另一个特点：可以实现简洁的隶属证明。（这点与区块链不同）
原理：为了证明某个数据区块来自一个梅克尔树，只需找到该数据区块到根节点的路径。
详情参见书18页。

梅克尔树隶属证明内容

非隶属证明：
有了排序梅克尔树，可在一个对数复杂度的条件下验证某一个数据区块并非来自梅克尔树。
证明某个特定区块不属于梅克尔树，通过展示被验证区块之前+之后的区块路径即可。
①如果之前之后两个区块在树上连续，则被验证区块与该梅克尔树之间为非隶属关系
②在两个条目之间，隶属于梅克尔树。

总结：可在任何以指针为基础的数据结构中使用哈希指针，只要数据结构不存在循环。（如果存在循环，将不能使所有哈希值得到匹配，因为没有一个根节点让我们追溯）

1.3 数字签名

数字签名 digital dignatures 被认为是对纸上手写签名的数字模拟。需要有两个特性要求：
①可自己制作自己签名，但任何看到它的人都可验证其有效性
②希望签名只与某一特定文件发生联系，因此该签名不能用于表明你同意或支持另一份不同的文件。
（对于手写签名，这条就是确保别人不能将你的签名从一份文件上扯下来粘贴到另一份文件末尾）

数字签名方案：其中generateKeys和sign可采用随机算法。

⑴ (sk,pk) := generateKeys(keysize) 
generateKeys方法把keysize作为输入：产生一对公钥和私钥。
私钥sk：被安全保存，用来签名一段消息。
公钥pk：任何人都可找到，拿着它可以用来验证你的签名。
⑵ sig := sign(sk,message) 
签名过程就是把一段消息和私钥作为一个输入
对于消息输出是签名。
⑶ isValid := verify(pk,message,sig)
验证过程通过把一段消息+签名消息与公钥作为输入
返回结果为真：证明签名属实。
返回结果为假：证明签名消息为假。

我们要求两个性质有效：即有效签名可以通过验证和签名不可伪造。
① 有效签名可以通过验证：verify(pk,message,sign(sk,message))==true
② 签名不可伪造

验证第一条性质：我用我的密钥sk签署一条消息后，有人使用我的公钥pk验证关于同一条消息的签名，该签名必须证实为正确。

验证第二条性质：不可为造性 要求计算上不可能伪造签名。不可伪造性游戏：对手和挑战者一起玩。如果对手可在一个没有见过的消息上进行签名，对手赢。反之，挑战者赢。证明这个数字签名方案不可伪造。

实践中的考量
算法概念转化为现实中可执行的数字签名机制，考虑问题很多。
ⅰ很多签名算法是随机的，则需要随机性的良好来源
ⅱ 信息大小 。
解决方法是：对信息的哈希值进行签署，使用输出值为256位的加密的哈希函数，将信息的哈希值作为信息摘要，哈希函数具有碰撞阻力，因此这种方式是安全的。后面还有一种方法是可以对哈希指针进行签署。

1.3.1 椭圆曲线数字签名算法
椭圆曲线数字签名算法 ECDSA：比特币使用的数字签名方案。（ECDSA是美国政府的标准，是DSA电子签名算法利用了椭圆曲线的升级版）
注：比特币使用ECDSA算法，而非标准椭圆曲线"secp 256k1"。

相关参数介绍：
个人密钥：256位。
公钥（未压缩）：512位。
公钥（压缩）：257位。
待签名信息：256位。
签名：512位。
注：虽然ECDSA只能签署256位的信息，但实际上信息在签署之前总是已经经过哈希压缩。因此，任何大小的信息都能被有效签署。

使用ECDSA，确保随机性良好来源至关重要。不良来源可能会导致密钥信息的泄露。但ECDSA很古怪，即你若仅在生成签名时使用了不良随机，而你使用的密钥完美无缺，你的个人密钥还是由可能泄露。（这是DSA的古怪之处，并不针对椭圆曲线）。
如果个人密钥泄露，对手就可伪造你的签名。
加密货币即加密技术
比特币没有使用任何加密术，因为没有加密的需要。很多技术（比如承诺方案）在某种程度上隐藏信息，但是这与加密术不同。

1.4 公钥即身份

从数字签名模式中拿出一个公共验证密钥，并将其一个人或一个系统参与者的身份对等。如果一条消息的签名被公钥pk正确验证，则可认为pk就是在表达这条信息。从这个角度，公钥就是身份，让某人能为pk身份发声，必须知道相应的密钥sk。
结果：可随时制定新的身份。
实践中，你可能会使用pk的哈希作为你的身份（因为公钥很大）。验证时候需要两点：（1）你的身份确实是pk的哈希（2）信息能经过公钥pk验证。

去中心化身份管理
公钥和私钥的体系，帮助我们引入去中心化的身份管理的概念。想要新的身份，可随机生成一个，想要多少就生成多少。事实上，这就是比特币对待身份的方式。这些身份在比特币语言中被称为地址，地址其实就是公钥的哈希值。
注：比特币系统中，你不需要明确地注册或揭露你的真实姓名，但是你的行为模式本身可能是可识别的。

1.5 两种简单的加密货币

密码术到加密货币。
1.5.1 高飞币
高飞币 GoofyCoin：想到的最简单的加密货币。仅有两个规则即：制定高飞可以随时创建新币 和 这个新创建的币都属于他。
详情参加书27页。

高飞币交易

1.5.2 财奴币
解决双重支付问题，涉及到财奴币ScroogeCoin。
财奴币是以高飞币为基础创建的，但在数据结构方面更复杂。

第一个概念：
一个叫财奴的指定实体将负责公布包含所有发生过的交易历史记录的仅增账目（保证了写入这个账目的任何数据都会永久保留下来）。
若项目真的仅增，则通过要求所有的交易在被接受前都写入项目，便可预防双重支付。
如何执行这个仅增功能？财奴创建一个区块链（形成一系列数据块，每个数据块中都包含一次交易，实践中优化的做法就是把多次交易放在同一个区块中，比如比特币，每个区块包含交易的ID和内容+上一个区块的哈希指针），进行数字签名（针对最后一个哈希指针），最后将签名和区块链一起发布。

财奴币系统中的区块链

财奴币中有两种交易。
第一种：造币CreateCoins
基于高飞创造新币的程序，将其扩展即可在一次交易中创建多个币量。（造币交易创造了多个不同个数量和归属于不同拥有者的新货币，称为虚拟货币ID即指该次交易中交易ID和货币序号的组合）详情参见书30页。
第二种：付币PayCoins
消耗币，创建具有相同总值的新币，新币可能属于不同的人（公钥），交易必须由一个支付该币的人来进行签署。满足以下四个条件，付币交易有效：
⑴被消耗的币为有效货币，即在之前交易中创建的
⑵被消耗的币在之前交易没被消耗掉，即不是双重支出
⑶本次交易产生的币值=消耗的币值量，即只有财奴才可以创建新币。
⑷本次交易被消耗的所有币均有其所有者的有效签署。
注意：直至发布之前，即使满足前三条件，仍然可能是一个被双重支付抢占的交易。

财奴币核心问题
工作原理是：人们可以看见哪些币是有效的。防止双重支付。
问题是：中心化。

写于2018.5.22 12：53