P2P Layer

To start communicating with other nodes, a node has to join the network. To do this, the node has to know some other node that already participates in the protocol; this node is called a bootstrap node.

After connecting to the bootstrap node, we receive a list of peers which we’ll use for network communication. Those peers are called neighbors. The list of neighbors should be maintained in such a way that these nodes are online and any node from the network can receive our messages. Moreover, messages should be delivered efficiently.

To achieve this, Cardano SL uses the Kademlia DHT protocol. Even though Kademlia provides more features, we only use it as a method of peer discovery.

Overview of Kademlia Protocol

See also: the P2P Network section of the technical overview.

In Kademlia, every node is associated with a 32-byte ID (see ID structure for more details). These IDs are used to identify nodes without having to refer to their network addresses. The keys used to store values in Kademlia are also 32-byte identifiers.

Kademlia uses the XOR metric to define the distance between nodes. Key-value pairs are stored in nodes with IDs that are “close” to the keys. This distance is also used to efficiently locate a node with the given ID.

At start, a bootstrap node should be provided to Kademlia in order to join the network. The address of this node can be hardcoded in the implementation or chosen by the user. Later, the node will attempt to find more peers by querying its neighbors (from the initial list of peers sent by the bootstrap node). A node sends messages to its peers, which resend messages to their peers close to the needed ID/key. The list of known peers is preserved between launches.

Here and later, by address we mean tuple (Host, Port, ID), while network address denotes just the pair (Host, Port).

Kademlia uses the UDP protocol for transmitting messages.

To learn more about how Kademlia is implemented, please refer to the paper Kademlia: a Peer-to-peer Information System Based on the XOR Metric.

Messages Used in Kademlia

Every message is represented as a binary string with the maximum length of 1200 bytes (so that it wouldn’t exceed IPv6 datagram size). A special case is RETURN_NODES: if it exceeds 1200 bytes, the node list is split into several messages. The number of messages is represented with a single byte. Please see serialize function for more details.

IDs, Keys and Values

IDs and keys in Kademlia are represented with the same structure called HashId:

Field size Description
18 Hash - PBKDF2 key generated from Nonce
14 Nonce - an arbitrary 14-bytes long binary string

Please see Addressing section for more details.

Cardano SL do not use Kademlia as key-value storage. Thus we just use empty strings as values.

PING

Check if a peer is still accessible. After sending this message, the node would expect to receive a PONG message as the reply. Kademlia pings every peer periodically to maintain a correct peer list.

Field size Value Description
1 0 1-byte value to determine message type
32   ID of our node

PONG

Used as a reply to PING messages.

Field size Value Description
1 1 1-byte value to determine message type
32   ID of our node

STORE

Store given value in Kademlia. This message is disabled and would be ignored by nodes.

Field size Value Description
1 2 1-byte value to determine message type
32   ID of our node
32   Key
0   Value (empty string in Cardano SL)

FIND_NODE

Request network address of node with given ID. After sending this message the node would expect to receive a RETURN_NODES message with a list of nodes closest to the requested one (including the requested node itself).

Field size Value Description
1 3 1-byte value to determine message type
32   ID of our node
32   ID of node we are looking for

RETURN_NODES

Send network addresses of some nodes in reply to FIND_NODE of FIND_VALUE. Answer is split into several messages because list of nodes can exceed IPv6 datagram size.

First, let’s describe binary representation of single peer:

Field size Value Description
32   Peer ID
1-255   Peer host name
1 32 Ascii code of “ “ to separate host name from port
2   Peer port

Now, let’s describe binary representation of RETURN_NODES message:

Field size Value Description
1 4 1-byte value to determine message type
32   ID of our node
1   Total number of RETURN_NODES messages sent as answer to this request
32   ID of node that requested nodes
at most 1136   Several peers close to the requested ID (at most 1136 bytes to not exceed IPv6 datagram size)

FIND_VALUE

Behaves in the same way as FIND_NODE, except that it can also receive a RETURN_VALUE response if the lookup was successful. Currently it’s only used in Cardano SL for finding peers. When the node starts working, it generates a random key and asks Kademlia to find it; this search always fails, but it lets the node discover some initial peer addresses.

Field size Value Description
1 5 1-byte value to determine message type
32   ID of our node
32   Key we are looking for

RETURN_VALUE

A reply to a STORE request. This message is not used in Cardano SL because it does not store any values in Kademlia.

Field size Value Description
1 6 1-byte value to determine message type
32   ID of our node
32   ID of node that requested value
0   Value (empty string in Cardano SL)

Security

Since Kademlia is a protocol for open P2P networks, it had to be modified in several other ways to become reasonably secure.

Possible Attacks

An eclipse attack is a situation when a node is surrounded by adversary nodes.

