Bitcoin and Cryptocurrency Technologies 学习笔记 （week 1)

Coursera - Introduction to Crypto and Cryptocurrencies 第一周的笔记

一、哈希函数

Hash函数指可以将任意长度的数据映射到有限长度的域上，比特币使用SHA-256作为Hash 函数，Hash函数具有以下三特性

1. Collision Free

假设 Hash 函数为H，没人有能力找到 x !=y ，但 H(x) == H(y)。
注意： x!=y 且 H(x) == H(y) 是可能存在的，但对于复杂的Hash函数，现有算力耗尽宇宙年龄，都不一定找到。

2. Hiding

Hash函数为H, 给出H(x), 无法反推出 x.
应用：网站密码存储，网站数据库保存Hash后的密码，而不是明文密码。为防止撞库，需要加salt.

3. Puzzle friendly

给定一个分布足够高的最小熵k 和 H(k | x) 后的结果 y, 想要求出x，只能通过随机遍历。
应用：比特币挖矿，谁最先计算出x, 谁就获得挖矿的奖励，挖矿难度的增加就是Hash函数复杂性的增加。

二、公钥私钥 + 数字签名

1. 公私钥左右

公钥的主要作用：加密；验证签名。
私钥的主要作用：签名；解密。

2. 公私钥产生

有两种产生公钥私钥的方法： RSA 和 ECC, 具体原理比较复杂，但本质上利用了某种数学计算的有限时间不可逆性。
指可以很容易的从私钥推导出公钥， 但从公钥推导出私钥，以现有的科技，需要耗费上亿年的时间..
ECC 比 RSA 性能好，强度高，未来可能成为唯一的产生算法，加密货币都是使用ECC

3. 数字签名

用伪代码来解释

(private_key, public_key) = generateKeys()

signature = sign( private_key, message) 

isValid = verify(pubic_key, message, signature)

三、区块链 + Merkle 树

1. 区块链

很多笔交易信息构成一个区块，每一个区块都会根据区块内容产生一个Hash值，每一个区块都保存其父区块的Hash值，如果区块内容改变，区块的Hash值就会发生变化。

区块链里的第一个区块被称为创世区块，此区块的数据被Hardcode到了比特币代码里，且里边包含的50个比特币无法交易。

2. Merkle 树

Merkle树是一种哈希二叉树，它用作快速归纳和校验大规模数据完整性。Merkle树根据区块中每一笔交易的Hash值自底向上构建。

应用：普通的手机钱包不可能保存所有区块链的数据，但可以只保存区块header数据(里边含有Merkle值)， 给定一笔transaction Hash值 和 Merkle树的路径，根据Merkle root，可以检查这笔交易是否存在在区块中。

四、 编程作业 Scrooge Coin

作业设计的特别好，能根据代码加深对transaction的理解, 粘贴一下transaction的数据结构

public class Transaction {

    public class Input {
        /** hash of the Transaction whose output is being used */
        public byte[] prevTxHash;
        /** used output's index in the previous transaction */
        public int outputIndex;
        /** the signature produced to check validity */
        public byte[] signature;

        public Input(byte[] prevHash, int index) {
            if (prevHash == null)
                prevTxHash = null;
            else
                prevTxHash = Arrays.copyOf(prevHash, prevHash.length);
            outputIndex = index;
        }

        public void addSignature(byte[] sig) {
            if (sig == null)
                signature = null;
            else
                signature = Arrays.copyOf(sig, sig.length);
        }
    }

    public class Output {
        /** value in bitcoins of the output */
        public double value;
        /** the address or public key of the recipient */
        public PublicKey address;

        public Output(double v, PublicKey addr) {
            value = v;
            address = addr;
        }
    }
}