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

引言

“哈希现金(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)

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

  1. 随机种子应该有多少个字符?
  2. 编码二进制计数器时,它应该以大字节序还是小字节序编码?在将整数(4字节)转换为字节数组时,应该排除前导零(大字节序)还是尾部的零(小字节序)?
  3. 更重要的问题是,很多情况下在最大值为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次迭代):

计算出一个可接受的散列值平均需要一秒以上!

结论

非常有趣的是——这与验证码的功能正好相反。Hashcash验证发件人一台机器(人类无法进行这样的计算),但是:

  1. 机器未被用于发送垃圾邮件或其他未经请求的信息。
  2. 发送消息的机器对消息头部(也可扩展为包含消息体)进行验证。
  3. 这样的方法可以用作节流器或调速器,以防止压垮服务器,即使是合法程序。
  4. 这种“工作量证明”算法已被用于防止拒绝服务攻击。

NHashCash(我之前发布的sourceforge链接)也包含在内,但对它的测试已被注释掉。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

让我们来看看 Hashcash 的思路:一封要证明其合法性的电子邮件需要附带一些对字符串的 hash 值来证明其耗费了一定的时间/资源运行了某个算法(Hashc...

43411
来自专栏区块链大本营

程序员们,快来找漏洞啊!找到就赏15ETH

在以太坊上递归检索动态数组或链接列表可能会造成很严重的安全问题,因为攻击者可能会增加它们的大小以使得智能合约出现异常。

1142
来自专栏追不上乌龟的兔子

使用Python标准库functools中的lru_cache实现缓存

很简单,也很容易理解,但是不难发现这个函数在计算斐波那契数列的时候事实上进行了很多重复计算,例如:

1904
来自专栏Crossin的编程教室

【每周一坑】校验文件哈希

先说个通知,给参与了码上行动的同学:又一期展示学习成果的编程擂台活动开始了,即是练手的好机会,又能得到助教的全程支持,还可以得积分赢奖金。赶紧来报名吧!从课程首...

36111
来自专栏WindCoder

Java设计模式学习笔记—建造者模式

文章最后“Java设计模式笔记示例代码整合”为本系列代码整合,所有代码均为个人手打并运行测试,不定期更新。本节内容位于其Builder包(package)中。

872
来自专栏IT可乐

深入理解计算机系统(5.1)------优化程序性能

  你能获得的对程序最大的加速比就是当你第一次让它工作起来的时候。   在讲解如何优化程序性能之前,我们首先要明确写程序最主要的目标就是使它在所有可能的情况下都...

24110
来自专栏醒者呆

以太坊挖矿源码:ethash算法

本文具体分析以太坊的共识算法之一:实现了POW的以太坊共识引擎ethash。 关键字:ethash,共识算法,pow,Dagger Hashimoto,...

1.4K6
来自专栏Python中文社区

多种方法爬取猫眼电影并分析(附代码)

摘要: 作为小白,爬虫可以说是入门python最快和最容易获得成就感的途径。因为初级爬虫的套路相对固定,常见的方法只有几种,比较好上手。选取网页结构较为简单的猫...

7853
来自专栏tkokof 的技术,小趣及杂念

iTween那些事儿(二)

  上次我们简单浏览了一番iTween的使用和原理,这次我们换个角度,转而看看iTween目前存在的一些缺陷以及一点点可能的改进之处,当然,这些所谓的缺陷或者改...

671
来自专栏月牙寂

[以太坊源代码分析]III. 挖矿和共识算法的奥秘

1.待挖掘区块需要组装 在Ethereum 代码中,名为miner的包(package)负责向外提供一个“挖矿”得到的新区块,其主要结构体的UML关系图如下...

4528

扫码关注云+社区

领取腾讯云代金券