In Kademlia, eclipse attacks (targeted at the particular participant of the network) are hard to perform, but possible. First, launch a hundred nodes with node IDs close to target node ID. These nodes would fill the node’s lowest k-buckets (which are expected to be empty, at a first sight), then perform a DDoS attack on nodes from target’s k-buckets (it’s possible to determine those nodes if network’s topology haven’t changed much since the node was started). After a successful DDoS attack, the node’s remaining neighbors would be adversary agents.

Please note that Kademlia’s structure implies that launching nodes close to the target is not enough to eclipse it. Node lists are stored by node in k-buckets (the i-th bucket contains no more than k nodes with relative distance 2^i-1 < d < 2^i), and new nodes are added to corresponding buckets only if these buckets are not already full. Kademlia prefers nodes that have been in lists for a long time and were recently seen alive. Without getting some nodes down, it’s impossible to eclipse a node.

This attack is tricky and unlikely to happen in practice. The Addressing modification makes it even harder.

A 100500 attack is an attack that launches significantly more nodes than the amount of nodes in the current P2P network, either in order to eclipse some nodes or to deny service by flooding the network. The attack wouldn’t cause any problems for old nodes (not counting possible network overhead), because old nodes preserve their routes. But when a new node joins the network, it would get eclipsed (isolated in an adversarial subnet), because old honest nodes won’t add it to their buckets (as these buckets are already filled by other nodes), and the new node would be known to adversaries only.

Defending against 100500 attacks remains an open problem. For now, we’re going to make them practically infeasible with a sophisticated ban system / adversary detection.

Addressing

We use so-called HashIds as node IDs. Since it contains a hash, assigning yourself an arbitrary ID is impossible, and this means that a 100500 attack is the only way to perform an eclipse attack.

Implementation Notes

HashId is a binary string with a fixed length (32 bytes) formed like this:

+---------------+------------+
|    Hashing    |    Nonce   |
+---------------+------------+

|   18 bytes    |  14 bytes  |

where:

  • Nonce is just random 14 bytes (from the system source of entropy),
  • Hashing is hashing data.

Hashing data is generated based on DerivingKey and Salt, where:

For DerivingKey generation we use these arguments:

  • prfPassword - PRF (pseudorandom function) for PBKDF2 using HMAC (Hash-based Message Authentication Code) with SHA-256 algorithm.
  • parameters - PBKDF2 parameters: 500 iterations, for 32 bytes as a result output.
  • Nonce mentioned above - as password.
  • Salt mentioned above - as salt.

Routing Data Anti-forging

In Kademlia, a node requests a list of peers from its neighbors and accepts the first message it receives. An adversary may forge those replies, providing addresses of adversary nodes as closest nodes to given ID. To overcome this issue, we make nodes wait for some period to gather as many replies as possible, and after that, the replies get merged and the node selects k closest nodes from the resulting set. This way, an adversary would have to eclipse a node in order to forge the list of peers it receives.

Implementation Notes

To implement this idea, we just add k neighbors nodes closest to the destination at the beginning of each lookup (lookup is a function used by FIND_NODE or FIND_VALUE to find k nodes closest to the given ID) to the pending set. When we receive a RETURN_NODES message, we update known list to make it contain k nodes currently known that are closest to the destination ID. This loop ends when no pending nodes are left. We do not introduce any specific period to collect neighbors replies. If any neighbors do not send us RETURN_NODES reply, we receive Timeout signal and this neighbor is handled by waitForReply function.

See also continueLookup function. It is the place where pending and known fields are updated, so this is where the core logic of this enhancement is located.

Routing Tables Sharing

When a node has just joined the network, it requests a list of neighbors (set of nodes closest to it). We have modified Kademlia to include some extra nodes into this list; specifically, now we pick some random nodes along with neighbors and return them. This gives the node additional knowledge to recover in case it’s surrounded with adversary nodes.

Implementation Notes

There is the function findClosest in our Kademlia implementation which finds k nodes closest to the given ID. The function pickupRandom was added. This function picks up given number of random nodes from Kademlia tree. The exact number of shared random nodes is specified through routingSharingN field from Kademlia config. This way, RETURN_NODES message includes the results of findClosest and pickupRandom calls.

Banning Nodes

We introduce a feature to ban nodes to Kademlia. We will use this to ban nodes when we detect them to act maliciously.

Implementation Notes

There are three possible states for a node:

  1. NoBan,
  2. BanTill,
  3. BanForever.

Please see BanState type. Values of this type are passed to banNode function.

NoBan is used to unban the already banned nodes. However, this action does not insert this node back into tree structure, but makes possible for this node to appear in peers again.

BanTill bans a node till some time (defined as a POSIX time).

BanForever bans a node forever.

The function banNode adds given node to the banned field of KademliaState type and deletes it from the tree. The function isNodeBanned checks if node is banned at the moment and deletes node from banned field if it was unbanned, or if the ban expired.

How a banned node is treated:

  • We cannot use it as our initial peer to join the network. Please see joinNetwork function.

  • We ignore all messages received from a banned node. Please see waitForReply function.

  • We do not include this node to the tree, do not send any messages to it and do not include this node to the RETURN_NODES messages.