Vesselin Velichkov, Open Zeppelin: ZK Proofs for Blockchain Applications: an Auditor's Perspective

[Music] thanks uh thanks for this introduction and thanks everyone for being here especially after the lunch break I know it's challenging I hope to get uh your attention so I'll be talking about let me first check the pointer okay it works I'll be going to talk about um zero knowledge proofs and their applications to blockchain and I specifically Focus on on security risks um and talk a bit about um auditing experience first a few words about open Zeppelin so it's founded in 2015 it's a world leader in securing blockchain smart contracts um and it's famous for its open source contract libraries for its de Defender develop development platform uh and also for uh securing many um high-profile projects such as coinbase ethereum Foundation compound and many others and I am part of the zkp practice and we specialize on reviewing and auditing zkp components so cryptography components and zkp specifically uh We've performed successful audits on plun prover and verifier on plun verifier and uh on the latest release of the uh open zeppel in contracts Library I briefly give a bit of motivation why zkp in blockchain um and I I will introduce the main concept of of zero knowledge proofs then I give some applications of blockchain you you've heard about them already in previous talks um and then I will focus a bit on vulnerabilities and I will highlight some vulnerabilities found in audits so blockchain as useful as it is it has some limitations specifically scalability and privacy and because of its limited transaction throughput um we we we observe High transaction fees uh as the transaction demand increases and then on the Privacy side we all know it's a transparent immutable Ledger which is good it's a feature but at the same time uh it gives it presents privacy issues because transactions can be can be traced since the information is publicly available and zero knowledge proofs can help alleviate those two limitations and more than that so informally what's a zero knowledge proof in fact zero knowledge proofs as a concept in cryptography they are a very old concept so their initial proposal dates from the 80s in this seminal paper from 85 and since then the area has been very active and we've seen a lot of research papers from this from these years but only recently they have achieved widespread adoption and practical applications um to a large extent because of uh of of blockchain and informally it's a protocol in which a prover proves to a verifier knowledge of some fact without revealing any information about the fact except that it it exists except that it exists so what what kind of facts what what kind of uh uh statements can we prove broadly speaking we can prove any computational relation that can be verified efficiently in polinomial time um you can think of and for example aover can prove knowledge of uh of a pre image of a hash without revealing the pre image so only the hash is given and then the prover convinces the verifier that he knows the a valid prage for it or for example he can prove knowledge of a discrete logarithm of of a field element y or more closer to what we are all concerned here is in in a blockchain scenario with a zkp we can prove for example that um that the blockchain correctly transitions from the current uh state route of the chain to the new state route when I say State truth I mean in the context of merries um that reflect the the chain state so a bit more formally um it's a protocol where a approver convinces verifier that they know a witness W for a statement X that is a member of a language L and this language is composed of all witness statement pairs that corresponds to an NP relation R without revealing anything about W the witness W so the witness W is the secret part that is not revealed to the verifier and the statement is is known both to prove and verify and just to give an example to give you some some sense behind those those Concepts um like witness statement language and relation we use um an example of proof of knowledge of discrete logarithm so uh we the prover wants to convin the verifier that he knows the value X such that X is the discrete logarithm of the element y so essentially X and Y are related by this relation and in that in that setting the witness is X the statement is y so the witness is the secret value X the statement is y they are related by this relation and then the the the NP relation we're talking about is the set of all witness uh statement pair so basically all the X and y's and the language that we work over is um all the elements in the field that have a discrete logarithm okay enough of technical content so let's let's go back a bit to more practical uh scenarios maybe one one one more concept to introduce so we Define zero knowledge as protocols so this implies some kind of interaction so there are some messages exchanged by between provs and verifiers and indeed on the top left side you can see uh a high level description of a zkp protocol so an exchange of messages between prover and verifier and then approver sends a commitment so some value to to which he he commits in this in this example it's a polinomial then the verifier sends a challenge which is randomly drawn element from the field and finally the prover evaluates his polinomial on the challenge and provides a a proof in the form of this evaluation so it's a very high level description but but conveys the main idea behind zero knowledge proofs but the point of this slide is that zero knowledge proofs don't have to be interactive and that's where the the Fiat Shamir transform comes into place and it's a tool for turning an interactive protocol into non-interactive so on the right hand side you you can see an equivalent representation of a zkp protocol that is non- Interactive and the trick is the use of a hash function so instead of the verifier being forced to produce some random challenges and keep in mind that in real world protocols we will have many more challenges than just single one so there will be many rounds of the protocol so instead of generating this challenge uniformly at random the prover and the verifier will be Computing it using a hash function independently on both sides and this hash function will be hashing public parameters so anything that is public in the protocol like for example or the generator of the group or the modulus of the field plus all the messages that have been in exchanged before that so they they has all this public information and they produce a challenge C so the benefit is that c is still pseudo random and that's what we require in the protocol but at the same time it can be it can be computed independently of both on both sides and that's that's why interaction is removed so you can see the protocol is turned only into a single round in which basically the prover sends his proof which is verified independently by the verifier and that's the the the situation that we see in blockchain application so we just send the proof that is verified that's why the fiir transform is instrumental in those cases and as we will see later it's also the source of a lot of vulnerabilities a few words on uh on the fundamental properties of zkp so completeness soundness and zero knowledge completeness is about um the fact that if a statement is true then the verifier can be convinced of of its Val um of its validity with probability one now if it's a state if a statement is false that's about the soundness property then the Prov still has some negligible probability of convincing the verifier of the valid validity of the false proof so the trick is the word negligible so it's the probability is negligibly small so in practice we don't expect this to happen and finally zero knowledge um models the fact that um the statement um in the process of the proof we don't reval anything about the statement except the fact that it's true okay and finally we have the succinus property so technically it's not a fundamental property of zkp but in fact it's critical for the use of zkps in blockchain context so the Suess property states that the proof should be short and what do we mean by short we mean logarithmic in the size of the statement so in other words it is more efficient to just verify the proof rather than Computing the computation yourself and that's the iCal property because of which we are using zkps in in Layer Two For example for um for addressing scalability and we'll see how in a moment two examples on the two limitations of blockchain that are started with the scalability and privacy um so the first one is on scaling ethereum with with ZK proofs ZK rollups Layer Two ZK rollups the these are Layer Two Chains that are executing transactions offchain so instead of publishing all transactions on layer one and then executing and validating them by all the nodes what happens is on Layer Two we execute a list of transactions that are batched together in a compressed form but after they're executed they're modifying the Merle Tre of the chain in some form and as a result the the state root of this Merkle tree that that reflects the current state of the chain is modified so this is the route before the transactions have been executed and this is the route after after the transactions have been executed but on Layer Two so so far we have no validation we have no trust that transactions are valid so instead of executing all those transactions on L1 we are submitting a sucin zkp proof this py here that is sent on layer one and on layer one we're verifying this proof so just a bit of more details uh of what is happening here um here we give an example of the scroll Layer Two rollup and essentially it it this slide contains the same information in the previous the previous one but a bit more detail so this here is the merco patri Tre reflecting the current state of the L1 chain with its own current current root and then we have we have um transaction or a list of transactions that we want to execute now if you just focus on the upper side here we we have whatever happens on L1 so no zkp for the moment and what will happen is the transactions go into to the ethereum virtual machine they're executed by the executor who is um who is uh pushing popping on the stock and um and reading and writing on the memory so this is transient memory he also has access to some list of published smart contracts in the form of bite code and some memory storage um and um as a result the transactions are are executed on L1 okay so in this transaction or list of transactions are internally represented as bite code so as as this kind of an execution Trace now we introduce the zkp component so on layer one instead of evm we we have a ZK evm so this is an evm equivalent so I have o here because it implements o evm codes modulus s so we have degrees of equivalence but regardless the ZK evm can compute anything that the evm can and as an input it takes in the list of transactions that we want to execute on layer one the current state roote of the of the world State and it outputs a succed proof pi and this proof P proves two things one is that the execution tray is unique and it is valid valid meaning it follows the rules of the of the evm so correct op codes that achieve the correct um computations and um the second thing is that this executing this execution trays causes a valid transition to the new State Route so we will move from this state to a next state t t plus one illustrating an application on uh private transactions so um how do we address privacy with zkp now an A na if approach would be to um to use uh to to work with encrypted accounts but this turns out to be INF feasible in practice so A and B want to send a transaction in between each other then they have to encrypt their accounts and and decrypt them on each side so it requires a lot of interaction and it is not um not feasible and it's expensive so an example of a successful project that is using zkp for addressing privacy is attec Network so they privacy first ZK rollup on ethereum and their core idea is that instead of working with accounts and balances they're working with nodes and owners so nodes as in Bank nodes and then all the funds of the chain are represented by a huge set of nodes and every note has a label and this label is its owner so when you do a transaction it simply comes down to relabeling the corresponding nodes this makes the setting much simpler if we want to achieve zkp so in AE case they maintain all the all the nodes and they are owners in encrypted form in a merco tree and they have a second merco tree that keeps track of the destroyed nodes because because of the utxo model that they use or similar one you need also to keep track of what kind of nodes were were destroyed so to make the long story short with in within this setting you can prove statements in zkp that have the following for form so the merco 3M contains a node of value X that is owned by Y which does not have a nullifier in then meaning it does not have a corresponding node in the tree of destroy node so that's a valid node so we've seen how we can use zkps to address privacy and scalability and uh here I move to the second part of my talk which is about vulnerability so as useful as they may be thank you as useful as they may be uh zkps uh have introduced a whole new class of vulnerabilities and in the past years five or 10 even we've been slowly accumulating knowledge in different zkp vulnerabilities that appear in in in audits um and only recently in 2024 uh a paper was published that systematized all this knowledge by chalas by chasu at all it systematized systematized all this knowledge and broke down all different vulnerabilities that we have seen so far into classes and into K kind of properties that it is breaking so in particular they analyze 141 uh zkp vulnerabilities that are publicly available they broke them down in classes and here is a very brief summary so in terms of the core properties of zkp that they're breaking so we can break soundness by booking the circuits specifically under constraint circuits and arithmetic field errors we can break soundness in um improper Fiat Shamir application or into the back end more generally where you implement the improver the verifier or the setup and for completeness you can still have books in the circuit um handling the point and infinity we'll see in a moment um and back end as well and for for zero knowledge blinding is a common error you can you can do blinding wrongly we can see again in a moment and then processing private inputs as public data one thing want to say while on this slide breaking soundness is the most critical vulnerability that you have so breaking soundness allows you to forge proofs and steal funds from the net n work so this is by far the the most serious the most serious um book that one may have in his implementations completeness and zero knowledge can be bad but not as bad okay so highlighting very quickly three vulnerabilities found in our audits that break each of those three properties so one vulnerability is a break on soundness um that we found uh while auditing the linear plun verifier so what you see here is the vulnerable part of the code and more specific Al this is the third uh this is the last round of the plong verifier in which the verifier is generating a challenge if you remember the Fiat Shamir in the in the beginning of my talk the verifier is generating challenges that are supposed to be pseudo random by following the Fiat Shamir transform now in this particular case the developers did not include all the public information into the Fiat Shamir transform they figured since this is the last challenge it's sufficient for it to be pseudo random but we don't have to necessarily include all the previous messages in into its pre image that saved them a bit of efficiency but it turn out um it caused a serious attack so I won't discuss too much this slide but it all comes down to essentially being able to freely modify some elements of the proof um thank you some elements of the proof without modifying The Challenge and as a result you end up with a simple system of two line linear equations in two unknowns which you solve for x and y you replace X and Y in forged proof and this forged proof will be accepted as valid and what are the implications well on Layer Two an attacker makes a false transaction that transfers all the user funds into an attacker controlled account he builds the bur merco tree he constructs his new merco route he he um makes his forted proof p p Prime Pi Prime that will cause correct transition from this route to the old one and because of the bug this false proof will be accepted on layer one and then the chain correctly transitions to this new state in which all the funds are into the attacker account okay very quickly back on um breaking completeness it's um we've seen so this is not from one particular audit but we've we've seen it at different places um how do you handle the point at Infinity on an elliptic curve so it's a point that has coordinate 0 0 and it's the only valid point on the curve that does not satisfy the curve equation and many implementations just choose to ignore this point so if you get a commitment equal to the point of infinity you just ignore it that's fine but if you have a polinomial that has a commitment that has roots in the secret parameter s of the SRS then its valid commitment will be the point at infinity and you will be ignoring this point so as a result you break you break completeness so valid proofs will be rejected um and finally a bck on uh on uh zero knowledge so a certain implementation specifically linear plon prover implementation did not properly blind their polinomial so you are seeing here the third round of the plun prover in which um at some point you are Computing well not at some point but that's the main goal of the third round you're Computing this large quotient polinomial and it's broken into three sub pooms which you're supposed to Blind so what does it mean blinding it means adding those random factors to to the original polinomial so this Row one row two and so on adding blinding is the idea is to prevent leaking of witness data by publishing commitments to those polinomial and in this implementation this blinding was was not done so the polinomial were just published as as is okay and as a result it directly makes applicable an attack recently proposed by seanic that actually addresses exactly this case so it breaks statistical zero knowledge um in zero knowledge proofs that's my final slide um I want to end up with some some wrap up um so the main message is that um ZK zkp auditing is a challenging field now it's it's it's uh fast moving we seen new new Pro new protocols being proposed every week every month if not every week um and we don't have an established checklist so at this stage in time it's very different than smart contract auditing for example where we have established checklist of books we we want to track many of those can be automated um and so on uh we don't have that yet for zero knowledge um often it auditing requires specialized knowledge in cryptography so the bar to enter can be can be high not always if you audit circuits it might be a bit easier uh and then we have also limited tooling so we don't have the comfort of uh uh of fuzzers and automated book trackers although we have some tools but not many um so finally for guidelines if you are a zkp auditor um pay special attention to custom modification of a protocol so you will be auditing a protocol that follows some paper um if you see a component that is modified from the paper now that's a red flag be careful to to audit this carefully um also be cautious with recently proposed schemes it's an abundance of them as I said new papers are being proposed every month um if you are an implementer follow the paper so make sure you're using the latest version and uh maintain detailed detailed specifications as you do the implementation uh read audit reports there are many reputable auditing companies that do excellent work and they publish their reports So reading them is very informative uh and finally consult a cryptographer or an auditing company if you're building a complex project that has CR critical zkp components so thank you very much [Music] I