Zero Knowledge Proofs: From Theory to Applications

Transcript

the newer systems that you would use additively homomorphic encryption have a more involved and uh susceptible setup phase that you have to do really carefully in this setup phase um the parties running it are going to use um asymmetric encryption so some forms of public cryptography to take um some secret and cook up from it various queries that you would want to ask later on and somehow encrypt them in advance in a way that the prover the honest proofer can answer them very easily and efficiently but approver who wants to prove a false statement will

not so this setup phase involves some secret that if it is somehow leaked or revealed um you know can ruin the system in the sense that knowing that secret that trapdoor would allow to you know 4 Forge pseudoproofs of of any statement true or false we published a paper showing how you can do multi-party secure multi-party computation to amateur amortize this uh this uh harmful secret this trapdoor among several parties if even one of us is is honest in the sense that don't reveal the secret then even if the rest collude the whole system is

still secure zero knowledge snark systems they depend on this kind of piece of mathematical scaffolding known as a reference string and it's a way of really making the computations that you need to do for a zero knowledge proof sufficiently Speedy that you can get this stuff to public networks straight away so it allows the kind of the proof size to be quite small and the amount of work that needs to be done for you to send a transaction to be kept relatively low what it does mean though is it's it's predicated on Computing a kind of encrypted number but no one must know what that encrypted number is and so the way we did this was through a sort of form of multi-party computation where we went to our community of people who were interested in the Aztec protocol and

said will you take part in this ceremony and this ceremony is such that it would require every single one of these participants to collude with everyone else in order to be able to reconstruct this number that actually needs to be destroyed and never know so if just one person behaves honestly and they destroy their their toxic information the system's secure there was a variety of technologies that allow you to scale systems up and assert their correctness and computational integrity and also to do so in a privacy preserving manner with ZK Roll-Ups we do something very elegant we provide a zero knowledge proof or like 16 zero knowledge proof of a snark of validity of all the

transactions that happened that produce this new root hash and the snark is verified by the smart contract itself so what it means is it's been verified on all the full nodes of ethereum and only if the snark is valid uh then we change the the new root hash on the smart corner and this way we can guarantee that no invalid transaction is ever included that's the difference between optimistic and CK in CK you just send the proof and this proof is validated by the smart contract and if this proof is invalid then the smart contracts you know just the transaction fails transaction throw so it's like the state doesn't change okay so it's impossible to forge an invalid

transaction in a secure lab and even better when it's forged so once the transaction is forged it cannot be rolled back you know it's it's fine and it's it's it's there um so you normally have someone called sequencer collecting the transactions from the users and packing them in a block and Computing the new root hash of this block with all the roll ups right now uh as far as I'm aware everyone is currently using centralized sequencers uh because with Roll-Ups you do not rely for the sequencer on the sequencer for security with CK Roll-Ups and zika Singh specifically what you do is you submit a transaction to the sequencer asking them

to withdraw the funds for you uh on their one they will include in the block and the moment the block is completed and verified on ethereum you will automatically get the funds on ethereum to the address which you wished they cannot censor you and all one so if you feel censored you can always go to layer 1 and retrieve your funds through some additional mechanisms in our case it's called priority queue and we have something called Exodus mode or emergency exit mode where you can exit without asking anyone for permission so A system that is scalable that's the s in the Stark which means that as the number of transactions you're processing goes to Infinity proving time scales with it nearly linearly so it's almost

the same cost to just compute the stuff as it is to generate a proof for it and at the same time verifying a proof skills exponentially smaller than the amount of computation and also transparent which means that there is no trusted setup in in all the the only ingredient that you need in order to make the system uh secure is is public source of Randomness or you need to assume that the Universe has some entropy in it one could say that the term succinct refers only only to one part of scalability which is you want the verifier to be very efficient so succinctness is not enough for

scalability it's necessary but not sufficient you also need this other aspect which is super efficient proving time so when we coined the definition of a stark we wanted to make sure that we're also capturing that aspect as well which is why we think it's better to use scalability as this sort of uh two-pronged definition both efficient proving time and efficient verification time snarks have uh famously very short proofs like around 200 bytes bulletproofs have longer proofs around let's say two kilobytes or so and Starks have longer proofs around 20 kilobytes

so you go one order of magnitude increase moving from Starks to bulletproofs and then to Starks in terms of uh verification time snarks and Starks are pretty similar they're very very fast the Starks are a little bit faster in verification but you know 10 milliseconds in snarks versus I don't know eight milliseconds or less than Starks and then bulletproofs are are less so because uh verification time and bulletproof scales actually linearly with the amount of computation not uh so so bulletproofs are not scalable according to our definition of the term uh that's in terms of verification time proving time is fastest in starts then

about one order of magnitude slower in snarks and bulletproofs and I think the most important difference is in sort of this other dimension of future proofing the systems or what kind of assumptions you're using so Starks require only the existence of some collusion resistant hash function which implies that they're possibly post Quantum secure and they require very lean cryptography bulletproofs require assumptions regarding the discrete log over elliptic curve groups which is a slightly more exotic problem but it's been around for I don't know like two decades or so and then snarks require things called

