我开发了一个基于 Beancount 的账本托管服务 HostedBeans,欢迎大家来了解纯文本复式记账并试用我的服务。
标签 #密码学

GPG 与端到端加密:论什么才是可以信任的

本文由我去年 6 月在 LeanCloud 的一次技术分享整理而来,需要读者对公钥加密算法有基本的了解。

如果提到 GPG 那么不得不提的就是公钥加密算法,首先我们先来快速地了解一下最知名的公钥加密算法 —— RSA:在 RSA 中有「公钥」和「私钥」两种密钥,其中私钥可以导出公钥,但公钥无法反推私钥。如果用公钥加密数据的话,那么只有私钥可以解密;如果使用私钥签名数据的话,那么可以验签名。

密码学账户

顾名思义,通常我们会将公钥公开地发布,作为自己身份的代表,就好像用户名一样(虽然是一个难以记忆的随机字符串);而将私钥秘密地保存,作为身份的证明,就像密码一样。如果一个账户是由一个公钥加密算法的密钥对所保护的,那我们称之为「密码学账户」,我们身边常见的密码学账户包括:

  • SSL 证书(用于 HTTPS 等加密通讯)
  • S/MIME 证书(用于邮件加密和认证)
  • SSH 密钥(用于登录服务器的凭证)
  • Bitcoin 钱包
  • GPG ID

这些账户和我们通常注册的互联网服务很不一样,在我们通常注册的互联网服务中,你的账户实际上是由网站的维护者管理的,你为账户设置的密码并没有真的用来加密数据,而只是一种证明账户所有权的凭证,在每次登录时你向网站发送密码,来证明自己是账户的所有者。一旦你忘记了密码,网站的维护者在通过其他渠道(邮箱地址、手机号码)确认了你的身份之后,也可以帮助你重置密码。

而在密码学账户中,你拥有账户的唯一凭证就是你的密钥对 —— 通常是计算机上的一个文件,你通过使用这个密钥对进行签名来管理你的账户、进行解密来访问机密数据。密码学账户既是更加安全的(不存在具有特权的管理者),同时也是更加危险的(一旦丢失无法找回;一旦泄漏也无法重置)。

公钥交换

公钥加密算法看上去很美好,一旦我们有了对方的公钥,只需在通讯时用对方的公钥加密数据,就万无一失了,但这其中 最薄弱的一个环节就是「得到对方的公钥」,即「公钥交换」

上图是理想的情况,A 和 B 互相之间交换公钥,后续的通讯就可以以加密的方式进行了。但如果这时出现了一个能够监听和篡改 A 和 B 之间的通讯的 C,然后将自己的公钥发给 A 和 B,就变成了这样:

A 和 B 都以为自己得到了对方的公钥,但实际上他们得到的都是中间人 C 的公钥,这意味着他们之后的通讯都会以 C 的公钥来加密,C 便可以在中间继续进行窃听和篡改。

所以在理论上 不可能存在一种在线的、可靠的、不事先协商的公钥交换机制,因为交换公钥意味着双方还没有开始加密通讯,交换的过程自然没有保障。那么在实际应用中我们是如何解决公钥交换的问题的呢,我们来看一下 SSL 所使用的 X.509 证书体系:

在 X.509 中有一个被称为「证书颁发机构(CA)」的权威的第三方,CA 的数量较为有限,资格变化也并不频繁,所有浏览器(browser)都内置了 CA 的公钥。而网站方(website)在生成了自己的公钥后,需要先找 CA 对自己的公钥进行签名然后才能使用。当浏览器访问一个新的网站时,网站方需要提供经过 CA 签名的公钥,浏览器使用内置的 CA 公钥来验证签名,确保收到的网站的公钥没有被篡改过。

X.509 实际上就是要求大家信任一个权威的第三方并将它们的公钥内置在客户端中,这并不是一个完美的方案,因为在这个体系中 CA 有着非常大的权力,一旦 CA 不按照规则签发证书,那么客户端是无法察觉这种攻击行为的。

GPG

GPG 是 PGP(Pretty Good Privacy)的一个 GPL 实现,也是目前使用最广泛的实现。

「信任一个权威的第三方」对于一些去中心化爱好者是无法接受的:首先我们凭什么去信任这个第三方,其次在 CA 申领证书通常也是需要付费的。那么有没有可能去除这个权威的第三方,而允许大家互相进行认证呢?如何确认一个公钥就是属于这个人的呢?这就是我们接下来要介绍的 GPG 的信任模型:

在 GPG 的信任模型中,用户互相之间对公钥进行认证(通过用自己的私钥进行签名的方式),例如 Alice 和 Bob 是很好的朋友,要么 Alice 就会用自己私钥给 Bob 的公钥签名,然后将这个签名通过 Key Server 广播给其他人。Key Server 仅仅用来交换公钥和签名,因为签名本身是可校验的,所以 Key Server 并没有任何特权。

当另外一个 Alice 的朋友看到 Bob 的公钥,并且发现 Alice 给 Bob 的公钥签过名,那么就可以认为他的朋友 Alice 已经检查过 Bob 的公钥了,如果看到更多朋友给 Bob 签过名,那么就几乎可以认定 Bob 的身份是真实的。

所以 GPG 实际上是一个由「熟人关系」建立起的信任网络,当你认可一个人的身份,即认可这个公钥是属于这个人的,你便可以给他的公钥进行签名,形成一种信任关系,同时这种信任关系又是可以传递的。当你的 GPG 通讯录中有了一些互相信任的朋友之后,便可基于这个关系网来拓展你的朋友圈。

那么既然我们前面提到不可能有一个在线的、可靠的、不事先协商的公钥交换机制,那么这个信任网络在一开始是如何建立起来的呢?答案是使用分散的、多渠道的、可能是线下的方式来交换和确认公钥。如果使用一个固定的协议去交换公钥,而且这个协议本身没有加密保护,那么当然容易被中间人攻击,但如果两个人同时使用多种渠道来交换公钥,例如先用邮件发一次、再用微信发一次、最后再用电话说一次,那么这些渠道同时被攻击的可能性会非常小。

或者更进一步,我们可以采用线下的方式来进行确认,实际上很多技术类会议结束后可能会有一个 Key Signing Party 的活动,大家面对面地确认身份(你可能有必要出示印有照片的证件,例如身份证或护照),用纸和笔记下公钥,然后回家进行签名和上传。

最后你便得到了一些来自其他人签名,代表他们认可了你的身份,即认可了某一个 GPG 公钥代表了你。

GPG 通讯簿

因为 GPG 需要用户自己维护信任关系,因此每个 GPG 的用户都会有一个通讯簿,里面是大量的公钥(代表着一个其他用户)和签名(代表着信任关系)。

下面是我的通讯录中与我自己相关的部分:

~> gpg --list-keys jysperm
pub   4096R/E466CF1E 2014-11-23 [expires: 2017-05-17]
uid       [ultimate] Wang Ziting <jysperm@gmail.com>
uid       [ultimate] Wang Ziting <jysperm@icloud.com>
uid       [ultimate] [jpeg image of size 1476]
sub   2048R/1D795875 2014-11-23 [expires: 2017-05-17]
sub   2048R/289286B3 2014-11-23 [expires: 2017-05-17]
sub   2048R/35B5DE4D 2016-05-17 [expires: 2017-05-17]

其中 E466CF1E 是我的「根公钥」的简写形式,4096R 表示这是一个 4096 bit 的 RSA 密钥对,创建时间是 2014-11-23,有效期至 2017-05-17。一个 GPG 帐号下可以有多个 uid,我可以使用根公钥签署类似于「jysperm@gmail.com 是我的邮箱地址」的签名,来将自己的多个身份关联到一起,上面的 3 个 uid 即我的 2 个邮箱地址和一个头像图片。

我还可以使用根公钥签署一个类似于「我授权 1D795875 为我的子密钥,可以代替我进行签名等操作」的消息来添加额外的子密钥,例如上面的三个 sub 就是三个不同功能的子密钥。就像这样,其实对于 GPG 帐号的管理操作都是通过用私钥签名消息来实现的。

还可以列出与我有关的签名:

