Hacker News Reader

Comment by sigil | Hacker News Reader

Interesting problem!

> It’s also possible to compress “updates” to the bloom filter. The server just needs to calculate the XOR of the version the client has and the updated version, then run that through LZMA (the input will be mostly zeros), and transmit the compressed diff to the client.

> Unfortunately, for a reasonably large user base, this strategy doesn’t work because the bloom filters themselves are too large to transmit to mobile clients. For 10 million TextSecure users, a bloom filter like this would be ~40MB, requested from the server 116 times a second if every client refreshes it once a day.

Wait, the LZMA-compressed daily diffs would be still be ~40MB? If the 40MB is just the initial bloom filter download, that's not so bad. If 40MB is the daily diff, I'd be interested in seeing the calculation for that.

View on HN

Our feeling is that 40MB for an initial download is not acceptable on mobile devices, particularly in many of the areas we'd like to support. Maybe we're wrong, but it seems like too much on edge networks, particularly given that it's only going to grow as more users join. Ideally we'd have 100MM or 500MM, not just 10MM.

We can definitely make lightweight diffs happen, but that initial download is tough, and is going to get tougher.

Could that mode be optional? Give the user the option protecting their contacts privacy at the cost of the large download or to trust your servers to delete the unmatched contacts.

So make contact discovery optional. My guess is most of your growth will come from that core of early adopters in the graph, and these folks have nice data plans / fast wifi and won't mind the 40MB download at all.

In the long term, where you're 10x or 50x where you are today, yes the filter size is a problem, but it's a "nice problem to have" as they say.

Side question: suppose I'm a less fortunate user of TextSecure, can I manually exchange keys with someone IRL? How does that work?

"My guess is most of your growth will come from that core of early adopters in the graph, and these folks have nice data plans / fast wifi and won't mind the 40MB download at all."

See my comment in this thread about low resource mobiles, or the article on BZR being overtaken by Github and complaints about resource use from low memory laptop users. Please don't assume technological knowledge or early adoption means plentiful resources from the user.

Aren't you essentially just offering the users to download as much data as they want to reduce the probability of 'collateral uploads' to levels that are acceptable for them?

My original device was what you may call an edge case. Underpowered, lack of space, pretty crappy carrier plan.

Thanks for thinking of us. :)

Ideas

1) Bundle a snapshot of the global contact list with the APK. Assume that end users will be on 3G or WI-FI when installing the program. I suppose that is is worth looking at the assumption about what is the largest download that we can live with under EDGE. The current TextSecure APK is 2.5MB as far as I can tell. The best case for the APK download is 1.4 minutes (236kbit/s). If the size is essentially zero, then we need to move to idea 2.

2) Split the rate-limiter into an anonymous proxy controlled by a partially trusted third party. Open Whisper Systems controls the database, but not the proxy. Open Whisper Systems doesn't know where the request comes from. The rate limiter doesn't know what is requested.

Edit: forgot to complete a sentence

Indeed; if I understand it correctly encrypted data goes into a standard bloom filter.

If that's indeed the case then, assuming that users can never be removed, a daily update would just contain the indexes of the additional bits set by the newly registered users, which could never be 40MB.

It seems they also forgot to include lowering the p-value of the bloom filter as a trade-off, since it seems that a false positive means that a contact is sent to the server which shouldn't have been.

If you push that down to p=.95/.98/.99 or so you'd get a much smaller Bloom filter and many people might not object to a few % of 'collateral uploads' so to speak.

Minimizing the amount of information leaked through these various tradeoffs is an interesting problem though, since you'll have to leak something one way or the other.

Reply on news.ycombinator.com