Quantum Unlinkability for Zcash Swaps

An ink key tree: sk at the bottom feeds ak and nk, marked unchanged, and rivk. From rivk, rose lines fan up over a pink disc to four keys, ivk 0 to ivk 3, each pointing to its own posted address.An ink key tree: sk at the bottom feeds ak and nk, marked unchanged, and rivk. From rivk, rose lines fan up over a pink disc to four keys, ivk 0 to ivk 3, each pointing to its own posted address.

Zcash’s shielded transactions are private against future quantum adversaries in many ordinary cases, which is crucial given harvest now, decrypt later attacks. But until Tachyon ships, there is a glaring hole: a single published shielded address lets a quantum attacker link every payment that address’s key has ever received. The most concerning case is swaps through NEAR Intents, where the user’s shielded address is posted on NEAR’s public chain.

We set out to build a fix that wallets can deploy today. It derives a separate incoming viewing key, or , for each address that has to be published, with the account’s spending key untouched, so an attacker who recovers one address’s key learns only the payments made to that address. We call it a one-time .

Each extra key is another key to scan with when restoring a wallet from seed, so a naive recovery would get slower with every swap. To keep it practical we use private information retrieval (PIR), the same technique behind our lookups for Zcash's coinholder voting.

How a Payment Finds You

Every Zcash shielded account has one secret key behind all of its addresses, the incoming viewing key . An address encodes a short diversifier and an elliptic curve point . The wallet hashes to a base point and computes

Alice's wallet can produce as many addresses as it likes by changing . Each gets its own and , and every one of them is computed from the same . Ordinarily, she would give an address to Bob directly when she wants to be paid rather than publishing it anywhere. Even if it were to leak, the address would not reveal , since recovering it from and is the discrete log problem, which is infeasible for a classical computer.

When Bob pays Alice, his wallet decodes her address, recovers from , and uses it with in a Diffie–Hellman key exchange. That gives Bob a secret that Alice can also compute, using . His wallet encrypts the payment under that secret and posts it to the chain, and Alice's wallet decrypts it.

Alice sends Bob her address, pk and g. Bob's payment, locked to her address, lands on a chain of nine blocks. A rose line from Alice's one ivk runs under the chain and opens four notes on it, Bob's payment among them, while the other notes stay sealed.
Bob locks his payment to Alice's address. Her one ivk opens it, and every other payment to her.

That same opens every payment anyone has ever sent to any of Alice's addresses. Whoever holds it sees the value and memo of each one, and sees that they all belong together.

Quantum Adversaries

Keeping Alice’s payments private comes down to keeping her secret. Her wallet never shares it, and nobody can compute it from one of her addresses with a classical computer, but a sufficiently powerful quantum computer running Shor’s algorithm could recover Alice's from the and decoded from any one of her addresses.

Even then, a quantum computer can only do this with one of Alice’s addresses in hand, because the chain itself never contains or . Each payment is locked to her address without revealing it, which is a large part of why, as Sean Bowe explains in Zcash and Quantum Computers, Zcash’s shielded transactions already keep their privacy against quantum computers in many common cases.

Alice’s exposure therefore depends on where her addresses end up. An address she sends to a payer can leak, but one posted somewhere public and permanent is easy to find, and it will still be there whenever a powerful enough quantum computer exists. From that one address, an attacker could recover Alice's and link together every payment her account has ever received.

The equation pk equals ivk times g on a pink disc. A publicly posted address sends one arrow into pk and another into g, both labelled known, and ivk is labelled solved by Shor.
The chain never shows pk or g. A published address hands both to a quantum computer.

How Addresses Become Permanently Exposed

Say Alice wants to pay Bob, who wants USDC on Ethereum. Alice only holds ZEC, so she swaps through NEAR Intents to pay Bob.

Alice's wallet deposits ZEC to a NEAR deposit address on the Zcash chain. The swap quote Alice's wallet generated injects a refundTo address, which is one of Alice's shielded addresses. If the swap fails, or some ZEC goes unused, NEAR sends it back to the refundTo address. That address is written to NEAR's public chain as soon as the deposit registers, whether or not a refund ever happens.

Alice's Zcash wallet sends ZEC to a NEAR deposit address, which sends USDC to Bob's Ethereum wallet. Below, NEAR's public chain lists three swaps, each with a different looking refundTo address, and lines from all three lead to one ivk.
Three swaps post three different looking refund addresses. One ivk sits behind all of them.

Every swap out of ZEC to another chain posts a new refund address. Similarly, swaps into ZEC from another chain post the shielded address as the recipient. The addresses all look different, but they are diversified addresses of one account. A quantum computer only has to break one of them to get the behind all of them, and with it every payment the account ever received.

A Naive Fix

