NAT-Traversal Testing with testnet.polykey.io

[CMCDragonkai]

Specification

To automatically test for NAT-busting is a bit complex, you need to simulate the existence of multiple machines, and then simulate full-cone nat, restricted cone nat and then symmetric nat.

Since we don't have a relay proxy enabled yet, symmetric NATs is going to be left out for now. So we'll focus on all the NAT architectures except for symmetric NAT.

Additional context

Actually I don't think we should bother with QEMU or NixOS here. It's too complicated. QEMU might be good choice for being able to run the test cross-platform, but lacking expertise on QEMU here (I've already worked on it with respect to netboot work), and more experience with network namespaces should mean we can do this tests on just Linux. NixOS limits our environment even more and requires running in a NixOS environment.

Note that network namespaces with Linux stateful firewalls should be perfectly capable of simulating a port-restricted firewall.

Old context follows...

The best way to do this is with VM system using QEMU.

NixOS has a multi-machine testing system that can be used to do this, however such tests can only run on NixOS: https://nixos.org/manual/nixos/unstable/index.html#sec-nixos-tests We have pre-existing code for this:

NixOS NAT Module Test

# here is the testing base file: https://github.com/NixOS/nixpkgs/blob/master/nixos/lib/testing-python.nix
with import ../../pkgs.nix {};
let
  pk = (callPackage ../../nix/default.nix {}).package;
in
  import <nixpkgs/nixos/tests/make-test-python.nix> {
    nodes =
      {
        privateNode1 =
          { nodes, pkgs, ... }:
          {
            virtualisation.vlans = [ 1 ];
            environment.variables = {
              PK_PATH = "$HOME/polykey";
            };
            environment.systemPackages = [ pk pkgs.tcpdump ];
            networking.firewall.enable = false;
            networking.defaultGateway = (pkgs.lib.head nodes.router1.config.networking.interfaces.eth1.ipv4.addresses).address;
          };
        privateNode2 =
          { nodes, pkgs, ... }:
          {
            virtualisation.vlans = [ 2 ];
            environment.variables = {
              PK_PATH = "$HOME/polykey";
            };
            environment.systemPackages = [ pk pkgs.tcpdump ];
            networking.firewall.enable = false;
            networking.defaultGateway = (pkgs.lib.head nodes.router2.config.networking.interfaces.eth1.ipv4.addresses).address;
          };
        router1 =
          { pkgs, ... }:
          {
            virtualisation.vlans = [ 1 3 ];
            environment.systemPackages = [ pkgs.tcpdump ];
            networking.firewall.enable = false;
            networking.nat.externalInterface = "eth2";
            networking.nat.internalIPs = [ "192.168.1.0/24" ];
            networking.nat.enable = true;
          };
        router2 =
          { ... }:
          {
            virtualisation.vlans = [ 2 3 ];
            environment.systemPackages = [ pkgs.tcpdump ];
            networking.firewall.enable = false;
            networking.nat.externalInterface = "eth2";
            networking.nat.internalIPs = [ "192.168.2.0/24" ];
            networking.nat.enable = true;
          };
        publicNode =
          { config, pkgs, ... }:
          {
            virtualisation.vlans = [ 3 ];
            environment.variables = {
              PK_PATH = "$HOME/polykey";
            };
            environment.systemPackages = [ pk pkgs.tcpdump ];
            networking.firewall.enable = false;
          };
      };
    testScript =''
      start_all()
      # can start polykey-agent in both public and private nodes
      publicNode.succeed("pk agent start")
      privateNode1.succeed("pk agent start")
      privateNode2.succeed("pk agent start")
      # can create a new keynode in both public and private nodes
      create_node_command = "pk agent create -n {name} -e {name}@email.com -p passphrase"
      publicNode.succeed(create_node_command.format(name="publicNode"))
      privateNode1.succeed(create_node_command.format(name="privateNode1"))
      privateNode2.succeed(create_node_command.format(name="privateNode2"))
      # can add privateNode node info to publicNode
      publicNodeNodeInfo = publicNode.succeed("pk nodes get -c -b")
      privateNode1.succeed("pk nodes add -b '{}'".format(publicNodeNodeInfo))
      privateNode2.succeed("pk nodes add -b '{}'".format(publicNodeNodeInfo))
      # can add publicNode node info to privateNodes
      privateNode1NodeInfo = privateNode1.succeed("pk nodes get -c -b")
      privateNode2NodeInfo = privateNode2.succeed("pk nodes get -c -b")
      publicNode.succeed("pk nodes add -b '{}'".format(privateNode1NodeInfo))
      publicNode.succeed("pk nodes add -b '{}'".format(privateNode2NodeInfo))
      # copy public keys over to node machines
      publicNodePublicKey = publicNode.succeed("cat $HOME/.polykey/.keys/public_key")
      privateNode1PublicKey = privateNode1.succeed("cat $HOME/.polykey/.keys/public_key")
      privateNode2PublicKey = privateNode2.succeed("cat $HOME/.polykey/.keys/public_key")
      privateNode1.succeed("echo '{}' > $HOME/publicNode.pub".format(publicNodePublicKey))
      privateNode1.succeed("echo '{}' > $HOME/privateNode2.pub".format(privateNode2PublicKey))
      privateNode2.succeed("echo '{}' > $HOME/publicNode.pub".format(publicNodePublicKey))
      privateNode2.succeed("echo '{}' > $HOME/privateNode1.pub".format(privateNode1PublicKey))
      publicNode.succeed("echo '{}' > $HOME/privateNode1.pub".format(privateNode1PublicKey))
      publicNode.succeed("echo '{}' > $HOME/privateNode2.pub".format(privateNode2PublicKey))
      # modify node info to match node machines' host address
      publicNode.succeed("pk nodes update -p $HOME/privateNode1.pub -ch privateNode1")
      publicNode.succeed("pk nodes update -p $HOME/privateNode2.pub -ch privateNode2")
      privateNode1.succeed(
          "pk nodes update -p $HOME/publicNode.pub -ch publicNode -r $HOME/publicNode.pub"
      )
      privateNode2.succeed(
          "pk nodes update -p $HOME/publicNode.pub -ch publicNode -r $HOME/publicNode.pub"
      )
      # privateNodes can ping publicNode
      privateNode1.succeed("pk nodes ping -p $HOME/publicNode.pub")
      privateNode2.succeed("pk nodes ping -p $HOME/publicNode.pub")
      # can create a new vault in publicNode and clone it from both privateNodes
      publicNode.succeed("pk vaults new publicVault")
      publicNode.succeed("echo 'secret content' > $HOME/secret")
      publicNode.succeed("pk secrets new publicVault:Secret -f $HOME/secret")
      privateNode1.succeed("pk vaults clone -n publicVault -p $HOME/publicNode.pub")
      privateNode2.succeed("pk vaults clone -n publicVault -p $HOME/publicNode.pub")
      # can create a new vault in privateNode1
      privateNode1.succeed("pk vaults new privateVault1")
      # can create a new secret in privateNode1
      privateNode1.succeed("echo 'secret content' > $HOME/secret")
      privateNode1.succeed("pk secrets new privateVault1:Secret -f $HOME/secret")
      # setup a relay between privateNode1 and publicNode
      privateNode1.succeed("pk nodes relay -p $HOME/publicNode.pub")
      # add privateNode1 node info to privateNode2
      privateNode1NodeInfo = privateNode1.succeed("pk nodes get -c -b")
      privateNode2.succeed("pk nodes add -b '{}'".format(privateNode1NodeInfo))
      # add privateNode2 node info to privateNode1
      privateNode2NodeInfo = privateNode2.succeed("pk nodes get -c -b")
      privateNode1.succeed("pk nodes add -b '{}'".format(privateNode2NodeInfo))
      # can ping privateNode1 to privateNode2
      privateNode2.succeed("pk nodes ping -p ~/privateNode1.pub")
      # can pull a vault from privateNode1 to privateNode2
      privateNode2.succeed("pk vaults clone -p ~/privateNode1.pub -n privateVault1")
    '';
  }

Tasks

1. - Create test harness/fixture utilities that create a multi-node situation
2. - Simulate a NAT table situation by making use of network namespaces
3. - This test can only run on Linux that supports virtual network namespaces.
   4. [ ] - The test will have to be run separately from npm test which runs jest. This test can be done inside Gitlab CI/CD if the CI/CD on Linux supports creating network namespaces. If not, it's a manual test. Using conditional testing instead Conditional testing for platform-specific tests #380
4. - Review my gist https://gist.github.com/CMCDragonkai/3f3649d7f1be9c7df36f which explains how to use network namespaces. The Linux iptables firewall has to be used that simulates a NAT that allows outgoing packets but denies incoming packets except for the connections that are already live. This is called a "stateful firewall". I've done this before, but I forgot the details.
5. - You'll need to use https://stackabuse.com/executing-shell-commands-with-node-js/ to run the ip netns commands. Remember to check whether the OS is linux before allowing one to run these tests.
6. [ ] - Add in testing involving testnet.polykey.io which should run only during integration testing after the integration:deployment job (because it has to deploy to the testnet in that job). - Reissued Integration Tests for testnet.polykey.com Polykey-CLI#71

[CMCDragonkai]

This should be incorporated into our automated tests when we run jest. But that would also mean using nix-build... etc. Or it can be done outside as a separate command that is only run in our checkPhase during the building of the application/library (possibly in our release.nix since our default.nix doesn't have this).

[CMCDragonkai]

We need to implement a test for relaying the hole punching message. This is not meant to be using the notifications domain because it's part of automated connection establishment.

We need to test several situations:

1. Test if we can do this with a designated seed node, this coincides with Testnet Node Deployment (testnet.polykey.io) #194 <- only this one for release
2. Test if we can do this with any node on the Polykey network, thus generalising to decentralised relays.

[CMCDragonkai]

@joshuakarp I'm curious how exactly are we going to implement a optimised routing system for routing the hole punching relay messages?

The same algorithm can later be used for picking the optimal relay for mesh proxying to defeat symmetric NAT.

I remember we mentioned some usage of kademlia or represenation of "closest" node.

If we just assume that we always use our seed cluster/bootstrap cluster, then this is just centralised routing. But if we enable any keynode to be a relay, then we need to understand that the the PK network is a loose mesh, with loose connection lifetimes as well. Is kademlia actually useful for routing here?

This feels like a routing problem, and it seems that existing routers already have algorithms that help solve this problem. Is there any cross over with things like spanning tree algorithms https://en.wikipedia.org/wiki/Minimum_spanning_tree?

Given that we all keynodes may be on the public internet. Another matter is whether all live network links are equal in quality. Of course in reality they are not where latency and throughput and reliability matters. But if we are only distinguishing between vertexes where edges can be made vs vertexes where edges cannot be made, then our algorithm should converge very quickly to find the proper relaying route.

[joshuakarp]

@CMCDragonkai Kademlia inherently has a "closeness" mechanism. That is, the XOR value of two node IDs determine closeness (smaller = closer, larger = further away). Remember that with Kademlia, we store more node ID -> node address mappings of the nodes that are "closest" to us: this is the fundamental part of the k-buckets structure.

Isn't this inherently a routing solution?

See this too, straight from the Kademlia paper https://www.scs.stanford.edu/~dm/home/papers/kpos.pdf:

We start with some definitions. For a k-bucket covering the distance range [2^i, 2^(i+1)), define the index of the bucket to be i. Define the depth, h, of a node to be [number of k buckets] − i, where i is the smallest index of a non-empty bucket. Define node y’s bucket height in node x to be the index of the bucket into which x would insert y minus the index of x’s least significant empty bucket. Because node IDs are randomly chosen, it follows that highly non-uniform distributions are unlikely. Thus with overwhelming probability the height of any given node will be within a constant of log n for a system with n nodes. Moreover, the bucket height of the closest node to an ID in the kth-closest node will likely be within a constant of log k.

Our next step will be to assume the invariant that every k-bucket of every node contains at least one contact if a node exists in the appropriate range. Given this assumption, we show that the node lookup procedure is correct and takes logarithmic time. Suppose the closest node to the target ID has depth h. If none of this node’s h most significant k-buckets is empty, the lookup procedure will find a node half as close (or rather whose distance is one bit shorter) in each step, and thus turn up the node in h − log k steps. If one of the node’s k-buckets is empty, it could be the case that the target node resides in the range of the empty bucket. In this case, the final steps will not decrease the distance by half. However, the search will proceed exactly as though the bit in the key corresponding to the empty bucket had been flipped. Thus, the lookup algorithm will always return the closest node in h − log k steps.

I found a pretty good animation of this too, to showcase the lookup procedure https://kelseyc18.github.io/kademlia_vis/lookup/

As a side note, I started to read quite an interesting paper about using notions of "trust" to overcome some of the issues with malicious nodes and attack vectors on these kinds of systems: https://ieeexplore.ieee.org/document/6217954

[CMCDragonkai]

Kademlia's closeness is used to route to the relevant node that has information on the node ID to IP address. I can see how that might mean that you can trigger a hole punch relay message at that node.

Does this mean you would need to send that as a option/flag that means you want to pass on a hole punching message on the call to resolve a node ID? This would mean resolution and relaying a hole punch is done at the same time.

Or you would need to know which node returned the resolution and then use that.

However there's still a problem with this mechanism. The relaying node must already have an open connection with the receiving node. If the relaying node does not have an open and live connection and that the receiving node is behind a restricted NAT, then the relaying cannot actually relay anything just like the sending node.

There is an assumption here that the node that resolves has an open connection to all the IP addresses. But is this actually true? There are several points here:

1. Relaying node must maintain an open and already have a live connection to the receiving node. Thus you want to route a relay message to a node that is open to it.
2. Sending node must be able to open a connection to the relaying node otherwise you have a chicken or egg problem here. A transitive NAT traversal problem.
3. Kademlia doesn't have a locality optimisation based on network locality for throughput nor latency. But this can solved later.
4. Seed/bootstrap nodes is the best candidate at the moment for relaying but if we want to decentralised this, this should work as a mesh.
5. Participating as part of the mesh should be optional... Or if not then all relay messages should ideally not leak which PK node is contacting which PK node. Which sounds like an onion routing scheme.

[CMCDragonkai]

Is the kademlia contact database rebalanced/replicated across the network like a DHT?

Otherwise how does one store a contact if not by being contacted by it and contacting it in turn?

[joshuakarp]

Does this mean you would need to send that as a option/flag that means you want to pass on a hole punching message on the call to resolve a node ID? This would mean resolution and relaying a hole punch is done at the same time.

In order for Kademlia to function, there are lots of implicit connection establishments taking place. That is, every time you receive k closest nodes from another node, the idea is that you would connect to each of these received nodes and query them for their k closest nodes. If you don't already have a connection established with them, then you need to send a hole-punching packet across the network to attempt to establish connection.

So yes, as part of the resolution process, we are already sending hole punch packets to each of these nodes we need to contact.

Or you would need to know which node returned the resolution and then use that.

This could be a worthwhile optimisation.

However there's still a problem with this mechanism. The relaying node must already have an open connection with the receiving node. If the relaying node does not have an open and live connection and that the receiving node is behind a restricted NAT, then the relaying cannot actually relay anything just like the sending node.

There is an assumption here that the node that resolves has an open connection to all the IP addresses. But is this actually true?

Yeah, you're right. I remember we had some brief discussion about whether we should consider having "persistent" connections to some of the "closest" nodes in the network. That is, upon coming online, we immediately connect to these nodes. But yeah, in order to even establish these persistent connections, we have the same issue.

[joshuakarp]

Is the kademlia contact database rebalanced/replicated across the network like a DHT?

Otherwise how does one store a contact if not by being contacted by it and contacting it in turn?

Currently no. There's no rebalancing/replication across the network. There's currently 2 ways that nodes are added to the database:

1. This kademlia "discovery" process, of contacting other nodes to find the k closest nodes (any found nodes that are able to be connected to are added to our database).
2. I added an initial "sync" to a node when it comes online. That is, it contacts the provided seed nodes (if any are provided) and asks for the k closest nodes to itself. Currently, this also attempts to establish connection before adding the node to our database.

[CMCDragonkai]

I think our plan is for the release, we'll stick with the centralised seed node cluster #194.

We can put the problem of decentralised relaying to a post-release issue. This issue is more focused on just creating a test-harness for NAT-traversal, so we should focus this issue on this problem.

In the mean time, I'll create a new issue for decentralised relaying.

[CMCDragonkai]

If you have difficulties working on this, I can ask @nzhang-zh or @Zachaccino to help advise.