基于PoW的Web服務(wù)保護(hù)方法

高 建，白曉菲，張 亮

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海201203)

(上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，上海201203)

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

E-mail:16210240009@fudan.edu.cn

1 引言

對(duì)于服務(wù)提供者而言，面向公共開(kāi)放的Web服務(wù)時(shí)，很容易遭受資源濫用和各類攻擊［1］.這些情況不但影響原有服務(wù)質(zhì)量，也常常造成經(jīng)濟(jì)損失.相應(yīng)保護(hù)系統(tǒng)的設(shè)計(jì)和部署并不簡(jiǎn)單，不同方案在不同環(huán)境下表現(xiàn)各異，某些場(chǎng)景中甚至可能引入額外的性能問(wèn)題和攻擊面.

現(xiàn)有的保護(hù)方案主要分為兩大類:以審計(jì)為主的離線方案和以圖靈測(cè)試為主的實(shí)時(shí)方案.審計(jì)方案認(rèn)為爬蟲等機(jī)器流量會(huì)帶有一定特征，可以進(jìn)行分析、識(shí)別和攔截;圖靈測(cè)試則要求訪問(wèn)者進(jìn)行一項(xiàng)機(jī)器難以完成的操作，只響應(yīng)完成測(cè)試的訪問(wèn).

以一個(gè)具體場(chǎng)景為例，一家公司計(jì)劃實(shí)現(xiàn)一個(gè)聚合的機(jī)票訂票服務(wù)(為了方便討論，將其稱為訂票平臺(tái))，完成業(yè)務(wù)需要頻繁向多家航空公司網(wǎng)站請(qǐng)求服務(wù).如果航空公司使用審計(jì)策略，則訂票平臺(tái)很容易因?yàn)樵L問(wèn)頻次過(guò)高而被禁止訪問(wèn);如果航空公司使用圖靈測(cè)試策略，則需要大量完成驗(yàn)證工作，無(wú)論使用機(jī)器來(lái)對(duì)抗還是發(fā)起眾包來(lái)消解，都無(wú)法建立可靠的合作關(guān)系——航空公司很容易發(fā)現(xiàn)這些自動(dòng)化流量并升級(jí)策略進(jìn)行應(yīng)對(duì)，對(duì)整合服務(wù)造成破壞.

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

本文提出一類基于工作量證明(Proof-of-Work，或PoW)的Web服務(wù)保護(hù)方法，作為對(duì)現(xiàn)有方法的補(bǔ)充.這一方法允許提供者對(duì)服務(wù)價(jià)值進(jìn)行建模來(lái)控制保護(hù)系統(tǒng)，在有效防止資源濫用的前提下，適度放行機(jī)器流量，幫助服務(wù)提供者在保護(hù)強(qiáng)度與合作可能之間做出權(quán)衡，搭建出符合自身需求的保護(hù)系統(tǒng)，應(yīng)對(duì)復(fù)雜的網(wǎng)絡(luò)環(huán)境.

PoW系統(tǒng)的概念最早由Dwork和Naor于1993年提出［2］，最初用于某些郵件服務(wù)中，防止資源濫用.這類方案要求用戶進(jìn)行一種耗時(shí)適當(dāng)?shù)膹?fù)雜運(yùn)算，但其答案能被快速驗(yàn)算，將耗用的時(shí)間、設(shè)備與能源作為擔(dān)保成本，維持受保護(hù)資源的公平分配.通過(guò)對(duì)這一成本的量化控制，服務(wù)提供者可以精確調(diào)控保護(hù)系統(tǒng)介入的方式，使PoW系統(tǒng)成為Web服務(wù)保護(hù)的有效手段.

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

如果例子中的航空公司使用傳統(tǒng)的兩類策略，保護(hù)系統(tǒng)的抵御能力有一定局限.尤其當(dāng)訂票平臺(tái)的技術(shù)實(shí)力和計(jì)算資源規(guī)模遠(yuǎn)高于航空公司時(shí)，有效的審計(jì)方案將產(chǎn)生很大開(kāi)銷，而圖靈測(cè)試方案又無(wú)法起到應(yīng)有的保護(hù)作用，都有可能對(duì)己方服務(wù)質(zhì)量產(chǎn)生不利影響.而如果使用PoW方案，航空公司總可以提高工作量要求，限制訂票平臺(tái)的請(qǐng)求，優(yōu)先保證服務(wù)質(zhì)量.

