ZK7: Structuring Computation for Privacy-Preserving Apps - Wei Dai - Bain Capital Crypto

Transcript

So, hi. I'm Wei Dai from Ben Ben Capital Crypto. And today, I'm going to be talking to you about why zero knowledge is not a full solution to privacy-preserving applications. I'm going to tell you, uh, you know, the the reason why and and the solutions going forward, right? So, first first of all, since I'm like the first talk uh one of the first talks here, raise your hand if you have prior knowledge of zero knowledge, you're familiar with zero knowledge. Should see every most Okay. Okay. So, so I can uh since almost everyone raised their hands, I'll just speed through the slides. Uh what is a zero knowledge proof? Well, it's pro it's a way for a prover to convince a verifier about about a statement succinctly, right? So, the prover here, uh uh prover verifier would take in some common input uh circuit C, and

um uh the prover will prove produce a proof to a verifier that is short uh that verifier can uh can can verify in, you know, in time that is independent of of the circuit C, right? So, uh and and so typical provers are, you know, mobile uh clients, right? And and typical verifiers are like chain applications like EVM uh contracts. And, you know, there's certain properties we want such as succinctness and non-interactivity, which I've shown in this diagram here, right? And there's other uh properties such as uh transparency uh transparency and universality, which means that uh you can't change uh the circuit without having to run additional trusted setup, right? And there's additional security properties such as completeness uh uh zero knowledge and notice soundness,

which I will not uh go into detail here. And, of course, uh we've seen an explosion of of works uh you know, along along these lines because of, you know, academic works uh that advance the state of the art as well as industry efforts, right? And second question. Do you think that zero knowledge will solve all our privacy problems, uh you know, for blockchain applications? Raise your hand if you think yes. Okay, good. Okay. All right. All right. So, all right. So, all right. Uh of course, uh you know, uh answer is no and I think it requires a careful reasoning right on why zero knowledge is is not the single solution to our private problems.

And so here is you know the of the talk. So so first we'll we'll actually go through the reasoning on why zero knowledge you know is actually in contention with on chain composability and on chain share share state, right? And we'll see actually you don't need to use zero knowledge for the for the full state transition and you can structure your application so that you use transparent computation for your on chain part, right? You know, while sacrificing privacy for that portion. And then for the second part we're going to talk talking about how FHE can actually help with the part that ZK does not do, which is confidentiality for on chain state, okay?

And at the end I'm going to show you a kind of a way forward maybe in like you know five three to five years what we can have if we can program computation between zero knowledge, trans you know, transparent computation and FHE. Okay, so let's get started. So first you know, what is a computation? So in this talk a computation is just going to be a state machine, right? So it it's keeps some states and you will you will taking inputs and you will update the state, right? And you know, typical the state machines are you know, blockchains are state machines. Here a block is a input, right? And and the blockchain is essentially the chain of states.

Right. And or actually each smart contract application can be seen as a state machine, right? So each call to the smart contract is an input and responding to the input the smart contract will update its states. So state machine is really just you know, a nice abstraction for most applications that that we know of that keep states. So how would you do you know, privacy for state machines generally? Well, you could do zero knowledge updates to state machines, right? And so this is actually what is done you know with Zexe, you know in the company like Aleo and Mina where uh update to state machine it's it's done via zero knowledge where the zero knowledge proof will um will say I have some states uh starting states and have some ending states and

have an input that actually made the state machine go from the starting state to the ending state, right? Uh and and then this entire package of state update is then submitted to chain and the chain will verify the proof and then uh modify the state. So uh you know this is okay but you know what's the problem with this? The problem is of course that there's you know race conditions that uh arise when you do such a state transition because your state uh your state update proof ties to your previous starting state. So therefore if two users try to update the same state at the same time uh one of one of the updates will not get through, right? And so uh so this is really the problem with uh you know doing general state transitions in zero knowledge.

And uh and so because of this uh you know applications if you want to do the entire state transition in zero knowledge, what happens is that your full zero knowledge application essentially have a server that sits off-chain that process that sequences transactions. So this is you know almost like a roll-up, right? Uh and so um you know the trade-offs are yes you gain scalability and uh but you actually do not gain that much privacy uh because because the zero knowledge provers um you know on on the side actually needs to know the information, needs to know the secret witnesses uh you know to produce the proofs. And um you know and you actually completely lose on-chain composability, right? Compared to the uh transparent counterparts which we know a lot on Ethereum where you get uh com- composability by default where smart contracts uh expose their

