Anna (00:07):
Welcome to zero knowledge, a podcast where we talk about the latest in zero knowledge research and the decentralized web. The show is hosted by me, Anna.

Fredrik (00:19):
and me Fredrik.

Anna (00:27):
This week, I chat with Wei Jie, from the EF all about MACI, which stands for Minimum Anti-Collusion Infrastructure. It's a project powered by zero-knowledge proofs. We talk about the challenges in voting digitally and in decentralized networks, how MACI uses ZKPs to solve this, and also how this could be used in the context of quadratic voting, like in the case of Gitcoin. Speaking of, I want to remind everyone that the Gitcoin CLR matching round 8 is on now. So if you've ever thought of donating to the show now would be a very good time to do so. All contributions big or small are matched. So even a small amount can go a really long way, just saying competition is pretty fierce this time around. So if you have a chance, please do help out. Now, before we kick off this week's interview, I want to say, thank you to this week's sponsor Parity Technologies.

Anna (01:18):
Parity is a company building the core infrastructure to power Web 3.0. And at the heart of the company is a genuine goal to empower developers, to create better products and services through decentralized web technologies. They are currently looking to fill a number of job positions. This includes many in engineering, business development and marketing. For the Berlin office they're looking for a passionate social media manager to maintain and grow the company's social networks as well as to activate customers and contributors alike. Also, they are looking for a CI/CD engineer to help automate an ever-growing set of open source repos in GitHub. You should have experience with GitHub actions, GitHub CI or something similar and compiler experience like Docker. If you're interested or know someone who might be, you can find out more at parity.io/jobs, I've added the link in the show notes. So thank you again, Parity. Now here's my conversation with Wei Jie, all about MACI.

Anna (02:19):
Today I'm sitting with Wei Jie and today we're going to talk about minimum anti-collusion infrastructure or MACI. Thank you so much for coming back on the show.

Wei (02:30):
Thank you so much for having me again. I'm a big fan and I'm super happy to be here.

Anna (02:35):
Cool. You've been on the show before you were on the show. Guess maybe three months ago to talk about trusted, maybe a little bit more, even maybe six months ago to talk about trusted setups and the trusted set up that you run for Semafore specifically. But in this episode, what we're going to be talking about is this project you have sort of told us a bit about your background, but maybe a question for you would be what have you been working on mainly since you were last on the show?

Wei (03:02):
Sure. So I worked on with the Ethereum Foundation, applied ZKP team, and one of our projects is called MACI. And this is something that I've been working full-time on for quite a while now. And so, since we last spoke, I have also still been working at this project, but also helping out in a few other projects with the team. And recently I've been working on the next version of MACI and also helping out with Clr.fund who is using MACI in production to build a system that allows for public goods funding on Ethereum.

Anna (03:40):
Cool. And I think, I mean, this is the first time that we're actually going to cover the topic of MACI. It's so funny because I actually heard about it, I think like a year ago or so. And I heard about it and was like, Oh, that's so neat, but I didn't really give, I didn't get a chance to dig into it until now, but in doing some research for this interview, actually, it's super interesting. I feel like it's an awesome ZK use case that we haven't really covered very extensively and I'm excited to dig into it. So I think maybe just start off, where does MACI come from? Where was the project born and what, what was it kind of like originally conceived as?

Wei (04:17):
Yeah, so rather than middle of 2019, I think in May, 2019, Vitalik posted a post on Eth.research, and this is where the idea first popped up. And I started working on this with other members of the team around late 2019. And that's where we translated the idea into actual running code as a proof of concept. And that's yeah, I guess that's where it came from. It's just, it came from an eth research post but there is extensive literature on the topic of collusion resistant voting, private voting, on receipt free voting in computer science academic publications. But the name MACI and the the particular instantiation of this construction was laid out in the post.

Anna (05:09):
I see. So what you just described, it's sort of like kind of an anti-collusion in the context of voting it's allowing, you know, no, basically .... actually I shouldn't say what it is. I should ask you, what is the problem that you're trying to address exactly?