如果航空公司使用了PoW策略，訂票平臺(tái)一開(kāi)始的訪問(wèn)只需付出較少的工作量.隨著訪問(wèn)頻次的增加，航空公司可能會(huì)提高工作量要求，直到訂票平臺(tái)因無(wú)法承受而不再增加訪問(wèn)頻次.這時(shí)，雙方已經(jīng)建立了相對(duì)穩(wěn)定的合作關(guān)系，且能自發(fā)隨著工作量要求和接受能力的變化(如航空公司因系統(tǒng)負(fù)載較高而提高難度)而動(dòng)態(tài)調(diào)整，增加或減少服務(wù)請(qǐng)求.

這類方法的技術(shù)貢獻(xiàn)主要在于:

·利用PoW“難計(jì)算、易驗(yàn)證”的屬性，服務(wù)提供者可以通過(guò)調(diào)整PoW工作的難度，獲得杠桿效果，只消耗少量資源即可對(duì)抗資源豐富的對(duì)手;

·簡(jiǎn)化審計(jì)系統(tǒng)，使其無(wú)需處理全部請(qǐng)求，只參與PoW難度調(diào)節(jié)，減少服務(wù)器資源開(kāi)銷，降低成本，提升服務(wù)質(zhì)量;

·不使用圖靈測(cè)試，不產(chǎn)生相應(yīng)的“混淆-識(shí)別”的技術(shù)對(duì)抗，也不徹底禁止用戶自動(dòng)化調(diào)用;

·最終服務(wù)請(qǐng)求方提供的PoW 證明可以在跨組織服務(wù)組合中作為等價(jià)物，隨著請(qǐng)求傳遞，在保證各方保護(hù)效果的前提下，降低門檻、促進(jìn)合作.

本文在第2節(jié)中討論相關(guān)工作;在第3節(jié)中提出單一服務(wù)提供方的問(wèn)題建模、解決方法和安全性證明;在第4節(jié)中提出涉及到多個(gè)服務(wù)提供方協(xié)作時(shí)的問(wèn)題建模、引入Merkle樹并給出相應(yīng)證明;在第5節(jié)討論實(shí)現(xiàn)與部署策略;第6節(jié)介紹實(shí)驗(yàn)規(guī)劃;最后進(jìn)行討論并對(duì)文章做出總結(jié).

2 相關(guān)工作

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

審計(jì)類策略通常使用Web后端日志、流量數(shù)據(jù)等信息，運(yùn)用語(yǔ)法分析、模式識(shí)別、統(tǒng)計(jì)和神經(jīng)網(wǎng)絡(luò)等手段，對(duì)產(chǎn)生資源濫用的自動(dòng)化訪問(wèn)進(jìn)行識(shí)別，并根據(jù)來(lái)源地址或提取的特征進(jìn)行過(guò)濾.此類方法已有諸多大規(guī)模應(yīng)用［7］，普遍能夠?qū)①Y源濫用的規(guī)模降低一個(gè)數(shù)量級(jí)以上［4］，但系統(tǒng)相對(duì)較為復(fù)雜，有一定的運(yùn)行時(shí)開(kāi)銷，也給實(shí)現(xiàn)和維護(hù)工作帶來(lái)了一定壓力.

圖靈測(cè)試類策略中應(yīng)用最廣泛的是驗(yàn)證碼，如CAPTCHA(Completely Automated Public Turing test to tell Computers and Humans Apart)系統(tǒng)［6］，可以有效區(qū)分人類和機(jī)器的訪問(wèn)請(qǐng)求.但是驗(yàn)證碼的大批量識(shí)別機(jī)制也發(fā)展迅速，主要有基于機(jī)器學(xué)習(xí)的識(shí)別方案［8］和眾包人工識(shí)別［9］.由于無(wú)法對(duì)攻擊者進(jìn)行識(shí)別，應(yīng)用此類方案的服務(wù)提供者通常會(huì)尋求盡可能嚴(yán)格的測(cè)試方法，試圖禁止一切自動(dòng)化訪問(wèn)，也就對(duì)服務(wù)間的交互產(chǎn)生了極大的阻礙.

