Keccacheck: solving the Keccak bottleneck in zk SNARKs

Transcript

[applause] >> I do realize my talk is slightly more technical than everything else you've heard today. I'm really sorry for the scary looking title, but I promise it's all going to make sense by the end of this talk. So, before we start, raise of hands, how many of you already work or work with zero knowledge circles circuits at all? Perfect. And how many of you knew what a catch-up function was before Vitalik explained it? Perfect. Okay, cool. I promise everything's going to be clear by the end of it.

So, you may have heard that zero knowledge cryptography is the future of Ethereum and blockchain scaling, but maybe the details are a little fuzzy. What does it mean exactly? In this talk, I'm going to focus on three aspects of it. One is increasing transaction volume, and this is something that Yi from Axiom was speaking about on Monday. Currently, all of the Ethereum nodes, all of the um all of the validators, they need to re-execute transactions to make sure they were done according to Ethereum rules. And this puts a limit on how much stuff we can put into those transactions.

Um think about payment operators, this puts a limit on how many payments uh they can process within the 12-second window. So, the idea with ZKPs here is that if we can instead move on to the world where the validator, the Ethereum node is only able only needs to verify a transaction, it doesn't have to re-execute it from scratch, then we can increase increase the throughput of the entire network. Another aspect of growing Ethereum, of growing our ecosystem, is bringing more institutionalized uh customers onto chain and making sure uh, they can operate in a way that's uh, regulatory safe. And in order to do that, we need KYC.

But if you're anything like me, you're not going to upload your passport data to a public blockchain. That would be uh, silly. Uh, but you can you're probably perfectly fine with attesting that, you know, you're not from a sanctioned country. Uh, that maybe you're an accredited investor. Um, and like just uploading a little proof that doesn't reveal all of your personal details onto the public chain. Uh, so this aspect of ZK can sort of increase the number of counterparties you can interact with on the chain. And then as the transaction volume grows, as the number of counterparty counter parties grow, um, the stakes also grow higher and higher.

So we might want to introduce some sort of credit scoring or risk scoring um, to be able to make sure that counterparties we're we're interacting with they're good for the money. Maybe they don't want to reveal all of their positions, all of their strategies, but still sort of convince us that they have funds somewhere uh, should something go wrong. So we can use ZKPs, zero knowledge proofs, for all of those aspects of scaling our ecosystem. However, um, there's a little roadblock in all of that, uh, and its name is a Keccak.

So Keccak is the hash function used by Ethereum and all of the EVM-based blockchains. Uh, it's used to commit to the state of the blockchain at any given uh, point in time. So you may recognize these weird transaction hashes on block explorers. Um, this is essentially a guarantee that everything under that hash stays immutable. So all of the account balances for that hash are already fixed, and users cannot cheat and modify them later. And Keccak is great because it's really fast on the CPU. And if you have a network node, like an Ethereum node, um, it needs to be executed as many transactions as possible. So, you want to have this commitment be really really fast on your CPU so that you can fit

more transactions inside a a single 12-second block. Unfortunately for us, Keccak is extremely difficult to prove inside zero-knowledge circuits. It causes tons of overhead. But, it's also already kind of too late for us to move on and replace it with something else. Like, it already exists. We've already processed hundreds of thousands, if not millions of blocks. So, we're not going to move off of it anyways anytime soon. So, what our team set out to do was how can we make Keccak proving better inside of zero-knowledge circuits? How we can make it better for all of the use cases that I've mentioned? And the key insight here is that we almost never want to prove a single

Keccak hash. It doesn't really make sense for anyone. Instead, we're always going to be dealing with hundreds, if not thousands, of them. I don't think even sort of fact that we're trying to prove. And spoiler alert, we could we were able to leverage that fact. Leverage the fact that we're dealing with tons of hashes at once, and provide results that are much better than the current state of the art. Before I describe how it works, let me sort of convince you even further that we're always dealing with a large number of instances.

So, let's take the simplest example of scaling transaction volume and sort of moving from nodes and validators executing all of the transactions to nodes and validators just verifying simple proof, verifying small proofs. But, what it means is that somebody else outside of blockchain had to produce those proofs in the first place. And in order to produce those proofs, they need to they need to execute and prove everything that happens in your smart contracts. And even if you don't see it in your solidity source source code, you are interacting with Keccak all the time. If you want to update an account balance, you use Keccak to sort of calculate where that balance is stored. So, this would be one example. If you call a

function, you calculate the Keccak. So, there is hundreds and hundreds of them inside every smart contract transaction. Um and in fact, modern ZK-EVMs spend probably about 40% of the time just proving those Keccak hashes that you don't even see. Another example, uh the risk scoring {slash} credit scoring Um we might want to do is prove some properties of your wallet. So, for example, prove that you have $5 somewhere. You maybe don't want to reveal where exactly. It doesn't really matter. Um but what you can do is you can convince your counterparty that you have those $5 somewhere. Um and in order to do that, you need to inside a zero-knowledge proof, you have to sort of establish a link uh of trust

from the block hash through the root of the state of the entire blockchain, through your account, uh all the way to the storage slot uh where your account balance is stored. Uh so, you sort of take a path from uh your account balance to block hash. Uh and in doing so, you can you already have to calculate dozens of Keccak hashes. And for any sort of reasonable credit scoring risk scoring, you may probably want to check those balances over time, or you may want to check more than a single path. So, again, we're moving into the land of hundreds of hashes at once.

And the third aspect that I touched on was doing ZK-KYC. And for this problem specifically, you maybe don't necessarily need to use Keccak, but I hope that the rest of this talk is going to convince you to look into Keccak again because of the improvements we've made. So, ZK-KYC is a bit different because we would typically have uh two separate components. There's the first one uh that would run like a STARK proof system, which is fairly fast to generate proofs, but those proofs are also fairly large. Um and they're too big to be digested by the smart contract. So, we cannot really work with that directly.

