Hashcash 是一個拒絕服務（denial-of-service）計數器度量工具。當前它的主要作用是幫助 hashcash 用戶避免因為使用了基於內容和基於黑名單的（blacklist-based）反垃圾郵件系統而丟失郵件。 可是，我認為，這項技術有著廣泛的適用性，並不是只適用於電子郵件。本文還將介紹這項技術在郵件過濾方面的應用，並將提供它在其他一些方面的應用。文中將介紹我自己用 Python 完成的 hashcash 實現（它似乎是第一個當前 發布的 Python 版本），hashcash.org 站點上現在已經包含該實現。David McNab 創建了一個 Python 實現，該實現使用的協議與 hashcash 不是特別相似；其他一些開發人員也創建了部分實現 hashcash 的不完全的 Pytyhon 版本。 不過，在開始這些話題之前，讓我們來回顧一下什麼是 hashcash。
hashcash 基礎知識 hashcash 的靈感來自於這樣一個想法，即一些數學結果難於發現而易於校驗。一個眾所周知的例子是因數分解一個大的數字（尤其是因數較少的數字）。將一些數字相乘來獲得它們的積的代價是低廉的（畢竟，CPU 周期就是金錢），但首先找到那些因數，而這項操作的代價卻要高得多。 RSA 公鑰密碼系統就是基於這種因數分解特性的。如果應答者能夠回答因數分解質詢（Challenge），則說明他已經做了相當多的工作（或者偷偷地從生成那個組合的人那裡得到了因數）。 對交互式質詢來說，因數分解足以勝任。比如，我有一個在線資源，希望您能象征性地為其付出代價。我可以向您發送一個消息，說“只要您能因數分解這個數，我將讓您得到這個資源”。沒有誠意的人將無法得到我的資源，只有那些能夠證明自己有足夠的興趣、付出一些 CPU 周期來回答這個質詢的人才能得到這個資源。
非交互式質詢 不過，有一些資源無法很方便地進行交互式協商。 我的電子郵件收件箱是我非常重視的一個資源。但不期而至的消息占用了我的一些磁盤空間和帶寬，最糟糕的是，它們吸引了我的注意力。我並不介意陌生人給我寫信，但是，我希望他們能以稍微認真的態度，親自通過對我有價值的郵件與我取得聯系。至少，我不希望他們是垃圾郵件制造者，那些人向我和上百萬的其他人發送包含同樣消息的郵件，期望我們中的某些人能購買某種產品或陷入一個騙局。 為了實現非交互式的“支付（payment）”，hashcash 讓我向所有想給我發送電子郵件的人都分發一個標准質詢。在您的消息頭中，必須包括一個合法的 hashcash 戳記（hashcash stamp）；具體地說，該標志中包含我的收件人地址。 hashcash 提出質詢的方式是，當通過安全散列算法（Secure Hash Algorithm）進行散列時，要求“minters”生成一個字符串（戳記，stamps），在它們的散列中有很多前導零。所找到的前導零的數目就是特定戳記的比特值。給定 SHA-1 的一致性與加密強度，找出給定比特值的 hashcash 戳記的惟一已知途徑是平均 2^b 次運行 SHA-1。 然而，要確認一個戳記，只需要進行一次 SHA-1 計算即可。對於電子郵件中的應用來說，當前推薦使用的是 20-比特值：為了找到一個合法的戳記，發送者需要進行大約一百萬次嘗試，在最新的 CPU 和經過編譯的應用程序上，這將需要不到一秒的時間。在相對舊一些的機器上它也只需要幾秒鐘的時間。 雖然我們已經開始討論 bashcash 基礎知識，但在繼續討論之前，讓我們先領略一下 SHA 算法的強大功能。
SHA 有多麼強大？ 在一次被證明是密碼界中具有重大意義的事件中，披露出一個對 SHA-0 的碰撞（collision）（請參閱參考資料中指向 Pascal Junod 的電子郵件的鏈接，它給出了實際碰撞的細節）。所使用的攻擊需要大約 2^51 步，遠遠少於我們所期望的暴力構造碰撞所需要的大約 2^80 步（以及存儲空間）（遵循“生日悖論（birthday paradox）；關於生日悖論以及如何將它應用於散列函數的更多信息的鏈接，請參閱參考資料）。 在過於擔心這種與 bashcash 相關的攻擊之前，要緊記兩點：一是這種方法攻擊的是 SHA-0，不是 SHA-1（目前還不是）。另一相關的保證是，在當前最快的 CPU 上，2^51 步需要的時間仍會超過 9 CPU 年。即便有類似的方法可以應用於 SHA-1，構造虛假碰撞的代價也不可能低於構造更大數量的 20-位戳記（或者甚至是 40-位 hashcash 戳記）。
hashcash（版本 1）格式 只有一個特定的 SHA-1 散列值是不夠的。我們還希望戳記特定於被請求的資源 —— 也就是說，用於
[email protected] 的戳記應該與用於
[email protected] 的戳記具有不同的適用性。如果不是這樣，垃圾郵件制造者就可以只生成一個高比特值的戳記並到處去使用它。 另外，一旦生成戳記，我不希望每一個想給我發送郵件的垃圾郵件制造者都能共享它。所以，hashcash 采用了以下兩個額外步驟（或者至少建議它們應該作為協議的一部分）： 首先，戳記攜帶一個日期。用戶可能會決定認為比特定期限更早的戳記是非法的。 其次，hashcash 客戶機可能（並且多半應該）實現一個 double spend 數據庫。 在 double spend 數據庫中，每一個戳記都只能使用一次；如果第二次收到它，那麼就認為它是非法的（非常類似於郵票在使用後會被做標記）。具體地說，hashcash（版本 1）戳記類似於下面的代碼： 1:bits:date:resource:ext:salt:suffix 戳記包括 7 個域。 版本號（版本 0 更簡單，但是有一些局限性）。 聲明的比特值。如果戳記沒有真正地使用聲明的前導零比特進行散列，那麼它就是非法的。 生成戳記的日期（和時間）。可以認為當前時間之後的戳記以及那些在很久以前的戳記是非法的。 戳記為哪個資源而生成。可能是一個電子郵件地址，但是也可能是一個 URI 或者其他命名的資源。 特定應用程序可能需要的擴展。任何附加的數據都可以放置在這裡，但是，在到目前為止的使用中，這個域通常是空的。 將該戳記與其他所有人為相同的資源在同一日期生成的戳記區別開來的隨機因子（salt）。例如，兩個不同的人可以合情合理地在同一天向我的同一個地址發送電子郵件。他們不應該由於我使用了 double spend 數據庫而無法發送成功。但是，如果他們每個人都使用一個隨機因子，那麼完整戳記將是不同的。 後綴是算法真正起作用的部分。假定給出了前 6 個域，為了生成一個通過期望數目的前導零進行散列的的戳記，minter 必須嘗試很多連續的後綴值。 現在讓我們來看 bashcash 如何在電子郵件中起作用。
bashcash 如何在電子郵件中起作用 在理想的世界中，所有發送者都應該在他們的消息中包含 bashcash 標記；接收者在接收時都將檢查它們的合法性。不過，在實際生活中，hashcash 還沒有得到那麼廣泛的應用。雖然如此，開始使用 bashcash（不管是作為發送者還是作為接收者）並不會對現有電子郵件工具產生任何影響。換句話說，在電子郵件中使用 bashcash，您不會有任何損失。 為了給發出的消息加上戳記，只需要向電子郵件添加頭文件即可：用於電子郵件的每一個 To: 或 Cc: 接收者的 X-Hashcash 頭。例如，某個想給我發送消息的人可能會在消息中包含一個與示例 rfc2822 頭文件類似的頭文件： X-Hashcash: 1:20:040927:
[email protected]::odVZhQMP:7ca28 顯然，應該由 MUA（郵件用戶代理，mail user agents）、過濾器或者 MTA（郵件傳輸代理，mail transport agents）來做這件事情，而不是要求用戶手工完成。不過，手工完成也不太難，至少實驗時如此。首先，通過查看戳記的散列來校驗它，如下所示： $ echo -n 1:20:040927:
[email protected]::odVZhQMP:7ca28 sha 00000b50b85a61e7ba8ac4d5fed317c737706ae5 注意前導零（每一個十六進制數是 4 個比特）。當然，還需要校驗哪個資源是您識別出來的那個資源（比如您的收件人地址之一），那個戳記還沒有被使用過，日期是當前日期。另外，一個合法的戳記擁有的前導零的數目應該與其聲明要擁有的數目相同（不過您可以決定強制實行您自己的允許郵件通過的最小代價：20 比特是一個不完全標准（semi-standard），它最終可能會隨著 Moore 定律而發生改變）。
為什麼這會起作用？ 生成一個 20-比特的戳記只需要幾秒鐘的時間。當您一天中只發送幾十封電子郵件時，這個代價並不大。但是，對那些想要發送數百萬消息的垃圾郵件制造者來說，不能容忍每條消息使用額外幾秒的 CPU 時間。一天之中只有 86,400 秒。即使垃圾郵件制造者利用植入木馬（trojans）的僵屍（zombies）的技術，需要使用具體的 hashcash 戳記至少也會減少那些僵屍進程的發出量。當然，校驗一個戳記所需的時間只是一秒的一小部分。 另一方面，向您自己的 MUA 添加 hashcash 生成和校驗對其他所有人沒有任何負面影響（不像其他一些反垃圾郵件方法）。對那些不使用該協議的接收者而言，這些只是一個他們很容易忽略的附加頭文件。對那些沒有添加 hashcash 戳記的發送者而言，檢驗 X-Hashcash: 的接收者不用校驗任何內容。如果發送者沒有添加戳記，那麼您的境況不會因為進行檢驗而變得更糟；也不會因此變得更好。 一個好的 MUA 或者垃圾郵件過濾系統可以將擁有合法 hashcash 戳記的電子郵件列入白名單（whitelist）。SpamAssassin 甚至更巧妙地為更多合法 hashcash 比特提供了更高的 +ve 分數。我認為，將基於 bashcash 的方法應用於白名單是對 TMDA 等交互式質詢系統的改進 —— 質詢消息在返回時不會丟失，發送者不會忘記響應質詢。質詢響應就在原始消息之中（作