The naive approach is to generate a new account for every swap. Each account has its own , so even if a posted address is broken, it exposes only that one account's payments.

This works, but it is impractical for everyday use since Alice's ZEC ends up split across many accounts. Software wallets can work around this, but hardware wallets such as Keystone and Ledger make this not feasible.

Keystone's Zcash support only allows signing from account index 0, which leaves funds in all other accounts inaccessible. Ledger has access to every account index, but can only spend from one account per transaction. This would mean going through the manual transaction review process / approval multiple times for a single payment, which wasn't an acceptable UX to us.

We needed to find a way for each swap to still have its own , while keeping everything spendable from a single key.

Three panels. First, a 1.2 ZEC balance splits across three accounts holding 0.4, 0.3 and 0.5 ZEC. Second, a Keystone can only sign for account 0, and accounts 1 and 2 are crossed out. Third, a Ledger can spend from every account but needs a separate transaction and approval for each.
The balance splits across accounts, a Keystone can only sign for account 0, and a Ledger needs a separate transaction and approval for each account.

The One-Time ivk

To give each swap its own without splitting the wallet, we needed to change how is generated while leaving everything that controls spending untouched. Zcash derives each of an account’s keys from the spending key , so it helps to look at that derivation first. The spending key derives three secrets. The first, , signs spends, and its public half is . The second, , derives the nullifiers that mark notes as spent, and the third, , randomizes so that it reveals nothing about or . Together , and form the full viewing key, and is a commitment to and .

Zcash's key tree, bottom to top. The spending key sk derives ask, whose public half is ak, along with nk and rivk. ak, nk and rivk form the full viewing key, which gives the incoming viewing key ivk, and the account's address is built on ivk.
An account’s key tree. ak, nk and rivk form the full viewing key, and ivk comes from all three.

What if we deterministically derived a new for each swap instead of using the same randomness every time?

is the keyed hash Zcash already uses to derive keys. ZIP 32 uses this same construction to give each account a separate set of internal keys for change, keeping and and deriving a new from the old one. Ours differs in two ways. It uses its own domain byte, so swap keys can never collide with internal keys, and it appends the purpose and an index, so one account can have as many swap keys as it needs instead of a single internal key. The swap's is then built the usual way, from the same and with the new , and the address Alice posts is built on that .

The same key tree for a swap. ak and nk are marked unchanged and the spending side is faded. rivk is replaced by rivk swap, derived from the account's rivk, a purpose and an index, which gives ivk swap, and the posted swap address is built on it.
Only rivk changes. The new ivk and the address built on it are the swap's own, and spending authority stays the account's.

Because and remain static, spending works the same as before. The account's spending key spends funds received at a swap address directly, and the wallet stays on one account.

Breaking a posted address now gives a quantum attacker that swap's and the payments to that one address. Each swap's looks like an unrelated account's, and tying it back to the account means inverting a hash based derivation, which stays out of reach even for a quantum computer.

The One-Time ivk In Use

Now take Alice's payment to Bob again, this time with the one-time . When she deposits, her wallet takes the next refund index (let's say index 0), derives a fresh swap key from it, and posts the refund address built on that key, so the address on NEAR's public chain has its own .

The deposit transaction Alice makes on the Zcash chain also leaves a note to herself in its change output, which is a memo containing the refund index used to derive that swap’s . The memo is encrypted to her own internal viewing key, so only she can read it, and is how a restored wallet will find this refund later. Recovery will soon be explained, just know that Alice leaves this memo behind to herself so she knows how the for this swap was derived.

A NEAR swap with the one-time ivk. Alice's deposit is one transaction on the Zcash chain with two outputs, 1.0 ZEC to the NEAR deposit address and change carrying a memo with refund index 0, which only her wallet can read. The NEAR deposit address sends USDC to Bob's Ethereum wallet and posts the refund addresses on NEAR's public chain. Each refund address is tied to its own key, and the second address and its key, ivk 1, are marked broken while ivk 0 and ivk 2 are untouched.
Each refund address has its own key. Breaking one exposes only that swap.

The swap fills and NEAR pays Bob his USDC. Any unused ZEC comes back to the refund address, and Alice spends it with her usual spending key. Every payment she makes this way takes the next index, with a new refund address, its own key and its own note to self.

On the day a sufficiently powerful quantum computer exists, an attacker can break one posted refund address and learn about that one refund. It doesn't tie that refund to Alice's other payments, or to her account.

Finding the Payments

Before this one-time idea, Alice’s wallet found all of her payments by trying her on every output on the chain in a process called trial decryption. Now, Alice has a key for every swap she has made. In everyday use this costs little, because her wallet only tries the keys of swaps that are still in flight, starting when each address is issued and retiring each one once its swap settles. Restoring from seed is different, since a fresh wallet would have to try every key Alice ever used against the whole chain, and that cost grows with every swap she makes.

