如何证明自己不群发

        2015 春节即(yi)将(jing)来(dao)临(lai),大家都在互发短信贺新年,这时如何证明自己的信息不是群发的呢?因为我之前研究过比特币,我立刻就想到了它所用到的“工作量证明”算法。这个算法正好是用来解决这个问题的。算法大概是这样的:要寻找一个字符串,使得信息与这个字符串拼接起来的数据的某个密码学哈希值末尾有多个零。其实算法的核心原理就是利用密码学哈希的随机分布,让计算机不停工作,直到某个公认的小概率时间发生。

这看起来很抽象,下面我以这次发拜年信息为例子来说明这个算法:

  • 首先要确定要发送的信息:这回我偷了个小懒,直接用名字的汉语拼音加上 2015happynewyear 就是要发送的信息了
  • 然后规定一下加入的随机的字符串的格式:我选择了小写字母和数字作为随机字符串
  • 之后需要选择一个合适的密码学哈希算法:我选择了 SHA1 算法
  • 最后需要选择难度值:这次我选择的难度是要求哈希值末尾有 8 个零

例如我要证明 zhangboyang-2015happynewyear 不是我群发的信息,我就需要计算出消息+各种随机字符串的 SHA1 哈希值,直到遇到某个随机字符串所对应的哈希值末尾有 8 个零。
算法过程如下:

SHA1(zhangboyang-2015happynewyear/aaaaaa)
     =A9A558C5725D44C9C1A0CCD39C028DBCAF31A15C
SHA1(zhangboyang-2015happynewyear/aaaaab)
     =8F30E6253FF48D8CDD8211C778E621525D5B2A78
SHA1(zhangboyang-2015happynewyear/aaaaac)
     =6CCDC2C571D7CD9DC4078C8823DABC56A029C7BD
...more...

直到我枚举出的随机字符串为 oqkj1e,此时有

SHA1(zhangboyang-2015happynewyear/oqkj1e)
     =345EC337DADBDDBA0115669A7B7ECCF100000000

根据密码学哈希函数的特性,可以假设它产生出的哈希值是随机分布的,即可以假设产生的哈希值字符串最后 8 位十六进制数字是随机的。因此遇到 8 个数字全部是 0 的概率是 1/4294967296。此即说明算法枚举次数的期望是 4294967296。在我的计算机上,运行一次这样的算法平均消耗机时约 20 分钟。也就是说我写一条拜年信息需要约 20 分钟来计算出这个值,从而证明了我没有群发(因为要是群发的话每条消息都得花约 20 分钟,我承受不起)。

p.s. #1 要证明自己不是群发是 MHY 同学的要求 ^_^
p.s. #2 其实写一条信息平均需要的时间可以少于 20 分钟,因为我可以让它并行计算。(事实上我用了两台双核电脑来运行这个算法)
p.3. #3 羊年的第一个比特币区块大概是第 344064 号区块,它的 SHA256 哈希值前有 16 个零!

此条目发表在计算机技术分类目录。将固定链接加入收藏夹。

如何证明自己不群发》有2条回应

  1. 阿丸弘说:

    诶我要求过么?:)

  2. Kepler说:

    我收到你的祝福短信,没想到会这么复杂。。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注