基于PoW的Web服務保護方法

高 建，白曉菲，張 亮

(復旦大學計算機科學技術學院，上海201203)

(上海市數據科學重點實驗室，上海201203)

(上海智能電子與系統研究院，上海201203)

E-mail:16210240009@fudan.edu.cn

1 引言

對于服務提供者而言，面向公共開放的Web服務時，很容易遭受資源濫用和各類攻擊［1］.這些情況不但影響原有服務質量，也常常造成經濟損失.相應保護系統的設計和部署并不簡單，不同方案在不同環境下表現各異，某些場景中甚至可能引入額外的性能問題和攻擊面.

現有的保護方案主要分為兩大類:以審計為主的離線方案和以圖靈測試為主的實時方案.審計方案認為爬蟲等機器流量會帶有一定特征，可以進行分析、識別和攔截;圖靈測試則要求訪問者進行一項機器難以完成的操作，只響應完成測試的訪問.

以一個具體場景為例，一家公司計劃實現一個聚合的機票訂票服務(為了方便討論，將其稱為訂票平臺)，完成業務需要頻繁向多家航空公司網站請求服務.如果航空公司使用審計策略，則訂票平臺很容易因為訪問頻次過高而被禁止訪問;如果航空公司使用圖靈測試策略，則需要大量完成驗證工作，無論使用機器來對抗還是發起眾包來消解，都無法建立可靠的合作關系——航空公司很容易發現這些自動化流量并升級策略進行應對，對整合服務造成破壞.

實際場景中，并非所有機器流量都產生資源濫用，尤其在有即席(ad-hoc)的整合服務存在的場景中，現有方法會將這些訪問一并攔截，產生顯著的合作門檻.現有方法帶來的復雜性、“混淆-識別”技術對抗等因素，也一定程度上制約了Web服務本身在質量和效率等方面的發展.

本文提出一類基于工作量證明(Proof-of-Work，或PoW)的Web服務保護方法，作為對現有方法的補充.這一方法允許提供者對服務價值進行建模來控制保護系統，在有效防止資源濫用的前提下，適度放行機器流量，幫助服務提供者在保護強度與合作可能之間做出權衡，搭建出符合自身需求的保護系統，應對復雜的網絡環境.

PoW系統的概念最早由Dwork和Naor于1993年提出［2］，最初用于某些郵件服務中，防止資源濫用.這類方案要求用戶進行一種耗時適當的復雜運算，但其答案能被快速驗算，將耗用的時間、設備與能源作為擔保成本，維持受保護資源的公平分配.通過對這一成本的量化控制，服務提供者可以精確調控保護系統介入的方式，使PoW系統成為Web服務保護的有效手段.

本文介紹此類中兩種具體的方法:其一作為單純的保護系統，要求用戶在請求服務時提供PoW 證明，確保請求的合理性，以抵御資源濫用;其二在此基礎上引入Merkle樹結構［3］，允許 PoW 證明在服務提供者之間傳遞，降低復雜整合服務中各參與者(最終用戶和各整合服務提供者)分別開展PoW 工作產生的較大資源開銷.

如果例子中的航空公司使用傳統的兩類策略，保護系統的抵御能力有一定局限.尤其當訂票平臺的技術實力和計算資源規模遠高于航空公司時，有效的審計方案將產生很大開銷，而圖靈測試方案又無法起到應有的保護作用，都有可能對己方服務質量產生不利影響.而如果使用PoW方案，航空公司總可以提高工作量要求，限制訂票平臺的請求，優先保證服務質量.

如果航空公司使用了PoW策略，訂票平臺一開始的訪問只需付出較少的工作量.隨著訪問頻次的增加，航空公司可能會提高工作量要求，直到訂票平臺因無法承受而不再增加訪問頻次.這時，雙方已經建立了相對穩定的合作關系，且能自發隨著工作量要求和接受能力的變化(如航空公司因系統負載較高而提高難度)而動態調整，增加或減少服務請求.

這類方法的技術貢獻主要在于:

·利用PoW“難計算、易驗證”的屬性，服務提供者可以通過調整PoW工作的難度，獲得杠桿效果，只消耗少量資源即可對抗資源豐富的對手;

·簡化審計系統，使其無需處理全部請求，只參與PoW難度調節，減少服務器資源開銷，降低成本，提升服務質量;