interfaces to each other. So um uh but actually you don't need to use zero knowledge for the full state transition, right? So for instance on on the on the right side here we have you know zero knowledge for the full state transition where the entire state update is computed off-chain. On the left here you can actually use your knowledge for something like a range check where you do not actually um you know, touch the state inside the zero knowledge proof. So, therefore, the proof is never invalidated uh when the state is updated, right? And in the middle here is actually applications where um your your state can be updated, but uh and your proofs actually touch the state.

But when the state is updated, your proof is not invalidated, right? And so, this is, you know, for instance, like Zcash. Actually, you know, if you uh because of the uh insertion-only Merkle tree, uh if you say that I have a note in a Merkle tree, even if the Merkle tree is updated, meaning there's new notes coming in, your your proof is still valid because uh you know, old old trees, you know, no or leaves are never deleted in such application. And so, if you if you actually construct your state carefully, you can actually gain uh you know, essentially uh concurrency with, you know, zero knowledge proof type of type of updates.

And I will say that um actually uh this this type of structure can be made uh composable on-chain. Uh and you can you actually build anonymity uh well, applications with anonymity while sacrificing privacy. Um I won't go into details here. Uh so, for instance, as I connect is is you know, actually uh achieves uh such a property uh using zero knowledge circuits. And so, now let's actually move on to the to the second part of the talk, which I think is the most interesting, which is how do we actually use uh other techniques to uh complement zero knowledge, right? Um And so, uh if you look at, you know, the two type of computations we have that we can program right now, you know, transparent on-chain and zero knowledge off-chain, um you know, they each have their trade-offs. And the question is, can we

have private input, right, to confidential on-chain computation? And the answer is uh is actually yes, you know, we can we can actually do this uh if you do MPC or FPG on-chain, right? And with essentially security um that's uh similar to the the you know, majority assumption of of uh consensus protocols. And and the way we do this is you know, in this talk we're going to be focusing on fully homomorphic encryption, right? And so let's briefly go through you know, what FHE is. And and really briefly it's really just a way for for you to do computation over data that is actually encrypted, okay?

And so we'll have a public key which is out to the public that everyone will know and a decryption key which it should be kept hidden, right? And with the public key you're able to encrypt messages. So here each M is going to be you know, a single bit. And for any circuit that actually computes over these plaintext bits, you're able to evaluate that circuit on ciphertext. So here I'm writing a brackets to mean that something's a ciphertext and the highest underlying message, right? And so with FHE you're you're able to do computation over ciphertext.

And later on when you decrypt, you actually get back the you know, the circuit output, right? And so inside the form your uh the computation it's you know, done in a in this confidential confidential manner. Um And so it has been you know, a very active area of research for you know, more than a decade and efficiency of FHE schemes has been improving you know, over over the past past years. And the kind of current state of the arts libraries can support about you know, couple of thousands binary FHE operations per second.

Um and so uh but here you know, there's still a problem, right? Because if you hold the decryption key then you can see the data, right? And there's a single point of failure. So whoever holds the decryption key gets to see all the data that's encrypted ever to the public key. So how do we fix that? Well, the solution is threshold cryptography, right? And so with threshold cryptography, you want to share the authority with a secret among a group of servers so that if K of of them you know usually I say 2/3 cooperate then you get essentially all the liveness guarantees.

But you know as long as no more than K minus one of them collude then you get essentially security. Okay. And so these are um really useful for for blockchains. When you set the threshold to be around you know 2/3. And and indeed in recent years there's been numerous works using threshold cryptography in different settings. In particular you know for for light clients in the case of threshold signatures and for front running protection um and also you know private trading in in in the case of threshold encryption.

And it turns out that people have actually studied threshold FHE. So there exists threshold FHE schemes. Actually no. Um Getting ahead of myself here. So there's a canonical way of doing threshold cryptography which is called Shamir secret sharing. And and there's many many different techniques that's proposed in recent years which we'll now get into detail to that actually manage these Shamir secret keys among a dynamic group of validators. So this means that servers can come in and out of the consensus set and you can re-share the secrets among this group of servers.

