先来思考一个问题：如何写一个能消耗对方时间的程序？

消耗时间还不简单，休眠一下就可以了：

Sleep(1000)

这确实消耗了时间，但并没有消耗 CPU。如果对方开了变速齿轮，这瞬间就能完成。

不过要消耗 CPU 也不难，写一个大循环就可以了：

for i = 0 to 1000000000

end

但这和 Sleep 并无本质区别。对方究竟有没有运行，我们从何得知？

所以，我们需要一个返回结果 —— 只有完整运行才有正确答案。

result = 0

for i = 0 to 1000000000

	result = result + i

end

return result

通过返回结果，我们就能校验，对方是否完整运行了我们的程序。

---

不过上面这个问题，毕竟还是 too simple。小学生都知道，用数列公式就可以直接算出结果，根本不用花时间去跑循环。

有什么函数，是无法用公式推测的？也就是说，必须老老实实运行函数，才能得出结果。而找不到一种更快的算法，也能算出相同的结果。

显然「单向散列函数」就是。例如，一个经典的问题：

MD5(X) == X

就无法用公式来解决了。要找出答案，只能一个个试过去，需要大量的时间。

但对于验证者，是非常轻松的 —— 只需将收到的答案，计算一次就可判断对错。

Hashcash

当然，上面的那个例子太困难了，一时间根本找不到答案。但可以做一些改进，例如只要求结果前几位是 0 就可以：

Hash(X) == "0000......"

这样 0 的数量越少，满足条件的 X 就越容易找到。

同时，为了防止答案重复使用，还可以再增加一个盐值：

Hash(X, Salt) == "0000......"

盐可以由验证者提供，这样就可以充当一个「问题」。符合条件的 X，则可以当做问题的「答案」，提交给验证者鉴定。

---

这就是所谓的 PoW（Proof-of-Work），一种鉴定对方是否投入计算工作的机制。并且只需花费少量的资源，即可鉴定大量的工作。

使用散列函数实现的 PoW，就叫做 Hashcash。现实中比特币使用了类似的原理，它使用了 SHA-256 作为散列函数。有权威的密码学算法作为保障，因此只能暴力穷举，而无法使用投机取巧的方法获得结果，保障了挖矿工作的价值。

传统应用

当然，Hashcash 早不是新鲜事，很久以前就用在反垃圾邮件中。

例如，用户写完邮件时，客户端将「收件地址 + 邮件内容」作为 Salt，然后计算符合条件的答案：

Hash(X, Salt) == "000000..."

最后将找到的 X 附加在邮件中并发送。

服务端收到后，即可鉴定发送这封邮件，是否花费了计算工作。

对于正常用户来说，额外的几秒计算并不影响使用；但对于制造垃圾邮件的人，就大幅增加了成本。

传统的限制策略，大多通过 IP、账号，攻击者可以用大量的马甲和代理，来绕过这些限制；而使用了 PoW，就把瓶颈限制在硬件上 —— 计算有多快，操作才能多快。

Web 应用

同样，Hashcash 也能用于 Web。例如论坛，增加机器发帖的计算成本。

在发帖时，计算：

Hash(X, 帖子内容) == "000000..."

提交时，带上额外的参数 X。

后端即可判断，用户发这条帖子，是否付出了计算工作。

Web 改进

然而，网页不同于客户端。

例如写邮件的例子：

邮件写完后，客户端可以隐藏在后台自动计算，然后再发送。但网页就大不相同了。如果发帖时，网页卡上好几秒，将大幅降低用户体验。

因此，不能像邮件那样，拿「帖子内容」、「标题」等这些用户输入的内容来计算。而是选择一个始终固定的参数。

---

例如，可以参考传统验证码的方式：

# 后端 - 生成随机问题

ques = rand()

session["pow_ques"] = ques

echo(ques)

在页面初始化时，后端生成一个随机数，并下发到前端。

前端使用这个随机数作为盐值 —— 这样页面打开时，就可以开始计算了。

# 前端 - 挖矿

while Hash(X, ques) != "000000..."

	X = X + 1

end

我们选择一个适中的难度，例如 10 秒。通过多线程，还可以更快的完成计算任务，同时不影响用户体验。

正常情况下，用户发帖前已完成计算。提交时，将答案 X 带上。

如果提交时答案还未算出，则等待计算完成。。。（发帖太快，有灌水嫌疑）

# 前端 - 提交

wait X

submit(..., X)

# 后端 - 校验

if hash(X, session["pow_ques"]) == "000000..."

	ok

else

	fail

end

这样，一个「测试机器算力」的验证码实现了。

目前也有不少 hashcash 的实际应用。例如 WordPress 的 hashcash 插件。甚至还有第三方的验证服务 hashcash.io。

Web 性能

当然在 Web 中使用，性能也是一大问题。如果 10 秒的脚本计算，用本地程序只需 1 秒，那攻击者就可以使用本地版的外挂了。

好在如今有 asm.js，可接近原生性能，让用户的劳动不至于贬值；对于较老的浏览器，也可以使用 Flash 作后补。在上一篇文章 0x08 节 中已详细讲解。

如果算力实在不够，也可以使用后备方案 —— 传统图形验证码。

这样，高性能用户可享受更好的体验，低性能用户也能保障基本功能。

这也算是鼓励大家使用现代浏览器吧：）