~> gpg --list-sigs jysperm
pub   4096R/E466CF1E 2014-11-23 [expires: 2017-05-17]
uid                  Wang Ziting <jysperm@gmail.com>
sig          C07CFB96 2016-05-04  paomian <qtang@leancloud.rocks>
sig 3        7CDC82A7 2015-05-11  Yeechan Lu <wz.bluesnow@gmail.com>
sig 3        E466CF1E 2016-05-17  Wang Ziting <jysperm@gmail.com>
sig          E411E711 2016-06-02  keybase.io/librazy <librazy@keybase.io>
sig          B0B002B8 2016-07-13  dennis (Dennis Zhuang) <killme2008@gmail.com>

这里看到除了我自己之外,还有其他四个人为我 jysperm@gmail.com 这个 uid 进行了签名,认可了 E466CF1E 这个公钥属于 Wang Ziting <jysperm@gmail.com> 这个人。对他人的签名也是可以区分不同的级别的,例如对于「在论坛上混了个脸属」和「每天都见面的同事」你可以给予不同级别的签名来更准确地表达信任关系

使用 GPG

前面我们介绍了 GPG 的信任模型和通讯簿,那么可以在哪些场景下使用 GPG 呢?

首先是你可以用它签名一段消息:

~> echo 'hello' | gpg --clearsign -a
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

hello
-----BEGIN PGP SIGNATURE-----

iQIcBAEBAgAGBQJXfifAAAoJELQPOvDkZs8epZAP/3/jP6k1Dev2a8i8KfY7VDfv
TVGl61kLEbgpgR3mWXFL7PaJ8SyW8N0Dv3cJhYbY8NGp8wbkZa7cUS7DkTb2ArhS
M+IKUJtwUwbfp5fOyT+esaDLWatqjSJ+5IjWX8BOnh5SnLNMURDxsYrJMShfecTD
tbBfnEkIeCFBwIfE0Xs5m23+6i7t77ZgLdn1qpWLTRNpd6Fzi0B653Kr8dREPflI
MAsn6CP90pX55V0LnsZGiAgZV+34iFolhFDd7N5mtPT/zF7OToN2SNJF3YOVikBp
M+1WJL9W8x9DwzhOq8AmPgHIEwBZVNS8Nv+UNadIZJuexR0ERl64e8MdTLft0Qui
ChjUiD7ibkLR433jcms+2EJ04xd6Ie0mp/nH5nMLY1mEgHtLMXql6VHQCbJt80Vf
ZrL2J+BF9Sk1zPh9Hn5NGe+RLX1d/CZ62rYMICRcEwiS9vpWq6m9ouSMNZUYr8S5
a/ooD6gc71t457pVgkMqjo3Auazf4PRilUsAraQZilr+8yPhciE/PX3gBL5CtKHJ
4vKH9P9RngigL6D+YyBB5vMcpXlhx9ShbH2qLr106adJ1XrCpGtSmfxygjRn3xX9
Q1dWUaELUahhcdtK6IwZ6qzyp9AESpSd+Z/bnV7jc8iC0VtMOXipVnMo7J5qyHKD
/+yt8/tzoC4+0MEzlaHJ
=aOto
-----END PGP SIGNATURE-----

上面我们先用 SHA1 对要签名的文本进行进行了一下摘要,然后用 GPG 对这个摘要进行了签名。

因为 Git 中的用户名和邮件地址其实是可以随意更改的,之前有过几次伪造 Commit 冒充大 V 的事件发生。最近 GitHub 支持了为帐号配置 GPG 公钥,然后你便可以在发布新版本的时候用 git tag -s v1.0.0 进行签名:

你可以在本地这样来验证签名,一旦签名认证通过,和正确的 GPG 帐号管理,那么这个 Commit 就不可能是伪造的:

~> git tag -v v1.1.0
object b0e42636df7394ac34f2b61c589233d0c3296d10
type commit
tag v1.1.0
tagger jysperm <jysperm@gmail.com> 1467084786 +0800

gpg: Signature made 6/28 11:33:17 2016 CST
gpg:                using RSA key B40F3AF0E466CF1E
gpg: Good signature from "Wang Ziting <jysperm@gmail.com>"

很多开源软件在发布新版本的二进制包时也会使用 GPG 进行签名,包括 Debian 的软件仓库 apt 也是通过 GPG 进行签名的。

然后你当然也可以用 GPG 加密消息:

~> echo 'hello' | gpg --encrypt -a -r jysperm
-----BEGIN PGP MESSAGE-----

hQEMAyp325QokoazAQf8DDqELYisLFSGo/9Gblr1MEabb9t3V3AcbWkA4uimpYeD
/DTWDlmxrIsvpmDDeV/1bAZ/gMc2DzhODfM4PQf8DfD+lvHwgMBhe1zSBCZlQwkj
xkP+CtF+S8xWTciaexIMQiTHLNu1tvhvCjIeR1qYJY0/E7tdKhS5iG4Jc3/oyCNN
a1m34O9GG5WJsHozGqpfKZFma50onDmQ6TnSuz4iDWrslvq3XuLRXvgOQ6DKArix
Sxnmxg1kMvlIF6AMmQRHaHpyXBoOlaX/NEsl8ESCe9w4KZFTCoFtsEB9tAwQGeGn
6Tnd7BLaxXOabqaSpoNcOlpWDlZcX89lbewAryKbY9I7AbURsuemI37bTizQUjWA
57xm4t7wTUJ/FLx22Amv1ljUa/Rq84rO8d38EQViNGyo31UmRVXy12AmBDU=
=T42S
-----END PGP MESSAGE-----

这里我们指定了我自己的公钥为收信人,可以看到不同于前面,加密消息没有明文部分,除非使用收信人的私钥,否则无法解密:

$ gpg -d < gpg-message
gpg 2048-bit RSA key, ID 289286B3, created 2016-06-28 (main key ID E466CF1E)
    Wang Ziting <jysperm@gmail.com>
hello

SSH

因为 SSH 和 GPG 都支持一样的公钥加密算法(例如 RSA),因此你也可以直接在 SSH 上使用 GPG 的密钥。

例如将你的 GPG 公钥添加到 GitHub,然后使用它来登录 GitHub:

~> export SSH_AUTH_SOCK=~/.gnupg/S.gpg-agent.ssh

~> ssh-add -l
2048 SHA256:wO93TcTQHZtltKfvS0jewFh0CMj4No6xnTegtB8FN+k

~> ssh git@github.com
Hi jysperm! You've successfully authenticated, but GitHub does not provide shell access.
Connection to github.com closed.

管理密码

有一个比较有趣的实践是你可以用 gpg 来加密你的密码,pass-store 是一个基于 GPG 和 Git 的非常简单的密码管理器,它可以用 GPG 来加密密码,然后用 Git 来进行版本控制:

~> pass find Coding
Search Terms: Coding
└── Code
    └── Coding
        └── jysperm.gpg

~> pass insert Code/Coding/jysperm

~> pass show Code/Coding/jysperm
DzizKKVIy22aHQwm

~> pass git pull --rebase
remote: Counting objects: 11, done.
remote: Total 11 (delta 1), reused 1 (delta 1), pack-reused 10
Unpacking objects: 100% (11/11), done.
From github.com:jysperm/passwords
   5026f34..e94a70f  master     -> origin/master
First, rewinding head to replay your work on top of it...
Fast-forwarded master to e94a70f8b42af5e1c13dd69246b156bbcb24a94c.

这样一来你甚至可以把密码托管在 GitHub 上:https://github.com/jysperm/passwords

KeyBase 和身份证明

再向大家介绍一个有趣的社区 —— Keybase,它就好像是 GitHub 之于 GPG 社区一样。提供了一个你的 GPG 身份的主页,上面有你的公钥、关联的 GitHub 帐号、Twitter 帐号以及所拥有的网站,他人还可以在这个网页上直接用你的公钥发送经过 GPG 加密的信息。你可以将你的私钥以加密的方式存储在 Keybase(当然不推荐这样做),Keybase 提供了在浏览器中使用密钥对进行加密、解密、签名、验签的功能。

前面我们提到在 Keybase 上你可以关联你的社交帐号,不同于一般的网站的「第三方帐号关联」,Keybase 的用户们显然都对去中心化非常在乎,那么如何去证明一个社交帐号是属于这个 GPG 公钥的呢?在这个场景中我们需要进行两方面的证明,一方面是要用 GPG 公钥去进行一个签名,声明他拥有这个社交帐号:

另一方面是用这个社交帐号将这个签名发布出来,来声明他拥有这个 GPG 公钥:

这种交叉的证明将不同的数字身份联系到了一起,我觉得这是一个挺有趣的事情,于是我在 KeyBase 之外也自己创建了一个 GPG 主页,并在上面列出了一些和其他数字身份的交叉证明,例如邮件、V2EX 帐号等。我还注册了一个我的 GPG 公钥后八位的域名来指向这个页面:http://E466CF1E.pub

端到端加密

我们再来转向这篇文章的第二个话题「端到端加密」,下图中分别展示了在无加密、SSL 加密和端到端加密的场景下,从 A 到 B、中间经过服务器的一次通讯的过程:

在没有加密的情况下,消息从 A 到服务器、再到 B 的全程都没有加密。这也意味着数据经过的链路上的任何一个节点(例如运营商的路由器)都可以查看和修改消息的内容,这种情况下的通讯安全是完全没有保证的。

在经过 SSL 加密的情况下,A 和 B 会分别在收发消息前通过 CA 签署的证书去认证服务器的身份,并协商一个用于加密数据的密钥。在从 A 到服务器,或从服务器到 B 的过程中,SSL 会保证数据不被窃听和篡改,但消息在服务器上则是以未加密的形态存在的,服务器可以查看和修改消息的内容,进行一些内容上的审查。

在端到端加密的情况下,消息在从 A 发出之前,就会利用我们前面介绍过的公钥加密技术,使用 B 的公钥进行加密,中间以加密的形式经过服务器和其他路由节点,直到 B 收到消息后,才使用自己的私钥进行解密。这种情况下的服务器并不能查看和修改消息,仅仅作为一个渠道来转发消息。

我们当然可以简单地使用 GPG 加密我们在第三方即时通讯软件上的聊天内容,就像下面这样:

但实际上例如 Tox、Line、WhatsApp、iMessage 等 IM 软件,都是默认提供了端到端加密的特性的,我们下面以 iMessage 为例去介绍一个 IM 软件是如何完成端到端加密通讯的。

iMessage 会在每台设备上生成一个 RSA 密钥对用于对数据进行加密,以及一个 ECDSA 密钥对用作签名(它出于安全性和性能的考虑使用了不同的密钥对,但其实是可以用同一个密钥对的)。这些密钥对中的公钥会被上传到 Apple IDS(Identity Services),然后其他用户会从 IDS 中取得你的所有公钥(每个设备一个公钥)。在 iMessage 中发出的所有文字消息都会使用自己的 ECDSA 私钥进行签名,使用对方的每个设备的 RSA 公钥加密一份,通过 APNs 发送给对方。对于多媒体消息,为了减少加密带来的开销,以及加密多份的流量开销,会使用一个临时密钥加密一次,通过 iCloud 进行传输,然后通过前面提到的方式发送临时密钥。苹果的很多应用都使用类似的方式进行端到端加密,包括 iCloud、Facetime、Keychain 等。

但在这个架构中,Apple IDS 依然是一个中心化的单点,它控制了全部的公钥交换过程,而且不允许用户干预。这就意味着 Apple 依然可以在 IDS 上进行中间人攻击,这也印证了我们在一开始提到的,公钥的交换是一个无法绕开的问题。在 GPG 中,用户需要繁琐地完全手动地去建立信任关系,换取了最高的去中心化程度;而在 iMessage 中 IDS 代劳了公钥交换的工作,方便了用户,但也引入了安全风险。

同时群聊也是一个比较难以解决的问题,在 Telegram 中群聊是无法开启端到端加密模式的,在 iMessage 中群聊也不总是可以使用端到端加密。这是因为就像前面提到的多设备的情况一样,在群聊的情况下我们必须用每个人的公钥来加密数据,这样数据在发送端就会膨胀许多倍(而不能发送端只发送一份,由服务器转发),具体的带宽开销会取决于群聊中的人数:

保管密钥

前面我们提到,在密码学账户中,你拥有一个账户的唯一凭证就是你的密钥对,一旦遗失,那么你便没有办法再去控制这个账户;或者一旦泄漏,其他人便拥有和你一样的控制这个账户的能力,无法重置,因此对密钥的保管显得尤为重要。

「备份」是具有两面性的 —— 一方面会让密钥更不容易丢失,但也让密钥变得更加容易泄漏。于是我就有个有趣的想法:能否做到将一个密钥分为若干「片段」保存,仅当拥有其中大部分片段的的时候才能够还原出密钥,但丢失了小部分片段又不影响还原呢?比如将密钥分为 5 份,仅当拥有其中任意三份的情况下可以还原出密钥。于是我找到了一个叫「Shamir’s Secret Sharing」的算法来做到这一点:

~> ssss-split -t 3 -n 5
Generating shares using a (3,5) scheme with dynamic security level.
Enter the secret, at most 128 ASCII characters: my secret root password
Using a 184 bit security level.
1-1c41ef496eccfbeba439714085df8437236298da8dd824
2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
4-468de7d6eb36674c9cf008c8e8fc8c566537ad6301eb9e
5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0

~> ssss-combine -t 3
Enter 3 shares separated by newlines:
Share [1/3]: 3-fa1c3a9c6df8af0779c36de6c33f6e36e989d0e0b91309
Share [2/3]: 5-4756974923c0dce0a55f4774d09ca7a4865f64f56a4ee0
Share [3/3]: 2-fbc74a03a50e14ab406c225afb5f45c40ae11976d2b665
Resulting secret: my secret root password

但将密钥作为一个文件,尤其是未加密的文件存储在电脑上仍然还是相当不安全的,因为你的电脑上安装了太多乱七八糟的软件了,目前大多数桌面操作系统其实都没有很好的权限控制 —— 几乎所有软件都可以随意地读取你所有的文件。因此 存储在硬盘上的文件是早晚要泄漏的,我们应该把密钥存储到一个无法被读取的地方,这就是我们下面要介绍的 TPM 芯片。

作为一个芯片来讲,外界必须通过已经被硬件定义好的协议去操作它,而对于 TPM 来讲,它在硬件的设计上就不允许你从芯片中取出私钥,你只能将私钥存进去,或者在 TPM 上生成密钥对。之后和私钥有关的所有运算,包括解密和签名都是在 TPM 芯片上进行的,整个过程中密钥都不会离开 TPM 芯片,即使作为硬件的 TPM 芯片被盗,他人也无法复制芯片中的私钥。

TPM 其实存在与很多笔记本和手机中,iPhone 的存储芯片和指纹识别都是依赖于 TPM 工作的。我目前在使用是的一款叫 Yubikey 的 USB TPM 芯片,它支持 GPG SmartCard 的标准,可以将 GPG 的密钥存储在其中。

小结

  • GPG 可以在互联网上,以数学为基础创造一个无法被伪造的身份,并以此身份签名信息、接收加密信息。
  • GPG 使用去中心化的信任模型,需要自行通过多种渠道来交换公钥,因此不会受制于单一的权威机构。
  • GPG 提供了身份管理和相互进行「信任签名」的机制来简化密钥的交换过程。
  • GPG 是一个开放的标准(兼容很多软件和硬件),有着活跃的社区,提供了相对易用的工具来进行公钥加密、解密、签名、验签。
  • 基于公钥加密并签名的端到端加密是从理论上保证通讯安全的唯一方法,但在此之前你需要通过某种方式来交换公钥。
  • 如果私钥丢失就只能改头换面、重新做人了。

参考来源

BlockChain 与 Ethereum 介绍

这篇文章由我 3 月末在 LeanCloud 进行的技术分享整理而来,假定读者已有基本的密码学知识且对 Bitcoin 的实现有初步的了解。

Blockchain 也叫区块链,可以认为它是 HashTree(散列树)的一种,也正因如此它有着一些和 HashTree 相同的性质:

图片来自 http://happypeter.github.io/bitcoin_basics/book/017_merkle_tree.html

即在一个树状结构中,每个末端节点都有一个散列值,而非末端节点的散列值则是由其所有直接子节点的散列值散列而来,因此每个节点都直接或间接地包含了其所有子节点的信息。进而,只要任意一个末端节点的散列值变化,其所有父节点的散列值都会发生变化,根节点也必定变化。

