工作量证明之Hashcash算法，了解一下？

请输入图片描述
图片来源于网络

一、基础概念

Hashcash是一个工作量证明（proof-of-work）算法，可以用于垃圾邮件过滤，拒绝服务攻击（DDOS）等领域。比特币中挖矿算法的工作量证明机制也是基于Hashcash来实现的。

Hashcash由Adam Back于1997年首次提出，论文戳这里。

先来了解一下Hashcash算法的原理吧。
正如密码学中的数学问题——难于解答，易于校验，hashcash算法的设计灵感也是来源于此：要求用户计算一个中等难度但不难解决的功能，以便获得对资源的访问权限，从而防止轻率使用。

在垃圾邮件和DDOS中，攻击方几乎是没有代价的。垃圾邮件软件可以批量、高并发的发送邮件给目标地址；DDOS可以利用海量的肉鸡对目标主机进行网络请求从而使目标主机限于瘫痪。

Hashcash解决这些问题的手段是让攻击方付出一些计算资源的「代价」。首先，目标方会按照既定规则给出一道数学题，这道数学题的结果不可复用（每次请求需要重新计算）。为了得出结果，需要一些CPU的计算资源，然后把计算结果附在请求上提交给目标方，目标方可以非常轻易的验证结果是否正确。这道数学题的难度可以定义。

具体来说，hashcash是基于hash的，在通常情况下，使用的是sha算法。拿电子邮件举例，我要求所有发给我的电子邮件header中必须包含一个合法的「戳记」。这个戳记中包含着一个特定的比特值和我的电子邮件地址以及一个计数器等等一系列信息。比如一个戳记的比特值是20，那么我要求通过这个戳记生成的哈希值的前面20个比特位都是零。这样的戳记我认为是合法的。为了得到这个戳记，算法会不断的累加计数器进行hash碰撞，在进行了上百万次的计算后，终于得到了20个比特位的前导零。对于目前的主流电脑来说，百万次hash大概需要几秒钟时间。

我相信，如果你很有诚意发送一个邮件给我，应该不会在乎这几秒钟。但是，对于垃圾邮件软件和DDOS来说，每个请求的计算累加却是及其昂贵的，难以实现批量的、大规模的网络请求。

你看，让你每次作恶付出有限的一些成本，而当你需要批量作恶的时候，累加的高昂成本会使你望而却步。

来具体看看hashcash戳记是长这个样子的，通常包含七个域，每个域使用:分割。

1:bits:date:resource:ext:salt:suffix

七个域说明如下：

1. 版本号（版本 0 更简单，但是有一些局限性）。
2. 声明的比特值。如果戳记没有真正地使用声明的前导零比特进行散列，那么它就是非法的。
3. 生成戳记的日期（和时间）。可以认为当前时间之后的戳记以及那些在很久以前的戳记是非法的。
4. 戳记为哪个资源而生成。可能是一个电子邮件地址，但是也可能是一个 URI 或者其他命名的资源。
5. 特定应用程序可能需要的扩展。任何附加的数据都可以放置在这里，但是，在到目前为止的使用中， 这个域通常是空的。
6. 将该戳记与其他所有人为相同的资源在同一日期生成的戳记区别开来的随机因子（salt）。例如，两个不同的人 可以合情合理地在同一天向我的同一个地址发送电子邮件。他们不应该由于我使用了 double spend 数据库而无法 发送成功。但是，如果他们每个人都使用一个随机因子，那么完整戳记将是不同的。
7. 后缀是算法真正起作用的部分。假定给出了前 6 个域，为了生成一个通过期望数目的前导零 进行散列的的戳记，minter 必须尝试很多连续的后缀值。

eg.
# 20比特位hashcash，一个十六进制字符代表4个比特位
# 耗时10.5283429623秒，计算2230427次
1:20:181126:foo::+JBvhrpi:22089b

00000ba45b80599e9849a787798312dc7533c7ed

二、代码实现

这里是David Mertz, Ph.D.实现的Python版本的hashcash


import sys
from string import ascii_letters
from math import ceil, floor
from sha import sha
from random import choice
from time import strftime, localtime, time

ERR = sys.stderr            # Destination for error messages
DAYS = 60 * 60 * 24         # Seconds in a day
tries = [0]                 # Count hashes performed for benchmark

def mint(resource, bits=20, now=None, ext='', saltchars=8, stamp_seconds=False):
    # 挖掘一个新的hash，满足前导零为bits位
    # 
    # resource: 资源，在垃圾邮件过滤中，通常表示邮箱地址
    # bits: 比特位，默认20，表示hash前5为是零（十六进制每字符4比特位）
    # now: 日期
    # ext: 扩展字段，通常留空
    # saltchars: 盐的长度
    # stamp_seconds: now字段是否支持秒级别
    #
    ver = "1"
    now = now or time()
    if stamp_seconds: ts = strftime("%y%m%d%H%M%S", localtime(now))
    else:             ts = strftime("%y%m%d", localtime(now))
    challenge = "%s:"*6 % (ver, bits, ts, resource, ext, _salt(saltchars))
    return challenge + _mint(challenge, bits)

