ULPSI stands for Unbalanced labelled private set intersection, but is somewhat of a misnomer for what the repository implements. Really what it implements is Unbalanced labelled private set intersection with the caveat that only the client’s set stays private, not the server’s set.
I stumbled upon ULPSI when trying to solve the problem of transaction retrieval on privacy preserving chains. After experimenting with Oblivious message retrieval we realised that it couldn’t scale to many users nor its performance could be improved further on CPUs. Although, I still think OMR implementation on GPU can give desired latency between the sender publishing the transaction and the user receiving it, there will be high costs for running such a server and there’s no clear path to funding them. Moving on, we reduced the difficulty of the problem. Instead of trying to figure out a way for users to find their transactions without any previous information, we asked how users can retrieve their transactions privately given that they share a secret with the sender (Don’t ask how they will share the secret in the first place. I have no clue).
For example, assume that Alice and Bob share a secret and keep track of a nonce between them. To send a transaction to Bob, Alice tags the transaction with the hash of shared secret and latest nonce value. To retrieve the transaction Bob optimistically searches for tags corresponding to the next couple of nonces in sequence. Bob then increments the nonce to +1 of the nonce that returned a transaction, thus setting the value as the latest nonce for future transactions.
The non-trivial part is finding that the tag exists and subsequently retrieving the transaction privately. Thinking of the server as having a set of all tags and corresponding transactions and the client set as all optimistic tags that the client generates using shared secrets of all of its known contacts, the client needs to retrieve transactions corresponding to tags that sit in intersection of client’s set and server’s set without leaking any information. This hints that we can structure the problem as a private set intersection with additional requirement of returning the label (i.e. transaction) corresponding to intersecting values. Since there will be many transactions, another key requirement is that the implementation must be efficient in an unbalanced case where the client’s set is way smaller than the server’s set.
To simplify the problem further, we can take advantage of the fact that transactions can be split into multiple field elements each of size 256 bits. For example, a typical transaction on Aztec may have 16 encrypted notes, where each note is a field element of size 256 bits. Now we can assign tags to each field element (we don’t actually need to assign a new tag to each field element. Instead, we can derive tags for each field element from the tag of transaction). Thus the problem is now reduced to enabling clients to retrieve field elements of size 256 bits corresponding to tags (of size 256 bits as well) that are in intersection of client’s set and server’s set with the constraint that protocol remains efficient even when client’s set is way smaller than server’s set.
After searching through PSI literature for a while, I came across APSI that implements private set intersection using levelled HE (homomorphic encryption). Even though HE isn’t required for PSI, apparently the only known efficient way to construct asymmetric (i.e. unbalanced) private set intersection is using HE. Another nice thing about APSI is that (as outlined in paper) it can easily be extended to return the labels corresponding to tags at intersection.
I implemented a slightly simplified version of APSI protocol with the difference being that the server’s set is assumed to be public. For the curious, a brief description of implementation lives here. Even though the implementation is quite flexible with the size of tags and corresponding labels, I am mostly concerned with tags and label sizes of 256 bits. Since I had somewhat arbitrarily assumed a maximum client set size of 4096, I set the parameters that have optimal server runtime when that is the case. I benchmarked client upload cost (ie client-server communication), client download cost (ie server-client communication), and server runtime for client set size 4096 with multiple server set sizes - 10M, 16M, 100M, 200M, 300M, 500M.
| Client set size | Server set size | Item size (bits) | Label size (bits) | Client upload cost (MB) | Client download cost (MB) | Server runtime (ms) |
|---|---|---|---|---|---|---|
| 4000 | 10M | 256 | 256 | 21 | 11.6 | 4798 |
| 4000 | 16M | 256 | 256 | 21 | 14.1 | 5906 |
| 4000 | 100M | 256 | 256 | 21 | 51.2 | 18881 |
| 4000 | 200M | 256 | 256 | 21 | 94.6 | 33976 |
| 4000 | 300M | 256 | 256 | 21 | 138.512 | 49806 |
| 4000 | 500M | 256 | 256 | 21 | 227 | 80676 |
Benchmarks were performed on x2idn.16xlarge which is equipped with 64 vcpus (i.e. 32 cores)
Not surprisingly, server runtime and client download cost increases linearly with server set size.
When others started to poke me with questions of how it varies across different client set sizes, I realised I had been a bit lazy before. So with a bit of procrastination (preprocessing millions of values takes a lot of time) I ran the benchmarks again for following client set sizes, 512, 1024, 2048. I spent some time trying to find optimal parameters for various client set sizes I intended to benchmark. But realising it was taking too long and I couldn't detect clear patterns, I gave up. So I ended up using the same parameters as I had used for client set size 4096.
| Client set size | Server set size | Item size (bits) | Label size (bits) | Client upload cost (MB) | Client download cost (MB) | Server runtime (ms) |
|---|---|---|---|---|---|---|
| 512 | 10M | 256 | 256 | 2.55 | 5.27 | 2566 |
| 512 | 100M | 256 | 256 | 2.55 | 44.83 | 16873 |
| 512 | 300M | 256 | 256 | 2.55 | 132.74 | 48922 |
| Client set size | Server set size | Item size (bits) | Label size (bits) | Client upload cost (MB) | Client download cost (MB) | Server runtime (ms) |
|---|---|---|---|---|---|---|
| 1024 | 10M | 256 | 256 | 5.10 | 6.05 | 2897 |
| 1024 | 100M | 256 | 256 | 5.10 | 45.71 | 17450 |
| 1024 | 300M | 256 | 256 | 5.10 | 133.62 | 49256 |
| Client set size | Server set size | Item size (bits) | Label size (bits) | Client upload cost (MB) | Client download cost (MB) | Server runtime (ms) |
|---|---|---|---|---|---|---|
| 2048 | 10M | 256 | 256 | 10.19 | 8.20 | 3764 |
| 2048 | 100M | 256 | 256 | 10.19 | 47.27 | 17717 |
| 2048 | 100M | 256 | 256 | 10.19 | 135.28 | 49617 |
As expected client download cost and server runtime increases with server set size in all 3 tables. But notice the odd behaviour when server set size is 10M. Across different client set sizes, with server set size 10M client download cost and server runtime increases, which isn’t the case with server set sizes 100M and 300M.
A quick observation is that client upload cost increases linearly with client set size as expected. But there’s something odd here. For a relatively small server set size, 10M, client download cost and server runtime increases linearly across different client set sizes. But the effect apparently diminishes with server set size 100M and completely disappears with server set size 300M. This also invalidates, for small server set sizes, my hypothesis (quite straightforward to reason) that both client download cost and server runtime depend on server set size and wouldn’t change much across different client sizes.
I had missed something obvious before, that with bigger client set sizes the server is forced to insert elements in a database with greater no. of rows. Moreover, database columns are inserted in sets of fixed size. For example, in implementation the columns increase in sets of 1305. So you can only have 1305, 1305 x 2, 1305 x 3 columns, so on and so forth and not 1, 2, 3… columns. For relatively smaller databases, with high client set size, the server isn’t able to tightly pack items in columns of the database. This causes client download and server runtime to get worse as client set size increases. This is confirmed by the absence of this effect when server set size is 300M, where server is able to pack elements in columns very tightly.
One way to avoid client download and server runtime to get worse as client set size increases on smaller server set sizes is by reducing the fixed set size of columns (i.e. reducing 1305!). This is what I meant before by not choosing optimal parameters suitable for different client set sizes. However, I think that even if I were to set optimal parameters for each client set size it will only improve server’s runtime but will have negligible effect on client’s download cost. This is because we can reduce the fixed size of set of columns which will decrease server’s runtime but we cannot reduce no. of rows which depends on the client’s set size.