34 Memory Bound

36. 密码学系列之:memory-bound函数

简介

memory-bound函数可以称为内存受限函数，它是指完成给定计算问题的时间主要取决于保存工作数据所需的内存量。和之相对应的就是计算受限compute-bound的函数，在计算受限的函数中，计算所需要的计算步骤是其决定因素。

本文将会介绍一下内存受限函数和它跟内存函数的关系。

内存函数

内存函数和内存受限函数看名字好像很类似，其实他们的作用是不同的，我们先来看下内存函数。

在学习算法中，有一个非常简单好用的算法叫做递归算法，熟悉递归算法的朋友可能都知道，递归算法虽然好用，但是有个缺点就是会重复计算递归过程中的函数，比如说递归中最经典的斐波拉赫数列：

 Recursive_Fibonacci (n)
 {
     if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

很简单，但是我们来考虑下计算过程，F(3)=F(2)+F(1), 而F(4)=F(3)+F(2)，在这个过程中需要计算2次F(2)的值。如果计算的N值够大的话，重复计算的值还会更多。

一个解决方法就是将之前计算过的结果使用内存存起来，这种方法就叫做内存函数：

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {
     if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2 ) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

虽然直接递归的逻辑很简单，写起来也很方便，但是它的时间复杂度会更高。

内存受限函数

内存受限函数主要用来描述一个使用XOR的函数，它由一系列计算组成，其中每一次计算都依赖于前一次计算。

因为这样的内存依赖关系，所以内存受限函数主要用在密码学中，可以防止密码的暴力破解工作。

下面举个内存受限函数在防止垃圾邮件中的使用。

内存受限函数的使用

使用内存受限函数来防止垃圾邮件，主要使用的是POW的原理，也就是说，你可以给我发垃圾邮件，但是前提是需要付出一些代价。

当然，最初的防垃圾邮件的原理是使用CPU受限函数。

1992年，IBM的研究科学家Cynthia Dwork和Moni Naor在CRYPTO上发表了一篇题为《通过定价来阻止垃圾邮件》的论文，他们提出了一种利用CPU受限函数的功能来阻止滥用者发送垃圾邮件的可能性。

该方案的原理是：如果滥发邮件的成本很低，那么垃圾邮件就可能横行。如果能够通过以昂贵的CPU计算的形式为发送邮件添加额外的计算成本，就可以减少垃圾邮件。使用CPU受限函数，使得每发一次邮件都需要消耗一定的CPU资源，从而防止在短时间内发送大量的垃圾邮件。

CPU受限函数是一种突破，但是也有其缺点。

因为快CPU的计算速度比慢CPU快得多。此外，高端计算机系统也有复杂的流水线和其他有利于计算的优化功能。因此，拥有高端系统的垃圾邮件发送者几乎不会受到这种CPU受限函数的影响。

从而会因为不同用户机器性能的不同，导致非常大的计算时间差异。比如如果一个算法在高级计算机上需要几秒钟，那么在老的计算机上可能需要1分钟，而在性能更差点的手机上可能会需要几分钟，那么这个算法肯定是无法被手机用户接受的。

因此，研究者们关注的是如何找到一种在大多数计算机系统都以大致相同的速度运行的函数，虽然在高级计算机上速度会更快，但也只是稍微快一点而已，不是几何级数的快，那么就可以在容忍范围之内。

这种方法就是使用内存受限函数。内存受限函数是指计算时间由访问内存的时间支配的函数。内存受限函数以一种不可预测的方式访问大内存区域的位置，从而无法使用缓存来提升性能。

使用内存受限而不是CPU受限也有其工业上的原因，近年来，虽然CPU的计算速度急剧增长，但在开发更快的主内存方面进展相对较小。所以可以预见，在未来的一定时间内，内存受限函数还会有越来越多的应用场景。