Saturday, December 2, 2023

Oblivious Message Retrieval

by Deirdre Connolly

The Zcash Basis has been trying into Oblivious Message Retrieval (OMR) to find out whether or not it affords a possible resolution to the current efficiency issues which have affected Zcash pockets customers, and whether or not there are any benefits to be gained from implementing this in a Zcash context. For instance, can OMR be used to handle the privateness leaks of utilizing lightwalletd? Mild wallets like Nighthawk Pockets, Zecwallet Lite, and YWallet use lightwalletd to fetch and ship Zcash transactions, with out the overhead of operating a full node domestically. Would operating OMR on a full node present us with any efficiency benefits when fetching transactions? 

The Present Lightwalletd Structure

Mild wallets are usually used to obtain shielded transactions through a lightwalletd server. To protect privateness about which transactions a pockets is inquisitive about, one can obtain all of the transactions in full. Nevertheless, that is costly and practically quantities to the total blockchain in measurement/bandwidth, which isn’t nice for lighter gadgets or these with low bandwidth/community velocity, and so forth. For this reason the lightwallet protocol exists.

Most gentle wallets fetch a restricted quantity of information about each shielded transaction (i.e. a `CompactTx`) from a lightwalletd proxy, simply sufficient to permit trial decryption. The pockets trial-decrypts each `CompactTx` to see if that transaction has been despatched to them. It’s because all shielded transactions on the Zcash blockchain are encrypted and indistinguishable from the others such that nobody can inform which transactions are addressed to whom, until you may have the incoming viewing key to decrypt them. Trial decryption takes extra computational effort than clear syncing, proportional to what number of shielded transactions are on on-chain, however advances in syncing algorithms have made this cheaper. Nevertheless, to assemble new transactions, a pockets wants information that’s not included in CompactTxs or CompactBlocks, so after detecting a transaction, the pockets has to fetch the total transaction through lightwalletd. All the things stays encrypted for shielded transactions (the ‘information’), however now the lightwalletd proxy is aware of {that a} pockets with a sure IP deal with has requested a sure subset of Zcash shielded transactions, at a selected time (‘metadata’). That is an unlucky and undesirable privateness leak.

It will be higher if we are able to trial-decrypt and fetch transactions privately, and likewise not should obtain all transactions in full to take action.

What If We Can Do Higher?

Oblivious Message Retrieval (OMR) is a building from Zeyu (Thomas) Liu and Eran Tromer that makes use of lattice-based (LWE) fully-homomorphic encryption. It permits a full node to scan the Zcash blockchain for shielded transactions encrypted for a selected recipient and return simply the transactions they want with out understanding the total question or the leads to plaintext. This might offload extra computational effort and bandwidth necessities to a full node whereas additionally defending the metadata privateness of a person or pockets, hiding which Zcash transactions the recipient cares about. The one factor the OMR-compatible full node learns concerning the person is that they’re inquisitive about OMR-compatible transactions, however not which of them.


At a excessive degree, right here’s how a model of Zcash that helps Oblivious Message Retrieval may work:

A person generates an up to date unified deal with that features a new clue key (this additionally helps diversified addresses). When sending cash to an OMR-supporting deal with, the common Zcash shielded transaction will happen, however the transaction will even embrace a clue ciphertext. This clue ciphertext is about 1KB of further information per shielded output.

The person then generates a detection key and registers that with an OMR-supporting Zcash full node. The node makes use of that detection key to scan all the shielded transactions on the chain and their hooked up clue ciphertexts. The scanning includes taking all of the transactions, together with the clue ciphertexts, and fully-homomorphically, making an attempt to make use of the detection key to decrypt the clue ciphertexts related to the shielded transactions.

That is the magic of fully-homomorphic encryption: the total node can’t distinguish the (encrypted) secret key that’s making an attempt to decrypt the clue ciphertexts, as it’s homomorphically encrypted, however it could possibly nonetheless do the computation and return the encrypted outcomes of the computation to the holder of the detection secret key.

Because the OMR-compatible full node scans all of the transactions, it homomorphically accumulates all of the transactions whose clue ciphertexts decrypt below the clue secret key, and returns the digest of all of the transactions as a brand new homomorphically-encrypted consequence. The person can then decrypt these outcomes with the detection secret key, after which have all of the Zcash transactions related to their pockets able to go. The total node doesn’t know which transactions are related to the pockets, because it processes all of them and computes the matching below fully-homomorphic encrypted computation.

What would possibly this really feel like? (past lightwalletd circulate)

OMR helps two sorts of querying for outcomes that help a number of methods for a pockets developer or different shopper to work together with an OMR-supporting full node:

“Sync” querying – Within the single-shot mannequin, the recipient makes a stateless question to the total node: it offers a detection key, a variety of blocks to scan, and a sure ok on the variety of pertinent messages, and asks the node to digest these blocks with respect to that key. The detector runs the entire `Retrieve` algorithm. Response latency is excessive: about 0.145 sec per transaction.