A ten-block Zcash chain. The account's ivk runs a line across the whole chain and opens Alice's ordinary payments, and ivk 0, ivk 1 and ivk 2 each run their own full line too, opening one refund each. A dashed line for ivk 3 marks the extra pass the next swap adds.
On a restore, every swap key is another full pass over the chain.

What if instead of scanning history with all of these keys, there existed some database we could query to not only determine if NEAR’s Zcash bridge sent funds to a given address, but also get pointed to the exact transaction?

Normally creating such a database in Zcash wouldn't be possible, but in the case of NEAR, every outgoing transaction from their bridge on Zcash is encrypted with the same all zero outgoing viewing key. This lets us scan the chain for all transactions that use this specific key and create an address to transaction database that we can query directly.

Instead of scanning history with many keys, a restoring wallet first checks its addresses against small filters, similar to Bloom filters, published alongside the database. Every wallet downloads the filters in full, so checking them reveals nothing about which addresses it holds. A filter can occasionally flag an address that was never paid, which only costs an extra lookup, but it never misses one that was. The wallet looks up only the addresses the filters say were paid, and each lookup points it to the exact transaction it must decrypt.

In order to prevent linking these addresses to the server hosting this database, the wallet asks with private information retrieval (PIR), the same lattice-based technique behind our private lookups for transparent wallets and Zcash voting. The wallet encrypts its question, the server computes the answer over every row of the database at once without being able to read what it is computing on, and only Alice can open the answer. The server never learns which address she asked about.

Top, NEAR payouts on the Zcash chain pass through the all zero outgoing viewing key, which reveals each recipient, into an index server that maps each address to a transaction. Bottom, Alice's wallet sends the server an encrypted question and gets back an encrypted answer. The server computes over every row and learns nothing, and Alice's wallet opens the answer to a transaction, or to no payment.
The all zero outgoing viewing key lets anyone index NEAR's payouts by address, and PIR lets Alice's wallet look up her addresses without the server learning which ones.

Restoring From Seed

Let's now discuss the steps to recover from mnemonic:

  1. The restored wallet runs its usual scan across all transactions with the account's viewing key. Among Alice's notes is the change from her NEAR deposit, with a note to self showing that index 0 was used to derive the for this specific swap.
  2. From index 0, the wallet re-derives the swap key and the refund address built on it, the same way it did for the deposit.
  3. If the published filter says that address was paid, the wallet looks it up privately and gets back the NEAR bridge transaction that paid it, without scanning the chain.
  4. The swap key decrypts that transaction.
One path above the Zcash chain, numbered to match the steps. 1, the account's ivk opens the note to self from Alice's deposit in the first block, which holds refund index 0. 2, index 0 gives back ivk 0 and the refund address u1njfsw7a4 through z9tfcz. 3, a private lookup returns the refund's transaction. 4, the path drops to the last block, where ivk 0 decrypts the refund.
The note to self names the index, the index gives back the swap key and address, and one private lookup finds the refund.

The wallet repeats this for every other note to self. Each note names one index, so the wallet rebuilds only the keys Alice actually used.

Swaps Into ZEC

There is one final NEAR swap case that needs to be handled, which is swaps from an external chain into ZEC. This needs a different approach, since Alice's Zcash wallet never sends anything on the Zcash chain itself, and is therefore not able to leave herself a change note which flags to her which index was used to generate the for that swap.

What Alice's wallet does in this case is derive a chunk of addresses, starting from index 0, and check them in order against the published filters, which list every Zcash address that was ever paid by NEAR, as well as every Zcash address NEAR has quoted but maybe not yet filled. Since her wallet used these addresses in order and the derivation is deterministic, she will find which of these addresses were paid via the filter, until she finds some continuous set of addresses that have gone unused.

Once, say, 30 addresses in a row are neither paid nor known to NEAR, the wallet knows it has found where the account left off. This is safe because the wallet never hands out an address more than 30 past the last one that was paid or given to NEAR. New swaps take the lowest address NEAR has never seen, so a quote Alice abandoned is never reused and two swaps never share an address.

A row of 35 addresses for swaps into ZEC, numbered 0 to 34. Addresses 0 to 4 are marked paid. Addresses 5 to 34 are each unused, bracketed as 30 unused addresses in a row, and the row ends at a stop mark. An arrow notes that the next swap into ZEC uses address 5.
Addresses for swaps into ZEC are checked in order against public filters. After 30 unused addresses in a row, the wallet stops.

Next Steps

Wallets using Zakura’s open source cryptography and wallet libraries, such as Vizor, will be able to integrate this one-time feature for software wallets in the coming weeks. Hardware wallets will follow once their firmware supports it.