這裡我們以一個高度為3的Shrubs默克爾樹為例，如圖1所示。當插入節點4時，Shrub節點為14，12，8，4。當插入節點5時，Shrub節 點變為14，12，10， 4,因為節點10成為了完美子樹的根。
因此，資料塊插入所消耗的gas比原生增量默克爾樹小了很多。對於每個非葉節點，它的雜湊值最多隻會計算-次，當所有葉節點都插入之後，整棵樹一共需要計算2f-1次。所以平均而言，插入一個葉節點只需要進行-次雜湊計算。
3. 雜湊函式的選擇
為zk- SNARKs選擇合適的雜湊演算法時，需要考慮兩個因素:gas的消耗和生成證明的時間。- -般來說，一個gas消耗更 少的雜湊函式將導致一個更大的電路(更多約束)，也就意味著更長的證明生成時間。考慮到雜湊函式只會在鏈外進行使用，我們只需關心後一因素。但對於鏈上使用的雜湊函式，則應該平衡好這兩個因素。
候選的雜湊函式、它們的gas消耗(對於2個輸入) v和zk- -SNARK約束列在了表1中。我們可以看到並沒有同時具有低.gas消耗且小電路尺寸的雜湊函式。但是，由於Shrubs默克爾樹使得構建低gas消耗的默克爾樹成為可能，因此我們可以在折衷方案中減少gas消耗的權重。最後，對於我們的系統來說,Poseidon或者MiMC雜湊函式是更好的選擇。注意Poseidon和MiMC雜湊函式還沒有被大多數密碼學專家稽覈過，因此它們可能會受到攻擊。
4.Shrubs公開輸入壓縮
如上所述，儘管Shrubs默克爾樹大大降低了將承諾插入樹中所消耗的gas,但它增加了證明承諾在一棵樹中所消耗的gas。基本上，為了證明一個葉節點在Shrubs默克爾樹上，不僅應該提，供從葉節點到其最近的Shrub節點的路徑，還應該提供所有的Shrub節點，後者用於證明到最近節點的有效性。結果是，由於有h+1個Shrub節點，公開輸入的大小由1增加到h+1。相關gas消耗計算公式如下:
其中n是公開輸入的大小，ScalarMulGas、 PairingBase-Gas、PairingPerPointGas是 三個橢圓曲線操作的gas消耗。這些操作是透過EVM.上的預編譯合約實現的，它們所消耗的gas如表2所示。我們可以看到，公開輸入的大小每增加1，gas消耗會增加40,000。因此，Shrubs默克爾樹比原生增量默克爾樹多耗費40,000 * h gas。
我們引入一種方案: Shrubs公開輸入壓縮，用來減少公開輸入的大小。如圖2所示，為所有Shrub節點建立另外一個默克爾樹，稱作節點默克爾樹。我們可以使用節點默克爾樹中的一條路徑，而不是所有的Shrub節點，來證明Shrub節點的有效性。這樣，公開輸入的大小將減小為1。
每當將葉節點插入到Shrubs默克爾樹中時，都會更新節點默克爾樹，因為Shrub節點已經更新。這將給插入資料的過程帶來額外的gas消耗。為了減少這部分消耗，節點默克爾樹使用了一種新的方案來計算默克爾樹根，如圖3所示。-棵節點默克爾樹會被分為幾個子樹，並且這些子樹的樹根會被儲存下來。當一個葉節點更新時，僅需重新計算相應子樹，默克爾樹根隨之更新。此外，選擇MiMC雜湊作為節點默克爾樹的雜湊函式，以平衡電路尺寸大小和gas消耗。
5.公開輸入壓縮
Shrubs公開輸入壓縮能正常工作是因為所有的Shrub節點是公開的，並且它們的默克爾樹根是固定的。但對於其他的公開輸入，這種方法可能不再起作用。這些公開的輸入必須受一個單獨的電路約束。我們使用一種方法:公開輸入壓縮，來減少公開輸入的大小。Christian Reitwiessner在部落格[8]中對此進行了介紹。.
假設一個電路可以由函式F(u, w)來表示，其中u表示公開輸入,w表示隱私輸入。可以將此函式更改為F(H, f(u, w) ^ H(u))的形式，所有公開輸入的大小變為1 (所有輸入的雜湊)。MiMC雜湊在我們的協議中用於公開輸入壓縮。
協議
所提出的協議提供了兩種資產:透明資產和隱私資產。前者是通用的ERC-20代幣，後者的設計與Zcash類似。隱私資產也可視作ERC-20代幣的隱私表示。使用這一協議，使用者可以輕鬆地轉移他們的透明和隱私資產。
圖4說明了協議的總體架構。若干個智慧合約部署在了區塊鏈上。Monitor幫助監控這些合約的交易並將交易傳送到區塊鏈上。Server 是核心元件，它呼叫zk- -SNARK引擎生成證明並同步區塊鏈的狀態。
1.金鑰管理
兩對定義在Fr上的公私鑰對被用在了協議中。sk、pk對用於身份識別。esk、epk對用於鏈上秘密分發的加密。它們的關係如圖5所示。
2.票據，承諾，廢棄符
協議使用與Zcash相同的UTXO模型。所有的票據承諾都儲存在Shrubs默克爾樹上。Shrubs默克爾樹的高度 被設定為31,以總共支援2票據。一張票據包含了下列欄位
3.鏈上秘密分發
在zk- SNARKs中，為了傳輸-張票據，傳送方需要透過區塊鏈將承諾傳送給接收方，並透過點對點方式將票據值傳送給接收方。我們的協議使用鏈上秘密分發技術，這允許傳送方也可以透過區塊鏈秘密地共享票據。這樣，整個過程都可以在區塊鏈上完成。
鏈上秘密分發如圖6所示。傳送方首先生成一對臨時金鑰tsk、tpk。然後透過tsk和來自接收方的epk生成‘共享加密金鑰”。最後，傳送方使用共享加密金鑰加密票據，並將加密的票據和tpk傳送到區塊鏈上。對於接受方，可以基於esk和區塊鏈上的tpk恢復共享加密金鑰。最後，接受方可以使用共享加密金鑰在鏈上將加密的票據進行解密。
協議中的隱私資產支援三種操作: MINT、TRANSFER和BURN。
MINT
MINT操作用於透過將等量的透明資產鎖定在合約中，以發行一定數量的隱私資產。如圖7所示，它將為已發行資產建立新的票據。zk-SNARK引擎使用MINT電路，以票據的金額和承諾作為公開輸入，來幫助生成票據證明。然後將它們傳送到智慧合約。如果證明被成功驗證，則將票據承諾新增到Shrubs默克爾樹中。
TRANSFER
如圖8所示，TRANSFER操作被用來將隱私資產從傳送方轉移,到接受方。它將生成一個包含四張票據的交易:兩張作為輸入，兩張作為輸出。傳送方必須為輸入提供兩個廢棄符，為輸出提供兩個承諾。zk-SNARK引擎使用TRANSFER電路為輸出生成證明。然後交易會被髮送到智慧合約。如果被成功驗證,智慧合約將記錄兩個廢棄符，並將兩個承諾追加到Shrubs默克爾樹上。
BURN
BURN操作可以銷燬-定數量的隱私資產並獲得等量的透明資產，如圖9所示。首先，必須提供票據和其默克爾路徑來證明對票據的所有權。zkSNARK引擎使用BURN電路為票據生成證明。數值、票據廢棄符、Shrubs默克爾樹根、賬戶是傳送到智慧合約的公開輸入。如果被成功驗證，票據的廢棄符將記錄在智慧合約中，並且票據也不能被再使用。
zk- SNARK電路
我們用一個例子來描述協議中的zk- -SNARK電路。Alice鑄造了-定數量的隱私資產，將其轉移到Bob,並由Bob進行銷燬。下標為A的符號表示其屬於Alice，B為Bob。
1.MINT電路
MINT電路被Alice用來發行隱私資產。
2.TRANSFER電路
3.BURN電路
Bob可以使用BURN操作將他的隱私資產進行銷燬。
效能
協議在裝有Intel(R) Core(TM) i5- 7500 CPU 3.40GHz處理器(4核)和8GBRAM的計算機上進行了評估。我們使用Qtumv0.18.1來啟動了一條嵌入了EVM的私有鏈然後把我們的智慧合約部署在了上面。每個MINT、TRANSFER和BURN操作都執行了20次來測量平均的證明生成時間，並且我們從區塊鏈資料中取得了它們的gas消耗。
引數和結果展現在了表3中。我們可以看到TRANSFER操作的gas消耗大約為1M，證明生成時間為5.68s，明顯低於其他協議。MINT和BURN操作比TRANSFER消耗了更少的資源。整體而言，協議在EVM.上表現得比其他協議更加高效。
總結
本文展示了一種基於智慧合約的使用zk- SNARKs的高效隱私協議。透過使用一種改進的默克爾樹和仔細選擇的雜湊函式，它將gas消耗減小到1M，並且在常規電腦上的交易生成時間低於6秒。此外，它使用鏈上秘密分發來在區塊鏈上儲存私有資訊，實現了交易傳送者和接受者之間的非互動式交易。
要部署zkSNARK電路，需要進行可信設定來生成證明金鑰和驗證金鑰。不幸的是，此過程還會產生一條稱為“有毒廢物”的資料，必須將其丟棄，因為它可能被用於產生虛假證據，從而破，壞系統的安全性。為了解決該問題，可以使用特殊的加密儀式來執行可信設定，在該儀式中，多個參與者輪流執行計算任務，以得到最終的結果。
Zcash在2017年舉行了這個儀式。在2019年8月，Semaphore團隊基於Zcash Powers of Tau儀式進行了多方信任設定儀式[9]的第一階段。實際上，儀式可以是永久的，任何zkSNARK專案都可以選擇儀式的任何一個節點來開始其指定電路的第二階段設定，並且參加人數沒有限制。我們的協議可以從新儀式中受益，併為其生成自己的證明金鑰和驗證金鑰。
