基於 2-of-2 多方安全計算的 MACI 匿名化方案

發表於 2023-04-06 11:15 作者： DAOrayaki_

這篇文章將展示基於 2-of-2 MPC 技術的 MACI 匿名化方案的具體實現。本文核心內容主要分爲三個部分：從任意算法到邏輯電路的實現；從邏輯電路到混淆電路的實現；利用不經意傳輸實現多方安全計算。最後，我們總結基於多方安全計算的匿名化方案。

感謝 Felix Cai 對 MACI 和隱私投票中多個問題的討論。

這篇文章將展示基於 2-of-2 MPC 技術的 MACI 匿名化方案的具體實現。本文核心內容主要分爲三個部分：從任意算法到邏輯電路的實現；從邏輯電路到混淆電路的實現；利用不經意傳輸實現多方安全計算。最後，我們總結基於多方安全計算的匿名化方案。

算法

在 MACI 系統中，操作員 Operator（記爲O）管理着一個數組，這個數組記爲 deactivate[]，其元素個數與 registry 數組中的元素個數相同。數組中每個位置的編號代表了 key 值（用戶的編號），而每個位置存儲着對應的公鑰。爲了更好地理解 deactivate[] 數組，可參考如下例子：在 deactivate[] 數組中，假設 registry 中的用戶1（deactivate[] 數組中的第一個元素）發起了 deactivate key 操作，操作員O收到該操作請求後，如果操作的合法性被O承認，O在 deactivate[] 數組中的第一個位置填入 registry 數組中第一個位置所包含的 value 值（用戶2的公鑰）。另外，假設用戶O沒有發起 deactivate key 操作，那么 deactivate[] 數組中的第二個元素的值爲 0。這樣一來, deactivate[] 數組的元素個數和 registry 數組中的元素個數相同就可以理解了。

現在，爲了實現 MACI 系統對管理員的匿名性，需要設計一個 2-of-2 的 MPC 方案來實現以下兩個性質:

先暫且不考慮這兩個要實現的目標。先考慮更換密鑰的操作: A發起更換 deactivate[] 數組中屬於A的公鑰的請求，O驗證A的請求是否合法，如果合法，則執行更換公鑰操作；否則，拒絕請求。

根據上述邏輯，我們先設計一份僞代碼來實現這個操作，如下:

function findElement(array, PK_1, PK_1′) {  for (let i = 1; i < array.length; i++) {    if (array[i] === PK_1) {      return PK_1′;    }  }  return false;}

<!---->

fn find_element(array: &[i32], a: i32, b: i32) -> bool {  let mut result = false;  for i in 1..array.len() {      result = result || (array[i] == a && b == a);  }  result}

邏輯電路的生成原理

爲了簡單起見，暫且假設一個公鑰由二位二進制數來表示（實際的公鑰是 256 位二進制數）。那么，現在就需要用用戶A的輸入公鑰，對比 deactivate[] 數組中的二把公鑰。因此，需要對比二次。

邏輯電路由邏輯門組成，邏輯電路中的邏輯門被分爲  層，比如上面的電路是兩層。邏輯門第一層需要用戶來添加輸入, 其他層是中間節點，最後是根節點。對於用戶輸入的邏輯門，有兩個輸入和一個輸出。其中一個輸入由用戶A完成。另外一個由O完成。這三個邏輯門組成了一個子邏輯電路。這個子邏輯電路負責一次公鑰的對比。

邏輯電路的生成工具

在現實中，爲了讓一個固定的算法轉換成邏輯電路，需要用到一些工具，如

1.Verilog HDL 和 VHDL：這兩種硬件描述語言被廣泛用於數字電路的設計和仿真，可以使用它們來描述算法的行爲，並將其轉換爲邏輯電路的形式。這些語言都支持從高級語言（如C、C++ 和 Java）轉換爲硬件描述語言的形式。使用 Verilog 或 VHDL 需要一定的硬件設計和編程經驗。

2.Xilinx Vivado Design Suite：這是一款商業軟件，用於 FPGA（現場可編程門陣列）的設計和开發。它提供了一個綜合工具，可以將高級語言或 RTL（寄存器傳輸級）代碼轉換爲邏輯電路的形式。它支持多種編程語言，包括 C、C++、SystemC、Verilog 和 VHDL 等。

3.Yosys：這是一款开源的 EDA（電子設計自動化）工具，用於數字電路的設計和仿真。它支持從 Verilog 和 VHDL 等硬件描述語言轉換爲邏輯電路的形式。它也支持從高級語言（如 C、C++ 和 Python）轉換爲 RTL 代碼，然後轉換爲邏輯電路的形式。

混淆電路（Garbled Circuit）

邏輯門的加密（混淆）