Wei (05:26):
Sure. So the main idea is that collusion is about having someone work with someone else who was a part of like a system where they give that person some kind of incentive to do something on their behalf. And this is bad if the fact that this incentive or this, you could call it a bribe. If that exists, it would violate some assumptions of their system. So for example, in voting, we don't want people to be bribed, to vote for things that we would expect them to be voting for based on their free choice. And this is something that MACI was designed to come to as this first use-case. So primarily MACI is used for voting. It would be an interesting exercise to figure out how to use cases. But I think in terms of the cryptocurrency and blockchain space voting is a pretty big use case in itself.

Anna (06:27):
Totally. But I mean, so this concept of collusion free voting though, this, I mean, this is a much older concept than even computer science, right? This is like democracy is how, how, you know, I think, I think I, I'm probably going to quote this wrong, but I think like it wasn't ancient Greece, like something about a stone that they put in a thing, like there's like these, all these ways that people voted over the years and they found that there were problems with them basically like ancient times, they discovered that if you did public voting, you could have pressure, direct pressure from some powerful entity, like staring at you, being like, you better vote the way I want you to vote. And if you had to put your hand up or something like that, you would definitely get in trouble if you voted the wrong way. Sure. There was then the introduction of like private voting or, you know, and, and I know that in traditional systems like those do exist, there are techniques right. For managing, uh, any sort of collusion or bribery.

Wei (07:20):
Sure. Um, so absolutely in Singapore, which is where I am from, when you vote, you have a piece of paper and you go into a shielded booth and you have a pen or a stamp and you tick the box that you wanna vote from and you fold it up and you put it in a cardboard box. And the cardboard box is then sent to a place where it is counted. And six months later, all the votes had burned and incinerated in front of theofficials and representatives from different political parties. There is a system in place to ensure privacy. And so I think that's where, yeah, I think we've, we've come to a point where, where that's sort of like a standard in voting, but I do want to say that MACI isn't, it doesn't have "national voting" in mind. This is something very specific to the, cryptocurrency and blockchain space, where it's designed for people who are distributed around the world. It's designed for people who don't mind having that votes done or having the elections done in a digital format. I am well aware that a lot of people who would oppose using any kind of e-voting system, uh, and that is fair because the stakes are very high, such as in politics. But MACI, doesn't try to address those issues, which run far deeper than what anti-collusion is meant to address.

Anna (08:47):
So you're saying like, it's not, this is not proposing itself as like an alternative to the private voting that happens in elect, like, national elections. But I, I guess what I am curious about is like, what is, when you go from that, that transition from the meat space voting to the digital voting, what was, what's the problem that you're trying to solve, even in that digital context?

Wei (09:09):
So in a digital context, whenever you make a transaction, you have a receipt for the transaction and the receipt in most cases shows exactly what happened on-chain. Yeah. And this is a, this is something that you could show a briber to prove that you have voted a sort of way. We want a way to vote for things in such a way that you can't prove how you voted, but you want your vote to be counted in the way that you voted for. So let's say that Eve who is an attacker tells Alice, who is a voter Alice, I want you to vote for option A and if you do that and show me the etherscan, your transaction ID and transaction hash and everything.

Anna (09:56):
Proof

Wei (09:56):
Exactly. Eve can verify that Alice had voted for option A and say and then Eve can pay Alice a bribe. But if Alice cannot prove that she had voted for option A, option B or whatever, so Eve has no way to tell how Alice had voted and therefore Eve doesn't have any incentive to even try. Yeah, exactly.

Anna (10:24):
So you're kind of trying to nip this problem in the bud, right? In the, at the starting point where it's not that you're going to add more and more security and privacy around the vote that's passed, but rather say Alice can't, she, she would be unable to prove one way or another, which way that she voted, even if she wanted to, I guess. Yeah, exactly. Right. So I want to try to picture myself in the situation. So let's say instead of Alice, it's me, Anna, and there's somebody who's trying to coerce me or get me to vote in a certain way. There's vote A or B and I want to vote for B, but someone's like, you really have to vote for A. So what am I actually going to do? Like what role or what kind of, what path does my vote take?