def _salt(l):
    # 返回一个l长度的随机字符串
    alphabet = ascii_letters + "+/="
    return ''.join([choice(alphabet) for _ in [None]*l])

def _mint(challenge, bits):
    # 部分hash碰撞
    counter = 0
    hex_digits = int(ceil(bits/4.))
    zeros = '0'*hex_digits
    while 1:
        digest = sha(challenge+hex(counter)[2:]).hexdigest()
        if digest[:hex_digits] == zeros:
            tries[0] = counter
            return hex(counter)[2:]
        counter += 1

def check(stamp, resource=None, bits=None,
                 check_expiration=None, ds_callback=None):

    # 校验stamp是否合法
    #
    # 如果指定了chack_expiration（应该用数字来表示），表示有效期
    # >>> from hashcash import DAYS
    # >>> check(stamp, check_expiration=28*DAYS)
    #
    if stamp.startswith('0:'):          # Version 0
        try:
            date, res, suffix = stamp[2:].split(':')
        except ValueError:
            ERR.write("Malformed version 0 hashcash stamp!\n")
            return False
        if resource is not None and resource != res:
            return False
        elif check_expiration is not None:
            good_until = strftime("%y%m%d%H%M%S", localtime(time()-check_expiration))
            if date < good_until:
                return False
        elif callable(ds_callback) and ds_callback(stamp):
            return False
        elif type(bits) is not int:
            return True
        else:
            hex_digits = int(floor(bits/4))
            return sha(stamp).hexdigest().startswith('0'*hex_digits)
    elif stamp.startswith('1:'):        # Version 1
        try:
            claim, date, res, ext, rand, counter = stamp[2:].split(':')
        except ValueError:
            ERR.write("Malformed version 1 hashcash stamp!\n")
            return False
        if resource is not None and resource != res:
            return False
        elif type(bits) is int and bits > int(claim):
            return False
        elif check_expiration is not None:
            good_until = strftime("%y%m%d%H%M%S", localtime(time()-check_expiration))
            if date < good_until:
                return False
        elif callable(ds_callback) and ds_callback(stamp):
            return False
        else:
            hex_digits = int(floor(int(claim)/4))
            return sha(stamp).hexdigest().startswith('0'*hex_digits)
    else:                               # Unknown ver or generalized hashcash
        ERR.write("Unknown hashcash version: Minimal authentication!\n")
        if type(bits) is not int:
            return True
        elif resource is not None and stamp.find(resource) < 0:
            return False
        else:
            hex_digits = int(floor(bits/4))
            return sha(stamp).hexdigest().startswith('0'*hex_digits)


    >>> from hashcash import mint, _mint
    >>> mint('foo', bits=16)
    '1:16:040922:foo::+ArSrtKd:164b3'
    >>> _mint('foo', bits=16)
    '9591'
    >>> from sha import sha
    >>> sha('foo9591').hexdigest()
    '0000de4c9b27cec9b20e2094785c1c58eaf23948'
    >>> sha('1:16:040922:foo::+ArSrtKd:164b3').hexdigest()
    '0000a9fe0c6db2efcbcab15157735e77c0877f34'

三、应用场景

Bitcoin

我们还需要一个类似于Adam Back提出的hashcash。在进行随机散列运算时，工作量证明机制引入了对某一个特定值的扫描工作，比方说 SHA-256 下，随机散列值以一个或多个 0 开始。那么随着 0 的数目的上升, 找到这个解所需要的工作量将呈指数增长，而对结果进行检验则仅需要一次随机散列运算。
我们在区块中补增一个随机数，这个随机数要使得该给定区块的随机散列值出现了所需的那么多个 0。我们通过反复尝试来找到这个随机数，直到找到为止，这样我们就构建了一个工作量证明机制。只要该 CPU 耗费的工作量能够满足该工作量证明机制，那么除非重新完成相当的工作量，该区块的信息就不可更改。由于之后的区块是链接在该区块之后的，所以想要更改该区块中的信息，就还需要重新完成之后所有区块的全部工作量。
—— 中本聪(Satoshi Nakamoto)《比特币:一种点对点的电子现金系统》

比特币使用类似hashcash算法来作为矿工的工作量证明，在hashcash的基础上，比特币使用了sha256算法，在最初的版本中要求32比特位的前导零，然后比特币网络会周期性的重置难度以应对矿工日益提升的硬件性能，目前的难度级别要求256位哈希72比特位的前导零。

比特币并没有完全照搬hashcash，相对于hashcash，比特币做了如下改进：

hashcash使用了sha1(160位)，而比特币使用了sha256(256位)。
为了提高安全性，Satoshi使hash运行了两次。
为了确保区块创建率不变（10分钟出块），周期性调整难度(前期32位零，目前72位零)。

四、参考链接

http://www.hashcash.org
https://en.wikipedia.org/wiki/Hashcash
http://www.gnosis.cx/download/gnosis/util/hashcash.py
https://www.ibm.com/developerworks/cn/linux/l-hashcash.html

版权声明

© 著作权归作者所有
允许自由转载，但请保持署名和原文链接。不允许商业用途、盈利行为及衍生盈利行为。