我可以举一个有关 HashTree 的应用:「100% 准备金证明」,它属于「零知识证明(Zero-knowledge proofs)」的这一类问题。我们可以考虑这样一个场景,Bitcion 的持有者为了进行交易,需要将 Bitcoin 寄存在交易所,理论上交易所可以将这笔钱(所有用户寄存的账户余额)挪作它用,这是用户们不希望看到的,而交易所也希望自证清白:交易所首先公布一个自己所持有的 Bitcoin 地址,供大家确认交易所确实持有这么多 Bitcoin 作为准备金,但如何证明这笔钱确实大于所有用户余额的总和呢?换句话说,如何在不公布每个用户的余额(会泄露用户的隐私)的情况下,让每个用户都认可自己的余额被包含在了总的准备金中呢?

图片来自 http://blog.bifubao.com/2014/03/16/proof-of-reserves

我们可以构造一个 HashTree,所有的末端节点都代表一个用户,包含了用户余额(Σ)和用户标识(如邮箱地址)的散列(h),而父节点包含了其子节点的余额总和(sum)和所有子节点信息的散列(hash)。对于每一个用户而言,只需向其展示他自己的末端节点和兄弟节点、其所有父节点和父节点的兄弟节点即可,因为这个用户可以通过逐步追溯父节点的方式,确认自己的余额被包含在了父节点中,最后进而包含在了根节点中。

这样一来,向每个用户展示的信息只有其自己的信息和一些经过聚合的信息,每个用户都可以在不获知其他用余额的情况下确认自己的余额被包含在了根节点中。上图中有一个小错误,he4df9d12 的节点不应该是一个代表用户的末端节点,而应该是一个经过聚合的信息节点(这个节点可以包含一个有 3333 余额的用户,和一个 0 余额的虚构用户)来避免泄漏某个用户的隐私信息。

接下来我们来看一下 Git,其实 Git 是一个非常典型的 Blockchain 应用:

图片来自 http://gitbook.liuhui998.com/1_2.html (GPL v2)

在 Git 中,无论是文件(Blob)、索引(Tree)还是提交(Commit),都有一个由其内容决定的 Hash,如果两个对象有着一样的内容,则有着一样的 Hash。在 Git 中,整个仓库的历史就是一条 Blockchain,每个 Commit 相当于一个 Block,Commit 中包含了前一个 Commit 的 Hash 以及此次修改相关的对象的 Hash,Commit 本身的 Hash 由其内容和这些元信息来决定。

Git 借助 Blockchain 为仓库来确定了一个唯一的历史 ———— 如果一个 Commit 被修改了,在其之后的所有的 Commit 的 Hash 都会改变。当然,因为 Git 只是一个版本控制工具,所以并没有阻止你去修改历史(毕竟还可以 rebase 然后 push --force),但这种修改会被所有协作者察觉到。

另一个 Blockchain 的经典应用就是 Bitcoin 了,也正是 Bitcoin 将 Blockchain 这个词传播开来(而这个概念其实是一直都有的):

图片来自 https://commons.wikimedia.org/wiki/File:Bitcoin_Block_Data.png(CC-BY-SA-3.0)

在 Bitcoin 中,每个 Block(块)包含了一系列 Transaction(交易)和上个 Block 的 Hash,而整个 Blockchain 则构成了一个去中心化的唯一账本。因为每十分钟才会产生一个新的 Block,而 Block 一经产生就会永远留在 Blockchain 上,所以 Blockchain 将交易发生的顺序固定了下来,维护了交易发生的先后顺序,进而确定一个账户是否有足够的余额发起一笔交易。

Bitcoin

这个分享的第一个部分是简单地回顾一下 Bitcoin.

Bitcoin 中 Block 的产生是通过「工作量证明」来实现的,即所有参与「挖矿」的「矿工」都要进行一种与计算力相关的、具有随机性质的散列计算,直到算出一个满足特定条件的随机数,才能获得发布一个 Block 的权利。

在设定上,每个矿工总是会去信任「最长的链」,在已知的、满足规则的最长的链的基础上去计算下一个 Block,否则你的计算力就会被白白浪费掉 —— 因为其他矿工也总是认可最长的链,而如果你不在最长的链的基础上开始工作,那么就是在和其他所有矿工的计算力对抗。

Bitcoin 被设计成每 10 分钟生成一个新的 Block, 这个时间是由大家共同通过观察过去几个 Block 的间隔时间,去调整下个 Block 的生成条件的难度去实现的。当过去几个 Block 的生成速度高于预期时,大家就会认为下一个 Block 的生成应该具有更高的难度。

正常来说,每一个 Bitcoin 节点都需要存储完整的 Blockchain 数据才能去确认一笔交易是否合法 —— 交易的发起者是否拥有足够的余额发起这笔交易。但现在完整的 blockchain 已有 66G,而且还在以每天 0.1G 左右的速度增长。如果要求 Bitcoin 的每个用户都存储完整的区块链未免过于苛刻,因此 Bitcoin 拥有一个「简化确认(SPV, Simplified payment verification)」的机制,所谓的「轻量级客户端」可以选择不存储完整的区块链,而是附着到一个或几个完整节点上,只存储所有 Block 的元信息(Hash、包含交易的 Hash、工作量证明),然后验证每个块的工作量证明,每当需要验证交易时便向完整节点查询这个交易所在的 Block,然后获取这个 Block 中必要的信息(Block 中的交易也是以 HashTree 的方式存储的),以便校验这笔交易是否包含在 Blockchain 中。

图片来自 https://github.com/ethereum/wiki/wiki/White-Paper

  • Blockchain ↔ 账本 ↔ 状态变更日志
  • Transaction ↔ 交易 ↔ 一次状态变更
  • Block ↔ 对于当前状态的一次「共识」

其实我们可以将 Bitcoin 的 Blockchain 想像成一个「状态机」,整个 Blockchain 是一个有状态的「账本」,其中存储着每一笔交易记录,根据这些交易记录可以推算出整个账本在任一时间的「状态」—— 即 Bitcoin 网络中每个账户有多少余额。每个 Transaction 就是一次对状态的变更,而每个 Block 是整个 Bitcoin 网络的矿工对当前状态的一个「共识」,因为 Bitcoin 每 10 分钟生成一个新的 Block,相当于每 10 分钟大家会对所有的账户的余额达成一次共识,而在这十分钟之间,账本的状态其实是一种「混沌」的状态。

Alt Coin

在比特币的基础上也衍生出来了很多其他密码学货币,通常被称为「山寨币(Alt Coin)」,通常这类货币有两种实现方案:

第一种是使用自己的、和 Bitcoin 相独立的网络,这样的好处是山寨币可以非常灵活地设计自己的协议和规则,但因为用户量很难达到和 Bitcoin 相当的数量级,所以对恶意攻击的防御能力将非常地弱。

第二种是去使用 Bitcoin 的网络实现「元协议」,在 Bitocin 的 Transaction 之上附带自定义的信息来实现自己的逻辑,这样的好处是可以利用 Bitcoin 的计算力规模去抵御攻击,但同时因为依附在 Bitcoin 网络上,并不是所有的矿工都会遵守山寨币的规则,因此无法防止不符合规则的 Block 进入 Blockchain,只能在客户端上过滤掉不符合规则的交易,也就无法利用前面提到的 Bitcoin 提供的简化确认的功能了。

对于这些山寨币而言,Bitcoin 可以提供一个具有大量矿工参与的、能够抵御住很大规模的恶意攻击的 Blockchain,同时 Bitcoin 的 Transaction 上也可以搭载自定义的数据,给山寨币的实现留出了一定空间。

Bitocin 也提供了一个 Bitcoin Script 用来实现更为复杂的 Transaction 但因为这并非是 Bitcoin 的核心功能,所以只能进行比较简单的运算,只能非常有限地读取 Blockchain 上的数据,同时因为缺少循环机制,很难编写通用的、图灵完备的逻辑。

Ethereum

图片来自 https://www.ethereum.org/assets (CC 3.0)

「Ethereum(以太坊)」是一个基于区块链的、去中心化的应用平台,它将 Bitcoin 的基础设施 —— 基于密码学的区块链技术构建为了一个通用的平台,并补齐了 Bitcoin 网络的一些缺失功能,以便开发者将自己的去中心化应用运行在 Blockchain 上。