Wei (11:11):
Sure. So in this case, the voter, Anna has to first, so let's say that Eve, Eve bribes Anna and Anna votes for option A, which is what Eve´s want Anna to vote for. What Anna can do next is to vote for option B in a way that nullifies her first vote. So this way, the vote that Anna was bribed to cast is made invalid. And Eve has no way to tell that Anna had cast a second vote that made the first one invalid because it was encrypted. At the end of the day, there is a coordinator Charlie who processes all the votes and tallies the results. The processing and tallying process is done using zk-SNARKs. And then this way, the computations that occur to process the encrypted votes and to tally the results can be verified to be correct and can be done in such a way that preserves the privacy of the data.

Anna (12:21):
What would happen though? I mean, say Eve was trying to blackmail or like, I dunno, bribe tons of people and everyone does this process. Doesn't it end up looking like there's just double the votes? Like say everybody votes one way, nullifies votes the second way, is the total amount double.

Wei (12:41):
Yes. Um, the attacker could see that there's a lot of traffic. That's a lot of votes

Anna (12:46):
Extra votes. Yeah.

Wei (12:48):
But this isn't necessarily a bad thing because in some cases you can vote for more than one item. So you could claim that you had been voting for not just for the voter, the party that you ended the vote for, but also on other stuff.

Anna (13:06):
Yeah. Like further down the ballot thing. Um, I guess the only case where like an Eve type character would be able to say: "Oh yeah, there is something going on". That's like, you're not doing what I'm saying would be if the vote that Eve wanted has zero, like results for it, right. If A, is the category that Eve wants and say, there's like 20 people and Eve has tried to blackmail all of them, but it ends up being a hundred percent option B. Then you've noticed that option A was not chosen and that people have disobeyed. But if there's even one, there's no way for Eve to be able to figure out who had voted in accordance to what Eve wanted.

Wei (13:54):
Yeah. I think that, that makes sense. Um, yeah, this would probably be less secure if there were a few voters, uh, to begin with. Yeah.

Anna (14:03):
You know, we were talking about this in the context of voting and we, and I think when people think of votes, they're thinking about like on-chain governance or something like that, but is there like, are there examples where it isn't exactly voting the way we understand it, but maybe something related?

Wei (14:19):
Ah, yeah. Yeah. Precisely. Um, there are use-cases where, um, MACI could be applied for things that are not like voting for protocol upgrades or DeFi, governance things. And so what could be done, uh, what makes it could be useful is in a system like Gitcoin grants. And this is where you have a way to indicate your preferences for projects that you want to fund. And you can do this by donating funds to individual projects. And then your contributions will be matched in the quadratic fashion by some kind of matching pool. So this comes from large donations from large institutions that once you have their funds allocated to projects in a way that, that reflect the communities, preferences and collusion resistance is when you have a tit-for-tat kind kind of arrangement where project says, if you contribute to me, I'm going to give you something to return. That goes against some of the assumptions of controlling voting and quadratic funding, because we want the votes to accurately reflect the preferences of the community in an unbiased way, uh, in a, in a way that isn't biased by any such incentives. So clr.fund is doing something like that with a, they are using MACI as one of the components to allocate donations to public goods projects on Ethereum.

Anna (15:54):
This is the CLR matching, right? Like, is this already implemented actually? Or is this more like an experiment still like the CLR matching where, you know, people are there, there's like this matching pool and donations and kind of the number of donations is like, it determines how, how funds are allocated. Like that's been going on now for, I don't know, like two years.

Wei (16:19):
Uh, yeah, I think the gitcoin grants has done this for seven rounds. Yeah. Um, I'm aware that, uh, in addition to that clr.fund has recently completed one round of funding for a few projects and they use MACI to do this. So it's been used, it is on a small scale and we are hoping to work together to continue working together, to make this happen on a larger scale and hopefully see this technology work in production.

Anna (16:48):
Cool. So I see. So it's still sort of like, it's still kind of in testing phase on gitcoin specifically, um, on clr.fund actually. Oh, I see. It's like, it's like gitcoin. Isn't gitcoin. Yeah. Clr.fund. Yeah.