·不使用圖靈測試，不產生相應的“混淆-識別”的技術對抗，也不徹底禁止用戶自動化調用;

·最終服務請求方提供的PoW 證明可以在跨組織服務組合中作為等價物，隨著請求傳遞，在保證各方保護效果的前提下，降低門檻、促進合作.

本文在第2節中討論相關工作;在第3節中提出單一服務提供方的問題建模、解決方法和安全性證明;在第4節中提出涉及到多個服務提供方協作時的問題建模、引入Merkle樹并給出相應證明;在第5節討論實現與部署策略;第6節介紹實驗規劃;最后進行討論并對文章做出總結.

2 相關工作

一般而言，Web服務的保護主要指各類安全手段和抵御資源濫用的策略(反垃圾、反爬蟲系統［4］等).前者是專門的研究領域，不在本文討論范圍內;而后者一般分為兩類:以審計為主的離線方案，如日志分析、流量分析［5］等;以圖靈測試為主的實時方案，其中典型代表是驗證碼［6］系統.

審計類策略通常使用Web后端日志、流量數據等信息，運用語法分析、模式識別、統計和神經網絡等手段，對產生資源濫用的自動化訪問進行識別，并根據來源地址或提取的特征進行過濾.此類方法已有諸多大規模應用［7］，普遍能夠將資源濫用的規模降低一個數量級以上［4］，但系統相對較為復雜，有一定的運行時開銷，也給實現和維護工作帶來了一定壓力.

圖靈測試類策略中應用最廣泛的是驗證碼，如CAPTCHA(Completely Automated Public Turing test to tell Computers and Humans Apart)系統［6］，可以有效區分人類和機器的訪問請求.但是驗證碼的大批量識別機制也發展迅速，主要有基于機器學習的識別方案［8］和眾包人工識別［9］.由于無法對攻擊者進行識別，應用此類方案的服務提供者通常會尋求盡可能嚴格的測試方法，試圖禁止一切自動化訪問，也就對服務間的交互產生了極大的阻礙.

3 直接應用PoW的方案

本節在單一服務提供者的環境中討論PoW安全性的定義和具體方案:首先給出一份可行的定義;然后闡述在Web API請求全文上使用PoW的系統的基本方法，并舉出對其進行重放攻擊［10］的場景;最后給出一種加鹽方案，通過證明其不受重放攻擊影響，證明其安全性.

需要說明的是，這里對PoW系統的形式化與數字貨幣領域使用的形式化方法略有不同，使用“價值”而非“難度”的概念來描述工作數量，更加直觀，便于服務提供者完成建模和部署工作.相應的模型對每個用戶、每次訪問都獨立提出“價值”要求，并不存在全局的難度設置.用戶不需要對抗全網的PoW算力，也就不會產生礦池壟斷服務資源.

3.1 問題定義

服務提供者定義一個價格函數 Pu，t(r)表示在t時刻用戶u使用請求r獲得其服務需付出的代價，即只要訪問者付出足夠代價，就將其服務請求視為合理，不認定為資源濫用.這一價格P可以根據服務提供者持有的任何信息來進行調節，包括但不限于請求規模、頻率、系統負載等.

將用戶u在t時刻已付出的代價記為 Cu，t，已完成的合理服務請求記為多重集Ru，t，tr為請求 r實際發生的時間，則PoW保護系統的安全性可以定義如下:

定義1.(安全性).單一服務提供者的PoW 保護系統的安全性指在任何時刻 t，對所有用戶 u，都有

這里使用 Cu，t的期望是為了與密碼學方面的研究工作(如文獻［2］)對接，免除本文中重復開展概率論證明的必要.

定義1可以寫成增量形式，即任何用戶在任何時刻新發出合理的服務請求都必須新付出服務提供者指定的代價.

在開銷和價格上同時忽略發起請求涉及的額外開銷，只考慮PoW要求用戶完成的工作，則安全性可進一步拆分成以下三個屬性:

1)用戶無法繞過PoW保護系統獲得服務.這一點需要在軟件實現和部署上保障，不在本文討論范圍.

2)不存在開銷的期望小于具體算法聲稱值的方法允許用戶通過PoW系統的檢驗，即用戶無法“繞過”工作.這一點已經在密碼學上有了一定保障［2］，在數字貨幣領域得到了廣泛驗證，并不斷有新的研究給出更強的保障［11］.

