DHT

The API of libgnunetblock

The block library requires for each (family of) block type(s) a block plugin (implementing gnunet_block_plugin.h) that provides basic functions that are needed by the DHT (and possibly other subsystems) to manage the block. These block plugins are typically implemented within their respective subsystems. The main block library is then used to locate, load and query the appropriate block plugin. Which plugin is appropriate is determined by the block type (which is just a 32-bit integer). Block plugins contain code that specifies which block types are supported by a given plugin. The block library loads all block plugins that are installed at the local peer and forwards the application request to the respective plugin.

The central functions of the block APIs (plugin and main library) are to allow the mapping of blocks to their respective key (if possible) and the ability to check that a block is well-formed and matches a given request (again, if possible). This way, GNUnet can avoid storing invalid blocks, storing blocks under the wrong key and forwarding blocks in response to a query that they do not answer.

One key function of block plugins is that it allows GNUnet to detect duplicate replies (via the Bloom filter). All plugins MUST support detecting duplicate replies (by adding the current response to the Bloom filter and rejecting it if it is encountered again). If a plugin fails to do this, responses may loop in the network.

Queries

The query format for any block in GNUnet consists of four main components. First, the type of the desired block must be specified. Second, the query must contain a hash code. The hash code is used for lookups in hash tables and databases and must not be unique for the block (however, if possible a unique hash should be used as this would be best for performance). Third, an optional Bloom filter can be specified to exclude known results; replies that hash to the bits set in the Bloom filter are considered invalid. False-positives can be eliminated by sending the same query again with a different Bloom filter mutator value, which parametrizes the hash function that is used. Finally, an optional application-specific "eXtended query" (xquery) can be specified to further constrain the results. It is entirely up to the type-specific plugin to determine whether or not a given block matches a query (type, hash, Bloom filter, and xquery). Naturally, not all xquery’s are valid and some types of blocks may not support Bloom filters either, so the plugin also needs to check if the query is valid in the first place.

Depending on the results from the plugin, the DHT will then discard the (invalid) query, forward the query, discard the (invalid) reply, cache the (valid) reply, and/or forward the (valid and non-duplicate) reply.

Sample Code

The source code in plugin_block_test.c is a good starting point for new block plugins — it does the minimal work by implementing a plugin that performs no validation at all. The respective Makefile.am shows how to build and install a block plugin.

Conclusion2

In conclusion, GNUnet subsystems that want to use the DHT need to define a block format and write a plugin to match queries and replies. For testing, the GNUNET_BLOCK_TYPE_TEST block type can be used; it accepts any query as valid and any reply as matching any query. This type is also used for the DHT command line tools. However, it should NOT be used for normal applications due to the lack of error checking that results from this primitive implementation.

libgnunetdht libgnunetdht libgnunetdht ————

The DHT API itself is pretty simple and offers the usual GET and PUT functions that work as expected. The specified block type refers to the block library which allows the DHT to run application-specific logic for data stored in the network.

GET

When using GET, the main consideration for developers (other than the block library) should be that after issuing a GET, the DHT will continuously cause (small amounts of) network traffic until the operation is explicitly canceled. So GET does not simply send out a single network request once; instead, the DHT will continue to search for data. This is needed to achieve good success rates and also handles the case where the respective PUT operation happens after the GET operation was started. Developers should not cancel an existing GET operation and then explicitly re-start it to trigger a new round of network requests; this is simply inefficient, especially as the internal automated version can be more efficient, for example by filtering results in the network that have already been returned.

If an application that performs a GET request has a set of replies that it already knows and would like to filter, it can call GNUNET_DHT_get_filter_known_results with an array of hashes over the respective blocks to tell the DHT that these results are not desired (any more). This way, the DHT will filter the respective blocks using the block library in the network, which may result in a significant reduction in bandwidth consumption.

PUT

Todo

inconsistent use of “must” above it’s written “MUST”