在详细介绍 Ethereum 之前,我先介绍一下(我所认为的)去中心化网络的两大基础 —— 密码学和博弈。密码学自然不用多说,无非是通过公钥加密、数字签名、散列和摘要算法去从数学上保证安全性;而博弈是说在去中心化的网络中,任何人,包括希望恶意地希望攻击这个网络的人都可能参与,在设计去中心化网络时需要站在每一个参与者的角度去思考其利益关系,确保遵守规则时利益最大化、违反规则时会遭受损失或承担风险。

然而在数字世界中,发布一段数据是没有成本的,无所谓「利益」和「损失」,因此必须和实体世界建立某种联系,才能去定义「利益」。例如在 Bitocin 网络中,如果攻击者希望去人为地改变 Blcokchain 的走向,需要拥有比其他所有矿工更高的计算力,而在实体世界中,计算力是需要计算设备来提供的,而计算设备是需要从实体世界购买的 —— 甚至有时候即使有钱也没有足够的产能,因此参与 Bitcoin 网络的矿工越多,它抵御攻击的能力将会越强。

所以说在去中心化网络中,并不是所有问题都是被「技术」解决的,在技术所达不到的部分,必须通过利益、通过经济激励来解决。也是因为「经济激励」的需要,Ethereum 也有一个钱包体系(货币单位叫「Ether(以太)」),每个用户有一个钱包地址作为其唯一标识,在这一点上和 Bitcion 比较类似。

「Contract(合约)」是 Ethereum 所引入的最重要的概念。在 Bitcoin 中,所有的地址都是属于一个用户的 —— 当我们说「用户」的时候,其实是说一对公钥和私钥。但在 Ethereum 中,除了由一个密钥对所拥有的地址之外,还有一种由「代码」拥有的地址,即 Contract. Contract 由用户发布,其本质是一段代码,在发布之后便无法修改,Contract 像普通账户一样也有一个钱包地址,每当这个地址收到交易时,所关联的代码便会被执行,这些代码:

  • 能且只能以区块链作为输入和输出,因此计算是可重复的 —— 实际上计算的结果并不需要被存储到区块链,因为随时可以重新进行计算。
  • 可以调用其他 Contract 中的函数(其他 Contract 的代码和数据同样存在于区块链上)。
  • 执行过程中可以创建新的交易(操纵自己的钱包余额),这些交易可能会去执行其他的 Contract.

首先举一个「多人共同持有的钱包」的例子,在 Ethereum 的官方客户端中便有一个创建多人钱包的功能:

如图,通过这个功能可以创建出一个与其他 2 个人共同拥有的钱包地址,每个人每天最多使用其中的 100 Ether,如果超过了这个限制,则必须经过另外一个人的同意。

这个功能实际上会创建出一个 Contract,而上述逻辑是通过 Contract 中的代码来描述的。当你希望从这个共有钱包中支出款项时,你需要向这个共有钱包发一个消息(交易即消息,交易金额可以为零,仅携带数据),然后共有钱包中的代码会被执行,若这个支出请求符合上述逻辑,则发起真正的支出交易,否则这个支出请求会被驳回(没有真正地支出款项)。

另外一个例子是「对冲合约」,一直都有人吐槽 Bitcoin 作为数字货币其币值(和法定货币的汇率)不稳定,经常出现一天之间币值涨一倍或跌一倍的情况,但如果借助 Contract 实现一个对冲合约便可一定程度上解决这个问题。

我们将希望保持币值不变的人称为「风险规避者」,将另外一个愿意承担币值波动的风险并从中盈利的人称为「风险承担者」,于是他们便可以约定一个金额(例如 1000 CNY)和一个时间窗口(例如一个月),并创建一个 Contract 执行下列逻辑:

  • 风险规避者将价值 1000 CNY 的 Ether 发送到 Contract 的钱包地址,风险承担者也将价值 1000 CNY(或更多)的 Ether 发送到 Contract 来应约(如无人应约,风险规避者可取回自己的 Ether)。
  • 一个月后,风险规避者可以从 Contract 取回当时价值 1000 CNY 的 Ether,而无论 Ether 和 CNY 之间的汇率如何,余下的 Ether 由风险承担者取回。

如 Ether 价值上涨,风险承担者获利,若 Ether 价值下降,风险承担者亏损,但风险规避者总是不亏不赚。当然,风险规避者和风险承担者可以事先商定一个风险规避者需要支付的「保费」,亦可商定风险承担者需要提供几倍于 1000 CNY 的担保(倍率越高能够承担的风险越大)。

上面的例子中其实还存在一个不是很好解决的问题,即如何去确定 Ether 和法定货币之间的汇率,在前面我们提到过,Contract 只能访问区块链上的数据,而法定货币是一个存在于实体世界而非密码学世界的数据,我们需要通过某种机制将这类「来自非密码学世界的数据」引入到区块链中。

我们可以设计另外一个 Contract 来指定这样的逻辑,来从实体世界中征集 Ether 和法定货币之间的汇率,在每个时间窗口(如一小时)中:

  • 所有人可以向 Contract 缴纳保证金并提供一个汇率。
  • 在时间窗口结束时,Contract 计算所有人提供的汇率的平均值(按照保证金加权)并公布。
  • 并将收集到的保证金分配(按照保证金加权)最接近平均值的 25% 的人。

对于任何一个参与者,因为不知道其他人的出价,所以提交一个真实的汇率有更大的可能性获得奖励,而提交一个很离谱的汇率将会有很大的机率失去保证金。

当然这个规则其中有几个漏洞,比如如果一个人有非常多的保证金,那么他就可以将平均值拉到一个比真实汇率更高或更低的价格的同时拿到奖励,并且使其他一些提供了准确汇率的人失去保证金。但其实在实体世界中也是一样的,如果你有非常多的钱同样可以抬高或打压一种商品的价格,只不过相比于实体世界,电子货币的体量还很小,并不需要太多钱就可以做到;但其实这样恶意地抬高或打压汇率也是有非常大的风险的,因为你不敢肯定自己缴纳的保证金是足够多的,一旦失败将会失去所有的保证金。

另外一个漏洞就是「所有人可以向 Contract 缴纳保证金并提供一个汇率」这个步骤是通过创建交易来实现的,而所有的交易会被写到 Blockchain 上,因此你提交的汇率其实是对其他人可见的,进一步给恶意的攻击者创造了机会,接下来我会通过一个「产生随机数」的例子来介绍如何规避这个问题。

前面我们提到了 Contract 可以读取 Blockchain 上的数据,但 Blockchain 上的数据都是确定的,如果我们要实现一个类似于赌博的应用,该从哪里获得一个随机数呢?

可以想到的一个随机数来源就是下一个 Block 的 Hash,在大多数情况下,这种程度的随机性足够了。但其实矿工是可以在一定程度上操控这个随机数的,假设一个矿工参与了某个赌博,且赌博的收益大于挖出一个块的收益,那么如果这个矿工挖出了一个将会使自己输掉赌博的块,那么显然这个矿工会选择不去公布这个新的块,这一点在单个矿工的计算力越强的情况下越明显。

因此我们需要引入一个类似征集汇率的机制来征集随机数种子,然后在每个时间窗口结束时使用这些种子来计算出一个随机数。但就像征集汇率一样,因为参与者是通过创建交易来实现提交汇率的,因此在一个时间窗口之间,每个人提交的随机数对其他人都是可见的,因此一个已经参与了某项赌博的人可以精心挑选一个随机数种子来使其他人已提交的种子加上新的种子所产生的随机数刚好符合他的期望。

所以我们有必要将征集种子的窗口分为两部分,来取得一个任何人都无法预测和干预的随机数:

  • 阶段一:所有人可以向 Contract 缴纳保证金并提供「一个随机选定的种子的散列值」。
  • 阶段二:参与阶段一的人向 Contract 提供未被散列的种子。
  • 阶段二结束:Contract 将所有合法的种子散列,生成一组随机数并公布;退回阶段二中提供了正确的种子的人的保证金。

在第一阶段你只知道其他人提交的种子的散列值,而不知道实际的种子,因此无法去精心构造一个种子来干预结果;而在第二阶段中,所有人只是在确认第一阶段提交的种子,而不能提交新的,也无法阻止其他人提交种子。