Wei (17:03):
Okay.

Anna (17:05):
I see. Okay. Sorry. I thought I thought it was gitcoin, but do you think gitcoin might eventually use it?

Wei (17:11):
I hope so.

Anna (17:14):
I guess this is the testing ground. Cool. So maybe now we can talk a little bit more about how the zero-knowledge proofs actually live in the MACI construct. Where did they live?

Wei (17:25):
The zero knowledge proofs live with the coordinator of the system. I see the Charlie of the system. Yeah. And in this case, we trust that Charlie isn't colluding with Eve. So this is one of the trust assumptions that we can't really avoid in the system. And we also trust that Charlie, isn't going to publish the plain text of the votes to everybody. So in this case, Charlie could be clr.fund or Charlie could be gitcoin grants, or Charlie could be the representatives of the protocol that actually Charlie could just be the people who would run the protocol of whatever system is using, uh, MACI.

Anna (18:09):
Got it.

Wei (18:10):
And so what Charlie does is they use zk-SNARKs to prove that they had processed and tallied all the votes correctly without revealing the votes themselves.

Anna (18:24):
So, but Charlie, Charlie's going to be receiving sort of the, "I voted for A, but then nullified it" and "B", but what does it look like to Charlie?

Wei (18:34):
What Charlie sees is that Alice has a certain public key and that also other users who have their own public keys in a system, and Charlie also sees a whole bunch of votes that they had sent to Charlie during the voting process. And so what Charlie does is take each vote and calculate whether that vote is valid or invalid based on certain rules, such as whether it's signed wit the correct private key corresponding to a public key owned by a user, whether like a nonce and the vote is valid because nonce have to go in a certain order. If a nonce out of order it becomes invalid. Charlie also makes sure that each vote is decrypted correctly. And so a vote that's jibberish would not be valid, so it won't be processed. And by processing each vote, Charlie's updating the number of votes that each option receives and also changing the number of credits, of voice credits, that each user has.

Wei (19:47):
If that vote is valid. So in the quadratic voting mechanism, if I have a 100 voice credits and I spend 25 of them on option A and if my vote is valid, then option A, gets five votes because we get a squared, well, it's 25, but if I spend 81 voice credits, then they get nine votes. Okay. Yeah. And so at the end of the day, Charlie sees the final results and use us a zk-SNARKs to show that all this processing and all this processing is, was done correctly. And the zk-SNARKs doesn't just update the number of voice credits that each user has after they had cast a vote. But it also ignores invalid votes. I see. Yeah.

Anna (20:44):
Are the invalid votes also proven though, to be invalid? Is there another proof that it's not correct?

Wei (20:53):
So if the proves that the vote is invalid as part of the same zk-SNARKSs circuit, what do we do if a vote is invalid, is that we simply ignore it. But not to get into too much detail, we also have a way to prevent someone who's observing the process to have no idea if when we process a batch of votes that all of them are invalid, what we do in here, Is that - and now this is getting a bit deeper into the system - we represent the user's public keys and number of voice credits per user in the merkle tree. Okay. And whenever a batch of votes is processed, the merkle trees updated to reflect the new number of voice credits by user, or whether that user had changed a public key to something else and so on. That, in addition to that, we also update the first leaf of that merkle tree to a random value. So even if all the votes are invalid, the merkle root is going to change anyway, in a way that an attacker can tell whether all the votes were invalid or not.

Anna (22:08):
I don't really understand that. How does putting the first, like a random first leaf as you described it, why does that make it indistinguishable to like what hides, what what's hidden about that?

Wei (22:21):
What it does is it makes the merkle roots, uh, scrambled up because we hash everything together

Anna (22:27):
Because yeah, yeah. Okay. I get it. It's like this randomness that's been added, therefore everything is, is that, is it that, is it like, because it itself is random. You couldn't recalculate it kind of without knowing that

Wei (22:39):
Because we only have the merkle root on chain. So the only public information about the user's public keys and stuff is the merkle root when we changed the first leaf to some random value is going to change a whole, the whole hash.

