基于區塊鏈的密封式投標拍賣方案

李 蓓，張問銀，王九如，趙 偉，王海峰

（1.山東科技大學計算機科學與工程學院，山東青島 266000；2.臨沂大學信息科學與工程學院，山東臨沂 276000）

0 引言

隨著互聯網技術和電子商務的迅速發展，電子拍賣已經成為人們拍賣商品的一種方式。網絡拍賣平臺為買賣雙方提供一個公平交易的拍賣環境，節省了大量的時間和成本，但其隱私性和安全性問題也越來越突出。傳統的電子拍賣有四種主要的拍賣方式：第一價格密封投標拍賣、第二價格密封投標拍賣（Vickrey 拍賣）、公開升價拍賣（英式拍賣）以及公開降價拍賣（荷式拍賣）。電子拍賣根據競拍價是否公開分為密封式投標拍賣和公開拍賣。密封式投標拍賣是指在規定時間內由競買人秘密地提交標書，在規定時間后才能打開投標并根據拍賣規則選出中標者。在密封式投標拍賣中，除了中標者的標價被公開以外，其余競買人的報價都保密，可以有效保護競買人身份的匿名性和標價的隱私性，在當今社會是應用廣泛的拍賣方式。本文討論的方案屬于第一價格的密封式投標拍賣。為了保證密封式投標拍賣的安全性，需要滿足以下基本特性：

1）正確性。拍賣必須保證能產生最高價格的中標者。

2）公平性。保證參與拍賣的競買人的地位相同，獲得信息一致，是否中標只與出價高低有關。

3）密封性。在打開標書前，無法通過別的方式獲取價格。

4）不可否認性。中標者在競標成功后不可以對自己的出價進行否認。

5）可驗證性。任何人都可以驗證中標者的身份。

6）時限性。在規定時間前提交標書才能有效參與拍賣，并且在提交標書后在規定時間后才能統一打開標書。

7）不可偽造性。任何人不能用偽造的身份參與競拍活動。

目前針對密封式投標拍賣已經存在大量研究。Brandt［1-2］設計了一個無第三方參與的密封電子拍賣協議，協議有效去除了第三方，可以很好地保護競標者的隱私；但由于所有計算都需拍賣人自己完成，具有計算量和通信量較大以及效率不高的問題。Bogetoft 等［3］提出使用基于線性秘密共享的安全多方計算取代可信第三方來構建安全拍賣協議，但該方案需要至少15輪交互。Wu等［4］提出了新的密封式電子拍賣，雖然該方案去除了第三方，但是交互過程也比較繁瑣。Lee等［5］和Sun 等［6］分別設計出了基于群簽名的密封電子拍賣協議及改進方案。王鑫等［7］利用基于身份的群簽名方案和可驗證的秘密共享協議，設計了一個密封式的電子拍賣方案，該方案實現了投標者的匿名性、強壯性、中標者的不可抵賴性、公開可驗證性和標價的保密性等一般性的安全要求。程文娟等［8］提出一個基于不可信第三方的密封式電子拍賣方案，采用了數字簽名技術對競買人的身份進行驗證，從而保護競買人身份。在計算成交價時，基于離散對數求解的困難性，對競拍價的二進制長度進行加密封裝，以保證競拍價的秘密性以及結果的正確性。曹剛［9］通過改造Bit 承諾協議，將盲簽名技術應用于Bit 承諾協議的生成階段，設計了一種密封式的電子拍賣方案。目前，大多數的密封式電子拍賣都依賴于第三方去管理和驗證拍賣者的身份信息；但是，現實中無法保證存在完全可信的第三方，一旦第三方不誠實或者與競買人勾結，將會違反拍賣的公平性，并且威脅到其他競買人隱私和利益。

