# Transaction retrieval on Aztec

**Oblivious message retrieval (OMR)**

With OMR one can retrieve only their transactions from the server without leaking privacy. In OMR each transaction is tagged with a clue and the clue is encrypted receiver's identity. For practical implementation, the encryption scheme used for clues should have a decryption circuit that can be evaluated efficiently homomorphically. To send a transaction, the sender retrieves the receiver's clue public key and generates a clue. The server collects all transactions and processes them in following manner: Server homomorphically decrypts each clue and checks whether clue's identity matches user's identity. Server homomorphically only packs pertinent transactions into an encrypted digest of fixed size. Whenever any user comes online, they can request the encrypted digest from server and decrypt it to find their transactions.

We prototyped an implementation of OMR and make following observations:
1. It takes 3.36ms (2.57 ms with some one time pre-compute per user) per transactions on 16 cores.
2. Clue size is almost 1Kb.
3. Clue key size is roughly 133 Kb
4. Detection key size is 163 Mb
5. Message digest size that can fit at-most 64 txs (each of size 512 bytes) is around 800 Kb.

[Link](https://github.com/Janmajayamall/ObliviousMessageRetrieval) to OMR implementation.

Further improvements:
1. Improved Key switching operation: Key switching operation (used in multiplications and rotations) comprises of majority of runtime in OMR (true for most FHE circuits using BFV scheme). Due to improvements in key switching operation introduced [7], key switching can be sped by roughly 1.3x-2.3x.
2. Improved polynomial evaluation: The most expensive part of OMR circuit is polynomial evaluation of degree 65536. To reduce no. of non-scalar multiplications (i.e. ciphertext-ciphertext multiplications), we use Paterson-Stockmeyer (PS) method of polynomial evaluation. Recently, a new approach for polynomial evaluation that is faster than PS was introduced in [8]. This may improve OMR runtime.

Observe that if there are $k$ users and $N$ transactions, then server's runtime complexity is $kN$. Moreover, since OMR uses levelled HE, each operation is lot more expensive than simple plaintext operation.

It is relevant to note that, in contrast to other approaches except FMD, OMR does not require any prior communication between sender and receiver. OMR provides complete sender-receiver unlink-ability whereas FMD may not. Moreover, OMR gives complete cryptographic security whereas FMD provides k-anonymity [9].

**Tag based approaches**

Tags are a form of clue. We differentiate between tags and clues on the basis that tags require prior contact between sender and receiver to be able to generate them, whereas clues do not.

We assume that sender and receiver share a secret and maintain a nonce between them. When a sender sends a transaction they produce a hash using the secret and the latest nonce they share with the receiver. A server stores all transactions in a database. To retrieve transactions, the receiver optimistically requests transactions corresponding to tags generated for next few nonce values in sequence. On the basis of the response received from server, receiver updates the nonce to latest value.

For privacy it is crucial that the user retrieves transactions corresponding to tags from the server without sever learning the tags and there are two ways to achieve this:

1. Private set intersection using levelled HE: Server runtime is linear (i.e. $\mathcal{O}(N)$) with size of server set (i.e. database) and server-client communication is sub-linear with size of server set. Client-server communication depends on client set (i.e. no. of tags client optimistically generates).
We [prototyped PSI and benchmarked](https://github.com/Janmajayamall/ulpsi) it for multiple server sets and client sets from which we can conclude that the prototype can process roughly 190txs/ms on 16 cores per request.
2. Single server PIR based on cryptographic primitives:
1. Levelled HE: All practical schemes suffer from $O(N)$ server-runtime complexity. Most schemes have communication complexity of $O(\log{N})$ but at expense of increased server computation. PIR using levelled HE is significantly slower than PIR based on other primitives. For ex, the two schemes with $O(\log{N})$ communication complexity are Spiral [10] and Onion PIR [11] and have throughput 1314Mb/s and 104 Mb/s [3].
2. Linear homomorphic encryption (LHE) using lattices: Schemes based on LHE suffer from communication complexity of $O(\sqrt{N})$ and server-runtime complexity of $O(N)$. But they offer much better throughput than PIR based on levelled HE. For example, SimplePIR has throughput of 10305 Mb/s [3].
3. Stateful PIR: PIR based on levelled HE and LHE can be called state-less PIR. Stateful PIR differ from stateless PIR on the basis that former requires client-dependent pre-processing step. Using client dependent pre-processing step, stateful PIR overcomes the limitations of stateless PIR. They offer server runtime complexity of $\mathcal{O}(\sqrt{N})$ with communication complexity of $O(\log{N})$ but at the expense of client-dependent pre-processing stage that is of complexity $O(N)$. To compare stateful PIR schemes with stateless PIR schemes we may compare Piano [1] and SimplePIR [3]. For a database of size 2GB with 64 byte entries, Piano's server runtime is 9ms and total communication is 128Kb, whereas SimplePIR's runtime is 219.5ms and communication is 338Kb [1]. However in case of Piano each client needs to download the entire database (i.e. 2GB) in pre-processing step.

$O(N)$ server runtime without client dependent pre-processing for stateless PIR may sound fundamental. However, DEPIR[4] paper shows that it isn't. With server-side pre-processing that allows evaluating a polynomial of degree $d$ in time $\log{d}$, DEPIR achieves communication and server runtime of $O(\log{N})$. However, as shown in [2], DEPIR is still not practical for large databases. For example [2] shows that for a DB of roughly $2^{24}$ 2 byte entries, pre-processing and server-runtime take a fairly impractical amount of time (table 3 of [2]). If you are curious about the main bottleneck in DEPIR I will refer you to section 8 of [2].

4. PIR using trusted hardware: Trusted hardware offer less security over cryptographic based approaches. A secure PIR implementation inside trusted hardware requires ORAM. In practice, client encrypts their query such that it can only be decrypted inside the enclave. To retrieve necessary data corresponding to client's query, enclave stores the database in ORAM and reads data via ORAM thus hiding its access patterns from untrusted part. We may consider ORAM's overhead in general case to be $log^2(N)$ [5]. Trusted hardware based approaches offer much higher throughput than other PIR approaches without any overhead on client communication but at the expense of security. For further information on PIR inside trusted hardware used in the wild I will refer you to [Signal](https://signal.org/blog/contact-discovery/) and [MobileFog](https://mobilecoin.com/learn/fog) (Note that Signal's linear scan ORAM implementation is not optimal as noted in [5]).
5. PIR using multi-server PIR: Multi server PIR still offers cryptographic security with assumption of >= 2 non-colluding servers. State of the art multi-server PIR [6] has total communication of $(130(log N - 7) + b / (2^L - 1)) \cdot 2^L$ bits. Each of the $2^L$ servers evaluate $L(r/64)$ AES-128 evaluations and $rb / (2^L - 1)$ bit operations where the database has $N$ entries each of $b$ bits [6]. It is important to note that, in general, multi-server PIR are faster than single server PIR.

How feasible it is to use multiple non-colluding servers?
One might hesitate to deploy multi-server PIR due to non-collusion assumption, but there are ways to assure non-collusion
1. [More is merrier in collusion mitigation](https://arxiv.org/abs/2201.07740) shows a way to have achieve collusion mitigation in multi-server PIR setting using any public blockchain
2. To strengthen collusion mitigation, we may equip the servers with secure enclaves and assure that they are geographically distributed and not accessible easily. This can be achieved by using different cloud providers for each server in different geographic locations.

**Fuzzy message detection**

FMD [12] provides k-anonymity. It uses false-positives and hides real user transactions within a bigger set with the intention that doing so will make it hard to recover the transaction graph. The false positives are controlled via a parameter. FMD can be viewed like trial decryption but one can decrease the number of transactions to download via decreasing the false positive rate. For example, if there are $N$ transactions of which $n$ are for user and user has set false positive parameter to $p$. Then user needs to download $n + p (N - n)$ transactions [9]. This shows that there exist a trade off between efficiency and privacy. If the user wants to download less transactions they will have to reduce their false positive rate hence reducing privacy. To get high privacy the user must set a high false positive rate, hence moving towards trial decrypting most transactions.

Penumbra modifies FMD suitable for decentralised setting by (1) allowing the transaction sender to set the false positive rate (2) having consensus set false positive parameter [13]. (2) is done with the intention that if chain traffic is low then false positive rate can be increased to provide high anonymity set even with less transactions. If chain traffic is high then false positive can be reduced to maintain efficiency.

Since FMD provides k-anonymity, its privacy guarantees are less than other cryptographic based approaches [9]. Assuming sender and receiver do not hide behind TOR/mixnets, FMD does not provide sender-receiver unlink-ability. In case they do, the privacy guarantees are as good as of TOR/mixnets. For more information on attacks on FMD I will direct you to [9].

Based on information above and public implementations ([14],[15]) I will briefly summarise key points for FMD:
1. It does not solve the core issue of client side trial decryption.
2. Like OMR, and unlike tag based approaches, it does not require prior contact between sender and receiver.
3. Clue size is 64.5 bytes
4. Clue key size is 1.5 Kb
5. Detection key size is 768 bytes
6. It takes 0.2ms per transaction on server side
7. Like OMR, server needs to process each incoming transaction for each user.

**Should we have clues/tags?**

Notice that clues/tags only prevent clients from trial decryption. They don't necessarily help the server. For OMR, FMD, PSI, Single-server/ multi-server PIR, the server still has to process all transactions. The only exception is PIR inside trusted hardware where server's overhead is $\log^2{N}$ where $N$ is total transactions.

So let's look at how helpful clues/tags are for clients. For OMR total communication cost depends on no. of transactions client usually receives. For tag based approach, communication cost depends on the type of PSI/PIR scheme server employs. Since server-client communication is majority of communication in levelled HE PSI, the cost is sub-linear to $N$, $N$ being total no. of transactions. For levelled HE based PIR, communication cost can be generalised as $\log{N}$. LHE based PIR approaches have communication cost of $\sqrt{N}$. Multi-server based PIR has client-server communication of $130(log N - 7) \cdot 2^L$ bits and server-client $b/(2^L - 1) \cdot 2^L$ bits. This implies that multi-server PIR does not add a lot of overhead in communication compared to case where client uploads query to $2^L$ servers in plain and downloads corresponding response once. PIR based on trusted enclave have equivalent communication cost to the case where client requests data in plain (with some constant factor overhead on server-client communication to pad response to fixed size). With false parameter $p$ and no. of user transactions $n$, in FMD client downloads $n + (N-n)p$ transactions. Thus, for FMD, communication depends on $N$ and $p$.

All approaches, except FMD, effectively require negligible client side compute. In case of FMD, client side compute is equal to $n + (N - n)p$ elliptic curve operations (i.e. trial decrypting all transactions client downloads).

**Clue/tag incompatibility**

OMR clues aren't compatible with FMD clues. Tags are generic over all set of approaches that solve PSI/PIR.

**Are OMR and FMD worth it?**

OMR and FMD offer oblivious retrieval as their key property and are suitable when users cannot know each other. Using them under situations when users can share a secret and generate tags may not be the correct choice.

OMR can be eliminated on the basis that one pays too much for obliviousness. If tags can be assumed, then there are better solutions based on PIR offering vastly better performance with equivalent privacy guarantees.

Any correct PIR/PSI scheme breaks connection between sender and receiver (i.e. perfect server-receiver unlink-ability). So assuming server employs correct PIR scheme, tag based approaches provide complete privacy whereas FMD only provides k-anonymity privacy.

FMD is clearly worse than PIR/PSI in terms of communication, so it must compensate on the server-runtime. However, whether it is better on server side isn't clear at first sight. FMD is clearly better at server-runtime compared to single server PIR (ones using levelled HE/LHE). But it seems to be equivalent (or probably slightly worse) on server side when compared to multi-server PIR and worse when compared to trusted hardware based PIR.

Now the concern is how close is multi-server PIR and trusted hardware based PIR to an ideal PIR scheme. Multi-server PIR clearly is as long as servers don't collude and trusted hardware, due to long [range of attacks](https://sgx.fail/), clearly isn't. But assuming that both are far from ideally correct PIR (which isn't a valid assumption for multi-server PIR), can we somehow force them to provide k-anonymity. That is, as good privacy FMD provides. I think yes, by simply forcing client to make many erroneous queries.

**Are tags feasible in practice?**

Tags are an option only under assumption that users can share secret. So it is natural to ask how feasible it is for users to share secrets?

If two users know each other, then sharing secrets is easy:
1. They can meet in person, send a mail/message, meet over e2e video call, etc.
2. If they don't want to rely on old classical crypto they can use [lasers](https://www.mpg.de/9298509/W004_material-technology-060-067.pdf)

What if they don't know each other? I can think of following ways:
1. Sender sends the secret to the receiver encrypted using the receiver's Ethereum public key as a transaction on layer 1.
2. Can use FMD or OMR. But note that in this case we don't have to support them at protocol level.
3. Receiver can make their email public and the sender can send the secret over mail.

Moreover, since secret sharing does not need to be specified in protocol and secret shares will be vastly less than transactions, simple solution of trial decryption may work initially.

**Tags are generic + future proof**

Key benefits of tags are
1. **They can be of arbitrary bits.** If tags must be posted on layer 1, then we can reduce their size to anything of our choosing.
2. **They are generic over all possible PIR schemes**. Client may rely on any type of PIR scheme suitable to their efficiency and privacy trade off. If client wants complete privacy, they may use less efficient PIR based on levelled HE / LHE. If client wants high efficiency and are comfortable with collusion mitigation in-place for multiple servers then they may use multi-server PIR.

Since tags are generic over set of all possible ways to build PIR, they set us in best position to benefit from any advances in PIR literature in future (which will be likely).

## References
1. https://eprint.iacr.org/2023/452.pdf (Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation)
2. https://eprint.iacr.org/2023/1510.pdf (Towards Practical Doubly-Efficient Private Information Retrieval)
3. https://eprint.iacr.org/2022/949.pdf (One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval)
4. https://eprint.iacr.org/2022/1703.pdf (Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE)
5. https://eprint.iacr.org/2022/1083.pdf (ENIGMAP: External-Memory Oblivious Map for Secure Enclaves)
6. https://petsymposium.org/popets/2019/popets-2019-0061.pdf (A Bit More Than a Bit Is More Than a Bit Better)
7. https://eprint.iacr.org/2023/413.pdf (Accelerating HE Operations from Key Decomposition Technique)
8. https://eprint.iacr.org/2023/1304 (Homomorphic polynomial evaluation using Galois structure and applications to BFV bootstrapping)
9. https://arxiv.org/pdf/2109.06576.pdf (The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees?)
10. https://eprint.iacr.org/2022/368 (Spiral: Fast, High-Rate Single-Server PIR via FHE Composition)
11. https://eprint.iacr.org/2021/1081 (OnionPIR: Response Efficient Single-Server PIR)
12. https://eprint.iacr.org/2021/089 (Fuzzy Message Detection)
13. https://protocol.penumbra.zone/main/crypto/fmd/construction.html (Penumbra protocol spec)
14. https://git.openprivacy.ca/openprivacy/fuzzytags.git (Optimised Fuzzy message detection implementation)
15. https://eprint.iacr.org/2021/1256.pdf (Oblivious message retrieval)