Anna (22:53):
I see. Okay. Okay. Yeah. In sort of the documentation around this, it talks about two SNARKs. Maybe you've already described it. Maybe you can articulate this again though. Where does each snark live?

Wei (23:05):
Right. So both snarks live with a coordinator. Okay. The first snark is what I just described, which processes the votes and what it does is just to make sure that this is clear before we move forward. At the end of the day, the SNARK shows that the coordinator has countered the votes that each user had cast in the correct order in the correct way, and had also ignored all the invalid votes. And at the end of the day, the coordinator knows that for example, Anna had voted for option A with like five votes and option B of nine votes, but also knows that Bob had voted for option A, with two votes and option C with four votes. So each user has like a ballot with the number of votes they have for each option. To count the number of votes per option across all the users, we use a different SNARK to tally everything up after the full process.

Anna (24:12):
But that's so interesting. Like, how are you? This is just a, like, how do you use a SNARK to tally? Like I thought it Snarks are mostly like, uh, as, I mean, as I've always understood zero knowledge proofs offer a correct or not correct answer, not necessarily like a balance. So how are you finding how are you calculating or tabulating them?

Wei (24:31):
So we, first of all, we tabulate the results outside the snark. And then we also have the snark, which proves that this tallying is correct because the logic in a circuit also tabbies the results and we pass into it, its inputs and outputs. And so as long as the snarks say's that yes, these outputs match what we expect a computational inputs to be, then yes It's a valid... results are valid.

Anna (25:02):
I wonder, I want to try to explain it back to you and you can tell me if I got this right. But it's like one snark includes in it, the actual information. So this is where you have the Merkle roots and you have the leaves. So like basically one snark is the Merkle tree kind of. And the other one proves that what's been tallied on the side is correct. Or did I miss that up?

Wei (25:25):
Um, we are, we use merkle trees for us in both snarks. And what we do is that because the merkle root is public and the smart contracts that we have, but the leaves are private. I see. So when we say that, when it's not, we use a SNARK to calculate stuff about the leaves for each leave. We pass in the merkle proof that that leave is a member of the merkle roots. Okay. And the snark verifies that proof. And if it's valid, then we know that, okay, we are talking about this user and we can operate on their voice credit balance and public key and so on.

Anna (26:04):
Okay. So one SNARK is verifying that the root in a Merkle tree is correct. And one, or like multiple roots are probably correct. And then one is verifying that the tabulation done separately is also correct.

Wei (26:18):
Uh, so the thing is, everything is in a merkle tree. That's the thing that's confusing.

Anna (26:25):
So there´s a merkle tree and then there's proofs going through it, I guess maybe that's a better way to think about it.

Wei (26:29):
Yeah. As a merkle tree for users, uh, public keys and voice credits, and there's a separate merkle tree for the final results. And one SNARK operates on the first tree and the second SNARK operates on the tree that contains the results based on the values in the first tree. So it takes, it takes it. Yeah.

Anna (26:55):
How does, how does the tabulation happen though from one Merkle tree to another Merkle tree? Like what what's actually happening there. Right.

Wei (27:02):
So let's say in the first Merkle Tree, which is the, what you call a state tree, the state tree contains issues as public key, voice credit balance. And here's where it gets even more confusing, a small tree containing the user's votes.

Anna (27:18):
Okay. So there's a sub tree.

Wei (27:20):
Yeah. That's, that's that's yet another tree inside the leaf of a tree. Well, we just had tho think about as tree as like an array, because we had just taken an array, compressing it into one value. And because snark can proof that you can use a SNARK to prove that you have knowledge of any value in that array. You can just forget about the tree and just think about a list of stuff.

Anna (27:45):
Hmm. And you're checking those, those lists.

Wei (27:49):
Yeah. So once SNARK updates the ballot for each user, and then the other SNARK takes all the ballots and counts down the columns. Option A has four, plus two, plus nine votes. And option B has like so-and-so.

Anna (28:04):
Is there any comparable system or is this a very novel use for of zero knowledge proofs? Is there anything similar that influenced this?