“Async” querying – The subscribe and finalize mannequin makes use of the streaming variant. The person offers a detection key and asks to subscribe to ongoing (and maybe some previous) transactions. The node begins processing these transactions, doing a lot of the computation (i.e. homomorphically computing the PV ciphertexts). Later, the person reveals up and asks the server to finalize the outcomes and pack them right into a digest, with respect to some ok. Neither the finalization time nor message sure ok want be recognized upfront. This reduces finalization to 0.35 milliseconds/tx per core. 

The latter strategy suits in properly with the steady-state pockets UX: open up pockets app each from time to time, get an up-to-date view of pockets state ~instantly, then take an motion.

That is enticing to pockets builders and customers who worth the privateness positive factors of OMR, however hopefully wouldn’t sacrifice usability and expertise to attain them.

This Sounds Nice! Are We Doing This?

Nicely, we’re making an attempt to determine that out. Zcash has modified a bit since OMR was first revealed (now we have Orchard Actions now, for instance). There are design choices we must make concerning the Zcash protocol with a view to help OMR, and different compatibility, design, and UX questions we’d have to handle. Reminiscent of:

  • How backwards suitable is that this?
    • Requires an up to date key/deal with (see under), but additionally new adjustments to shielded transactions, particularly the inclusion of 956 bytes of clue information per shielded transaction (or particularly per description: Sapling Output, could have to be up to date for Orchard Actions). That is okay however requires a community improve and coordination between node and pockets builders. It additionally will increase the transaction measurement, along with the bigger Orchard Actions from NU5.
    • “It will be the cleanest to increase the transaction format with a devoted clue subject,” in accordance with the OMR paper. The clue is 1KB per spend.
  • Do I have to generate new keys and a brand new deal with?
    • Nicely, sort of. You want to generate a brand new clue key to be a part of the deal with, so with Unified Addresses, this is usually a new extension with present Sapling/Orchard key materials, however the Unified Handle will look totally different. This clue key makes use of a special sort of cryptography from the Sapling/Orchard keys so we are able to’t reuse the opposite keys to help Oblivious Message Retrieval.
    • Per the constructions proposed within the OMR paper, the clue secret is 133KB. That’s proper, kilobytes (thanks, lattices!) That is too massive for a daily QR code encoding, or hex/ascii string, however, an alternate that ought to work within the Unified Handle framework, and as an alternative of getting the total clue key inlined within the deal with, we encode and inline a hyperlink to and hash of the clue key, and fetch it from someplace else. The clue secret is a ~public key.
    • How can we keep belief and anonymity if we host OMR keys on one other platform? Key transparency?
    • While you arrange a full node to do OMR detection for you, you generate and add a detection key. This key just isn’t a part of your deal with. It’s even bigger than the clue key, at ~129MB (sure, megabytes). It is a one-time add for recipients, however full nodes should hold them per-recipient so long as they’re privately scanning for that person. The Zcash mainnet chain is developing on 100GB in measurement, and storage is comparatively low cost, however this does imply including one other recipient shopper as a full node has non-negligible storage prices in addition to the computation prices, and the clue key measurement could limit the variety of addresses that may be detected dwell collectively, as some use instances contain tons of or 1000’s of keys.
  • What about diversified addresses?
    • OMR clue keys are diversifiable, in order that property of unlinkable keys is maintained; incoming funds despatched to any of a person’s (a number of) diversified addresses may be retrieved and spent utilizing a single key tuple.
  • How a lot compute does this require from full node operators?
    • “∼$1.02 per million funds scanned (for every recipient served), utilizing commodity cloud computing,” in accordance with the OMR paper. That is about the entire present Zcash mainnet chain proper now so it sounds scalable and inexpensive to serve a number of recipients.
  • If I serve lots of OMR recipients on one full node, will question latency endure?
    • Arduous to say earlier than there’s a full implementation to check. Utilizing the subscribe and finalize question mannequin for the overall pockets case would point out it may very well be fairly quick and scale nicely basically in an async-supporting full node like zebrad.
  • That is primarily based on lattices, does that imply it’s post-quantum safe?
    • It seems prefer it, sure!
  • How is that this totally different from viewing keys?
    • Registering viewing keys (incoming, outgoing, or full) with a full node and having them scan the chain on a person’s behalf will get near the info circulate of OMR, however with one essential distinction: the node can see which shielded transactions you have an interest in and addressed to you, and can learn the memo subject, transaction worth, and goal deal with. OMR doesn’t enable this.

What’s Subsequent?

If it had been attainable to deploy OMR with out the necessity for a community replace and/or different vital adjustments (corresponding to addresses), then we’d be trying very carefully at doing so. Nevertheless, given the hassle concerned, we don’t assume it’s a precedence presently, and we’d wish to contemplate various efficiency enchancment approaches (like detection keys).

The submit Oblivious Message Retrieval appeared first on Zcash Basis.

Related Articles


Please enter your comment!
Please enter your name here

Latest Articles