Foreword

最近正在学cryptocurrency，闲来无事想把自己的学习路程记录下来（有时间就写，反正写了也没人看zz）

Introduction to Cryptography and Cryptocurrencies

1. hash function

三大特性：collision resistance, hiding和puzzle friendliness。前两个都很好理解，就是正常密码学里的hash的特性，第三个在密码学里面没有要求。

puzzle friendliness: A hash function is said to be puzzle friendly if for every possible n-bit output value y, if k is chosen from a distribution with high min-entropy, then it is infeasible to find x such that H(k||x)=y in time significantly less than 2^n

这个是官方的解释，那什么是high min-entropy呢，就是说取一个数，组成它的bit数越多，他的min-entropy越高。也就是，如果你均匀的随机取一个很大的数做为k，那取的这个过程就是chosen from a distribution with high min-entropy. 

如果即使是这样已知了某个k还是没有除了trying random values of x以外别的更好的方法求解x，那么这个hash function就是puzzle friendly的。从high min-entropy distribution 里面取k是为了防止有些人cheat by pre-computing a solution to the puzzle 在一个范围较小的k取值范围内.

2. data structure (block chain)

block chain

和linked list类似，只不过把previous block pointer换成了hash pointer。这样每个block不仅告诉我们上一个block在哪，也告诉我们上一个block的hash。最后连起来只要存储最后的hash就能保证全部数据的integrity。注意：这里每个hash的值都是hash的全部的上一个block的东西，也就是H(previous hash + data)。

Tamper-evident log

就算attacker改了数据并修改了所有之后的hash pointer，因为它不能修改最终的H( )，他的修改最终还是会被检测到。所以block chain可以作为tamper-evident log来用。

Merkle tree

类似的binary tree 结构，只不过一层一层的hash上去，最后也是只存一个root hash值就可以。Merkle tree有个好处，就是可以快速的认证proof of membership，block chain的确认是O(n)，tree的确认只需O(log(n))。（当你想确认一个block data是否是member的时候，你需要提供从data一直到root这一条链上的hash值，如上图你只需要log(n)=4个block，而block chain最坏情况需要n个block才能确认。）

还有sorted merkle tree，就是最底层的data都按照某种顺序排列，这种可以方便找到proof of nonmembership，只要相邻的两个data block一个比它大一个比它小，就说明它不在这里面。

3. digital signature

bitcoin主要用的是ECDSA (Ellipse Curve Digital Signature Algorithm) secp256k1曲线，而TLS用的是secp256r1曲线。

特性：private key: 256 bits, uncompressed public key: 512 bits, compressed public key: 257 bits, message to be signed: 256 bits, signature: 512 bits. (Note: always sign the hash of message, not the whole plaintext)

4. two simple cryptocurrencies

Goofycoin: 

-Goofy可以创造coin用一个独一无二的coin id

-币的拥有者可以把币给别人，通过用自己的密钥sign the statment "pass on this coin to X" (X 是接收者的pk)

-任何人都可以verify这个币通过hash pointer一步一步直到创建者goofy

goofycoin的币转移机制和bitcoin类似，但goofycoin不安全，因为没有解决double-spending attack.

Double-spending attack: Alice 把币卖给bob但是不让任何其他人知道，然后再把相同的币卖给Charlie。

Scroogecoin:

使用block chain，scrooge来签最后的data，这样就能总体认证这个transaction的有效性，scrooge会publish所有的transaction这样别人也能知道自己收到的币是不是有效（没有被double spending）的。

但是这样scrooge的权利就太大了，比如他可以故意不给人publish自己的signature直到那个人付一些费用。或者一旦他不打算继续运营下去，整个系统都将瘫痪。（主要问题：centralization）

去中心化的scroogecoin就非常像bitcoin了，难点有三：1）用户怎么同意一个block chain作为这个币过去所有交易的认证？ 2）所有用户必须统一哪个transaction是有效的，及哪个transaction是真实发生的 3）产生新币的过程也必须是decentralized