前面我们提到 Bitcoin Script 是没有提供循环、递归、跳转之类的能力的,也许 Bitcoin 是出于控制一段 Bitcoin Script 执行时间的考虑,因为根据图灵的「停机定理」,由图灵完备的编程语言所编写的程序,无法总是仅从静态分析的角度判断其是否会在有限的步骤后结束,这样依赖恶意的攻击者便可以构造一个会引起死循环的 Transaction 来干扰矿工的正常工作。

而 Ethereum 则再次通过「经济激励」绕过了这个问题,Contract 以 opcode(操作码)的形式运行在一个叫 EVM(Ethereum Virtual Machine)的虚拟机上,EVM 是一个自带「计费」的虚拟机,在 EVM 的标准中,根据操作所需要的内存和 CPU 时间,定义了每一种 opcode 所消耗的 Gas,这是一种由 Ether 购得的计算资源。前面提到当一笔交易的目标是 Contract 时,Contract 的代码会被执行,交易的发起者需要为 Contract 执行过程中消耗的 Gas 付费,同时声明一个「愿意支付的最大的 Gas 数量」,如果 Gas 中途耗尽,Contract 的执行将会停止。

然后我们再重新讨论一下「共识间隔」的问题,前面提到 Bitcoin 每 10 分钟出现一个新的 Block,即整个网络每 10 分钟达成一个「共识」,所以通常的 Bitcoin 交易要等上十几分钟才会被确认,在计算力不是很高的早期,可能要等待一个小时(6 个 Block),大家才会认为这笔交易是可靠的。

显然更短的共识时间对用户而言会有更好的体验,为什么 Bitcoin 不缩短出块时间呢?这是因为更快的共识间隔会一定程度上增加「中心化矿池」的优势。所谓「矿池」就是指比特币矿工聚在一起挖矿,矿工无条件地听从矿池的指令,最后和矿池来约定收益分成,显然 Bitcoin 作为一个去中心化系统,并不希望这种中心化的矿池有额外的优势。

当一个矿工 A 挖到一个新的块的时候,他会将这个 Block 广播出去,其他人一旦收到了这个消息,就会立刻基于这个新的块开始工作。而其他人在「A 挖到新的块」和「收到 A 广播的消息」之间这段时间之间的计算实际上是被浪费掉了的,而中心化矿池中的其他矿工则不会有这个问题,因为他们可以更快地得到新产生的块的信息,立刻在新的块的基础上开始工作。

这个广播的时间可能需要十几秒,对于 10 分钟来讲这点时间并不是十分重要,但如果去缩短共识间隔,中心化矿池的优势将会越来越明显。但 Ethereum 通过引入「叔块(Uncle Block)」的概念解决了这个问题,将共识间隔减少到了 15 秒钟,在支付确认速度上较 Bitcoin 有了很大的提升。

在 Bitcoin 的 Blockchain 中,一个 Block 只能有一个父块,也只能有一个子块。但在 Ethereum 中,一个新产生的块可以有一个父块和若干个叔块。回到上面的例子,如果在 A 挖到新的块但其他人尚未收到广播的时间中,如果有人挖出了一个新的块,但因为广播较晚没有被大家接受,那么这个块有可能成为下个块的「叔块」—— 这个块所代表的工作量证明会被认为是下一个块的一部分(即这个人挖出下一个块的难度降低了),叔块也仅仅提供工作量证明,其中所包含的交易是无效的。这样一来便补偿了较晚收到广播的客户端在低出块间隔情况下的劣势,具体来讲,直接的叔块提供 50% 的工作量证明、二代叔块提供 25% 的工作量证明以此类推,最多会承认最多五代的叔块。

图片来自 https://blog.ethereum.org/2014/07/11/toward-a-12-second-block-time

尚未解决的问题

接下来这个部分我向大家介绍一下 Ethereum 目前尚未解决的几个问题。

首先就是 Ethereum 目前达成共识的方式依然和 Bitcoin 一样是通过 POW(工作量证明)来担保的,只有完成了特定工作量的节点才能够参与 Block 生成的工作,工作量证明的问题就在于会浪费大量的计算力去保证网络的安全性,虽然者也是基于我们前面提到的「经济激励」思想,但其实是可以改进的。Ehtereum 认为更好的方式是用 POS(所有权证明)去代替工作量证明,这样可以极大地提高这个网络的效率 —— 不需要再去进行无意义的计算了。

既然 Ether 本身就是有价值的,那么为什么不用它本身来进行经济激励呢?所谓 POS 就是说大家用所拥有的 Ether 去做担保,即每一个希望参与 Block 生成(传统意义上的挖矿)的节点(被称为验证人)都需要向系统(这里说的系统是指在协议上做规定,所有节点都认为这笔保证金被「冻结」了)缴纳一笔保证金,然后大家用自己的保证金来对可能成为下一个 Block 的 Block 下注(所谓「可能」的一个重要前提就是这个 Block 必须是符合协议规定的),如果这个块真的成为下一个 Block,那么所有下注的节点将会得到奖励,否则保证金将会被罚没。

这个模式其实和 POW 非常类似,在 POW 中,矿工用自己的计算力来「下注」,而且如果一旦有一个链更长,就有必要切换到这个链上继续挖矿 —— 因为参与的人越多的链越有可能成为正确的链,最终大家达成一个共识。而在 POS 中,大家使用自己的保证金下注,大家同样倾向于选择已经被很多其他人下注的块(如果它是合法的话),最后达成一个共识。

POS 势必会增加整个网络的吞吐量 —— 大家不再需要通过进行大量无意义的计算来达成共识了,每个节点的运算量将趋近于执行 Contract 中代码和进行数据验证的计算量。

当然 POS 之所以目前还未被采用,是因为还存在一些尚未解决的问题,其中之一就是和 POW 一样的 51% 攻击问题,在 POW 中集中全网 51% 的计算力是有一定物理限制的 —— 因为计算力需要计算设备来提供;而相比之下在 POS 中收集全网 51% 的 Ether 则相比之下容易一些 —— 只要你有足够的钱。POS 天然地比 POW 更非复杂,要实现上述的工作逻辑,需要处理例如维护有效的验证人列表、保证金的冻结、罚没和返还、提议区块和投注区块、防止验证人之间的结盟攻击、网络分区之后的恢复等等。

另外一个话题是「分片」,无论是 Bitcoin 还是 Ethereum, 目前都是在同一个 Blockchain 上完成所有的交易确认,这极大地限制了一个分布式网络的计算能力 —— 每个节点都需要接收、存储、验算每一笔交易,整个网络的处理能力其实等于一个节点的处理能力。

因此 Ethereum 希望在未来引入一个「分片」的机制,来将整个网络分为若干个部分,之间独立地进行交易验证。但分片之间会通过指针的结构去引用其他分片的数据、通过异步调用的方式去影响其他分片,所以整个网络在用户看来依然是一体的,只不过整个网络的处理能力将会有非常强的可拓展性。目前分片相关的实现还在比较早期的开发阶段,我找到的资料有限,所以就不过多介绍了。

Contract

这一部分我将会给大家展示一些实际的、可以工作的 Contract 的代码。Contract 可以由很多种不同范式的语言来编写,最终它们都会被编译成 opcode 在 EVM 上执行,今天我们选择以 Solidity 这个类 JavaScript 的语言为例,它是目前维护得最好的一个 EVM 语言。

contract Test {
  uint storedData; // State variable

  struct Voter { // Struct
    uint weight;
    bool voted;
    address delegate;
    uint vote;
  }

  event HighestBidIncreased(address bidder, uint amount); // Event

  function func() { // Function
    if (msg.sender.balance < 10 finney) {
        msg.sender.send(10 finney);
    }

    sha256("...");

    address nameServer = 0x72ba7d8e73fe8eb666ea66babc8116a41bfb10e2;
    nameServer.delegatecall("isAvailable", "MyName");
    nameServer.call("register", "MyName");
  }
}

以上是一些核心语法的展示,在 Solidity 中你可以声明状态变量(uint storedData;),这些变量的值会永远被保存在 Blockchain 上;可以用 struct 去声明复杂的数据结构;也可以定义函数,这些函数会在收到交易时被执行,交易的发起者可以选择执行哪些函数,所以一个 Contract 可以提供若干个函数,在函数内可以进行逻辑判断、循环、修改变量的值。