And it turns out that we actually know how to do threshold cryptography and FHE together. And this means that for the decryption key we will secret share it among a group of servers. And you know have this threshold guarantee on you know liveness and security right. And and there's actually only a single work outlining how how this will work. So so yeah if you are FHE researcher out there I encourage you to you know think more about threshold FHE. There's there's not just not enough work on improving you know threshold FHE at the moment.

And we um you know if if you buy the the idea of my talk then we really really need threshold FHE for blockchains. Um and so so why do we want to actually decrypt, uh you know, during consensus? Well, you as you will see uh in the later slides that applications actually need to communicate between the confidential parts and the public parts, right? We need some form of information release to actually make our applications work. And I now will show you why. And so uh before we, you know, jump into uh applications, so you know, what are we actually doing here? So we talked about FHE and threshold FHE, uh you know, but we're, you know, we want to do blockchains, right? So what are blockchains? Blockchains are state machines replicated uh in consensus,

right? And so it turns out actually if you want to do threshold decryption uh in consensus, there's some um you know, um subtleties in that you actually have to change your consensus mechanism to also include decryption. And you want to guarantee that uh decryption happens if and only if a block is finalized. So uh you know, I won't go into details here, but uh just, you know, take my word for it that there's ways to essentially take any uh you know, Byzantine fault tolerance uh consensus protocols and have it support threshold decryption. Um so so that this property will hold. And so uh so for the rest of the talk, we'll we'll assume that we'll have uh a consensus mechanism that replicates a state machine which supports threshold decryption for for FHE schemes, okay?

And we'll fix some uh single public key that's essentially uh the chain public key, right? For for the for for the for for our chain. And now so our question is uh you know, how do we actually program the state machine, right? We have we have a state machine, but you know, how do we actually like build useful applications? And the second question is, you know, why is this any any useful? FHE is slow, you know, zero-knowledge are already slow by itself, uh you know, what does this actually buy us, right? Uh and so that's hopefully what will convince you of uh that we can actually build uh you know, maximal privacy-preserving applications with this if this is possible.

Um and so um so let's take a look at the landscape of three types of computations, right? So for transparent on-chain, uh you know, we'll have like, you know, EVM and WASM-based solutions, you know, with different frameworks to program them. And for uh zero-knowledge off-chain, you know, there's a lot more libraries that you use, but you know, there's different proof systems and you know, different libraries. And for FHE, actually, uh if you want to do threshold FHE, there's actually no existing library to do it. Um but in this talk, uh I'm going to abstract away over all of that and just say, "Okay, we're going to uh essentially write pseudocode, okay?

Uh I'm going to demonstrate to you that uh if you're if you if we do have a framework to program all these, you know, different computations nicely, then we can build application in a very, very expressive manner, okay? And uh it's going to be code named Pasca, meaning uh it's a privacy-enhancing smart contract architecture, okay? Uh and so uh and so so what what what does it look like? It will look like just any other smart contract, but the computation is going to uh essentially, you know, marks uh you know, with with for for for different parts of the computation, right? So we'll have the standard on-chain transparent computation, which is essentially replicated and executed on-chain, right? And we'll have uh you know, user user uh computation, which is actually computed off-chain, right? So it encapsulates

what the users uh will compute. And we'll have zero-knowledge circuits, which encodes the off off-chain proving parts and on-chain verification parts, as well as the FHE circuits, which which are going to be uh computed confidentially on-chain, right? And so uh how it how will actually build applications? Well, we're still going to use zero-knowledge circuits. In particular, you know, the Zcash-like zero-knowledge circuits to actually keep our token accounting, right? But instead of uh just doing everything in zero-knowledge, we'll have an interface with FHE circuits, meaning we'll actually uh encode the values Oops.

The values that uh the uh zero-knowledge circuits uh essentially uh prove to uh as input to this uh I V G circuit. And we'll do the I V G computation and uh threshold decrypt some crucial output bits, right? Which we'll then use in the transparent computation to uh do further processing, right? So, application logic really happens uh on chain in the I V G circuit and the transparent parts. Okay. So, so this might sound vague right now, but uh hopefully, you know, it will clear up once I show the later slides.

