commit e52742fa7251cfa6e333b07b11683e059ae2b63e
parent d18767809341e4e63fd3f42f6b1d8510e31c6477
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Tue, 19 Jan 2021 15:05:11 +0100
Added some comments
Diffstat:
1 file changed, 207 insertions(+), 104 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -81,7 +81,7 @@
Our primary envisioned application domain is the
distribution of revocation messages in the GNU Name
- System (GNS) (FIXME-CITE: some paper on GNS...). In GNS,
+ System (GNS) <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/gns2014wachs.pdf -->. 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
@@ -96,13 +96,13 @@
in this specification are Byzantine fault-tolerant
bulletin boards, like those required in some secure
multiparty computations. A well-known example for
- secure multiparty computations are various E-voting
- protocols (FIXME-CITE DOLD BS-thesis, etc...) which
+ secure multiparty computations are <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/ba_dold_voting_24aug2014.pdf --> various E-voting
+ protocols which
use a bulletin board to share the votes and intermediate
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!).
+ described in (FIXME-CITE: DOLD MS Thesis! Which paper is his MS thesis on fdold.eu).
</t>
<t>
The protocol described in this report is generic and
@@ -125,7 +125,7 @@
is one major choice to be made, which is between sending the
full set of elements, or just sending the elements that differ.
In the latter case, our design is basically a concrete
- implementation of a proposal by Eppstein. (FIXME-CITE!).
+ implementation of a proposal by Eppstein. <!-- TODO: citate: https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf -->
</t>
<t>
@@ -207,7 +207,7 @@
</figure>
<t>
A typical mapping function is constructed by hashing the element, for example
- using the well-known HKDF construction (FIXME: cite HKDF RFC!).
+ using the well-known <relref section="2" target="RFC5869" displayFormat="of">HKDF construction</relref>.
</t>
<t>
To add an element to the BF, the corresponding buckets under the map M are set to 1.
@@ -372,7 +372,7 @@ hashSum | HASHSUM | HASHSUM | HASHSUM | HASHSUM | H..
</t>
<t>
In the following example, the insert operation is illustrated using an element with the
- ID 0x01020304 and a hash of 0x4242, and a second element with the ID 0x03040506 and
+ ID 0x0102 and a hash of 0x4242, and a second element with the ID 0x0304 and
a hash of 0x0101.
</t>
<t>Empty IBF:</t>
@@ -388,25 +388,29 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
- <t>Insert first element: [0101] with hash 0x4242:</t>
+ <t>Insert first element: [0101] with ID 0x0102 and hash 0x4242:</t>
<figure anchor="figure_ibf_insert_1">
<artwork name="" type="" align="left" alt=""><![CDATA[
bucket-0 bucket-1 bucket-2 bucket-3
+-------------+-------------+-------------+-------------+
count | 0 | 1 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0000 | 0x4242 | 0000 | 0x4242 |
+ idSum | 0000 | 0x0102 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0000 | 0x4242 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
- <t>Insert second element: [1100] with hash 0101:</t>
+ <t>Insert second element: [1100] with ID 0x0304 and hash 0101:</t>
<figure anchor="figure_ibf_insert_2">
<artwork name="" type="" align="left" alt=""><![CDATA[
bucket-0 bucket-1 bucket-2 bucket-3
+-------------+-------------+-------------+-------------+
count | 1 | 2 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0101 | 0x4343 | 0000 | 0x4242 |
+ idSum | 0x0304 | 0x0206 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0101 | 0x4343 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
@@ -429,18 +433,22 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
count | 1 | 2 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0x0101 | 0x4343 | 0000 | 0x4242 |
+ idSum | 0x0304 | 0x0206 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
- <t>Remove element [1100] with hash 0x0101 from the IBF:</t>
+ <t>Remove element [1100] with ID 0x0304 and hash 0x0101 from the IBF:</t>
<figure anchor="figure_ibf_remove_1">
<artwork name="" type="" align="left" alt=""><![CDATA[
bucket-0 bucket-1 bucket-2 bucket-3
+-------------+-------------+-------------+-------------+
count | 0 | 1 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0000 | 0x4242 | 0000 | 0x4242 |
+ idSum | 0000 | 0x0102 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0000 | 0x4242 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
@@ -522,7 +530,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
count | 1 | 2 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0101 | 4343 | 0000 | 4242 |
+ idSum | 0x0304 | 0x0206 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
@@ -536,13 +546,15 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
count | 0 | 1 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0000 | 4242 | 0000 | 4242 |
+ idSum | 0000 | 0x0102 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0000 | 0x4242 | 0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
<t>
In the IBF only pure buckets are left, we choose to continue decoding bucket 2 and decode element
- with the hash 4242. Now the IBF is empty (all buckets have count 0) that means the IBF has successfully
+ with the hash 0x4242. Now the IBF is empty (all buckets have count 0) that means the IBF has successfully
decoded.
</t>
<figure anchor="figure_ibf_decode_2">
@@ -551,7 +563,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
count | 0 | 0 | 0 | 0 |
+-------------+-------------+-------------+-------------+
- value | 0000 | 0000 | 0000 | 0000 |
+ idSum | 0000 | 0000 | 0000 | 0000 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
@@ -582,25 +596,29 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
To demonstrate the set difference operation we compare IBF-A with IBF-B and generate as described
IBF-AB
</t>
- <t>IBF-A containing elements with hash 0101 and 4242:</t>
+ <t>IBF-A containing elements with hashes 0x0101 and 0x4242:</t>
<figure anchor="figure_ibf_setdiff_A">
<artwork name="" type="" align="left" alt=""><![CDATA[
bucket-0 bucket-1 bucket-2 bucket-3
+-------------+-------------+-------------+-------------+
count | 1 | 2 | 0 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0101 | 4343 | 0000 | 4242 |
+ idSum | 0x0304 | 0x0206 | 0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
- <t>IBF-B containing elements with hash 4242 and 5050</t>
+ <t>IBF-B containing elements with hashes 0x4242 and 0x5050</t>
<figure anchor="figure_ibf_setdiff_B">
<artwork name="" type="" align="left" alt=""><![CDATA[
bucket-0 bucket-1 bucket-2 bucket-3
+-------------+-------------+-------------+-------------+
count | 0 | 1 | 1 | 1 |
+-------------+-------------+-------------+-------------+
- value | 0000 | 4242 | 5050 | 4242 |
+ idSum | 0000 | 0x0102 | 0x1345 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
@@ -611,13 +629,15 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-------------+-------------+-------------+-------------+
count | 1 | 1 | -1 | 0 |
+-------------+-------------+-------------+-------------+
- value | 0101 | 0101 | 5050 | 0000 |
+ idSum | 0000 | 0x0304 | 0x1345 | 0000 |
+ +-------------+-------------+-------------+-------------+
+hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 |
+-------------+-------------+-------------+-------------+
]]></artwork>
</figure>
- <t>After calculating and decoding the IBF-AB its clear that in IBF-A the element with the hash 5050
+ <t>After calculating and decoding the IBF-AB its clear that in IBF-A the element with the hash 0x5050
is missing (-1 in bit-3) while in IBF-B the element with the hash 0101 is missing
- (1 in bit-1 and bit-2). The element with hash 4242 is present in IBF-A and IBF-B and is
+ (1 in bit-1 and bit-2). The element with hash 0x4242 is present in IBF-A and IBF-B and is
removed by the set difference operation (bit-4).
</t>
</section>
@@ -719,7 +739,10 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
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 to just
exchange the full sets.
- ############# IMAGE ##################
+ </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>
</t>
<t>
The second possibility is that the difference of the sets is small compared to the set size.
@@ -751,7 +774,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
transitions into the <strong>Full Sending</strong> state.
</t>
<t>
- ############# Statemaschine diagram full mode ##################
+ <!-- TODO: Add smaller version -->
+ <eref target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg">Link to statemachine diagram</eref>
</t>
<t><strong>The behavior of the participants the different state is described below:</strong></t>
<dl>
@@ -797,7 +821,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
is called the passive peer.
</t>
<t>
- ############# Statemaschine Delta Synchronisation Mode ##################
+ <!-- TODO: Add smaler version -->
+ <eref target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg">Link to statemachine diagram</eref>
</t>
<t><strong>The behavior of the participants the different states is described below:</strong></t>
<dl>
@@ -835,21 +860,30 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
is received if the active peer has decoded an element that is present in the active peers set and may be missing in the
set of the passive peer. If the SHA-512 hash of the offer is indeed not a hash of any of the elements from the set of
the passive peer, the passive peer MUST answer with a <em><xref target="messages_demand" format="title" /></em> message
- for that SHA-512 hash and remember that it issued this demand.
+ for that SHA-512 hash and remember that it issued this demand. The send demand need to be added to a list with unsatisfied demands.
</dd>
<dt><em><xref target="messages_elements" format="title" /></em> message:</dt>
<dd>
- A element that is received is validated and safed and not further action is taken.
- FIXME: Eh, don't we need to (1) check that we did in fact DEMAND this element, and (2) strike it
- from the list of pending demands?
+ When a new element 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, removed it from the list
+ of pending demands and then then saves the element to the the set otherwise the peer
+ rejects the element.
</dd>
<dt><em><xref target="messages_ibf" format="title" /></em> message:</dt>
<dd>
If an <em><xref target="messages_ibf" format="title" /></em> message is received, this
indicates that decoding of the IBF on the active site has failed and roles should be swapped.
- The receiving passive peer transitions into the <strong>Active Decoding</strong> state
- or into the <strong>Expecting IBF Last</strong> state depending on how many IBFs are sent.
- FIXME: really should use two IBF message types (IBF_DATA, IBF_LAST).
+ The receiving passive peer transitions into the <strong>Expecting IBF Last</strong> state,
+ and waits for more <em><xref target="messages_ibf" format="title" /></em> messages
+ or the final <em><xref target="messages_ibf_last" format="title" /></em> message to be received.
+ </dd>
+ <dt><em><xref target="messages_ibf_last" format="title" /></em> message:</dt>
+ <dd>
+ If an <em><xref target="messages_ibf_last" format="title" /></em> message is received this
+ indicates that the there is just one IBF slice and a direct state and role transition from
+ <strong>Passive Decoding</strong> to <strong>Active Decoding</strong> is initiated.
</dd>
<dt><em><xref target="messages_done" format="title" /></em> message:</dt>
<dd>
@@ -877,15 +911,18 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<t>
In case the IBF does not successfully decode anymore, the active peer sends a new IBF to the passive client
and changes into <strong>Passive Decoding</strong> state. This initiates a role swap.
- FIXME: 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.
+ To reduce overhead and prevent double transmission of offers and elements the new IBF is created
+ on the new complete set after all demands and inquiries have been satisfied.
+
+ </t>
+ <t>
+ As soon as the active peer successfully finished decoding the IBF, the active peer sends a
+ <em><xref target="messages_done" format="title" /></em> message to the passive peer.
</t>
<t>
All other actions taken by the active peer depend on the message the active peer receives from
the passive peer. The actions are described below on a per message basis:
</t>
- <!-- FIXME: Done message generation not described anywhere! -->
<dl>
<dt><em><xref target="messages_offer" format="title" /></em> message:</dt>
<dd>
@@ -894,7 +931,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
the active peer. If a Inquiry has been sent and <!-- FIXME: is this indeed a condition that is checked? -->
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.
+ passive peer. The send demand need to be added to a list with unsatisfied demands.
+ In the 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>
@@ -904,23 +942,31 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
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.
- FIXME: Do we really check that we first made an offer? FIXME: what happens if
- we do not have an element with the respective SHA-512 hash?
- FIXME: should we check that a demand cannot be sent repeatedly for the same element?
+ <!-- IMPLEMENT: This is not implemented in code // Change -->
+ In the case the demanded element does not exist in the
+ set there was probably a bucket decoded that was not really pure so potentially all <em><xref target="messages_offer" format="title" /></em>
+ and <em><xref target="messages_demand" format="title" /></em> messages sent after 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>
- A element that is received is validated and saved and not further action is taken.
- FIXME: what if we receive elements we already know? Is that cause for failure?
- FIXME: Do we not need to remember that our demands were satisfied?
+ A element that is received is marked in the list of demanded elements as satisfied, validated and
+ saved and not further action is taken.
+ Elements that are not demanded or already known are discarded.
</dd>
<dt><em><xref target="messages_done" format="title" /></em> message:</dt>
<dd>
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
state <strong>Finish Closing</strong> state.
- FIXME: We cannot really receive this message before we completed decoding the IBF and send DONE to the passive peer.
- So that might be an additional constraint to check here!
+ <!-- IMPLEMENT: This is not implemented in code // Change -->
+ If the IBF is 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>
@@ -928,7 +974,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<dd>
<t>
In the <strong>Expecing IBF Last</strong> state the active peer continuously receives <em><xref target="messages_ibf" format="title" /></em>
- messages from the passive peer. When the last <em><xref target="messages_ibf" format="title" /></em> message is received
+ messages from the passive peer. When the last <em><xref target="messages_ibf_last" format="title" /></em> message is received
the active peer changes into <strong>Active Decoding</strong> state.
</t>
</dd>
@@ -936,8 +982,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<dd>
<t>
In this states the peers are waiting for all demands to be satisfied and for the synchronisation
- to be completed. When all demands are satisfied the peer changes into state <strong>done</strong>.
- FIXME: I thought "done" was a message, and the final state was called "Finished"!??!?
+ to be completed. When all demands are satisfied the peer changes into state <strong>Finished</strong>.
</t>
</dd>
</dl>
@@ -959,10 +1004,12 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<t>
There are two main cases when a <xref target="modeofoperation_full-sync" format="title" />
is always used.
- The first case is when one of the peers announces having an empty set. FIXME: HOW is this announced?
+ 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 requested 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).
@@ -970,6 +1017,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
than 25% or the set size of the receiving peer is zero. Otherwise the delta synchronisation mode is used.
############# NOTE END############
</t>
+ -->
</section>
</section>
@@ -990,8 +1038,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
This message is sent in the transition between the <strong>Initiating Connection</strong> state and the <strong>Expect SE</strong> state.
</t>
<t>
- If a peer receives this message and is willing to run the protocol, it answers by sending back a Strata estimator message.
- FIXME: turn 'strata estimator' into a link!
+ If a peer receives this message and is willing to run the protocol, it answers by sending back a <em><xref target="messages_se" format="title" /></em> message.
Otherwise it simply closes the connection.
</t>
</section>
@@ -1023,8 +1070,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</dd>
<dt>OPERATION TYPE</dt>
<dd>
- is a 32-bit unsigned integer which describes the type of operation that should be initiated.
- FIXME: unclear what this is. What operation types are there? What are the numeric values?
+ 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? -->
+ 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>
@@ -1048,16 +1098,10 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</t>
<t>
The <em>IBF</em> message is sent at the start of the protocol from the initiating peer in the transaction
- between <strong>Expect SE</strong> -> <strong>Passive Decoding</strong> or when the IBF does not decode and there is a role change in the
- transition between <strong>Active Decoding</strong> -> <strong>Passive Decoding</strong>.
- </t>
- <t>
- This message is received either in the state transmission between <strong>Expecting IBF</strong> -> <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong>
- if multiple IBFs need to be transmitted or if only one IBF needs to be transmitted directly from
- <strong>Expecting IBF</strong> -> <strong>Active Decoding</strong>. Since the active and passive roles can be reversed in this
- protocol, receiving the <em>IBF</em> message can initiate a role change so receiving
- the message can initiate the transitions <strong>Passive Decoding</strong> -> <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong> and
- <strong>Passive Decoding</strong> -> <strong>Active Decoding</strong>.
+ between <strong>Expect SE</strong> -> <strong>Expecting IBF Last</strong> or when the IBF does not
+ decode and there is a role change in the transition between <strong>Active Decoding</strong> -> <strong>Expecting IBF Last</strong>.
+ This message is only sent if there are more than one IBF slice to sent, in the case there is just
+ one slice the <xref target="messages_ibf_last" format="title" /> message is sent.
</t>
</section>
<section anchor="messages_ibf_structure" numbered="true" toc="default">
@@ -1070,7 +1114,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| OFFSET | SALT |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF-SLICES
+ | IBF-SLICE
+ /
/ /
/ /
@@ -1098,21 +1142,36 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</dd>
<dt>OFFSET</dt>
<dd>
- is a 32-bit unsigned integer which signals the offset of the strata estimator. ### Beser erklähren postion der nachfolgenden ibf slices im orignial
+ is a 32-bit unsigned integer which signals the offset to the following ibf slices in the original.
</dd>
<dt>SALT</dt>
<dd>
is a 32-bit unsigned integer that contains the salt which was used to create the
IBF.
</dd>
- <dt>IBF-SLICES</dt>
+ <dt>IBF-SLICE</dt>
<dd>
- are variable count of slices in an array. A single slice contains out of a 64-bit Key, a
- 32-bit Key Hash and an 8-bit count.
+ <t>
+ are variable count of slices in an array. A single slice contains out multiple 64-bit IDSUMS,
+ 32-bit HASHSUMS and 8-bit COUNTERS. In the network order the array of IDSUMS is first, followed
+ by an array of HASHSUMS and ended with an array of COUNTERS. Length of the array is defined
+ by MIN( 2^ORDER - OFFSET, MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as
+ 32768 divided by the BUCKET_SIZE which is 13-byte (104-bit).
+ </t>
+ <t>
+ The IDSUMS The HASHSUMS is calculated as a standard CRC32 check sum from
+ the key of the element.
+ <!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the
+ salt_key function in gnunet-service-set_union.c file and the ibf_insert_into (why exponentiation? ^=) in the ibf.c
+ The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32.
+ -->
+ </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.
+ test vectors.-->
</dd>
</dl>
<figure anchor="figure_ibf_slice">
@@ -1120,9 +1179,13 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
IBF-SLICE
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | KEY |
+ | IDSUMS |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | KEY HASH | COUNT |
+ | IDSUMS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASHSUMS | HASHSUMS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | COUNTERS | COUNTERS |
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1131,6 +1194,28 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</section>
</section>
+ <section anchor="messages_ibf_last" numbered="true" toc="default">
+ <name>IBF</name>
+
+ <section anchor="messages_ibf_last_description" numbered="true" toc="default">
+ <name>Description</name>
+ <t>
+ This message indicates to the remote peer that all slices of the bloom filter have been sent.
+ The binary structure is exactly the same as the <xref target="messages_ibf_structure" format="title" /> of
+ the message <xref target="messages_ibf" format="title" /> with a different "MSG TYPE"
+ which is defined in <xref target="gana" format="title" /> "SETU_P2P_IBF_LAST".
+ </t>
+ <t>
+ Receiving this message initiates the state transmissions
+ <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong>,
+ <strong>Expecting IBF</strong> -> <strong>Active Decoding</strong> and
+ <strong>Passive Decoding</strong> -> <strong>Active Decoding</strong>. This message
+ can initiate a peer the roll change from <strong>Active Decoding</strong> to
+ <strong>Passive Decoding</strong>.
+ </t>
+ </section>
+ </section>
+
<section anchor="messages_elements" numbered="true" toc="default">
<name>Elements</name>
@@ -1356,8 +1441,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<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.
- FIXME: we might want to consider adding an additional final checksum (XOR SHA-512 hash) over
- all elements to this message, to ensure that really both sides ended up with the same set?
+ <!-- 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" />.
@@ -1371,6 +1459,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE |
+-----+-----+-----+-----+
+ | HASH
+ +-----+-----+-----+-----+
]]></artwork>
<!-- <postamble>which is a very simple example.</postamble>-->
</figure>
@@ -1384,6 +1474,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
<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.
+ </dd>
+
</dl>
</section>
</section>
@@ -1514,7 +1609,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</dd>
<dt>SETSIZE</dt>
<dd>
- is a 64-bit unsigned integer that is defined by the size of the set the SE is #### 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 <!--IMPLEMENT: Mögliche optimierung wäre wäre hier eine 32bit padding einzuführen damit es aligned -->
</dd>
<dt>SE-SLICES</dt>
<dd>
@@ -1614,35 +1709,43 @@ hashSum | 0000 | 0000 | 0000 | 0000 |
</section>
+
<section anchor="performance" numbered="true" toc="default">
<name>Performance Considerations</name>
+ <!--
+ <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>
+
+ <section anchor="security" numbered="true" toc="default">
+ <name>Security Considerations</name>
+ <!--
+ <section anchor="security_crypto" numbered="true" toc="default">
+ <name>BLAH</name>
<t>
- --- TEXT HERE ---
+ 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 anchor="security" numbered="true" toc="default">
- <name>Security Considerations</name>
- <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>
<section anchor="gana" numbered="true" toc="default">
<name>GANA Considerations</name>
@@ -1660,8 +1763,9 @@ 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.
+ 565 | SETU_P2P_IBF | [This.I-D] | Invertible 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.
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.
@@ -1687,7 +1791,7 @@ Type | Name | References | Description
<back>
<references>
<name>Normative References</name>
-
+ &RFC5869;
&RFC1034;
&RFC1035;
&RFC2782;
@@ -1696,7 +1800,6 @@ Type | Name | References | Description
&RFC3686;
&RFC3826;
&RFC3912;
- &RFC5869;
&RFC5890;
&RFC5891;
&RFC6781;
