区块链技术概观(二):资料分割与密码学

时间:2019-07-27       来源:

前篇讲到了如何利用大型流水系统来产生可取代传统货币的数位货币系统,那幺这个系统为何称做区块链呢?我们接下来再做个技术概观。

将流水帐资料分成区块

传统的流水帐有如电脑系统的 Log 一样,将所有资料一行一行写入,其实相当容易窜改,而且死无对证,加上一直不断写入也不能确定有没有漏写或少写。为了解决这个问题,将资料按照出现的时间点切分成区块就显得必要了!那幺链又从何来的呢?

过去某些应用程式中,的确曾经出现过将连续性资料切分成许多小区块的做法,且每个区块都会使用一些有检查效果甚至错误更正效果的检查码来确保它的正确性,好比 Checksum。如果我们把前一个区块的 checksum 也带入后一个区块的内容,一起计算出后一个区块的 checksum 会如何呢?马上可以见到在这种资料结构下,如果想要更动某一区块的内容,那就必需重新计算由目标区块起往最末端区块中所有 checksum!因此要更动历史资料就变得很麻烦了!这样子的资料结构由于前后密切相关,因此称为区块链。我们可以很简单地看到,愈早的资料愈难以修改,因此愈早的资料愈安全,而最新的资料最不安全。

Proof-of-Works

在新型资料链技术中有一个很大的安全性保障就是 Proof-of-works。回头看一下早期的资料链,如果依现在的电脑计算力,要重新计算十万个 checksum 会有多难?就算用到 SHA3 加上一般 CPU 来做,恐怕也不用几分钟吧?(笔者的 i 牌 2680 就可以轻鬆达到近每秒 1K hash 的效能了),如果用 SHA-1 就更惊人了,一用上 GPU 大概没几秒就破光光了。因此可以发现,光是使用传统 checksum 概念全然没有安全性可言。当初设计比特币的中本聪先生就导入了原本用以防止 SPAM Mail 的 Proof-of-Works 概念,让每个区块的「Checksum」代换成「种子数 + 特定範围内的 hash 解」,这样就达成了确保每个区块都要花上不少时间来包装。

所谓的 Proof-of-Works 概念相当简单,只是一般人很难一下子理解。电脑传送资料时常会导入 checksum 的观念,以防止资料在传输过程有错误。因此在资料结尾加上 checksum 是天天在做的事,Proof-of-Works 只不过是把资料尾端加上一个种子数字,套入一个数学函数,去计算结果的值,我们可以在协定中设计好,这个值必需符合某种规範才能叫正确解。通常这个种子数会由 0 开始一直往上加到极大,如果条件很难,那幺计算出结果就要试非常多次,也等于会花掉很多时间。因此叫做 Proof-of-Works。

我们来玩一段非常简单且有「笑」的 Proof-of-Works:假设我们要传的资料在数字层面来看,资料码是 0×F0、0×A1、0×08、0×32,就这样 4 个 byte 的资料好了,如果设计一个 Proof-of-Works 规则是:将 4 个 byte 做无进位相加起来,再加上一个 byte 的种子数,它的结果必须是 0×00,那幺我们由 0 开始要试几次才能找到解呢?我们先把 4 个数字做无进位相加得到了 0×CC,再加上种子数字 1,得到 0×CD……一直试到第 51 次,在种子数为 51 的时候终于找到解了!所以 Proof-of-Works 的解答就是(51,0),而且我们试了 51 次。当然任何一个学过密码学的人现在应该都笑到抽筋了,因为加法是可以逆推的演算法,也就是现实世界里,当我们把 4 个数字加起来得到 0×CC 时,我们马上就可以用 0 去减 0×CC 得到 51,根本连试的必要都没有。以上只是给各位一个概念,Proof-of-Works 是如何运作。

Hash 函数登场

那幺世界上有适用于实做高强度,且效果可预期的计算方法吗?有的,就是密码学常用到的各种 Hash 函数。密码学用的 Hash 函数都要符合几个特性才算设计成功:

输出长度最好固定,不会因为资料变动一个 Byte,输出长度就爆增 10 个 byte。输出的空间大小也要够大,否则用猜的就可以暴力破解了。随机性要很好,Hash(杂凑)的用意就是将一大段数字,映射到一个目标空间中,好比 SHA-256 就是将输入的资料,映射到 256 bit 的数字空间任意一个数字。因此要有随机很好的特性,否则如果特定分布在某个段落,骇客也不用真算了,只要去猜那几个段落就会有很高的中奖率。不可逆推,我们无法像加减法一样,看到结果就知道原本的数值(看看上面的例子就知道了)。传统上 Hash 的使用方法是将资料丢进杂凑函数中,得到一个值,这个值基本上就代表那个资料在解答空间的映射特徵,其他文件与它有同样值的机率小到可视为 0。因此我们可以靠检查杂凑值来知道文件是否有被修改或传输错误。

Hashcash 运作观念

当年垃圾信件氾滥又没有很好的挡信方案时,有部分人士提出 Hashcash 的观念,来确保你不是寄垃圾信的人,做法就是标準的 Proof-of-Works。Hashcash 当时要求寄件者在把 Email 内容加上一串种子数字做 SHA-1 160 bit 杂凑运算,如果得到结果它的前 N bit 都是 0,那幺就把那个种子数字及 hash 结果加在信件标头中,这个标头显示的是前 20 bit 都为 0 的强度要求以及种子数和解。

X-Hashcash: 1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi

当时要做到求出前 20 bit 为 0 的解需要花掉数十秒,因此这个方法可以确保送信的 CPU 每十至数十秒才能送出一封信,对于一般寄信人的影响应该不大,但是对要发送上万封圾垃信的人影响就很大了。我们可以简单由机率论来推出要试几次才能得到解:如果 SHA-1 非常随机,那幺要求出前 20 bit 都为 0 的次数就差不多在 2^20 这幺多次(1Mega = 1048576)。如果只要第一个 bit 为 0,那幺只要两次就差不多找到了。

那幺收件方如何确认对方真的找到解了呢?当然只要做一次快速验算就知道了,在寄信者的标头已包括了正确的种子数以及求出来的解,因此拿来做一次 SHA-1 运算马上就可以知道正确与否了。这样子一来,寄件者非常辛苦忙了几十秒,但收件者很轻鬆就搞定了,也是 Proof-of-Works 重要的特性之一。而 Hashcash 被採用的原因之一,则是它提供了不同难度的设定,可以将它写在协议中,这点也很重要,试想网路中如果只有一台挖矿机,绝对挡不了骇客攻击,但是如果有成千上万台挖矿机,而难度维持不变,那幺也无法维持平均每 10 分钟包装出一个区块的速度。因此比特币的设计就会以近两週的包装速度来为基準计算是否该将难度提升。

比特币如何做?

Hashcash 诞生的时间很早,且 SHA-1 编码事实上后来也被发现可用较短时间找出解的破解方法,比特币的设计者当然不可能在多年之后还照抄。我们先来看看比特币如何把资料串成链:比特币的区块大致分成两区,第一区叫标头,第二区则是放置交易资讯。比特币会将 Proof-of-Works 的结果,以及前一个区块的 Proof-of-Works 放在标头,标头中并没有交易资讯,但是有第二区中的交易资讯做的 hash,这些交易资讯 hash 出来的结果,会依马可夫链的排列方式写在标头中一个叫 Merkle Root 的栏位,当区块在做 Proof-of-Works 时,事实上只做标头部分,但因为交易资讯的 hash 已放入标头了,因此若单独改变交易资讯而不改变标头的 Merkle Root,其他人会发现交易的 hash 值和标头的不符合,所以虽然交易资讯本身没有进区块链运算,但是安全性仍然很好。

Block #477922

