ZK14 - Client-side Validation in Private Payment Protocols - Ying Tong Lai ({ ideal })

Transcript

Thanks everyone for joining. Um, my name is YingTong. I work at Ideal Group with Liam and our co-founder Robin. And we are working on a private payment protocol based on client-side validation. So, what client-side validation means is that consensus does not validate your transactions and your state transitions for you. Instead, all this is done on the client-side. Um, all this is becomes the responsibility of the users, the senders and receivers of the protocol.

And if you're familiar with how Zcash works, the main difference between our protocol and Zcash is that uh, where Zcash posts uh, zero-knowledge proofs on chain, we do not. And we keep it client-side. So, that's the headline of this talk. And we're going to go through sort of the implications of what such a consensus change does, uh, implications in terms of the proof systems we need to use, and in terms of um, maybe UX issues, unsolved open problems, and so on.

So, our our original motivation was actually trying to introduce privacy to Bitcoin. And this is harder, a lot harder than you might expect. Um, this partially because of governance issues. So, it's very difficult to actually um, push through a consensus change in Bitcoin. Uh, either soft or hard fork. And for that reason, um, going for a meta-protocol is way more practical. So, what a meta-protocol means is that we simply inscribe data onto Bitcoin L1. We do not change the consensus. However, we use the L1 for data availability and canonicality. And

then off-chain, we uh execute this meta protocol that interprets this inscribed information according to our rules. So, when we're inscribing things onto Bitcoin L1, uh cost is of the essence cuz Bitcoin block space is expensive, and we want to leave as light a footprint as possible. And this is why we would like to take the proofs off-chain. So, unlike in Zcash, where we submit proofs that are generally larger than simple payment transactions, in this case, we want to keep that off-chain. Uh we don't want Bitcoin L1 to see this.

Um and so, a quick recap. I'm sure everyone here is familiar of how Zcash works. Um once we understand this, we can see very clearly how our protocol differs. So, Zcash works in the following way. Their on-chain state consists of firstly, a set of commitments to notes, and secondly, a set of nullifiers uh tracking the spent notes. So, uh how to do a transaction, a transfer in Zcash. First of all, I spend a note in the commitment set.

Secondly, I deterministically compute the corresponding nullifier of the spent note, and I append it to the nullifier set, um and consensus checks for me that it has not appeared before in the set. And this is the double-spend prevention guarantee that consensus gives us in Zcash. Um having done this, I can output a new note, commit to it in a blinding way, and append that commitment to the note commitment set. And the point here is that um it is not possible to link the old note commitment to the exposed nullifier or to the new note commitment. And this is what we

need the zero knowledge property for. Uh in particular, we need to conceal the index of the old note commitment. And that our anonymity set now becomes every single note in a note commitment set that has historically existed on Zcash. Um And the zero knowledge proofs that we're publishing onto Zcash uh achieve this, they allow us to um verifiably create a new note um by spending an old note, but without revealing what the old note was. Um And it is precisely these zero knowledge proofs that we would now want to move off chain. Uh we don't want consensus to see them at all. We're going to rely purely on a client-side

incentives uh to verify these proofs. So, yeah, the main the headliner the main difference with Zcash is that client-side validated protocols move proof verification off chain. So, the intuition why this is okay to do is the following. Um If you think about it, we really strictly only need consensus for global properties. So, in this case, the global property we're interested in is uniqueness, and in particular, the uniqueness of the nullifier. So, every

nullifier that is submitted on chain cannot have appeared before. And this is a property of uh it's a global property of every single nullifier we've ever seen. Um however, we do not need consensus to concern itself with the validity of state transitions. So, this can be checked locally. So, this is the main intuition here. So, how would we go about checking if a transaction is valid? How would we do this locally?

