It's only partially open source. Some server-side code remains proprietary, and the client-side will depend on proprietary code of Google and Apple and they do not plan to support platforms that are actually Free Software. The law overall is badly written. For example, articles 12 and 26 effectively say that "The source is shared with public, except if it is proprietary or insecure." Or take Article 4: "The government may operate systems that protect the privacy of the identity subjects."
On this Internet if you don't trust third parties to route all of your traffic through and peers are behind NAT or CGNATs. Or imagine a mixed network with some peers on https://en.wikipedia.org/wiki/Wireless_ad_hoc_network (s), possibly with some connected to the Internet. The key assumption we have (for the random walk to work) is that it must be a small-world network (https://en.wikipedia.org/wiki/Small-world_network) and network topologies surprisingly often are.
Yes, the random walk relates to the "NAT problem". Basically, due to NAT, peers may not succeed when trying to connect to arbitrary other peers (especially if you assume no TURN servers or other infrastructure to facilitate). The same situation may also arise in mobile ad-hoc networks, where your wireless signals simply don't get everywhere. As a result, the usual greedy routing will get stuck in a local minimal. By prefixing the greedy routing with a random walk, you basically randomize the starting position, and then end up at a random local minima. Replicate at enough local minima (O(sqrt(n)) and do enough (O(sqrt(n)) lookups and the birthday paradox will make it increasingly likely for you to succeed. Without the random walk, both the putter and the getter would greedily route always to their local minimum, and if they differ, never find each other's data.