That's the idea.

> How are NAT entries recycled?

DNS responses have a TTL. The mappings last at least as long as the TTL and get extended if any traffic is sent to the address or there is another name lookup. After there is no traffic for a period of time the address goes back into the pool.

> Also couldn't SNI be used here to do this via a single IP?

SNI is HTTP. Doing it this way works with other protocols too.

I can't think of a way to make this compatible with the DNS method you're using now though... you'd need a new address class that only ever returns a fixed IP by DNS, which was used exclusively for alternative determinations of the .key name requested. You could do this for TCP/80 with the HTTP Host header and TCP/443 with SNI, for instance. I'm wondering if one way to do it would be with haproxy to avoid having to implement this yourself.

Since a lot of connections going over Snow are going to be HTTP or HTTPS, this might make sense, at least for IPv4 where you IP space is limited.

The way Tor does it is to use a SOCKS proxy. Then you don't need an IP address and it's protocol-agnostic but the client application has to support SOCKS.

I'm not sure address space limitations are even a major problem. Address assignments are local, not global, and there are millions of RFC1918 addresses.

For HTTP you have to solve it from the other side anyway. An HTTP server would be more likely to run out of addresses than a client would. But running out of IPv4 addresses is what IPv6 is for. We could even return both IPv4 and IPv6 addresses until the IPv4 addresses run out. Then if you want to burn through millions of peers you just have to support IPv6.