So, to check if a transaction is valid, it's a kind of recursive property in the sense that we need to check if the inputs to the transaction were valid. Uh but, now to check if these inputs were each valid, we need to check if each of them originated from some earlier valid transaction. And then to check these originating transactions, we need to check that their inputs are valid and so on. So, in in this way, um transaction validity can be checked in a recursive way, but it can be checked completely locally.

This business logic can be enforced fully locally uh without referencing um global properties. So the how um the these local checks interact with the global uniqueness checks is that um a valid transaction cannot be the result of a double spend. So, um basically, we are combining the nullifier uniqueness uh global property with uh local recursive validity checks.

So um I'm sure people here are familiar with recursive zero-knowledge proofs. They emerge here as a very natural solution to compress this history and this arbitrarily long recursive trace into O(1) size. And therefore, when you're doing a client-side validated transfer, you need only present the receiver with a constant-size proof um instead of this whole, uh, recursive trace. So, I will actually skip the recursive proof slide cuz I think this audience is familiar.

Um, but suffice to say that, um, at each step of, uh, the proof, we not only verify, um, that some business logic, for instance, transaction validity is satisfied, we also verify, uh, the validity of a previous instance of the proof. And so, this lets us, um, very efficiently, um, check transaction validity even though it's happening fully client-side.

And um so, if we get into more detail, um, this is, uh, a concept known as, um, PCD, proof-carrying data, whereby, uh, we can map out a flow of state transitions and programs and annotate each of them with a proof. And, uh, um, the output proof from one program is ingested into the next program recursively. And so, it's important to get familiar with this annotation as we go into, um, um, a more detailed flow, transaction flow.

So, all that was background, um, and setting up the motivation for client-side validated protocols. Um, now we're going to go into the end-to-end architecture and how what we are actually building. So, um, the first component, uh, of our architecture is going to be a bridge from the L1 into our meta protocol. And we don't need to get into detail here but on certain very restrictive L1s such as Bitcoin, this is

not an easy problem at all. And part of our solution is a trust reduced bridge that allows us to verify ZK-SNARKs like Groth16 proofs even on even just using Bitcoin script. So, the second part of our architecture is actually communicating between the L1 and the side system. So, in one direction, we need to inscribe or publish information onto the L1.

And so, as we mentioned before, we are using the L1 for this guarantee for canonicity and for data availability. So, as before, we need to publish our nullifiers and our state commitments onto Bitcoin L1. And here I've used a word tachygram. This will be familiar to anyone who's read about the Tachyon project. Um So, we use this term slightly different from the Tachyon folks.

Um But, we'll see later on specifically what a tachygram is. Basically, a nullifier and a commitment. So, that's the first direction. And in the other direction, the client-side protocol needs to be able to read this finalized state from Bitcoin L1. And the last part of our architecture is fully client-side. So, um these transaction validity proofs must be made fully client-side using recursive SNARKs.

And furthermore, um proofs of non-inclusion um must also be made client-side. So, over here, this is the link between uh the global property of uniqueness and the locally verifiable property of transaction validity. So, given um a set of all nullifiers published on Bitcoin L1, uh any client can make a non-inclusion proof of their nullifier. That's the intuition.

And this is also um similar to Tachyon's architecture, where they outsource this step to uh an oblivious thinking service that's just producing non-inclusion proofs of a given nullifier against a canonical state. So, the last part of my talk is going to run through step-by-step how this protocol works. I find this often is the most useful part of my talk. Um So, we see here um this division between on-chain state and client-side state.

And you're going to see that uh very little state goes on-chain. So, we begin with the on-chain ledger in >> [snorts] >> some sigma one. And the user's the client-side um account state is in some omega one. And uh following the convention of proof-carrying data, we can think of state omega one as being annotated with some proof of its validity omega one. pi.

And now Alice the owner of omega one receives a note. And this note is itself annotated with some validity proof. So a proof that it originated from a valid account state. And note that all of this is happening completely client side. So what Alice does is she adds the notes value to her balance and transitions to state omega two.

