ZIP 314 has been assigned to me for proposing privacy improvements to the Zcash light wallet protocol. A lot of the changes I would like to propose have severe UX drawbacks like drastically increasing the wallet’s bandwidth usage or sync times. So, ahead of writing the ZIP, I would like to explain my thinking and ask the community for feedback on which trade-offs to make.
This is going to be a lengthy and technical post whose purpose is both to educate the community and to request feedback. If you’d like to contribute without slogging through the technical details, please let me know in a reply and I will put together a short nontechnical survey to collect opinions to help inform these decisions.
Let’s start with a survey of what’s wrong with privacy in the current protocol. All of the weaknesses are already documented in the Wallet App Threat Model. In this post I will be focusing exclusively on the privacy problems.
This post will extend previous research by the Zcash Foundation on the same topic.
Privacy against a compromised lightwalletd
The issue I’ve seen raised most frequently in the community is the fact that lightwalletd—the server the wallet connects to—can learn the transaction graph of all shielded transactions sent between its users. This is because wallets broadcast transactions through lightwalletd, so by watching a wallet send a transaction, lightwalletd learns where each transaction comes from. Then, when a wallet receives a transaction, it will fetch the memo ciphertext by indicating exactly which transaction they want the ciphertext for, so lightwalletd learns where transactions are going to, as well. Combining these two pieces of information, lightwalletd learns who sent and received each transaction between its users.
Some implementations introduce ad-hoc defenses against this leakage, for example by requesting to download all memos in a block instead of just the one transaction they are interested in. I don’t consider this to be an adequate defense, since blocks have few shielded transactions at present, so the anonymity set is very small.
I’ve investigated several potential solutions to this problem, but before I enumerate them below, I want to describe a different kind of vulnerability that can be exploited by passive network eavesdroppers. I’m actually a bit more concerned about it, and I think it might be under-appreciated by the community in discussions about light wallet privacy.
Privacy against network eavesdroppers
While the above issue seems to be the most salient one within the community, I am more concerned about similar attacks that can be carried out by network eavesdroppers who haven’t even compromised lightwalletd.
The connection to lightwalletd is encrypted and authenticated, so we don’t need to worry about active attackers modifying or inserting traffic. However, there are bandwidth side-channels that a passive adversary (for example, the NSA or an ISP) can observe to learn information about the wallet’s behavior:
- When the wallet downloads a compact block, it creates an observable traffic pattern.
- When the wallet fetches a memo, it creates an observable traffic pattern.
- When the wallet submits a transaction, it creates an observable traffic pattern.
By watching these information leaks, a passive eavesdropper can approximate the transaction graph that the compromised lightwalletd learns with certainty. The attack goes something like this:
- The eavesdropper watches for traffic patterns that indicate a wallet is submitting a transaction. When they see a wallet submit a transaction, they watch lightwalletd broadcast it to the network in plaintext (or if lightwalletd did so privately, they look for the new transaction in the Zcash mempool). Now, the eavesdropper knows which transaction the wallet broadcasted and which block it ended up in.
- The eavesdropper watches for traffic patterns indicating that the wallet fetched a memo. When they see a wallet fetch a memo, they know that a transaction in one of the recently-downloaded blocks belongs to the wallet.
- If they observe Wallet A broadcasting a transaction and then they observe Wallet B fetching a memo just after Wallet B downloaded the block the transaction went in to, they can conclude with some confidence that Wallet A just paid Wallet B.
The attack is not exact: If a large set of wallets S1 all broadcasted transactions that all ended up in the same block, while another large set of wallets S2 all fetched memos after receiving that block, the attacker can’t find out who in S1 paid who in S2. But they do learn that…
- if a wallet wasn’t in S1, then it wasn’t the originator of a transaction to a wallet in S2.
- if a wallet wasn’t in S2, then it wasn’t the recipient of a transaction made by a wallet in S1.
So, privacy gets a bit better the more active wallets there are (S1 and S2 are larger), but this is still a substantial amount of information leakage, especially at current usage levels. At present, S1 and S2 are likely to be so small they’re just one wallet each—so in practice, an eavesdropper can still find out exactly who is paying who. (I haven’t confirmed this attack with a proof of concept, but I believe it works.)
Solutions I’ve considered
So far I’ve described the two main privacy weaknesses in the light wallet protocol: a compromised lightwalletd server learns the exact transaction graph between its users and a passive network eavesdropper learns an approximation of that same transaction graph.
What options do we have for plugging these information leaks? The following sections walk through the options I’ve been considering. As you’ll see, a lot of the solutions have UX drawbacks—like increased bandwidth usage or long sync times—that would make it harder for a Zcash wallet to be competitive with centralized payment processors like PayPal and Venmo.
PIR
Private information retrieval (PIR) would let a wallet fetch a memo without explicitly revealing which memo they are fetching. However, just adding PIR alone doesn’t solve the information leakage, for two reasons:
- PIR queries are huge (~3MB), so it would actually make the bandwidth side-channels easier for an eavesdropper to observe.
- If a wallet does a PIR query immediately after it learns it received a transaction, lighwalletd and eavesdroppers still learn that a transaction in the last block-or-so belongs to the wallet, so the anonymity set is still very small.
To really illustrate the problem, imagine you’re eavesdropping on a wallet and you have a guess for what its address might be (e.g. you’re an evil dictator trying to find out which wallet owns an address known to be associated with activist activity). To confirm without a doubt the address belongs to the wallet, you send it a transaction and see if it makes a PIR query. Then send two transactions and see if it makes two PIR queries. Then send three and see if it makes three PIR queries. As long as the wallet keeps making PIR queries in response to your transactions, you can be sure that you have found the correct wallet, and you’ve de-anonymized the address.
To fix these issues, the wallet would need to perform ‘dummy’ PIR queries at regular or random intervals even when it has not received any transactions so that when it does need to make a real PIR query to fetch a memo, the attacker can’t know if it’s actually fetching a memo or just making a dummy query. In practice, that would translate to the wallet using 3MB of data each time it is opened, and, if we want the wallet to automatically receive memos while it’s open, probably another 3MB every 30-60 seconds continually. This also creates a UX problem: when the wallet wants to fetch a memo, it can’t do it immediately, it has to wait for the next scheduled ‘dummy’ query, otherwise timing of the query leaks whether it was real or fake.
(Technical point: The bandwidth cost of PIR can be reduced by a factor of 10, to ~0.3MB/query, by using SealPIR’s technique which would require the wallet to register pseudonymous identities with lightwalletd. An argument could be made that this is okay to do, since with transparent address support, the wallet is effectively pseudonymously identifying itself to lightwalletd anyway).
Connecting over Tor
Another suggestion has been to have the wallet connect to lightwalletd over Tor. This alone would not hide the bandwidth side-channels, because Tor only applies minimal amounts of padding to the traffic. What Tor would do is hide the wallet’s IP addresses from lightwalletd as well as from any eavesdroppers local to lightwalletd. Tor could also provide some degree of censorship-resistance to help wallets on censored networks access lightwalletd.
With Tor, a compromised lightwalletd would still learn the transaction graph and eavesdroppers local to lightwalletd would still learn an approximation to the transaction graph. But, since Tor is hiding the IP addresses, wallets’ “names” are no longer written on the graph; the adversary can only identify wallets by the time they are active.
(In fact, once t-addresses are implemented, lightwalletd does learn wallets’ “names”, because wallets must reveal their transparent addresses in order to fetch their transparent UTXOs. So with transparent address support implemented, Tor is not much of a privacy improvement at all.)
By combining the “nameless” graph with other information, parts of the full graph can still be recovered. For example, “X paid Y at 3:00pm then X paid Z at 4:00pm” combined with “Alice was seen using her wallet from 3:00-4:00pm, Bob was seen looking at his wallet at 3:00 and Charlie at 4:00”, we can conclude that X is likely Alice, Y is likely Bob, and Z is likely Charlie. I’m curious if scenarios like this matter to the community: can anyone think of scenarios where “combining information” attacks like this one would cause real harm to users?
Tor also fails to defend against attackers who are eavesdropping on the wallet’s local internet connection. Imagine, for the sake of illustration, a country surveils all of its inbound and outbound traffic to a foreign lightwalletd server. Even though the wallets are connecting over Tor (to foreign guard nodes, let’s say), and all the attacker sees is Tor traffic*, the attacker can still use the bandwidth side-channels to learn when the wallets are sending transactions and fetching memos. So, by correlating the timing of those events, they can still tell who’s paying who within their country.
(* - This is assuming they can distinguish Zcash wallet Tor traffic from all other Tor traffic, which they would have to do by taking advantage of other traffic analysis techniques. I expect that it would be easy to identify a wallet’s traffic, since it would probably not look anything like web browsing, chat apps, etc.)
So, adding Tor by itself doesn’t offer a solution to the privacy problems. Another drawback to Tor, which I haven’t investigated or understood fully myself, is that apparently it’s hard to get working on mobile devices; perhaps that’s something Arti could solve.
Constant-Bandwidth Protocol
To prevent passive eavesdroppers from learning information about what the wallet is doing, we could implement a constant-bandwidth protocol, as I’ve written up in draft form here.
If we did this, wallets could send transactions and request memos without revealing what they are doing to eavesdroppers. As long as the wallet is open, it would be repeatedly sending and receiving chunks of data large enough to contain mempool contents, memo queries, outgoing transactions, etc., so the downside is that it will need to use more bandwidth.
A constant-bandwidth protocol on its own wouldn’t do anything to help privacy against a compromised lightwalletd, since lightwalletd can see the actual queries and knows which ones are real versus filled with padding, but it would eliminate all of the privacy leaks that are visible to passive network eavesdroppers.
Download all memos, when on WiFi
The way that a Zcash full node retains its privacy is by downloading all of the blocks, including all of the transactions. As far as other peers and network eavesdroppers are concerned, a full node’s observable behavior does not change depending on whether some transactions belonged to it or not, so privacy is preserved at the expense of having to download everything.
We could take the same approach in the light wallet protocol. A light wallet could download all of the memos, not just the ones that belong to it, so that it never reveals to lightwalletd or any eavesdroppers which transactions it is interested in. I’ve estimated that a full sync from sapling activation, optimized to remove all unnecessary data, would cost 300MB of data downloaded to the wallet during its initial sync, and on the order of 0.5KiB more for each Sapling transaction that gets mined thereafter (this conservatively works out to ~0.5MiB/day at 2020 shielded usage levels, or ~5MiB/day if shielded transaction frequency grew to match transparent transaction frequency).
This is probably an unreasonable amount of data to download over a cellular connection by default without explicit permission (please let me know if you think otherwise!), so if we implemented this, I would recommend that the large data download would only happen when the phone is connected to WiFi. This would affect the user experience: if you’re away from home and receive a transaction, you’d have to either (a) wait until you’re on WiFi to receive the memo or (b) click a button to approve the use of X MiB of data to fetch all of the memos, including the one you want. (I imagine ECC’s wallet team could work out improvements to this UX!)
Downloading all of the memos would also increase sync times whenever they are bandwidth-constrained, since the compact blocks that the light wallets download would be modified to include the memo ciphertexts for each note.
With this change, and without additionally implementing a constant-bandwidth protocol, network eavesdroppers can still learn who is sending each transaction, but not who is receiving them. So there is still some information leakage, but eavesdroppers can no longer recover the transaction graph. (Zcash full nodes also suffer from this information leakage.)
At the moment this is my preferred solution, since it seems easiest to implement and it prevents both a compromised lightwalletd and any eavesdroppers from being able to learn the transaction graph. I’ve heard objections that it would use too much bandwidth or the sync times would become too long, so I’m curious what the community thinks. How should we prioritize bandwidth usage and sync times against strong privacy properties?
Other options
For completeness, here are some other options:
- Sending transaction information out of band. I think that in the long run, we should replace lightwalletd with a mixnet for distributing transaction information. In the medium term, we could implement liberated payments, but we would still have to support regular (“non-liberated”) payments even if we do that.
- We could have wallets broadcast their transactions privately using something like Dandelion++. This would prevent lightwalletd from seeing one side of the transaction graph, where transactions are coming from, but they would still see the other side, where transactions are going to. If the attacker already knows where a transaction came from, for example if they saw a Zcash full node broadcast it un-privately, then this doesn’t help.
Conclusion
If I’ve been able to convey a couple messages, I hope they’re that these trade-offs can be difficult to make and that solutions that might seem great on the surface (e.g. PIR and Tor) sometimes don’t provide the kinds of guarantees we would expect and want to have.
Regarding the trade-offs, on one hand, we can provide world-class privacy sufficient to protect high-risk users like activists (when combined with additional OpSec training) at the expense of worsening UX (using more bandwidth, adding more buttons to click). Down the road, these decisions might make it harder to compete on usability with centralized payment processors like Paypal and Venmo, but I’m inclined to make these privacy improvements now and face those challenges later once they become real blockers to adoption. Of course, if anyone thinks that implementing my preferred solution—downloading all of the memos on WiFi—would introduce any blockers to adoption in the short term, I would really like to know!
As Zcash begins to see adoption and begins to reach wider audiences, privacy-versus-performance trade-offs will start to matter more and more, and we’ll have to start making even tougher choices, so I’m eager to get that discussion started early.
For your use cases, what matters to you? What do you think matters to other people and their use cases? Do you think you and others want absolute, solid privacy, or would you prefer something performant enough to compete with centralized payment processors so that we can improve the privacy (albeit not as perfectly) of vastly more people? Should these trade-offs end up being options, so that people can decide for themselves which privacy-versus-convenience trade-off they would like to make, even though that adds complexity to the implementations and makes them more confusing to use?
Thanks!
p.s. apologies for the delay in getting this ZIP written up—writing out this post has helped clarify my thinking and decide to recommend download-all-memos-on-WiFi, so unless I hear substantial objections, I’ll be proceeding along those lines!