而隨著區塊鏈技術的不斷發展，越來越多的研究嘗試通過將區塊鏈作為基礎設施，利用區塊鏈的特性，實現拍賣的公開透明性、不可篡改性等。區塊鏈作為一個公開透明的賬本，所具有的分布式容錯、不可篡改性、去中心化等特性，使得區塊鏈成為一個適合密封式電子拍賣的平臺。基于區塊鏈的密封式投標拍賣可以有效去除第三方，從而節省第三方拍賣中心的費用。拍賣活動的穩定進行依賴于拍賣系統的安全性和穩定性，區塊鏈上的數據不可篡改性并且可追溯，一旦交易確認，無法修改歷史記錄，保證投標后拍賣報價就不可修改和撤銷。區塊鏈上地址的匿名性也可以保證競買人的身份隱私。目前已有一些研究通過區塊鏈來實現密封式投標拍賣。如Galal 等［10］提出了一個智能合約，用于以太坊區塊鏈上的可驗證密封競價拍賣方案，協議確保了拍賣結果公開的可驗證性、投標的保密性和公平性。Galal 等［11］又提出了一種在以太坊區塊鏈上基于簡潔非交互式零知識證明zk-SNARKs（zeroknowledge Succinct Non-interactive ARgument of Knowledge）的拍賣方案，通過拍賣人和競買人之間的多方安全計算協議生成zk-SNARKs 的證明和驗證密鑰，該方案可以解決競買人與拍賣行間的信任問題。彭燁等［12］提出了一種基于區塊鏈和并發簽名的密封式投標拍賣方案，利用并發簽名的模糊性保護競標者的信息不被泄露，同時保證標價的保密性和競標者的匿名性和不可否認性。Xiong 等［13］介紹了基于聯盟鏈的密封競標拍賣協議，利用數字證書的身份機制和基于橢圓曲線技術的盲簽名來允許競標者匿名參與，并采用定時釋放公鑰加密算法對競拍進行加密，防止拍賣人與競拍人串通。

本文針對目前競拍系統中的隱私泄露、不可公開驗證等缺陷，提出了一種基于區塊鏈的密封式投標拍賣方案。通過區塊鏈上的安全保證金策略約束競買人行為，利用Pedersen承諾方案保護競買人的信息不被泄露，利用同態加密的加法同態性進行密文的算術運算，競買人可以利用零知識范圍證明來驗證中標價格的正確性。

1 預備知識

1.1 區塊鏈

2008 年中本聰在《比特幣：一種點對點電子現金系統》［14］一文中首次提出區塊鏈的概念。區塊鏈本質上是一種多方參與共同維護的分布式數據庫，采用對等網絡（Peer-to-Peer，P2P）的網絡通信方式，通過密碼學技術保護隱私，利用智能合約［15］實現業務邏輯，依賴分布式共識技術實現存儲一致。與傳統的數據結構不同，區塊鏈采用鏈式結構存儲，將數據記錄組織成區塊（Block），并在每個區塊的區塊頭中通過記錄前一區塊的哈希值將區塊組織成鏈式結構。

區塊鏈在走向應用之前，必須解決隱私問題。在區塊鏈中主要保護兩類隱私：身份隱私和交易隱私［16-17］。保護身份隱私是指減少用戶身份與區塊鏈地址之間的關聯。在區塊鏈上用戶可以創建多個地址，與用戶的身份無關，并且創建過程不需要第三方參與。因此通過地址信息很難將用戶身份關聯起來，相較于傳統創建的地址信息來說具有較好的匿名性。保護交易隱私是指保護在區塊鏈中存儲的交易記錄和交易隱藏的信息（如交易金額、用戶的消費水平等）。目前區塊鏈主要采用隱蔽地址［18］、同態加密［19］、零知識證明［20］等方案保護隱私。

1.2 承諾方案

在機密交易中，可以用Pedersen 承諾算法［21］保護交易金額的隱私性。該承諾算法由承諾者向接收者承諾某個秘密數，即生成某個承諾值。接下來通過展示該秘密數，由接收者確認前后承諾值是否相等。基于橢圓曲線的Pedersen 承諾算法表現形式如下：

其中：C為橢圓曲線上的一個曲線點，作為承諾值；a為需要承諾的秘密數；r為隨機數值；G為所選擇橢圓曲線上的生成元；H為橢圓曲線上的另一個基點。

基于橢圓曲線問題的難解性，該承諾方案是抗沖突的并且不會泄露被承諾的信息，因此具有隱藏性和綁定性；而且該承諾方案滿足加法同態性，即：

1.3 零知識證明Bulletproofs

零知識證明是指證明者能夠在不向驗證者提供任何有用信息的情況下，使驗證者相信某個論斷是正確的。Bulletproofs［22］是一種新的非交互式零知識證明協議，具有證明時間短、不需要可信設置的特點。從計算要求上看，該證明系統的性能優于zk-SNARKs［23］和zk-STARKs（zero-knowledge Succinct Transparent ARgument of Knowledge）［24］，且在加密貨幣系統中具有實用性。Bulletproofs 可以證明交易的金額在給定的正區間內，這對驗證交易至關重要。它依賴于Pedersen承諾來隱藏秘密輸入并提供計算完整性檢查。

具體過程如下：

2 競拍方案

在本章中描述了基于區塊鏈的密封式投標拍賣方案的具體流程。在競拍流程中利用Pedersen 承諾方案保護競買人的信息不被泄露，將零知識范圍證明與承諾機制結合，可以在不泄露中標者身份信息的情況下進行驗證，保證中標者身份不可偽造和中標價格的正確性，在不泄露隱私的情況下，能夠高效地完成競拍任務。

