Topic: Idea: XPIR for more private lightweight nodes (Read 995 times)

This is a list of PIR implementations that includes other schemes besides XPIR and the schemes Percy++ supports.

https://en.wikipedia.org/wiki/Private_information_retrieval


Popcorn is a modified version of Percy++. Unfortunately I haven't found a download for it yet. However page 7 of its paper states RAID-PIR has similar speeds to Percy++. Regrettably the RAID-PIR github hasn't been updated in two years, and the upPIR site's code hasn't been updated in 4 years.

http://www.cs.utexas.edu/~trinabh/papers/popcorn-PIR-nsdi16.pdf


Page 13 lists other PIR implementations prior to popcorn.  


Unfortunately popcorn's privacy guarantee can be compromised by state-level adversaries using colluding organisations to serve objects.


These are a few other links to popcorn information.

http://keylorch.github.io/cs616-paper-presentation/#/23

https://github.com/keylorch/cs616-paper-presentation/blob/master/example/itpir.py

https://blog.acolyer.org/2016/04/01/scalable-and-private-media-consumption-with-popcorn/


Another PIR scheme implementation is the Apache Pirk framework.

https://pirk.incubator.apache.org/


It was initiated by the NSA and given to Apache in July 2016.

https://pirk.incubator.apache.org/pirk_origin


http://events.linuxfoundation.org/sites/events/files/slides/ApachePirk-ApacheConEurope-20161115.pdf

I haven't had time to study whether XPIR or Percy++ rely on "key switching", but last August some cryptographers released a paper identifying weaknesses in a homomorphic encryption scheme by Zhou and Wornell. The paper explains how the encryption scheme relies on "key switching" and demonstrates three attacks on it.

The paper makes some assumptions that the exploits rely on, and they might not be relevant to XPIR or Percy++ even if those encryption schemes rely on "key switching".

The paper's abstract is here.

http://eprint.iacr.org/2016/775

The paper is here.

http://eprint.iacr.org/2016/775.pdf

These are the exploits and the assumptions made.

Percy++ can do single server... though it's much slower than the multi-server mode.  I think it may be using the same kind of crypto as xpir for the the single server... not sure which of the two is faster. (I wasn't aware of xpir before your message.)

All of this stuff is super slow, but fast enough to be usable. It just needs a lot of glue work.


With respect to the multiserver assumption-- well if due to performance reasons your options are multi-server OR no PIR-- the multiserver is still better than nothing. It also has the advantage that no crypto break could ever compromise your privacy, where the single server PIR has the unfortunate property that if the server logs your queries and then later it's discovered the crypto was weak, your privacy could be lost.

I also think Percy++ can combine the two. E.g. multiserver, but if they cooperate then you're still protected but I could be misremembering. The elaborations are kind of moot when AFAIK no one uses PIR for anything anywhere.

I looked at percy++, but it wasn't immediately clear to me what version of single-server, computation PIR it was using. XPIR had a nice paper that I could read. percy++ could be better, I don't know. Though it seems to be focusing mainly on the version of PIR where multiple servers are involved and assumed to be non-cooperating, which I feel is an assumption that's too difficult to ensure in practice for this situation.


Perfect! I was thinking that an RPC method like that was exactly what was needed. Non-PIR services to provide that data will also be useful in the near future -- loss of rescan was a huge downside to pruning.


Cool!


It does seem to have constant size, but it doesn't seem that the size affects efficiency much. The entries also seem to be streamed to clients in order, since the XPIR paper talks about streaming video. So if a record is 10MB composed of 250kB followed by 9.75MB of zeroes, the client could stop reading at some random point after receiving their 250kB.

If that doesn't work, another thing that occurred to me is that you could have lists of txids, and then another PIR database for fetching transactions. Or even just the simple piece of data that all of the address's transactions appear between blocks x and y, which the client could then go download elsewhere. Perhaps the database could degrade through all three of these possibilities depending on how much transaction data there is.

I'm glad this stuff is on your mind!

Search bitcoin-wizards logs for percy++  which is another PIR library; there have been some similar proposals to yours.

