ZK14 - Merces: Private Token Transfers via MPC and CoSNARKs - Roman Walch (TACEO)

Transcript

Hi guys, thank you for the introduction. Yeah, let's jump right into it. And the title will say we're using MPC and collaborative SNARKs, so I want to quickly spend one slide on introducing what this actually is. So MPC or secure multi-party computation is a cryptographic technique that allows us to compute functions on private data without leaking this data. And the way it works is that we have a set of compute nodes. So here on this picture on the right we have three compute nodes. And they get so-called secret shares of the data. You can see these random-looking noisy images there. And these secret shares do not leak anything about the underlying data itself, but the MPC nodes can use them to compute functions on them. And this might require some

communication, but also this communication between the nodes does not leak anything about the data. And what the outcome of that is is another set of secret shares. And once the MPC nodes are done with computation, they just combine these secret shares and get the desired result. So here it is a super cat. And that's the way we can use MPC to compute on encrypted data. Regarding collaborative SNARKs, that is essentially, simply put, just creating a zero-knowledge proof in MPC. So we have the witness as secret shares, and we compute the proof in MPC. And yeah, essentially a collaborative SNARK. So by having MPC and collaborative SNARKs, what we get is the computability from MPC, provability from the SNARK, and

from both techniques we do not leak anything about the underlying data. So coming back to MERCES, the actual goal of MERCES is that we want to write a private wrapper around any token. This could be a native token like ETH, it could be USDC, or any other ERC-20 token. And we want to be able to deploy this wrapper on any EVM-compatible chain. And what this wrapper should be able to do is that on one hand if a user has some balance with this wrapper token, we will do not want to leak anything about this balance of the users. Also, when a user wants to make a transfer to someone else, we want to be able to hide both the sender and the receiver, but also the actual

transfer amount that the user was sending to someone else. And the way we achieve this is something that we in general call private shared state. And the blueprint for that is actually quite simple. So, on chain in our wrapper contract, we only have a commitment, a cryptographic commitment to all the balances of the users. The balances themselves are stored off chain on an MPC network in secret shared form. And since they are secret shared, the MPC nodes can compute on them. For example, when I make a transfer, then the MPC network can update the balances of the users.

This will then also compute the new commitment of the of these balances which we then store on chain to reflect the new state. And the smart contract will only accept this new commitment if we also provide a zero knowledge proof that this were the computations were done correctly and as intended. And this is where the collaborative snag comes into play. So, summarizing, on chain we only have a commitment and we store the actual balances in some data structure off chain in an MPC network in secret shared form.

So, how do we achieve a private and provable smart contract there? So, on the MPC network, what we actually want to build is some kind of hash map where we map an user address to some kind of balance. And here this square brackets they indicate already, this should be remain private. So, the balances are stored in secret shared form, but also when we access these balances, we should hide which addresses we are actually accessing here. And our way to achieve this is essentially we model this uh uh hash map as a Merkle tree and then this Merkle tree is fully secret shared on the MPC network. On the leaf layer, we have the actual balances of the users

and the path from the commitment to a balance is the address of the user. And the root node of this Merkle tree is just a commitment to the whole data structure which will be public on chain and whenever we update the balances, we also update this root commitment here and this is the new commitment that we store on chain. And we can use a membership proof to prove that the updates of all these leaves were done correctly. So so far there is nothing too special about this, but what is interesting about our design is that each layer of this Merkle tree is implemented as a so-called oblivious RAM and that is a primitive from MPC which allows us to read and write this to these slots without the MPC network actually knowing to which slots

it actually accessed. So the MPC network will just get secret shares to the addresses we want to access here and the oblivious RAM primitive allows us to read these slots and update these slots again. So from the point of view of the MPC network, when a user wants to do a transfer, a private transfer, what is actually happening is that the MPC network will get secret shares from the transfer amount, secret shares from the sender address and secret shares from the receiver address and they also require some kind of user identification here because we don't want to give anyone the possibility to make transfers on behalf of someone else. So the user needs to also provide a zero-knowledge

proof that it knows the secret key corresponding to the sender address here. And if the MPC network is able to verify the proof, what it does is essentially just accessing the oblivious RAMs in the leaf layer, modifying the balances. This also triggers then update of the whole Merkle tree structure, produces a new commitment and this is the commitment that we post on chain. The MPC network as we said before also needs to create a collaborative snack and this essentially just proves three things. On one hand the balance was positive, the other hand the sender needs to have enough balance to fulfill the request and the third thing is that um data structure needs to be updated correctly and that essentially requires

four Merkle proofs to binding the old balances to the old commitment and two we're using the same path to Merkle proofs which prove that the new balances produced a new commitment that we stored then on chain. So this is essentially everything that is happening on the MPC side. And with that we could already implement full private transfers. However, if we just follow it the way we I talked about now we will get a very inefficient design. And the reason for that is that in Ethereum we usually have where 160-bit addresses and if you build a Merkle tree that has the addresses as the path from the commitment to the balances, then we need 160 layers there.

