Introduction of MACI

February 04, 2023

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這篇貼文提出,想法源自解決在區塊鏈上共謀 (中文版詳見 )的問題,後續主要由 BarryWhiteHatKendrick Tan, Kobi GurkanKoh 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 提供的公私鑰對與合約互動?

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

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

References

Videos

Articles