Introduction of MACI

Minimum Anti-Collusion Infrastructure (MACI)

Author & acknowledgement

Author: Fu-Chuan Chung @swfLAB

Special thanks to @ for reviewing this article

建議具備知識

• hash function
• merkle tree
• ECDSA、EDDSA
• ethereum transaction
• smart contract written by solidity

目錄

• 簡介
• 共謀
• MACI higher-level (基礎 )
• MACI technical-level (深入 )
• 結論

簡介

MACI 的全名為 Minimum Anti-collusion Infrastructure，最初由 Vitalik 在這篇貼文提出，想法源自解決在區塊鏈上共謀 (中文版詳見此 )的問題，後續主要由 BarryWhiteHat 與 Kendrick Tan, Kobi Gurkan 和 Koh Wei Jie 等人共同開發。

共謀

為了避免產生語意上的差異，先說明關於一些名詞的解釋，我也會用圖案來呈現兩者差異

• 😈  行賄者 = 操縱者 = 意圖改變投票結果的人。
• 🤑  受賄者 = 投票者 = 可以透過投票獲得來自行賄者利益的人。

在深入介紹 MACI 之前，需要先理解何謂共謀 (collusion )？

「有些人會為了自己的利益串通他人，導致多數人的資源掌握在少數人手上」，這類的現象被稱為「共謀」。最常被舉到的例子就是「賄賂 (bribing )」，例如在投票時 😈 行賄者會為了投票結果而不擇手段地去收買、廣告、吸引票源。

觀察現實中的投票情景，政府會透過法律來限制賄賂的發生、投票的隱私、審/計票人員的公正等。但在區塊鏈中，由於任何資訊都是透明公開的，沒有任何有效的制度或法律可以限制共謀的行為。

甚至區塊鏈中的賄賂場景可能會以另一種較隱晦、難以看透的方式存在。例如某些 😈 行賄者會告訴投票者：「這並非賄賂，而是可分享利潤的質押」，使得在區塊鏈中賄賂變得明目張膽，也會因對於 😈 行賄者與 🤑 受賄者無法懲罰而難以遏止。 這邊舉一個在區塊鏈上投票的例子：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract Voting {

  mapping (bytes32 => uint256) public votesReceived; // 用來記錄候選人獲得的票數
  mapping (address => bool) public voters; // 投票者名單
  mapping (bytes32 => bool) public candidateList;

  /* constructor input example:
    // John, Alice, Bob after keccak256
    [
			0x0bfa36c40b8771f59912a8b06e3ba9cd68504e69345a0ebcb952c3c6100ec88e,
			0x6070f87e7650727769f301b1e264c58d77a49792dc17c13fe3cb44a9bb1f7b44,
			0x780641b8ceca510c40f5f0178d126444811cc3e3edf7fa86f3656f77615dcc5c
		],
    [
			0xB5e30182B2EC04A58C8dFaB9f0E42Bbd5a551618,
			0x5B38Da6a701c568545dCfcB03FcB875f56beddC4,
			0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2,
			0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db
		]
  */
  constructor(bytes32[] memory _candidateNames, address[] memory _voters) {
    for (uint8 i = 0; i < _candidateNames.length; i++) { // 候選人名單
      candidateList[_candidateNames[i]] = true;
    }
    for (uint8 i = 0; i < _voters.length; i++) { // 投票的白名單
      voters[_voters[i]] = true;
    }
  }

  function voteForCandidate(bytes32 candidate) public { // 投票
    require(candidateList[candidate], "input is not a candidate");
    require(voters[msg.sender], "invalid voter");
    votesReceived[candidate] += 1;
  }
}

這個合約利用 bytes32 來作為候選者的名稱，投票者可以透過 voteForCandidate() ，直接輸入候選人的名稱進行投票。

任何人都可以從 etherscan 上直接看見我在鏈上投票的結果，就是投給 John。

Function: voteForCandidate(bytes32 candidate) ***

MethodID: 0xcc9ab267
[0]:  0bfa36c40b8771f59912a8b06e3ba9cd68504e69345a0ebcb952c3c6100ec88e
(byte32 of keccak256("John"))

• 😈  行賄者可以透過撰寫 script 抓取鏈上資料，或甚至可以直接透過智能合約來完成賄賂。
• 🤑  受賄絡者可自行提供在鏈上投票的證明給 😈  行賄者。

這樣子使得在區塊鏈上進行投票變得非常困難，

透過 MACI 建構的系統/ App 可以讓共謀者難以進行共謀，且同時保留了審查的機制與在鏈上進行投票等特性。

---

MACI 流程：

以下則會分成兩個流程講述：

第一個是在較高層次 (high-level )觀察投票流程，會利用一個例子來解釋 MACI 投票的流程，另一個流程則會解釋在投票時使用的技術 (technical-level )，本流程參考自此篇文章。