3)重放安全性，即用戶無法使用同一份工作通過PoW系統檢驗兩次.

由此可知，在使用已得到充分驗證的PoW算法時，本文構造的PoW保護系統在結構上只需保證重放安全性即可達成保護目標.重放安全性的形式化定義在下一小節討論基本方法時給出.

3.2 基本方法

服務提供者選擇一個價值函數V(proof)估算請求方完成的工作數量，其參數稱為一個PoW證明，在基本方法中proof=(r，n).其中r為請求全文，n為請求方計算求得的解，常稱為 nonce.

價值函數通常分兩個階段完成:哈希驗證階段 Hv(proof)返回一個定長二進制串h或(當 proof完全無效時)返回ε表示失敗;估價階段V'(h)將該二進制串映射到工作數量，并對 h=ε的情況輸出0.

請求者使用相應地使用一個工作算法W(r，p)求出一個可行的n使V(r，n)大于當前時刻服務提供者要求的 Pu，t(r).工作算法W枚舉大量n的取值并運行一個 Hs(proof)過程直到其返回的 h滿足V'(h)＞Pu，t(r).Hs過程的大量重復構成了PoW的核心，其“無法繞過”的屬性已經在上一節中進行了討論.

在大部分PoW算法體系中，Hv=Hs，但由于價值函數 V只包含一次Hv，其計算開銷較小，使該系統在服務器一側的資源占用保持在較低的水平.某些算法［12］還使用了比 Hs輕量的 Hv，進一步減輕服務器驗證開銷.

用戶在請求服務前獲取價值函數V及價值目標 Pu，t(r)(后者也可由服務提供者公開的價格函數 P等其他信息求出)，使用(隨服務提供的或自己選擇的)Hs實現完成工作，并將 proof隨HTTP請求發送給服務器(在這一方法中實際只需額外發送n).

服務器計算價值函數V并做出對應處理:對工作數量滿足要求的，提供正常的服務;對于工作數量不滿足要求的，視為攻擊者并交由相應系統處理(如累積到一定數量后在防火墻上屏蔽).

對這一系統進行重放攻擊非常簡單，用戶求得有效的 n后只需將整個proof發送兩次，即可獲得兩次服務，但實際只完成了一份工作.

由于proof和具體工作具有直接對應的關系，我們可以借助它來對重放安全性進行定義:

定義2.(重放安全性).單一服務提供者的PoW 保護系統的重放安全性指其識別曾經通過驗證的 proof且拒絕其再次通過驗證的能力.

3.3 加鹽的方法

在基本方法中，服務器因為沒有保存關于過往或未來proof的任何信息，所以會受到重放攻擊而無法保證安全性.服務器顯然可以記錄所有已通過驗證的 proof并拒絕其再次通過，但是這種手段要實現重放安全就必須進行永久存儲，每次將新收到的 proof在其中進行檢查的代價會逐漸增大，使這種方法不適合長期使用.

對抗重放攻擊的核心思路是讓proof中n以外的部分及時改變.服務提供者可以通過在請求上追加一個能夠及時變化的鹽來完成，即令 proof=(r，salt，n)，其中 salt為服務器選擇的鹽.這時工作算法的參數也相應改變，訪問者的計算工作變為 W((r，salt)，p).每當 salt改變，舊的 n無法通過驗證，訪問者如需再次請求服務，就需要重新運行工作.

定理1.加鹽的PoW 保護系統具有重放安全性，當且僅當服務器給同一個鹽salt提供不超過一次服務.

證明:必要性由3.2節末尾的例子可知，以下證充分性.salt改變則(r，salt)改變，那么攻擊者無法使用原有的 n和新的salt通過價值函數V驗證;如果攻擊者使用原有的salt請求服務，則服務器會因為 salt失效而拒絕.證畢.

這一方案要求用戶在每次請求服務前(執行W過程時)都持有一個有效的鹽 salt，看似會顯著增加服務器需要處理的請求數量，但實際可以通過一些部署技巧進行消解，以下列舉兩種思路:1)在每個請求(無論是否有效)的應答中附帶一個新的、有效的鹽;或者2)給鹽設置存活時間.由于定理1是充要條件，只要在同一請求 r能再次獲取到有意義的服務(如所請求的數據發生變化)前使鹽失效即可實現有效保護.