SummaryNumber Of Transactions1657Output Total26,295.84722444 BTCEstimated Transaction Volume2,449.84737287 BTCTransaction Fees1.19323829 BTCHeight477922 (Main Chain)Timestamp2017-07-28 06:41:02Received Time2017-07-28 06:41:02Relayed ByAntPoolDifficulty860,221,984,436.22Bits402736949Size996.843 KBVersion0x20000002Nonce1445765072Block Reward12.5 BTCHashesHash0000000000000000012bfae6f7ad25c56e53729ff9adfee157b6c7f28c4201d4Previous Block00000000000000000036154762753295f46fa39b609c6f676f2fd60406412ecdNext Block(s)Merkle Root492d9973d12330ade7f103a44926926830d9fadb5a811baede590b1dfd35255f

 

从上图中我们可以看到比特币的 Proof-of-Works 是採行 256 bit 的输出结果,那是因为比特币用的是改良后的 SHA-1,计算结构很相近但其中部分参数不同,输出的结果也由 160 bit 扩增至 256 bit。不过在 2005 年一篇论文中已证实 SHA-1 有潜在危险,有机会较少的尝试次数就破解(事实上在今年初,Google 的研究团队的确找到方式,成功在有限时间内破解 SHA-1。所谓破解的意思是,当文件被小幅度修改时,原本 SHA-1 值就会随机改变,要再利用短时间且小幅的改变文件其他部分来找到同样 hash 值的机率机乎为 0,但利用破解手法就可在短时间且只要适量的计算力就办到)。

SHA-256 既然是 SHA-1 的变体,那幺同样的漏洞自然也存在(但由于空间较大因此目前还是比较难破解),比特币为了安全性问题使用 Double SHA-256,也就是 Hash 结果 = SHA256 ( SHA256 ( 本文内容 ) )。这样子就算使用速算破解法难度还是会拉高到天文数字,所以我们在比特币标头看到的 Proof-of-Work Hash 值都是 Double SHA256。

我们在标头还可以看到种子数的栏位,其实由这个栏位笔者就可以判断出中本聪一定是一个年纪比笔者还大的老人,因为可看到一个几近吝啬而危害安全性的设计:它只有 32 位元!我们从机率论来倒推,基本上只要 Hashcash 的难度达到 32 个 0 之后,这个栏位就不够用了,而目前比特币的难度早就飙破天际了。看看上图足足有 52 个 0!那幺为何不一开始就写死足够的长度在固定栏位使用呢?通常只有很老的工程师才会有这种坏习惯,因为以前电脑记忆体不足,网路不快,大家都省着用,没到达必需扩增前都不想使用太多位元来放东西。现在的比特币种子数只有最低的 32 位元放在 Nonce 栏位内,其他多出来的部分是 coin base transaction 中拿没用的栏位来放,且协定没有写得很明确应该如何做,是靠开发者社群协议达成的。

标头也有目前难度,过去 Hashcash 一次就往后跳一个 0,难度增加一倍,这是固定的倍增法,但比特币为了维持更好的精确性,控制每分钟左右产出一个区块,所以没有用倍增的方法(如果用倍增法,那幺只要调整一次难度,就会让原本 10 分钟可产生的区块变成 20 分钟),因为短期内的计算量增加根本不可能倍增,而是使用了只要 hash 值小于一个特定整数就算找到解的方式。

原本 Hashcash = 解答要小于 2^N(最前面的 160-N bit 要为零)比特币用的 Hashcash = 解答小于一个系统计算出的整数即可。目前的难度为 860,221,984,436.22

目前的比特币区块长度只定义到 1MB,因此如果短期内挤进太多交易量,就会有些交易没有包到了。当然按照比特币的定义,这交易绝不会随便消失,会一直等到区块使用量足够包装这笔交易时再被封进区块链。

近来有不少交易都延迟得很严重,就是因为区块空间不够大,这和比特币原本的设计精神有违,因此社群开发者也在讨论将区块空间放大 4 倍的方法(当然这被放大成一场比特币大分裂的政治风暴又是可另外讨论的议题了)。

(首图来源:shutterstock)

延伸阅读:区块链技术概观(一):让我们从历史文本说起