前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >哈希现金(Hashcash)与“工作量证明”

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

作者头像
懂啵
发布2018-03-15 11:22:56
2.6K0
发布2018-03-15 11:22:56
举报
文章被收录于专栏:懂啵的蟒络空间

引言

“哈希现金(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链接,但是在我测试这个算法时出现了一些错误。首先是日期戳中的一个小错误:

代码语言:javascript
复制
string stampDate = date.ToString("yymmdd");

糟糕,这是年-分钟-天的格式!

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

代码语言:javascript
复制
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周期,所以我并不是特别担心这一点。

验证

首先看看头部如何验证:

代码语言:javascript
复制
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,但以上是我所选择的实现方式。

我们可以像这样验证维基百科上的头部示例:

代码语言:javascript
复制
var check = HashCash.Verify("1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi");
Console.WriteLine(check ? "Passed Verification" : "Failed Verification");

验证通过了,所以我们对信息的真实性有了一定程度的信任。还可以进一步验证以提高消息的有效性:

  • 计算散列的零的位数
  • 可接受范围内的时间戳
  • 随机种子是唯一的(不重复使用)

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

初始化

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

代码语言:javascript
复制
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();
}

如果没有随机种子,可通过以下方式计算:

代码语言:javascript
复制
public string GetRandomAlphaNumeric(int len = 8)
{
  var chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

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

在内部计算一些常用值:

代码语言:javascript
复制
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:

代码语言:javascript
复制
private bool AcceptableHeader(string header)
{
  byte[] hash = sha.ComputeHash(Encoding.UTF8.GetBytes(header));

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

计算头部

包括构造头部以及每次失败时递增计数器直到哈希头部通过位测试:

代码语言:javascript
复制
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次“工作量证明”:

代码语言:javascript
复制
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 条评论
热度
最新
推荐阅读
目录
  • 引言
    • 其他实现方法
    • 算法
    • 实现
      • 验证
        • 初始化
          • 测试头部
            • 计算头部
            • 测试
            • 结论
            相关产品与服务
            验证码
            腾讯云新一代行为验证码(Captcha),基于十道安全栅栏, 为网页、App、小程序开发者打造立体、全面的人机验证。最大程度保护注册登录、活动秒杀、点赞发帖、数据保护等各大场景下业务安全的同时,提供更精细化的用户体验。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档