Zero Knowledge in 2023 - Andrija Novakovic | Geometry

hahaha uh hello everyone I'm Andrea I'm cryptography researcher and geometry and I'll be presenting a joint work with wayj we worked on something called semacolk and first of all when building privacy application on ethereum we always had this evm trilemma so you always had a applications that you want to be cheap in smart contracts uh you want to have a high privacy which means that you use very efficient and audited hash functions and similar Concepts and you want to have a fast Brewing time for scaling and it's kind of very hard to achieve all three so first of all you can do really easy smart contract costs with high privacy but by using like sha or cachac functions but the problem with that is you're proving time of the circuit gets enormously huge and everything gets very slow and you cannot do that if you try something else if you try to use a snark friendly hash functions as Poseidon Mimsy and I don't know how many you heard of uh you get faster proving time but now doing these hash functions which are snark friendly are so to say not evm friendly which means that it takes a lot of gas to to update your smart contract with with some uh to just compute hash function in the contract so it's very hard as I said to achieve all three but what we are able to achieve with this uh with this protocol is to kind of actually pack and achieve all three so that there is no more tree Lemma okay so semicolc easy to say is a very gas efficient zero knowledge set membership protocol okay so uh maybe the keynote is that if you compare current state of like semaphore protocol or tornado cache our protocol achieves like 90 percent cheaper insertions in the contract Okay so uh that's like the main point the huge picture is that you're proving time gets so low around 50 milliseconds uh your verification cost also since we have like a very customized protocol for making proofs and verifier uh is in the cost almost similar as grad 16 which has the cheapest uh very far to execute in the smart contract we also added something called private information retrieval which I'll speak later about so uh this new kind of lookup arguments that are very popular last few years are always coming with some pre-computation part and we cannot Escape that and that precomputation part takes around 30 seconds so to say and after that you can generate your proofs is like more than 50 less than 50 milliseconds after this one-time pre-computation part so it's currently uh kind of common to measure and Benchmark your uh like proving time verification cost and uh in general gas cost of maintaining the group in uh size of 2 to the 20 and simply because if you want to get higher groups like 2 to the 30 it just gets so expensive and so slow however what we are able to achieve is this constant proof times which enables us to go to extremely large groups which for applications as like Z cash internet cache is very important because you want to have that group maintained like forever so what is the membership proof uh it's very common primitive that is used in zero knowledge applications so simply have some public set of some commitments and you want to prove that you own one or many of Secrets which leads to commitments in those sets and the most common approach now is doing it with myrtle tree so you'll represent your group as a Merkle tree and in order to prove that you know a secret to the Merkle tree you will actually privately compute the Merkel pet and you'll just the circuit the proof will just constraint that you're using the good route now this is again a huge issue once you want to go to this two to the 30 groups because your tree gets very deep and let's say that you take the most friendly hash function today which is like Poseidon uh the smart contract cost of maintaining that tree is enormously huge so it's like never used however we take very different approach we build this very customized protocol based on memc hash and we leverage a kcg commitments I don't know if you heard of them so that's also a commitment scheme similar to Miracle tree which gives some nicer properties as a constant verification time uh and now insertion in your group in the contract instead of taking uh a lot of hashes through this tree takes just a few elliptic curve uh operations in the contract which gets to be just like 68k gas which is extremely cheap compared to million or more for a current state of the applications which use Merkle trees uh each General agnostic to curve you can use any pairing friendly curve uh we built our system and bench it on bn254 just to be compatible with ethereum uh I'm not going to stay here for too long the idea is that once you get to this uh LaGrange base setting and working with commitments in kcg scheme you can leverage a lot of homomorphic operations from this commitment to very efficiently update your group however large it is so it's not that straightforward since you wanna extremely huge group you need to like store all LaGrange basis commitment in the contract which again will be very expensive so we again have to leverage some more efficient techniques to to enable this again cheap updates but in general what we achieve is the 68k gas it's very scalable you can batch it very easy and it's very easy to just maintain that group Okay so I don't know how interested uh you can be into this but um if you can like look at this formula where you update C it's uh it's doing something that is called a scalar Edition and points multiplic and scalar multiplication and point condition which happens to be again not that cheap in contract but since you can update with just two of these it's actually very very cheap compared to what you do in hashing all your Merkel pads um it's all done on chain of course uh okay so when we speak about these applications you always want to have some kind of signaling or uh so to say uh whistleblowing or like just spending something so all these applications are based on a few similar Concepts where you have some public group you have some secret as we said and only once you can spend something so if you look at the tornado cache you put something in the pool you prove that you uh put you have something in the pool you withdraw and then you cannot double spend again so our goal was to really keep the same interface as all these applications nothing to change on the API level to have like backwards compatibility and something that is very audited so to say so all changes that we made were only on the actual protocol level so the the the interface itself is already compatible with all applications that are out there uh that are based on membership proofs signaling which are preventing double spending or double signaling uh okay so if you look lower what's the difference from maybe the official version of semaphore which is the most popular primitive for this kind of proofs um as I said we use different hash function which is mem C compared to Poseidon and then we had to do a lot of math so you have something called caulk plus that's this new lookup argument and we had to customize it in order to make it compatible with all that we want but this is actually the key why we achieve uh why we achieve this fast uh like lower than 50 milliseconds pervert time um that you can easily run in browser then I guess everybody is already familiar with Planck so the problem with Planck is that you're very far in the on chain can be much more expensive than grot16 even though plan gives you some much better uh performance and uh much Freedom when designing your protocol for the proverb side so we also had to do something similar to plunk but also like customized in order to achieve this very specific grot16 verification Target and uh Halo 2 the the framework developed by zcash also has the multi-open argument which like allows you to prove that your polynomials are correct and you also had to like build very custom protocol which is kind of modification of this to again achieve all this uh all these things that we needed for the protocol and now uh as I said you have to pre-compute a lot of data and maybe that's also not very uh good for user and not easy to just put that burden on user so uh let's just again high level see what's happening so you have to in about 20 seconds or more pre-compute some data then you can many many times generate the proofs in less than 50 milliseconds you just submit proofs on chain and that's it now uh you can as I said do it on any elliptic curve you have like a lot of freedom but still you have to leverage all this data do it all locally will you do it in browser where are you how are you going to do setup how are you going to update if group gets updated that's kind of the problems that are not very specific to this scheme these are the problems which occur in all this signaling based privacy pools so what we do we privately Outsource computation so what I mean by by saying that there is something called private information retrieval which allows you to download data from a public database where the server which holds the database learns nothing about which index or which data is being queried okay so what actually you're going to do now you're going to privately retrieve some data you need to for proof so that you don't need to bother by storing it having uh maybe some secure extension and key management in general like some secret management platforms so it's all precomputed on one server we did this with collaboration of this very nice team from Bliss which are also working on private information retrieval so what's happening on one server that server actually uh maintains the group and that server learns nothing about your privacy uh it cannot do anything maliciously on you so it's just like a helper some imagine it as a real layer and now what you can do you can actually Outsource all this precomputation and efficient updates of the group to that specific server or many of them however and then you privately retrieve the information you need to compute the proof which is just like one query to some remote server which is again very fast uh it's all open source you can see it on our GitHub uh we told like benchmarks with very detailed explanations and documentations how this proving system work how can you spin your own groups how can you integrate it on ready in already maintained applications and how to migrate to this and this thing for like private information retrieval is not necessary if you still have a system which does not leverage something like that it's not must have that's just something that makes users of these applications even easier um here uh we just uh put some uh codes to show how easy it is to use so literally you have a bucket where you can write data in that bucket and you can just say private read and you will read data from that bucket well in our case will be some quotients on G2 group of the elliptic curve and I'm not going to bother you with that but you just can take that and the server who hosts database will learn nothing about which thing you queried and if you think current applications can have that problem if you try to like time these queries like it's common to have some servers maintain these huge Merkle trees from which you can take the Merkel pets in order not to store on your local storage and whatever and now if you try to time attack you can try to deduce which person downloaded which index and who is actually making the proofs with this it's just not possible and now what we want to do next is uh also build a very tailored protocol for using Poseidon instead of Mimsy hash function in general we just want to encourage teams to build tooling around this and migrate already existing applications into the into the space um we need to build something like a vasm to to give you the the browser compatibility but that's now all straightforward after this heavy lifting and as I said you can take this presentation find all the documentation uh all code you can Benchmark it locally you can put your trusted setup into that if you already have something like it's very easy to just migrate can start using this also Vijay made a very nice documentation where you can really step by step see how everything of this works and yeah thank you [Applause] well I guess I should say here for a question from the audience there's a question feel free to raise your hand yeah yes um do we have volunteers in the room um to pass the mic hello thank you for a nice presentation uh what is the good use case for this okay so uh this is like just a low lever protocol for this kind of membership roofs but if you look now uh all kind of privates voting that happens on ethereum is based on this uh all these privacy applications for uh astronado Casey cache they're all built on this concept so this is just like a new kind of protocol which just optimizes kind of all parts of those protocols so use cases already there this is not like uh building new application this is just a speeding up all those applications is there a chance that this could be used in a way for authentication and authorization like could this replace current login uh yeah yeah I think that's already being used on a lot of this untrained government governance kind of things where you literally prove that you have credentials that are in the group so yeah that's quite common thing to do thank you oh yeah so we have another question we do hey so you mentioned there's something akin to private key so how so I need to I want to understand like having the private key and having this something akin to private key how does that relate to user experience yeah okay so when you when I say private key uh it can mean a lot of things so here you have like a few values that are your witness which you can call Private key and now you need to keep them somewhere secure yeah and also since these groups can over the time they get larger like you have new stuff inserted some stuff spend it and they are changing uh you wanna always have as big group as possible when making the proof because that gives you the most the biggest privacy so to say so you kind of want to keep up to date with how these groups uh is getting larger and now you need to have like as in a myrtle tree bass proofs you have a new Mortal tree commitment now you need a different Merkel pet to prove that you are the membership that to prove that you just have a valid Markle path leading to the commitment here however since we have this different kind of commitment you have some elliptic curve points that you need to preserve and pre-compute so yeah we literally just enabled user not to care about it and they can just retrieve it privately from from this server that actually does all of that and that server cannot do anything maliciously like um if they do something wrong you can just slash them and they can never learn anything about your actual private key nice nice um so one more question if I may you have time please go ahead um so you mentioned private voting as one use case um so maybe a noob question how would you tally the votes in that case how would you do what Telly um compute the votes oh oh so um what's actually happening is the signal you're sending it can be like a message uh a memo or like a vote it's public the application just allows that nobody learns who from the group actually sent that vote so your smart contract will just come to the vote and that's it so it's privacy preserving right yeah thank you do we have any more questions yes there's a hand there oh uh okay yeah sorry this 20 seconds of pre-compute that's using CPU GPU or something else oh it's just simple CPU preconciliation uh but you have to do it in order to have this uh caulk plus lookup argument which I'm just not gonna go there now but uh it's based on just like starting with some group pre-computing something and then we again add some more stuff to that to enable also very like fast updates of that group um so yeah but you kind of do it just once any more questions from the audience raise your hand if you do yeah I think that's it do we have any more questions okay then so please give it up for Andrea for an amazing talk [Applause]