Oblivious Message Retrieval

Due to lack of space, please see the full proposal here: https://hackmd.io/@thomaslzy/HyZ0XYG5Y

Applicant background

The main proposer is Zeyu (Thomas) Liu, a masters' student and Graduate Research Assistant at Columbia University, who is applying for a scholarship to support his ongoing academic research on this problem and his collaborations for bringing it to practical integration. Thomas’ research interests broadly lie in the field of cryptography, including lattice-based cryptography and blockchain-based protocols, as exemplified by his recent works on fully homomorphic encryption schemes and their applications.

The proposal is submitted jointly with Eran Tromer, who will collaborate with Thomas on the academic research and will advise on execution and integration, but is not requesting support. Eran is an Associate Research Scientist at Columbia University, a coauthor of the Zerocash paper, a founding scientist of the Electric Coin Company (he has donated all of his interest in it), and formerly an advisor to the Zcash Foundation.

Description of Problem or Opportunity

  • Efficient private node detection/retrieval has long been a problem on Zcash light clients.

    • The recipient wants to know and retrieve the transactions that are addressed to them.
    • If the recipient has only limited computation power (e.g., on mobile chips), the recipient may want to outsource this detection/retrieval process to some server, while maintaining privacy (i.e., the server should not know which transactions are for the recipient)
    • When the server is sending back the result of detection/retrieval as a digest, ideally, we want the digest to contain only relevant information (e.g., for retrieval, only all the transactions addressed to that recipient)
  • Currently, Lightwalletd is sending part of each node back to the recipient and letting the recipient use trial decryption to identify which transactions are addressed to them ZIP-307

    • Cost is 116 bytes per node
    • For the recipient, the computation cost is hundreds of microseconds per transaction (on a Compute-optimized GCP instance)
    • It is for detection only, and, therefore, the retrieval process is still not done privately
  • Importance evidence:

    • Zcash developers [Hor20] deem it an “action item” that the “lightwalletd server” learns which transactions belong to the wallet”

Proposed Solution

  • Oblivious Message Retrieval (OMR)
    • A protocol, developed by Eran and Thomas, that can allow the recipient to outsource all the work to the server, while remaining fully private
    • Detailed paper
    • Preliminary demo implementation
    • Potentially, all the Zcash users can use this protocol to privately retrieve their transactions
  • Integrating OMR with Nighthawk Wallet
    • Providing support for building a Zcash SDK integration with OMR library
    • Providing server side libraries for integration with lightwalletd
    • All the users of the Nighthawk wallet will be able to use OMR to privately retrieve their transactions

Solution Format

  • C++ based libraries (published under an open-source license, tentatively MIT)
    • OMR library
    • Library of improved OMR schemes (e.g., group OMR)
  • Demos of integration with Zcash transactions
  • Academic papers

Technical approach

image info

OMR research:

  • Current Version:
    • The figure above shows the high-level picture of our protocols.
    • The recipient holds a detection key and a clue key, both public. The sender generates a clue using the clue key and attaches the clue with the transaction.
    • The server (detector) uses the detection key to compress the transactions into a small digest and send them to the recipient.
    • Full protocol in: https://eprint.iacr.org/2021/1256.pdf
    • Implement the open-sourced OMR library using C++, and make the library easy to use for developers
  • Group OMR
    • Group version of OMR, serving for an ad-hoc group of recipients instead of processing each recipient’s clue separately, thereby improving efficiency
    • We also use the group OMR to improve the efficiency of regular OMR (Expecting ~3-5x faster on the server’s side, but 2~3x larger for the digest size)
    • Implement the group OMR schemes
  • Other improved versions of OMR
    • E.g., hardware-accelerated

Due to lack of space, please see the full proposal here: https://hackmd.io/@thomaslzy/HyZ0XYG5Y


Tips Received


a month ago
Funded through  Zomg logo
Initial cost
Develop usable OMR library
Offline demo
Group OMR
Improving OMR
Group OMR implementation
Improved OMR implementation
Offline demo
Further research

Develop usable OMR library

Estimate: April 2022
Reward: $14,700
Convert the current benchmark/demo into a developer-friendly C++ library, with API guided by requirements from Nighthawk and other wallet developers

Payment Request

The team may request a payout for this milestone at any time.