Oblivious Message Retrieval


/*! elementor – v3.8.1 – 13-11-2022 */
.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{shade:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}

by Deirdre Connolly

/*! elementor – v3.8.1 – 13-11-2022 */
.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#818a91;shade:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{shade:#818a91;border:3px strong;background-color:clear}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;peak:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:middle;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{show:inline-block}

The Zcash Basis has been wanting into Oblivious Message Retrieval (OMR) to find out whether or not it presents a possible answer to the latest 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 deal with 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 regionally. Would operating OMR on a full node present us with any efficiency benefits when fetching transactions? 

The Present Lightwalletd Structure

Mild wallets are sometimes 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. Nonetheless, that is costly and almost quantities to the complete blockchain in measurement/bandwidth, which isn’t nice for lighter gadgets or these with low bandwidth/community pace, and so forth. That is why the lightwallet protocol exists.

Most mild 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’ve gotten 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. Nonetheless, 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 complete transaction through lightwalletd. The whole lot 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 might be higher if we are able to trial-decrypt and fetch transactions privately, and likewise not need to obtain all transactions in full to take action.

What If We Can Do Higher?

Oblivious Message Retrieval (OMR) is a development 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 realizing the complete question or the ends in plaintext. This might offload extra computational effort and bandwidth necessities to a full node whereas additionally defending the metadata privateness of a consumer or pockets, hiding which Zcash transactions the recipient cares about. The one factor the OMR-compatible full node learns concerning the consumer is that they’re inquisitive about OMR-compatible transactions, however not which of them.


/*! elementor – v3.8.1 – 13-11-2022 */
.elementor-widget-image{text-align:middle}.elementor-widget-image a{show:inline-block}.elementor-widget-image a img[src$=”.svg”]{width:48px}.elementor-widget-image img{vertical-align:center;show:inline-block}

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

A consumer 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 may also embrace a clue ciphertext. This clue ciphertext is about 1KB of further information per shielded output.

The consumer 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, attempting 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 complete node can not distinguish the (encrypted) secret key that’s attempting 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 underneath the clue secret key, and returns the digest of all of the transactions as a brand new homomorphically-encrypted end result. The consumer 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 complete node doesn’t know which transactions are related to the pockets, because it processes all of them and computes the matching underneath fully-homomorphic encrypted computation.

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

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

“Sync” querying – Within the single-shot mannequin, the recipient makes a stateless question to the complete node: it gives a detection key, a spread of blocks to scan, and a sure okay 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 consumer gives a detection key and asks to subscribe to ongoing (and maybe some previous) transactions. The node begins processing these transactions, doing many of the computation (i.e. homomorphically computing the PV ciphertexts). Later, the consumer exhibits up and asks the server to finalize the outcomes and pack them right into a digest, with respect to some okay. Neither the finalization time nor message sure okay want be recognized upfront. This reduces finalization to 0.35 milliseconds/tx per core. 

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

That is engaging to pockets builders and customers who worth the privateness good points of OMR, however hopefully wouldn’t sacrifice usability and expertise to realize them.

This Sounds Nice! Are We Doing This?

Effectively, we’re attempting to determine that out. Zcash has modified a bit since OMR was first printed (now we have Orchard Actions now, for instance). There are design selections we must make concerning the Zcash protocol with a view to help OMR, and different compatibility, design, and UX questions we’d have to deal with. Equivalent to:

  • How backwards appropriate is that this?
    • Requires an up to date key/deal with (see beneath), but additionally new modifications to shielded transactions, particularly the inclusion of 956 bytes of clue information per shielded transaction (or particularly per description: Sapling Output, might should 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 might be the cleanest to increase the transaction format with a devoted clue discipline,” in line with the OMR paper. The clue is 1KB per spend.
  • Do I must generate new keys and a brand new deal with?
    • Effectively, sort of. You might want to generate a brand new clue key to be a part of the deal with, so with Unified Addresses, this generally is a new extension with present Sapling/Orchard key materials, however the Unified Tackle will look completely different. This clue key makes use of a unique 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 large for an everyday QR code encoding, or hex/ascii string, however, an alternate that ought to work within the Unified Tackle framework, and as an alternative of getting the complete clue key inlined within the deal with, we encode and inline a hyperlink to and hash of the clue key, and fetch it from some place 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?
    • Once you arrange a full node to do OMR detection for you, you generate and add a detection key. This key shouldn’t be a part of your deal with. It’s even bigger than the clue key, at ~129MB (sure, megabytes). This can be a one-time add for recipients, however full nodes should hold them per-recipient so long as they’re privately scanning for that consumer. The Zcash mainnet chain is arising on 100GB in measurement, and storage is comparatively low cost, however this does imply including one other recipient consumer as a full node has non-negligible storage prices in addition to the computation prices, and the clue key measurement might limit the variety of addresses that may be detected reside collectively, as some use circumstances contain lots 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 consumer’s (a number of) diversified addresses will 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 line 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 quite a lot of OMR recipients on one full node, will question latency endure?
    • Onerous to say earlier than there’s a full implementation to check. Utilizing the subscribe and finalize question mannequin for the final pockets case would point out it could possibly be fairly quick and scale properly typically in an async-supporting full node like zebrad.
  • That is based mostly on lattices, does that imply it’s post-quantum safe?
    • It appears prefer it, sure!
  • How is that this completely different from viewing keys?
    • Registering viewing keys (incoming, outgoing, or full) with a full node and having them scan the chain on a consumer’s behalf will get near the information circulation 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 discipline, transaction worth, and goal deal with. OMR doesn’t enable this.

What’s Subsequent?

If it had been doable to deploy OMR with out the necessity for a community replace and/or different important modifications (akin to addresses), then we might be wanting very intently at doing so. Nonetheless, given the trouble concerned, we don’t suppose it’s a precedence right now, and we’d need to contemplate different efficiency enchancment approaches (like detection keys).

The submit Oblivious Message Retrieval appeared first on Zcash Basis.


Please enter your comment!
Please enter your name here