3 直接應(yīng)用PoW的方案

本節(jié)在單一服務(wù)提供者的環(huán)境中討論P(yáng)oW安全性的定義和具體方案:首先給出一份可行的定義;然后闡述在Web API請(qǐng)求全文上使用PoW的系統(tǒng)的基本方法，并舉出對(duì)其進(jìn)行重放攻擊［10］的場(chǎng)景;最后給出一種加鹽方案，通過(guò)證明其不受重放攻擊影響，證明其安全性.

需要說(shuō)明的是，這里對(duì)PoW系統(tǒng)的形式化與數(shù)字貨幣領(lǐng)域使用的形式化方法略有不同，使用“價(jià)值”而非“難度”的概念來(lái)描述工作數(shù)量，更加直觀，便于服務(wù)提供者完成建模和部署工作.相應(yīng)的模型對(duì)每個(gè)用戶、每次訪問(wèn)都獨(dú)立提出“價(jià)值”要求，并不存在全局的難度設(shè)置.用戶不需要對(duì)抗全網(wǎng)的PoW算力，也就不會(huì)產(chǎn)生礦池壟斷服務(wù)資源.

3.1 問(wèn)題定義

服務(wù)提供者定義一個(gè)價(jià)格函數(shù) Pu，t(r)表示在t時(shí)刻用戶u使用請(qǐng)求r獲得其服務(wù)需付出的代價(jià)，即只要訪問(wèn)者付出足夠代價(jià)，就將其服務(wù)請(qǐng)求視為合理，不認(rèn)定為資源濫用.這一價(jià)格P可以根據(jù)服務(wù)提供者持有的任何信息來(lái)進(jìn)行調(diào)節(jié)，包括但不限于請(qǐng)求規(guī)模、頻率、系統(tǒng)負(fù)載等.

將用戶u在t時(shí)刻已付出的代價(jià)記為 Cu，t，已完成的合理服務(wù)請(qǐng)求記為多重集Ru，t，tr為請(qǐng)求 r實(shí)際發(fā)生的時(shí)間，則PoW保護(hù)系統(tǒng)的安全性可以定義如下:

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

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

定義1可以寫成增量形式，即任何用戶在任何時(shí)刻新發(fā)出合理的服務(wù)請(qǐng)求都必須新付出服務(wù)提供者指定的代價(jià).

在開(kāi)銷和價(jià)格上同時(shí)忽略發(fā)起請(qǐng)求涉及的額外開(kāi)銷，只考慮PoW要求用戶完成的工作，則安全性可進(jìn)一步拆分成以下三個(gè)屬性:

1)用戶無(wú)法繞過(guò)PoW保護(hù)系統(tǒng)獲得服務(wù).這一點(diǎn)需要在軟件實(shí)現(xiàn)和部署上保障，不在本文討論范圍.

2)不存在開(kāi)銷的期望小于具體算法聲稱值的方法允許用戶通過(guò)PoW系統(tǒng)的檢驗(yàn)，即用戶無(wú)法“繞過(guò)”工作.這一點(diǎn)已經(jīng)在密碼學(xué)上有了一定保障［2］，在數(shù)字貨幣領(lǐng)域得到了廣泛驗(yàn)證，并不斷有新的研究給出更強(qiáng)的保障［11］.

3)重放安全性，即用戶無(wú)法使用同一份工作通過(guò)PoW系統(tǒng)檢驗(yàn)兩次.

由此可知，在使用已得到充分驗(yàn)證的PoW算法時(shí)，本文構(gòu)造的PoW保護(hù)系統(tǒng)在結(jié)構(gòu)上只需保證重放安全性即可達(dá)成保護(hù)目標(biāo).重放安全性的形式化定義在下一小節(jié)討論基本方法時(shí)給出.

3.2 基本方法

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

價(jià)值函數(shù)通常分兩個(gè)階段完成:哈希驗(yàn)證階段 Hv(proof)返回一個(gè)定長(zhǎng)二進(jìn)制串h或(當(dāng) proof完全無(wú)效時(shí))返回ε表示失敗;估價(jià)階段V'(h)將該二進(jìn)制串映射到工作數(shù)量，并對(duì) h=ε的情況輸出0.

