[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Added some comments
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: Added some comments |
|
Date: |
Tue, 19 Jan 2021 15:06:02 +0100 |
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 e52742f Added some comments
e52742f is described below
commit e52742fa7251cfa6e333b07b11683e059ae2b63e
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Tue Jan 19 15:05:11 2021 +0100
Added some comments
---
draft-summermatter-set-union.xml | 311 ++++++++++++++++++++++++++-------------
1 file changed, 207 insertions(+), 104 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index ca001a2..e32f905 100644
--- 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" />.
@@ -1370,6 +1458,8 @@ hashSum | 0000 | 0000 | 0000 |
0000 |
0 8 16 24 32
+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE |
+ +-----+-----+-----+-----+
+ | HASH
+-----+-----+-----+-----+
]]></artwork>
<!-- <postamble>which is a very simple
example.</postamble>-->
@@ -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;
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0003] branch master updated: Added some comments,
gnunet <=