MACI Introduction

Minimum Anti-Collusion Infrastructure

Author: Fu-Chuan Chung @ swfLAB

感謝 Paul (Tzu Chun) Yu review 此篇文章。

建議具備知識

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

Table of Content

• 簡介
• 共謀
• MACI higher-level （基礎）
• MACI technical-level（深入）
• ECDH shared key解釋
• 結論

簡介

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

picture from element5digital

共謀

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

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

在深入介紹 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 建構的投票系統可以讓共謀者難以進行共謀，且同時保留了審查的機制與在鏈上進行投票等特性。

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 紀錄整個投票者的註冊狀態、投票權重等（詳細可見圖二）。
3. sign-up 階段結束，無法再加入其他的投票者，並進入投票階段。
4. 投票時，投票者可以做兩種行為（這些行為都可以透過 publishMessage() 更新在合約中）投票：投票者送入的資訊會經由下面的處理（見上方加密流程）上傳至合約中，並將訊息儲存在一棵 Message Tree 中。
5. 更改公鑰（在 high-level 的第五點）：若某人被 😈 行賄者逼迫投出非意願的票時，可以透過 publisgMessage 更改其公鑰，而更改的動作其實與投票類似，只是在一開始簽章時將傳入的投票訊息改成新的公鑰（newPubKey），更改後便可以用新的公鑰再進行投票了。（關於 message 的敘述可見圖三。）
6. 投票階段結束，計票者需要解密（見下方 ECDH 解釋）與紀錄所有人的票以統計結果。
7. 避免計票者黑箱，在計票時會使用 zk-snark 的 proof 讓系統可以不透過公布投票者投出的票卷內容，但可以證實所有計票的公正性（類似實體投票時的唱票，在旁有投票者監督）。

圖二、Sign-up 流程圖。

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

ZKProof：

在 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。因此是使用自己的錢包與合約互動，且不需擔心此錢包的隱私問題。我原本認為透過地址與合約互動則會洩露隱私，但是在此重視的隱私是指投票的結果被公開在鏈上被他人看見而非地址上的隱私。

歡迎 donate

References

Videos

• Privacy in Ethereum by Barry WhiteHat (Devcon5)
• Minimum Anti-Collusion Infrastructure (MACI)
• Public key cryptography — Diffie-Hellman Key Exchange (full version)

Articles

• MACI — Barry WhiteHat, Kendrick Tan, Kobi Gurkan, and Koh Wei Jie
• [ZKP 讀書會] MACI
• MACI spec （MACI 關於每個部分的說明）
• 動手實作零知識 — circom
• Circom & Snarkjs
• ECDH — yanlong
• Encryption with ECDH (Diffie–Hellman key exchange)