Wei (28:14):
I'm not familiar with the prior art in the field? So I can't comment. I can't speak to that, but I'm also aware about a project called Vocdoni, that is also about using also doing e-voting and they do use zk-SNARKs, however, I'm not exactly sure exactly what to expect.

Anna (28:38):
Or how its different

Wei (28:38):
Yeah, exactly. Yeah. And yeah. So I can't speak on whether their use of zk-SNARKs is specifically with regards to privacy or anti-collusion. So MACI is just one instance of using cryptographyto make elections or voting little bit more safe.

Anna (28:55):
So interesting. Is it, do you think it's, um, like, is the focus more on privacy or is it more on this collusion resistance? Like, is there, I guess it has to be absolutely private for there not to be able to be collusion, but like say even someone wanted to see their own vote. Can they see it?

Wei (29:15):
Yeah. They can see it. Okay. Anna, who is a voter can see her votes, but because it's encrypted to only Anna and Charlie. Okay.

Anna (29:24):
Can Charlie see the votes? Can, could Charlie decipher this?

Wei (29:28):
Yes. Charlie must see the votes because Charlie has to count them in the end, however, that is another Eth.research post. This is freedom by Kobi Gurkan where he describes way to provide privacy in a way that Charlie can tell which ballots, which vote belongs to which user,

Anna (29:49):
But for the current structure, the current construction of MACI, there is this sort of trusted individuals. And this is why, I guess you say it should be like the organization that's trying to do the voting because you can assume that they want it done correctly. I'm kind of curious though, what is the solution? What is, what is the way that Kobi, um, suggested that we actually could make, even Charlie not have to be trusted? Is it like decentralized Charlie, somehow?

Wei (30:16):
Decentralizing Charlie is a pretty advanced, uh, um, like it is, it is something that people are thinking about, but it's not at a stage where I'm able to like speak to at this point of time,

Anna (30:29):
By the way, I think the name decentralizing Charlie should be like, the name of an album or something.

Anna (30:33):
It´s something weird, but I like it.

Wei (30:40):
So, uh, yeah, when it comes to what Kobi's idea was, the point is to re-randomise a users registered public key. And so what is re-randomisation?

Anna (30:54):
And by user you mean the voter, right? You don't mean Charlie you mean the...

Wei (30:57):
Yeah. So what Anna is a voter, she has a public key and this public key is what she uses to sign on the votes. And so in this case with a common construction, Charlie can see that Anna had voted for whatever she voted for, because Charlie can look at her signature attached to other votes. But what if we could have Anna change of public key to something else in such a way that Charlie has no idea to tell who owns that new public key. So to do this as a certain technique called re-randomisation. In regular asymmetric cryptography when you encrypt the message, you encrypt it with a public key and decrypt it with a private key with re-randomisation, you encrypt the message with your a public key. Do something special to it called - you guessed it - re-randomisation such that these cyphertext changes. And then you can decrypt this new ciphertext with the same private key and get the same message. But because the re-randomisation changes the encrypted format or encrypted version of that cypher off that plain text, this is a way for Anna to change to a new public key. If she can anonymously submit a proof of the re-randomisation. Um, yeah.

Anna (32:33):
Are we talking about a third SNARK here?

Wei (32:35):
Yeah. We are. This is SNARKs all the way down!

Anna (32:41):
Oh man! Maybe I don't know enough about the exact inner workings of SNARKs despite having talked about it for all of these years, but like, is it not possible that one SNARK does all of these things, you really do need these unique SNARKs?

Wei (32:54):
It would be a bit expensive to do that. Um, I see. And it would make it more convoluted with it because within the logic of a SNARK, if like a SNARK have three functions, there has to be a way to, to ignore the first two functions. If you didn't want a third function. And it just complicates things.

Anna (33:10):
Is everything that's developed around MACI or projects like MACI, like, are they libraries? Are they just like logic? Like what are they actually, they're not like a piece of software that you plug in. What are they?