回到現在的例子中，因爲我們的公鑰在 deactivate[] 數組中都是有序號的（序號等價於用戶的編號），且數組 deactivate[] 中的最大元素個數是有上限的（用戶的個數）。因此，假設最大元素個數是N，那么，就需要構建N個子電路，然後合成一個最終的邏輯電路。

由於邏輯電路在每一個 epoch 中（一個 epoch 是區塊鏈更新 registry 中元素的一個周期）是固定的，那么，所有用戶都可以使用這個早已經生成好的，並存儲在區塊鏈中的邏輯電路。在本文例子中，由於 deactivate[] 數組中只有兩個元素，因此子電路只有兩個（每個子電路對應於一次公鑰的對比）。

注：在一個 epoch 中，registry 數組中元素個數是固定的，因此用戶的輸入和數組中的元素的對比次數是固定的，因此邏輯子電路的個數是確定的，且邏輯子電路是事先可以確定好的，因此整個邏輯電路是唯一確定的。

接下來，就是將邏輯電路的每一個輸入進行加密，然後將每一個邏輯門進行混淆。

先考慮加密。加密這個動作是由用戶A完成的。他對每一個輸入和輸出的 0 和 1 用加密值表示。注意，最終的根邏輯門的輸出不需要進行加密，在本案例中，就是 0（對比失敗），和 1（更換新的公鑰）。如圖所示：

邏輯電路中的每一條引线的 0 和 1 都用加密值代替。同時，每一個邏輯電路都有一個固定的編號（這個是所有人都已知的）。例如，編號 1、2、5 就構成了一個子電路 1（比較用戶的公鑰和數組中的第一把公鑰）。

基於此，將邏輯電路的每一個邏輯門的輸入和輸出（除了根邏輯門）進行加密後，在 Operator 的視角裏，對於加密後的邏輯電路，他就不知道每個邏輯門的輸入數字（加密值）對應的明文（是 0 還是 1）。

輸入加密的方法

在混淆電路中，爲每個輸入值生成兩個隨機 key 的過程通常是使用僞隨機數生成器（PRNG）來實現的。常用的生成隨機 key 的實現和庫有很多，例如 OpenSSL、Crypto++、libsodium 等。

輸出加密的方法

基於僞隨機函數 PRF 的方法是 Yao 的混淆電路中實現對輸出二進制數 0 和 1 的加密的主要方法之一。具體來說，這種方法可以實現對每個邏輯門的輸出進行加密，保證了數據的機密性和可靠性。

在基於 PRF 的方法中，每個邏輯門的輸出都被混淆成爲一組包含多個 label 的二元組，其中每個 label 都是一個隨機的 01 字符串。在生成每個 label 時，可以使用僞隨機函數（PRF）來實現。具體來說，可以使用一個密鑰和輸入值（如 0 或 1）作爲 PRF 的輸入，然後得到一個隨機的 01 字符串作爲 label。由於 PRF 是一種可以模擬真正隨機數的算法，因此生成的 label 具有高度的隨機性和不可預測性，保證了數據的機密性和安全性。

在混淆輸出時，可以將每個邏輯門的輸出表示爲一個包含兩個 label 的二元組（如 {label0, label1}）。其中，當輸入爲 0 時，使用 label0 作爲輸出；當輸入爲 1 時，使用 label1 作爲輸出。在將邏輯門的輸出發送給下一個參與方時，只發送一個包含正確 label 的二元組，保證了數據的機密性和保密性。常見的 PRF 包括 HMAC、SHA、AES 等。

需要注意的是，對邏輯門的輸出採用上述方法的目的是爲了便於不經意傳輸（oblivious transfer）的實現。

這裏其實就可以推導不經意傳輸過程了。比如，用戶 A 將這四個輸出——

用戶 A 輸入的生成

現在，我們繼續假設，用戶A公鑰的編號是 1，數值是 10，而數組中的二把公鑰（編號分別爲 0、1）的數值分別是 11, 10。也就是說用戶A的公鑰在數組中。

接着，用戶將自己的輸入，分別輸入到兩個子電路中（sub-circuit 1 和 2）。用戶在第一個邏輯子電路（1、2、5）中進行輸入。他的輸入是：在編號爲 1 的邏輯門輸入 2674（代表二進制數 1）；在編號爲 2 的邏輯門輸入 8798（代表二進制數 0）。用戶在第二個邏輯子電路（3、4、6）中進行輸入。那么，他的輸入是：在編號爲 3 的邏輯門中輸入 9809（代表二進制數 1）；在編號爲 4 的邏輯門中輸入 3453（代表二進制數 0）。

電路混淆

接下來的步驟就是將邏輯電路進行混淆。