语言内置一些很方便的小功能,例如常见的密码学算法(sha256)、单位换算(10 finney)、直接书写钱包地址(0x72ba7d8e73fe8eb666ea66babc8116a41bfb10e2)等。msg 是内置的全局变量,可以从上面读取与此次交易有关的信息,如发起者、金额等。Contract 可以通过两种方式去调用其他 Contract 的代码,delegatecall 相当于将另一个 Contract 的代码放到当前上下文执行,就好像引入了一个库函数;而 call 则是发起一笔新的交易去触发另一个 Contract 的逻辑。

那么 Contract 如何从 blockchain 上读取和写入数据呢?这个复杂的工作被抽象为了「状态变量」,上面的 storedData 就是一个状态变量。其实 Contract 执行过程中对状态变量的修改并不会保存到 blockchain 中,因为 Contract 执行的都是确定性的计算 —— Contract 的执行由交易触发,执行过程中只能读取 blockchain 上已有的数据,因此只要我们知道历史上每一笔与这个 Contract 有关的交易,我们就可以随时推算出一个 Contract 在某个时间点上各个状态变量的值。

接下来我来展示一个真正可用的 Contract —— 在 Ethereum 网络的基础上发行一个属于自己的代币:

contract Coin {
    // The keyword "public" makes those variables
    // readable from outside.
    address public minter;
    mapping (address => uint) public balances;

    // Events allow light clients to react on
    // changes efficiently.
    event Sent(address from, address to, uint amount);

    // This is the constructor whose code is
    // run only when the contract is created.
    function Coin() {
        minter = msg.sender;
    }
    function mint(address receiver, uint amount) {
        if (msg.sender != minter) return;
        balances[receiver] += amount;
    }
    function send(address receiver, uint amount) {
        if (balances[msg.sender] < amount) return;
        balances[msg.sender] -= amount;
        balances[receiver] += amount;
        Sent(msg.sender, receiver, amount);
    }
}

代码来自 http://solidity.readthedocs.io/en/latest/introduction-to-smart-contracts.html#subcurrency-example (MIT)

这个名为 Coin 的 Contract 声明了两个状态变量,minter 用来存储这个代币的创建者,在构造函数(function Coin())中将第一笔用于创建 Contract 的交易的发起者赋值给了这个变量;还声明了一个钱包地址到数字的映射表 balances, 用来表示每个持有该代币的地址的余额。

mint 这个函数中先判断了交易的发起者是否是该代币的创建者,如果是的话就按照函数参数,将一定数量的代币加给指定的地址。send 这个函数可以被所有人调用,会从交易发起者的地址扣除一定量的余额(如果有足够的余额的话),加到目标地址上,相当于一个转账的功能。

我们还声明了一个名为 Sent 的事件,事件其实并不会有什么实际的作用,只是便于调试时打印关键性事件,未来也会方便轻量级客户端的实现(轻量级客户端只接受事件而不实际执行 Contract)。

Ethereum 提供了一个叫 Mix 的 IDE 来调试这段代码,在 Mix 的右侧你可以虚构一些 Block 和账户来测试你的 Contract,也可以看到在执行过程中每个状态变量的值的变化情况。值得一提的是 Contract 一旦发布便无法修改,此后的运行完全靠其他人的交易触发,对于每天都在写 Bug 的程序员来讲这一点会令人非常不爽,但是 Contract 的语义本来就是「合约」,一旦你发布了一个合约自然不能去修改它,否则谁还会信任你的合约呢。当然你可以在 Contract 中给自己一些特权(就像前面的 Coin 中那样,只有创建者可以凭空创造代币),但这些代码也存在于 Blockchain 上,其他使用者也是知晓的。

编写完成后我们就可以用 Ethereum 钱包将这个 Contract 发布到网络上了:

发布之后你可以关注这个 Contract,随时点到 Contract 的详情界面:

在左侧可以看到两个状态变量的值,minter 的值就是我自己的地址,balances 因为是一个映射表,所以你可以输入一个地址去查询它的余额。在右侧你可以向这个 Contract 发起新的交易,有一个下拉菜单可以选择 send 或是 mint 函数,你可以填写传递给 Contract 的参数。因为在这里我们发交易的目的是传递一个消息,而非传递 Ether,所以我们不必设置交易的金额。

接下来我要介绍一个很有趣的 Contract,这个 Contract 实现了一个「庞氏骗局」的效果,即你可以向这个 Contract 支付 1 Ether 来加入这个游戏,之后每加入三个人,就会按顺序支付给先加入的人 3 Ether:

contract Pyramid {
    struct Participant {
        address etherAddress;
    }

    Participant[] public participants;

    uint public payoutIdx = 0;

    // events make it easier to interface with the contract
    event NewParticipant(uint indexed idx);

    // fallback function - simple transactions trigger this
    function() {
        enter();
    }

    function enter() {
        if (msg.value < 1 ether) {
            msg.sender.send(msg.value);
            return;
        }

        if (msg.value > 1 ether) {
            msg.sender.send(msg.value - 1 ether);
        }

        uint idx = participants.length;
        participants.length += 1;
        participants[idx].etherAddress = msg.sender;

        NewParticipant(idx);

        // for every three new participants we can
        // pay out to an earlier participant
        if (idx != 0 && idx % 3 == 0) {
            // payout is triple, minus 10 % fee
            uint amount = 3 ether;
            participants[payoutIdx].etherAddress.send(amount);
            payoutIdx += 1;
        }
    }

    function getNumberOfParticipants() constant returns (uint n) {
        return participants.length;
    }
}

代码简化自 https://ethereumpyramid.com/contract.html

代码还算简单,这个 Contract 声明了一个 participants 数组用来按顺序存储所有参与者的钱包地址,还是声明了一个 payoutIdx 用来记录前多少名参与者已经得到了 3 Ether 的返还。enter 实现了这个 Contract 的主要功能,首先是一些参数检查,保证每个参与者都支付了 1 Ether, 然后将新的参与者放到 participants 数组的末尾,最后如果当前参与者的序号刚好是 3 的倍数,就发送 3 Ether 给第 payoutIdx 个参与者,并将 payoutIdx 指向下一个参与者。

参考链接

HashTree:

Bitcoin:

Halting Problem:

Ethereum:

Ethereum Network:

Next of Ethereum:

Contract:

Contract IDE:

笔记:散列算法的使用场景

大家都知道散列算法,如 MD5, SHA, 但是对其具体特性恐怕都很模糊。说不准哪些用法是可靠的,哪些用法是不可靠的,只是通过加 salt, 或者反复散列的方式提高可靠性。本文将精确地讨论它们在各种使用方法下的可靠性,本文不讨论原理,只讨论使用,以下部分资料来自网络,感谢 wxy 帮忙检验文中的论断。

MD5 和 SHA 系列算法都属于同一类——我还没给这类算法找到一个足够贴切的名字。首先在大的分类上,它们都是散列算法。
散列是怎么个定义呢?典型的散列算法可以是任何一个:具有无限的定义域,且具有有限的值域的函数。甚至,宽松的广义散列算法可以是任何一个(数学意义上的)函数,因为函数本身的概念就是将一个或多个值映射到一个唯一的值。

从具体特征上来说,它们(的目标)都是足够安全的信息摘要算法。究竟何谓安全?
MD5 和 SHA 系列函数所追求的安全,在于下面两个方面。

  • 单向性
  • 抗冲突性

所谓单向性,就是指明文 M, 经过散列后的 hash(M). 从 hash(M) 无法推算出 M. 这是大部分摘要算法都具有的特征,因为大多数情况下,被摘要的信息长度要大于散列值,因为缺少信息,且值域明显小于定义域,即一个散列值会对应多个(无限个)原文,所以天然地就无法从散列值反向计算出原文。MD5 和 SHA 系列函数在单向性方面目前都还没有被发现明显的漏洞。

但是以上讨论的只是理论上的单向性,实际使用中,攻击者可以通过穷举,即暴力破解的方式推算出可能的原文。这种情况适用于已知信息原文定义域且范围较小的情况。例如如果直接对用户的密码进行散列,因为密码大多在十位字母左右,攻击者可以以很低的成本计算所有密码组合的散列值,以得到可能的信息原文。

从散列算法的角度,应对暴力破解攻击没有明显有效的手段,但也可以通过『提高计算成本』和『减少散列值长度』的方式提升单向性。

