了解与实现“工作量证明”的源头 Hashcash

介绍

Hashcash 是一种用于减少垃圾邮件和 DDoS(拒绝服务攻击)的工作量证明体系,最近因其在比特币(和其他加密货币)中被作为挖矿算法的重要组成部分而闻名。这种体系由 Adam Back 于 1997 年 3 月提出。 ——维基百科

你可以在这里阅读 Adam Back 的论文。

让我们来看看 Hashcash 的思路:一封要证明其合法性的电子邮件需要附带一些对字符串的 hash 值来证明其耗费了一定的时间/资源运行了某个算法(Hashcash 中是需要运行 SHA-1,去计算出一个前 20 位均为 0 的 hash 值)。

由于通过暴力方式进行计算来找到符合特定条件的 hash 值会耗费一定的计算时间,垃圾邮件的制造者在发送大量邮件时可能会因此知难而退。

hashcash.org 上的说法,每条 hashcash 可以被认为是“帮助 hashcash 用户在滤除邮件时避免由内容过滤或是黑名单机制误杀错过重要邮件的的‘白名单通行证’。”

如今“工作量证明机制”这一概念最主要的应用,是比特币的挖矿功能。所谓挖矿,就是“在区块链演进过程中充当投票角色并验证交易日志”。而《比特币之书》(The Book of Bitcoin)是这样说的:“Hashcash 使得任何对区块链的更改都需要付出一定的成本,而只有各个节点协商一致认可的更改才能为矿工挣得能够抵偿更改成本的报酬。因此,比特币通过采用 Hashcash 机制能保护其区块链免受恶意篡改的影响。在比特币的设计中,Hashcash 所要计算的问题的复杂度随着最近的求解时间的变化而变化,一般会使得平均求解时间控制在 10 分钟左右。”

其他实现

hashcash.org 上有一个链接,指向了 SourceForge 上的一种 C# 实现。但是,在我测试这个算法时,发现了一些错误。其中,日期戳这里有一个小错误:

string stampDate = date.ToString("yymmdd");

注意了,这个时间格式是:年—分钟—日!(译者注:对 C# 中的日期对象的 ToString 方法而言,yyMMdd 才代表年月日)

一个更显著的问题是,计算出的头部信息常常不能通过校验:

SHA1CryptoServiceProvider sha = new SHA1CryptoServiceProvider();
byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(header));

最后发现,计算出的 hash 常常只有前 16 或 18 位被置 0(译者注:而标准要求前 20 位均被置 0)。我认为这是一个与进行 base64 编码时,对字节进行补齐处理的算法的问题。

算法

Hashcash 头具有以下字段(来自 维基百科):

  • 版本号:(目前为 1)
  • 零位数:hash 开头一共有多少个连续的 0 位
  • 时间戳:日期/时间戳(时间部分是可选的)
  • 资源:需要传输的数据字符串,例如IP地址,电子邮件地址或其他数据
  • 扩展:在版本 1 中被忽略
  • 随机种子:经过 base-64 编码的随机字符集
  • 计数器:0 和 2^{20}(1,048,576)之间的某个经过 base-64 编码的二进制计数器

如果你要写代码实现这一机制,需要考虑到一些问题和算法设计中的一个缺陷。

  1. 随机种子应该长多少个字符?
  2. 编码二进制计数器时,它应遵循大端编码还是小端编码?在将整数(4字节整型)转换为字节数组时,应该去掉头部的零(大端模式下)还是末尾的零(小端模式下)?
  3. 一个更重要的问题是:在很多情况下,对于最大可以为 2^{20} 的计数器值来说,并不一定存在一个对应解。我见到过有一次计数器值为 8,069,934(0x7B232E)时,这一实现仍在要求求解。

我修改后的算法是:

  • 随机种子是8个字符
  • 计数器从int.MinValue()开始递增,直到求出解为止
  • 计数器值中 4 个小端编码的代表这一整数的字节会被进行 base64 编码
  • 如果计数器的值增加到了int.MaxValue(),则抛出异常

履行

我当然不会说这个算法的实现非常高效。不过,再次申明,由于这个机制本身就是要消耗一些 CPU 时间的,我对于性能问题并不是特别担心。

验证

首先看看头部如何验证:

public class HashCash
{
  public static bool Verify(string header)
  {
    // 我们假设要被置 0 的几位所代表的值在 10 到 99 之间
    int zbits = int.Parse(header.Substring(2, 2));
    int bytesToCheck = zbits / 8;
    int remainderBitsToCheck = zbits % 8;
    byte[] zArray = Enumerable.Repeat((byte)0x00, bytesToCheck).ToArray();
    byte remainderMask = (byte)(0xFF << (8 - remainderBitsToCheck));
    SHA1CryptoServiceProvider sha = new SHA1CryptoServiceProvider();
    byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(header));

    return hash.Take(bytesToCheck).SequenceEqual(zArray) && ((hash[bytesToCheck] & remainderMask) == 0);
  }
}

完成这些位操作的方式不止一种,例如使用 BitArray(https://msdn.microsoft.com/en-us/library/system.collections.bitarray(v=vs.110%29.aspx),不过我的以上实现没有用到它。

我们可以像这样对维基百科上举出的头验证例子进行实验:

var check = HashCash.Verify("1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi");
Console.WriteLine(check ? "验证通过" : "验证失败");

运行结果是验证通过。看到算法给出验证通过的结果,我们可以对消息的真实性给出一定的信任。要进一步增强对消息有效性的验证,我们可以进行如下验证:

  • 在计算 hash 时用到了几个 0 位
  • 时间戳是否在预期的范围内
  • 随机种子是否独特(没有被重复使用)

所有这些验证都有助于将消息列入白名单。

初始化

一些构造函数提供了一些初始化 hash 头的方法:

public HashCash(string resource, int zbits = 20)
{
  rand = GetRandomAlphaNumeric();
  this.msgDate = DateTime.Now;
  this.resource = resource;
  this.zbits = zbits;
  Initialize();
}

public HashCash(DateTime msgDate, string resource, int zbits = 20)
{
  rand = GetRandomAlphaNumeric();
  this.msgDate = msgDate;
  this.resource = resource;
  this.zbits = zbits;
  Initialize();
}

public HashCash(DateTime msgDate, string resource, string rand, int zbits = 20)
{
  this.rand = rand;
  this.msgDate = msgDate;
  this.resource = resource;
  this.zbits = zbits;
  Initialize();
}

如果你不提供随机种子,那么就应该为你生成一个:

public string GetRandomAlphaNumeric(int len = 8)
{
  var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

  return new String(chars.Select(c => chars[rnd.Next(chars.Length)]).Take(len).ToArray());
}

在内部,一些计算过程中一直要被用到的一些值也会先被算出来:

private void Initialize()
{
  counter = 0;
  sha = new SHA1CryptoServiceProvider();
  bytesToCheck = zbits / 8;
  remainderBitsToCheck = zbits % 8;
  zArray = Enumerable.Repeat((byte)0x00, bytesToCheck).ToArray();
  remainderMask = (byte)(0xFF << (8 - remainderBitsToCheck));
}

测试头部生成

一旦我们构造了头部,我们就可以通过验证其前 n 位是否 0 来测试我们的实现:

private bool AcceptableHeader(string header)
{
  byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(header));

  return hash.Take(bytesToCheck).SequenceEqual(zArray) && ((hash[bytesToCheck] & remainderMask) == 0);
}

计算头部

这个步骤包括构造头部,以及对每次构造失败后,递增计数器值,直到哈希头部通过位测试:

public string Compute()
{
  string[] headerParts = new string[]
  {
    "1",
    zbits.ToString(),
    msgDate.ToString("yyMMddhhmmss"),
    resource,
    "",
    Convert.ToBase64String(Encoding.UTF8.GetBytes(rand)),
    Convert.ToBase64String(BitConverter.GetBytes(counter))
  };

  string ret = String.Join(":", headerParts);
  counter = int.MinValue;
  Iterations = 0;

  while (!AcceptableHeader(ret))
  {
    headerParts[COUNTER_IDX] = Convert.ToBase64String(BitConverter.GetBytes(counter));
    ret = String.Join(":", headerParts);

    // Failed 
    if (counter == int.MaxValue)
    {
      throw new HashCashException("Failed to find solution.");
    }

    ++counter;
    ++Iterations;
  }

  return ret;
}

