Hashcash 或“工作量证明”

• 下载源代码 - 33.3 KB

引言

“Hashcash 是一种工作量证明系统，用于限制电子邮件垃圾邮件和拒绝服务攻击，最近因其在比特币（和其他加密货币）中用作挖矿算法的一部分而闻名。Hashcash 由 Adam Back 于 1997 年 3 月提出。”（维基百科）您可以阅读 Adam Back 的论文 此处。

其思想是，一封邮件（如电子邮件）通过以某种方式对某些 string 进行哈希处理来“证明”其合法性，从而证明计算机在某个特定算法上花费了时间/精力——特别是，计算一个 SHA-1 哈希，使得哈希的前 20 位为 0。由于通过暴力破解找到这样一个合格的哈希需要一定的计算时间，因此会给发件人带来少量的成本，这对于发送大量电子邮件的垃圾邮件发送者来说被认为是不可取的。“Hashcash 可以被视为‘一种白名单提示，有助于 Hashcash 用户避免因基于内容的和基于黑名单的反垃圾邮件设备而丢失电子邮件’。”（hashcash.org）

如今，这种“工作量证明”概念主要用作比特币挖矿功能。“它们‘作为对区块链演进的投票，并验证区块链交易日志’。”或者换句话说：“比特币使用 Hashcash 来防止区块链被恶意篡改，它通过为篡改设置成本，矿工必须希望通过合作奖励来收回……在比特币中，Hashcash 问题的难度会根据近期解决方案时间的历史而随时间变化，平均目标是在十分钟内找到解决方案。”（比特币之书）

其他实现

hashcash.org 链接到 SourceForge 上的一个 C# 实现。但是，在我测试该算法时，存在一些错误。一个小的错误是日期戳

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

哎呀，那是年-月-日格式！

一个更严重的错误是，生成的标头经常无法通过验证

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

结果发现，生成的哈希值通常只有前 16 或 18 位设置为 0，我认为这是由于在完成字节时，base64 值的计算方式存在算法问题。

算法

Hashcash 标头包含以下字段（维基百科）

• 版本：(当前为 1)
• 位数：前导零的位数
• 时间戳：日期/时间戳（时间是可选的）
• 资源：正在传输的数据 string，例如 IP 地址、电子邮件地址或其他数据
• 扩展：版本 1 中忽略
• 随机种子：base-64 编码的随机字符集
• 计数器：base-64 编码的二进制计数器，范围在 0 到 2²⁰ (1,048,576) 之间

如果您要编写代码，会遇到几个问题，并且算法存在一个缺陷。

1. 随机种子应该有多少个字符？
2. 编码二进制计数器时，应该是大端还是小端？在将整数（4 字节）转换为字节数组时，是否应排除前导零（大端）或尾随零（小端）？
3. 一个更重要的问题是，许多情况在计数器最大值为 2²⁰ 时没有解决方案。我曾见过需要计数器值为 8,069,934 (0x7B232E) 才能找到解决方案。

我的修订算法是

• 随机种子是 8 个字符。
• 计数器从 int.MinValue() 开始，并递增直到找到解决方案。
• 计数器从代表整数的 4 个小端字节转换为 base64。
• 如果计数器达到 int.MaxValue()，则会抛出异常。

实现

我当然不建议以高效的方式编写此算法，但话说回来，既然它旨在消耗 CPU 周期，我对此并不特别担心。

验证

让我们首先看看标头是如何验证的

public class HashCash
{
  public static bool Verify(string header)
  {
    // We assume the bits that are going to be 0 are going to be between 10 and 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，但以上是我选择的实现。

我们可以像这样验证维基百科页面上的标头示例

var check = HashCash.Verify("1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi");
Console.WriteLine(check ? "Passed Verification" : "Failed Verification");

这通过了。因为它通过了，我们可以一定程度上相信消息是真实的。可以进行进一步的验证来提高消息的有效性

• 用于计算哈希值的零比特数。
• 时间戳在可接受的范围内。
• 随机种子是唯一的（未重复使用）。

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

初始化

几个构造函数提供了一些初始化标头的方法

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 ? "Passed Verification" : "Failed Verification");

  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("Verification failed.");
      }

      int ms = (int)((stop - start).TotalMilliseconds);
      Console.WriteLine(i + "-> Time: " + ms + "ms Iterations = " + hc.Iterations);
      totalTime += ms;
    }
    catch (HashCashException ex)
    {
      Console.WriteLine(ex.Message);
      break;
    }
  }

  Console.WriteLine("Average time: " + (int)(totalTime / iterations) + "ms");
}

示例输出（最后 19 次迭代）

计算一个可接受的哈希值平均需要超过一秒钟！

结论

我认为这真的很有趣——它有点像验证码的反面。Hashcash 验证发送者 *是* 一台机器（没有人能完成这项计算），但

1. 机器未被用于发送垃圾邮件或其他未经请求的消息。
2. 发送消息的机器正在对消息标头进行身份验证（这可以扩展到包括消息正文）。
3. 可以使用这种方法作为节流阀或调速器，以防止即使是合法的程序也压垮服务器。
4. 这种“工作量证明”算法已被用于帮助防止拒绝服务攻击。

NHashCash（我之前发布的 sourceforge 链接）也包含在内，但其测试已被注释掉。