Wei (33:23):
MACI is built using Solidity, Circom and TypeScript. Okay. So we have three pieces already. And the smart contracts within Solidity gonna interact with other smart contracts that do things like funding and batching pools and stuff like that. The SNARKs are going to be a, you have to do a whole trusted set up, and then produce the proving key, verifying key, and then the coordinator can use them to generate proofs. And the TypeScript is basically the code that glues everything together, allows people to use like the command line interface to interact with the system. So MACI is really a library, but also some CLI tools and also some circuits. So it's, it is kind of a library I would say, but also has a few things of its own.

Anna (34:15):
Back to clr.fund. Like how does does a project like clr.fund actually interact with it?

Wei (34:21):
Clr.fund has a bunch of smart contracts that work with the actual tokens. And if that's deposited into their matching pools and when a user indicates that they want to fund a certain project, their smart contracts takes a transaction and then does like a call to the MACI contract, which they deploy alongside their own contracts. And then MACI updates the merkle trees inside its own storage, and then the clr.fund contracts continue on and operate as usual. So MACI is really make a base layer or like a separate components that that's talking to the use case contracts that deploy MACI.

Anna (35:07):
Cool I'm wondering, like, what do you see as sort of the future for this project? Like, is it, is it, you sort of mentioned that there's like MACI 2, or there's like something, something else is that it MACI 2 kind of like the decentralized Charlie is MACI 2 a new version. What is that?

Wei (35:25):
Sure. Technically we call it MACI 1.0 because the first version was like really basic. Um, yeah. And the first version, there are a few downsides to using the first version because it was not optimized for gas consumption and you could only use it once per contract. So why do you want to do with MACI 1, is to reduce the amount of gas we use per vote and allow people to have more than one election of vote each time they sign up. So we want more flexibility in a system, the core system isn't really going to change because it's still about anti-collusion, but we want to make this a little bit more friendly to projects that want to use this. And we also want to experiment with deploying MACI on top of some kind of like layer2 optimistic rollup solution, because we just want to save on gas costs. And...

Anna (36:27):
Yeah. So you've just said multiple votes. Are you, is this sort of like that down-ballot or is it more like if you had to vote two out of three?

Wei (36:35):
Oh, actually, sorry. I meant multiple elections.

Anna (36:37):
Multiple elections. Oh, I see. Okay. So they're like totally separate units, but using, Oh yeah. Using the same account. So like how, how expensive going back to price then? How expensive is MACI like to use? Because I can just picture like the level of computation.

Wei (36:54):
Oh yeah. This is something that's occupied me for the past two months. And trying to optimize for. MACI is expensive. So when you sign up or publish a vote, it could cost between like 400,000 gas to, I think a 1.000.000 gas and this is expensive. And the reason it's expensive is because we are inserting leaves into a merkle tree on chain, and this is comparable to a Tornado Cash deposit. What we do is we use a SNARK friendly hash function and the SNARK friendly hash function is unfortunately expensive in the EVM. What we are trying to do if MACI 1.0 is too... what we are going to do is to allow people to deposit in such a way that they don't update the entire merkle tree every time they deposit, or they cast a vote or they signup. The idea is to just insert it into like a really small tree, like a tree of two levels. And at the end of the day, the coordinator mergers all release together into the single merkle root. And this in total actually costs less gas and it also costs much less gas for each user.

Anna (38:10):
Cool. And so you picture kind of doing this and then also kind of experimenting with this on an L2 where it would also be cheaper, I guess like those are, those are two separate optimizations, but like could be used together.

Wei (38:22):
Yeah, I think, yeah, I think using an L2 is going to solve the gas issue, but I don't want to place my bets on a whole new system just to solve this problem. I just want to find a way that works, even if we had to use L1.

Anna (38:37):
Cool. Yeah. I feel like we've covered a lot of ground with this explanation of MACI, but maybe is there anything else that you think our listeners should pay attention to or think about when thinking about MACI?

