ZK-STARK:如何實現抗量子計算與隱私保護共生?

買賣虛擬貨幣
在OKChain(OK公鏈)的多鏈狀態分片設計中,考慮到BLS在同一訊息的聚合簽名驗證上僅需2次對映操作的效率優勢,所以採用了基於BLS多籤的改進版PBFT協議作為共識組的出塊標準方案。

然而隨著量子計算理論的快速發展,非量子安全的BLS簽名方案註定只能在中短期使用,更長期的區塊鏈演進需要能夠更好抵禦量子計算破解的技術。

得益於今年3月份EliBen-Sasson等研究者的工作成果,量子安全的STARK(Scalable Transparent Argument of Knowledge)技術開始變得極具吸引力,大幅減少的證明大小,使其很有希望成為適合的長期方案。

在提及STARK之前,我們首先需要簡單介紹計算複雜性理論中的IOP(Interactive Oracle Proof)和STIK(Scalable Transparent IOP of Knowledge)。

IOP是一個互動式協議,參與雙方為證明方(Prover)和驗證方(Verifier)。驗證方在每個回合隨機選取隨機數,而證明方根據隨機數提供相應位置的諭示結果(oracle access)。

經過多個回合的互動隨機查詢,驗證方可以對證明方的正確與否作出判定,而在這個過程裡驗證方無須讀取證明方所構造的完整證明,而僅需依概率查詢部分證明即可。如果驗證方採用均勻分佈來生成隨機數,那麼IOP可以基於Fiat-Shamir協議構造為非互動式版本。

具有透明(transparent)、可擴充套件(scalable)等特性的IOP被稱為STIK,這裡透明指的是驗證方發出的全部訊息包括向證明發提出的諭示查詢都是公開隨機數(即Arthur-Merlin協議),類似概率可驗證明(PCP)。

可擴充套件表示驗證方進行全部驗證的時間複雜度和證明方生成證明的時間複雜度都存在一定限制,即驗證方複雜度近似基本計算時間T的對數多項式時間(poly log T),而證明方複雜度接近準線性表示(T poly log T)。

保護隱私的STIK系統通常可以很好地支援零知識證明(zero knowledge),一般記作ZK-STIK。STARK作為STIK在證明方計算能力受約束下的一種實現,可以在STIK的基礎上轉化為互動式STARK(iSTARK)或非互動式STARK(nSTARK)。我們這裡談論的ZK-STARK即ZK-nSTARK。

在今年3月釋出的《Scalable, transparent, and post-quantum secure computational integrity》論文中,Ben-Sasson等研究者構建了高效的ZK-STARK系統,將計算完整性(computational integrity)歸約為Reed-Solomon編碼問題,提出FRI方案(Fast Reed-Solomon Interactive Oracle Proofs of Proximity)在每步計算電路(arithmetic circuit)當中使用類似快速傅立葉變換(FFT)的方式減少原驗證問題的規模實現快速計算。ZK-STARK具備幾個很好的特性:

零知識證明,可保護隱私資料的安全;
非互動式,可減少參與雙方的通訊複雜度;
透明,無須依賴第三方可信基礎設施;
可擴充套件,參與雙方的時間複雜度都相對較低;
量子安全,STARK沒有使用公私鑰對對映,僅依賴抗碰撞性hash和隨機諭示模型,能夠抵禦量子攻擊。

這些特性使得ZK-STARK非常適合那些既需要互信同時又存在很多欺詐動機的應用場景,例如區塊鏈出塊驗證、安全資訊驗證、投票系統等。

以太坊團隊考慮將ZK-STARK作為其長期計劃的關鍵技術,而由Eli Ben-Sasson與Alessandro Chiesa等人所在的StarkWare團隊也正持續推進ZK-STARK技術在區塊鏈上的應用,增強它的可擴充套件性和隱私保護。

相信隨著ZK-STARK技術越來越完善,將其引入OKChain的共識層將會為OKChain提供更加透明的可驗證信任和更加安全的隱私資料防護。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;