commit a139d3cafd16a7188aa4c24ec1d9b3eeb7ff8418
parent b3a4e43da5328292e6a6acb35d3b5d5f8623aba7
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Fri, 31 Dec 2021 12:12:34 +0100
hello wire format
Diffstat:
1 file changed, 82 insertions(+), 20 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -361,7 +361,45 @@ peer-public-key := [A-HJ-NP-Z1-9]+
The following is a non-normative example of a HELLO containing three
HELLO URIs:
</t>
- <!-- FIXME peer id type | length | id payload | 0-terminated strings for addresses -->
+ <figure anchor="figure_hello">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+0 8 16 24 32 40 48 56
++-----+-----+-----+-----+-----+-----+-----+-----+
+| TYPE | SIZE | NODEID /
++-----+-----+-----+-----+ (variable length) /
+/ /
++-----+-----+-----+-----+-----+-----+-----+-----+
+| ADDRESSES /
+/ (variable length) |
++-----+-----+-----+-----+-----+-----+-----+-----+
+ ]]></artwork>
+ </figure>
+ <dl>
+ <dt>TYPE</dt>
+ <dd>
+ is the type of HELLO. A 16-bit number in network byte order.
+ This value determines the type of the NODEID field.
+ </dd>
+ <dt>SIZE</dt>
+ <dd>
+ is the SIZE of the following fields NODEID and ADDRESSES in bytes.
+ In network byte order.
+ </dd>
+ <dt>NODEID</dt>
+ <dd>
+ is the Node ID of the peer which has generated this HELLO.
+ The length content of the NODEID is determined by the TYPE field.
+ Usually, this is a cryptographic public key which allows the
+ Underlay to uniquely identify and authenticate the node.
+ </dd>
+ <dt>ADDRESSES</dt>
+ <dd>
+ is a list of strings which can be used as addresses to contact the
+ node. The strings MUST be 0-terminated.
+ FIXME: Examples? Format determined?
+ </dd>
+ </dl>
+ <!-- FIXME peer id type | length | id payload | 0-terminated strings for addresses
<figure>
<artwork name="" type="" align="left" alt=""><![CDATA[
Y924NSHMMZ1N1SQCE5TXF93ED6S6JY311K0QT86G9WJC68F6XVZ0 \
@@ -371,7 +409,7 @@ Y924NSHMMZ1N1SQCE5TXF93ED6S6JY311K0QT86G9WJC68F6XVZ0 \
tor+onionv3://rasdflkjasdfliasduf.onion/
]]></artwork>
</figure>
-
+ -->
<!--
1) The current API is always fire+forget, it doesn't allow for flow
@@ -465,8 +503,37 @@ see how we can offer even the most minimal protections against peer
<section anchor="routing" numbered="true" toc="default">
<name>Routing</name>
- <section anchor="peer_selection" numbered="true" toc="default">
- <name>Peer selection</name>
+ <section>
+ <name>Distance Metric</name>
+ <t>
+ The distance between two keys <tt>KeyA</tt> and <tt>KeyB</tt> is
+ calculated relative to their shared prefix.
+ The prefix length is determined by the number of low order bits
+ that succesively match between <tt>KeyA</tt> and <tt>KeyB</tt>
+ starting from the first bit.
+ </t>
+ <t>
+ Relative to the (identical) bits in the shared prefix, differences
+ in the lower bits must count stronger than higher bits.
+ The resulting distance value is a FIXME: I think we wanted to
+ move to a 512-bit distance value. And I think we may have decided
+ to use a "regular" xor.
+ </t>
+ </section>
+
+
+ <section anchor="routing_table">
+ <name>Routing Table</name>
+ <t>
+ R5N stores the information of all connected peers in a a set of lists
+ similar to the k-buckets data structure of <xref target="Kademlia"/>.
+ The size of this set is determined by the number of connected peers.
+ A k-bucket contains a list of connected node IDs which share the same
+ bit prefix length with the local <tt>PeerID</tt>.
+ This number is called the <tt>index</tt> of the k-bucket.
+ The index which determines in which of the k-buckets to add a given
+ peer is calculated using the <tt>FindBucket</tt> procedure.
+ </t>
<t>
In order to select peers from the routing table which are suitable
destinations for sending messages, R5N uses a hybrid approach:
@@ -486,13 +553,8 @@ see how we can offer even the most minimal protections against peer
</t>
<!-- Fixme: We may want to propose our modified, optimized XOR metric here or reference Kademlia -->
<t>
- R5N stores the information of all connected peers in a a set of lists
- similar to the k-buckets data structure of <xref target="Kademlia"/>.
- The index which determines in which of the k lists to add a given peer
- is calculated using the <tt>FindBucket</tt> procedure.
- </t>
- <t>
- The buckets serve implicitly as a routing table for messages:
+ The buckets serve implicitly as a routing table for messages by
+ calculating the shortest distance from a message key to node ID.
In order to select a peer for a given message key and bloomfilter,
the <tt>PEER-SELECT</tt> is used (see <xref target="peer-select"/>.
</t>
@@ -516,16 +578,16 @@ END
]]></artwork>
</figure>
<t>
- R5N requires the following procedures for its routing table:
+ Apart from the k-bucket datastructure,
+ the R5N routing component MUST implement the following functions:
</t>
<dl>
<dt><tt>FindBucket(PeerID, Key) -> k-bucket as List</tt></dt>
<dd>
- The <tt>FindBucket</tt> procedure determines how many low
+ The <tt>FindBucket</tt> function determines how many low
order bits succesively match between a <tt>PeerID</tt> and a
<tt>Key</tt> starting from the first bit. The procedure returns
- the k-bucket for this index. It contains all connected nodes which
- share the same prefix length with <tt>PeerID</tt>.
+ the k-bucket for this index.
</dd>
<dt><tt>GetDistance(NodeKey_A, NodeKey_B) -> Distance as Integer</tt></dt>
<dd>
@@ -534,26 +596,26 @@ END
</dd>
<dt><tt>SelectClosestPeer(Key) -> NodeID</tt></dt>
<dd>
- This procedure determines the closest node ID to <tt>Key</tt>
+ This function determines the closest node ID to <tt>Key</tt>
of all connected nodes using <tt>GetDistance</tt>.
FIXME: Also has a bloomfilter. Isn't AmClosestNode simply
!SelectClosestPeer == myID ?
</dd>
<dt><tt>SelectRandomPeer() -> NodeID</tt></dt>
<dd>
- This procedure selects a random node ID from all connected
+ This function selects a random node ID from all connected
nodes. FIXME find elegant way to handle bloomfilter
</dd>
<dt><tt>SelectPeer(Key, NumberOfHops)</tt></dt>
<dd>
- This procedure selects a peer depending on the <tt>NumberOfHops</tt>
+ This function selects a peer depending on the <tt>NumberOfHops</tt>
Parameter. If <tt>NumberOfHops < NETWORK_SIZE_ESTIMATE</tt>
- this procedure returns <tt>SelectRandomPeer()</tt> and
+ this function returns <tt>SelectRandomPeer()</tt> and
<tt>SelectClosestPeer(Key)</tt> otherwise.
</dd>
<dt><tt>AmClosestNode(NodeID, Key, Bloom) -> true | false</tt></dt>
<dd>
- This procedure first determines which k-bucket contains the
+ This function first determines which k-bucket contains the
closest node IDs to <tt>Key</tt>.
Any node IDs which match the bloom filter are not considered.
If there is a node ID <tt>NodeID'</tt> in the k-bucket where