Um all this completely locally. And um to then produce a validity proof for omega two, she has to recursively ingest the omega one's proof as well as the new notes proofs. So all this should be pretty straightforward right now. This happens completely client side. So now Alice wants to finalize her state.

Which means she wants to nullify her old state and commit to a new state. So how this happens in our design is that she updates her ephemeral private key. So what previously she used priv key one, now she just updates it to another random private key priv key three. And now she is ready to nullify her old state and commit to her new state. How she does this is by publishing a so-called taggy gram. So when I say taggygram, I'm referring to this topple

of the old ephemeral public key, as well as the commitment to the new account state. Um So, in particular, Alice signs the new account state commitment with her old ephemeral private key. Um And in doing so, she reveals both the ephemeral the old ephemeral pub key, therefore nullifying the old account state, as well as the commitment to the new account state. So, the taggygram has this dual purpose of atomically nullifying the old account state and

committing to the new account state. And um this is authenticated using a signature of the new account state commitment uh over the new account state commitment using the old ephemeral private key. And so, yeah, I think we should stay with this slide a little longer. So, over here, uh what a double spend would look like is Alice signs two different commitments using the same uh private key.

Right? And so, we could detect that on chain because we're going to see pub key one uh a second time. And here is where we are relying on a Bitcoin L1 for canonicality for some kind of ordering. For example, we'll just keep the the pub key the first instance of the pub key one and reject the second. And so, um yeah, basically, the what we're inscribing to L1 is just taggygrams.

It's just these tuples of old ephemeral pub keys and new account state commitments. And this is enough to give us double spend detection properties, even though we didn't submit any proofs on chain. Um So, yeah, the chain validates the signature, and then it includes the taggygram into the new block, um sigma two.

So, now, um since Alice's taggygram has been included on chain, she's able to finalize, um her new state. And what this means is that she can make a proof of non-inclusion of her nullifier, uh or a proof of uniqueness of her nullifier of the old state, as well as a proof of inclusion, um of the commitment to her new state. And both of these were global properties. Um and Alice needed to um submit this taggygram to the L1 before she can make a proof

about it. Um So yeah in order to make the validity proof for her new account state, omega three, she ingests, once again, the old validity proof from omega two, as well as these, um uniqueness and inclusion proofs that we just mentioned. Um I have a quick question about Um how does this proof know that the taggygram was actually on chain?

Cuz I thought obviously you could create an attached ground that isn't on the off chain but it would still be valid signature. Um but you need to know that it's actually visible on the Bitcoin network. Yeah. Yeah. So um basically we need some kind of um Bitcoin light client. Uh yeah. So you can think of it Yeah. Basically uh on the client-side system you need a way um to recognize uh whether or not a state is canonical um Bitcoin L1. Yeah.

Yeah. Can we do the question at the end? So [snorts] um Yeah. And then finally uh Alice updates her local ledger state to this new sigma two. Um and basically this is um her tracking the latest um Bitcoin L1 state in which her account is uh included.

Um So this is a very detailed um overview of how a client-side validated private payments protocol would work. Um And we do have a few open questions. I think the biggest one would be um civil resistance. Um so in Zcash because uh each transaction uh is submitted with a validity proof on chain, uh it's hard to uh submit invalid transactions.

Uh whereas in this case, uh it's very easy to do so. Um and yeah, a closely related question is uh uh fee payments. So, I think civil resistance Without civil resistance, it's hard to have uh fee payments. So, I think this is all I had, and we can open it up for questions. Thank you. >> [applause] >> Thank you, Yingtong Ge. I guess we have questions. Maybe you want to start?

Yeah. Can you return this to a previous slide, if it's possible? Yeah, I want to ask who send tagigram on chain. Is it Alice who do it? Oh, yeah. Who submits the tagigram on chain? So, um basically, um the moment Alice wants to finalize her state, she will submit this tagigram on chain. Yes, so that means each time she make a transaction off chain on client side, everybody can understand what she make yeah, this kind of yeah, private transaction, because they can see it on chain, because she use your

