Internet-Draft The R5N Distributed Hash Table May 2021
Schanzenbach, et al. Expires 24 November 2021 [Page]
Workgroup:
Independent Stream
Internet-Draft:
draft-schanzen-r5n-00
Published:
Intended Status:
Informational
Expires:
Authors:
M. Schanzenbach
GNUnet e.V.
C. Grothoff
Berner Fachhochschule
B. Fix
GNUnet e.V.

The R5N Distributed Hash Table

Abstract

This document contains the R5N DHT technical specification.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on 24 November 2021.

Table of Contents

1. Introduction

Distributed Hash Tables (DHTs) are a key data structure for the construction of completely decentralized applications. DHTs are important because they generally provide a robust and efficient means to distribute the storage and retrieval of key-value pairs.

This document contains the technical specification of the R5N DHT [R5N], a secure DHT routing algorithm and data structure for decentralized applications.

This document defines the normative wire format of peer-to-peer messages, routing algorithms, cryptographic routines and security considerations for use by implementors.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

2. Peer-to-peer wire formats

2.4. PUT message

0     8     16    24    32    40    48    56
+-----+-----+-----+-----+-----+-----+-----+-----+
|  MSIZE    |   MTYPE   |       OPTIONS         |
+-----+-----+-----+-----+-----+-----+-----+-----+
|       BTYPE           |       HOPCOUNT        |
+-----+-----+-----+-----+-----+-----+-----+-----+
|    REPLICATIONLVL     |       PATH_LEN        |
+-----+-----+-----+-----+-----+-----+-----+-----+
|     EXPIRATION        |     BLOOMFILTER       /
+-----+-----+-----+-----+                       /
/                 (128 byte)                    /
/                       +-----+-----+-----+-----+
/                       |       KEY             /
+-----+-----+-----+-----+                       /
/                 (64 byte)                     /
/                       +-----+-----+-----+-----+
/                       |   PUTPATH             /
+-----+-----+-----+-----+                       /
/                 (variable length)             /
+-----+-----+-----+-----+-----+-----+-----+-----+
/              PAYLOAD (variable length)        /
+-----+-----+-----+-----+-----+-----+-----+-----+
Figure 1

where:

MSIZE
denotes the size of this message in network byte order.
MTYPE
is the 16-bit message type. This type can be one of the DHT message types but for put messages it must be set to the value 146 in network byte order.
OPTIONS
is a 32-bit options field (see below).
BTYPE
is a 32-bit block type field. The block type indicates the content type of the payload. In network byte order.
HOPCOUNT
is a 32-bit number indicating how many hops this message has traversed to far. In network byte order.
REPLICATIONLVL
is a 32-bit number indicating the desired replication level of the data. In network byte order.
PATH_LEN
is a 32-bit number indicating the length of the PUT path recorded in PUTPATH. As PUTPATH is optiona, this value may be zero. In network byte order.
EXPIRATION
denotes the absolute 64-bit expiration date of the content. In microseconds since midnight (0 hour), January 1, 1970 in network byte order.
BLOOMFILTER
A bloomfilter (for peer identities) to stop circular routes.
KEY
The key under which the PUT request wants to store content under.
PUTPATH
the variable-length PUT path. The path consists of a list of PATH_LEN peer IDs.
PAYLOAD
the variable-length resource record data payload. The contents are defined by the respective type of the resource record.

2.5. GET message

0     8     16    24    32    40    48    56
+-----+-----+-----+-----+-----+-----+-----+-----+
|  MSIZE    |   MTYPE   |       OPTIONS         |
+-----+-----+-----+-----+-----+-----+-----+-----+
|       BTYPE           |       HOPCOUNT        |
+-----+-----+-----+-----+-----+-----+-----+-----+
|    REPLICATIONLVL     |       XQUERY_SIZE     |
+-----+-----+-----+-----+-----+-----+-----+-----+
|     BF_MUTATOR        |     BLOOMFILTER       /
+-----+-----+-----+-----+                       /
/                 (128 byte)                    /
/                       +-----+-----+-----+-----+
/                       |       KEY             /
+-----+-----+-----+-----+                       /
/                 (64 byte)                     /
/                       +-----+-----+-----+-----+
/                       |   XQUERY              /
+-----+-----+-----+-----+                       /
/                 (variable length)             /
+-----+-----+-----+-----+-----+-----+-----+-----+
/              BF_RESULT (variable length)      /
+-----+-----+-----+-----+-----+-----+-----+-----+
Figure 2

where:

MSIZE
denotes the size of this message in network byte order.
MTYPE
is the 16-bit message type. This type can be one of the DHT message types but for put messages it must be set to the value 147 in network byte order.
OPTIONS
is a 32-bit options field (see below).
BTYPE
is a 32-bit block type field. The block type indicates the content type of the payload. In network byte order.
HOPCOUNT
is a 32-bit number indicating how many hops this message has traversed to far. In network byte order.
REPLICATIONLVL
is a 32-bit number indicating the desired replication level of the data. In network byte order.
XQUERY_SIZE
is a 32-bit number indicating the length of the optional extended query XQUERY. In network byte order.
BF_MUTATOR
The bloomfilter mutator.
BLOOMFILTER
A bloomfilter (for peer identities) to stop circular routes.
KEY
The key under which the PUT request wants to store content under.
XQUERY
the variable-length extended query. Optional.
BF_RESULT
the variable-length result bloomfilter.

2.6. RESULT message

0     8     16    24    32    40    48    56
+-----+-----+-----+-----+-----+-----+-----+-----+
|  MSIZE    |   MTYPE   |       OPTIONS         |
+-----+-----+-----+-----+-----+-----+-----+-----+
|       BTYPE           |     PUT_PATH_LEN      |
+-----+-----+-----+-----+-----+-----+-----+-----+
|    GET_PATH_LEN       |       EXPIRATION      |
+-----+-----+-----+-----+-----+-----+-----+-----+
|                      KEY                      /
/                 (64 byte)                     |
+-----+-----+-----+-----+-----+-----+-----+-----+
/                    PUTPATH                    /
/                 (variable length)             /
+-----+-----+-----+-----+-----+-----+-----+-----+
/                    GETPATH                    /
/                 (variable length)             /
+-----+-----+-----+-----+-----+-----+-----+-----+
/                   PAYLOAD                     /
/              (variable length)                /
+-----+-----+-----+-----+-----+-----+-----+-----+
Figure 3

where:

MSIZE
denotes the size of this message in network byte order.
MTYPE
is the 16-bit message type. This type can be one of the DHT message types but for put messages it must be set to the value 148 in network byte order.
OPTIONS
is a 32-bit options field (see below).
BTYPE
is a 32-bit block type field. The block type indicates the content type of the payload. In network byte order.
PUT_PATH_LEN
is a 32-bit number indicating the length of the PUT path recorded in PUTPATH. As PUTPATH is optiona, this value may be zero. In network byte order.
GET_PATH_LEN
is a 32-bit number indicating the length of the GET path recorded in GETPATH. As PUTPATH is optiona, this value may be zero. In network byte order.
EXPIRATION
denotes the absolute 64-bit expiration date of the content. In microseconds since midnight (0 hour), January 1, 1970 in network byte order.
KEY
The key under which the PUT request wants to store content under.
PUTPATH
the variable-length PUT path. The path consists of a list of PATH_LEN peer IDs.
GETPATH
the variable-length PUT path. The path consists of a list of PATH_LEN peer IDs.
PAYLOAD
the variable-length resource record data payload. The contents are defined by the respective type of the resource record.

3. Security Considerations

4. GANA Considerations

GANA [GANA] is requested to create a "DHT Block Types" registry. The registry shall record for each entry:

The registration policy for this sub-registry is "First Come First Served", as described in [RFC8126]. GANA is requested to populate this registry as follows:

Number | Name    | Contact | References | Description
-------+---------+---------+------------+-------------------------

Figure 4

GANA is requested to amend the "GNUnet Signature Purpose" registry as follows:

Purpose | Name            | References | Description
--------+-----------------+------------+--------------------------
Figure 5

5. Test Vectors

6. Normative References

[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/info/rfc2119>.
[RFC8126]
Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, , <https://www.rfc-editor.org/info/rfc8126>.
[GANA]
GNUnet e.V., "GNUnet Assigned Numbers Authority (GANA)", , <https://gana.gnunet.org/>.
[R5N]
Evans, N. S. and C. Grothoff, "R5N: Randomized recursive routing for restricted-route networks", , <https://doi.org/10.1109/ICNSS.2011.6060022>.

Authors' Addresses

Martin Schanzenbach
GNUnet e.V.
Boltzmannstrasse 3
85748 Garching
Germany
Christian Grothoff
Berner Fachhochschule
Hoeheweg 80
CH-2501 Biel/Bienne
Switzerland
Bernd Fix
GNUnet e.V.
Boltzmannstrasse 3
85748 Garching
Germany