密碼學系列之:memory-bound函數

簡介

記憶體函數

記憶體受限函數

記憶體受限函數的使用

memory-bound函數可以稱為記憶體受限函數，它是指完成給定計算問題的時間主要取決于儲存工作資料所需的記憶體量。和之相對應的就是計算受限compute-bound的函數，在計算受限的函數中，計算所需要的計算步驟是其決定因素。

本文将會介紹一下記憶體受限函數和它跟記憶體函數的關系。

記憶體函數和記憶體受限函數看名字好像很類似，其實他們的作用是不同的，我們先來看下記憶體函數。

在學習算法中，有一個非常簡單好用的算法叫做遞歸算法，熟悉遞歸算法的朋友可能都知道，遞歸算法雖然好用，但是有個缺點就是會重複計算遞歸過程中的函數，比如說遞歸中最經典的斐波拉赫數列：

很簡單，但是我們來考慮下計算過程，f(3)=f(2)+f(1), 而f(4)=f(3)+f(2)，在這個過程中需要計算2次f(2)的值。如果計算的n值夠大的話，重複計算的值還會更多。

一個解決方法就是将之前計算過的結果使用記憶體存起來，這種方法就叫做記憶體函數：

雖然直接遞歸的邏輯很簡單，寫起來也很友善，但是它的時間複雜度會更高。

記憶體受限函數主要用來描述一個使用xor的函數，它由一系列計算組成，其中每一次計算都依賴于前一次計算。

因為這樣的記憶體依賴關系，是以記憶體受限函數主要用在密碼學中，可以防止密碼的暴力破解工作。

下面舉個記憶體受限函數在防止垃圾郵件中的使用。

使用記憶體受限函數來防止垃圾郵件，主要使用的是pow的原理，也就是說，你可以給我發垃圾郵件，但是前提是需要付出一些代價。

當然，最初的防垃圾郵件的原理是使用cpu受限函數。

1992年，ibm的研究科學家cynthia dwork和moni naor在crypto上發表了一篇題為《通過定價來阻止垃圾郵件》的論文，他們提出了一種利用cpu受限函數的功能來阻止濫用者發送垃圾郵件的可能性。

該方案的原理是：如果濫發郵件的成本很低，那麼垃圾郵件就可能橫行。如果能夠通過以昂貴的cpu計算的形式為發送郵件添加額外的計算成本，就可以減少垃圾郵件。使用cpu受限函數，使得每發一次郵件都需要消耗一定的cpu資源，進而防止在短時間内發送大量的垃圾郵件。

cpu受限函數是一種突破，但是也有其缺點。

因為快cpu的計算速度比慢cpu快得多。此外，高端計算機系統也有複雜的流水線和其他有利于計算的優化功能。是以，擁有高端系統的垃圾郵件發送者幾乎不會受到這種cpu受限函數的影響。

進而會因為不同使用者機器性能的不同，導緻非常大的計算時間差異。比如如果一個算法在進階計算機上需要幾秒鐘，那麼在老的計算機上可能需要1分鐘，而在性能更差點的手機上可能會需要幾分鐘，那麼這個算法肯定是無法被手機使用者接受的。

是以，研究者們關注的是如何找到一種在大多數計算機系統都以大緻相同的速度運作的函數，雖然在進階計算機上速度會更快，但也隻是稍微快一點而已，不是幾何級數的快，那麼就可以在容忍範圍之内。

這種方法就是使用記憶體受限函數。記憶體受限函數是指計算時間由通路記憶體的時間支配的函數。記憶體受限函數以一種不可預測的方式通路大記憶體區域的位置，進而無法使用緩存來提升性能。

使用記憶體受限而不是cpu受限也有其工業上的原因，近年來，雖然cpu的計算速度急劇增長，但在開發更快的主記憶體方面進展相對較小。是以可以預見，在未來的一定時間内，記憶體受限函數還會有越來越多的應用場景。

本文已收錄于 http://www.flydean.com/memory-bound/ 最通俗的解讀，最深刻的幹貨，最簡潔的教程，衆多你不知道的小技巧等你來發現！