If both parties are behind a NAT, you need a STUN server to help set up UDP hole punching. STUN servers are cheap to run, as it is a stateless UDP protocol. I imagine a single server could handle tens of millions of concurrent users, or more if the STUN client is not aggressive.
There are enough public STUN servers that I think an open source project could ship with a big list of them and it'd be functional. (The two peers don't need to be using the same STUN server.)
There is also pwnat, which uses a neat trick to connect two parties behind a NAT without a third server necessary.
> If there was an open-source library that managed this well I have a feeling it would be used everywhere.
Check out telehash.org for one attempt to make a p2p overlay of the regular Internet as an open source library.
ZeroTier, as mentioned in the link, has all the code necessary to also provide a p2p library. (It's p2p VPN software right now, but I imagine someone could separate out the guts if that hasn't been done already.)
That's correct. How would you use Tor to initiate the NAT traversal only, and then go direct? Perhaps using it as a way to advertise ports bound upstream from local NAT?
It would be interesting if somehow Tor could be used only to initiate the NAT traversal, then the direct connection could be used with better performance. (This article feels like it's talking about routing everything through Tor.) If there was an open-source library that managed this well I have a feeling it would be used everywhere.