6 ms·

What kind of things are impossible?

lewisl9029 11y ago
The two features I mentioned, automatic contact discovery and robust offline messaging, are examples of features that I have concluded to be impossible to build without some degree of centralization (there are probably more, but those two were the only ones I could recall off the top of my head). Though it is certainly possible that I simply haven't put enough thought into it. Toc's original goal was to be a decentralized messaging app that makes no compromises in terms of UX compared to a centralized messaging app. Toc managed to tackle decentralized cross platform sync, but to this day I still have no idea how to approach automatic contact discovery and robust offline messaging.
- qrmn 11y ago
  Automatic contact discovery is tricky, but the beginnings of one potential solution is I think explored in agl's Pond, using pairings on BN curves?: https://pond.imperialviolet.org/ https://pond.imperialviolet.org/ To a point, so is offline messaging. Distributed datastores in general do that kind of thing - there are old implementations over Freenet in particular, and GNUnet as well and other things I think. The robust part is harder: if the client is offline, where's the disk space coming from? Volunteers' (nodes') cache? That needs to be opaque, and so do lookups. What's to stop spammers flooding the network? (Spam, and denial-of-service in general, is a Hard problem to deal with in general even in distributed systems.) They're not among the hardest problems. Pseudonymity is a huge challenge as the latency gets lower against traffic correlation attacks, and a secure messenger is most definitely up against the kind of threat model that can and will try to pull those off in the wild. Perhaps mixing high and low-latency traffic may help, although it's going to need to be very carefully analysed how much (I believe I2P's design can do that, although I'm not sure if jrand0m ever implemented it in the router).
  - lewisl9029 11y ago
    Yes those are definitely not the hardest problems in this space. I was only referring to UX-related features in my original post (i.e. rather than the much more tricky privacy and security related ones), ones that I couldn't figure out how to actually implement in the context of a client-side web app. Impossible was probably too strong of a word to express that. Thank you for all the interesting ideas and resources though! They'll definitely come in handy when I eventually revisit this space when I have more time later on.
qrmn 11y ago
Impossible is a strong word - one prefers to reserve that for provably doomed problems like DRM - but several common, simple paradigms do present an unexpected technical challenge, or even an open research problem, or need to be expressed slightly differently to be practical, in a distributed, privacy-preserving, untrusted-server kind of model. For example, paraphrasing quite a lot - uniqueness of names requires ordering; ordering probably requires consensus; consensus has a Sybil problem for which some kind of countermeasure is needed. So a namespacing problem that seems simple, and is simple in a centralised/trusted context, may only be practical to solve with a blockchain-like structure with a computationally-heavy proof-of-work in a distributed trust architecture. Even that may still be vulnerable to attacks from someone who can outcompute the rest of the network: and a Nation State Adversary (as a friend snarkily puts it) may actually have enough budget to try that. There may be another way, but maybe not another way that satisfies all the security requirements or that would survive an attack. And there are still other niches you need to worry about, like homoglyph attacks. That's a long way to go just to make sure that there aren't two ~bobs! So you end up thinking, maybe it's better to find another way that ~alice knows she's talking to the right ~bob? Then you have rephrased your security problem as more of a UX problem: how do I try to avoid impersonation? - which is perhaps more practical to solve another way. [Edit: Also, now your users won't have to fight over who gets to take ~bob first. This may or may not be an advantage, depending on how you feel about username exclusivity.] It's going to require a lot of hard work to solve this type of problem comprehensively; in the meantime, Signal does more or less the best we can do practically right now, and there's a lot of value in a practical solution that's best-in-class, works and millions of people can just pick up and use now.

The two features I mentioned, automatic contact discovery and robust offline messaging, are examples of features that I have concluded to be impossible to build without some degree of centralization (there are probably more, but those two were the only ones I could recall off the top of my head). Though it is certainly possible that I simply haven't put enough thought into it. Toc's original goal was to be a decentralized messaging app that makes no compromises in terms of UX compared to a centralized messaging app. Toc managed to tackle decentralized cross platform sync, but to this day I still have no idea how to approach automatic contact discovery and robust offline messaging.

qrmn 11y ago
Automatic contact discovery is tricky, but the beginnings of one potential solution is I think explored in agl's Pond, using pairings on BN curves?: https://pond.imperialviolet.org/ https://pond.imperialviolet.org/ To a point, so is offline messaging. Distributed datastores in general do that kind of thing - there are old implementations over Freenet in particular, and GNUnet as well and other things I think. The robust part is harder: if the client is offline, where's the disk space coming from? Volunteers' (nodes') cache? That needs to be opaque, and so do lookups. What's to stop spammers flooding the network? (Spam, and denial-of-service in general, is a Hard problem to deal with in general even in distributed systems.) They're not among the hardest problems. Pseudonymity is a huge challenge as the latency gets lower against traffic correlation attacks, and a secure messenger is most definitely up against the kind of threat model that can and will try to pull those off in the wild. Perhaps mixing high and low-latency traffic may help, although it's going to need to be very carefully analysed how much (I believe I2P's design can do that, although I'm not sure if jrand0m ever implemented it in the router).
- lewisl9029 11y ago
  Yes those are definitely not the hardest problems in this space. I was only referring to UX-related features in my original post (i.e. rather than the much more tricky privacy and security related ones), ones that I couldn't figure out how to actually implement in the context of a client-side web app. Impossible was probably too strong of a word to express that. Thank you for all the interesting ideas and resources though! They'll definitely come in handy when I eventually revisit this space when I have more time later on.

qrmn 11y ago

Impossible is a strong word - one prefers to reserve that for provably doomed problems like DRM - but several common, simple paradigms do present an unexpected technical challenge, or even an open research problem, or need to be expressed slightly differently to be practical, in a distributed, privacy-preserving, untrusted-server kind of model. For example, paraphrasing quite a lot - uniqueness of names requires ordering; ordering probably requires consensus; consensus has a Sybil problem for which some kind of countermeasure is needed. So a namespacing problem that seems simple, and is simple in a centralised/trusted context, may only be practical to solve with a blockchain-like structure with a computationally-heavy proof-of-work in a distributed trust architecture. Even that may still be vulnerable to attacks from someone who can outcompute the rest of the network: and a Nation State Adversary (as a friend snarkily puts it) may actually have enough budget to try that. There may be another way, but maybe not another way that satisfies all the security requirements or that would survive an attack. And there are still other niches you need to worry about, like homoglyph attacks. That's a long way to go just to make sure that there aren't two ~bobs! So you end up thinking, maybe it's better to find another way that ~alice knows she's talking to the right ~bob? Then you have rephrased your security problem as more of a UX problem: how do I try to avoid impersonation? - which is perhaps more practical to solve another way. [Edit: Also, now your users won't have to fight over who gets to take ~bob first. This may or may not be an advantage, depending on how you feel about username exclusivity.] It's going to require a lot of hard work to solve this type of problem comprehensively; in the meantime, Signal does more or less the best we can do practically right now, and there's a lot of value in a practical solution that's best-in-class, works and millions of people can just pick up and use now.