public key, Bitcoin public key. >> Uh yeah. Um so, basically, these ephemeral pub keys that Alice is revealing on chain are completely random. So, from one account state to the next, there is no connection at all um between the pub keys that she reveals. Wait, wait. She use some kind of wallet on Bitcoin layer. Right, right. >> Yeah, to pay for fee. So, she need to use the same wallet for each of her transaction. Okay. Okay. Inside this transaction here is meta information with taggygram.

I see. I see. So, you're saying because Alice is using the same Bitcoin wallet to pay for for inscribing her taggygrams. Um All these pop keys all these ephemeral pop keys can be linked to the same Bitcoin wallet. Okay. >> Um yeah, I think that's a good point. Um So, I think what we need is more work on this relay relay layer between the client side system and the Bitcoin L1. Yeah. Yeah. Because in mean in current state everybody can understand here that it was Alice who

made this transaction and everybody can link it. Okay. Oh. Yeah. >> Yeah, we could also rely on some uh publisher service on a client site. So, Alice would use like a say tour or some anonymous network service. >> need to trust these services and everybody needs to trust >> to trust the that publisher to not censor her. That's right. Yeah. >> Yeah. Okay. I think you could use a bolt style You could use a bolt style protocol to um kind of make Alice anonymous to the publisher.

So, um uh kind of uh lightweight um private payments to the the service. >> Yeah, I think this is my thinking recently that like centralized services are okay if all its users are completely anonymous. So, you can say, "Okay, this publisher is centralized right?" This publisher could censor anyone. That's true. But, all the messages that this publisher is receiving look completely random. So, why would they censor one message over another?

That That's my thinking recently. Okay, we have one more here. I'm not convinced. >> [laughter] >> Um yeah, I was So, the note that Alice receives presumably has been like sent by someone, right? Yeah. >> Is that like My question is like how does Alice know that that person didn't produce like different notes from the same state? And hasn't yet finalized on chain, which like kind of cannot like writes canonically which note is the the true one?

Right. So, when Alice receives this note, um she receives along with it some proof of its validity. And in particular, uh some proof that it originated from a finalized account. Right but So, the note was created from a finalized account. >> Right. But, that doesn't mean the account with its balance reduced because of that note. Oh, uh-huh. has been finalized. So, in some sense, it's the same finalized account could make three different notes.

And then only afterwards one of these three will be the finalized one. I see. Uh it has to be uh basically the the account state with a reduced balance. That state has to be finalized. Right. So, you prove the validity of the note after you've you've done the validity of your resulting state. >> Yes, exactly. Like, this note must be included in a finalized the basically. So, uh the sender Bob made this outgoing note, deducted his balance, and finalized that account state.

Yeah. Sorry, um I missed the beginning, so maybe you addressed this. Couldn't Bob just send it to multiple different recip- recipients? Like the the final balance is deducted and finalized, but let's say it's $10 that has been spent, they can send it to multiple different people, and whoever settles it first gets the 10.

Uh so I >> How do you prevent Well, not double spending but Yeah. So, maybe I should have included it here that the note has a recipient. Yeah. Yeah. Yeah, I'm sure. Um so, do you have a a freshness problem? So, when I'm accepting a payment, um I have to know not just that the the proof is valid, but it's fresh in the sense that it refers to a recent um chain state, because otherwise I could just accept a

played proof from ages ago. So, how do I check that? Um Mm. Mhm. So, basically you're saying that I could be receiving a note from some account that has since already been nullified. Exactly, yeah. >> Okay. Okay. Um I think this is basically the risk that the receiver needs to decide how old the ledger state is acceptable. So, if your account is from a really old ledger state, I as a receiver would just reject

it. Okay. Yeah, we're on time. It's lunch time, so some people are hungry. So, yeah, thank you very much, Yingtong, for the talk.