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

in #cn7 years ago (edited)


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;
        }
    }
}