哈希现金（Hashcash）与“工作量证明”

懂啵

发布于 2018-03-15 11:22:56

2.5K0

发布于 2018-03-15 11:22:56

下载 HashCash.zip - 33.3 KB

引言

“哈希现金（Hashcash）是一种用于防止垃圾电子邮件和拒绝服务攻击的工作量证明系统，最近以其在比特币（以及其他加密货币）挖矿算法中的应用而闻名，由Adam Back于1997年3月提出。”（维基百科）你可以点击这里阅读Adam Back的论文。

一条消息（例如一封电子邮件）通过包含一些字符串的散列值，证明计算机花费了一些时间或能量在特定的算法上，以“证明”它是合法的消息，具体方法是计算一个SHA-1散列使得散列值的前20位为0。因为需要一定的计算时间来通过暴力计算找到这样一个合格的散列值，所以发送者需要花费一些成本来计算散列值，这对于发送大量电子邮件的垃圾邮件发送者来说是不现实的。Hashcash可以被视为“帮助Hashcash用户避免因基于内容和基于黑名单的反垃圾邮件装置导致电子邮件丢失的白名单。”（hashcash.org）

这种“工作量证明”的概念现在主要用于比特币挖矿功能，“充当区块链更新的投票机制，并验证区块链交易日志。” 或者换句话说：“比特币采用Hashcash，通过收取一笔用于补偿矿工所希望得到的合作激励作为更新费用，来实现防止区块链被恶意篡改的安全性……在比特币中，Hashcash问题的困难性随着时间的推移而变化，取决于最近解决时间的记录，目标为平均10分钟完成一次。“ （The Book of Bitcoin）

其他实现方法

hashcash.org上有一个用C#实现的SourceForge链接，但是在我测试这个算法时出现了一些错误。首先是日期戳中的一个小错误：

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

糟糕，这是年-分钟-天的格式！

一个更重要的错误是，结果得到的头部经常无法验证：

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

结果表明，生成的散列值常常只有前16或18位被设置为0，这应该是在计算base64值中完成八位字节时的算法问题导致的结果。

算法

hashcash的头部具有以下字段（维基百科）：

版本：(目前为1）
位：前导位为0的数量
时间戳：一个日期/时间戳（时间是可选的）
资源：正在传输的数据字符串，例如IP地址、电子邮件地址或其他数据
扩展：在版本1中被忽略
随机种子：base-64编码的随机字符集
计数器：0到220之间的base-64编码二进制计数器，（1048576）

如果你直接按照这个进行编程，会出现如下一些疑问和算法缺陷。

随机种子应该有多少个字符？
编码二进制计数器时，它应该以大字节序还是小字节序编码？在将整数（4字节）转换为字节数组时，应该排除前导零（大字节序）还是尾部的零（小字节序）？
更重要的问题是，很多情况下在最大值为220的计数器内无法得出结果。有的时候需要计数器值为8069934（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次迭代）：