Uh and so, the idea is uh you know, for general circuits, we're going to use Zcash in this particular case, we're going to use the, you know, the most recent edition of Zcash called Orchard and change the value commitment to be a value encryption that's under the threshold uh I V G public key. Okay. So, we're going to keep a Merkle tree and a nullifier set. So, if you're familiar with Zcash, this is exactly how how Zcash work. And uh the circuit will make the following modification. So, it will say that, you know, the circuit will say that I have some net value change that uh you know, I have spent some notes and created some notes, and I have I have encrypted this net value change uh against this threshold uh I V G key, right? And and and encoded in some transaction.dot.encryptedvalue,

right? And um And on the processing part, uh you know, we simply verify that the knowledge proof is constructed correctly and you know, do some additional processing, right? So, this process will actually is actually does not balance itself. So, so like, you know, there's a net value change that's not accounted for. But but we'll essentially balance out the the encrypted value inside I V G circuit. Um and you know, of course, there's a way to generate uh these transactions. And and so, so this uh this type of contract will allow us to have a Zcash type um you know, shielded token pool to interact with the I V G uh uh circuit-based application.

So, so really quickly, uh you know, what is the first application that that we could build? Well, one of the one example is, you know, constant function market makers, right? And and so these are like really simple markets which match uh you know, buyers and sellers to liquidity providers, right? And it's a mechanism that's uh essentially a very very simple. It only keeps track of two numbers, which is the reserve of amounts in, you know, the asset A and asset B, right? Of the liquidity pool. And there's some trading function that's uh actually very simple. In In this case, you know, in this case of Uniswap, it's actually just uh the product of A and B.

And so uh what do we mean by privacy in this case? In this case, uh we actually want to hide uh mostly all the information, right? So, both the uh the the the trader identity and the amounts that, you know, we would like to hide, right? So, it's actually very very hard to hide the trade amounts because it actually reveals uh you know, what's uh so so if you reveal the the spot price, it actually reveals what your trade amount is. So, so therefore, we, you know, we we would like to actually release the spot price programmatically to to hide um the the trading price essentially in the arbitrary long.

And so uh so let's look at how how to actually build this. So, we're going to use the previous contract we have shown, which is, you know, essentially a modification of Zcash. And we're going to keep uh average heat state, which will encode these two two numbers encoding your state, right? And here is the average heat circuit. It's It's really really simple. It just simply computes the uh CFMM trading function, which is just a multiplication and comparison, and setting up a bit. So, this upper bit is zero one or zero will denote whether the trade have gone through or not, right? So, it simply test checks the, you know, validity check, and either update the state and outputs one, or it does not update the state and outputs zero.

Okay? Uh and so how do we interface with this? So, we'll have some additional transparent computation that will interface uh with this average heat circuit. You will first process uh the funding transaction, right? So the funding transaction is you know, you want to swap some some Ethereum to USDC. You'll actually spend your Ethereum first regardless of whether your trade is valid or not. And the user will actually construct both a refund transaction, right? That refunds the the the you know, the the Ethereum and you will construct also a payout transaction which actually pays out the USDC. And inside the FG circuit you will actually compute whether your trade is valid or not, right? And depending on whether it's valid or not, you will actually construct a refund or or the output.

Okay, so it seems that I might be a bit short on time. So it actually turns out there's actually subtleties when you want to do this with you know, FG states. There's actually attacks where an attacker can take a FG state and copy it to a an attacker contract and attempt to decrypt everything, right? So you need to like going to prevent these type of attacks and there's ways to mitigate this by essentially saying that every single FG state and FG input must be accompanied by a zero knowledge proof of knowledge that the user actually knows what the state is that's tied to each contract okay? So you know, there's ways to do this essentially with zero knowledge proof, right? And so and the last I'll mention is auctions, right? So we know what auctions are. So I'll just quickly mention what we mean

by by privacy in this case is that we want to run an auction where bids are not revealed to anyone even after the auction is over, right? And this is traditionally not really thought about and it's actually really really useful for multi-round auctions if your bids are hidden for later rounds. And again, there's a way to do this and the trading function is really really simple where you just compare the the bids to the max bid and either update it or not, okay? And so with that I think I'll just conclude since I'm short on time. And the paper on on Pasca will will appear soon. And uh And we're hiring.

If you're interested uh, in any of these topics, working on zero knowledge, FHE, threshold cryptography, uh, come contact me. THANK YOU. PERFECT. SO, THERE'S TIME FOR FIVE five minutes for Q&A before, uh, we take the first break. Yeah. Yeah, two quick questions. In the opening you mentioned one that, you know, you need to consider this to prevent trace conditions, right?