In contrast to GET operations, developers must manually re-run PUT operations periodically (if they intend the content to continue to be available). Content stored in the DHT expires or might be lost due to churn. Furthermore, GNUnet’s DHT typically requires multiple rounds of PUT operations before a key-value pair is consistently available to all peers (the DHT randomizes paths and thus storage locations, and only after multiple rounds of PUTs there will be a sufficient number of replicas in large DHTs). An explicit PUT operation using the DHT API will only cause network traffic once, so in order to ensure basic availability and resistance to churn (and adversaries), PUTs must be repeated. While the exact frequency depends on the application, a rule of thumb is that there should be at least a dozen PUT operations within the content lifetime. Content in the DHT typically expires after one day, so DHT PUT operations should be repeated at least every 1-2 hours.

MONITOR

The DHT API also allows applications to monitor messages crossing the local DHT service. The types of messages used by the DHT are GET, PUT and RESULT messages. Using the monitoring API, applications can choose to monitor these requests, possibly limiting themselves to requests for a particular block type.

The monitoring API is not only useful for diagnostics, it can also be used to trigger application operations based on PUT operations. For example, an application may use PUTs to distribute work requests to other peers. The workers would then monitor for PUTs that give them work, instead of looking for work using GET operations. This can be beneficial, especially if the workers have no good way to guess the keys under which work would be stored. Naturally, additional protocols might be needed to ensure that the desired number of workers will process the distributed workload.

DHT Routing Options

There are two important options for GET and PUT requests:

GNUNET_DHT_RO_DEMULITPLEX_EVERYWHERE This option means that all

peers should process the request, even if their peer ID is not closest to the key. For a PUT request, this means that all peers that a request traverses may make a copy of the data. Similarly for a GET request, all peers will check their local database for a result. Setting this option can thus significantly improve caching and reduce bandwidth consumption — at the expense of a larger DHT database. If in doubt, we recommend that this option should be used.

GNUNET_DHT_RO_RECORD_ROUTE This option instructs the DHT to record

the path that a GET or a PUT request is taking through the overlay network. The resulting paths are then returned to the application with the respective result. This allows the receiver of a result to construct a path to the originator of the data, which might then be used for routing. Naturally, setting this option requires additional bandwidth and disk space, so applications should only set this if the paths are needed by the application logic.

GNUNET_DHT_RO_FIND_PEER This option is an internal option used by

the DHT’s peer discovery mechanism and should not be used by applications.

GNUNET_DHT_RO_BART This option is currently not implemented. It may

in the future offer performance improvements for clique topologies.

The DHT Client-Service Protocol

PUTting data into the DHT

To store (PUT) data into the DHT, the client sends a struct GNUNET_DHT_ClientPutMessage to the service. This message specifies the block type, routing options, the desired replication level, the expiration time, key, value and a 64-bit unique ID for the operation. The service responds with a struct GNUNET_DHT_ClientPutConfirmationMessage with the same 64-bit unique ID. Note that the service sends the confirmation as soon as it has locally processed the PUT request. The PUT may still be propagating through the network at this time.

In the future, we may want to change this to provide (limited) feedback to the client, for example if we detect that the PUT operation had no effect because the same key-value pair was already stored in the DHT. However, changing this would also require additional state and messages in the P2P interaction.

GETting data from the DHT

To retrieve (GET) data from the DHT, the client sends a struct GNUNET_DHT_ClientGetMessage to the service. The message specifies routing options, a replication level (for replicating the GET, not the content), the desired block type, the key, the (optional) extended query and unique 64-bit request ID.

Additionally, the client may send any number of struct GNUNET_DHT_ClientGetResultSeenMessages to notify the service about results that the client is already aware of. These messages consist of the key, the unique 64-bit ID of the request, and an arbitrary number of hash codes over the blocks that the client is already aware of. As messages are restricted to 64k, a client that already knows more than about a thousand blocks may need to send several of these messages. Naturally, the client should transmit these messages as quickly as possible after the original GET request such that the DHT can filter those results in the network early on. Naturally, as these messages are sent after the original request, it is conceivable that the DHT service may return blocks that match those already known to the client anyway.