测试

我整理了一个简单的测试,执行100次“工作证明”:

static void TestHashCash()
{
  var check = HashCash.Verify("1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi");
  Console.WriteLine(check ? "验证通过" : "验证失败");

  int totalTime = 0;

  for (int i = 0; i < iterations; i++)
  {
    try
    {
      HashCash hc = new HashCash("foo.bar@foobar.com");
      DateTime start = DateTime.Now;
      string header = hc.Compute();
      DateTime stop = DateTime.Now;
      bool ret = HashCash.Verify(header);

      if (!ret)
      {
        throw new HashCashException("验证失败");
      }

      int ms = (int)((stop - start).TotalMilliseconds);
      Console.WriteLine(i + "-> 时间:" + ms + "毫秒 循环数 = " + hc.Iterations);
      totalTime += ms;
    }
    catch (HashCashException ex)
    {
      Console.WriteLine(ex.Message);
      break;
    }
  }

  Console.WriteLine("平均时间:" + (int)(totalTime / iterations) + "毫秒");
}

输出示例(最近19次迭代):

平均而言,算出一个符合要求的 hash 平均需要一秒以上的时间!

结论

我觉得 Hashcash 非常有趣——它在某些方面与验证码机制差不多完全相反。Hashcash 验证发件人一台机器(没有人可以手算那么多 hash),但是:

  1. 这台机器不是被用来发垃圾邮件或是虚假消息的
  2. 发送消息的机器正在验证消息头(可以扩展到包含消息主体)
  3. 类似 Hashcash 的机制可以为非法程序上一道闸门,防止其压垮服务器。
  4. 这种“工作证明”算法已被用于防止拒绝服务攻击。

NHashCash(我之前发布过的sourceforge链接)也包含在内,但测试代码都被注释掉了。

本文的版权归 sjhstone 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏斑斓

设计匠艺 | 对象的角色

若要获得良好的对象设计,就必须对职责进行合理的分配。每个对象承担的职责不能太多,也不能太少,恰如其分即可。职责分配如乐谱中对音符的组织,高明的音乐家总是能让不同...

2475
来自专栏懂啵的蟒络空间

哈希现金(Hashcash)与“工作量证明”

“哈希现金(Hashcash)是一种用于防止垃圾电子邮件和拒绝服务攻击的工作量证明系统,最近以其在比特币(以及其他加密货币)挖矿算法中的应用而闻名,由Adam ...

44210
来自专栏码匠的流水账

聊聊partition的方式

一般来说,数据库的繁忙体现在:不同用户需要访问数据集中的不同部分,这种情况下,我们把数据的各个部分存放在不同的服务器/节点中,每个服务器/节点负责自身数据的读取...

541
来自专栏LET

CPU Cache简介

真空中光速为299,792,458米/秒,目前,Intel的i7频率可以达到4GHz,简单换算一下,可以得出结论:光(电流)在一个Cycle内移动的距离约为0....

602
来自专栏撸码那些事

是什么影响了数据库索引选型?

上一篇文章我们介绍了索引背后的数据结构,这篇文章我们来介绍影响索引数据结构选型的因素——存储器存取。

492
来自专栏华章科技

巧用MapReduce+HDFS,海量数据去重的五大策略

重复数据删除往往是指消除冗余子文件。不同于压缩,重复数据删除对于数据本身并没有改变,只是消除了相同的数据占用的存储容量。重复数据删除在减少存储、降低网络带宽方面...

753
来自专栏LET

glTF简介

27910
来自专栏Golang语言社区

从Baa开发中总结Go语言性能渐进优化

在Go生态已经有很多WEB框架,但感觉没有一个符合我们的想法,我们想要一个简洁高效的核心框架,提供路由,context,中间件和依赖注入,而且拒绝使用正则和反射...

4538
来自专栏CDA数据分析师

入门 | 一小时向非程序员介绍 R 编程语言

来源 | 伯乐在线 我妹妹正在念大四,主修社会学。她刚刚签了下个学期一份不错的分析员工作,对方告诉她工作中要用到 R 编程语言。她让我在寒假时教教她,我欣然同意...

1846
来自专栏JAVA高级架构

策略模式(Strategy)

982

扫码关注云+社区