# Quantum Unlinkability for Zcash Swaps

Engineering post by Adam Tucker about the one-time ivk: a way for a Zcash
wallet to give every NEAR Intents swap its own incoming viewing key, so that a
future quantum computer that breaks one publicly posted swap address cannot
link it to the rest of the wallet's payments. It also covers how a wallet
restored from seed finds those swaps again without scanning the whole chain
with every key.

Status: a design built into Zakura's open source cryptography and wallet
libraries. The post says wallets using those libraries, such as Vizor, will be
able to integrate it for software wallets "in the coming weeks", and that
hardware wallets will follow once their firmware supports it. The post does
not give a release date or version, and nothing in it says the feature has
shipped.

What the post says:

- Background. Every Zcash shielded account has one incoming viewing key,
  ivk. An address encodes a short diversifier d and an elliptic curve point
  pk_d; the wallet hashes d to a base point g_d, with pk_d = [ivk] g_d. A
  payer recovers g_d from d and uses it with pk_d in a Diffie-Hellman key
  exchange to encrypt the payment, and the recipient's ivk opens it. A wallet
  can produce many different looking (diversified) addresses by changing d,
  but all are computed from one ivk, and whoever holds it can open every
  incoming payment, see each value and memo, and see they belong together.
- Quantum risk. Recovering ivk from an address's pk_d and g_d is a discrete
  log problem, infeasible classically, but a sufficiently powerful quantum
  computer running Shor's algorithm could do it from any one of the account's
  addresses. The chain itself never contains the address material, which is a
  large part of why, as Sean Bowe's "Zcash and Quantum Computers" explains,
  shielded transactions keep their privacy against quantum computers in many
  common cases. The risk comes from addresses that are posted somewhere
  public and permanent; the post frames it against harvest now, decrypt later
  attacks and calls it a glaring hole until Tachyon ships.
- NEAR Intents. When a Zcash wallet swaps ZEC to another chain through NEAR
  Intents, the swap quote includes a refundTo address, one of the user's
  shielded addresses, where NEAR returns ZEC if the swap fails or some goes
  unused. That address is written to NEAR's public chain as soon as the
  deposit registers, whether or not a refund happens. Swaps into ZEC post the
  receiving shielded address as the recipient. These posted addresses look
  different but are diversified addresses of one account, so breaking any one
  of them would expose the ivk and every payment the account ever received.
  The post singles these swaps out as the most concerning case.
- Naive fix, rejected. A new account per swap would isolate each ivk but
  splits the balance across accounts. Keystone's Zcash support only signs
  from account index 0, and Ledger can spend from only one account per
  transaction, so one payment could need several manual approvals.
- The one-time ivk. An account's spending key derives ask (whose public half
  is ak), nk and rivk; ak, nk and rivk form the full viewing key, and ivk
  comes from them, randomized by rivk. The one-time ivk derives a new rivk
  per swap:
  rivk_swap = ToScalar(PRF^expand_rivk([0x85] || ak || nk || purpose || index)).
  This mirrors the construction ZIP 32 uses for an account's internal (change)
  keys, with its own domain byte so swap keys cannot collide with internal
  keys, plus a purpose and an index so an account can have many swap keys.
  The swap's ivk is built from the same ak and nk with the new rivk, and the
  posted address is built on it. Because ak and nk are unchanged, the
  account's spending key spends funds received at swap addresses directly and
  the wallet stays on one account.
- What a quantum attacker gets. Breaking one posted swap address yields that
  swap's ivk and the payments to that one address. Each swap's ivk looks like
  an unrelated account's, and tying it back to the account would mean
  inverting a hash based derivation, which the post says stays out of reach
  even for a quantum computer.
- Note to self. Each deposit takes the next refund index (0, 1, 2, ...). The
  deposit transaction's change output carries a memo holding only that index.
  The memo is encrypted to the account's internal viewing key, so only the
  wallet can read it, and a restored wallet uses it to find the refund.
- Everyday scanning. A running wallet trial-decrypts only with the keys of
  swaps still in flight, from when each address is issued until its swap
  settles, so the cost stays small. Restoring from seed is the expensive
  case: a fresh wallet would otherwise have to try every swap key it ever
  used against the whole chain.
- The zero-OVK directory. NEAR's Zcash bridge encrypts every outgoing
  transaction with the same all zero outgoing viewing key, so anyone can see
  which address each payout went to. That allows an address-to-transaction
  database of NEAR's payouts.
- Filters. Alongside the database, small filters similar to Bloom filters
  are published. Every wallet downloads them in full, so checking them reveals nothing about its addresses. A filter can
  flag an address that was never paid (costing one extra lookup) but never
  misses one that was. A restoring wallet looks up only addresses the filters
  say were paid.
- Private lookups. Lookups use private information retrieval (PIR), the same
  lattice-based technique behind Zakura's private lookups for transparent
  wallets and Zcash voting. The server computes over every row without
  learning which address was asked about, and only the wallet can open the
  answer, which points to the exact transaction to decrypt (or to no
  payment).
- Restoring a refund: (1) the restored wallet's usual scan with the account's
  viewing key finds the deposit's change and its memo naming the index;
  (2) the wallet re-derives the swap key and refund address from that index;
  (3) if the filter says the address was paid, a private lookup returns the
  NEAR bridge transaction that paid it, with no chain scan; (4) the swap key
  decrypts it. This repeats per memo, so only keys actually used are rebuilt.
- Swaps into ZEC leave no memo, because the wallet sends nothing on the
  Zcash chain. The wallet derives addresses in order from index 0 and checks
  them against the filters, which list every Zcash address ever paid by NEAR
  and every Zcash address NEAR has quoted, filled or not. After 30 addresses
  in a row that are neither paid nor known to NEAR, it stops. 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 an abandoned quote's address is never reused and two
  swaps never share an address.

Sources linked from the post:

- NEAR Intents: https://near.org/intents
- Sean Bowe, Zcash and Quantum Computers:
  https://seanbowe.com/blog/zcash-and-quantum-computers/
- ZIP 32: https://zips.z.cash/zip-0032
- Zakura's transparent PIR post (private lookups for transparent wallets):
  https://zakura.com/engineering/transparent-pir-rotating-addresses/
- Zakura's PIR security parameters post (Zcash voting):
  https://zakura.com/engineering/pir-security-parameters/
- Background articles on Wikipedia: discrete logarithm, Diffie-Hellman key
  exchange, Shor's algorithm, Bloom filter, private information retrieval,
  "harvest now, decrypt later".

---

Canonical HTML version: https://zakura.com/engineering/quantum-unlinkability/