2.1 競拍流程

拍賣方案總共分為拍賣準備階段、任務發布階段、競標階段、公開中標者承諾階段、證明階段、驗證階段和拍賣完成階段。該方案包含三個實體：拍賣者、競買人和拍賣合約。拍賣者需要將想要拍賣的物品信息這個任務發布到區塊鏈中，因區塊鏈具有產生新數據塊的屬性，待區塊鏈產生新塊時，這個任務發布成功。在身份注冊成功后，競買人可以查看區塊鏈中已有的拍賣任務，對感興趣的任務進行競價。為了保證競拍有意義，拍賣合約將進行相應的計算，判斷最低競價的數量，在競買人數量大于等于2 時，競拍任務繼續進行。接下來，各個競買人提交報價承諾，最終由拍賣人公布中標者的承諾值。其余競買人將會驗證收到的證明記錄，驗證通過后可以結束拍賣。拍賣服務整體流程如圖1所示。

圖1 拍賣服務流程Fig.1 Flowchart of auction service

2.2 競拍階段

2.2.1 符號介紹

2.2.2 拍賣準備階段

拍賣方案包含三個實體：拍賣者、競買人、拍賣合約。各個參與方在使用拍賣合約之前，競買人和拍賣者必須進行注冊成為合法用戶才能參與拍賣。注冊成功后用戶持有一對公鑰、私鑰和一個身份ID，身份ID 將以哈希值Hash（ID）的形式存儲在區塊鏈中。

算法1 拍賣準備階段算法。

2.2.3 任務發布階段

拍賣者使用智能合約賬戶的公鑰對身份ID 進行加密得到E(H(Uid))；

拍賣方利用智能合約初始化拍賣狀態，并提交拍賣要求。

智能合約根據其私鑰進行解密得到競買人的身份信息H(Uid)′并判斷等式H(Uid)=H(Uid)′是否成立，如若成立，則身份驗證成功；否則，丟棄該拍賣任務。

算法2 任務發布階段算法。

2.2.4 競標環節

首先競買人Pi需要完成和拍賣方相同的身份認證，僅當通過身份認證的競買人才能參加競拍活動。Pi瀏覽已經發布在區塊鏈中的任務，在提交承諾截止時間T3之前，對自己感興趣的任務進行投標，即在區塊鏈中發布自己的報價承諾：Ci=xiG+riH，每個競買人Pi將xi、ri通過拍賣方的公鑰加密后發送到區塊鏈上。

智能合約在判定當前時間T小于T3后，判斷在競買人Pi有足夠余額的情況下，從Pi賬戶扣除保證金，轉入到合約的保證金賬戶中。隨后將競買人Pi加入到競買人集合中，并將競買人的報價承諾存儲在區塊鏈上。完成執行上述操作后，Pi投標成功。為了保證此次拍賣活動有意義，智能合約會判斷投標人數num，僅當拍賣活動num≥2時，拍賣可繼續進行。

算法3 競標環節算法。

2.2.5 公開中標者承諾階段

拍賣方在T2時利用私鑰得到xi'、ri'，重新計算出承諾值C'，判斷C=C′，若相等則認為競買者誠實的在區塊鏈上發布承諾值。拍賣方選擇最高報價W作為中標價。拍賣方公布中標者承諾CW，而不公布中標者的真實報價。

算法4 公開中標者承諾階段算法。

2.2.6 證明階段

假設失敗的競買人報價為L，承諾為CL，則d=W-L，Cd=CW-CL。如果W＞L，則d＞0。拍賣方打開承諾后，計算出差價d，根據Pedersen 承諾計算出Cd，發送給每一個競買人。

算法5 證明階段算法。

2.2.7 驗證階段

其余競買人作為一個獨立的驗證者，首先根據中標者的公開承諾和自己的承諾計算，用Cd來確保他們收到正確的證明記錄。競買人利用Cd'=CW-CL，比較Cd是否等于Cd'。若相等，則其余失敗競買人可以確認拍賣方發送給他們的承諾值Cd是正確的。

拍賣方設置零知識范圍證明，證明d位于范圍[0，2n-1]且不會被泄露，n表示可能的最大出價的位大小，任何出價之間的最大可能差為[-(2n-1)，2n-1]。若L＞W，則d＜0 且群大小p足夠大，則負值d將位于范圍間隔之外。拍賣者向每個驗證者發送一份范圍證明記錄，該記錄使驗證者使用協議來驗證以下關系：

失敗的競買人通過驗證出d的范圍從而得知中標價為最高價。