沿用第2節中的場景，如果航空公司使用了加鹽的PoW保護系統，則訂票平臺首次請求服務的流程如圖1所示.

圖1 航空訂票場景使用加鹽PoW保護系統時的交互Fig.1 Interaction of a salted PoW system in an airline booking scenario

如果航空公司在這一請求的回應中附帶了一個新的salt，那么訂票平臺的下一次請求就無需再請求參數，可以直接執行工作過程W并請求服務.

4 帶有Merkle樹的方案

不難發現，無論在多服務提供者的環境中如何定義PoW系統的安全性，只要不與定義1產生沖突，加鹽的方案都能夠有效對Web API進行保護.

在有復雜的服務組合的場景中，如果參與的每一個調用者都需要進行工作過程W的調用來計算n，就會造成較大的計算資源浪費.

為了消除這種資源浪費對大型系統的不利影響，需要對PoW保護系統進行適當的放寬.本節嘗試將最終調用者提交的PoW證明作為組織間服務調用的等價物，降低服務提供者之間API調用的開銷.我們首先給出該場景中安全性和重放安全性的一組可行定義，然后介紹在保護系統中使用Merkle樹［3］的方法并證明其具有重放安全性.

4.1 問題定義

對3.1節中安全性的定義進行調整，加入對服務提供者的表述，可以得到多方協作環境中安全性的一個可行定義:

定義3.(多提供者安全性).多服務提供者PoW 保護系統的安全性，指其中包含的每一個單一服務提供者的PoW保護系統都具有安全性.即在任何時刻t，對所有服務提供者sp和所有用戶 u，都有 E(Csp，t)= ∑r∈Rsp，u，tPsp，u，tr(r).

相似地，也可以給出對應的安全性的定義:

定義4.(多提供者重放安全性).多服務提供者PoW 保護系統的重放安全性，指其中包含的每一個單一服務提供者的PoW保護系統都具有重放安全性.即其中每個服務提供者都具有識別曾經通過驗證的proof且拒絕其再次通過驗證的能力.

以上定義是可行的，由3.1節中服務提供者定義價格函數P的方式可知，單個服務提供者只要求調用者付出相應代價，并不關心系統的其他參與者，即可以允許同一個PoW證明被用于請求其他提供者的服務.

4.2 具體方案

要保證保護效果，多提供方場景中的PoW計算工作開始前指定若干對具體的請求全文r和鹽salt.這要求發起請求時攜帶的證明必須包含(或引用)一個結構來記錄這些數據，提交給服務器完成驗證.

出于嚴謹考慮，我們保持PoW證明的定義不變，指“完成了工作”的證明，而將本節中使用Merkle樹實現的“請求已被PoW證明指定”所需的額外數據稱為Merkle證明.此時要獲得服務，請求方不僅需要發送PoW證明，還需要發送對應的Merkle證明.

取一個常用的哈希算法 H，將 (H(r，salt)，H(node))作為一個請求單元，則本節的系統中使用的Merkle樹節點定義為由請求單元組成的非空集合，其中H(node)通過哈希完成對一個子節點的引用.這一集合需要實際實現為數組以便完成哈希操作.

由于樹結構上有以下公理:

公理1.節點 n在樹 T中當且僅當 n是 T的根節點，或其父節點在T中.

這時，服務請求者可以從 H(r，salt)所在的節點開始逐級給出父節點直到樹根，記作［node］，證明 H(r，salt)記錄在 Merkle 樹 T.三元組 (H(r，salt)，H(root(T))，［node］)稱為Merkle證明，其中root(T)為對應Merkle樹的根節點.

由于Merkle樹中已經記錄了請求和鹽，上一節中的PoW證明無需重復記錄，即令 proof=(H(root(T))，nonce).使服務器先進行Merkle驗證，則:

定理2.使用Merkle樹的PoW系統具有多提供者重放安全性，當且僅當每個服務器對H(root(T))相同的Merkle證明只接受不超過一次.

證明:必要性顯然，以下證充分性.由于 H(root(T))直接出現在proof中，攻擊者無法使用原有的n和新的 H(root(T))通過價值函數V驗證.證畢.

如果proof中的鹽已經失效，就無法通過PoW驗證.利用這一屬性，服務器可以清理舊的 H(root(T))，無需永久記錄，即:

推論1.服務器對每個通過PoW驗證的請求記錄根節點哈希值H(root(T))，至收到該請求前發出的所有鹽都已失效為止，拒絕后續使用同一 H(root(T))的Merkle證明，整個PoW保護系統具有多提供者重放安全性.

這時最終用戶請求服務的過程可以描述如下:

1)預先獲取價值函數 V和服務價格 Psp，u，tr(r);

2)向服務器請求鹽salt和一個子節點c的引用H(c);

3)以r、salt和H(c)組成一個請求單元，與其他請求單元(如果有)，一起構造根節點root(T);

4)調用工作算法W求得n;

5)將PoW證明和Merkle證明隨各個請求發送給服務器.

服務器驗證請求后可以根據價值函數 V的輸出，選擇是否將該份證明用于事先在子節點c中記錄的服務請求.這時只需將c的某個子節點c'加到［node］中并以對應的請求替換掉 H(r，s)，就可以組成新的Merkle證明，用于請求預先選定的其他服務.

在先前的場景中，訂票平臺可以事先向若干航空公司請求參數，并準備好一棵包含若干請求的Merkle樹.最終用戶(旅客)向訂票平臺請求服務時，將這棵樹的引用作為參數交給用戶.訂票平臺可以進一步在用戶提交的Merkle證明上追加節點，使對應的PoW證明能夠用于向對應的航空公司請求服務，如圖2所示.

圖2 航空訂票場景使用帶有Merkle樹的PoW保護系統時的交互Fig.2 Interaction of a PoW system with Merkle tree in an airline booking scenario

如果航空公司要求的價值低于訂票平臺向用戶要求的價值，那么每個PoW證明都能成功傳遞;反之，訂票平臺則需要篩選出價值符合航空公司要求的PoW證明.這一操作與數字貨幣“礦池”［13］相似，從期望上來看，只要訂票平臺收取的價值總和超過向每一個航空公司付出的價值，訂票平臺的整合服務就能夠持續運轉而不需要進行PoW計算工作.這一過程并不會導致訂票平臺壟斷服務資源，因為航空公司可以通過訪問來源地址進行區分:來自訂票平臺的訪問規模大、頻率高，因而工作量要求高;一般用戶訪問規模小、頻率低，工作量要求低，可以很快完成.

由于樹節點的引用中加了鹽，這一整合服務調用過程中所有請求都只對直接相關的參與者(請求者和提供者)可見.系統的參與者還可以在哈希函數H的值域中生成隨機數，作為節點引用填入Merkle樹中，進一步對元數據進行保護.

與3.3節中相似，服務器仍然可以在應答中附帶新的鹽和子節點引用，但因為環境發生了較大變化，放寬重放安全性的策略可能會對系統的其他部分產生作用，是否影響安全性還有待進一步研究.

5 實現與部署

作為一個軟件系統，PoW能夠投入使用需要滿足功能、性能等各方面的屬性，僅完成證明是不夠的.本節討論該系統在實現和部署時需要注意的問題及應對策略，供后續研發和部署工作參考.

價值函數V需要調用Hv函數，隨著請求的增加，會積累顯著的資源開銷.為了防止在此處構造DoS攻擊，PoW保護系統必須與黑名單系統相連——連續多次PoW驗證失敗的用戶需要被及時加入黑名單，以防其發送大量隨機生成的無效PoW證明，大量觸發驗證過程，消耗服務器資源.

理想情況下，包括PoW在內的服務保護系統與服務本身的業務邏輯應該完全解耦，以免影響服務本身的操作和維護屬性.為了實現這一目標，PoW系統需要部署在前置的反向代理設施中.企業中出于負載均衡等需求，通常已部署nginx1https://www.nginx.com/或haproxy2https://www.haproxy.org/等軟件在此位置，則PoW系統的服務器端組件可以實現為相應軟件的插件，并配置為優先于其他插件調用，以防緩存等功能使部分請求漏過.如第3、4https://github.com/dashpay/dash_hash/blob/master/dash.c節所述，PoW 系統需要短期存儲少量數據提供重放安全性，這些數據應當存儲在獨立的數據庫(如redis3https://redis.io/)中，以防對其他業務產生管理上或者性能上的串擾.