請(qǐng)求者使用相應(yīng)地使用一個(gè)工作算法W(r，p)求出一個(gè)可行的n使V(r，n)大于當(dāng)前時(shí)刻服務(wù)提供者要求的 Pu，t(r).工作算法W枚舉大量n的取值并運(yùn)行一個(gè) Hs(proof)過(guò)程直到其返回的 h滿足V'(h)＞Pu，t(r).Hs過(guò)程的大量重復(fù)構(gòu)成了PoW的核心，其“無(wú)法繞過(guò)”的屬性已經(jīng)在上一節(jié)中進(jìn)行了討論.

在大部分PoW算法體系中，Hv=Hs，但由于價(jià)值函數(shù) V只包含一次Hv，其計(jì)算開(kāi)銷較小，使該系統(tǒng)在服務(wù)器一側(cè)的資源占用保持在較低的水平.某些算法［12］還使用了比 Hs輕量的 Hv，進(jìn)一步減輕服務(wù)器驗(yàn)證開(kāi)銷.

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

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

對(duì)這一系統(tǒng)進(jìn)行重放攻擊非常簡(jiǎn)單，用戶求得有效的 n后只需將整個(gè)proof發(fā)送兩次，即可獲得兩次服務(wù)，但實(shí)際只完成了一份工作.

由于proof和具體工作具有直接對(duì)應(yīng)的關(guān)系，我們可以借助它來(lái)對(duì)重放安全性進(jìn)行定義:

定義2.(重放安全性).單一服務(wù)提供者的PoW 保護(hù)系統(tǒng)的重放安全性指其識(shí)別曾經(jīng)通過(guò)驗(yàn)證的 proof且拒絕其再次通過(guò)驗(yàn)證的能力.

3.3 加鹽的方法

在基本方法中，服務(wù)器因?yàn)闆](méi)有保存關(guān)于過(guò)往或未來(lái)proof的任何信息，所以會(huì)受到重放攻擊而無(wú)法保證安全性.服務(wù)器顯然可以記錄所有已通過(guò)驗(yàn)證的 proof并拒絕其再次通過(guò)，但是這種手段要實(shí)現(xiàn)重放安全就必須進(jìn)行永久存儲(chǔ)，每次將新收到的 proof在其中進(jìn)行檢查的代價(jià)會(huì)逐漸增大，使這種方法不適合長(zhǎng)期使用.

對(duì)抗重放攻擊的核心思路是讓proof中n以外的部分及時(shí)改變.服務(wù)提供者可以通過(guò)在請(qǐng)求上追加一個(gè)能夠及時(shí)變化的鹽來(lái)完成，即令 proof=(r，salt，n)，其中 salt為服務(wù)器選擇的鹽.這時(shí)工作算法的參數(shù)也相應(yīng)改變，訪問(wèn)者的計(jì)算工作變?yōu)?W((r，salt)，p).每當(dāng) salt改變，舊的 n無(wú)法通過(guò)驗(yàn)證，訪問(wèn)者如需再次請(qǐng)求服務(wù)，就需要重新運(yùn)行工作.

定理1.加鹽的PoW 保護(hù)系統(tǒng)具有重放安全性，當(dāng)且僅當(dāng)服務(wù)器給同一個(gè)鹽salt提供不超過(guò)一次服務(wù).

證明:必要性由3.2節(jié)末尾的例子可知，以下證充分性.salt改變則(r，salt)改變，那么攻擊者無(wú)法使用原有的 n和新的salt通過(guò)價(jià)值函數(shù)V驗(yàn)證;如果攻擊者使用原有的salt請(qǐng)求服務(wù)，則服務(wù)器會(huì)因?yàn)?salt失效而拒絕.證畢.

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

沿用第2節(jié)中的場(chǎng)景，如果航空公司使用了加鹽的PoW保護(hù)系統(tǒng)，則訂票平臺(tái)首次請(qǐng)求服務(wù)的流程如圖1所示.

圖1 航空訂票場(chǎng)景使用加鹽PoW保護(hù)系統(tǒng)時(shí)的交互Fig.1 Interaction of a salted PoW system in an airline booking scenario