這樣一來，根據這個表格的排序可能性，O想通過表三還原成真正的表一，會碰到 4 種可能性。那么，如果在一次證明中涉及到N個邏輯門，每個邏輯門用戶A都做上述操作，那么就有4N種可能性。這樣，通過排序任意顛倒，使得O很難推斷出每個數字到底代表 0 還是 1。

第一次通信

不經意傳輸（Oblivious Transfer）

此時，我們需要回顧兩個一定要保證的性質：

上述三個步驟，滿足了第二個性質，但是沒有滿足第一個性質，也就是說，O在解密了其中一個加密值後，得到了明文 1，但是，也暴露了另一個明文 0。這樣一來，混淆邏輯門表就暴露了很多信息給O，這樣讓O有機會破解A的祕密，從而使得性質 1 無效。

從對一個邏輯門的 OT 通信可以看出整個 OT 通信的全貌，即每個邏輯門的 OT 通信都是如此，且在一次 OT 通信過程中全部完成。這樣，O就能得到所有葉子邏輯門的輸出，這樣他就能進一步得到分支邏輯門的輸出，從而最終得到根邏輯門的輸出。

方案改進

上述方案中，需要且可以改進的地方有很多。例如，改進算法設計，降低算法的復雜度；改進邏輯電路的設計，讓邏輯電路變得更加簡單（減少門的個數，減少通信是需要傳遞的信息）；增加方案的安全性，加大破解方案的計算復雜度；讓交互變成非交互。

算法和邏輯電路的改進

但是，如果採用 Merkle Patricia Tree 的數據結構的話，對比的次數要少很多（這是因爲對於 256 位的公鑰來說，形成的 MPT 一定是稀疏的，因此，可能篩選二到三輪就可以篩選出想要的值）。那么，一旦算法計算復雜度下降了，邏輯電路的設計也就要簡單很多。

邏輯電路的設計也有化簡的可能性。

A的每個輸入都不同，O也是。實際上，可以進行化簡。變成如下圖所示。

這樣的化簡可以讓輸入變少。

增加安全性

如果O想輸入的是 0，那么他得到的結果必然是 0，也就是說，他天然知道輸出 0 的加密值，那么他就天然知道了 1 的加密值。同時，由於A的輸入已經是確定的，那么他可以根據A的輸入值，和1的輸出的加密值所在的行，去分析，如果 1 的輸出的加密值所在的行，不包含A的輸入加密值，那么A的輸入就是 0，否則就是 1。

爲了解決這類問題，我們需要對輸出全部進行加密。比如使用該種方法：上表中的四個輸出值 0、0、0、1 分別加密爲——

——這樣一來，輸出的四個值分別對應爲四個不同的密文。因此，在此環境下， 無法通過上述推斷來反推出A的輸入值是 0 還是 1。但是，這種方法使得輸出加密值的個數從二變成了四。通信復雜度會增大。

此外，非交互式的不經意傳輸協議也值得研究。

總結

上述方法首先不考慮需要實現 MACI 匿名化的兩個目標，即在明文下設計一個算法，讓O能夠正確判斷是否執行用戶A的請求。基於此，再將所設計的算法轉化成邏輯電路。再將邏輯電路轉化成混淆電路。需要注意的是，邏輯電路在每一個區塊鏈的 epoch 中是固定的且能夠從區塊鏈中直接獲取的。用戶A獲取該 epoch 的邏輯電路，利用相應工具將邏輯電路轉化成混淆電路。同時，用戶A將每一個混淆電路的輸入進行加密，並將加密好的信息發送給O。此時，O由於不知道加密後的輸入對應的明文是什么，O也就不知道用戶A具體的輸入是什么了，這樣就實現了匿名化的第一個性質。

進而，使用不經意傳輸是實現第二個目的的方法。通過不經意傳輸，用戶A並不知道O具體採用了哪些加密值進行進一步的輸入，因此用戶A無法推斷出 deactivate[] 數組中的其他元素信息。同時，由於O通過不經意傳輸獲得了足夠的有效輸入，因此O將這些有效輸入輸入到被加密的混淆電路中，最終能夠得到正確的輸出，該輸出和明文下執行第一節的算法所得到的輸出是相同的。因此，O就能夠根據輸出來判斷是否要執行用戶A的請求。

最終，O將上述所有操作利用零知識證明生成操作的 proof。區塊鏈對 proof 進行驗證，驗證通過後，區塊鏈將根據 deactivate[] 數組中的元素和 registry 數組中的元素來更新 registry 數組並結束 epoch 和开啓下一個 epoch。

標題：基於 2-of-2 多方安全計算的 MACI 匿名化方案

地址：https://www.coinsdeep.com/article/12065.html

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。