[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Added some more stuff
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: Added some more stuff |
|
Date: |
Sun, 06 Jun 2021 21:37:55 +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 736ea05 Added some more stuff
736ea05 is described below
commit 736ea05a43a995479fe1e36c8a8d523420fc956e
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Sun Jun 6 21:34:53 2021 +0200
Added some more stuff
---
draft-summermatter-set-union.xml | 524 +++++++++++++--------------------------
1 file changed, 176 insertions(+), 348 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 9074380..cef2baa 100644
--- 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
@@ -160,6 +150,13 @@
an upper bound.
</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.
@@ -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>
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
- [lsd0003] branch master updated: Added some more stuff,
gnunet <=