In our design where we have ORAMs for each layer, this also implies that we have 160 ORAMs, 160 ORAM accesses for each transfer and also in the lowest layer we have two to the power of 160 elements in there and this is way too big for any ORAM design to be efficient at all. So we need to come up with some kind of optimization. So we experimented in the past already with some sparse Merkle tree designs in MPC but the what we learned in the last months is that the most efficient solution in our opinion is to introduce something that is called an ID registry. And that is essentially when a user wants to engage with our private token transfer system, it has to register in this ID

registry and this is essentially then just a lookup from the user address to some incrementing index. So, if I'm the seventh user to register, I get the index seven. And this is then the index that we use in the Merkle tree on the MPC side to to access the balance of the user. And essentially, when a user then >> [snorts] >> wants to make a private transfer, the authentication proof also needs to take account this lookup from this address to the index. So, how did we implement this ID registry? Essentially, this is also just a Merkle tree. You see this here on the left side. This is a fully public Merkle tree. And I when I register, then I get the next free leaf assigned. And the path from the

commitment to the leaf will be my index. That is also the index on the MPC network. So, here on the right is the MPC Merkle tree. And you can see that the path is the same as in this public ID registry Merkle tree here. So, as I said before, when the client wants to authenticate itself with the zero knowledge proof that it knows the the secret key to address, we also now need to include a membership proof of this ID registry Merkle tree. And then that the path for this where my public key is stored is then the one that is put into the MPC network as a sender index.

Okay. Um Sorry. Yeah. So, this is now the the the full view of the protocol from the point of view of the client. So, when I'm a client and I want to engage in a private transfer with Merces, first I obviously need to register with the ID registry. If I have already done that, then I still need to engage with the ID registry to be able to create this authentication zero knowledge proof. Then I secret share the amount that I want to send to someone else. I secret share my index. I secret share the receiver index. And what I also need to do is create some commitments to um ID, receiver ID, and the amount. And these commitments will then later be

used to bind the proof uh created by the MPC network to my user intent. Uh also in our system, we um give the secret shares uh to the MPC network via the um smart contract. So, what we do there is we um encrypt each secret share with the public key of the receiving party, and that is also posted on the on on chain. And the client then creates a zero-knowledge proof that proves everything of that. So, on one hand, the ID registry look up uh that it knows the secret key for its uh address, and also that the commitments and the uh encryptions of the secret shares were computed correctly. Once this is done, it uh posts this into our wrapper smart contract, where the zero-knowledge proof gets verified, and on success, um the

request get puts uh gets put into some uh action queue, and the MPC network regularly um queries this action queue, reads the cipher text from chain, gets the uh secret shares from it, and is able to update the uh full Merkle tree based on these uh secret shares. Once it's done, it uh creates the um the new commitment to the data structure and the zero-knowledge proof, proving that everything was done correctly. Okay. Um regarding performance, on this slide, I give you some benchmarks on the uh MPC network's computation. This includes uh reading and updating the data structure, and also creating the zero-knowledge proofs in MPC. And I give you numbers for um different uh sizes of

the Merkle trees, so how different um users were registered in there, and also for different um um machine setups. So, on one hand, we have a M7a.4xlarge, is a fairly standard AWS uh CPU machine. Um and in the other hand, I give you benchmarks for a G5.4xlarge, where each party also has access to a graphic card. And you can see uh if we If we around 100,000 users registered in Merces 2, it takes um around 200 milliseconds to process a request including zero knowledge proofs.

And this is done both on the CPU and GPU machine. If we have around 4 million users registered in Merces, then on the CPU machine, this you can see it takes a little bit longer now, around 1 second for this request. But on the machine with access to a GPU, we see that the scaling is way better and here it uh takes roughly 370 milliseconds to fulfill the request. So in total we get around three to five transfers per second on the MPC side depending on how many users are registered in the system. Okay, this brings me already to the end of the talk.

I introduced Merces, our solution to realize private token transfers. We hide sender, receiver, balances, and transfer amount. And I want to say that we use MPC for privacy, but for integrity of the whole system, we only use the CK system. So essentially if all the MPC parties would collude, they would not be able to misuse the funds. So and we implemented this design using what we call an oblivious hash map, and this is based on a Merkle tree and ORAMs. The design is fully implemented and if you scan this QR code here, you can interact with a demo that we launched on a plasma testnet. So you can make private transfers there and also see what is actually posted on chain and

you will see that nothing is actually leaked to the users. Throughput of our system depends on how many users are registered for Merces and is around 40 TPS. And I want to note here that if we deploy a system where we always allowed to leak sender and receiver, then we can actually get up to 300 TPS. And for this system with the relaxed security assumption, we actually wrote a paper that we published last week and there we have a full UC security proof in there. So, future work about our system. So, on one hand, so we also hint this in this demo already, is that we want to be able to um implement some private swaps. So, when you have deployed some tokens into our Merkle system, you can swap this to

some yield bearing tokens with uh for example from Aave or Morpho. Then your um deployed tokens actually generate some yield. And another thing is we want to integrate um Merkle system as the payment backends from some more complex protocols, for example the X4 to payment standard. Um, that's uh the end of my talk. If you have any questions, I don't know if you have time, you can ask me now or find me later and then I will happy to discuss further. Thank you for your attention.