Good morning everyone,
I thought it might interest some of you.
We have just released a paper and a proof of concept implementation of Zerocash on Ethereum.
The paper can be found here: http://arxiv.org/abs/1904.00905
The code can be found here: https://github.com/clearmatics/zeth
This is a proof of concept and many things need to be addressed (see paper and issues on the github repo) for more details on this.
Happy to get any feedback/comment.
Have a great day 
Great job! 
The main issue that I see for things like this to be useful in ethereum in practice is the fact that ETH used to pay for transaction fees to withdraw is a deanonymization vector. Do you have any proposals for how to fix this?
Thanks @vbuterin!
In the paper we acknowledge the fact that users of the mixer are distinguishable from users who do not use the mixer (as they need to call the mix function of the mixer).
However, our claim is that ZETH blurs the transaction graph well enough to be considered in cases where we need to obfuscate:
To support this claim it was important to follow the statement and the construct detailed in Zerocash that allows to execute payments of arbitrary denominations “directly in the mixer” (by this I mean that the proof generated by the sender ensures that the system remains sound - no value is created, no double spend occurs and so forth. That way the mixer only processes obfuscated data while being sure the system remains sound.).
The rational behind this was to avoid to “bounce on the Ethereum public state” every time a payment was received and needed to be done.
In fact, the mixer contract in charge of maintaining the merkle tree of commitment and the nullifiers, and in charge of calling the SNARK verifier contract only implements a unique mix function (we deliberately moved away from functions like deposit, and withdraw). This mix function can be used to add public value to the mix (deposit), remove public value form the mix (withdraw), transfer zethNotes (transfer), or do all three at the same time.
The proof verified in a mix call is a proof generated for a statement similar to the one of Zcash-Sprout (but simplified for the PoC). This statement includes the check of a joinsplit equation which allows to “pour” some notes in some others (see section 3.4.3 of the paper).
These newly created notes (the output of the joinsplit) are not necessarily dedicated to the same users. Moreover, the statement used in zeth supports the use of dummy notes of values 0 (via the addition of extra constraints in the R1CS in the form v_i · (1−e) = 0, where v_i is the value of the note_i, and where e is a boolean used to enforce a merkle root equality check between the merkle root given in the instance (rt) and the merkle root rt' obtained from the check of the merkle path mkPath_i of cm_i (commitment of note_i). See 3.4.3 of the paper).
With this possibility to use deposited funds on the mixer as inputs to the joinsplit, someone who has deposited or received funds from someone else can use these to pay someone else without ever needing to withdraw from the mixer.
Zeth becomes a layer of obfuscation seating on top of Ethereum where new notes can be created and destroyed to transfer value. This requires to pay for the gas to execute the mix function but does not leak any other data. Only meaningful leakages happen when public funds are added to the mix or when obfuscated funds are removed from the mix.
The claim here is that state transition encoded by the mix function of the Mixer smart contract is not equal to the state transition resulting from plain Ethereum transactions in term of information leakage.
Moreover, to protect the sender and recipient relationship, we leveraged Ethereum events as a way to implement an encrypted broadcast to send the value of the zethNotes to the intended recipient. The sender encrypts a zethNote under the recipient’s key (here we need to have an IK-CCA scheme), and adds the ciphertexts as an argument to the mix function of the mixer.
The mixer mix function’s signature looks like:
Mix(π,rt,v_{in},v_{out},{cm^{new}_i}^M_{i=1},{sn_i}^N_{i=1},{c_i}^M_{i=1})
Where:
Here’s a screenshot of the pseudocode of the Mix function.
Now, let’s consider an example with Alice, Bob and Charlie being 3 users of the system:
Assumptions:
N (joisnplit inputs) = 3
M (joisnplit outputs) = 3
gasEpsilon denotes the gas cost of the execution of mix
Note: Alice and Bob are free to spread their wealth as they prefer across all their notes. Alice deposit could have translated in 3 zethNotes (zethNote1.val = 0, zethNote2.val = 7, zethNote3.val = 2ETH) for instance. Same for Bob. In order to deposit their funds, Alice and Bob can generate dummy notes as input to the joinsplit.
Note: Alice’s has used her note zethNote2 along with dummy inputs to create the note zethNote4.val = 2ETH for Bob along with her change zethNote4.val = 1ETH, zethNote5 = 0ETH. Again, Alice could have created notes zethNote4.val = 1.9ETH, zethNote5 = 0.1ETH for Bob, and taken a change in the form of a unique note zethNote4.val = 1ETH for instance.
mix call (this leakage does not leak anything else)As mentioned in the paper, we encourage users to send periodic dummy payments to themselves. While this costs a bit of gas, this introduces some noise in the system.
Namely, here Charlie, cannot decrypt any of the mixer events payload, so he can only guess that the recipient was either Alice or Bob (assuming the encryption scheme is IK-CCA). Thus, despite Alice’s call to the mixer, no information is gained.
Now, Bob can either withdraw some funds back from the mixer, or pay someone else. If he decides to withdraw more than the value he initially deposited, then Charlie learns some information and knows that he has received funds from someone else on the network (here this someone else is only Alice, but it might not be as obvious in a network with a large set of users). In fact, Charlie learns that Bob’s received funds were at least r = w - d where w denote the value withdrawn and d the total value initially deposited by Bob.
We propose some best practices and present some limitations in section 4 of the paper. One of the best practice being to keep the funds as long as possible on the mixer, and use these to do payments. This yields long chains of payments and makes it harder to follow.
Last but not least, the use of Ethereum events along with the possibility to create M notes (for potentially M distinct users) present the nice property that Alice can pay up to 3 recipients in a single transaction. Thus, this might be a nice way to have scalable systems as it could limit the number of transactions sent to the system (However, checking merkle paths remains a big performance bottleneck.)
I’ve been looking at this under the category of Locally Differential-Privacy such as with Google’s RAPPOR. Wondering if this could be adapted to the problem faced here at the client level. Would take a bit to unwind that idea, but have you seen this?
Great work! Coming from AI/ML, I’ve found expander walks and min-entropy in light of the graph isomorphism problems behind Hamiltonian cycle zk pretty interesting to consider at large enough scale. Am also looking into methods to apply zk.
Everything I’ve heard above feels very imperfect. For the most simple usecase, where I have funds in an address A1 and I want to send them to a new address A2, without linking A1 to A2, I need to send ETH to A2 to be able to call the withdraw function, and this send itself unfortunately creates the link. Sure, you can make weird heuristic approaches to get around this, but that’s very unsatisfying next to the extremely high level of privacy that a ZK snark mixer gives you.
I think the only truly viable solution at least right now before we have some form of account abstraction is a separate gossip network for broadcasting withdrawal requests, along with the ability for withdrawal requests to include a fee. But that’s harder than a smart contract to use…
Yes that’s indeed true, but I think we are not talking about the same thing here. Zeth does not address the case you are describing (which is also something we have been thinking quite a lot when working with Mobius)
If you create a new address and want to send funds to it you indeed need to fund it with ETH to pay for the gas to the mix function. There’s no way around this in the current stage of the Ethereum. Zeth is no exception and will not help with it (a proposal to bypass this is proposed in Appendix A, but it assumes account abstraction).
Zeth helps in a very specific case where you’d like to (privately) exchange value between a set of funded addresses. These funds are represented in the form of notes and the statement being proven allows to do payments of arbitrary denominations so that users are given the possibility to keep their funds obfuscated.
In the example given (Alice, Bob and Charlie), I took care of depositing almost all Alice and Bob’s wealth on the mixer, and keeping a few ETH to pay for the gas (these public balances are then decrement by gasEpsilon to represent the action of paying for gas when calling mix).
Charlie has a balance of 0ETH, but does not intereract with the mixer. We can assume that he is a passive attacker monitoring the Ethereum balance of his counterparts
With this respect, what is your opinion on BGP level routing in ETH? Is there a canonical view to this? Adapting differential privacy in this case may be ill-suited, it really comes down to the architecture. I am putting ideas out.
Have had some issues with sMPC in the past. Wouldn’t full nodes using >1-2 oblivious transfer possibly be subject to an unknown key-share attack depending on how the keys are generated and distributed? The remixing or broadcasting of a coupling between payload and address would have to change client logic substantially and be substantiated quite robustly.
Agree regarding gossip networks and would extend also to general overlay networks, however the economics of the fee, incentive, and designs thereof can become problematic especially with the public good assumptions underlying the use of a public utility, however this risks going off topic at this point. zk-S[N/T]ARKs at least are quite direct in their natural utility.
Thanks for the comments!
I’d say for the simplest prototype, any dumb gossip network will do; you can outsource internet packet anonymization to the user’s choice of VPN/Tor/going to Starbucks. For “version 2” it’s definitely true that the ethereum network as a whole needs a better special-purpose solution!