比特币与区块链技术 Week 1 - Scrooge Coin

开始

这周开始刷Coursera上的区块链MOOC: Bitcoin and Cryptocurrency Technologies

普林斯顿大学15年开的以比特币为例的区块链课程,看起来不明觉历的样子。


区块链要用到的加密算法

开始之前首先要了解一下区块链用到了哪些加密算法。

Hash Function

Hash Function 是一类有如下特质的函数:

在比特币中,使用了 SHA256 作为 Hash Function。SHA256 输出长度为 256-bit。其它常用的 Hash Function 还包括 MD5, SHA-1 等。

通过 Hash Function 的特质,我们会发现它可能存在「碰撞」(Collision) 的问题。很显然,「任意长度字符串」的集合,其规模要远远大于 256-bit 的集合。不过概率上来说,找到两个字符串的 Hash Value 完全相同的可能性是可以忽略不计的。不过要是哪天量子计算机成熟了,人类还是有可能破解这些 Hash Function 的……

通过 Hash Function, 比特币对每次交易的内容进行签名,防止交易被伪造。

非对称加密

你可能会听说过「对称加密」「非对称加密」两类加密算法。在区块链技术中,非对称加密常常用来做钱包/交易的验证。

对称加密中我们只有一个密钥,同时用于加密和解密;而非对称加密中,我们同时有「公钥」「私钥」两把密钥,他们分别用于解密和加密密文。

如果你使用过比特币钱包的话,你可能会注意到每个钱包都有一个唯一的地址。事实上那就是一把公钥,通过这把公钥解密密文,我们才能验证钱包的合法性。同时我们也保证了密文不会被伪造。

比特币中使用的非对称加密算法为ESCDA。


数据结构

那么我们用什么数据结构来存储交易信息并且能防止交易信息不被篡改呢?这就要说到区块链中最重要的数据结构,Hash Pointer(哈希指针)。

链表

使用链表存储,每个Block Chain中的Hash Pointer不仅指向前一个数据块,还指向其哈希值的数据。

篡改一个块的数据,会导致其前部哈希值无法验证成功。

同时,头部的块是不可修改的。它被称为创世块(Genesis Block)。

Merkle Tree

Merkle Tree的idea就是用二叉树来存储交易信息。使用哈希指针的二叉树就叫做梅克尔树(Merkle Tree),因为发明这玩意的人就叫做Ralph Merkle。

假设我们有很多包含数据的区块,这些区块就构成了树的叶子节点。我们将这些数据区块两两分组,然后为每一组建立一个有两个哈希指针的数据结构,每个指针对应一个区块,这些数据结构就构成了树的下一个层次。按照这种方法将这些区块组两两分组,为每一组建立一个包含每个区块组哈希指针的新的数据结构。以此类推,直到我们得到一个单一区块,这就是树根节点。

相对链表,二叉树的优点在于更高的查找效率。我们能够很快判断一个区块的有效性。


两种简单的「数字货币」

了解了基本算法和数据结构,我们可以来看看他们实践的结果是什么样的。有趣的是,课本里这两种数字货币都使用了动画片米老鼠里的人物命名……

GoofyCoin 高飞币

这里的Goofy就是那只二缺的狗高飞……

GoofyCoin是最简单的一种数字货币。它遵循如下规则:

但是GoofyCoin在实践的时候会遇到「双重支付」的问题。即一个人可以同时给多个人转账。

Scrooge Coin

这是一个真正能用的数字货币。这里的Scrooge指的是唐老鸭一个葛朗台式的土豪叔叔。。

它可以用于解决双重支付问题,Scrooge Coin是以Goofy Coin为基础创建的,但是在数据结构方面更复杂。一个叫Scrooge奴的指定实体将负责公布包含所有发生过的交易历史记录的仅增账目,账目的仅增特性保证了写入这个账目的任何数据都会永久保留下来。如果账目真的为仅增,通过要求所有的交易在被接收前都写入项目,我们可以用其防止双重支付的发生。这样,如果之前币已经转给了一个不同的所有者,大家都可以看到。


当然了,以上说到的数字货币都没有涉及到比特币最重要的一个环节:去中心化。那么比特币的去中心化是怎么实现的?请听下回分解。