Anonymity in MACI - Marija Mikic | 3327

I thank you today's topic is a little different than the topics that we have here uh before so I hope that someone of you uh will be interesting this topic I hope so let's start uh today's topic is anonymity in Macy when we say may see we think that Macy is a minimal anti-collusion infrastructure this is Project from ethereum foundation and my team 327 obtained a grant to add anonymity in Macy we think that we want to add that no one cannot know how Waters voted so anonymity is in relation with voters but before we go uh there how much he actually works and what is done so far in Macy and what we want to add in Macy I think that is very important here to note that it's very difficult to create voting system that is completely resistant to collage and we want to have a voting system where we cannot manipulate with votes when we cannot censor the votes and also to have privacy and anonymity of voting so naturally question arise is it possible to make this such a voting system perfect voting system without uh collusion and I think the answer is yes and I think that this answer is related with Macy so let's start uh we can tell that Macy is an application which allows a user to uh allows user to have on-chain voting process and this voting process is not completely collusion resistant but I think that may seem uh have a big made a big step in this way and with adding anonymity I think we will get a voting system that is completely resistant to collage or we will be so close uh from technical perspective we can see that Macy is collection of smart contracts contracts of course zero knowledge circuits and type script packages and I think that is important to say that initial idea uh came from vitalik and we said before but I think it's important to remember that Macy currently reduced the bribery and disables tensor voting today I think that is a very important to answer on these three questions the first one is how actually Macy Works who can see how voters voted and is it possible for voters to cancel the vote if for example we have a voter which was blackmailed okay let's start how Macy works we have here two different roles the first role is we have users on voters and the second role we have coordinator we have one single coordinator and this coordinator uh he's he's trusted coordinator uh so voters need to sign up first with theirs public key and there's public key plays a role of their identity after sign up phase voters need to vote and before they send the vote to Macy's Mark contract they need to encrypt that vote and when they encrypt that vote we call it message and they send the message to Macy's Mark contract after that yeah it's important to say that they encrypt the message using share key and only voter and coordinator knows that share key okay so when a coordinator decrypt the message he can decrypt the message because he knows share key he gets the vote but to be more precisely we want to uh we want to explain what is the message the message uh to get the message we need to put uh some things together for example we need to put new public key vote option vote amount and some others variables that is not important for us today and we create a comment when we create a comment a user needs to sign this this comment with his public key when he signed this comment with his public key he needs to encrypt comment and his sign to obtain a message and this message will be sent to Macy's Mark contact and why this is important because uh voter in this message can change his public key and also he can change his vote in one message and this is important if user was blackmailed he can prove to a blackmailer that he wrote for option that blackmailer wants to vote but that message will be invalid and I think that the best way to understand this is to give you one example for example we have a voter or user how do you want that he has a public key one and he used that public key in sign up phase okay after that he wants to vote and he wants to vote for option one but he was blackmailed to vote for option two so firstly he will send the message he will wrote here in the field New public key publicity too he wants to change his public key and he will wrote he option one because he really wants to vote for option one after that he puts all this stuff together to get a comment sign this comment with his public event and after that encrypts the other sign and command to get the message and send this message to Macy's Mark contact okay then coordinator decrypts the message he will update his State he will wrote that uh this voter change his public key and his new public key will be publicly too and he will update a state tree with the vote for option one after that a user can vote again he can right here public key one the old public key and he can write here vote for option two he will put this stuff together to get a command he will sign it with his public key one and after that he will encrypt the command and signature to get the message and then he will send the message to Macy's Mark contract when coordinator decrypts this message he will show that the uh that the public key that user use to assign this message is not the same like his previous public key and this message will be invalid but beautiful thing here is that the voter can decrypt this message and can prove to the blackmailer that he really vote for option two and blackmailer cannot know that this message was invalid message so user can vote for option they want and blackmailer cannot know that user didn't want for the option that blackmailer wants to vote let's start the encryption in Macy we are using elliptical difficultman encryption to in order to obtain the shared key uh we we will uh we will use generator point on an elliptic curve uh this is G and we will use private key of a user and private key of coordinator to get public Keys we need to multiply this uh um this private key bit generator point on elliptic curve when we multiply this we will get the point on elliptic curve and that point will be the public key it's very easy and how we can get the share key we told already before that only user and coordinator knows share key when user can multiply his private key with public key of coordinator because public key of coordinator is public for him but coordinator can do similar similar thing coordinator can multiply his private key with the public key of user okay and both will obtain the same and this is share key and this is one point on elliptical and how we get this because we use very elegant property of elliptic curve and that property give us this equality so only user and only coordinator can know the share key of course the security of this algorithm lies in difficulty to calculate discrete logarithm well when the Voting is over we will have coordinator which will enter the scene coordinator will need to make a zero knowledge proof that he decrypt all the votes correctly and that he update a state 3 correctly after that he needs to collect all the votes and to make zero knowledge proof with outcome of the voting so every user can be sure that this voting was done correctly okay but no one will know how voters voted except coordinator remember coordinator can decrypt everyone's vote so coordinator knows how voters voted okay even if coordinator is corrupted he cannot add the extra vote he cannot censor the vote because if he is trying to do that he uh will not be able to make uh true uh valid zero knowledge proof so uh we will not have finished voting never but uh we can be sure that coordinator cannot cannot publish false results and this is very important in the previous slide we explain everything what is done so far in Macy and I think that the big problem is uh because coordinator can see how voters voted and if you are good with coordinator he can pass you information and you will know how voters voted and this is good for you but it's not good good for voters and because of this I think that is a big problem that we need to solve and we solve it adding anonymity in Macy so how we could achieve this thing what do you mean it's easy we want that coordinator cannot see the link between the old and new public key okay so what we need to obtain this we need to have new type of encryption we will using algamel encryption we need rare randomization and of course we need zero knowledge proofs so we will use the same notation as we used before G will be generator point on elliptic curve and we have private keys of user and coordinator and their public keys so the user is person who will encrypt the data for coordinator in the user needs to do first thing that he needs to do he will pick some random number from interval and after that he will multiplied this random number with a generator point on elliptic curve to obtain big X uh I want to note here that if we want to go and obtain Little X from the big X we cannot do it because this is discrete logarithm problem okay um big X will be sent to coordinator from the user and we have one more things to do here we need to map the message on elliptical and this is hard problem for example if we want that some message some number some secret map on elliptic curve and we want to do that in the way that first coordinate of the elliptic curve point B this message we knows how equation of elliptic curves like and when we want to calculate the second coordinate we can get that that second coordinate is not in the final field that we use so it's a problem and how we solved this problem well our message will be some states and we have final finite numbers of States so we can find bijective mapping of states to elliptical for example we can map 0 to Infinity Point we can map one to base point on elliptic curve okay and this is bijective map we can go in vice versa okay and we done it like that okay after that a user can calculate this this is a public key of coordinator he knows Little X this is a secret and add this point on elliptic curve and obtain m e and this is mistake user will send m e and X to coordinator after ascending this coordinator needs to decrypt the message how he can do it well uh this left hand side uh coordinator cannot decrypt because coordinator doesn't know little X it's a secret but we have equality here and coordinator can compute this he knows big X and he knows of course his private key so on this way he can obtain this and after that because he no m e users sent them to he can obtain the point M which represents message on elliptic curve and in this way coordinator can decrypt the message it's important here to note that using Algoma encryption coordinator can decrypt the message without knowing public key of the user and when we used share key we can do that because to decrypt the message coordinator needs to know publicly of the user and here he doesn't need to know of course the security of Alabama encryption lies in difficulty to calculate discriminate logarithm like we have it before and we said before that we will need to to use rare randomization why this is important because we usually use rare randomization when we want to convey in the same message when we have two Cipher texts but we don't want that that Cipher text be connected okay and um that function uh that randomize uh existing side protects uh can be decryptable using the same way uh when we decrypt existing Cipher text and this is important too uh I think that maybe we don't need to go through this if it is okay for you uh so what we want to add we want to preserve two nice features we want that every vote to be encrypted and stored on chain we want that user have ability to change his public key in order to prove blackmailer the heat really vote for option that black mayor wants of course we want that message to be invalid but we want to add one feature and that is that coordinator cannot know how voters voted so what how we will use all uh that we said already Algoma encryption decryption randomization let's see we don't want that coordinator can see the link between old and the new public key so we want that user make zero knowledge proof that he knows private key for his old public key okay and um he will need to we will need to add two new sets one of them is set of deactivated keys uh user needs to prove that he knows private key for old public key that is in the set of the activated keys so we will need to have membership proof and of course here we need to be more careful because we want that user can generate new games only once and because of that we need to add nullifiers and we need to add the set to store the nullifiers and we need to add some more things we need to add two more types of messages the first messages is for the activation publicly to deactivate the whole public user needs to send the message to coordinator and this message will be encrypted using elgamel encryption uh after decryption coordinator will will add this this public key in the set of the activated key if this public key exists and he will also add encrypting state in uh in the field in that field there is uh public key that we want to um deactivate if anything go wrong coordinator will put in this set public key but he will change uh the state and the state will be false so after that user can create new public key uh proving that he have a public key in the set of the activated keys so what user needs to do user needs to make zero knowledge proofs that he knows private key private key for the public key that is in the set of the activated keys and the output of this circuit needs to be nullifier nullifier is Hash of public of private key and needs to be randomized message because we don't want to see connection with this message with old public key of user and we don't want that coordinator knows uh who is that user and because of that we need to use array randomization okay when users send the message coordinator decrypts the message and if everything is okay is uh if proof what's valid if an alifier is not in the set of nullifiers coordinator will uh according to the coordinator will update State and he will add this new public key and this encrypted state it every if anything goes wrong he will add also uh this uh public key but the state will be false and with this we really obtain that coordinator cannot know how voters voted so we get anonymity in voting like we want and that's it thank you [Applause] we're welcoming questions so if if all this happens on chain that means transactions are assigned and they are signed with my private keys of my address right so I I wonder I'm trying to put myself in the worst case scenario of blackmailing right if I cannot know who you have voted for but I still will know if you bought it or not right so maybe the blackmail could do you think the blackmail could turn into forcing people not to vote because if it's on chain I can see that your your address your wallet has both one way or the other right and if you cannot control your the direction of your boat maybe the blackmail turns into okay I'm gonna stop you for boating I think that I understand what you are talking to me uh if I understand good uh probably the blackmailer uh will know how these things are are working and I think that maybe the best way uh is uh to have a large enough set where we have all keys deactivated to obtain anonymity and maybe we can add uh when sign up users old to be deactivated or you're talking about keys I think you're talking of two different set of keys right the keys that were initially were the the share Keys uh but all these transactions need to be signed in ethereum with your wallet right where your address right and that is something that we cannot hide so I guess my my point here is uh the identity of the voter is still expressed as an ethereum key right that goes into every single transaction that goes on chain right we cannot hide that that is still public right so there is still a visible uh signal that links the person the individual to the transaction performing on chain okay but that now it's clear thank you thank you cool any more questions do we want to vote on it okay thank you Maria [Applause]