PoW系統使用的算法及其參數、鹽生成和管理方法、服務價值模型等要素都有很大的調整余地.服務提供者可以僅考慮保護效果，選擇簡易的配置(如 Hv=Hs=H=SHA256、V'(h)=、隨著訪問頻率指數增長的服務定價 P);也可以根據自身的具體需求仔細調整配置，提高保護效果和服務質量.其中，H的選擇對系統影響相對較小，V'和P主要依靠服務提供者的建模工作選擇，因而不在本文討論范圍之內;Hs和Hv則直接來自于PoW系統，其資源開銷等屬性對系統的諸多指標有較大影響，我們在表1中列出一些常見的PoW算法體系及其主要特點，以便后續研究和開發工作做出合適的選擇.

表1 常見PoW算法及特點Table 1 Common PoW algorithm and characteristics

6 實驗規劃

在保護效果、可控性、性能開銷和可維護性等方面，PoW方案需要通過實驗與現有方案進行比較.其中涉及實際攻擊者的行為(在攻擊代價大幅上升時如何應對等)，無法通過流量鏡像和模擬攻擊等方式完成，必須進行實際部署并收集數據.為了盡可能減少實驗本身給現有系統帶來的風險，我們將方法本身及證明過程公開5https://github.com/davidgao/POWonWEB，收集相關反饋，并在實現和后續部署時進行相應的調整.

7 討論

從證明來看PoW系統用作Web服務保護是輕量且有效的，只需一個基本的鍵值數據庫就能夠有效完成工作，甚至可以無需使用持久化存儲.與圖靈測試系統類似，PoW系統將一個“做與不做”的選擇交給對手，但在“做”的一側，兩種系統的處理是差異很大的——驗證碼無法快速增加難度，使對手可以使用眾包等方案繼續完成訪問;PoW系統則可以快速提升服務價格，提供更有效的保護.

在一些攻擊場景中，這個“做與不做”的選擇也可以協助其他系統完成一定程度的識別和防御:在較高的服務價格下，如果攻擊者不完成PoW計算工作，會被PoW驗證過程篩出而拒絕訪問;如果攻擊者繼續完成PoW計算，又會顯著拖慢攻擊進程，提高攻擊代價.尤其在需要多個請求才能完成攻擊時，PoW系統也能夠起到輔助保護作用.

相應的，PoW系統也存在一些已知的局限性.其一在于，特定場合(如設計上存在大規模突發訪問的服務)中對服務價格函數P的設計比較困難，有潛在可能影響到3.1節中假設的可滿足性;其二在于，PoW作為密碼學應用，向運行環境中引入了新的因素，如果設計、實現或部署不當，可能產生額外的攻擊面.

在多提供者的環境中，定義3和定義4是比較嚴格的，會導致同一份proof完全無法用于向同一個服務提供者請求兩次服務.考慮到較為復雜的整合服務中確實可能有不同參與者各自發起這樣的請求，這種屬性會對服務組合產生一定的限制.我們尚不明確這種限制會對具體場景產生怎樣的影響，或者是否存在更合理的安全性定義能夠放松這種限制.這些疑問還需要等待后續研究工作來給出解答.

8 結論

開放公共訪問的Web服務常常需要進行防止資源濫用的保護，而現有的保護系統未能在保護效果、服務質量和合作能力等指標上達成一致.

本文提出了一類將PoW系統用于公共Web服務保護的方法，在不削弱保護效果的條件下，降低組織間服務整合的門檻.我們對兩種具體方法的有效性進行了證明，并簡要討論了實現、部署策略和已知的局限性.其中加鹽的方法較為簡單、易于實現且提供更好的保護效果，但在服務組合大量出現的復雜系統中可能產生資源浪費;使用Merkle樹的方法相對復雜，在保護上進行了適當的放松，防止了這種浪費的發生，并降低了合作門檻，促進了Web服務資源的優化分配.

PoW系統用于Web服務保護的方案尚不成熟，存在一些子問題有待后續研究，主要包括:如何對服務價值進行有效建模、多服務提供者環境中的安全性是否應該進一步放寬、Merkle樹方法中是否存在潛在攻擊面等.

PoW系統允許服務提供者將其服務價值模型投入到Web服務保護系統中，適當放行機器流量換取合作機會，給互聯網服務提供者提供新的思路.