And so, what the ecosystem is usually doing is they wrap those proofs into another proof system called a SNARK, a succinct non-interactive argument of knowledge. It gives us all of the nice properties of being cheap to verify, being really tiny, um something that's perfect for working uh with blockchains. And that outer layer, the wrapper, uh what it needs to do is essentially validate the inner proof. Again, we sort of establish a chain of trust where if the smart contract accepts the SNARK, the outer proof, it means that we that the verification of the inner proof was done correctly, which in turn means that the original computation that we wanted to do was done correctly. For

example, checking your passport data against the sanction list or or something like that, or checking that you're a credited investor. And this outer layer, again, it needs to calculate thousands of hashes to be able to verify the inner layer. Uh and now with this ZK KYC problem, we have an interesting trade-off where folks can choose different hash functions. We're not directly tied to any specific one hash function, uh but based on what we choose, we're going to be uh very various uh trade-offs.

Uh so, currently a lot of folks use something like Poseidon, uh which is much more friendly uh to zero-knowledge circuits, but it's also much more expensive uh to calculate on CPU than Keccak. So, the sort of performance characteristic might look something like the chart on the left where you spend a lot of time in the Stark computing those ZK-friendly hashes, um so that your outer layer SNARK is quite a bit faster. Now, uh with the protocol we call Keccak, which is our contribution, we say that you can switch back to Keccak, which is about 10 times faster than Poseidon, for about five times improvement of the inner uh proof system

for only a little bit of overhead in the outer proof system. Um and so the hope is that if you structure this right, the overall performance goes up. So, how do we do this? Um our team started looking into a protocol called the GKR, uh which is a way of expressing your program >> Yeah. >> using polynomials. And what it promises is a single instance of the problem might not necessarily be be very fast, but GKR is going to scale much better than anything else. So, as you keep adding more and more of these uh problem instances, you're going to get more and more benefits from using GKR. So, it promises sublinear scaling.

And sort of the comparison I can get give here for a little bit of intuition is CPU versus GPU compute. Imagine you have your computer screen. It has about 8 million pixels. Um and GPUs are really well optimized towards pushing all of those pixels as quickly as possible by having literally thousands of cores on your GPU. Each one of those cores is not exactly powerful. It's, you know, fairly limited in in what it can do, but it's very, very efficient for dealing with pixel data and sort of the limited set of operations you can do on pixel data. On the other hand, CPU is sort of like super powerful, super fast core, but you have only a few of them and they can

only process one thing at a time. So, GKR is in this scenario is sort of like the GPU uh of the ZK proof industry. So, we did just that. We applied GKR to Keccak um see what happens and, you know, the thing worked, the thing scaled sublinearly. It's all great. However, the base version was really, really slow. And to continue my analogy of GPU versus CPU, it's as if you took a 10-year-old GPU and compared compared it to a modern day day CPU.

Like, yes, the sort of logic still applies, but the CPU is just so much faster. There's so much more raw power on it that even if it processes everything sequentially, it's going to be faster. Um so, GKR was not sufficient to sort of uh move the needle for us. So, what we then did next is we sort of took the original idea of GKR, which is let's lay all of the inputs to our hash functions as the first layer, and then instead of processing things hash by hash or like an instance by instance, we take all of our inputs at once and we apply the first operation inside Keccak on all of them at once.

Then we take those results and we apply second operation of Keccak on all of those instances at once. But rather than having like a generic purpose computer that can do anything, we really, really custom-made all of the operations inside to be as efficient as possible with Keccak and leveraging everything we could think of about Keccak hashes. So, our algorithm, you know, you cannot really apply it to other problems, but it's really, really efficient with Keccak itself. And the gain we were able to get, this is log scale, so maybe uh slightly difficult to to read, but compared to the state-of-the-art in our Keccak implementation, which is a popular uh framework that a lot of people who work in in ZK circles use,

we start breaking even at around 13 uh 16 to 32 uh Keccak instances. And again, like this is already a win cuz, you know, even a simple storage proof is going to be about that size. But by the time you have 200 or 500 instances, we're 10, 30 times faster um than Gnark. So, all of this is to say to show that despite all of the progress we've made all of over these years, there's still a lot of stuff that we can do to improve the efficiency, performance, cost of our zero-knowledge circuits if we apply um ZK talent to like specific problems.

Uh so, we can still improve a lot of protocols um by sort of searching for for those custom-made solutions um to make everything a little cheaper to run. Uh it can also be used to increase privacy because now we are able to do more and more things, for example, on mobile devices. One of the things we're working on is like accelerating mobile proving so that, for example, your password data never leaves your phone, and this way you don't have to trust anyone with your personal personal details.

Another thing we can apply this to is the ZK KYC process that I've mentioned. Uh if you're a big institution, you may want to integrate your existing data sources um with your smart contracts, with your new blockchain operations, and you may want to do it in a privacy-preserving ways where you don't need customer data, you don't need your strategy data, but you have some sort of um agent acting on your behalf on the blockchain that you can reference to to make sure that, you know, certain certain properties that you care about hold.

Um so, I'm Jagoš, I'm co-founder of Rail Labs. If this was in any way way interesting for you, you can say hi in this email address. And then, if you want to learn more about the protocol that we've built, we call it Katatsek. Uh you can scan the QR code that points to a blog post that gives you to more tech details on how these things works work. It also gives you a link to a white paper where you can read all the fancy math behind it, and it gives you access to a GitHub repo where you can already try it out. Thank you. >> [applause]