In response to a GET request, the service will send struct GNUNET_DHT_ClientResultMessages to the client. These messages contain the block type, expiration, key, unique ID of the request and of course the value (a block). Depending on the options set for the respective operations, the replies may also contain the path the GET and/or the PUT took through the network.

A client can stop receiving replies either by disconnecting or by sending a struct GNUNET_DHT_ClientGetStopMessage which must contain the key and the 64-bit unique ID of the original request. Using an explicit "stop" message is more common as this allows a client to run many concurrent GET operations over the same connection with the DHT service — and to stop them individually.

Monitoring the DHT

To begin monitoring, the client sends a struct GNUNET_DHT_MonitorStartStop message to the DHT service. In this message, flags can be set to enable (or disable) monitoring of GET, PUT and RESULT messages that pass through a peer. The message can also restrict monitoring to a particular block type or a particular key. Once monitoring is enabled, the DHT service will notify the client about any matching event using struct GNUNET_DHT_MonitorGetMessages for GET events, struct GNUNET_DHT_MonitorPutMessage for PUT events and struct GNUNET_DHT_MonitorGetRespMessage for RESULTs. Each of these messages contains all of the information about the event.

The DHT Peer-to-Peer Protocol

Routing GETs or PUTs

When routing GETs or PUTs, the DHT service selects a suitable subset of neighbours for forwarding. The exact number of neighbours can be zero or more and depends on the hop counter of the query (initially zero) in relation to the (log of) the network size estimate, the desired replication level and the peer’s connectivity. Depending on the hop counter and our network size estimate, the selection of the peers maybe randomized or by proximity to the key. Furthermore, requests include a set of peers that a request has already traversed; those peers are also excluded from the selection.

PUTting data into the DHT

To PUT data into the DHT, the service sends a struct PeerPutMessage of type GNUNET_MESSAGE_TYPE_DHT_P2P_PUT to the respective neighbour. In addition to the usual information about the content (type, routing options, desired replication level for the content, expiration time, key and value), the message contains a fixed-size Bloom filter with information about which peers (may) have already seen this request. This Bloom filter is used to ensure that DHT messages never loop back to a peer that has already processed the request. Additionally, the message includes the current hop counter and, depending on the routing options, the message may include the full path that the message has taken so far. The Bloom filter should already contain the identity of the previous hop; however, the path should not include the identity of the previous hop and the receiver should append the identity of the sender to the path, not its own identity (this is done to reduce bandwidth).

GETting data from the DHT

A peer can search the DHT by sending struct PeerGetMessages of type GNUNET_MESSAGE_TYPE_DHT_P2P_GET to other peers. In addition to the usual information about the request (type, routing options, desired replication level for the request, the key and the extended query), a GET request also contains a hop counter, a Bloom filter over the peers that have processed the request already and depending on the routing options the full path traversed by the GET. Finally, a GET request includes a variable-size second Bloom filter and a so-called Bloom filter mutator value which together indicate which replies the sender has already seen. During the lookup, each block that matches they block type, key and extended query is additionally subjected to a test against this Bloom filter. The block plugin is expected to take the hash of the block and combine it with the mutator value and check if the result is not yet in the Bloom filter. The originator of the query will from time to time modify the mutator to (eventually) allow false-positives filtered by the Bloom filter to be returned.

Peers that receive a GET request perform a local lookup (depending on their proximity to the key and the query options) and forward the request to other peers. They then remember the request (including the Bloom filter for blocking duplicate results) and when they obtain a matching, non-filtered response a struct PeerResultMessage of type GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT is forwarded to the previous hop. Whenever a result is forwarded, the block plugin is used to update the Bloom filter accordingly, to ensure that the same result is never forwarded more than once. The DHT service may also cache forwarded results locally if the "CACHE_RESULTS" option is set to "YES" in the configuration.