Decode Directed Routing
From Pfyshnet
Decode Directed Routing (ddr) is a form of Onion Routing where the next node to forward the data to is not specified. Instead the data contains an encoded header block with a special marker. If the node can successfully decode the header, revealing the marker, then it continues to decode the rest of the data. The decoded data is then forwarded to a node picked from a smaller set of nodes. If the data cannot be decoded it is forwarded to a node picked from a larger set of nodes. This continues until the data reaches a destination node that is one of only a few nodes.
To understand how this works, you must understand how the nodes of the network are organized. Note that this is an oversimplification that would not be completely practical or secure, but it is meant to give the reader a general understanding of DDR. Each node in the network is a member of one of four different groups of nodes. These four groups are called the first or primary routing level groups. Each of the primary routing level groups are also divided into 4 more subgroups, called the 2nd level routing groups. Then each of these are divided into 4 subgroups, called the 3rd level routing groups, and so on until a minimum number of nodes in a group is achieved. That means that any given node is a member of increasing smaller groups of nodes, where each subgroup contains nodes that were also a member of the preceding group.
For example, in a network of 192 nodes, nodes 1 through 48 might comprise one of the primary level routing groups. Nodes 1 through 12 are in the same 2nd level routing group. Nodes 1, 2 and 3 are all in the same 3rd level routing group. Each node knows what other nodes are in its groups. For example, Node 1 knows that nodes 2 and 3 are also in its 3rd level routing group. Within each group a key pair is shared. In our example, nodes 1 through 48 would all know key pair A, while nodes 1 through 12 would also know key pair B. Nodes 1,2, and 3 would also know key pair C.
The private keys are kept secret, only known inside the routing groups to which they belong. However, the public keys are used by other nodes to build DDR Onions through the network. For example, data is encoded with the public key from the key pair C. Then it is encoded with the public key from pair B. Finally it is encoded with the public key from key pair A. Now the encoded packet is sent out on the network. If it is sent to a node that is not a member key pair A’s primary routing group, it will not be able to decode the data and it will forward it on to another node. If the arrives at a node in A’s primary routing group it will be successfully decoded. Then that node will forward the decoded data to another node that it knows to be in the same primary routing group. It indicates that the data is to be decoded by a second level routing group key. If that node is not a member of public key B’s 2nd level routing group it will fail to decode the data and it will forward it on to another node in its primary routing group. Once it arrives at a node that is a member of B’s 2nd level routing group the data is successfully decoded. The decoded data is then forwarded on to another node in B’s routing group, with an indication that it is ready for 3rd level routing group decoding. Once it arrives at a node in C’s routing group the data has been completely decoded and will be acted upon.
When a node decides it will store data, it gives the data a unique ID number. The data and ID is shared with the other nodes in it's last routing level group. The ID is combined with the public keys of the node's routing levels to form the Route Specification (RS). Other nodes can use the RS to request the data. A request command with the ID number is encoded using the public keys in reverse order. Note that a randomly generated symmetric key is actually used to encode the data, and then that key encrypted with the public key. This means that even though everyone uses the same public keys from the RS, each resulting onion will be unique. It is not possible to determine what data is being requested from an encoded DDR onion, without being a memeber of the last routing group for the data.
When a node receives encoded data it makes note of the node that sent it the data and records the sending node’s group. If the receiving node also fails to decode the data, it knows not to send the data to another node in its group. It also knows not to send it back to a member of the sending node’s group. Therefore, there are only 2 groups to chose from when forwarding data that has failed to decode. From this we can calculate an average of 2 hops per decode layer (this will be adjusted later when we look at a practical implementation of DDR). The number of hops needed to go from the primary routing group to the bottom group can be calculated:
2 * Ln ( N / L ) / Ln (4) N = Total number of nodes in the network L = Minimum number of nodes needed to form a group.
This gives us O(log n) hop performance. For example if there are 1000000 nodes and a minimum group size of 5, then the average number of hops needed would just be 18.
DDR protects data facilitators. If you are participating in Pfyshnet then you are inherently allowing others to store data on your machine. You will not know what is being stored on your machine, and as a consequence you do not want others to be able figure out what you are storing. DDR allows you to let others build a route to you (and other nodes in your last routing level) such that your identity is hidden. I2P does this by building tunnels, but the problem is that implication is simply transferred to the Kademlia nodes and gateway nodes. They are now the primary facilitation points of the data being sought. By allowing 1/4th of the entire network to serve as the entry point to any data, facilitation is mitigated by the shear size of the nodes to choose from.
DDR also replaces the idea of a key search. Many networks use a key (usually a hash of the encoded data) to search for a facilitator. The problem is that the search is plain to any node that it travels through. It cannot be hidden that someone is searching for a given piece of data. However, with DDR the data being sought is completely hidden until the request reaches the destination.
