[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Changed some stuff
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: Changed some stuff |
|
Date: |
Wed, 09 Jun 2021 22:17:22 +0200 |
This is an automated email from the git hooks/post-receive script.
elias-summermatter pushed a commit to branch master
in repository lsd0003.
The following commit(s) were added to refs/heads/master by this push:
new 9c42def Changed some stuff
9c42def is described below
commit 9c42def25d73b5b284eaf0f58d66d5e4ffbef07c
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Wed Jun 9 22:14:30 2021 +0200
Changed some stuff
---
draft-summermatter-set-union.pdf | Bin 489183 -> 516883 bytes
draft-summermatter-set-union.xml | 1394 +++++++++++++++++------------------
statemachine/full_state_machine.png | Bin 168364 -> 178403 bytes
statemachine/full_state_machine.svg | 2 +-
statemachine/full_state_machine.xml | 2 +-
statemachine/state_machine_full | 2 +-
statemachine/state_machine_full.png | Bin 56892 -> 57400 bytes
statemachine/state_machine_full.svg | 2 +-
8 files changed, 693 insertions(+), 709 deletions(-)
diff --git a/draft-summermatter-set-union.pdf b/draft-summermatter-set-union.pdf
index 779b351..c1708ed 100644
Binary files a/draft-summermatter-set-union.pdf and
b/draft-summermatter-set-union.pdf differ
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 682b76a..1d0f0b6 100644
--- a/draft-summermatter-set-union.xml
+++ b/draft-summermatter-set-union.xml
@@ -61,11 +61,11 @@
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
<t>
- This document describes a Byzantine fault-tolerant set
reconciliation protocol used to efficient and securely
+ This document describes a byzantine fault tolerant set
reconciliation protocol used to efficient and securely
compute the union of two sets across a network.
</t>
<t>
- This Byzantine fault-tolerant set reconciliation
+ This byzantine fault tolerant set reconciliation
protocol can be used in a variety of applications.
Our primary envisioned application domain is the
@@ -128,7 +128,7 @@
The objective here is to limit resources wasted on
malicious actors. Malicious actors could send malformed
messages, including malformed set elements, claim to
- have much larger numbers of valid set elements than the
+ have much larger numbers of valid set elements than they
actually hold, or request the retransmission of elements
that they have already received in previous
interactions. Bounding resources consumed by malicous
@@ -228,7 +228,7 @@
]]></artwork>
</figure>
<t>
- Is easy to see that the M(element) = (0,3) could be in the
BF below and M(element) = (0,2) can't be
+ It is easy to see that the M(element) = (0,3) could be in
the BF below and M(element) = (0,2) cannot be
in the BF below:
</t>
@@ -361,7 +361,7 @@ hashSum | HASHSUM | HASHSUM | HASHSUM |
HASHSUM | H..
<section anchor="ibv_operations_insert" numbered="true"
toc="default">
<name>Insert Element</name>
<t>
- To add an element to a IBF, the element is mapped to a
subset of k buckets using
+ To add an element to an IBF, the element is mapped to a
subset of k buckets using
the mapping function M as described in the <xref
target="bf" format="title" /> section introducing
BFs. For the buckets selected by the mapping function,
the counter is increased by one and the
IDSUM field is set to the XOR of the element ID and the
previously stored IDSUM. Furthermore,
@@ -643,24 +643,21 @@ hashSum | 0x0101 | 0x0101 | 0x5050 |
0x0000 |
<section anchor="ibf_format" numbered="true" toc="default">
<name>Wire format</name>
<t>
- To facilitate a reasonably CPU-efficient
- implementation, this specification requires the
- IBF counter always to use 8 bits.
- FIXME: I thought we lifted this constraint!?
- Fewer bits
- would result in a particularly inefficient
- implementation, while more bits are rarely useful
- as sets with so many elements should be
- represented using a larger number of buckets. This
- means the counter of this design can reach a
- minimum of -127 and a maximum of 127 before the
- counter reaches "infinity" (-128).
+ The counter size transmitted over the wire
+ varies between 1 and 64 bit, depending on the
+ maximum counter in the IBF. This variable counter
+ should cover most areas of application.
+ The bit length for the transmitted IBF
+ is defined in the header of the
+ <em><xref target="messages_ibf" format="title" /></em>
message
+ in the "IMCS" field as unsigned 8-bit integer.
+ For implementation details see section <xref
target="performance_counter_variable_size" format="title" />.
</t>
<t>
For the "IDSUM", we always use a 64-bit representation.
The IDSUM value MUST have sufficient entropy for the
mapping function M to yield reasonably random buckets
- even for very large values of L. With a 32 bit
+ even for very large values of L. With a 32 bit
value the chance that multiple elements may be mapped
to the same ID would be quite high, even for moderately
large sets. Using more than 64 bits would at best make
@@ -695,10 +692,10 @@ hashSum | 0x0101 | 0x0101 | 0x5050 |
0x0000 |
The ID is generated as 64-bit output from a <relref
section="2" target="RFC5869" displayFormat="of">HKDF construction</relref>
with HMAC-SHA512 as XTR and HMAC-SHA256 as PRF and
salt is set to the unsigned 64-bit equivalent of 0.
The output is then truncated to 64-bit.
- Its important that the elements can be redistributed
over the buckets in case the IBF does not
- decode. That's why the ID is salted with a random salt
given in the SALT field of this message.
- Salting is done by calculation the a random salt
modulo 64 (using only the lowest 6-bits of the salt)
- and do a bitwise right rotation of output of KDF by
the 6-bit salts numeric representation.
+ It is important that the elements can be redistributed
over the buckets in case the IBF does not
+ decode. That is why the ID is salted with a random
salt given in the SALT field of this message.
+ Salting is done by calculating a random salt modulo 64
(using only the lowest 6-bits of the salt)
+ and doing a bitwise right rotation of the output of
KDF by the 6-bit salts numeric representation.
</t>
<t>
Representation in pseudocode:
@@ -829,12 +826,16 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
a reasonable choice of L should be highly unlikely), one
can retry using a different
mapping function M.
</t>
+ <t>
+ In addition, when decoding the IBFs in the strata
estimator, it is possible to determine
+ on which side which part of the difference is. For this
purpose, the pure buckets with
+ counter 1 and -1 must be distinguished and assigned to the
respective side when decoding the IBFs.
+ </t>
</section>
</section>
-
<section anchor="modeofoperation" numbered="true" toc="default">
- <name>Mode of operation</name>
+ <name>Mode of Operation</name>
<t>
The set union protocol uses IBFs and SEs as primitives.
Depending on the state of the two sets there are different
strategies or operation modes how to efficiently
@@ -842,23 +843,22 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</t>
<t>
- The simplest mode is the "full" synchronization mode. The idea
is that if the difference between the sets of the two
+ The simplest mode is the "full" synchronisation mode. The idea
is that if the difference between the sets of the two
peers exceeds a certain threshold, the overhead to determine
which elements are different outweighs
the overhead of sending the complete set. In this case, the
most efficient method can be just to
exchange the full sets.
</t>
<t>
- <!-- TODO: Add smaller version -->
<eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/full_state_machine.png";>Link
to statemachine diagram</eref>
</t>
<t>
The second possibility is that the difference of the sets is
small compared to the set size.
- In this case, an efficient "delta" synchronization mode is
more efficient. These two possibilities given,
+ In this case, an efficient "differential" synchronisation mode
is more efficient. These two possibilities given,
the first steps of the protocol are used to determine which
mode MUST be used.
</t>
<t>
- Thus, the set synchronization protocol always begins with the
following operation mode independent steps.
+ Thus, the set synchronisation protocol always begins with the
following operation mode independent steps.
</t>
<t>
@@ -873,24 +873,23 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</t>
<section anchor="modeofoperation_full-sync" numbered="true"
toc="default">
<name>Full Synchronisation Mode</name>
-
<t>
- When the initiating peer decides to use the full
synchronisation mode and the set of the initiating peer is bigger than the set
of the receiving peer, the initiating
+ When the initiating peer decides to use the full
synchronisation mode and it is better that the other peer sends his set first,
the initiating
peer sends a <em><xref target="messages_request_full"
format="title" /></em> message, and transitions from <strong>Expecting
SE</strong> to the <strong>Full Receiving</strong> state.
- If the set of the initiating peer is smaller, it sends all
set elements to the other peer followed by the <em><xref
target="messages_full_done" format="title" /></em> message, and
- transitions into the <strong>Full Sending</strong> state.
+ If it has been determined that it is better that the
initiating peer sends his set first, the initiating peer sends a <em><xref
target="messages_send_full" format="title" /></em> message followed by all
+ set elements in <em><xref target="messages_full_element"
format="title" /></em> messages to the other peer, followed by the <em><xref
target="messages_full_done" format="title" /></em> message, and transitions
into the <strong>Full Sending</strong> state.
</t>
<t>
- <!-- TODO: Add smaller version -->
- <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg";>Link
to statemachine diagram</eref>
+ <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/state_machine_full.png";>Link
to statemachine diagram</eref>
</t>
<t><strong>The behavior of the participants the different
state is described below:</strong></t>
<dl>
<dt><strong>Expecting IBF:</strong></dt>
<dd>
If a peer in the <strong>Expecting IBF</strong> state
receives a <em><xref target="messages_request_full" format="title" /></em>
message from the other peer, the
- peer sends all the elements of its set followed by a
<em><xref target="messages_full_done" format="title" /></em> message to the
other peer, and transitions to the
- <strong>Full Sending</strong> state. If the peer
receives an <em><xref target="messages_full_element" format="title" /></em>
message, it processes the element and transitions to the <strong>Full
Receiving</strong> state.
+ peer sends all the elements of his set followed by a
<em><xref target="messages_full_done" format="title" /></em> message to the
other peer, and transitions to the
+ <strong>Full Sending</strong> state. If the peer
receives an <em><xref target="messages_send_full" format="title" /></em>
message followed by
+ <em><xref target="messages_full_element"
format="title" /></em> messages, the peer processes the element and transitions
to the <strong>Full Receiving</strong> state.
</dd>
<dt><strong>Full Sending:</strong></dt>
<dd>
@@ -898,20 +897,20 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
peer. As soon as a the <em><xref
target="messages_full_done" format="title" /></em> message is received, the
peer transitions into
the <strong>Finished</strong> state.
</dd>
- <dt><strong>Full Receiving (In code: Expecting IBF):
</strong></dt>
+ <dt><strong>Full Receiving: </strong></dt>
<dd>
While a peer is in the <strong>Full Receiving</strong>
state, it expects to continuously receive elements from the other
peer. As soon as a the <em><xref
target="messages_full_done" format="title" /></em> message is received, it sends
- the remaining elements (those it did not receive) from
its set to the other
+ the remaining elements (those it did not receive) from
his set to the other
peer, followed by a <em><xref
target="messages_full_done" format="title" /></em>.
After sending the last message, the peer transitions
into the <strong>Finished</strong> state.
</dd>
</dl>
</section>
<section anchor="modeofoperation_individual-elements"
numbered="true" toc="default">
- <name>Delta Synchronisation Mode</name>
+ <name>Differential Synchronisation Mode</name>
<t>
- When the initiating peer in the <strong>Expected
SE</strong> state decides to use the delta synchronisation mode, it
+ When the initiating peer in the <strong>Expected
SE</strong> state decides to use the differential synchronisation mode, it
sends a <em><xref target="messages_ibf" format="title"
/></em> to the receiving peer and transitions into the <strong>Passive
Decoding</strong> state.
</t>
<t>
@@ -928,8 +927,7 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element,
ibf_size)
is called the passive peer.
</t>
<t>
- <!-- TODO: Add smaler version -->
- <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_machine.png";>Link
to statemachine diagram</eref>
+ <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/differential_state_machine.png";>Link
to statemachine diagram</eref>
</t>
<t><strong>The behavior of the participants the different
states is described below:</strong></t>
<dl>
@@ -971,7 +969,7 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element,
ibf_size)
</dd>
<dt><em><xref target="messages_elements"
format="title" /></em> message:</dt>
<dd>
- When a new element message has been received
the peer checks if a corresponding
+ When a new <em><xref
target="messages_elements" format="title" /></em> message has been received the
peer checks if a corresponding
<em><xref target="messages_demand"
format="title" /></em> for the element has been sent
and the demand is still unsatisfied.
If the element has been demanded the peer
checks the element for validity, removes it from the list
@@ -1109,9 +1107,12 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
is always used.
The first case is when one of the peers announces having
an empty set. This is announced by setting
the SETSIZE field in the <em><xref target="messages_se"
format="title" /></em> to 0.
- The second case is if the application requests full
synchronization explicitly.
+ The second case is if the application requests full
synchronisation explicitly.
This is useful for testing and MUST NOT be used in
production.
</t>
+ <t>
+ <eref
target="https://git.gnunet.org/lsd0003.git/plain/statemachine/full_state_machine.png";>Link
to statemachine diagram</eref>
+ </t>
</section>
</section>
@@ -1179,7 +1180,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_ibf_description" numbered="true"
toc="default">
<name>Description</name>
<t>
- The IBF message contains a slice of the IBF.
+ The <xref target="messages_ibf" format="title" />
message contains a slice of the IBF.
</t>
<t>
The <em>IBF</em> message is sent at the start of the
protocol from the initiating peer in the transaction
@@ -1195,7 +1196,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE | SIZE |
+ | MSG SIZE | MSG TYPE | IBF SIZE |
+-----+-----+-----+-----+-----+-----+-----+-----+
|IMCS | OFFSET | SALT |
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -1216,7 +1217,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
the type of SETU_P2P_REQUEST_IBF as registered in
<xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>SIZE</dt>
+ <dt>IBF SIZE</dt>
<dd>
is a 32-bit unsigned integer which signals the
number of buckets in the IBF.
</dd>
@@ -1226,8 +1227,6 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
is required to store a single counter. This is
used for the unpacking function as described
in the <xref
target="performance_counter_variable_size" format="title" /> section.
</dd>
-
-
<dt>OFFSET</dt>
<dd>
is a 32-bit unsigned integer which signals the
offset to the following ibf slices in the original.
@@ -1246,9 +1245,9 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
by an array of HASHSUMS and ended with an
array of COUNTERS (details are described in section
<xref
target="performance_counter_variable_size" format="default"/>). Length of the
array is
defined by MIN( SIZE - OFFSET,
MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as
- 32768 divided by the BUCKET_SIZE which is
13-byte (104-bit).
+ 32768 divided by the BUCKET_SIZE which is
13-byte (104-bit). The minimal number of buckets in a single
+ IBF is 79.
</t>
-
<t>
To get the IDSUM field, all IDs hitting a
bucket are added up with a binary XOR operation.
See <xref target="ibf_format_id_generation"
format="title" /> details about ID generation.
@@ -1290,7 +1289,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</section>
<section anchor="messages_ibf_last" numbered="true" toc="default">
- <name>IBF</name>
+ <name>IBF Last</name>
<section anchor="messages_ibf_last_description"
numbered="true" toc="default">
<name>Description</name>
@@ -1317,13 +1316,13 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_elements_description"
numbered="true" toc="default">
<name>Description</name>
<t>
- The Element message contains an element that is
synchronized in the <xref target="modeofoperation_individual-elements"
format="title" />
+ The <em><xref target="messages_elements"
format="title" /></em> message contains an element that is synchronized in the
<xref target="modeofoperation_individual-elements" format="title" />
and transmits a full element between the peers.
</t>
<t>
This message is sent in the state <strong>Active
Decoding</strong> and <strong>Passive Decoding</strong>
as answer to a <em><xref target="messages_demand"
format="title" /></em> message from the remote peer.
- The Element message can also be received in the
<strong>Finish Closing</strong> or <strong>Finish Waiting</strong>
+ The <em><xref target="messages_elements"
format="title" /></em> message can also be received in the <strong>Finish
Closing</strong> or <strong>Finish Waiting</strong>
state after receiving a <em><xref
target="messages_done" format="title" /></em> message from the remote peer, in
this
case the peer changes to the <strong>Finished</strong>
state as soon as all demands for elements have been satisfied.
</t>
@@ -1387,9 +1386,9 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_offer_description" numbered="true"
toc="default">
<name>Description</name>
<t>
- The offer message is an answer to an <em><xref
target="messages_inquiry" format="title" /></em> message
+ The <em><xref target="messages_offer" format="title"
/></em> message is an answer to an <em><xref target="messages_inquiry"
format="title" /></em> message
and transmits the full hash of an element that has
been requested by the other peer.
- This full hash enables the other peer to check if the
element is really missing in its set and
+ This full hash enables the other peer to check if the
element is really missing in his set and
eventually sends a <em><xref target="messages_demand"
format="title" /></em> message for that element.
</t>
<t>
@@ -1424,7 +1423,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</dd>
<dt>HASH</dt>
<dd>
- is a SHA 512-bit hash of the element that is
requested with a inquiry message.
+ is a SHA 512-bit hash of the element that is
requested with a <em><xref target="messages_inquiry" format="title" /></em>
message.
</dd>
</dl>
</section>
@@ -1437,7 +1436,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_inquiry_description" numbered="true"
toc="default">
<name>Description</name>
<t>
- The Inquiry message is exclusively sent by the active
peer in <strong>Active Decoding</strong> state
+ The <em><xref target="messages_inquiry" format="title"
/></em> message is exclusively sent by the active peer in <strong>Active
Decoding</strong> state
to request the full hash of an element that is missing
in the active peers set. This is normally answered
by the passive peer with <em><xref
target="messages_offer" format="title" /></em> message.
</t>
@@ -1481,10 +1480,10 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_demand_description" numbered="true"
toc="default">
<name>Description</name>
<t>
- The demand message is sent in the <strong>Active
Decoding</strong> and in the <strong>Passive Decoding</strong>
+ The <em><xref target="messages_demand" format="title"
/></em> message is sent in the <strong>Active Decoding</strong> and in the
<strong>Passive Decoding</strong>
state. It is an answer to a received <em><xref
target="messages_offer" format="title" /></em> message
and is sent if the element described in the <em><xref
target="messages_offer" format="title" /></em> message
- is missing in the peers set. In the normal workflow
the answer to the demand message is an
+ is missing in the peers set. In the normal workflow
the answer to the <em><xref target="messages_demand" format="title" /></em>
message is an
<em><xref target="messages_elements" format="title"
/></em> message.
</t>
<t>
@@ -1527,7 +1526,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_done_description" numbered="true"
toc="default">
<name>Description</name>
<t>
- The done message is sent when all <em><xref
target="messages_demand" format="title" /></em> messages
+ The <em><xref target="messages_done" format="title"
/></em> message is sent when all <em><xref target="messages_demand"
format="title" /></em> messages
have been successfully satisfied and the set is
complete synchronized.
</t>
<t>
@@ -1565,11 +1564,11 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_full_done_description"
numbered="true" toc="default">
<name>Description</name>
<t>
- The full done message is sent in the <xref
target="modeofoperation_full-sync" format="title" />
+ The <em><xref target="messages_full_done"
format="title" /></em> message is sent in the <xref
target="modeofoperation_full-sync" format="title" />
to signal that all remaining elements of the set have
been sent. The message is received and sent in the
- <strong>Full Sending</strong> and in the <strong>Full
Receiving</strong> state. When the full done message is received
+ <strong>Full Sending</strong> and in the <strong>Full
Receiving</strong> state. When the <em><xref target="messages_full_done"
format="title" /></em> message is received
in <strong>Full Sending</strong> state the peer
changes directly into <strong>Finished</strong> state. In
- <strong>Full Receiving</strong> state receiving a full
done message initiates the sending of
+ <strong>Full Receiving</strong> state receiving a
<em><xref target="messages_full_done" format="title" /></em> message initiates
the sending of
the remaining elements that are missing in the set of
the other peer.
</t>
</section>
@@ -1603,25 +1602,27 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_request_full_description"
numbered="true" toc="default">
<name>Description</name>
<t>
- The request full message is sent by the initiating
peer in <strong>Expect SE</strong> state to the receiving peer if
+ The <em><xref target="messages_request_full"
format="title" /></em> message is sent by the initiating peer in <strong>Expect
SE</strong> state to the receiving peer, if
the operation mode "<xref
target="modeofoperation_full-sync" format="title" />" is
- determined as the better <xref
target="modeofoperation" format="title" /> and the set size of the initiating
peer is smaller
- than the set size of the receiving peer. The
initiating peer changes after sending the request full message into
+ determined to be the superior <xref
target="modeofoperation" format="title" /> and that it is the better choice
that
+ the other peer sends his elements first. The initiating
peer changes after sending the <em><xref target="messages_request_full"
format="title" /></em> message into
<strong>Full Receiving</strong> state.
</t>
<t>
- The receiving peer receives the Request Full message
in the <strong>Expecting IBF</strong>, afterwards the receiving peer
- starts sending its complete set in <xref
target="messages_full_element" format="title" /> messages to the initiating
peer.
+ The receiving peer receives the <em><xref
target="messages_request_full" format="title" /></em> message in the
<strong>Expecting IBF</strong>, afterwards the receiving peer
+ starts sending his complete set in <xref
target="messages_full_element" format="title" /> messages to the initiating
peer.
</t>
</section>
<section anchor="messages_request_full_structure"
numbered="true" toc="default">
<name>Structure</name>
<figure anchor="figure_request_full">
<artwork name="" type="" align="left" alt=""><![CDATA[
- 0 8 16 24 32
- +-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE |
- +-----+-----+-----+-----+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | REMOTE SET DIFF |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | REMOTE SET SIZE | LOCAL SET DIFF |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
</figure>
<t>where:</t>
@@ -1634,10 +1635,85 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<dd>
the type of SETU_P2P_REQUEST_FULL as registered in
<xref target="gana" format="title" /> in network byte order.
</dd>
+ <dt>REMOTE SET DIFF</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the remote (from the perspective of the
+ sending peer) set difference calculated with
strata estimator.
+ </dd>
+ <dt>REMOTE SET SIZE</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the total remote
+ (from the perspective of the sending peer) set
size.
+ </dd>
+ <dt>LOCAL SET DIFF</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the local
+ (from the perspective of the sending peer) set
difference calculated with strata estimator.
+ </dd>
</dl>
</section>
</section>
+
+ <section anchor="messages_send_full" numbered="true" toc="default">
+ <name>Send Full</name>
+
+ <section anchor="messages_send_full_description"
numbered="true" toc="default">
+ <name>Description</name>
+ <t>
+ The <em><xref target="messages_send_full"
format="title" /></em> message is sent by the initiating peer in <strong>Expect
SE</strong> state to the receiving peer if
+ the operation mode "<xref
target="modeofoperation_full-sync" format="title" />" is
+ determined as superior <xref target="modeofoperation"
format="title" /> and that it is the better choice that the
+ peer sends his elements first. The initiating peer
changes after sending the <em><xref target="messages_request_full"
format="title" /></em> message into
+ <strong>Full Sending</strong> state.
+ </t>
+ <t>
+ The receiving peer receives the <em><xref
target="messages_send_full" format="title" /></em> message in the
<strong>Expecting IBF</strong> state, afterwards the receiving peer
+ changes into <strong>Full Receiving</strong> state and
expects to receive the set of the remote peer.
+ </t>
+ </section>
+ <section anchor="messages_send_full_structure" numbered="true"
toc="default">
+ <name>Structure</name>
+ <figure anchor="figure_send_full">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | REMOTE SET DIFF |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | REMOTE SET SIZE | LOCAL SET DIFF |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ]]></artwork>
+ </figure>
+ <t>where:</t>
+ <dl>
+ <dt>MSG SIZE</dt>
+ <dd>
+ is a 16-bit unsigned integer in network byte order
which describes the message size in bytes and header included.
+ </dd>
+ <dt>MSG TYPE</dt>
+ <dd>
+ the type of SETU_P2P_REQUEST_FULL as registered in
<xref target="gana" format="title" /> in network byte order.
+ </dd>
+ <dt>REMOTE SET DIFF</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the remote (from the perspective of the sending peer)
+ set difference calculated with strata estimator.
+ </dd>
+ <dt>REMOTE SET SIZE</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the total remote (from the perspective
+ of the sending peer) set size.
+ </dd>
+ <dt>LOCAL SET DIFF</dt>
+ <dd>
+ is a 32-bit unsigned integer in network byte order
which represents the local (from the perspective of the sending peer)
+ set difference calculated with strata estimator.
+ </dd>
+ </dl>
+ </section>
+ </section>
+
+
<section anchor="messages_se" numbered="true" toc="default">
<name>Strata Estimator</name>
@@ -1652,9 +1728,16 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</t>
<t>
When the initiating peer receives the strata estimator
the peer decides which <xref target="modeofoperation" format="title" /> to use
- for the synchronization. Depending on the size of the
set difference and the <xref target="modeofoperation" format="title" /> the
initiating peer
+ for the synchronisation. Depending on the size of the
set difference and the <xref target="modeofoperation" format="title" /> the
initiating peer
changes into <strong>Full Sending</strong>,
<strong>Full Receiving</strong> or <strong>Passive Decoding</strong> state.
</t>
+ <t>
+ The <em><xref target="messages_se" format="title"
/></em> message can contain one, two, four or eight strata estimators with
different salts, depending on the initial size of the sets.
+ More details can be found in section <xref
target="performance_multi_se" format="title" />.
+ </t>
+ <t>
+ The IBFs in a strata estimator always have 79 buckets.
The reason why can be found in Summermatter's work. <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ </t>
</section>
<section anchor="messages_se_structure" numbered="true"
toc="default">
<name>Structure</name>
@@ -1662,7 +1745,7 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE | SETSIZE
+ | MSG SIZE | MSG TYPE | SEC | SETSIZE
+-----+-----+-----+-----+-----+-----+-----+-----+
SETSIZE | SE-SLICES
+-----+-----+-----+-----+
@@ -1680,13 +1763,19 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<dd>
the type of SETU_P2P_SE as registered in <xref
target="gana" format="title" /> in network byte order.
</dd>
+ <dt>SEC</dt>
+ <dd>
+ is a 8-bit unsigned integer in network byte order
which indicates how many strata estimators
+ with different salts are attached to the message.
Valid values are 1,2,4 or 8, more details can be found
+ in the section <xref target="performance_multi_se"
format="title" />.
+ </dd>
<dt>SETSIZE</dt>
<dd>
is a 64-bit unsigned integer that is defined by
the size of the set the SE is
</dd>
<dt>SE-SLICES</dt>
<dd>
- is variable in size and contains the same
structure as the IBF-SLICES field in the IBF message.
+ is variable in size and contains the same
structure as the IBF-SLICES field in the <xref target="messages_ibf"
format="title" /> message.
</dd>
</dl>
</section>
@@ -1715,17 +1804,17 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="messages_full_element_description"
numbered="true" toc="default">
<name>Description</name>
<t>
- The full element message is the equivalent of the
<xref target="messages_elements" format="title" /> message in
+ The <em><xref target="messages_full_element"
format="title" /></em> message is the equivalent of the <xref
target="messages_elements" format="title" /> message in
the <xref target="modeofoperation_full-sync"
format="title" />. It contains a complete element that is missing
in the set of the peer that receives this message.
</t>
<t>
- The full element message is exclusively sent in the
transitions <strong>Expecting IBF</strong> -> <strong>Full Receiving</strong>
and
+ The <em><xref target="messages_full_element"
format="title" /></em> message is exclusively sent in the transitions
<strong>Expecting IBF</strong> -> <strong>Full Receiving</strong> and
<strong>Full Receiving</strong> ->
<strong>Finished</strong>. The message is only received in the <strong> Full
Sending</strong> and
<strong>Full Receiving</strong> state.
</t>
<t>
- After the last full element message has been sent the
<xref target="messages_full_done" format="title" /> message
+ After the last <em><xref
target="messages_full_element" format="title" /></em> message has been sent the
<em><xref target="messages_full_done" format="title" /></em> message
is sent to conclude the full synchronisation of the
element sending peer.
</t>
</section>
@@ -1780,7 +1869,6 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
</section>
</section>
-<!-- CORRECT -->
<section anchor="performance" numbered="true" toc="default">
<name>Performance Considerations</name>
<section anchor="performance_formulas" numbered="true"
toc="default">
@@ -1788,31 +1876,31 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<section anchor="performance_formulas_operationmode"
numbered="true" toc="default">
<name>Operation Mode</name>
<t>
- The decision which mode of operations is used is
described by the following code. The function is complex
- and more detailed explanations can be found in the
accompanying thesis.<xref target="byzantine_fault_tolerant_set_reconciliation"
format="default"/>
+ The decision which <xref target="modeofoperation"
format="title"/> is used is described by the following code. The function is
complex.
+ More detailed explanations can be found in the
accompanying thesis.<xref target="byzantine_fault_tolerant_set_reconciliation"
format="default"/>
</t>
<t>
- The function takes as input the avg element size, the
local setsize, the remote setsize, the
- by the strata estimator calculated difference for
local and remote set,
+ The function takes as input the average element size,
the local setsize, the remote setsize, the
+ by the strata estimator calculated difference for
local and remote set
and the bandwith/roundtrips tradeoff.
- The function returns the exact mode of operation as
output: FULL_SYNC_REMOTE_SENDING_FIRST
- if it is optimal that the other peer transmits its
elements first, FULL_SYNC_LOCAL_SENDING_FIRST
+ The function returns the exact <xref
target="modeofoperation" format="title"/> as output:
FULL_SYNC_REMOTE_SENDING_FIRST
+ if it is optimal that the other peer transmits his
elements first, FULL_SYNC_LOCAL_SENDING_FIRST
if it is optimal that the elements are transmitted to
the other peer directly and
DIFFERENTIAL_SYNC if the differential synchronisation
is optimal.
</t>
<t>
The constant IBF_BUCKET_NUMBER_FACTOR is always 3 and
IBF_MIN_SIZE is 37. The method for deriving
- this can be found in Elias Summermatter's Thesis.
<xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ this can be found in Summermatter's work. <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
</t>
<figure anchor="performance_formulas_operationmode_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding
fails
-# RTT_MIN_FULL = 2: Minimal Round Trips used for full sync (always 2 or 2.5)
+# RTT_MIN_FULL = 2: Minimal round trips used for full syncronisation (always 2
or 2.5)
# IBF_MIN_SIZE = 37: The minimal size of an IBF
# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol
# INPUTS:
-# avg_element_size: The avg element size
+# avg_element_size: The average element size
# local_set_size: The initial local setsize
# remote_set_size: The remote setsize
# est_local_set_diff: the estimated local set difference calculated by the
strata estimator
@@ -1898,7 +1986,7 @@ FUNCTION decide_operation_mode(avg_element_size,
<section anchor="performance_formula_ibf_parameters"
numbered="true" toc="default">
<name>IBF Size</name>
<t>
- The in this section described functions calculate the
initial size (initial_ibf_size) optimal size
+ The functions, described in this section, calculate
the initial size (initial_ibf_size) optimal size
and in case of decoding failure the next bigger IBF
size (get_next_ibf_size).
</t>
<t>
@@ -1943,25 +2031,24 @@ FUNCTION END
</t>
</section>
</section>
- <!-- CORRECT -->
<section anchor="performance_counter_variable_size"
numbered="true" toc="default">
- <name>Counter variable size</name>
+ <name>Variable Counter Size</name>
<t>
Since the optimal number of bytes a counter in the IBF
contains is very variable and varies
due to different parameters. Details are described in the
BSC thesis
- by Elias Summermatter, BFH 2021<xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ by Summermatter <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
Therefore a compression algorithm has been implemented,
which always creates the IBF counter in optimal size.
and thus minimizes the bandwidth needed to transmit the
IBF.
</t>
<t>
A simple algorithm is used for the compression. In a first
step it is determined, which is the largest counter
- and how many bits are needed to store it. In a second step
for every counter of every bucket the counter
+ and how many bits are needed to store it. In a second step
for every counter of every bucket, the counter
is stored in the bits determined in the first step and
these are concatenated.
</t>
<t>
- Three individual functions are used for this purpose. The
first one is a function that iterates over each bucket of the
- bucket of the IBF to get the maximum counter in the IBF.
As second it needs
- a function that compresses the counter of the IBF and
thirdly a function that decompresses the IBF.
+ Three individual functions are used for this purpose. The
first one is a function that iterates over each bucket of
+ the IBF to get the maximum counter in the IBF. As second
it needs
+ a function that compresses the counter of the IBF and
thirdly a function that decompresses the counter.
</t>
<figure anchor="performance_counter_variable_size_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -1969,7 +2056,7 @@ FUNCTION END
# INPUTS:
# ibf: The IBF
# OUTPUTS:
-# returns: minimal amount of bytes required to store the counter
+# returns: Minimal amount of bytes required to store the counter
FUNCTION ibf_get_max_counter(ibf)
max_counter=0
@@ -1982,9 +2069,9 @@ FUNCTION ibf_get_max_counter(ibf)
# INPUTS:
# ibf: The IBF
# offset: The offset which defines the starting point from which bucket the
compress operation starts
-# count: The number of buckets to in the array that will be compressed
+# count: The number of buckets in the array that will be compressed
# OUTPUTS:
-# returns: An byte array of compressed counters to send over the network
+# returns: A byte array of compressed counters to send over the network
FUNCTION pack_counter(ibf, offset, count)
counter_bytes = ibf_get_max_counter(ibf)
@@ -2037,7 +2124,7 @@ FUNCTION pack_counter(ibf, offset, count)
# INPUTS:
# ibf: The IBF
# offset: The offset which defines the starting point from which bucket the
compress operation starts
-# count: The number of buckets to in the array that will be compressed
+# count: The number of buckets in the array that will be compressed
# counter_bit_length: The bit length of the counter can be found in the ibf
message in the ibf_counter_bit_length field
# packed_data: A byte array which contains the data packed with the
pack_counter function
# OUTPUTS:
@@ -2091,6 +2178,54 @@ FUNCTION unpack_counter(ibf, offset, count,
counter_bit_length, packed_data)
]]></artwork>
</figure>
</section>
+ <section anchor="performance_multi_se" numbered="true"
toc="default">
+ <name>Multi Strata Estimators</name>
+ <t>
+ In order to improve the precision of the estimates, not
only one strata estimator
+ is transmitted for larger sets. One, two, four or eight
strata estimators can be
+ transferred. Transmitting multiple strata estimators has
the disadvantage that
+ additional bandwidth will be used, so despite the higher
precision, it is not
+ always optimal to transmit eight strata estimators.
Therefore, the following
+ rules are used, which are based on the average element
size multiplied by the number
+ of elements in the set. This value is denoted as "b" in
the table:
+ </t>
+ <dl>
+ <dt>SEs</dt>
+ <dd>Rule</dd>
+ <dt>1</dt>
+ <dd>b < 68kb</dd>
+ <dt>2</dt>
+ <dd>b > 68kb</dd>
+ <dt>4</dt>
+ <dd>b > 269kb</dd>
+ <dt>8</dt>
+ <dd>b > 1'077kb</dd>
+ </dl>
+ <t>
+ When creating multiple strata estimators, it is important
to salt the keys for the IBFs in the strata
+ estimators differently, using the following bit rotation
based salting method:
+ </t>
+ <figure anchor="performance_multi_se_salting_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+
+# Inputs:
+# value: Input value to salt (needs to be 64 bit unsigned)
+# salt: Salt to salt value with; Should always be ascending and start at zero
+ i.e. SE1 = Salt 0; SE2 = Salt 1 etc.
+# Output:
+# Returns: Salted value
+
+FUNCTION se_key_salting(value, salt)
+ s=(salt * 7) % 64
+ return (value >> s) | (value << (64 - s))
+
+ ]]></artwork>
+ </figure>
+ <t>
+ Performance study and details about the reasoning for the
used methods can be found in the work of Summermatter.
+ <xref target="byzantine_fault_tolerant_set_reconciliation"
format="default"/>
+ </t>
+ </section>
</section>
@@ -2128,118 +2263,355 @@ FUNCTION unpack_counter(ibf, offset, count,
counter_bit_length, packed_data)
It is important to close and purge connections after a given
timeout
to prevent draining attacks.
</t>
-
<section anchor="security_generic_functions" numbered="true"
toc="default">
- <name>Generic functions</name>
+ <name>General Security Check</name>
<t>
- Some functions are used in most of the messages described in
the State
- section.
+ In this section general checks are described which should be
applied to multiple states.
</t>
- <section anchor="security_generic_functions_missing_message"
numbered="true" toc="default">
- <name>Duplicated or Missing Message detection</name>
+
+ <section
anchor="security_generic_functions_check_byzantine_boundaries" numbered="true"
toc="default">
+ <name>Byzantine Boundaries</name>
<t>
- Most of the messages received need to be checked that they
are not
- received multiple times. This is solved with a global
store (message)
- and the following code
+ To restrict an attacker there should be an upper and lower
bound defined and check
+ at the beginning of the protocol, based
+ on prior knowledge, for the number of elements.
+ The lower byzantine bound can be, for example, the number
of elements the
+ other peer had in his set at the last contact.
+ The upper byzantine bound can be a practical maximum e.g.
the number
+ of e-voting votes, in Switzerland.
</t>
<figure
anchor="security_generic_functions_missing_message_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
+# Input:
+# rec: Number of elements in remote set
+# rsd: Number of elements differ in remote set
+# lec: Number of elements in local set
+# lsd: Number of elements differ in local set
+# UPPER_BOUND: Given byzantine upper bound
+# LOWER_BOUND: Given byzantine lower bound
+# Output:
+# returns TRUE if parameters in byzantine bounds otherwise returns FALSE
+FUNCTION check_byzantine_bounds (rec,rsd,lec,lsd)
+ IF (rec + rsd > UPPER_BOUND)
+ RETURN FALSE
+ IF END
+ IF (lec + lsd > UPPER_BOUND)
+ RETURN FALSE
+ IF END
+ IF (rec < LOWER_BOUND)
+ RETURN FALSE
+ IF END
+ RETURN TRUE
+FUNCTION END
+ ]]></artwork>
+ </figure>
+ <t>
+ For the byzantine upper bound checks to function
flawlessly, it needs to be ensured that the estimates of the set size
+ difference added together never exceed the set byzantine
upper bound. This could for example happen
+ if the strata estimator overestimates the set difference.
+ </t>
+ </section>
-# Initially creates message store
-# OUTPUTS:
-# returns: Store
-FUNCTION createStore()
- store = {}
- return store
+ <section anchor="security_generic_functions_check_valid_state"
numbered="true" toc="default">
+ <name>Valid State</name>
+ <t>
+ To harden the protocol against attacks, controls were
introduced in the improved
+ implementation that check for each message whether the
message was received
+ in the correct state. This is central so that an attacker
finds as little attack
+ surface as possible and makes it more difficult for the
attacker to send the
+ protocol into an endless loop, for example.
+ </t>
+ <t>
+ The following function is executed every time a message is
processed.
+ The array allowed_state, which contains a list of allowed
messages for
+ the current state of the application.
+ </t>
+ <figure
anchor="security_generic_functions_check_valid_state_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+# Input:
+# allowed_states: A array containing all states in which the message can be
received
+# state: The state in which the protocol is in
+# Output:
+# Returns TRUE if message is valid in state and FALSE if not
+
+FUNCTION check_valid_state (allowed_states, state)
+ FOR (allowed_state in allowed_states)
+ IF (allowed_state == state)
+ RETURN TRUE
+ END IF
+ FOR END
+ RETURN FALSE
+FUNCTION END
+ ]]></artwork>
+ </figure>
+ </section>
+ <section anchor="security_generic_functions_mfc" numbered="true"
toc="default">
+ <name>Message Flow Control</name>
+ <t>
+ For most messages received and sent there needs be a check
in place that checks
+ that a message is not received multiple times. This is
solved with a global store (message)
+ and the following code
+ </t>
+ <t>
+ The sequence in which messages are received and sent is
arranged in a chain.
+ The messages are dependent on each other. There are
dependencies that are
+ mandatory, e.g. for a sent "Demand" message, an "Element"
message must
+ always be received. But there are also messages for which
a response is
+ not mandatory, e.g. the "Inquiry" message is only followed
by an
+ "Offer" message, if the corresponding element is in the
set. Due to this
+ fact, checks can be installed to verify compliance with
the following chain.
+ </t>
+ <figure anchor="security_generic_functions_mfc_chain">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+Chain for elements +---------+ +---------+ +---------+
+---------+
+NOT in IBF decoding | INQUIRY | ---> | OFFER | ===> | DEMAND | ===> |
ELEMENT |
+peers set +---------+ +---------+ +---------+
+---------+
-# Returns adds a message to the store
-# INPUTS:
-# store: store to add key to
-# key: unique key to add
-# OUTPUTS:
-# returns: Returns true if element could be added to store.
-# Returns false if element could not be added to store.
-FUNCTION addMessageToStore(store, key)
- IF store.get(key) != NULL
- return FALSE
- store.set(key) = 1
- return TRUE
-
-# Check if hash is in store
-# INPUTS:
-# store: Store to search
-# key: Unique key to add
-# OUTPUTS:
-# returns: Returns true if key is in store
-# Returns false if key is not in store
-FUNCTION markElementAsReceived(store, key)
- IF store.get(key) != NULL || store.get(key) != 1
- return FALSE
- store.update(key, 0)
- return TRUE
-
-# Check if all elements added to store are also received
-# INPUTS:
-# store: Store to check for completion
-# OUTPUTS:
-# returns: Returns true if key all messages added are received
-# Returns false if one or more messages are not received
-FUNCTION isStoreComplete(store)
- FOR elements in store
- IF elements.value != 0:
- return FALSE
- ENDIF
- ENDFOR
- return TRUE
-
-# Returns the number of message received
-# INPUTS:
-# store: Store to count
-# OUTPUTS:
-# returns: Returns true if key all messages added are received
-# Returns false if one or more messages are not received
-FUNCTION getNumberOfMessage(store)
- return store.size()
+Chain for elements +---------+ +---------+ +---------+
+in IBF decoding | OFFER | ---> | DEMAND | ===> | ELEMENT |
+peers set +---------+ +---------+ +---------+
+ --->: Answer not mandatory
+ ===>: Always answer needed.
]]></artwork>
</figure>
+ <t>
+ A possible implementation of the check in pseudocode could
look as follows:
+ </t>
+ <figure anchor="security_generic_functions_mfc_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+# ValidStates:
+# The following message states are used to track the message flow.
+# - NOT_INITIALIZED: Fresh initialized value
+# - SENT: Element has been sent
+# - EXPECTED: Element is expected
+# - RECEIVED: Element is received
+
+# Function to initialize new store
+# Output:
+# Returns empty store
+FUNCTION initialize_store()
+ RETURN {}
+FUNCTION END
+
+# Function to initialize a store element
+# Output:
+# Returns an empty element for the store
+FUNCTION initialize_element()
+ RETURN {
+ INQUIRY: NOT_INITIALIZED,
+ OFFER: NOT_INITIALIZED,
+ DEMAND: NOT_INITIALIZED,
+ ELEMENT: NOT_INITIALIZED
+ }
+FUNCTION END
+
+# Function called every time a new message is transmitted to other peer
+# Input:
+# store: Store created by the initialize_store() function
+# message_type: The message that was sent type e.g. INQUIRY or DEMAND
+# hash: The hash of the element which is sent
+# Output:
+# Returns TRUE if the message flow was followed, otherwise FALSE
+FUNCTION send(store, message_type, hash)
+
+ IF NOT store.contains(hash)
+ store_element = initialize_element()
+ ELSE
+ store_element = store.get(hash)
+ END IF
+
+ CASE based on message_type
+ CASE INQUIRY
+ IF store_element.INQUIRY == NOT_INITIALIZED
+ store_element.INQUIRY = SENT
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE OFFER
+ IF store_element.OFFER == NOT_INITIALIZED
+ store_element.OFFER = SENT
+ store_element.DEMAND = EXPECTED
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE DEMAND
+ IF store_element.DEMAND == NOT_INITIALIZED AND
+ (store_element.INQUIRY == SENT OR
+ store_element.INQUIRY == NOT_INITIALIZED)
+ store_element.DEMAND = SENT
+ store_element.ELEMENT = EXPECTED
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE ELEMENT
+ IF store_element.ELEMENT == NOT_INITIALIZED AND
+ store_element.OFFER == SENT
+ store_element.ELEMENT = SENT
+ ELSE
+ RETURN FALSE
+ END IF
+ DEFAULT
+ RETURN FALSE
+ CASE END
+ store.put(hash,store_element)
+ RETURN TRUE
+FUNCTION END
+
+# Function called every time a new message is received from the other peer
+# Input:
+# store: Store created by the initialize_store() function
+# message_type: The message that was received type e.g. INQUIRY or DEMAND
+# hash: The hash of the element which is received
+# Output:
+# Returns TRUE if the message flow was followed, otherwise FALSE
+FUNCTION receive (store, message_type, hash)
+ IF NOT store.contains(hash)
+ store_element = initialize_element()
+ ELSE
+ store_element = store.get(hash)
+ END IF
+
+ CASE based on message_type
+ CASE INQUIRY
+ IF store_element.INQUIRY == NOT_INITIALIZED
+ store_element.INQUIRY = RECEIVED
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE OFFER
+ IF store_element.OFFER == NOT_INITIALIZED
+ store_element.OFFER = RECEIVED
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE DEMAND
+ IF store_element.DEMAND == EXPECTED AND
+ store_element.OFFER == SENT
+ store_element.DEMAND = RECEIVED
+ ELSE
+ RETURN FALSE
+ END IF
+ CASE ELEMENT
+ IF store_element.ELEMENT == EXPECTED AND
+ store_element.DEMAND == SENT
+ store_element.ELEMENT = RECEIVED
+ ELSE
+ RETURN FALSE
+ END IF
+ DEFAULT
+ RETURN FALSE
+ CASE END
+ store.put(hash,store_element)
+ RETURN TRUE
+FUNCTION END
+
+# Function called when the union operation is finished to ensure that all
demands have
+# been fulfilled
+# Input:
+# store: Store created by the initialize_store() function
+# Output:
+# Returns TRUE if all demands have been fulfilled otherwise FALSE
+FUNCTION check_if_synchronisation_is_complete(store):
+ FOR element in store.getAll()
+ IF element.ELEMENT == EXPECTED OR
+ element.DEMAND == EXPECTED
+ RETURN FALSE
+ IF END
+ FOR END
+ RETURN TRUE
+FUNCTION END
+
+ ]]></artwork>
+ </figure>
+ <t>
+ This is based on the work of Summermatter. More details
can be found in his thesis <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ </t>
</section>
- <section anchor="security_generic_functions_element_nr"
numbered="true" toc="default">
- <name>Store Remote Peers Element Number</name>
- <t>
- To prevent an other peer from requesting the same set multiple
times,
- it is important to memorize the number of elements a peer had
in previous
- reconciliation sessions.
- </t>
- <figure anchor="security_generic_functions_element_nr_code">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-# Get the number of elements from previous sync
-# INPUTS:
-# client_id: A unique id that identifies the client
-# OUTPUTS:
-# returns: The number of elements from last sync
-FUNCTION number_elements_last_sync(client_id)
- IF number_store.get(clientID)
- return number_store.get(client_id)
- ENDIF
- return 0
+ <section
anchor="security_generic_functions_active_passive_switches" numbered="true"
toc="default">
+ <name>Limit Active/Passive Decoding changes</name>
+ <t>
+ The limitation of the maximum allowed active/passive
changes during differential synchronisation is key
+ to security. By limiting the maximum rounds in
differential synchronisation an attacker can not waste
+ unlimited amount of resources by just pretending an IBF
does not decode.
+ </t>
+ <t>
+ The question after how many active/passive switches it can
be assumed that the other peer is not honest,
+ depends on many factors and can only be solved
probabilistically. In the work of Summermatter <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ this is described in detail. From this work it is
concluded that the probability of decoding failure is about
+ 15% for each round. The probability that there will be n
active/passive changes is given by 0.15^{round number}.
+ Which means that after about 30 active/passive switches it
can be said with a certainty of 2^80 that one of the peers
+ is not following the protocol. It is reasonable that a
maximum of 30 active/passive changes should be set.
+ </t>
+ </section>
-# Updates the stored remote
-# INPUTS:
-# client_id: A unique id that identifies the client
-# remote_setsize: The set size of the remote peer
-# OUTPUTS:
-# returns: The number of elements from last sync
-FUNCTION save_number_of_elements_last_sync(client_id, remote_setsize)
- number_store.update(clientID, remote_setsize)
- ]]></artwork>
- </figure>
- </section>
- </section>
+ <section
anchor="security_generic_functions_full_plausibility_check" numbered="true"
toc="default">
+ <name>Full Synchronisation Plausibility Check</name>
+ <t>
+ An attacker can try to use up a peer's bandwidth by
pretending that the peer
+ needs full synchronisation, even if the set difference is
very small and the attacker
+ only has a few (or even zero) elements that are not
already synchronised.
+ In such a case, it would be ideal, if the plausibility
could already be checked
+ during full synchronisation as to whether the other peer
was honest or not with
+ regard to the estimation of the set size difference and
thus the choice of mode
+ of operation.
+ </t>
+ <t>
+ In order to calculate this plausibility, in Summmermatters
paper <xref target="byzantine_fault_tolerant_set_reconciliation"
format="default"/>
+ a formula was developed, which depicts the probability
with which one
+ can calculate the corresponding plausibility based on the
number of
+ new and repeated elements after each received element.
+ </t>
+ <t>
+ Besides this approach from probability theory, there is an
additional check
+ that can be made. After the entire set has been
transferred to the other peer,
+ no known elements may be returned by the second peer,
since the second peer
+ should only return the elements that are missing from the
initial peer's set.
+ </t>
+ <t>
+ This two approaches are implemented in the following
pseudocode:
+ </t>
+
+ <figure
anchor="security_generic_functions_full_plausibility_check_code">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+# Input:
+# SECURITY_LEVEL: The security level used e.g. 2^80
+# state: The statemachine state
+# rs: Estimated remote set difference
+# lis: Number of elements in set
+# rd: Number of duplicated elements received
+# rf: Number of fresh elements received
+# Output:
+# Returns TRUE if full syncronisation is plausible and FALSE otherwise
+
+FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf)
+ security_level_lb = 1 / SECURITY_LEVEL
+ IF (FULL_SENDING == state)
+ IF (rd > 0)
+ RETURN FALSE
+ IF END
+ IF END
+ IF (FULL_RECEIVING == state)
+ IF (0 <= rs)
+ rs = 1
+ IF END
+ base = (1 - ( rs / (lis + rs)))
+ exponent = (rd - (rf * (lis/rs)))
+ value = POWER(base, exponent)
+ IF ((value < security_level_lb) || (value > SECURITY_LEVEL)
+ RETURN FALSE
+ IF END
+ IF END
+ RETURN TRUE
+FUNCTION END
+ ]]></artwork>
+ </figure>
+ </section>
+ </section>
<section anchor="security_states" numbered="true" toc="default">
<name>States</name>
@@ -2257,209 +2629,28 @@ FUNCTION save_number_of_elements_last_sync(client_id,
remote_setsize)
<dt><xref target="messages_request_full" format="title"
/></dt>
<dd>
<t>
- It needs to be checked that the full synchronisation is
- plausible according to the formula deciding which
operation mode
- is applicable. This is achieved by calculating the
upper and lower
- boundaries of the number of elements in the other
peers set.
- The lower boundary of number of elements can be easily
- memorized as result from the last synchronisation and
the upper
- boundary can be estimated with prior knowledge of the
maximal
- plausible increase of elements since the last
reconciliation and
- the maximal plausible number of elements.
+ It needs to be checked that the full synchronisation
mode with receiving peer
+ sending first, is plausible according to the algorithm
deciding which operation mode
+ is applicable as described in <xref
target="performance_formulas_operationmode" format="default"/>.
</t>
- <figure
anchor="security_states_expecting_ibf_request_full_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# client_id: Unique remote peer id
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# initial_local_size: The initial local setsize
-# set_diff: The set difference calculated with the strata estimator
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_request_full(client_id, remote_setsize,
local_setsize, initial_local_size, set_diff)
-
- last_setsize = getNumberOfElementsLastSync(clientId)
- IF remote_setsize > last_setsize
- return FALSE
- ENDIF
-
- # Update number of elements in store
- save_number_of_elements_last_sync(client_id, remote_setsize)
-
- # Check for max plausible set size as defined on use case basis (can be
infinite)
- plausible_setsize = getMaxPlausibleSetSize()
- IF remote_setsize > plausible_setsize
- return FALSE
- ENDIF
-
- # Check for correct operation mode operation_mode function is described in
performance section
- IF decide_operation_mode(initial_local_size, remote_setsize, set_diff) !=
"FULL"
- return FALSE
- ENDIF
-
- # Check that the other peer is honest and we should send our set
- IF decide_full_sending(local_size, initial_remote_setsize ) != "LOCAL"
- return FALSE
- ENDIF
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_ibf" format="title" /></dt>
<dd>
<t>
- It is important to define a threshold to limit
- the maximal number of IBFs that are expected from
the other peer.
- This maximal plausible size can be calculated with
the known inputs:
- number of elements in the local set and the
predefined applications upper
- limit, as described in the <xref
target="performance" format="title" /> section.
- That the other peer chooses the correct mode of
operation MUST
- be checked as described in the section above.
+ It needs to be checked that the differential
synchronisation mode is plausible according
+ to the algorithm deciding which operation mode
+ is applicable as described in <xref
target="performance_formulas_operationmode" format="default"/>.
</t>
- <figure
anchor="security_states_expecting_ibf_message_ibf_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# initial_local_size: The initial local setsize
-# set_diff: The set difference calculated with the strata estimator
-# ibf_msg: received ibf message
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_ibf(remote_setsize, local_setsize,
initial_local_size, set_diff, ibf_msg)
- IF is_undefined(number_buckets_left)
- number_buckets_left = get_bucket_number(remote_setsize, local_setsize,
initial_local_size, set_diff, ibf_msg)
- ENDIF
- number_buckets_left --
- IF number_buckets_left < 0
- return FALSE
- return TRUE
-# Security check executed when first ibf message is received
-# INPUTS:
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# initial_local_size: The initial local setsize
-# set_diff: The set difference calculated with the strata estimator
-# ibf_msg: received ibf message
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION get_bucket_number(remote_setsize, local_setsize, initial_local_size,
set_diff, ibf_msg)
-
- # Check for max plausible set size as defined on use case basis (can be
infinite)
- max_plausible_setsize = getMaxPlausibleSetSize()
- IF remote_setsize > max_plausible_setsize
- return 0
- ENDIF
-
- # Check for correct operation mode operation_mode function is described in
performance section
- IF decide_operation_mode(initial_local_size, remote_setsize, set_diff) !=
"DIFFERENTIAL"
- return 0
- ENDIF
-
- ibf_params = calculate_optimal_IBF_params(local_setsize)
- total_number_of_buckets = ibf_params[0]
- number_of_bucket_per_element = ibf_params[0]
- IF ( 2^(ibf.order) != total_number_of_buckets ) ||
- (ibf.number_of_bucket_per_element != number_of_bucket_per_element)
- return 0
-
- return total_number_of_buckets
- ]]></artwork>
- </figure>
</dd>
- <dt><xref target="messages_full_element" format="title"
/></dt>
+ <dt><xref target="messages_send_full" format="title"
/></dt>
<dd>
<t>
- If a full element is received, the set of the other
peer
- is smaller than the set of the peer in the
<strong>Expecting IBF</strong>
- state and the set difference is smaller than threshold
for
- full synchronisation as described in the <xref
target="performance" format="title" /> section.
- This can be verified by calculating the plausible
upper and lower boundaries
- of the number of elements in the other peers set as
described in
- the first section.
+ It needs to be checked that the full
synchronisation mode with initiating peer
+ sending first is plausible according to the
algorithm deciding which operation mode
+ is applicable as described in <xref
target="performance_formulas_operationmode" format="default"/>.
</t>
- <figure
anchor="security_states_expecting_ibf_full_element_code">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-# Security check executed when first ibf message is received
-# INPUTS:
-# client_id: Unique remote peer id
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# initial_local_size: The initial local setsize
-# set_diff: The set difference calculated with the strata estimator
-# full_element_msg: received full element message
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_full_element(client_id, remote_setsize,
- local_setsize, initial_local_size, set_diff, full_element_msg)
-
- # On first run create store and make initial checks
- IF is_undefined(store)
- full_element_msg_store = createStore()
- IF ! validate_messages_full_element_init(client_id, remote_setsize,
- local_setsize, initial_local_size,
set_diff)
- return FALSE
- ENDIF
- ENDIF
-
- # Prevent duplication of received message
- IF ! addMessageToStore(full_element_msg_store, full_element_msg.unique_id)
- return FALSE
- ENDIF
-
- # Prevent to receive more elements than the remote peer has
- number_received_messages = getNumberOfMessage(full_element_msg_store)
- IF ( number_received_messages > remote_setsize )
- return FALSE
- ENDIF
-
- return TRUE
-
-
-# INPUTS:
-# client_id: The initial local setsize
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# initial_local_size: The initial local setsize
-# set_diff: the set difference calculated by the strata estimator
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_full_element_init(client_id, remote_setsize,
- local_setsize, initial_local_size, set_diff)
-
- last_setsize = getNumberOfElementsLastSync(clientId)
- IF remote_setsize < last_setsize
- return FALSE
- ENDIF
-
- # Update number of elements in store
- save_number_of_elements_last_sync(client_id, remote_setsize)
-
- # Check for max plausible set size as defined
- # on use case basis (can be infinite)
- plausible_setsize = getMaxPlausibleSetSize()
- IF remote_setsize > plausible_setsize
- return FALSE
- ENDIF
-
- # Check for correct operation mode operation_mode
- # function is described in performance section
- IF decide_operation_mode(initial_local_size, remote_setsize, set_diff) !=
"FULL"
- return FALSE
- ENDIF
-
- # Check that the other peer is honest and he should send us his set
- IF decide_full_sending(local_size, initial_remote_setsize ) != "REMOTE"
- return FALSE
- ENDIF
-
- return TRUE
-
- ]]></artwork>
- </figure>
</dd>
</dl>
</section>
@@ -2471,50 +2662,21 @@ FUNCTION validate_messages_full_element_init(client_id,
remote_setsize,
<dt><xref target="messages_full_element" format="title"
/></dt>
<dd>
<t>
- When receiving full elements there needs to be
checked, that every
- element is a valid element, no element has been
received more than once and
- not more or less elements are received, as the other
peer has committed
- to in the beginning of the operation. Detail
pseudocode implementation
- can be found in <xref
target="security_states_expecting_ibf" format="title" />.
+ When receiving full elements there needs to be
checked, that every
+ element is a valid element, that no element has
been received more than once and
+ not more or less elements are received, as the
other peer has committed
+ to in the beginning of the operation. The
plausibility should also be checked
+ with an algorithm as described in <xref
target="security_generic_functions_full_plausibility_check" format="default"/>.
</t>
</dd>
<dt><xref target="messages_full_done" format="title"
/></dt>
<dd>
<t>
- When receiving the full done message it is important
to check that
+ When receiving the <em><xref
target="messages_full_done" format="title" /></em> message, it is important to
check that
not less elements are received as the other peer has
committed to
send. If the sets differ, a resynchronisation is
required. The number of possible
- resynchronisation MUST be limited to prevent resource
exhaustion attacks.
+ resynchronisation MUST be limited, to prevent resource
exhaustion attacks.
</t>
- <figure
anchor="security_states_full_sending_full_done_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# full_done_msg: received full done message
-# full_element_msg_store: Store that stores the the uniq keys of
-# full elements
-# remote_setsize: The remote setsize
-# local_set: The local set
-# client_id: Unique remote peer id
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_full_done(full_done_msg, full_element_msg_store,
- remote_setsize, local_set, client_id)
-
- # Check that correct number of elements has been received
- number_received_messages = getNumberOfMessage(full_element_msg_store)
- IF ( number_received_messages != remote_setsize )
- return FALSE
- ENDIF
- IF local_set.getFullHash() != full_done_msg.fullSetHash
- return FALSE
- ENDIF
-
- # Update other peers remote_setsize
- save_number_of_elements_last_sync(client_id, remote_setsize)
-
- return TRUE
- ]]></artwork>
- </figure>
</dd>
</dl>
</section>
@@ -2526,28 +2688,23 @@ FUNCTION validate_messages_full_done(full_done_msg,
full_element_msg_store,
<dt><xref target="messages_ibf" format="title" /></dt>
<dd>
<t>
- When receiving multiple IBFs it is important to
check that the other
- peer can only send as many IBFs as expected. The
number of expected IBFs can
- be calculated with the knowledge of the set
difference as described in the
- performance section.
- </t>
- <t>
- Use pseudocode of the function
"validate_messages_ibf" as described in
- <xref target="security_states_expecting_ibf"
format="title" /> section.
+ No special safety measures are necessary in this
state.
+ The maximum of <xref target="messages_ibf"
format="title" /> messages should be limited to a reasonable amount.
</t>
</dd>
</dl>
</section>
+
<section anchor="security_states_active_decoding" numbered="true"
toc="default">
<name>Active Decoding</name>
<t>
- In the Active Decoding state it is important to prevent an
attacker from
+ In the <strong>Active Decoding</strong> state it is
important to prevent an attacker from
generating and passing an unlimited amount of IBFs, that
do not decode or
- even worse, generate an IBF constructed, to send the peers
in an endless loop.
- To prevent an endless loop in decoding, a loop detection
MUST be implemented.
+ even worse, generate an IBF constructed to send the peers
in an endless loop.
+ To prevent an endless loop in decoding, a loop detection
should be implemented.
The simplest solution would be to prevent decoding of more
than a given amount of elements.
A more robust solution is to implement a algorithm that
detects a loop by
- analyzing past partially decoded IBFs. This can be archived
+ analyzing past partially decoded IBFs. This can be achieved
by saving the hash of all prior partly decoded IBFs hashes
in a hashmap and check
for every inserted hash, if it is already in the hashmap.
</t>
@@ -2556,7 +2713,7 @@ FUNCTION validate_messages_full_done(full_done_msg,
full_element_msg_store,
operation MUST be terminated. The upper and lower threshold
for the decoded elements can be calculated with the peers
set sizes
and the other peer committed set sizes from the
<strong>Expecting IBF</strong>
- State.
+ state.
</t>
<t>Security considerations for received messages:</t>
@@ -2568,68 +2725,20 @@ FUNCTION validate_messages_full_done(full_done_msg,
full_element_msg_store,
an inquiry or if an offer is received twice, the
operation MUST be terminated.
This requirement can be fulfilled by saving lists
that keep track of the state of
all sent inquiries and offers. When answering
offers these lists MUST be checked.
+ The sending and receiving of <xref
target="messages_offer" format="title" /> messages should
+ always be protected with an <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled,
not in order or unexpected messages.
</t>
- <figure
anchor="security_states_active_decoding_offer_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# offer_msg: Received offer message
-# inquiry_msg_store: Store that stores the the uniq keys of
-# the inquiries
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_offer(offer_msg,inquiry_msg_store)
- IF is_undefined(store)
- offer_msg_store = createStore()
- ENDIF
-
- # Store message to prevent double sending of messages
- IF ! addMessageToStore(offer_msg_store, offer_msg.unique_id)
- return FALSE
- ENDIF
-
- # Check that for every received offer a inquiry has been sent and non is
- # sent multiple times
- IF ! markElementAsReceived(inquiry_msg_store, offer_msg.unique_id)
- return FALSE
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
<t>
If an element that never has been requested by
a demand or is received double the operation MUST
be terminated.
- This requirement can be fulfilled by a simple
table that keeps track
- of the state of all sent demands.
- If an invalid element is received, the operation
has failed and it
- MUST be terminated.
+ The sending and receiving of <xref
target="messages_elements" format="title" /> messages should
+ always be protected with an <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled,
not in order or unexpected messages.
</t>
- <figure
anchor="security_states_active_decoding_elements_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# element_msg: Received element message
-# demand_msg_store: Store that stores the the uniq keys of
-# received demands.
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_elements(element_msg,demand_msg_store)
- IF is_undefined(store)
- element_msg_store = createStore()
- ENDIF
-
- # Store message to prevent double sending of messages
- IF ! addMessageToStore(element_msg_store, element_msg.unique_id)
- return FALSE
- ENDIF
-
- # Check that for every received element a demand has been sent and non is
- # sent multiple times
- IF ! markElementAsReceived(demand_msg_store, element_msg.unique_id)
- return FALSE
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_demand" format="title" /></dt>
<dd>
@@ -2638,100 +2747,46 @@ FUNCTION
validate_messages_elements(element_msg,demand_msg_store)
for an element is received, that never has been
offered or the offer already has
been answered with a demand, the operation MUST be
terminated. It is required to implement
a list which keeps track of the state of all sent
offers and received demands.
+ The sending and receiving of <em><xref
target="messages_demand" format="title" /></em> messages should
+ always be protected with an <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled, not
in order or unexpected messages.
</t>
- <figure
anchor="security_states_active_decoding_demand_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# demand_msg: Received demand message
-# offer_msg_store: Store that stores the the uniq keys of
-# send offers.
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_demand(demand_msg,offer_msg_store)
- IF is_undefined(demand_msg_store)
- demand_msg_store = createStore()
- ENDIF
-
- # Store message to prevent double sending of messages
- IF ! addMessageToStore(demand_msg_store, demand_msg.unique_id)
- return FALSE
- ENDIF
-
- # Check that for every received demand a offer has been sent and non is
- # sent multiple times
- IF ! markElementAsReceived(offer_msg_store, demand_msg.unique_id)
- return FALSE
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_done" format="title" /></dt>
<dd>
<t>
- The done message is only received, if the IBF has
been finished
- decoding and all offers have been sent. If the
done message is received before
+ The <em><xref target="messages_done"
format="title" /></em> message is only received, if the IBF has been finished
+ decoding and all offers have been sent. If the
<em><xref target="messages_done" format="title" /></em> message is received
before
the decoding of the IBF is finished or all open
offers and demands
have been answered, the operation MUST be
terminated. If
the sets differ, a resynchronisation is required.
The number of possible
resynchronisation MUST be limited to prevent
resource exhaustion attacks.
</t>
- <figure
anchor="security_states_active_decoding_done_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# done_msg: received done message
-# offer_msg_store: Store that stores the the uniq keys of
-# received offers.
-# demand_msg_store: Store that stores the the uniq keys of
-# received demands.
-# element_msg_store: Store that stores the the uniq keys of
-# received elements.
-# client_id: Unique remote peer id
-# remote_setsize: The remote setsize
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_done(done_msg, offer_msg_store,
- demand_msg_store, element_msg_store, client_id,
remote_setsize)
-
- # Check that all offers have been received
- IF ! isStoreComplete(offer_msg_store)
- return FALSE
- ENDIF
-
- # Check that all demands have been received
- IF ! isStoreComplete(demand_msg_store)
- return FALSE
- ENDIF
-
- # Check that all elements have been received
- IF ! isStoreComplete(element_msg_store)
- return FALSE
- ENDIF
-
- # Validate that set is truly identical
- IF local_set.getFullHash() != done_msg.fullSetHash
- return FALSE
- ENDIF
-
- # Update other peers remote_setsize
- save_number_of_elements_last_sync(client_id, remote_setsize)
-
- return TRUE
- ]]></artwork>
- </figure>
+ <t>
+ When a <em><xref target="messages_done"
format="title" /></em> message is received the
+ "check_if_synchronisation_is_complete()" function
from the <xref target="security_generic_functions_mfc" format="title" />
+ is required to ensure that all demands have been
satisfied successfully.
+ </t>
</dd>
</dl>
</section>
<section anchor="security_states_finish_closing" numbered="true"
toc="default">
<name>Finish Closing</name>
<t>
- In case not all sent demands or inquiries have been
answered in time, a predefined
- timeout, the operation has failed and MUST be terminated.
+ In the <strong>Finish Closing</strong> state the protocol
waits for
+ all sent demands to be fulfilled.
+ </t>
+ <t>
+ In case not all sent demands have been answered in time,
+ the operation has failed and MUST be terminated.
</t>
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
- Checked as described in section <xref
target="security_states_active_decoding" format="title" />.
+ When receiving <xref target="messages_elements"
format="title" /> messages it is important
+ to always check the <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled, not
in order or unexpected messages.
</dd>
</dl>
</section>
@@ -2748,49 +2803,15 @@ FUNCTION validate_messages_done(done_msg,
offer_msg_store,
<dt><xref target="messages_se" format="title" /></dt>
<dd>
<t>
- In case the Strata Estimator does not decode, the
- operation MUST be terminated to prevent to get to
a unresolvable state.
+ In case the strata estimator does not decode, the
+ operation MUST be terminated to prevent to get to
an unresolvable state.
The set difference calculated from the strata
estimator needs to be plausible,
- to ensure this, multiple factors need to be
considered: The absolute plausible maximum of
- elements in a set, which has to be predefined
according
- to the use case and the maximal plausible element
increase since the last
- successful set reconciliation, which SHOULD be
either predefined or can be calculated
- with the gaussian distribution function over all
passed set reconciliations.
+ which means within the byzantine boundaries
described in section <xref
target="security_generic_functions_check_byzantine_boundaries" format="title"
/>.
</t>
<t>
In case of compressed strata estimators the
decompression algorithm needs to
be protected against decompression memory
corruption (memory overflow).
</t>
- <figure anchor="security_states_expect_se_se_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# se_msg: received strata estimator message
-# remote_setsize: The remote setsize
-# local_setsize: The local setsize
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_se(se_msg, remote_setsize, local_setsize)
-
- # Check that se decoded successfully if not return -1
- set_diff = decode_se(se_msg)
- IF set_diff < 0
- return FALSE
- ENDIF
-
- # Check that set difference cant be larger than local + remote setsize
- IF set_diff > (remote_setsize + local_setsize)
- return FALSE
- ENDIF
-
- # Check for max plausible set size as defined on use case basis (can be
infinite)
- plausible_setsize = getMaxPlausibleSetSize()
- IF set_diff > plausible_setsize
- return FALSE
- ENDIF
-
- return TRUE
- ]]></artwork>
- </figure>
</dd>
</dl>
</section>
@@ -2801,29 +2822,22 @@ FUNCTION validate_messages_se(se_msg, remote_setsize,
local_setsize)
<dt><xref target="messages_full_element" format="title"
/></dt>
<dd>
<t>
- The peer in <strong>Full Receiving</strong> state
needs to check
- that exactly the number of elements is received
from the remote peer as
- he has initially committed too. If the remote peer
transmits less or
- more elements the operation MUST be terminated.
- </t>
- <t>
- Pseudocode for implementation described in section
<xref target="security_states_expecting_ibf" format="title" />.
+ When receiving full elements there needs to be
checked, that every
+ element is a valid element, no element has been
received more than once and
+ not more or less elements are received, as the
other peer has committed
+ to in the beginning of the operation. The
plausibility should also be checked
+ with an algorithm as described in <xref
target="security_generic_functions_full_plausibility_check" format="default"/>.
</t>
</dd>
<dt><xref target="messages_full_done" format="title"
/></dt>
<dd>
<t>
- When the full done message is received from the
remote peer all
+ When the <em><xref target="messages_full_done"
format="title" /></em> message is received from the remote peer, all
elements, that the remote peer has committed to,
need to be received,
otherwise the operation MUST be terminated. After
receiving the
- full done message, future elements MUST NOT be
accepted.
- The 512-bit hash of the complete reconciled set
contained in
- the full done message is required to ensure that
both sets are truly identical. If
+ <em><xref target="messages_full_done"
format="title" /></em> message, future elements MUST NOT be accepted. If
the sets differ, a resynchronisation is required.
The number of possible
- resynchronisations MUST be limited to prevent
resource exhaustion attacks.
- </t>
- <t>
- Pseudocode for implementation described in section
<xref target="security_states_full_sending" format="title" />.
+ resynchronisation MUST be limited to prevent
resource exhaustion attacks.
</t>
</dd>
</dl>
@@ -2835,108 +2849,42 @@ FUNCTION validate_messages_se(se_msg, remote_setsize,
local_setsize)
<dt><xref target="messages_ibf" format="title" /></dt>
<dd>
<t>
- In case an IBF message is received by the peer a
active/passive role switch
+ In case an <xref target="messages_ibf"
format="title" /> message is received by the peer a active/passive role switch
is initiated by the active decoding remote peer.
In this moment the peer MUST
wait for all open offers and demands to be
fulfilled, to prevent
retransmission before switching into active
decoding operation mode.
A switch into active decoding mode MUST only be
permitted for
- a predefined number of times as described in the
top section
- of the security section.
+ a predefined number of times as described in <xref
target="security_generic_functions_active_passive_switches" format="default"/>
</t>
- <figure
anchor="security_states_passive_decoding_ibf_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# offer_msg_store: Store that stores the the uniq keys of
-# received offers.
-# demand_msg_store: Store that stores the the uniq keys of
-# received demands.
-# element_msg_store: Store that stores the the uniq keys of
-# received elements.
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_ibf(offer_msg_store, demand_msg_store,
element_msg_store)
-
- # Check that all offers have been received
- IF ! isStoreComplete(offer_msg_store)
- return FALSE
- ENDIF
-
- # Check that all demands have been received
- IF ! isStoreComplete(demand_msg_store)
- return FALSE
- ENDIF
-
- # Check that all elements have been received
- IF ! isStoreComplete(element_msg_store)
- return FALSE
- ENDIF
-
- # Check that not more active/passive switches are done as configured
- IF getNumberRollSwitches() > getMaxNumberRollSwitches()
- return FALSE
- ENDIF
-
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_inquiry" format="title" /></dt>
<dd>
<t>
A check needs to be in place that prevents receiving
an inquiry
for an element multiple times or more inquiries than
are plausible.
- The amount of inquiries that is plausible, can be
estimated by considering
- known values, as the remote set size, the local set
size, the
- predefined absolute maximum of elements in the set,
which is defined
- by real world limitations.
- To implement this restrictions, a list with all
received inquiries
- MUST be stored and new inquiries MUST be checked
against.
+ The sending and receiving of <xref
target="messages_inquiry" format="title" /> messages should
+ always be protected with an <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled, not
in order or unexpected messages.
</t>
- <figure
anchor="security_states_passive_decoding_inquiry_code">
- <artwork name="" type="" align="left"
alt=""><![CDATA[
-# INPUTS:
-# inquiry_msg: received inquiry message
-# set_diff: The set difference calculated by strata estimator
-# OUTPUTS:
-# returns: Boolean as indicator if message is valid
-FUNCTION validate_messages_inquiry(inquiry_msg, set_diff)
-
- IF is_undefined(inquiry_msg_store)
- inquiry_msg_store = createStore()
- ENDIF
-
- # Store message to prevent double sending of messages
- IF ! addMessageToStore(inquiry_msg_store, inquiry_msg.unique_id)
- return FALSE
- ENDIF
-
- # Check that not more inquiries are received as estimated
- IF set_diff < getNumberOfMessage(inquiry_msg_store)
- return FALSE
- ENDIF
-
- return TRUE
- ]]></artwork>
- </figure>
</dd>
<dt><xref target="messages_demand" format="title" /></dt>
<dd>
- Same action as described for demand message in section
+ Same action as described for <em><xref
target="messages_demand" format="title" /></em> message in section
<xref target="security_states_active_decoding"
format="title"/>.
</dd>
<dt><xref target="messages_offer" format="title" /></dt>
<dd>
- Same action as described for offer message in section
+ Same action as described for <em><xref
target="messages_offer" format="title" /></em> message in section
<xref target="security_states_active_decoding"
format="title"/>.
</dd>
<dt><xref target="messages_done" format="title" /></dt>
<dd>
- Same action as described for done message in section
+ Same action as described for <em><xref
target="messages_done" format="title" /></em> message in section
<xref target="security_states_active_decoding"
format="title"/>.
</dd>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
- Same action as described for element message in section
+ Same action as described for <em><xref
target="messages_elements" format="title" /></em> message in section
<xref target="security_states_active_decoding"
format="title"/>.
</dd>
@@ -2945,21 +2893,55 @@ FUNCTION validate_messages_inquiry(inquiry_msg,
set_diff)
<section anchor="security_states_finish_waiting" numbered="true"
toc="default">
<name>Finish Waiting</name>
<t>
- In case not all sent demands or inquiries have ben
answered in time, the operation
+ In the <strong>Finish Waiting</strong> state the protocol
waits for
+ all send demands to be fulfilled.
+ </t>
+ <t>
+ In case not all sent demands have ben answered in time,
the operation
has failed and MUST be terminated.
</t>
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_elements" format="title" /></dt>
<dd>
- Checked as described in section <xref
target="security_states_active_decoding" format="title" />.
+ When receiving <xref target="messages_elements"
format="title" /> messages it is important
+ to always check the <xref
target="security_generic_functions_mfc" format="title" />
+ to secure the protocol against missing, doubled, not
in order or unexpected messages.
</dd>
</dl>
</section>
-
</section>
</section>
-
+ <section anchor="constants" numbered="true" toc="default">
+ <name>Constants</name>
+ <t>
+ The following table contains constants used by the protocol. The
constants marked with a * are
+ validated through experiments in Summermatter's work <xref
target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ </t>
+ <figure anchor="figure_constants">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+Name | Value | Description
+----------------------------+------------+--------------------------
+SE_STRATA_COUNT | 32 | Number of IBFs in a strata estimator
+IBF_HASH_NUM* | 3 | Number of times an element is
hashed to an IBF
+IBF_FACTOR* | 2 | The factor by which the size of the
IBF is increased
+ in case of decoding failure or
initially from the
+ set difference
+MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are
transmitted in single message
+IBF_MIN_SIZE* | 37 | Minimal number of buckets in an IBF
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for
a differential syncronisation
+SECURITY_LEVEL* | 2^80 | Security level for probabilistic
security algorithms
+PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding
failure in the differential
+ synchronisation mode
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for
a differential syncronisation
+MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF
+AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single
strata estimator
+VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in
+
+ ]]></artwork>
+ </figure>
+
+ </section>
<section anchor="gana" numbered="true" toc="default">
<name>GANA Considerations</name>
<t>
@@ -2971,6 +2953,7 @@ FUNCTION validate_messages_inquiry(inquiry_msg, set_diff)
Type | Name | References | Description
--------+----------------------------+------------+--------------------------
559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of
the other peer
+ 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the full
set to the other peer
560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole element
from the other peer, given only the hash code.
561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to
send us a list of hashes that match an IBF key.
562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which
hashes match a given IBF key.
@@ -2981,8 +2964,8 @@ Type | Name | References |
Description
567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter
Last Slice.
568 | SETU_P2P_DONE | [This.I-D] | Set operation is done.
569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed
- 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full
synchronization mode have been send is done.
- 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in
full synchronization mode.
+ 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full
synchronisation mode have been send is done.
+ 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in
full synchronisation mode.
]]></artwork>
</figure>
@@ -2991,7 +2974,7 @@ Type | Name | References |
Description
<section anchor="contributors" numbered="true" toc="default">
<name>Contributors</name>
<t>
- The original GNUnet implementation of the Byzantine Fault
Tolerant Set Reconciliation
+ The original GNUnet implementation of the byzantine fault
tolerant Set Reconciliation
protocol has mainly been
written by Florian Dold and Christian Grothoff.
</t>
@@ -3003,6 +2986,16 @@ Type | Name | References |
Description
&RFC5869;
&RFC2119;
+ <reference anchor="byzantine_fault_tolerant_set_reconciliation"
target="https://summermatter.net/byzantine-fault-tolerant-set-reconciliation-summermatter.pdf";>
+ <front>
+ <title>Byzantine Fault Tolerant Set Reconciliation</title>
+ <author initials="E." surname="Summermatter"
fullname="Elias Summermatter">
+ <organization>University of Applied Sciences
Bern</organization>
+ </author>
+ <date year="2021"/>
+ </front>
+ </reference>
+
<reference anchor="GANA" target="https://gana.gnunet.org/";>
<front>
<title>GNUnet Assigned Numbers Authority (GANA)</title>
@@ -3088,15 +3081,6 @@ Type | Name | References |
Description
<date year="2014"/>
</front>
</reference>
- <reference anchor="byzantine_fault_tolerant_set_reconciliation"
target="https://summermatter.net/byzantine-fault-tolerant-set-reconciliation-summermatter.pdf";>
- <front>
- <title>Secure Set Reconciliation</title>
- <author initials="E." surname="Summermatter"
fullname="Elias Summermatter">
- <organization>University of Applied Sciences
Bern</organization>
- </author>
- <date year="2021"/>
- </front>
- </reference>
</references>
<section anchor="test_vectors" numbered="true" toc="default">
diff --git a/statemachine/full_state_machine.png
b/statemachine/full_state_machine.png
index 0d7196e..ea9e89e 100644
Binary files a/statemachine/full_state_machine.png and
b/statemachine/full_state_machine.png differ
diff --git a/statemachine/full_state_machine.svg
b/statemachine/full_state_machine.svg
index 38873ea..bf2c557 100644
--- a/statemachine/full_state_machine.svg
+++ b/statemachine/full_state_machine.svg
@@ -1,3 +1,3 @@
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd";>
-<svg xmlns="http://www.w3.org/2000/svg"; style="background-color: rgb(255, 255,
255);" xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="1541px"
height="921px" viewBox="-0.5 -0.5 1541 921" content="<mxfile
host="app.diagrams.net" modified="2021-05-20T13:48:38.286Z"
agent="5.0 (X11)" etag="Nrj_kDXvqoQ1CdzchEh5"
version="14.6.12" type="device"><diagram
id="C5RBs43oDa-KdzZeNtuy" name="Page-1&quo [...]
\ No newline at end of file
+<svg xmlns="http://www.w3.org/2000/svg";
xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="1542px"
height="921px" viewBox="-0.5 -0.5 1542 921" content="<mxfile
host="app.diagrams.net" modified="2021-06-09T09:00:23.118Z"
agent="5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko)
Chrome/91.0.4472.77 Safari/537.36" etag="nBSEvaX3-Qq_OyputO_f"
version="14.7.6" type="device"><diagram
id="C5RBs43o [...]
\ No newline at end of file
diff --git a/statemachine/full_state_machine.xml
b/statemachine/full_state_machine.xml
index 679cee1..18ce7fd 100644
--- a/statemachine/full_state_machine.xml
+++ b/statemachine/full_state_machine.xml
@@ -1 +1 @@
-<mxfile host="app.diagrams.net" modified="2021-05-20T13:48:24.900Z" agent="5.0
(X11)" etag="a3Ebk57OIP6ERtez1A7k" version="14.6.12" type="device"><diagram
id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">7V1bc9vGFf41nGkzI8zeF3i0JTl167ROnNbJIyxCIlKSkEFKlvLru7gsCBwsSVwW5LKJHjTEEliAu+d8534wo9erl+/T8HHxQzKPljOC5i8zejMjhHGi/mcDr8WAj1Ax8JDG82II7wY+xb9H5aA+7SmeR5vGidskWW7jx+bgXbJeR3fbxliYpsm35mn3ybJ518fwIWoNfLoLl+3Rz/F8uyhHBWe7L/4WxQ8LfWssguKbVajPLn/KZhHOk2+1IXo7o9dpkmyLT6uX62iZLZ5emM/vXz8vP/xXfP/3Hzdfw
[...]
\ No newline at end of file
+<mxfile host="app.diagrams.net" modified="2021-06-09T09:00:04.439Z" agent="5.0
(X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.77
Safari/537.36" etag="S3dK_qrw8OXXDkhOVYPX" version="14.7.6"
type="device"><diagram id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">7V1td9u2Ff41PmfbOebBO8iPie102dItbbql/chYtMVOEh1Kduz++oEvoMgLSKJIUIba+kMiQiRI4d774L7zgl4tn7/L44f599ksWVwQNHu+oNcXhBAkiPqvGHmpRjAWUTVyn6ezemw78Cn9LakHUT36mM6SdefETZYtNulDd/A2W62S201nLM7z7Fv3tLts0b3rQ3yfGAOfbuOFOfo
[...]
\ No newline at end of file
diff --git a/statemachine/state_machine_full b/statemachine/state_machine_full
index dd6b21a..4d172ff 100644
--- a/statemachine/state_machine_full
+++ b/statemachine/state_machine_full
@@ -1 +1 @@
-<mxfile host="app.diagrams.net" modified="2021-06-09T06:52:44.377Z" agent="5.0
(X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.77
Safari/537.36" etag="pelenmTsAhDcsqPl0I7k" version="14.7.6"
type="device"><diagram id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">5Vtdc6M2FP01nml3Jow+kIDHfDjbbbftdtM27SMxis0WIy/gJM6vrwAJI4RdAjhLpvuy6CKu4d6jo3MlZYYv10/vE3+z+pkHLJohEDzN8NUMIQQoEv/lll1pgZB6pWWZhIG07Q034TOTRiCt2zBgqdYx4zzKwo1uXPA4ZotMs/lJwh/1bvc80n914y+ZYbhZ+JFpvQ2DbCWtlNj7Gz+
[...]
\ No newline at end of file
+<mxfile host="app.diagrams.net" modified="2021-06-09T09:03:07.281Z" agent="5.0
(X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.77
Safari/537.36" etag="KR6ZhX0G6TfHJ9lJQmcM" version="14.7.6"
type="device"><diagram id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">5Vtbc6M2FP41nmk7E0YXxOUxF2ebNr1t2m77SIxis8XICziJ8+srgYQRwi4BnCXTfVl0EAd8zqdP35GUGb5cP39Ig83qJxbSeIZA+DzDVzOEEHAQ/09YdqUFQuCWlmUahdK2N9xFL1QagbRuo5BmWsecsTiPNrpxwZKELnLNFqQpe9K7PbBYf+smWFLDcLcIYtP6KQrzlbQ6xN7f+J5
[...]
\ No newline at end of file
diff --git a/statemachine/state_machine_full.png
b/statemachine/state_machine_full.png
index 395a21c..6caa0b0 100644
Binary files a/statemachine/state_machine_full.png and
b/statemachine/state_machine_full.png differ
diff --git a/statemachine/state_machine_full.svg
b/statemachine/state_machine_full.svg
index f3d4b43..dc199cb 100644
--- a/statemachine/state_machine_full.svg
+++ b/statemachine/state_machine_full.svg
@@ -1,3 +1,3 @@
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd";>
-<svg xmlns="http://www.w3.org/2000/svg";
xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="752px"
height="531px" viewBox="-0.5 -0.5 752 531" content="<mxfile
host="app.diagrams.net" modified="2021-06-09T06:55:05.725Z"
agent="5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko)
Chrome/91.0.4472.77 Safari/537.36" etag="Ho4LXeUk9jqtwfKfm4ic"
version="14.7.6" type="device"><diagram
id="C5RBs43oDa [...]
\ No newline at end of file
+<svg xmlns="http://www.w3.org/2000/svg";
xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="752px"
height="531px" viewBox="-0.5 -0.5 752 531" content="<mxfile
host="app.diagrams.net" modified="2021-06-09T09:03:20.632Z"
agent="5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko)
Chrome/91.0.4472.77 Safari/537.36" etag="FuY_nssVVWUIB2rbHQ9Y"
version="14.7.6" type="device"><diagram
id="C5RBs43oDa [...]
\ No newline at end of file
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0003] branch master updated: Changed some stuff,
gnunet <=