Did I get that right? Yeah. Um, what if like if you do a decentralized sequencing scheme, right? Does that mitigate the concerns there? Yeah. Uh, yes. So, like, you know, if you were at the last talk, like, you know, what Protura was saying is that you can have essentially pool results on MPC, right? So, along those same lines, yes, you can decentralize the sequencer, but you know, it it's morally speaking, is that aren't you just building a chain at that point, right? So, if you really think what those sequencers are doing, they're coordinating among themselves, you know, maybe using, uh, MPC or threshold techniques to to essentially hold out the secret information, right?

So, it's it's it's actually along the same similar lines where your sequencer becomes a chain, uh, I think, you know, if you really spell out the details and have it support general applications. Yeah, okay. Well, I mean, that's how we're approaching it in Mina, so that's why I was curious. And then, secondly um you mentioned, you know, like, with just with the current ZK like Zexe like schemes, uh, that you can't get in like good privacy for these applications, right? Are you suggesting that only for like AMM type stuff that require constant on-state change? Or do you also propose that you can't like any other type of application which, you know, you or data verification or stuff like that?

Are you also saying that, you know, you that that's not going to work as well? No, I only only for application What was the question? Uh, yeah, so the question was, um, you know, is ZKPs bad for privacy only for shared state applications or for applications, you know, uh, like, you know, for data verification and stuff like that? So, uh, the the point is really that for these applications that require shared states, like, you know, on-chain AMMs and you know, auctions where you have you're you're keeping track of like, you know, comparison of different bids. So, whenever you need to compare users' inputs, right? Like, meaning you need to compute over shared inputs or have a shared state where user will access and read and write, then it's really hard for ZKPs to provide privacy in that context. But, when you have private states that's particular to a user, then

I believe, you know, ZKPs suffice in in that case. So, for instance, you know, if you have tokens that's held by one person, right? Like, in the case of Zcash, then zero-knowledge works perfectly right? Thanks. Yeah. Great nice talk. Thanks. Uh just two questions. First is about the private AMM part, right? Uh so, let me try to uh for like better words, synthesize attack. Um let's say I'm a trader itself. I just like put a small small amount per block, just kind of probing correctly Um I assume this is kind of like a permissionless system.

Yeah. So, in that case, like, how much information leakage uh I can get by just like constantly sending this kind of probing transactions under this uh uh like uh AMM over FHE scheme. Um I believe uh you know, it depends on how you design it, right? So, yeah, it is definitely possible that if you send a transaction, if it goes through, you know, you know, the price is above, you know, or maybe below certain threshold. And if it does not, then uh uh you know, you know, you know, essentially you gain the a binary information of the state, right? Um and so, uh the it actually turns out for these AMMs, you actually want to release the state periodically because, you know, you want user to be able to trade. So, if you have no idea what the spot price is, you

cannot trade. So, I think uh so, this I think more along the question of like mechanism design. You want to release price soon enough so that users can actually trade against it, but uh not too soon to lose privacy, but also soon enough so that people don't probe their probe the spot price themselves. Right. I think I think agree but it's actually binary part right? It's actually not binary information. You actually get the like pool size if you have a probing query and depending on the I feel like there is kind of balance of like because it's permissionless system I mean presumably you need to pay more right? Because you need to trade itself to do this kind of a probing query. Right but I think still I I just find it's kind of hard to like quantify the information leakage

you can get from this kind of probing queries. Right so the question is you know what exactly is the probing query leakage for the information you gain. In this case for the construction I've shown here for actual trade it's actually binary information. It's either it went through or not right? So when you construct the trade you need to actually construct exact trading price you're you're you're asking. And so if the spot price is below that you'll get executed. If it's not then you will not. It's just pretty good with this construction. There's no there's no slippage in this construction I'm showing here. And it turns out it's actually really hard to build flexible slippage price because you will need to compute essentially encryption inside FHE circuits which is a lot more efficient. So in these two

constructions I've tried to keep the FHE circuit extremely small. Um sorry. Quick quick second question. Is there a way that we can using not full FHE just like some homomorphic crypto primitives to get a relatively kind of like a performance burden on this data? Yeah yeah so I think so you can actually net all trades with just you know partially homomorphic encryption by simply aggregating trades. And this what Penumbra does for instance. And I think I'm out of time so we'll now conclude.

Thanks. Thanks Wei.