commit 736ea05a43a995479fe1e36c8a8d523420fc956e
parent 7ea92b4312916063fb0b3bd6225e2d1d8e36facb
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 6 Jun 2021 21:34:53 +0200
Added some more stuff
Diffstat:
1 file changed, 176 insertions(+), 348 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -4,19 +4,8 @@
<!ENTITY RFC1035 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.1035.xml">
<!ENTITY RFC2119 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.2119.xml">
<!ENTITY RFC2782 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.2782.xml">
- <!ENTITY RFC3629 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3629.xml">
<!ENTITY RFC3686 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3686.xml">
- <!ENTITY RFC3826 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3826.xml">
- <!ENTITY RFC3912 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3912.xml">
<!ENTITY RFC5869 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.5869.xml">
- <!ENTITY RFC5890 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.5890.xml">
- <!ENTITY RFC5891 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.5891.xml">
- <!ENTITY RFC6781 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.6781.xml">
- <!ENTITY RFC6895 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.6895.xml">
- <!ENTITY RFC6979 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.6979.xml">
- <!ENTITY RFC7748 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.7748.xml">
- <!ENTITY RFC8032 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.8032.xml">
- <!ENTITY RFC8126 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.8126.xml">
]>
<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
<?rfc strict="yes" ?>
@@ -81,7 +70,7 @@
Our primary envisioned application domain is the
distribution of revocation messages in the GNU Name
- System (GNS) <xref target="GNUNET" format="default" />. In GNS,
+ System (GNS) <xref target="GNUNET" format="default" /><xref target="GNS" format="default"/>. In GNS,
key revocation messages are usually flooded across the
peer-to-peer overlay network to all connected peers
whenever a key is revoked. However, as peers may be
@@ -102,7 +91,8 @@
computational results. We note that for such systems,
the set reconciliation protocol is merely a component of
a multiparty consensus protocol, such as the one
- described in (FIXME-CITE: DOLD MS Thesis! Which paper is his MS thesis on fdold.eu).
+ described in F.Dold's "Byzantine set-union consensus using
+ efficient set reconciliation" <xref target="ByzantineSetUnionConsensusUsingEfficientSetReconciliation" format="default"/>.
</t>
<t>
The protocol described in this report is generic and
@@ -161,6 +151,13 @@
</t>
<t>
+ Initially, this RFC was created as part of Elias Summermatter's
+ bachelor thesis. Many of the algorithms and parameters
+ documented in this RFC are derived in detail in this thesis.
+ <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ </t>
+
+ <t>
This document defines the normative wire format of resource records, resolution processes,
cryptographic routines and security considerations for use by implementors.
SETU requires a bidirectional secure communication channel between the two parties.
@@ -307,7 +304,7 @@
</section>
</section>
- <section anchor="ibv" numbered="true" toc="default">
+ <section anchor="ibf" numbered="true" toc="default">
<name>Invertible Bloom Filter</name>
<t>
An Invertible Bloom Filter (IBF) is a further extension of the <xref target="cbf" format="title" />.
@@ -1036,12 +1033,11 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dd>
The <em><xref target="messages_offer" format="title" /></em> message indicates that the
passive peer received a <em><xref target="messages_inquiry" format="title" /></em> message from
- the active peer. If a Inquiry has been sent and <!-- FIXME: is this indeed a condition that is checked? -->
+ the active peer. If a Inquiry has been sent and
the offered element is missing in the active peers set,
the active peer sends a <em><xref target="messages_demand" format="title" /></em> message to the
passive peer. The sent demand needs to be added to a list with unsatisfied demands.
In case the received offer is for an element that is already in the set of the peer the offer is ignored.
- <!-- FIXME: what happens if the offer is for an element that is not missing? I think then we just ignore it, right? -->
</dd>
<dt><em><xref target="messages_demand" format="title" /></em> message:</dt>
<dd>
@@ -1050,15 +1046,12 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
the active peer. The active peer satisfies the demand of the passive peer by sending
<em><xref target="messages_elements" format="title" /></em> message if a offer request
for the element has been sent.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
In case the demanded element does not exist in the
set there was probably a bucket decoded that was not pure so potentially all <em><xref target="messages_offer" format="title" /></em>
and <em><xref target="messages_demand" format="title" /></em> messages sent later are invalid
in this case a role change active -> passive with a new IBF is easiest.
If a demand for the same element is received multiple times the demands should be
discarded.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
- <!--FIXME: Do we really check that we first made an offer?-->
</dd>
<dt><em><xref target="messages_elements" format="title" /></em> message:</dt>
<dd>
@@ -1071,10 +1064,8 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
Receiving the message <em><xref target="messages_done" format="title" /></em> indicates
that all demands of the passive peer have been satisfied. The active peer then changes into the
<strong>Finish Closing</strong> state.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
If the IBF has not finished decoding and the <em><xref target="messages_done" format="title" /></em>
is received, the other peer is not in compliance with the protocol and the set reconciliation MUST be aborted.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
</dd>
</dl>
</dd>
@@ -1117,15 +1108,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
The second case is if the application requests full synchronization explicitly.
This is useful for testing and should not be used in production.
</t>
- <!--
- <t>
- ############# NOTE ############
- To ensure that ...... the difference is multiplied by 1.5 if there are more than 200 elements differences between the sets (WHY? line 1398).
- The Full Synchronisation Mode is used if the flag to force full sync is set, the estimated difference between the two sets is bigger
- than 25% or the set size of the receiving peer is zero. Otherwise the delta synchronisation mode is used.
- ############# NOTE END############
- </t>
- -->
</section>
</section>
@@ -1175,16 +1157,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dd>
the type of SETU_P2P_OPERATION_REQUEST as registered in <xref target="gana" format="title" />, in network byte order.
</dd>
- <!-- dt>OPERATION TYPE</dt>
- <dd>
- is a 32-bit unsigned integer which describes the type of operation that should be initiated on the set. The filed can have three
- different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. - @Christian can you check?: Right, alas we
- here only do UNION and INTERSECTION is a completely different protocol => we shall simply REMOVE this field. Hence commented out here:
- reminder to _remove_ in implementation!
- NONE should never occur and signals the set supports no operation and is just for local use.
- INTERSECTION returns only elements that are in both sets and the default case UNION, return all
- elements that are in at least one of the sets.
- </dd -->
<dt>ELEMENT COUNT</dt>
<dd>
is the number of the elements the requesting party has in its set, as a 32-bit unsigned integer in network byte order.
@@ -1289,12 +1261,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<t>
Test vectors for an implementation can be found in the <xref target="test_vectors" format="title" /> section
</t>
-
- <!--
- FIXME: this is not sufficiently precise! How are the element IDs (and IDSUMS) computed?
- How are the HASHes (and HASHSUMS) computed? Which byte order is used? What role does
- the SALT have in these computations? Definitively needs DETAILED algorithm(s) and
- test vectors.-->
</dd>
</dl>
<figure anchor="figure_ibf_slice">
@@ -1473,9 +1439,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<t>
This message is exclusively sent in the <xref target="modeofoperation_individual-elements" format="title" />.
</t>
- <t>
- NOTE: HERE IS AN IMPLEMENTATION BUG UNNECESSARY 32-BIT PADDING!
- </t>
</section>
<section anchor="messages_inquiry_structure" numbered="true" toc="default">
<name>Structure</name>
@@ -1561,11 +1524,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<t>
The done message is sent when all <em><xref target="messages_demand" format="title" /></em> messages
have been successfully satisfied and the set is complete synchronized.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
- A final checksum (XOR SHA-512 hash) over all elements of the set is added to the message
- to allow the other peer to make sure that the sets are equal.
- <!-- IMPLEMENT: This is not implemented in code // Change -->
-
</t>
<t>
This message is exclusively sent in the <xref target="modeofoperation_individual-elements" format="title" />.
@@ -1577,10 +1535,9 @@ 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 | HASH
- +-----+-----+-----+-----+
- / /
- / /
+ | MSG SIZE | MSG TYPE |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+
]]></artwork>
</figure>
<t>where:</t>
@@ -1593,12 +1550,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dd>
the type of SETU_P2P_DONE as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASH</dt>
- <dd>
- is a 512-bit hash of the set to allow a final equality check.
- <!-- IMPLEMENT: Needs to be implemented -->
- </dd>
-
</dl>
</section>
</section>
@@ -1623,10 +1574,8 @@ 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 | HASH
- +-----+-----+-----+-----+
- / /
- / /
+ | MSG SIZE | MSG TYPE |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
]]></artwork>
</figure>
<t>where:</t>
@@ -1639,11 +1588,6 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
<dd>
the type of SETU_P2P_FULL_DONE as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASH</dt>
- <dd>
- is a 512-bit hash of the set to allow a final equality check.
- <!-- IMPLEMENT: Needs to be implemented -->
- </dd>
</dl>
</section>
</section>
@@ -1733,7 +1677,7 @@ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
</dd>
<dt>SETSIZE</dt>
<dd>
- is a 64-bit unsigned integer that is defined by the size of the set the SE is <!--IMPLEMENT: Mögliche optimierung wäre wäre hier eine 32bit padding einzuführen damit es aligned -->
+ is a 64-bit unsigned integer that is defined by the size of the set the SE is
</dd>
<dt>SE-SLICES</dt>
<dd>
@@ -1831,7 +1775,7 @@ 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">
@@ -1839,101 +1783,168 @@ 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:
- </t>
- <t>
- The function takes as input the initial local setsize, the remote setsize, the
- by the strata estimator calculated difference, a static boolean that enforces full
- synchronisation mode of operation and the bandwith/roundtrips tradeoff.
- As output the function returns "FULL" if the full synchronisation
- mode should be used and "DIFFERENTIAL" if the differential mode should be used.
+ 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"/>
</t>
- <figure anchor="performance_formulas_operationmode_code">
- <artwork name="" type="" align="left" alt=""><![CDATA[
-
-# INPUTS:
-# initial_local_setsize: The initial local setsize
-# remote_setsize: The remote setsize
-# set_diff: the set difference calculated by the strata estimator
-# force_full: boolean to enforce FULL
-# ba_rtt_tradeoff: the tradeoff between round trips and bandwidth defined by the use case
-# OUTPUTS:
-# returns: the decision (FULL or DIFFERENTIAL)
-
-FUNCTION decide_operation_mode(initial_local_setsize, remote_setsize, set_diff, force_full, ba_rtt_tradeoff)
- IF set_diff > 200
- set_diff = set_diff * 3 / 2
- ENDIF
- IF force_full || ( set_diff > initial_local_setsize / 4 ) || remote_setsize = 0
- return "FULL"
- ENDIF
- return "DIFFERENTIAL"
-
- ]]></artwork>
- </figure>
- </section>
- <section anchor="performance_formulas_full_sending_dec_first_send" numbered="true" toc="default">
- <name>Full Synchronisation: Decision which peer sends elements first</name>
<t>
- The following function determinates which peer starts sending its full set in full synchronisation
- mode of operation.
+ 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,
+ 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
+ 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 function takes as input the initial local setsize (set size of the first iteration) and
- the remote setsize and returns as output the decision "REMOTE" or "LOCAL" to determinate if the
- remote or the local peer starts sending the full set.
+ 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"/>
</t>
- <figure anchor="performance_formulas_full_sending_dec_first_send_code">
+ <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)
+# IBF_MIN_SIZE = 37: The minimal size of an IBF
+# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol
# INPUTS:
-# initial_local_setsize: The initial local setsize
-# remote_setsize: The remote setsize
+# avg_element_size: The avg 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
+# est_remote_set_diff: the estimated remote set difference calculated by the strata estimator
+# rtt_tradeoff: the tradeoff between round trips and bandwidth defined by the use case
# OUTPUTS:
-# returns: the decision (LOCAL or REMOTE)
+# returns: the decision (FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST, DIFFERENTIAL_SYNC)
+
+FUNCTION decide_operation_mode(avg_element_size,
+ local_set_size,
+ remote_set_size,
+ est_local_set_diff
+ est_remote_set_diff,
+ rtt_tradeoff)
+ IF (0 == local_set_size)
+ RETURN FULL_SYNC_REMOTE_SENDING_FIRST
+ IF END
+ IF (0 == remote_set_size)
+ RETURN FULL_SYNC_LOCAL_SENDING_FIRST
+ IF END
+
+ estimated_total_diff = est_set_diff_remote + est_local_set_diff
+
+ total_elements_to_send_local_send_first = est_remote_set_diff + local_set_size;
+
+ total_bytes_full_local_send_first = (avg_element_size * total_elements_to_send_local_send_first)
+ + (total_elements_to_send_local_send_first * sizeof(ELEMENT_MSG_HEADER))
+ + (sizeof(FULL_DONE_MSG_HEADER) * 2)
+ + RTT_MIN_FULL * rtt_tradeoff
+
+ total_elements_to_send_remote_send_first = est_local_set_diff + remote_set_size
+
+ total_bytes_full_remote_send_first = (avg_element_size * total_elements_to_send_remote_send_first)
+ + ( total_elements_to_send_remote_send_first * sizeof(ELEMENT_MSG_HEADER))
+ + (sizeof(FULL_DONE_MSG_HEADER) * 2)
+ + (RTT_MIN_FULL + 0.5) * rtt_tradeoff
+ + sizeof(REQUEST_FULL_MSG)
+
+ ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR
+
+ IF (ibf_bucket_count <= IBF_MIN_SIZE)
+ ibf_bucket_count = IBF_MIN_SIZE
+ END IF
+
+ ibf_message_count = ceil ( ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE);
+
+ estimated_counter_size = MIN (
+ 2 * LOG2(local_set_size / ibf_bucket_count),
+ LOG2(local_set_size)
+ )
+ counter_bytes = estimated_counter_size / 8
+
+ ibf_bytes = sizeof(IBF_MESSAGE) * ibf_message_count * 1.2
+ + ibf_bucket_count * sizeof(IBF_KEY) * 1.2
+ + ibf_bucket_count * sizeof(IBF_KEYHASH) * 1.2
+ + ibf_bucket_count * counter_bytes * 1.2
+
+ element_size = (avg_element_size + sizeof(ELEMENT_MSG_HEADER)) * estimated_total_diff
+ done_size = sizeof(DONE_HEADER)
+ inquery_size = (sizeof(IBF_KEY) + sizeof(INQUERY_MSG_HEADER)) * estimated_total_diff
+ demand_size = (sizeof(HASHCODE) + sizeof(DEMAND_MSG_HEADER)) * estimated_total_diff;
+ offer_size = (sizeof(HASHCODE) + sizeof(OFFER_MSG_HEADER)) * estimated_total_diff;
+
+ total_bytes_diff = (element_size + done_size + inquery_size
+ + demand_size + offer_size + ibf_bytes)
+ + DIFFERENTIAL_RTT_MEAN * rtt_tradeoff
+
+ full_min = MIN (total_bytes_full_local_send_first,
+ total_bytes_full_local_send_first)
+ IF (full_min < total_bytes_diff)
+ IF (total_bytes_full_remote_send_first > total_bytes_full_local_send_first)
+ RETURN FULL_SYNC_LOCAL_SENDING_FIRST
+ ELSE
+ RETURN FULL_SYNC_REMOTE_SENDING_FIRST
+ END IF
+ ELSE
+ RETURN DIFFERENTIAL_SYNC
+ IF END
-FUNCTION decide_full_sending(initial_local_size, remote_setsize)
- IF ( initial_local_size <= remote_setsize ) || ( remote_setsize = 0 )
- return LOCAL
- ELIF
- return REMOTE
-
- ]]></artwork>
+ ]]></artwork>
</figure>
</section>
<section anchor="performance_formula_ibf_parameters" numbered="true" toc="default">
- <name>IBF Parameters</name>
+ <name>IBF Size</name>
<t>
- The following function calculates the required parameter to create an optimal sized IBF. These
- parameters are the number of buckets and the number of buckets a single element is mapped to.
+ The in this section described functions 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>
- The function takes as input the setsize and returns an array with two numbers, the total number of buckets
- and the number of buckets a single element is mapped to.
+ These algorithms are described and justified in more details in the following work
+ <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
</t>
<figure anchor="performance_formula_ibf_parameters_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
-# INPUTS:
-# setsize: The set size
-# OUTPUTS:
-# returns: Array: first element total nr ob buckets and
-# second element number of buckets per element
-
-FUNCTION calculate_ibf_params (set_diff):
- number_of_bucket_per_element = 4
- total_number_of_buckets = set_diff
- return [ total_number_of_buckets, number_of_bucket_per_element ]
+# CONSTANTS:
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
+# Inputs:
+# set_difference: Estimated set difference
+# Output:
+# next_size: Size of the initial IBF
+
+FUNCTION initial_ibf_size(set_difference)
+ return MAX(37, IBF_BUCKET_NUMBER_FACTOR * set_difference );
+FUNCTION END
+
+# CONSTANTS:
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
+# Inputs:
+# decoded_elements: Number of elements that have been successfully decoded
+# last_ibf_size: The number of buckets of the last IBF
+# Output:
+# next_size: Size of the next IBF
+
+FUNCTION get_next_ibf_size(decoded_elements, last_ibf_size)
+ next_size =(last_ibf_size * IBF_BUCKET_NUMBER_FACTOR) - ( IBF_BUCKET_NUMBER_FACTOR * decoded_elements )
+ return MAX(37, next_size);
+FUNCTION END
]]></artwork>
</figure>
</section>
- </section>
+ <section anchor="performance_num_buck_hash" numbered="true" toc="default">
+ <name>Number of buckets a element is hashed into</name>
+ <t>
+ The number of buckets an element is hashed to is hardcoded to 3. Reasoning and
+ justification can be found in the following work
+ <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ </t>
+ </section>
+ </section>
+ <!-- CORRECT -->
<section anchor="performance_counter_variable_size" numbered="true" toc="default">
<name>Counter variable 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.
- <!-- TODO link Thesis -->
+ by Elias Summermatter, BFH 2021<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>
@@ -2077,14 +2088,6 @@ FUNCTION unpack_counter(ibf, offset, count, counter_bit_length, packed_data)
</section>
</section>
- <!--
- <t>
- - TEXT HERE -
- On what basis is the new IBF constructed? Specifically, which set is used? Do we
- wait for the completion of pending demands first? How do L/k/M change? Some of this should
- be detailed here, but the full details likely need a separate section on the algorithms.
- </t>
- -->
<section anchor="security" numbered="true" toc="default">
<name>Security Considerations</name>
@@ -2100,14 +2103,12 @@ FUNCTION unpack_counter(ibf, offset, count, counter_bit_length, packed_data)
to be adapted per use basis. To enhance reliability and to allow
failures in the protocol, it is possible to introduce a threshold for max failed reconciliation
ties.
- <!-- IMPLEMENT: How to implement? IP? Other construct? -->
</t>
<t>
The formal format of all messages needs to be properly validated. This is important to prevent many
attacks on the code. The application data should be validated by the application using
the protocol not by the implementation of the protocol.
In case the format validation fails the set operation MUST be terminated.
- <!-- IMPLEMENT: Are all messages checked for formal valid format -->
</t>
<t>
@@ -2116,15 +2117,11 @@ FUNCTION unpack_counter(ibf, offset, count, counter_bit_length, packed_data)
a simple counter which terminates the operation after a predefined number of switches.
The number of switches needs to be defined in such a way that it is very unprobable that more
switches are required an the malicious intend of the other peer can be assumed.
-
- <!-- IMPLEMENT: This counter -->
</t>
<t>
- <!--- SHOULD BE HANDLED BY UNDERLYING PROTOCOL BUT HOW IS IT HANDLED? -->
It is important to close and purge connections after a given timeout
to prevent draining attacks.
- <!-- IMPLEMENT: How ist this handheld right now? -->
</t>
<section anchor="security_generic_functions" numbered="true" toc="default">
@@ -2264,14 +2261,6 @@ FUNCTION save_number_of_elements_last_sync(client_id, remote_setsize)
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.
- <!-- Entscheindungsfindung: myset fulltransimtion or epstein
- 5.3 ist zu verckürtzt fall: nur 2 cases Es fehlt traidof nach paramer in perfomance section
- -->
- <!-- Erlaubt perfomance section formel für mode choose: das sind die inputs klar definitert:
- formel invertierte aus
- 7.1/7.2: INPUT/OUTPUT Forcefull:-->
- <!-- IMPLEMENT: Check if this two checks already exists -->
- <!-- Christian: Should we implement a check for max increase over time? -->
</t>
<figure anchor="security_states_expecting_ibf_request_full_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2318,15 +2307,11 @@ FUNCTION validate_messages_request_full(client_id, remote_setsize, local_setsize
<t>
It is important to define a threshold to limit
the maximal number of IBFs that are expected from the other peer.
- <!-- change count to number full section -->
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 performance section.
- <!-- IMPLEMENT: Is this already checked?-->
- <!-- TODO: Link performance section -->
+ 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.
- <!-- IMPLEMENT: Is this already checked?-->
</t>
<figure anchor="security_states_expecting_ibf_message_ibf_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2386,12 +2371,10 @@ FUNCTION get_bucket_number(remote_setsize, local_setsize, initial_local_size, se
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 performance section.
- <!-- TODO: Add performance section -->
+ 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.
- <!-- if valid ok otherwise cancel connection! -->
</t>
<figure anchor="security_states_expecting_ibf_full_element_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2488,7 +2471,6 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize,
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" />.
- <!-- IMPLEMENT: Is this check already implemented?-->
</t>
</dd>
<dt><xref target="messages_full_done" format="title" /></dt>
@@ -2496,12 +2478,8 @@ FUNCTION validate_messages_full_element_init(client_id, remote_setsize,
<t>
When receiving the full done message it is important to check that
not less elements are received as the other peer has committed to
- send.
- 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
- the sets differ, a resynchronisation is required. The number of possible
+ send. If the sets differ, a resynchronisation is required. The number of possible
resynchronisation MUST be limited to prevent resource exhaustion attacks.
- <!-- IMPLEMENT: Is this check already implemented?-->
</t>
<figure anchor="security_states_full_sending_full_done_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2567,8 +2545,6 @@ FUNCTION validate_messages_full_done(full_done_msg, full_element_msg_store,
analyzing past partially decoded IBFs. This can be archived
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.
- <!-- TODO: Link some algo to find loops in directed graph -->
- <!-- IMPLEMENT: Implement an algo that detects loops in IBF decoding -->
</t>
<t>
If the IBF decodes more or less elements than are plausible, the
@@ -2578,8 +2554,6 @@ FUNCTION validate_messages_full_done(full_done_msg, full_element_msg_store,
State.
</t>
- <!-- Wenn ein Element mehrfach decodiert seitenwechseln daher detecten. -->
-
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_offer" format="title" /></dt>
@@ -2589,7 +2563,6 @@ 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.
- <!-- IMPLEMENT: Check to keep track of all send Inquiries -->
</t>
<figure anchor="security_states_active_decoding_offer_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2624,10 +2597,8 @@ FUNCTION validate_messages_offer(offer_msg,inquiry_msg_store)
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.
- <!-- IMPLEMENT: Check to keep track of all send demands -->
If an invalid element is received, the operation has failed and it
MUST be terminated.
- <!-- IMPLEMENT: Termination if invalid element si revived -->
</t>
<figure anchor="security_states_active_decoding_elements_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2688,7 +2659,6 @@ FUNCTION validate_messages_demand(demand_msg,offer_msg_store)
return TRUE
]]></artwork>
</figure>
- <!-- IMPLEMENT: Check to keep track of all send demands -->
</dd>
<dt><xref target="messages_done" format="title" /></dt>
<dd>
@@ -2696,10 +2666,7 @@ FUNCTION validate_messages_demand(demand_msg,offer_msg_store)
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 decoding of the IBF is finished or all open offers and demands
- have been answered, the operation MUST be terminated.
- <!-- IMPLEMENT: Check that in active decoding no done message is received before ibf has been decoded-->
- The 512-bit hash of the complete reconciled set contained in
- the done message is required to ensure that both sets are truly identical. If
+ 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>
@@ -2755,7 +2722,6 @@ FUNCTION validate_messages_done(done_msg, offer_msg_store,
In case not all sent demands or inquiries have been answered in time, a predefined
timeout, the operation has failed and MUST be terminated.
</t>
- <!-- FIXME: In state diagram in finish closing only Elements can be received. What happens if i receive an offer? -->
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_elements" format="title" /></dt>
@@ -2779,14 +2745,12 @@ FUNCTION validate_messages_done(done_msg, offer_msg_store,
<t>
In case the Strata Estimator does not decode, the
operation MUST be terminated to prevent to get to a unresolvable state.
- <!-- IMPLEMENT: If in expect SE state the strata estimator does not decode terminate the operation -->
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.
- <!-- IMPLEMENT: Terminate if in check expect se state for a max size difference is exceeded -->
</t>
<t>
In case of compressed strata estimators the decompression algorithm needs to
@@ -2848,7 +2812,6 @@ FUNCTION validate_messages_se(se_msg, remote_setsize, local_setsize)
elements, that the remote peer has committed to, need to be received,
otherwise the operation MUST be terminated. After receiving the
full done message no future elements should be accepted.
- <!-- FIXME: Check that after full done in full receiving no elements can be received anymore! Additional state? -->
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
the sets differ, a resynchronisation is required. The number of possible
@@ -2874,7 +2837,6 @@ FUNCTION validate_messages_se(se_msg, remote_setsize, local_setsize)
A switch into active decoding mode should only be permitted for
a predefined number of times as described in the top section
of the security section.
- <!-- IMPLEMENT: What does happen here in the code? -->
</t>
<figure anchor="security_states_passive_decoding_ibf_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2981,7 +2943,6 @@ FUNCTION validate_messages_inquiry(inquiry_msg, set_diff)
In case not all sent demands or inquiries have ben answered in time, the operation
has failed and MUST be terminated.
</t>
- <!-- FIXME: In state diagram in finish closing only Elements can be received. What happens if i receive an offer? -->
<t>Security considerations for received messages:</t>
<dl>
<dt><xref target="messages_elements" format="title" /></dt>
@@ -2992,34 +2953,12 @@ FUNCTION validate_messages_inquiry(inquiry_msg, set_diff)
</section>
</section>
-
- <!--
- <section anchor="security_crypto" numbered="true" toc="default">
- <name>BLAH</name>
- <t>
- Bulub.
- </t>
- <t>
- Another probabilistic approach to discover bad behaving peers is sampling, in this approach the proving peer needs
- to prove that he is in possession of the elements he claimed to be. This is achieved by the following procedure:
- </t>
- <t>
- The verifying peer chooses some
- random salt and sends the salt to the proving peer. The proving peer salts the hash of elements with the given
- salt from the verifying peer. Then the proving peer calculates the new hashes modulo a number depending on the set sized difference and
- sends all the elements where the modulo calculation equals 0 to the verifying peer.
- As soon as the verifying peer receives the elements the verifying peer can verify that all the elements
- are valid and the modulo calculation equals 0 then the verifying peer can be assured with a high probability
- that the peer is honest about his remaining set size and difference.
- </t>
- </section>
- -->
</section>
<section anchor="gana" numbered="true" toc="default">
<name>GANA Considerations</name>
<t>
- GANA is requested to amend the "GNUnet Message Type" registry
+ GANA is requested to amend the "GNUnet Message Type" <xref target="GANA" format="default"/> registry
as follows:
</t>
<figure anchor="figure_purposenums">
@@ -3032,7 +2971,7 @@ Type | Name | References | Description
562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes match a given IBF key.
563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from a remote peer.
564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed
- 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter Slice.
+ 565 | SETU_P2P_IBF | [This.I-D] | InvertibFle Bloom Filter Slice.
566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements.
567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter Last Slice.
568 | SETU_P2P_DONE | [This.I-D] | Set operation is done.
@@ -3057,22 +2996,7 @@ Type | Name | References | Description
<references>
<name>Normative References</name>
&RFC5869;
- &RFC1034;
- &RFC1035;
- &RFC2782;
&RFC2119;
- &RFC3629;
- &RFC3686;
- &RFC3826;
- &RFC3912;
- &RFC5890;
- &RFC5891;
- &RFC6781;
- &RFC6895;
- &RFC6979;
- &RFC7748;
- &RFC8032;
- &RFC8126;
<reference anchor="GANA" target="https://gana.gnunet.org/">
<front>
@@ -3094,6 +3018,20 @@ Type | Name | References | Description
</reference>
+ <reference anchor="ByzantineSetUnionConsensusUsingEfficientSetReconciliation" target="https://doi.org/10.1186/s13635-017-0066-3">
+ <front>
+ <title>Byzantine set-union consensus using efficient set reconciliation</title>
+ <author initials="F." surname="Dold" fullname="Florian Dold">
+ <organization>Technische Universität München</organization>
+ </author>
+ <author initials="C." surname="Grothoff" fullname="Christian Grothoff">
+ <organization>Inria, Domaine de Voluceau Rocquencourt</organization>
+ </author>
+ </front>
+ </reference>
+
+
+
<reference anchor="GNUNET" target="https://git.gnunet.org/bibliography.git/plain/docs/gns2014wachs.pdf">
<front>
<title>A Censorship-Resistant, Privacy-Enhancing andFully Decentralized Name System</title>
@@ -3145,126 +3083,16 @@ Type | Name | References | Description
<date year="2014"/>
</front>
</reference>
- <reference anchor="R5N" target="https://doi.org/10.1109/ICNSS.2011.6060022">
- <front>
- <title>R5N: Randomized recursive routing for restricted-route networks</title>
- <author initials="N. S." surname="Evans" fullname="Nathan S. Evans">
- <organization>Technische Universitaet Muenchen</organization>
- </author>
-
- <author initials="C." surname="Grothoff"
- fullname="Christian Grothoff">
- <organization>Technische Universitaet Muenchen</organization>
- </author>
- <date year="2011"/>
- </front>
- </reference>
-
-
- <reference anchor="Argon2" target="https://datatracker.ietf.org/doc/draft-irtf-cfrg-argon2/">
- <front>
- <title>The memory-hard Argon2 password hash and proof-of-work function</title>
- <author initials="A." surname="Biryukov" fullname="Alex Biryukov">
- <organization>University of Luxembourg</organization>
- </author>
-
- <author initials="D." surname="Dinu" fullname="Daniel Dinu">
- <organization>University of Luxembourg</organization>
- </author>
-
- <author initials="D." surname="Khovratovich"
- fullname="Dmitry Khovratovich">
- <organization>ABDK Consulting</organization>
- </author>
- <author initials="S." surname="Josefsson"
- fullname="Simon Josefsson">
- <organization>SJD AB</organization>
- </author>
- <date year="2020" month="March"/>
- <abstract>
- <t>
- This document describes the Argon2 memory-hard function for
- password hashing and proof-of-work applications. We provide an
- implementer-oriented description with
- test vectors. The purpose is to simplify adoption of Argon2 for
- Internet protocols. This document is a product of the Crypto Forum Research Group (CFRG)
- in the IRTF.
- </t>
- </abstract>
- </front>
- </reference>
- <reference anchor="MODES" target="https://doi.org/10.6028/NIST.SP.800-38A">
- <front>
- <title>Recommendation for Block Cipher Modes of Operation: Methods and Techniques</title>
- <author initials="M." surname="Dworkin" fullname="Morris Dworkin">
- <organization>NIST</organization>
- </author>
-
- <date year="2001" month="December"/>
- <abstract>
- <t>
- This recommendation defines five confidentiality modes of operation for use with an
- underlying symmetric key block cipher algorithm: Electronic Codebook (ECB), Cipher Block
- Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB), and Counter (CTR). Used with
- an underlying block cipher algorithm that is approved in a Federal Information Processing
- Standard (FIPS), these modes can provide cryptographic protection for sensitive, but
- unclassified, computer data.
- </t>
- </abstract>
- </front>
- </reference>
- <reference anchor="ed25519" target="http://link.springer.com/chapter/10.1007/978-3-642-23951-9_9">
- <front>
- <title>High-Speed High-Security Signatures</title>
- <author initials="D." surname="Bernstein" fullname="Daniel Bernstein">
- <organization>University of Illinois at Chicago</organization>
- </author>
-
- <author initials="N." surname="Duif"
- fullname="Niels Duif">
- <organization>Technische Universiteit Eindhoven</organization>
-
- </author>
- <author initials="T." surname="Lange"
- fullname="Tanja Lange">
- <organization>Technische Universiteit Eindhoven</organization>
-
- </author>
- <author initials="P." surname="Schwabe"
- fullname="Peter Schwabe">
- <organization>National Taiwan University</organization>
-
- </author>
- <author initials="B." surname="Yang"
- fullname="Bo-Yin Yang">
- <organization>Academia Sinica</organization>
-
- </author>
- <date year="2011"/>
- </front>
- </reference>
- <reference anchor="secure_set_reconciliation" target="http://ti.bfh.ch">
+ <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>BFH - Berner Fachhochschule</organization>
+ <organization>University of Applied Sciences Bern</organization>
</author>
<date year="2021"/>
</front>
</reference>
- <!-- <reference anchor="ISO20022">
- <front>
- <title>ISO 20022 Financial Services - Universal financial industry message scheme</title>
- <author>
- <organization>International Organization for Standardization</organization>
- <address>
- <uri>http://www.iso.ch</uri>
- </address>
- </author>
- <date month="May" year="2013"/>
- </front>
- </reference>-->
</references>
<section anchor="test_vectors" numbered="true" toc="default">
<name>Test Vectors</name>