如果航空公司在這一請(qǐng)求的回應(yīng)中附帶了一個(gè)新的salt，那么訂票平臺(tái)的下一次請(qǐng)求就無(wú)需再請(qǐng)求參數(shù)，可以直接執(zhí)行工作過(guò)程W并請(qǐng)求服務(wù).

4 帶有Merkle樹的方案

不難發(fā)現(xiàn)，無(wú)論在多服務(wù)提供者的環(huán)境中如何定義PoW系統(tǒng)的安全性，只要不與定義1產(chǎn)生沖突，加鹽的方案都能夠有效對(duì)Web API進(jìn)行保護(hù).

在有復(fù)雜的服務(wù)組合的場(chǎng)景中，如果參與的每一個(gè)調(diào)用者都需要進(jìn)行工作過(guò)程W的調(diào)用來(lái)計(jì)算n，就會(huì)造成較大的計(jì)算資源浪費(fèi).

為了消除這種資源浪費(fèi)對(duì)大型系統(tǒng)的不利影響，需要對(duì)PoW保護(hù)系統(tǒng)進(jìn)行適當(dāng)?shù)姆艑?本節(jié)嘗試將最終調(diào)用者提交的PoW證明作為組織間服務(wù)調(diào)用的等價(jià)物，降低服務(wù)提供者之間API調(diào)用的開(kāi)銷.我們首先給出該場(chǎng)景中安全性和重放安全性的一組可行定義，然后介紹在保護(hù)系統(tǒng)中使用Merkle樹［3］的方法并證明其具有重放安全性.

4.1 問(wèn)題定義

對(duì)3.1節(jié)中安全性的定義進(jìn)行調(diào)整，加入對(duì)服務(wù)提供者的表述，可以得到多方協(xié)作環(huán)境中安全性的一個(gè)可行定義:

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

相似地，也可以給出對(duì)應(yīng)的安全性的定義:

定義4.(多提供者重放安全性).多服務(wù)提供者PoW 保護(hù)系統(tǒng)的重放安全性，指其中包含的每一個(gè)單一服務(wù)提供者的PoW保護(hù)系統(tǒng)都具有重放安全性.即其中每個(gè)服務(wù)提供者都具有識(shí)別曾經(jīng)通過(guò)驗(yàn)證的proof且拒絕其再次通過(guò)驗(yàn)證的能力.

以上定義是可行的，由3.1節(jié)中服務(wù)提供者定義價(jià)格函數(shù)P的方式可知，單個(gè)服務(wù)提供者只要求調(diào)用者付出相應(yīng)代價(jià)，并不關(guān)心系統(tǒng)的其他參與者，即可以允許同一個(gè)PoW證明被用于請(qǐng)求其他提供者的服務(wù).

4.2 具體方案

要保證保護(hù)效果，多提供方場(chǎng)景中的PoW計(jì)算工作開(kāi)始前指定若干對(duì)具體的請(qǐng)求全文r和鹽salt.這要求發(fā)起請(qǐng)求時(shí)攜帶的證明必須包含(或引用)一個(gè)結(jié)構(gòu)來(lái)記錄這些數(shù)據(jù)，提交給服務(wù)器完成驗(yàn)證.

出于嚴(yán)謹(jǐn)考慮，我們保持PoW證明的定義不變，指“完成了工作”的證明，而將本節(jié)中使用Merkle樹實(shí)現(xiàn)的“請(qǐng)求已被PoW證明指定”所需的額外數(shù)據(jù)稱為Merkle證明.此時(shí)要獲得服務(wù)，請(qǐng)求方不僅需要發(fā)送PoW證明，還需要發(fā)送對(duì)應(yīng)的Merkle證明.

取一個(gè)常用的哈希算法 H，將 (H(r，salt)，H(node))作為一個(gè)請(qǐng)求單元，則本節(jié)的系統(tǒng)中使用的Merkle樹節(jié)點(diǎn)定義為由請(qǐng)求單元組成的非空集合，其中H(node)通過(guò)哈希完成對(duì)一個(gè)子節(jié)點(diǎn)的引用.這一集合需要實(shí)際實(shí)現(xiàn)為數(shù)組以便完成哈希操作.

由于樹結(jié)構(gòu)上有以下公理:

公理1.節(jié)點(diǎn) n在樹 T中當(dāng)且僅當(dāng) n是 T的根節(jié)點(diǎn)，或其父節(jié)點(diǎn)在T中.

這時(shí)，服務(wù)請(qǐng)求者可以從 H(r，salt)所在的節(jié)點(diǎn)開(kāi)始逐級(jí)給出父節(jié)點(diǎn)直到樹根，記作［node］，證明 H(r，salt)記錄在 Merkle 樹 T.三元組 (H(r，salt)，H(root(T))，［node］)稱為Merkle證明，其中root(T)為對(duì)應(yīng)Merkle樹的根節(jié)點(diǎn).

由于Merkle樹中已經(jīng)記錄了請(qǐng)求和鹽，上一節(jié)中的PoW證明無(wú)需重復(fù)記錄，即令 proof=(H(root(T))，nonce).使服務(wù)器先進(jìn)行Merkle驗(yàn)證，則:

定理2.使用Merkle樹的PoW系統(tǒng)具有多提供者重放安全性，當(dāng)且僅當(dāng)每個(gè)服務(wù)器對(duì)H(root(T))相同的Merkle證明只接受不超過(guò)一次.

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

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

推論1.服務(wù)器對(duì)每個(gè)通過(guò)PoW驗(yàn)證的請(qǐng)求記錄根節(jié)點(diǎn)哈希值H(root(T))，至收到該請(qǐng)求前發(fā)出的所有鹽都已失效為止，拒絕后續(xù)使用同一 H(root(T))的Merkle證明，整個(gè)PoW保護(hù)系統(tǒng)具有多提供者重放安全性.

這時(shí)最終用戶請(qǐng)求服務(wù)的過(guò)程可以描述如下:

1)預(yù)先獲取價(jià)值函數(shù) V和服務(wù)價(jià)格 Psp，u，tr(r);

2)向服務(wù)器請(qǐng)求鹽salt和一個(gè)子節(jié)點(diǎn)c的引用H(c);

3)以r、salt和H(c)組成一個(gè)請(qǐng)求單元，與其他請(qǐng)求單元(如果有)，一起構(gòu)造根節(jié)點(diǎn)root(T);

4)調(diào)用工作算法W求得n;

5)將PoW證明和Merkle證明隨各個(gè)請(qǐng)求發(fā)送給服務(wù)器.

服務(wù)器驗(yàn)證請(qǐng)求后可以根據(jù)價(jià)值函數(shù) V的輸出，選擇是否將該份證明用于事先在子節(jié)點(diǎn)c中記錄的服務(wù)請(qǐng)求.這時(shí)只需將c的某個(gè)子節(jié)點(diǎn)c'加到［node］中并以對(duì)應(yīng)的請(qǐng)求替換掉 H(r，s)，就可以組成新的Merkle證明，用于請(qǐng)求預(yù)先選定的其他服務(wù).

在先前的場(chǎng)景中，訂票平臺(tái)可以事先向若干航空公司請(qǐng)求參數(shù)，并準(zhǔn)備好一棵包含若干請(qǐng)求的Merkle樹.最終用戶(旅客)向訂票平臺(tái)請(qǐng)求服務(wù)時(shí)，將這棵樹的引用作為參數(shù)交給用戶.訂票平臺(tái)可以進(jìn)一步在用戶提交的Merkle證明上追加節(jié)點(diǎn)，使對(duì)應(yīng)的PoW證明能夠用于向?qū)?yīng)的航空公司請(qǐng)求服務(wù)，如圖2所示.

圖2 航空訂票場(chǎng)景使用帶有Merkle樹的PoW保護(hù)系統(tǒng)時(shí)的交互Fig.2 Interaction of a PoW system with Merkle tree in an airline booking scenario