Hashcash 缺陷

不过，语言上的性能差距还是有限的，外挂不会纠结于此，而是使用更强力的武器 —— GPU。

Hashcash 的本质就是跑 hash，这是 GPU 最擅长的。例如著名的 oclHashcat，和 CPU 完全不在一个数量级。

对抗硬件的并行计算，大致有如下方案和思路：

• 硬件瓶颈

• 移植难度

• CPU 算法

• 以暴制暴

• 自创加密

• 串行模式

前 3 个在上一篇文章 0x09 节 提到了，下面讨论一些不同的。

以暴制暴

如果我们也能在 Web 中调用显卡计算，那 GPU 版的外挂就毫无优势了。

不过，这个想法似乎有些遥远。尽管目前主流浏览器都支持 WebGL，但都只局限于渲染加速上，并未提供通用计算接口。

当然，也可以通过一些 hack 的方式，例如曾有人尝试用 WebGL 挖比特币，但效率并不高。

如果未来 WebCL 成为标准，或许还能考虑。

自创加密

不要自创加密算法 —— 这似乎是一条真理。

在账号安全里，这固然正确。但在对抗的场合下，就未必如此了。

经典的加密算法固然权威，但研究的人也多，破解的工具也多。

自创的算法，虽然在密码学上很弱，但可以把逻辑实现的很长很复杂，并且加以混淆，就可以在「隐蔽性」上占优势了。

这样，要将其移植到 GPU 上，就困难了。

同时还可以制作模板，定期变幻代码。在攻击者破解之前，逻辑又变化了。

在对抗中，随机应变的弱算法，显然比一成不变的强算法更好。

串行模式

Hashcash 的原理，决定了它是可以并行计算的。有什么样的算法，是无法并行计算的？

如果每次计算都依赖上次结果，就无法并行了。例如 slowhash：

function slowhash(x)

	for i = 0 to 1000000000

		x = hash(x)

	end

	return x

end

这种串行的计算，自然是无法拆分的。

但这能用到 PoW 上吗？显然不行！

因为 PoW 虽然计算困难，但得 容易鉴定。而这种方式，鉴定时也得重复算一遍，成本太大了。

---

但发挥一下想象：如果能够设计得当，这还是可以尝试的 —— 我们可以使用 UGC 的模式，让用户来贡献算力！

首先，需要一个访问量较大的网站，在其中悄悄放置一个脚本：

# 隐蔽的脚本

Q = rand()

A = slowhash(Q)

submit(Q, A)

我们利用在线的用户，来生成问题和答案！！

当然，这项工作必须足够隐蔽，防止被好奇的用户发现，提交错误的答案。

当后端题库有一定的积累时，就可以使用验证码的模式了。

用户访问时，后端从题库中抽取一个问题，安排给前端计算：

# 后端 - 分配问题

Q = select_key_from_db()

session["pow_ques"] = Q

# 前端 - 计算问题

A = slowhash(Q)

用户提交时，后端无需任何计算，直接通过查表，判断答案是否正确：

# 前端 - 提交

submit(..., A)

# 后端 - 鉴定

Q = session["pow_ques"]

if A == db[Q]

	ok

else

	fail

end

使用预先计算的方式，避免了耗时的鉴定工作。同时，把让用户来出题，可大幅节省硬件成本。

---

回顾之前的 hashcash，因为散列结果是不确定的，题解时间有一定的随机性。

但 slowhash 这种方式，只是重复执行散列函数 N 次，所以解题的时间更固定。

演示

出于简单，这里演示一个 hashcash-md5 版的：

https://github.com/EtherDream/proof-of-work-hashcash

如果想看算力速度，可以查看这里：

看起来好像不慢，不过对比 GPU 的速度 就相形见绌了。

所以 hashcash 如果使用经典算法，简直就是不堪一击的。或许自己写的「隐蔽式加密」算法，反而更能对抗一些。

至于 slowhash 那种串行模式的 PoW，涉及到较多策略和数据积累，本文就不演示了，下回再讨论。

---

（2017/03/01 补充）现在 WebGL2 出来了，着色器支持整数以及位运算，因此非常适合 PoW 计算：

Demo：https://www.etherdream.com/FunnyScript/glminer/glminer.html

用我的笔记本核显，每秒都能计算 2700 万次 SHA256 算法。换成好点的显卡例如泰坦，每秒可以 5 亿以上的 hash 计算~ （注意 SHA256 比 MD5 慢多了）

---

总结

最后来对比下，算力验证和传统图形验证的区别。

	验证方式	验证对象	用户体验	拦截假人	实际意义
传统验证	图像识别	人脑	有交互	部分拦截	杜绝假人
算力验证	问题解答	电脑	无感知	无法拦截	减少滥用

论效果，当然还是传统验证码更好；论体验，计算对于用户是透明的，无需任何交互。

简单来说，传统验证码是防止机器「不能使用」；而 PoW 防止的则是「不能滥用」。

---

当然上述提到发帖那个案例，并不恰当。即使用上 PoW，限制每 5 秒发一帖，那么一分钟仍有 12 贴 —— 这速度显然还是有点太快。更适合 PoW 的场合，应该类似找回密码、或者接收短信等功能，比较容易在短时间内被大量滥用，用于增加攻击者刷接口的成本。