4 ms·
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 a
by sigil 13y ago
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.
- mtrimpe 13y agoIndeed; 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.
- moxie 13y agoOur 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.
- josephlord 13y agoCould 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.
- deleted 13y ago[deleted]
- sigil 13y agoSo 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?
- streetnigga 13y ago"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.
- mtrimpe 13y agoAren'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?
- streetnigga 13y agoMy original device was what you may call an edge case. Underpowered, lack of space, pretty crappy carrier plan. Thanks for thinking of us. :)