如果航空公司要求的價(jià)值低于訂票平臺(tái)向用戶要求的價(jià)值，那么每個(gè)PoW證明都能成功傳遞;反之，訂票平臺(tái)則需要篩選出價(jià)值符合航空公司要求的PoW證明.這一操作與數(shù)字貨幣“礦池”［13］相似，從期望上來(lái)看，只要訂票平臺(tái)收取的價(jià)值總和超過(guò)向每一個(gè)航空公司付出的價(jià)值，訂票平臺(tái)的整合服務(wù)就能夠持續(xù)運(yùn)轉(zhuǎn)而不需要進(jìn)行PoW計(jì)算工作.這一過(guò)程并不會(huì)導(dǎo)致訂票平臺(tái)壟斷服務(wù)資源，因?yàn)楹娇展究梢酝ㄟ^(guò)訪問(wèn)來(lái)源地址進(jìn)行區(qū)分:來(lái)自訂票平臺(tái)的訪問(wèn)規(guī)模大、頻率高，因而工作量要求高;一般用戶訪問(wèn)規(guī)模小、頻率低，工作量要求低，可以很快完成.

由于樹節(jié)點(diǎn)的引用中加了鹽，這一整合服務(wù)調(diào)用過(guò)程中所有請(qǐng)求都只對(duì)直接相關(guān)的參與者(請(qǐng)求者和提供者)可見(jiàn).系統(tǒng)的參與者還可以在哈希函數(shù)H的值域中生成隨機(jī)數(shù)，作為節(jié)點(diǎn)引用填入Merkle樹中，進(jìn)一步對(duì)元數(shù)據(jù)進(jìn)行保護(hù).

與3.3節(jié)中相似，服務(wù)器仍然可以在應(yīng)答中附帶新的鹽和子節(jié)點(diǎn)引用，但因?yàn)榄h(huán)境發(fā)生了較大變化，放寬重放安全性的策略可能會(huì)對(duì)系統(tǒng)的其他部分產(chǎn)生作用，是否影響安全性還有待進(jìn)一步研究.

5 實(shí)現(xiàn)與部署

作為一個(gè)軟件系統(tǒng)，PoW能夠投入使用需要滿足功能、性能等各方面的屬性，僅完成證明是不夠的.本節(jié)討論該系統(tǒng)在實(shí)現(xiàn)和部署時(shí)需要注意的問(wèn)題及應(yīng)對(duì)策略，供后續(xù)研發(fā)和部署工作參考.

價(jià)值函數(shù)V需要調(diào)用Hv函數(shù)，隨著請(qǐng)求的增加，會(huì)積累顯著的資源開(kāi)銷.為了防止在此處構(gòu)造DoS攻擊，PoW保護(hù)系統(tǒng)必須與黑名單系統(tǒng)相連——連續(xù)多次PoW驗(yàn)證失敗的用戶需要被及時(shí)加入黑名單，以防其發(fā)送大量隨機(jī)生成的無(wú)效PoW證明，大量觸發(fā)驗(yàn)證過(guò)程，消耗服務(wù)器資源.

理想情況下，包括PoW在內(nèi)的服務(wù)保護(hù)系統(tǒng)與服務(wù)本身的業(yè)務(wù)邏輯應(yīng)該完全解耦，以免影響服務(wù)本身的操作和維護(hù)屬性.為了實(shí)現(xiàn)這一目標(biāo)，PoW系統(tǒng)需要部署在前置的反向代理設(shè)施中.企業(yè)中出于負(fù)載均衡等需求，通常已部署nginx1https://www.nginx.com/或haproxy2https://www.haproxy.org/等軟件在此位置，則PoW系統(tǒng)的服務(wù)器端組件可以實(shí)現(xiàn)為相應(yīng)軟件的插件，并配置為優(yōu)先于其他插件調(diào)用，以防緩存等功能使部分請(qǐng)求漏過(guò).如第3、4https://github.com/dashpay/dash_hash/blob/master/dash.c節(jié)所述，PoW 系統(tǒng)需要短期存儲(chǔ)少量數(shù)據(jù)提供重放安全性，這些數(shù)據(jù)應(yīng)當(dāng)存儲(chǔ)在獨(dú)立的數(shù)據(jù)庫(kù)(如redis3https://redis.io/)中，以防對(duì)其他業(yè)務(wù)產(chǎn)生管理上或者性能上的串?dāng)_.

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

表1 常見(jiàn)PoW算法及特點(diǎn)Table 1 Common PoW algorithm and characteristics

6 實(shí)驗(yàn)規(guī)劃

