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

sjhstone

发布于 2018-03-13 15:28:04

1.6K0

发布于 2018-03-13 15:28:04

下载 HashCash.zip - 33.3 KB

介绍

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 编码的二进制计数器

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

随机种子应该长多少个字符？
编码二进制计数器时，它应遵循大端编码还是小端编码？在将整数（4字节整型）转换为字节数组时，应该去掉头部的零（大端模式下）还是末尾的零（小端模式下）？
一个更重要的问题是：在很多情况下，对于最大可以为 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），但是：

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

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

其他

登录后参与评论

0 条评论

热度