knowledge of exponent which are even more recent and slightly more exotic the first generation of ziki Roll-Ups were application specific they could only do some very limited fixed functionality for example transfers or or amm or decks but it was limited to to one function which could be repeated multiple times with smart contracts the challenge was that the users want to Define smart contracts themselves A suitcasing 2 will have not just smart contracts but full evm computability or like evm portability you will be able to take existing smart contracts that are live on layer 1 and easily Port them to the keysync and just deploy out of box most

of them will just work and this was very hard to wrap in zero knowledge Pros like is your knowledge proofs require the programs for which we can construct snarks and they prove some computational statements to be con representable as arithmetic circuits you can think of it as a as a uh is it like as a physical circuit you have some inputs and then it goes through some gates in like one one wave flow without uh without back loops and then at the end you get some results so the other way to think about it is a is a just a function a mathematical function

F from X is equal to a plus b times C blah blah blah you know like some it's a very complex expression but it's a single expression there's no way to encode Loops in this expression there is no way to encode conditionals except for just like build two branches of this conditional statement separately and then combine them uh conditionally like if we wanted to go to the left Branch then take this result if you want to go to the to the right Branch take this result but that that's some fixed structure which you cannot program so how you add programmability um so that that was a big challenge one of the main problems with Xenoverse

cryptography is constructing this proofs is generally quite slow as I said it's like a like factor of 100K to a million times clearer than running a computation now one of the ways that this is can be sold is by delegating proof construction to third parties but because we've had we're dealing with private transactions you can't delegate pre-construction because then you're leaking information secrets to that third party so in so effectively all of these programs that have been created in Noir they're also being turned into Xerox proof that where the pre-construction is happening be made directly by the user you know by people with old laptops crummy phones Noir is our highly efficiency it's not programming language it's a rust based in tax language that compiles directly to a highly optimized

clock circuits the first thing that non needs to solve is that these programs that people are creating need to be turned into extremely efficient zero knowledge groups you'll have a program uh solidity program that when you compile it you get a set of bike you said a set of bytes that are up codes mainly so you just take those bytes and instead of running here you just run there it's like at the end is from the user perspective is like having a side change it should work the same way with a ckvm so we have our growth 16 or block that's uh validating a set of starks okay in each Stark we expect to be able to process half a million gas and we can have I would say easily about

1 000 Starks in a single proof so this is maybe two orders of magnitude of the current ethereum so you can actually get privacy out of box with with this kind of type of solution with easy roll ups because for the transactions uh that contain some snarks for privacy you don't have to publish the proofs on chain it's sufficient to have them as a witness or as input of the transaction which you just omit in the final block but you verify them in as a part of of your block proof so that means that you will be able to implement something like zcash protocol on top of ziki sync and the transactions should the

transactions in this protocol will cost almost the same as normal transfers just slightly more expensive so in a nutshell it enables private tokens on ethereum it's a kind of a privacy layer that you can use to either create a private token actually like someone like a ESL C20 token or you can wrap an existing erc20 token and make chances of it private the reason why we went with the uotxo model is because it's significantly easier to give strong privacy guarantees in UTC terminal than it is in an account based model look term if you want to break the transaction graph entirely so you want to hide not just the values being sent to the identities then that makes an

account this model extremely difficult to do because if you're hiding people's identities then you don't really want there to be a kind of a like one encrypted number which represents somebody's balance because making repeated modifications to this balance it's very difficult to do that without leaking the fact that those transactions are connected but the problem with these approaches is that um in a private world um you can't have public state because modifying a public a public State variable leaks information about what you're doing for example things like Eden swap you need free assault you need to understand the total amount the total Supply you have a big of an asset to perform so it does established

liquidity you have and so if you deposit into a liquidity pool then you're changing the total amount of liquidity that's public variable so people can see what you've deposited that's not private um similarly for makerdale if you create a collateralized debt position that's private that means it's encrypted and so how in the Blazers is anybody supposed to figure out if you're becoming under characterized and if they are how are they supposed to liquidate your position because it's encrypted only only the cdb Creator knows how to decrypt it and they're not going to help you liquidate their position so that's one of the fundamental problems um with with privacy um basically you leave you make you keep the default protocols public you know uniswap make a doubt you leave them where they are you hang out on layer one

completely public everyone can see what's going on and what you do is you make the assets private you ensure that individuals have uh their Holdings of various cryptocurrencies is anonymous so if for example let's consider the make it our position again imagine you know you know make this public so you can see when a CDP is created you can see its value you can see when it comes on the Killer is Liquidators but you don't know who holds it and that's very high quality privacy because at that I mean it could be anybody and so the most important thing isn't an operating to make the the the the the the the D5 protocols private it's not to make the the the um this effectively like the sites which interact with the value private the important thing is to make the value

holders private and give them anonymity and and that's how we're planning on doing and on on achieving privacy