Tech Design Doc: Relay Path Validation

Although signatures in a signature chain guarantee that it is signed by the claimed relayers, they do not guarantee the correctness of the relay path, where a path is defined as correct if it is the designated path of our distributed data transmission network (DDTN). Being able to validate the correctness of a path is crucial for the security of signature chains, otherwise attackers could break the assumption that each hop leads to a random node by selecting specific node as next hop, and a malicious party could construct signature chains fully under control by relaying packets only to nodes under control. Signature chain fully controlled by a party is no longer unpredictable by the party, and can be computed by the party without actually transmitting any data. The malicious party can then gain unfair economic advantage by producing more signature chains than it should, increasing its chance to get mining rewards.

The validity of any relay path should be consensus among all nodes as it is a prerequisite to select globally unique mining node for each block. There are two ways to achieve the consensus: 1. nodes use global information (e.g. previous blocks) that has already be agreed on; 2. nodes use their own local information, and reach consensus later. We choose the first approach as it does not require extra communication between nodes and is much more efficient. The disadvantage of such approach is that global information has time delay so that the topology may be different from the time when past consensus was reached. We consider this to be acceptable as long as the valid path is unique or almost unique, and the valid path still exists and will be selected by honest nodes with nontrivial probability at the time of validation.

To validate a path, we validate if each node on the route is relaying the packet to its neighbor that is closest to the destination address, considering only nodes that appeared in the last X blocks, where X is configurable. To be more specific, at each hop, let the node NKN address be x, the virtual ring can be separated into m segments, where segment i contains nodes whose NKN address is between (x + 2^i) mod 2^m (inclusive) and (x + 2^(i+1)) mod 2^m (exclusive). If there are any nodes within segment i, then the node in segment i that is closest to x will be a neighbor of node x. Similarly, if the destination NKN address is located in segment i, then the node in segment i that is closest to x should be the next hop which x should send the packet to. In practice, each node validating the path will check:

1. The next hop is indeed in segment i
2. No node that appeared in the last X blocks is in segment i and is closer to x than the next hop.

A hop is valid if it satisfies these two conditions. A path is valid if every hop is valid. Since the validation only utilizes information in the signature chain and data in previous blocks, every node in the NKN network that receives the signature chain and has previous blocks information will produce the same output, ensuring the consistency of validation.

A consequence of the above validation algorithm is that, if any hop in a path should select a node which appeared in the last X blocks but is now offline, then the actual hop will skip that node and select its immediate successor instead, make the path invalid. This cannot be avoided unless information other than previous blocks is used (e.g. ping the skipped node to see if it's indeed offline). We argue that this false negative is acceptable because it can be viewed as another random factor that rejects a portion of honest signature chain, similar to the role of the hash of the signature chain. The probability that an actual valid path is identified as valid can be computed as p = (1 - N_off / N)^l, where N_off is the number of nodes that appear in the last X blocks and then go offline when the packet is being relayed, N is the total number of nodes in the network, and l the length of the path. One can choose smaller X or making nodes more stable to reduce N_off and increase the validation rate.