We added functionality in the Bitcoin Core RPC 'importprunedfunds' that could be used to import transaction data retrieved from this kind of PIR scanning service. I was thinking very much along the same lines as you with a free queue and then the ability to use blind tokens to add priority to entries in the queue.


It's possible to avoid downloading that initial index:

Create that index.

now build a binary tree over it e.g.   the rood node says [go left for <= 1WWWW..., right for the rest]
then the next layer down has [go left for <= 1FFFFF..., right for rest] [go left for <= 1kkkkkk... right for rest]
then the later below that would have four entries and so on..

each row of the tree in a separate database... then you just make multiple queries with the PIR hiding which of the nodes you are reading..
until you get to the bottom layer and know what index your spk is at.

In practice sending the whole index is probably fine.


I'm not sure if XPIR does something special here, but normally all the results have to be the same size.. so the fact that there are wildly different numbers of transactions connected to addresses has to have something done about it.

Currently, all lightweight nodes have to more-or-less give a list of all of their addresses to someone else in order to find their incoming and outgoing transactions. This totally destroys their privacy because it connects all of their addresses together, even if they're behind Tor. Some wallets try to obfuscate this with bloom filters, but research has shown that this isn't all that effective at maintaining privacy. Bitcoin Core avoids this problem by downloading the entire block chain, but this uses a lot of bandwidth, and if you don't store the entire block chain, you have to download everything again if you want to rescan.

I found that there is a (beta) library called XPIR which may be able to improve this. It uses homomorphic encryption to allow for a server to have a database which clients can query, but without the server or any listeners knowing which entries in the database the client is querying/receiving. So clients could ask the server (encrypted), "please give me all transactions associated with address ____", and the server would be able to provide this data without knowing anything about the client's query. This would significantly improve privacy.

Running a server will be pretty resource-intensive, so this isn't something that every full node is going to be doing. However, it would be appropriate for Electrum servers, sites like GreenAddress, etc.

I haven't actually tried the software, but looking at the paper, here's how I think it'd work on a technical level:

 - The database to be queried must be structured as index -> value, where indices must be sequential integers starting at 0, and clients can only query for specific indices. So the first step is for the server to publish a mapping between all possible scriptPubKey queries and their indicies. This can be done by hashing each scriptPubKey seen in the block chain (maybe with wildcards to handle cases like stealth addresses), sorting the hashes, and giving each one a sequential index. All clients need to download this initial mapping. If the hash is 128 bits and the index is 64 bits (both of these could maybe be shortened), currently the mapping would be around 10.3 MB with today's 429k unique addresses. Everyone gets the same mapping, so there's no need to download it in any special anonymous way.
 - The efficiency of the database goes down with the number of entries. Here, "entries" is the number of possible scriptPubKey queries. So each server should actually have several XPIR databases, each of which will contain perhaps around 100,000 possible scriptPubKeys. Info about which scriptPubKey ranges belong to which database will also have to be downloaded by clients, but this is a negligible amount of data. Each database needs to start its indices at 0, so the client will have to adjust the global index down according to which database it's querying. Segregating the scriptPubKeys like this allows the server to know that the client has some address in that range, but there are enough addresses to make this not-very-useful. The client could also send dummy queries to disrupt even this.
 - The client would just send one query for every address in its wallet. For each one, they'd get all of the address's transactions along with its merkle branch linking it to the block chain. From page 14 of the XPIR paper, it looks like you can very roughly expect to download your transaction data at 12.5 kB/s, with a latency between first query and initial transaction data of 10-500 seconds depending mainly on the client's upload speed. These speeds seem OK.
- If clients are only interested in addresses that currently have BTC, you can significantly reduce the size of the database, and therefore increase efficiency. Similarly, the database size can be reduced for clients that have been online for a while and are therefore only interested in new/recent blocks.
 - I'm not sure how many clients a reasonable server could comfortably handle. If it's not very many, then servers might need to charge for this. Maybe they could have a free queue, and then the possibility of paying to jump the queue. They could use blinded tokens to accept micropayments anonymously. The current XPIR library seems not to be very optimized, especially for multiple simultaneous clients, so performance improvements are probably possible.

Thoughts?