[dave_universetf]

IPv6 by and large solves the NAT problem per se, but doesn't solve the stateful firewall traversal problem. Fortunately that one is _much_ simpler, especially now that we have QUIC as a robust stream protocol over UDP. IPv6 also introduces complexity while IPv4 is still around, because you have to detect and handle NAT64 in order to get a v6-only node (with NAT64) and a v4-only node talking to each other.

Completely solving NAT... I've tried a couple of times over the last 10 years, bunch of false starts. You can see one of the older attempts at https://github.com/danderson/nat (don't use it, it's very basic and fails at a lot of NATs). One of the tricky parts is that to make it work right, you really need control of the wire protocol you're using, because you have to inject frames and do all kinds of weird things to help with the NAT part, while ignoring all that noise at the "upper protocol" layer. You can make it generic with some careful layering, but it turns a simple API into a complicated one.

You absolutely need a coordination server for NAT traversal to work. That's unfortunately one of the great unsolved problems for fully decentralized p2p. But it can be _any_ low-bandwidth channel you have available (one of my first implementations piggybacked over XMPP messages), and it doesn't have to be a trusted part of the system (although making it trusted simplifies a ton of stuff). And you also need some kind of data plane relay (like DERP) for when NAT traversal fails, which still happens a fair bit. Without that extra layer of relaying, you'll only ever hit 95-99% connectivity, not 100%.

I'm (slowly) writing an article on NAT traversal that covers all this. It's a thorny problem, and I'd love to solve it once and for all (which is sort-of why I work at Tailscale - I think I have a shot of solving it once and for all at the IP layer, so that all the other layers can just stop caring)