Sunday, May 19, 2024

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{coloration: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;coloration:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{coloration:#818a91;border:3px stable;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:heart;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 affords a possible answer 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? Gentle wallets like Nighthawk Pockets, Zecwallet Lite, and YWallet use lightwalletd to fetch and ship Zcash transactions, with out the overhead of working a full node regionally. Would working OMR on a full node present us with any efficiency benefits when fetching transactions? 

The Present Lightwalletd Structure

Gentle wallets are usually used to obtain shielded transactions by way of a lightwalletd server. To protect privateness about which transactions a pockets is thinking about, one can obtain all of the transactions in full. Nevertheless, that is costly and almost quantities to the total blockchain in dimension/bandwidth, which isn’t nice for lighter units or these with low bandwidth/community pace, and so on. 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 is 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, except you could 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 knowledge that’s not included in CompactTxs or CompactBlocks, so after detecting a transaction, the pockets has to fetch the total transaction by way of lightwalletd. Every thing stays encrypted for shielded transactions (the ‘knowledge’), 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 will trial-decrypt and fetch transactions privately, and in addition not need to 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 figuring out the total question or the ends in plaintext. This could 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 thinking about OMR-compatible transactions, however not which of them.


/*! elementor – v3.8.1 – 13-11-2022 */
.elementor-widget-image{text-align:heart}.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 degree, right here’s how a model of Zcash that helps Oblivious Message Retrieval may 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 even embody a clue ciphertext. This clue ciphertext is about 1KB of further knowledge 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, 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 will 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 beneath the clue secret key, and returns the digest of all of the transactions as a brand new homomorphically-encrypted outcome. 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 beneath fully-homomorphic encrypted computation.

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

OMR helps two sorts of querying for outcomes that assist 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 supplies a detection key, a spread of blocks to scan, and a certain 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 consumer supplies 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 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 certain ok want be identified upfront. This reduces finalization to 0.35 milliseconds/tx per core. 

The latter method matches in properly with the steady-state pockets UX: open up pockets app each every now and then, 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 making an attempt to determine that out. Zcash has modified a bit since OMR was first printed (we’ve got Orchard Actions now, for instance). There are design choices we must make concerning the Zcash protocol so as to assist OMR, and different compatibility, design, and UX questions we’d have to handle. Comparable to:

  • How backwards suitable is that this?
    • Requires an up to date key/deal with (see under), but in addition new modifications to shielded transactions, particularly the inclusion of 956 bytes of clue knowledge 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 dimension, along with the bigger Orchard Actions from NU5.
    • “It will be the cleanest to increase the transaction format with a devoted clue area,” in keeping with the OMR paper. The clue is 1KB per spend.
  • Do I must generate new keys and a brand new deal with?
    • Effectively, type of. It’s good 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 current Sapling/Orchard key materials, however the Unified Tackle will look completely different. This clue key makes use of a special sort of cryptography from the Sapling/Orchard keys so we will’t reuse the opposite keys to assist Oblivious Message Retrieval.
    • Per the constructions proposed within the OMR paper, the clue secret’s 133KB. That’s proper, kilobytes (thanks, lattices!) That is too huge for a daily QR code encoding, or hex/ascii string, however, an alternate that ought to work within the Unified Tackle framework, and as a substitute 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 some place else. The clue secret’s 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 developing on 100GB in dimension, 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 dimension could prohibit the variety of addresses that may be detected reside collectively, as some use circumstances 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 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 keeping with the OMR paper. That is about the entire present Zcash mainnet chain proper now so it sounds scalable and reasonably priced to serve a number of recipients.
  • If I serve numerous OMR recipients on one full node, will question latency undergo?
    • 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 might be fairly quick and scale properly usually in an async-supporting full node like zebrad.
  • That is primarily based on lattices, does that imply it’s post-quantum safe?
    • It seems to be 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 info stream 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 area, transaction worth, and goal deal with. OMR doesn’t permit this.

What’s Subsequent?

If it have been attainable to deploy OMR with out the necessity for a community replace and/or different important modifications (resembling addresses), then we might be wanting very carefully at doing so. Nevertheless, given the hassle concerned, we don’t suppose it’s a precedence right now, and we’d need to think about 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