区块链相关算法
什么时区块链
区块链本质上是一个去中心化的分布式账本数据库，它的特点有：
- 去中心化
- 记录不可更改
- 多数表决认可记录
- 非对称加密
Blockchin结构
比较早的知名应用就是比特币了，其他比较多用的联合／私有区块链是hyperledger。
数字摘要： Hash算法
数字摘要是对内容进行 Hash 运算，获取唯一的摘要值来指代原始数字内容。数字摘要主要用来确保内容没被篡改过。
hash （哈希或散列）算法是信息技术领域非常基础也非常重要的技术。它能任意长度的二进制值（明文）映射为较短的固定长度的二进制值（hash 值），并且不同的明文很难映射为相同的 hash 值。
比如使用MD5 Hash “Hello， world” 获取到其hash值为 22c3683b094136c3398391ae71b20f04
$ echo "hello, world" | MD5
22c3683b094136c3398391ae71b20f04
好的hash算法需要满足：
- 正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
- 逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
- 输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。
- 冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。
冲突避免有时候又被称为“抗碰撞性”。如果给定一个明文前提下，无法找到碰撞的另一个明文，称为“抗弱碰撞性”；如果无法找到任意两个明文，发生碰撞，则称算法具有“抗强碰撞性”
比较流行的Hash算法有MD5， SHA-1等，其中MD5已经被验证不安全，SHA-1不够安全，建议使用SHA-256／SHA-512或更新的算法。
比特币中的Hash方法采用的是SHA-256和RIPEMD-160， Hyperledge采用了 ECDASign (Elliptic Curve Digital Signature Algorithm )
加密算法
Hash的内容不可逆转，而需要逆转的内容需要使用加密算法，加密算法分为对称加密和非对称加密。
对称加密(symmetric-key algorithm)是指加密和解密都用一个密钥。常用的对称加密算法有：AES，DES，RC4，RC5等。
非对称加密方法(asymmetric key encryption AKA public-key encryption)所采用公钥和私钥的形式来对文件进行加密。用户可以用公钥来对文件进行加密，用私钥对文件解密。常见的非对称加密算法有RSA，Elgamal，ECC等
Bitcoin中本地密钥保存使用了对称加密，节点之间交互使用非对称加密算法[ECDSA(secp256k1实现)]。
Hyperledge的加密算法是ECDSA+X509
Bloom Filter 布隆转换
Bloom Fitler可谓是最优雅的算法之一，它是1970年由Burton Howard Bloom提出的一种多哈希函数映射的快速查找算法，通常应用在一些需要快速判断某个元素是否属于集合，但是并不严格要求100%正确的场合，比如判断网页是否已经爬过，电话是否在黑名单中。
Bloom Filter的处理流程
- 初始化m位的位数组，每一位都设置为零
- 采用k个不同的hash算法
- 对于n个元素集，k次hash算法将每个元素影射到{1,…,m}的范围
- 单需要判断一个元素是否在其中，只需要将此元素应用k次hash，如果映射赶出来的位置都是1，表示此元素在集合中，否则不在
以维基百科上的图为例
- m=18, k=3, 元素集为{x, y, z}
- x, y, z经三次hash后值为 010111000001010010
- w经过3次hash后值为 000010000000010100, 由于whash后的值并不是每一位1在集合hash上并不是1，所以w不在集合中
- 如果某个元素hash后的值为000010000001000010，1位元素全中，则在集合中
k一般是参数，会比m小很多。一般建议k的取值参考公式：k = (m / n) * ln2， 最好不超过50次
此算法的问题：
- 存在一定的错误率，元素越多错误率越高
- 不支持删除元素
改进算法：
Counting filter：它将标准Bloom Filter位数组的每一位扩展为一个n的计数器（n-bit Counter），在插入元素时给对应的k（k为哈希函数个数）个Counter的值分别加1，删除元素时给对应的k个Counter的值分别减1。Counting Bloom Filter通过多占用几倍的存储空间的代价，给Bloom Filter增加了删除操作。一般n设置为3～4，多占用3~4倍左右的空间。
[待续]
Proof of work / Consensus
PoW是为了解决拜占庭问题