While it is true that encryption will be involved, it is not the hard problem, I think that's a bit like saying nails will be used to construct a building. The hard problems are how to get a packet of data from here to there without a central mediator (solvable with current tech but can have performance issues), and how to create a human-usable naming service of some kind that doesn't have a central mediator and doesn't inevitably degenerate back into having a central mediator by its very nature. Technically DNS is decentralized but the way it works causes it to centralize naturally. I'm not sure if this is avoidable.
Alas, such discriminatory routing by per-packet payments and reputation is probably illegal under the FCC's recently asserted 'neutrality' regulations.
Strictly speaking there's no need for a DNS-like system to use domain _names_ - you could use domain keys instead (locating the authoritative servers could then be done with a DHT of some sort). The problem then is that it becomes hard to type them in manually, but people could exchange such things with QR codes, or abbreviated hashes of the keys. You do lose usability, but it's a compromise that wouldn't be entirely unusable.
And you'd have to solve the issues of deliberately corrupting DHT nodes, deliberately constructed collisions, and forged copies of the whatever-human-key ends up being used, since it is pretty much out of the question that we will all type in 128-bit numbers for website access.
Note I do not mean this as criticism of your comment, because you can't possibly solve these issues in an HN comment. Just pointing it out. Designing a decentralized network that works at all is a big enough challenge, designing a fully decentralized network that stands up to hostile attacks by intelligent adversaries is even harder.