提高计算成本即通过将算法设计得更为复杂,增加更多次计算,来提高对单个信息进行散列的时间。对于正常单次散列来讲,即使增加十倍的计算时间,仍然是可以接受的。但当攻击者进行暴力破解时,同样需要原来十倍的计算时间,这个成本对攻击者来说可能无法接受。除此之外,还可以改造算法,使其只能运行于 CPU 上,无法使用显卡或专用芯片进行计算,以提高暴力破解的计算成本。
但似乎这种方式并没有被业界接受,SHA 系列函数中的新成员均减少而不是提高了计算成本。

减少散列值长度,即通过减少散列值的长度来使得多个(大量)信息原文映射到同一个散列值,使攻击者无法分辨究竟哪个才是真正的原文。
例如将散列值减少到 8 bit, 这样密码组合中 1/256 的密码都会映射到同一个散列值,根本无法分别哪个才是真正的密码。
这种方式显然很扯淡,因为这种方式会明显降低下面要提到的抗冲突性。

实际使用中,我们可以通过提高定义域范围的方式,来增强单向性。同样是散列用户密码的例子,我们可以将原来的 hash(M) 改为 hash(hash(M)). 因为 hash 的值域范围通常要比密码(约 10 位字母,即约 60 bit)大, 如 MD5 的值域是 128 bit, SHA-1 的值域是 160 bit. 因此我们通过第一次散列将第二次散列的定义域提高到了 2-4 倍,一定程度上提高了攻击者暴力破解的成本。

但是,攻击者会将 hash(hash(x)) 视为一个独立的散列函数 hash2(x), 除了正常地增加了一倍的计算时间,并没有受到我们增加作用域的影响。因此,这时我们需要引入 salt(佐料,干扰), 将散列算法改为 hash(hash(x + salt)), salt 需要与散列值一同储存。

在已知 salt 的情况下,对攻击者其实没有任何影响,因为这个函数依旧可以转换为 hash2(x + salt), 当然,有些攻击者会通过 Rainbow Table(彩虹表) 的方式进行协作和缓存,加 salt 会使他们无法使用 Rainbow Table.

Rainbow Table, 即事先对预定范围的数据进行散列,储存散列结果。然后通过数据库或者分布式技术(小型 Rainbow Table 就不需要了), 来优化从散列值到原文的『反向』查询。相似的技术还有『字典』,即收集大家常用的原文(密码,或其他短语), 代替穷举,以提高暴力破解的效率。

而在这个场景中,将 hash(hash(x + salt)) 更换为 hash(hash(x) + salt) 会获得更好的效果。因为前一种情况,攻击者可以将密码和 salt 视为一个整体来使用 Rainbow Table (虽然在 Rainbow Table 中很可能查不到这些信息); 后者则不能。因为后者是一个散列值加一个 salt, 长度已经远远超出了 Rainbow Table 的范围。当然,单纯加长 salt 也可以实现 hash(hash(x) + salt) 的效果。

在攻击者不知道 salt 的情况下,有两种选择。
一是将 hash2(x) 改为 hash2(x, salt), 这种情况适用攻击者知道 salt 的长度或范围的情况,因为这个函数有两个参数,因此破解成本与 x 或 salt 的长度呈指数函数,只要 salt 足够长,那么可以认为攻击者即使暴力破解也无能为力。
二是将第二个 hash 的输入视为一个散列值,换言之就是进行两次爆破,这种方式的计算成本相比于前一种会更高,因为暴力破解的成本同原文长度也是呈指数关系的。

所以,在未知 salt 的情况下,可以防御所有暴力破解,除非攻击者拥有极其惊人的计算力。
举个例子,如果密码为 10 位的字母,salt 为 3 位的字母,暴力破解需要相当于 Bitcoin 全网计算力的约 60 天时间。

虽然我们还拥有更强大的变种,例如:

hash(x, salt[]) = hash(hash(x + salt[1]) + hash(x + salt[2]) + ...)

但是我们认为,使用 hash(hash(x) + salt) 和足够长的 salt(大致相当于散列值的长度), 已经足够安全。

接下来,那么如何生成 salt 呢?是否有必要为每条数据(还是前面的例子,每个用户)使用单独的 salt 呢。通过前面的讨论我们看到,要保证单向性,对 salt 进行保密十分必要。如果你能够保证 salt 的绝对安全的话,那么是否使用单独的 salt 其实无关紧要。不要担心使用相同的 salt 会让攻击者找到某种规律而计算出 salt(当然前提是 salt 足够长), 因为 MD5, SHA 系列函数保证了单向性,攻击者无法从散列值推测出原文的任何信息。

至于 salt 的取值,没有什么特别的要求,基于保密的考虑,通常要使用随机生成的字符串,然后就是足够长(大约等于散列值的长度).

但我们认为仍有必要为每条数据使用单独的 salt, 这是基于下面两点考虑。
一是虽然暴力破解需要惊人的计算力,但是如果只需破解一个散列值,就可以获知所有数据的 salt, 这个破解也是值得的,也许攻击者就能够提供这么多的计算力也说不定,虽然如果你使用足够长的 salt 的话,这种可能性极小。
二是也许你不能保证 salt 的绝对安全,当你的 salt 泄漏后,每条数据使用不同的 salt 将会为攻击者制造最后一道障碍。

如果你所有的数据都使用同样的 salt, 那么攻击者在拿到数据后,只需进行一次暴力破解,即可破解出所有的数据(如果都命中了的话), 但如果你为每条数据使用不同的 salt, 那么攻击者将不得不为每条数据单独运行一次暴力破解,因为每条数据相当于在使用不同的散列函数,因为 salt 是不同的。

综上,我们认为网站的用户系统使用下面的散列即可保证安全性:

hash(hash(passwd) + salt)

其中 salt 是随机生成的,长度等于散列值长度的字符串。hash 可以是 MD5 或 SHA 系列函数。


我们接着来谈抗冲突性,所谓抗冲突性即从计算上不可能找到两个有同样散列值的原文。抗冲突性分为抗强冲突性,和抗弱冲突性。
抗强冲突性,即给定一个散列值,无法找到另一个具有同样散列值的信息原文。
抗弱冲突性,即无法找到两个具有同样散列值的信息原文。

加上单向性,这三条特性是呈阶梯状的,满足『抗弱冲突性』就一定满足『抗强冲突性』也就一定满足『单向性』同时也就满足『散列映射具有随机性和均匀性』。MD5 和 SHA 系列函数在设计上都满足这三条特征,但目前已经被发现了存在某些漏洞。

抗冲突性的主要应用场景就是为信息原文进行摘要,鉴别两段信息原文是否相同。
而攻击者的目标就是,对信息原文进行修改,然后在信息原文后(或者修改信息原文)添加给定的数据段,使其能够生成与之前相同的散列值,实现伪造数据原文。

在这种场景下攻击者是否也能够进行暴力破解呢?很难,因为在这种情况下,攻击者需要不断更换附加在信息原文后的数据,以获得和之前相同的散列值,在不理想的情况下,需要尝试所有的散列值,这个计算力被认为是无法接受的。但通过算法的一些漏洞,可以降低这个暴力破解的成本。

抗冲突性是检验散列算法设计是否优秀的重要指标,很多散列算法被淘汰都是因为抗冲突性存在漏洞。

目前 MD5 已在 2005 年被中国数学家王小云发现有抗强冲突性的漏洞,给定一个散列值,可以在几分钟内用普通计算机找到一个碰撞,即具有相同散列值的信息原文。

SHA-0 被发现漏洞可以将寻找碰撞的难度从 2^80 次暴力破解降低到 2^39 次,SHA-1 被发现漏洞可以将寻找碰撞的难度从 2^80 次降低到 2^63 次,SHA-2 系列函数还未发现漏洞。

因此目前使用 MD5 进行信息摘要并不安全,攻击者可以轻易地伪造一段散列值相同,但内容不同的原文,虽然攻击者还不能够自由地修改原文。
而 SHA-1 和 SHA-2 系列函数目前来讲是足够安全的。

精子生于 1995 年,英文 ID jysperm.

订阅推送

通过 Telegram Channel 订阅我的博客日志、产品和项目的动态:

王子亭的博客 @ Telegram


通过邮件订阅订阅我的博客日志、产品和项目的动态(历史邮件):

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-ND  授权发布。最后生成于 2023-12-20.