High Level

這邊會講述投票者如何與系統互動進行投票。 前提： ⭐️ 整個系統中會有兩個身份：

• 投票者 (Voter )：可以將一組公鑰送入 contract 中，使自己的身份變成投票者。
• 計票者 (Coordinator )：系統中負責計票的角色，會進行計票的工作，其公鑰會公開讓所有人知道。

⭐️ 基本流程：

1. 註冊
2. 投票 (簽章與加密 )
3. 計票

投票流程 (實例 )：

這個例子中有：

• 三個投票者：Alice、Bob、Charlie，其公私鑰分別為 keyPairA: (pubKeyA, privKeyA)、keyPairB、keyPairC。
• 一個計票者：David，其公私鑰分別為 pubKeyD (公開的資訊 )、privKeyD (只有 David 知道 )。

1. 在建立合約後會有一個 sign-up 階段 (時間到了便無法再加入 )，投票者只有在這時候可以加入投票。此時 Alice、Bob、Charlie 則需要將他們的公鑰送到 MACI 的合約中以完成註冊。 (這邊的公私鑰並不是進行交易錢包中的那一對公私鑰，而是由鏈下 app 產生的公私鑰對 )
2. 當 Alice 投票時，會將他的票 X (一段 message，像是上面例子中的 bytes32 )透過 privKeyA 簽章，得到 privA(X)
3. privA(X) 再經過 David 的 pubKeyD 加密，得到 encD(privA(X))，最後透過 MACI 的合約完成投票。
4. 透過 David 的公鑰加密後便只有 David 可以解開，因此只有 David 知道 Alice 到底投了什麼。
5. 此時若 😈 Bob 與 🤑 Alice 為行賄者與受賄者：Bob 便無法從鏈上直接得知 Alice 投給了誰；Alice 也無法透過鏈上的紀錄來向 Bob 證明他的投票結果。
6. 若 Alice 在投票時不幸被 Bob 逼迫，投給了 Alice 不想投的人。MACI 也提供了一個機制，可以讓 Alice 換一組公私鑰對 keyPairA': (privKeyA', pubKeyA')，再經由上述的 2、3 步驟進行投票。 (MACI 在最後計票時，會將原本的票數作廢，只計算其最新產生的票 )
7. 最後，當投票時間結束時，計票人 David 會從合約將每張票 (簽章 & 加密後的資訊 )抓下來，計算結果，並產生一段 zk proof 到合約上以更新票數。

圖一、MACI 投票的簡化流程圖

透過 MACI，除了可以保護 Alice 的隱私 (只有計票者可以解密並紀錄 Alice 的投票結果 )，也可以提高賄賂的難度，使共謀在 MACI 建立的投票系統下變的窒礙難行。

---

Technical-Level

此段會是上段流程更深入的探討。

前提：

⭐️ 在 MACI 中投票或更換公鑰等未加密之動作稱為指令 (command )，而加密後的資訊稱為訊息 (message )。

⭐️ 加密流程：