Wei (38:49):
Sure. I think listeners who are interested in building complex systems using zk-SNARKs would find MACI really interesting. And that's because it's a whole new way of thinking about building an application. Um, first of all, you think about building service SNARKs. It's a different paradigm of understanding what kind of data is private and public and understanding what can be proven and what can't be proven and things like that. So the construction of MACI is, I would say that it's like, it takes some time to really understand at a technical level and myself, I took like, like two whole weeks to really understand how this should be built when I first started the project. And sometimes I, sometimes I find that it's so complex that I have to go back to the specifications to understand what's going on, even though I wrote the specs myself. Um, so yeah, I think, I think MACI has to be an, a really, really enriching project to work on. And it would be possible without my teammates: Barry, Kobi, Kendrick, Chih-Cheng and Nashban for very good feedback and a lot of work throughout the months.

Anna (40:07):
Cool. So given that like the first time that we met was actually to talk about the trusted setups. I'm wondering like when we, when we talked about trusted setups. So we talked primarily about Semaphore. So has MACI had a trusted setup? Will it have one, does it need one for every election? Like how, how does it work with the sort of trusted setup in the SNARKs?

Wei (40:28):
So with MACI, we can do a trust that's set up and we have to, if you've been to a place, a lot of funds, a lot of value on-chain into it, but we haven't done that yet because at this point of time we just haven't got around to it. Uh, but there are plans in place to run one. We need a trusted set up per circuit. So they're gonna be at least two, uh, two setups, one per circuit, and it could be done in the same process. So you could have, have some kind of like trusted set up program that takes two circuits and runs the set up for both. And then you get output. So it would take some, some more time than just doing one circuit, but to a user, it should just be in a one-shot process.

Anna (41:17):
One shot. Is this still, is this like still using the Perpetual Powers of Tau as its Phase 1? Or does it have to do both phase 1 and phase 2?

Wei (41:25):
This would be a phase 2 trusted set up per a circuit. And this is if we stick to Groth16 as the proving system, I am hopeful for other systems that don't need a per circuit trusted set up, such us Plonk. And, um, I've been keeping an eye on the developments in building DSLs for those systems, so that MACI could just iterate faster because it would be so much better if we had a system where you could just skip the Phase 2 entirely and you could have circuits for different tree sizes, and it would be much, much easier to do things.

Anna (42:06):
So it sounds like you're kind of like waiting a little bit to see if maybe there's some of these solutions or some of these trusted setups happening that you could also use the parameters from. But are you also examining like zero knowledge, proof systems that are just not... like different? Like, are you ever thinking of replacing the SNARK?

Wei (42:25):
Yeah. Basically we are window shopping at this point. And I can't really like say that tell you which system I've chosen, because I think everything has said Groth16 is not super developer friendly yet. I think there are some frameworks that have been put out there that are really promising, but I have not tested them very extensively. So in the zkSummit, there was a presentation about Mattar Labs doing Zinc, and I believe they're using Plonk. So that's something I want to try out.

Anna (43:01):
Cool.

Wei (43:01):
And there have been other developments in taking circuits in Circom and plugging them into Plonk. Again, those are really early on, it's too early to see whether that's going to work. Um, but I am very keen to, to try those when it's ready.

Anna (43:21):
Well, we're all keeping our eye on what's coming out in that department. So good to hear that you're kind of keeping, keeping your options open, I guess you can say. Um, nice. So I guess if somebody wants to get involved with MACI where did they find you? What did they do?

Wei (43:36):
So I am on Twitter, um, @weijie_eth, or you can link them in the show notes if that's okay.

Anna (43:46):
For sure! And should they just tweet at you or is there also like a GitHub repository?

Wei (43:49):
There is a Github repository and all the code is open source. And there are also a few recorded presentations I made at a couple of meetups. So I think those would be good resources to look at.

Anna (44:03):
Nice. Oh yeah. And just before we sign off, you know, we were talking about Gitcoin earlier in the show. And even though I understand MACI is not currently working under the hood in Gitcoin, I did want to just quickly say that we do have a grant for the Zero Knowledge Podcast in case anyone wants to contribute. It would be really good time cause there's the matching on. But anyway, thank you so much for sharing all of this info about MACI with us and uh, yeah. And I hope to have you back sometime soon. Yeah.

Wei (44:29):
Yeah. I'm a huge fan of the podcast and I'm so happy to be here.

Anna (44:32):
Cool. And to our listeners, thanks for listening.