This proposal has been around for the longest time, but it’s living inside this go-libp2p issue: libp2p/go-libp2p#1480 (comment).
Writing this up here now, so we have all the protocol improvements in one place.

Protocol Description

Compared to AutoNAT v1, AutoNAT v2 should provide the following features:

1. It should be a protocol to test the reachability of particular addresses (not list of addresses). This allows nodes to use AutoNAT to test address candidates (derived from different sources, e.g. Identify, circuit addresses etc.) for their reachability. The idea is to enable building of an address pipeline, where address candidates can go from “suspected” to “confirmed” listen address (with occasional re-confirmations of already confirmed addresses).
2. It makes it more difficult to lie to us. Now this only works in one direction: we can have a node prove that a connection attempt succeeded. The other direction isn’t provable: a node can always claim that it tried to dial us, but that dialing failed. This can be achieved by asking the node to provide a certain identifier (random string / number), and then wait for an incoming connection (on the right transport, we won’t be able to distinguish between different addresses on the same transport) where this identifier has to be presented.

(2) definitely is a breaking a protocol change, and (1) in practice is as well, because old go-libp2p versions would return a DIAL_FAILED instead of a DIAL_REFUSED error if a transport was unsupported.

Rollout Strategy

AutoNAT v2 is only useful if a sufficient number of nodes support the protocol. During a transition period, nodes will need to support both versions (at least on the client side). Once a large enough fraction of the network (20%? tbd) supports AutoNAT v2, we can start disabling support for v1.