1. 將指令 (傳入內容 msg )雜湊後得到 h。
2. 利用系統給予的 EdDSA privKey ，將 h 進行簽章。
3. 利用一個隨機產生的 ephemeral key 與計票者的 pubKey' 產生出一組 ECDH shared key - Ekey。
4. 最後透過 Ekey 將簽章與指令中的 data 進行加密。 (計票者可以透過他的 privKey' 解開 )

投票流程：

1. 首先，計票者會將投票的合約部署到鏈上，並開始 sign-up 階段，會將他的 pubKey’ 公開地儲存在合約中。

2. 在 sign-up 階段，系統會隨機產生一組 EdDSA 計算出的公私鑰對給予投票者，投票者需要保存自己的私鑰 (privKey )，並將公鑰 (pubKey )傳到合約上進行註冊。合約中會有一棵 Merkle Tree 紀錄整個投票者的註冊狀態、投票權重等 (詳細可見圖二 )。
   圖二、Sign-up 流程圖。

3. sign-up 階段結束，無法再加入其他的投票者，並進入投票階段。

4. 投票時，投票者可以做兩種行為 (這些行為都可以透過 publishMessage() 更新在合約中 )：

   1. 投票： 投票者投的資訊會經由下面的處理上傳至合約中，並將訊息儲存在一棵 Message Tree 中：

      • 將指令 (投票內容 )雜湊後得到 hash。
      • 利用系統給予的 EdDSA privKey ，將 hash 進行簽章。
      • 利用一個隨機產生的 ephemeral key 與計票者的 pubKey’ 產生出一組 ECDH shared key Ekey。 (計票者可以透過他的 )
      • 最後透過 Ekey 將簽章與指令中的 data 進行加密。

   2. 更改公鑰：

      若某人被 😈  行賄者逼迫投出非意願的票時，可以透過 publisgMessage 更改其公鑰，而更改的動作其實與投票類似，只是在一開始簽章時將傳入的投票訊息改成新的公鑰 (newPubKey )，更改後便可以用新的公鑰再進行投票了。

   關於 message 的敘述可見圖三。

   圖三、來自 Vitalik 在 ethresear 中提案的內容。

5. 投票階段結束，計票者需要解密與紀錄所有人的票以統計結果。

6. 避免計票者黑箱，在計票時會使用 zk-snark 的 proof 讓系統可以不透過公布投票者投出的票卷內容，但可以證實所有計票的公正性 (類似實體投票時的唱票，在旁有投票者監督 )。

在 MACI 中有兩個 zk-SNARK circuit，也代表計票者需要執行的兩個動作 (process & tally )：

Process：是用來證實在鏈上 state tree transition 的正確性 (確認所有票都是 valid )，其中會檢查三件事：

• 使用正確的 key 進行加密。
• 解密出來的 message 有儲存在 message tree 中。
• 指令運算後的 state root 要與計算後的結果一致。

Tally：用來證實計票者計票的正確性，避免計票者黑箱。

---

ECDH shared key  解釋

在這邊我想簡單地解釋一下 ECDH 的概念，但是不會討論太深入的數學概念。

在 ECDH 中的 DH 代表的是 Diffie-Hellman key exchange，兩位密碼學家創造了一個方法，可以在不安全通信通道中建立起一組「共享金鑰 (shared key )」，且這個金鑰只會由雙方計算得出來，並可以使雙方在此通道下以此金鑰進行加密 (encrypt )與解密 (decrypt )的方法；而 EC 則代表橢圓曲線加密。

下面來舉個例子，若有 Alice 與 Bob 想進行金鑰轉換，但是他們會通過一個公開的通道進行。

1. 若 Alice 與 Bob 說好使用特定的橢圓曲線，並使用他們知道的一基點 G 作為 generator。
2. Alice 選擇一個私鑰 a，計算其公鑰 A = a * G，並將 A 傳給 Bob。
3. Bob 也選擇一私鑰 b，計算其公鑰 B = b * G，也將 B 傳給 Alice。
4. 這時，Alice 與 Bob 可以計算出一組只有他們知道的 shared key k = a _ b _ G (Alice ：得到 B = b * G，可以將其私鑰相乘即得到 k；反之亦然 )
5. 此時在公開的訊息中只會觀察到 A 與 B 兩組公鑰，而在此通道中的其他人因為無法獲得 a、b，因而無法得到 k。
6. Alice 與 Bob 此時便可以使用 k 作為加密與解密的公鑰進行訊息交換。

MACI 中就是利用這種交換金鑰的方式來加密，即使是在一個公開的通道上 (區塊鏈 )，也可以讓計票者可以透過共同金鑰計算投票者的訊息。

更詳盡的名詞解釋可見此。

更詳盡的系統設計圖可見圖四，並參見此影片。

圖四、MACI 的系統圖

結論

預防共謀在區塊鏈上是一件非常重要的事情，MACI 簡單的透過加密演算法的技術讓共謀這件事情變得困難，並且也利用 zkProof 來證實投票的正當性，在每個方面都思考的很縝密。但目前的架構中，仍有計票者與 😈  行賄者串通以得知 🤑  受賄者投的票 (因此只能假設計票者為完全公正 )，或是只使用單一的 server 進行運算等缺陷。目前 MACI 的開發也在進行中，預計是要將其運算的架構改成 MPC (Multiple-Party Computation )。

這邊放幾個我在讀 doc 與看範例時遇到的問題

Q：投票者與 MACI 互動的時候，是透過自己的公私鑰還是 MACI 提供的公私鑰對與合約互動？

Ｑ：如果是 MACI 提供的公私鑰對，這樣則需要將一些 gas 傳進此公鑰產生的 address 嗎？還是會透過在 MACI 中的私鑰來與合約互動 ？

A：MACI 提供的公私鑰對是採用 EDDSA，而非 Ethereum 上使用的 ECDSA。因此是使用自己的錢包與合約互動，且不需擔心此錢包的隱私問題，我原本認為透過地址與合約互動則會洩露隱私，但是在此的隱私是指投票的結果被公開在鏈上被他人看見。

References

Videos

• Privacy in Ethereum by Barry WhiteHat (Devcon5)
• Minimum Anti-Collusion Infrastructure (MACI)

Articles

• MACI - Barry WhiteHat, Kendrick Tan, Kobi Gurkan, and Koh Wei Jie
• MACI spec (MACI 關於每個部分的說明 )
• 動手實作零知識 - circom
• Circom & Snarkjs