在保護(hù)效果、可控性、性能開(kāi)銷和可維護(hù)性等方面，PoW方案需要通過(guò)實(shí)驗(yàn)與現(xiàn)有方案進(jìn)行比較.其中涉及實(shí)際攻擊者的行為(在攻擊代價(jià)大幅上升時(shí)如何應(yīng)對(duì)等)，無(wú)法通過(guò)流量鏡像和模擬攻擊等方式完成，必須進(jìn)行實(shí)際部署并收集數(shù)據(jù).為了盡可能減少實(shí)驗(yàn)本身給現(xiàn)有系統(tǒng)帶來(lái)的風(fēng)險(xiǎn)，我們將方法本身及證明過(guò)程公開(kāi)5https://github.com/davidgao/POWonWEB，收集相關(guān)反饋，并在實(shí)現(xiàn)和后續(xù)部署時(shí)進(jìn)行相應(yīng)的調(diào)整.

7 討論

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

在一些攻擊場(chǎng)景中，這個(gè)“做與不做”的選擇也可以協(xié)助其他系統(tǒng)完成一定程度的識(shí)別和防御:在較高的服務(wù)價(jià)格下，如果攻擊者不完成PoW計(jì)算工作，會(huì)被PoW驗(yàn)證過(guò)程篩出而拒絕訪問(wèn);如果攻擊者繼續(xù)完成PoW計(jì)算，又會(huì)顯著拖慢攻擊進(jìn)程，提高攻擊代價(jià).尤其在需要多個(gè)請(qǐng)求才能完成攻擊時(shí)，PoW系統(tǒng)也能夠起到輔助保護(hù)作用.

相應(yīng)的，PoW系統(tǒng)也存在一些已知的局限性.其一在于，特定場(chǎng)合(如設(shè)計(jì)上存在大規(guī)模突發(fā)訪問(wèn)的服務(wù))中對(duì)服務(wù)價(jià)格函數(shù)P的設(shè)計(jì)比較困難，有潛在可能影響到3.1節(jié)中假設(shè)的可滿足性;其二在于，PoW作為密碼學(xué)應(yīng)用，向運(yùn)行環(huán)境中引入了新的因素，如果設(shè)計(jì)、實(shí)現(xiàn)或部署不當(dāng)，可能產(chǎn)生額外的攻擊面.

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

8 結(jié)論

開(kāi)放公共訪問(wèn)的Web服務(wù)常常需要進(jìn)行防止資源濫用的保護(hù)，而現(xiàn)有的保護(hù)系統(tǒng)未能在保護(hù)效果、服務(wù)質(zhì)量和合作能力等指標(biāo)上達(dá)成一致.

本文提出了一類將PoW系統(tǒng)用于公共Web服務(wù)保護(hù)的方法，在不削弱保護(hù)效果的條件下，降低組織間服務(wù)整合的門檻.我們對(duì)兩種具體方法的有效性進(jìn)行了證明，并簡(jiǎn)要討論了實(shí)現(xiàn)、部署策略和已知的局限性.其中加鹽的方法較為簡(jiǎn)單、易于實(shí)現(xiàn)且提供更好的保護(hù)效果，但在服務(wù)組合大量出現(xiàn)的復(fù)雜系統(tǒng)中可能產(chǎn)生資源浪費(fèi);使用Merkle樹的方法相對(duì)復(fù)雜，在保護(hù)上進(jìn)行了適當(dāng)?shù)姆潘桑乐沽诉@種浪費(fèi)的發(fā)生，并降低了合作門檻，促進(jìn)了Web服務(wù)資源的優(yōu)化分配.

PoW系統(tǒng)用于Web服務(wù)保護(hù)的方案尚不成熟，存在一些子問(wèn)題有待后續(xù)研究，主要包括:如何對(duì)服務(wù)價(jià)值進(jìn)行有效建模、多服務(wù)提供者環(huán)境中的安全性是否應(yīng)該進(jìn)一步放寬、Merkle樹方法中是否存在潛在攻擊面等.

PoW系統(tǒng)允許服務(wù)提供者將其服務(wù)價(jià)值模型投入到Web服務(wù)保護(hù)系統(tǒng)中，適當(dāng)放行機(jī)器流量換取合作機(jī)會(huì)，給互聯(lián)網(wǎng)服務(wù)提供者提供新的思路.