算法6 驗證階段算法。

2.2.8 拍賣完成階段

智能合約在該階段將所有未中標的誠實參與者的保證金返回其賬戶，中標者則需支付中標與初始保證金F之間的差額。

算法7 拍賣完成階段算法。

3 方案分析

3.1 安全性分析

本文的拍賣方案基于區塊鏈技術，利用承諾值的區間驗證來保護數據隱私，而不泄露任何隱私信息，相較于傳統的中心化存儲具有明顯優勢：去中心化的存儲降低了黑客攻擊的風險，也避免了單一節點失效帶來的系統數據丟失的隱患。本文拍賣方案能有效滿足電子拍賣的需求：

1）正確性。拍賣人在公開中標者承諾階段選擇最高價作為中標者，保障拍賣的正確性。

2）公平性。區塊鏈上所有用戶權利相等，區塊鏈上數據公開透明，所有用戶獲得信息一致。由于拍賣方發起拍賣后需要交納競價保證金F。假設拍賣方不誠實，此時拍賣方既拿不到競價保證金，也無法使拍賣成功進行。

3）密封性。對于拍賣人A、競拍方Pi，在時間T2前對其可見的信息只有承諾值、公鑰加密后的密文。競買人Pi承諾值的(xi，ri)用拍賣者公鑰Pi加密后發送到智能合約賬戶上，對于拍賣人A，在時間T2前對其可見的信息只有承諾值，所以拍賣人A不能將競買人的(xi，ri)發送給其他競買人，從而避免Pi的承諾值被模仿。

4）不可否認性。區塊鏈所具有的不可篡改性，中標者W在競標成功后不可以對自己的出價進行否認。

5）可驗證性。未中標用戶可以通過零知識證明協議驗證證明階段收到的范圍證明的正確性，保證中標價為最高價。

6）時限性。利用智能合約自動觸發的特點，競拍承諾提交后只有在T2時間段才能打開。

7）不可偽造性。拍賣方案開始和最終都有一個身份驗證過程，任何人不能用偽造的身份參與競拍活動。并且假設拍賣人A對競買人Pi是惡意的，聲明競買人Pi發送在智能合約上的密文是無效的。此時誠實的競買人可以在拍賣合約上發出(xi，ri)，拍賣合約通過公鑰Pk加密的值如果發現密文與之前提交的密文相等，將對拍賣人進行處罰，并將保證金退還給Pi，該懲罰由智能合約執行。

3.2 實驗結果分析

本文使用如表1所示的測試環境進行測試。

通過表2 可看出，競拍各個階段運行時間在毫秒以內，運行花費時間在可接受范圍內，基本不會對日常應用造成影響。

表1 實驗環境Tab.1 Experimental environment

表2 不同階段的運行時間 單位：msTab.2 Running times of different stages unit：ms

本文競拍方案與其他方案的對比如表3所示。

表3 方案對比Tab.3 Scheme comparison

基于fabric 對本文方案進行設計實現，實驗如圖2 所示生成了一份報價承諾，圖3 展示了生成的零知識范圍證明，圖4對生成的證明驗證，并驗證成功。實驗結果表明本文方案是可行的。

圖2 生成報價承諾Fig.2 Generating quotation commitment

圖3 生成范圍證明Fig.3 Generating range proof

圖4 驗證收到承諾Fig.4 Verifying commitment received

本文設計了基于區塊鏈的密封式投標拍賣方案。相較于傳統密封式投標拍賣，充分地利用區塊鏈不可篡改、去中心化等特性，有效去除第三方，避免了單點故障和操作的不透明。彭燁等［12］提出的方案所選出的中標價是否的確高于其余競拍價的正確性不可驗證；而本文方案可以驗證中標價的正確性。程文娟等［8］提出的方案滿足匿名性、保密性和不可偽造性，但其不能公開驗證成交價，而是由拍賣中心計算和公布。對比而言，本文方案是由拍賣方公布中標者的承諾，而不公布除承諾以外的信息，利用區塊鏈保證公布信息的真實性。

4 結語

本文提出的基于區塊鏈的密封式投標拍賣方案，在不泄露隱私的情況下，能夠高效地完成競拍任務。本文方案將零知識范圍證明與承諾機制結合，可以在不泄露中標者身份信息的情況下進行驗證，并通過數字貨幣保證金來提高拍賣的公平性和約束競買人的行為。同時，借助于區塊鏈去中心化、不可篡改等特性，有效地去除第三方，避免了單點故障和操作的不透明性，實現了密封式電子拍賣協議要求的正確性、公平性、密封性、不可否認性、時限性以及中標者的公開可驗證性。