diff options
author | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-01-19 15:05:11 +0100 |
---|---|---|
committer | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-01-19 15:05:11 +0100 |
commit | e52742fa7251cfa6e333b07b11683e059ae2b63e (patch) | |
tree | 132a8e65119760c4be5aecaa0db6e84c11e8470b | |
parent | d18767809341e4e63fd3f42f6b1d8510e31c6477 (diff) | |
download | lsd0003-e52742fa7251cfa6e333b07b11683e059ae2b63e.tar.gz lsd0003-e52742fa7251cfa6e333b07b11683e059ae2b63e.zip |
Added some comments
-rw-r--r-- | draft-summermatter-set-union.xml | 311 |
1 files 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 @@ | |||
81 | 81 | ||
82 | Our primary envisioned application domain is the | 82 | Our primary envisioned application domain is the |
83 | distribution of revocation messages in the GNU Name | 83 | distribution of revocation messages in the GNU Name |
84 | System (GNS) (FIXME-CITE: some paper on GNS...). In GNS, | 84 | System (GNS) <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/gns2014wachs.pdf -->. In GNS, |
85 | key revocation messages are usually flooded across the | 85 | key revocation messages are usually flooded across the |
86 | peer-to-peer overlay network to all connected peers | 86 | peer-to-peer overlay network to all connected peers |
87 | whenever a key is revoked. However, as peers may be | 87 | whenever a key is revoked. However, as peers may be |
@@ -96,13 +96,13 @@ | |||
96 | in this specification are Byzantine fault-tolerant | 96 | in this specification are Byzantine fault-tolerant |
97 | bulletin boards, like those required in some secure | 97 | bulletin boards, like those required in some secure |
98 | multiparty computations. A well-known example for | 98 | multiparty computations. A well-known example for |
99 | secure multiparty computations are various E-voting | 99 | secure multiparty computations are <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/ba_dold_voting_24aug2014.pdf --> various E-voting |
100 | protocols (FIXME-CITE DOLD BS-thesis, etc...) which | 100 | protocols which |
101 | use a bulletin board to share the votes and intermediate | 101 | use a bulletin board to share the votes and intermediate |
102 | computational results. We note that for such systems, | 102 | computational results. We note that for such systems, |
103 | the set reconciliation protocol is merely a component of | 103 | the set reconciliation protocol is merely a component of |
104 | a multiparty consensus protocol, such as the one | 104 | a multiparty consensus protocol, such as the one |
105 | described in (FIXME-CITE: DOLD MS Thesis!). | 105 | described in (FIXME-CITE: DOLD MS Thesis! Which paper is his MS thesis on fdold.eu). |
106 | </t> | 106 | </t> |
107 | <t> | 107 | <t> |
108 | The protocol described in this report is generic and | 108 | The protocol described in this report is generic and |
@@ -125,7 +125,7 @@ | |||
125 | is one major choice to be made, which is between sending the | 125 | is one major choice to be made, which is between sending the |
126 | full set of elements, or just sending the elements that differ. | 126 | full set of elements, or just sending the elements that differ. |
127 | In the latter case, our design is basically a concrete | 127 | In the latter case, our design is basically a concrete |
128 | implementation of a proposal by Eppstein. (FIXME-CITE!). | 128 | implementation of a proposal by Eppstein. <!-- TODO: citate: https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf --> |
129 | </t> | 129 | </t> |
130 | 130 | ||
131 | <t> | 131 | <t> |
@@ -207,7 +207,7 @@ | |||
207 | </figure> | 207 | </figure> |
208 | <t> | 208 | <t> |
209 | A typical mapping function is constructed by hashing the element, for example | 209 | A typical mapping function is constructed by hashing the element, for example |
210 | using the well-known HKDF construction (FIXME: cite HKDF RFC!). | 210 | using the well-known <relref section="2" target="RFC5869" displayFormat="of">HKDF construction</relref>. |
211 | </t> | 211 | </t> |
212 | <t> | 212 | <t> |
213 | To add an element to the BF, the corresponding buckets under the map M are set to 1. | 213 | 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.. | |||
372 | </t> | 372 | </t> |
373 | <t> | 373 | <t> |
374 | In the following example, the insert operation is illustrated using an element with the | 374 | In the following example, the insert operation is illustrated using an element with the |
375 | ID 0x01020304 and a hash of 0x4242, and a second element with the ID 0x03040506 and | 375 | ID 0x0102 and a hash of 0x4242, and a second element with the ID 0x0304 and |
376 | a hash of 0x0101. | 376 | a hash of 0x0101. |
377 | </t> | 377 | </t> |
378 | <t>Empty IBF:</t> | 378 | <t>Empty IBF:</t> |
@@ -388,25 +388,29 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
388 | +-------------+-------------+-------------+-------------+ | 388 | +-------------+-------------+-------------+-------------+ |
389 | ]]></artwork> | 389 | ]]></artwork> |
390 | </figure> | 390 | </figure> |
391 | <t>Insert first element: [0101] with hash 0x4242:</t> | 391 | <t>Insert first element: [0101] with ID 0x0102 and hash 0x4242:</t> |
392 | <figure anchor="figure_ibf_insert_1"> | 392 | <figure anchor="figure_ibf_insert_1"> |
393 | <artwork name="" type="" align="left" alt=""><![CDATA[ | 393 | <artwork name="" type="" align="left" alt=""><![CDATA[ |
394 | bucket-0 bucket-1 bucket-2 bucket-3 | 394 | bucket-0 bucket-1 bucket-2 bucket-3 |
395 | +-------------+-------------+-------------+-------------+ | 395 | +-------------+-------------+-------------+-------------+ |
396 | count | 0 | 1 | 0 | 1 | | 396 | count | 0 | 1 | 0 | 1 | |
397 | +-------------+-------------+-------------+-------------+ | 397 | +-------------+-------------+-------------+-------------+ |
398 | value | 0000 | 0x4242 | 0000 | 0x4242 | | 398 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | |
399 | +-------------+-------------+-------------+-------------+ | ||
400 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | ||
399 | +-------------+-------------+-------------+-------------+ | 401 | +-------------+-------------+-------------+-------------+ |
400 | ]]></artwork> | 402 | ]]></artwork> |
401 | </figure> | 403 | </figure> |
402 | <t>Insert second element: [1100] with hash 0101:</t> | 404 | <t>Insert second element: [1100] with ID 0x0304 and hash 0101:</t> |
403 | <figure anchor="figure_ibf_insert_2"> | 405 | <figure anchor="figure_ibf_insert_2"> |
404 | <artwork name="" type="" align="left" alt=""><![CDATA[ | 406 | <artwork name="" type="" align="left" alt=""><![CDATA[ |
405 | bucket-0 bucket-1 bucket-2 bucket-3 | 407 | bucket-0 bucket-1 bucket-2 bucket-3 |
406 | +-------------+-------------+-------------+-------------+ | 408 | +-------------+-------------+-------------+-------------+ |
407 | count | 1 | 2 | 0 | 1 | | 409 | count | 1 | 2 | 0 | 1 | |
408 | +-------------+-------------+-------------+-------------+ | 410 | +-------------+-------------+-------------+-------------+ |
409 | value | 0101 | 0x4343 | 0000 | 0x4242 | | 411 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | |
412 | +-------------+-------------+-------------+-------------+ | ||
413 | hashSum | 0101 | 0x4343 | 0000 | 0x4242 | | ||
410 | +-------------+-------------+-------------+-------------+ | 414 | +-------------+-------------+-------------+-------------+ |
411 | ]]></artwork> | 415 | ]]></artwork> |
412 | </figure> | 416 | </figure> |
@@ -429,18 +433,22 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
429 | +-------------+-------------+-------------+-------------+ | 433 | +-------------+-------------+-------------+-------------+ |
430 | count | 1 | 2 | 0 | 1 | | 434 | count | 1 | 2 | 0 | 1 | |
431 | +-------------+-------------+-------------+-------------+ | 435 | +-------------+-------------+-------------+-------------+ |
432 | value | 0x0101 | 0x4343 | 0000 | 0x4242 | | 436 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | |
437 | +-------------+-------------+-------------+-------------+ | ||
438 | hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | ||
433 | +-------------+-------------+-------------+-------------+ | 439 | +-------------+-------------+-------------+-------------+ |
434 | ]]></artwork> | 440 | ]]></artwork> |
435 | </figure> | 441 | </figure> |
436 | <t>Remove element [1100] with hash 0x0101 from the IBF:</t> | 442 | <t>Remove element [1100] with ID 0x0304 and hash 0x0101 from the IBF:</t> |
437 | <figure anchor="figure_ibf_remove_1"> | 443 | <figure anchor="figure_ibf_remove_1"> |
438 | <artwork name="" type="" align="left" alt=""><![CDATA[ | 444 | <artwork name="" type="" align="left" alt=""><![CDATA[ |
439 | bucket-0 bucket-1 bucket-2 bucket-3 | 445 | bucket-0 bucket-1 bucket-2 bucket-3 |
440 | +-------------+-------------+-------------+-------------+ | 446 | +-------------+-------------+-------------+-------------+ |
441 | count | 0 | 1 | 0 | 1 | | 447 | count | 0 | 1 | 0 | 1 | |
442 | +-------------+-------------+-------------+-------------+ | 448 | +-------------+-------------+-------------+-------------+ |
443 | value | 0000 | 0x4242 | 0000 | 0x4242 | | 449 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | |
450 | +-------------+-------------+-------------+-------------+ | ||
451 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | ||
444 | +-------------+-------------+-------------+-------------+ | 452 | +-------------+-------------+-------------+-------------+ |
445 | ]]></artwork> | 453 | ]]></artwork> |
446 | </figure> | 454 | </figure> |
@@ -522,7 +530,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
522 | +-------------+-------------+-------------+-------------+ | 530 | +-------------+-------------+-------------+-------------+ |
523 | count | 1 | 2 | 0 | 1 | | 531 | count | 1 | 2 | 0 | 1 | |
524 | +-------------+-------------+-------------+-------------+ | 532 | +-------------+-------------+-------------+-------------+ |
525 | value | 0101 | 4343 | 0000 | 4242 | | 533 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | |
534 | +-------------+-------------+-------------+-------------+ | ||
535 | hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | ||
526 | +-------------+-------------+-------------+-------------+ | 536 | +-------------+-------------+-------------+-------------+ |
527 | ]]></artwork> | 537 | ]]></artwork> |
528 | </figure> | 538 | </figure> |
@@ -536,13 +546,15 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
536 | +-------------+-------------+-------------+-------------+ | 546 | +-------------+-------------+-------------+-------------+ |
537 | count | 0 | 1 | 0 | 1 | | 547 | count | 0 | 1 | 0 | 1 | |
538 | +-------------+-------------+-------------+-------------+ | 548 | +-------------+-------------+-------------+-------------+ |
539 | value | 0000 | 4242 | 0000 | 4242 | | 549 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | |
550 | +-------------+-------------+-------------+-------------+ | ||
551 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | ||
540 | +-------------+-------------+-------------+-------------+ | 552 | +-------------+-------------+-------------+-------------+ |
541 | ]]></artwork> | 553 | ]]></artwork> |
542 | </figure> | 554 | </figure> |
543 | <t> | 555 | <t> |
544 | In the IBF only pure buckets are left, we choose to continue decoding bucket 2 and decode element | 556 | In the IBF only pure buckets are left, we choose to continue decoding bucket 2 and decode element |
545 | with the hash 4242. Now the IBF is empty (all buckets have count 0) that means the IBF has successfully | 557 | with the hash 0x4242. Now the IBF is empty (all buckets have count 0) that means the IBF has successfully |
546 | decoded. | 558 | decoded. |
547 | </t> | 559 | </t> |
548 | <figure anchor="figure_ibf_decode_2"> | 560 | <figure anchor="figure_ibf_decode_2"> |
@@ -551,7 +563,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
551 | +-------------+-------------+-------------+-------------+ | 563 | +-------------+-------------+-------------+-------------+ |
552 | count | 0 | 0 | 0 | 0 | | 564 | count | 0 | 0 | 0 | 0 | |
553 | +-------------+-------------+-------------+-------------+ | 565 | +-------------+-------------+-------------+-------------+ |
554 | value | 0000 | 0000 | 0000 | 0000 | | 566 | idSum | 0000 | 0000 | 0000 | 0000 | |
567 | +-------------+-------------+-------------+-------------+ | ||
568 | hashSum | 0000 | 0000 | 0000 | 0000 | | ||
555 | +-------------+-------------+-------------+-------------+ | 569 | +-------------+-------------+-------------+-------------+ |
556 | ]]></artwork> | 570 | ]]></artwork> |
557 | </figure> | 571 | </figure> |
@@ -582,25 +596,29 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
582 | To demonstrate the set difference operation we compare IBF-A with IBF-B and generate as described | 596 | To demonstrate the set difference operation we compare IBF-A with IBF-B and generate as described |
583 | IBF-AB | 597 | IBF-AB |
584 | </t> | 598 | </t> |
585 | <t>IBF-A containing elements with hash 0101 and 4242:</t> | 599 | <t>IBF-A containing elements with hashes 0x0101 and 0x4242:</t> |
586 | <figure anchor="figure_ibf_setdiff_A"> | 600 | <figure anchor="figure_ibf_setdiff_A"> |
587 | <artwork name="" type="" align="left" alt=""><![CDATA[ | 601 | <artwork name="" type="" align="left" alt=""><![CDATA[ |
588 | bucket-0 bucket-1 bucket-2 bucket-3 | 602 | bucket-0 bucket-1 bucket-2 bucket-3 |
589 | +-------------+-------------+-------------+-------------+ | 603 | +-------------+-------------+-------------+-------------+ |
590 | count | 1 | 2 | 0 | 1 | | 604 | count | 1 | 2 | 0 | 1 | |
591 | +-------------+-------------+-------------+-------------+ | 605 | +-------------+-------------+-------------+-------------+ |
592 | value | 0101 | 4343 | 0000 | 4242 | | 606 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | |
607 | +-------------+-------------+-------------+-------------+ | ||
608 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | | ||
593 | +-------------+-------------+-------------+-------------+ | 609 | +-------------+-------------+-------------+-------------+ |
594 | ]]></artwork> | 610 | ]]></artwork> |
595 | </figure> | 611 | </figure> |
596 | <t>IBF-B containing elements with hash 4242 and 5050</t> | 612 | <t>IBF-B containing elements with hashes 0x4242 and 0x5050</t> |
597 | <figure anchor="figure_ibf_setdiff_B"> | 613 | <figure anchor="figure_ibf_setdiff_B"> |
598 | <artwork name="" type="" align="left" alt=""><![CDATA[ | 614 | <artwork name="" type="" align="left" alt=""><![CDATA[ |
599 | bucket-0 bucket-1 bucket-2 bucket-3 | 615 | bucket-0 bucket-1 bucket-2 bucket-3 |
600 | +-------------+-------------+-------------+-------------+ | 616 | +-------------+-------------+-------------+-------------+ |
601 | count | 0 | 1 | 1 | 1 | | 617 | count | 0 | 1 | 1 | 1 | |
602 | +-------------+-------------+-------------+-------------+ | 618 | +-------------+-------------+-------------+-------------+ |
603 | value | 0000 | 4242 | 5050 | 4242 | | 619 | idSum | 0000 | 0x0102 | 0x1345 | 0x0102 | |
620 | +-------------+-------------+-------------+-------------+ | ||
621 | hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 | | ||
604 | +-------------+-------------+-------------+-------------+ | 622 | +-------------+-------------+-------------+-------------+ |
605 | ]]></artwork> | 623 | ]]></artwork> |
606 | </figure> | 624 | </figure> |
@@ -611,13 +629,15 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
611 | +-------------+-------------+-------------+-------------+ | 629 | +-------------+-------------+-------------+-------------+ |
612 | count | 1 | 1 | -1 | 0 | | 630 | count | 1 | 1 | -1 | 0 | |
613 | +-------------+-------------+-------------+-------------+ | 631 | +-------------+-------------+-------------+-------------+ |
614 | value | 0101 | 0101 | 5050 | 0000 | | 632 | idSum | 0000 | 0x0304 | 0x1345 | 0000 | |
633 | +-------------+-------------+-------------+-------------+ | ||
634 | hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | ||
615 | +-------------+-------------+-------------+-------------+ | 635 | +-------------+-------------+-------------+-------------+ |
616 | ]]></artwork> | 636 | ]]></artwork> |
617 | </figure> | 637 | </figure> |
618 | <t>After calculating and decoding the IBF-AB its clear that in IBF-A the element with the hash 5050 | 638 | <t>After calculating and decoding the IBF-AB its clear that in IBF-A the element with the hash 0x5050 |
619 | is missing (-1 in bit-3) while in IBF-B the element with the hash 0101 is missing | 639 | is missing (-1 in bit-3) while in IBF-B the element with the hash 0101 is missing |
620 | (1 in bit-1 and bit-2). The element with hash 4242 is present in IBF-A and IBF-B and is | 640 | (1 in bit-1 and bit-2). The element with hash 0x4242 is present in IBF-A and IBF-B and is |
621 | removed by the set difference operation (bit-4). | 641 | removed by the set difference operation (bit-4). |
622 | </t> | 642 | </t> |
623 | </section> | 643 | </section> |
@@ -719,7 +739,10 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
719 | peers exceeds a certain threshold, the overhead to determine which elements are different outweighs | 739 | peers exceeds a certain threshold, the overhead to determine which elements are different outweighs |
720 | the overhead of sending the complete set. In this case, the most efficient method can be to just | 740 | the overhead of sending the complete set. In this case, the most efficient method can be to just |
721 | exchange the full sets. | 741 | exchange the full sets. |
722 | ############# IMAGE ################## | 742 | </t> |
743 | <t> | ||
744 | <!-- TODO: Add smaller version --> | ||
745 | <eref target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg">Link to statemachine diagram</eref> | ||
723 | </t> | 746 | </t> |
724 | <t> | 747 | <t> |
725 | The second possibility is that the difference of the sets is small compared to the set size. | 748 | 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 | | |||
751 | transitions into the <strong>Full Sending</strong> state. | 774 | transitions into the <strong>Full Sending</strong> state. |
752 | </t> | 775 | </t> |
753 | <t> | 776 | <t> |
754 | ############# Statemaschine diagram full mode ################## | 777 | <!-- TODO: Add smaller version --> |
778 | <eref target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg">Link to statemachine diagram</eref> | ||
755 | </t> | 779 | </t> |
756 | <t><strong>The behavior of the participants the different state is described below:</strong></t> | 780 | <t><strong>The behavior of the participants the different state is described below:</strong></t> |
757 | <dl> | 781 | <dl> |
@@ -797,7 +821,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
797 | is called the passive peer. | 821 | is called the passive peer. |
798 | </t> | 822 | </t> |
799 | <t> | 823 | <t> |
800 | ############# Statemaschine Delta Synchronisation Mode ################## | 824 | <!-- TODO: Add smaler version --> |
825 | <eref target="https://git.gnunet.org/lsd0003.git/plain/statemaschine/full_state_maschine.jpg">Link to statemachine diagram</eref> | ||
801 | </t> | 826 | </t> |
802 | <t><strong>The behavior of the participants the different states is described below:</strong></t> | 827 | <t><strong>The behavior of the participants the different states is described below:</strong></t> |
803 | <dl> | 828 | <dl> |
@@ -835,21 +860,30 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
835 | is received if the active peer has decoded an element that is present in the active peers set and may be missing in the | 860 | is received if the active peer has decoded an element that is present in the active peers set and may be missing in the |
836 | 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 | 861 | 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 |
837 | the passive peer, the passive peer MUST answer with a <em><xref target="messages_demand" format="title" /></em> message | 862 | the passive peer, the passive peer MUST answer with a <em><xref target="messages_demand" format="title" /></em> message |
838 | for that SHA-512 hash and remember that it issued this demand. | 863 | 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. |
839 | </dd> | 864 | </dd> |
840 | <dt><em><xref target="messages_elements" format="title" /></em> message:</dt> | 865 | <dt><em><xref target="messages_elements" format="title" /></em> message:</dt> |
841 | <dd> | 866 | <dd> |
842 | A element that is received is validated and safed and not further action is taken. | 867 | When a new element message has been received the peer checks if a corresponding |
843 | FIXME: Eh, don't we need to (1) check that we did in fact DEMAND this element, and (2) strike it | 868 | <em><xref target="messages_demand" format="title" /></em> for the element has been sent |
844 | from the list of pending demands? | 869 | and the demand is still unsatisfied. |
870 | If the element has been demanded the peer checks the element for validity, removed it from the list | ||
871 | of pending demands and then then saves the element to the the set otherwise the peer | ||
872 | rejects the element. | ||
845 | </dd> | 873 | </dd> |
846 | <dt><em><xref target="messages_ibf" format="title" /></em> message:</dt> | 874 | <dt><em><xref target="messages_ibf" format="title" /></em> message:</dt> |
847 | <dd> | 875 | <dd> |
848 | If an <em><xref target="messages_ibf" format="title" /></em> message is received, this | 876 | If an <em><xref target="messages_ibf" format="title" /></em> message is received, this |
849 | indicates that decoding of the IBF on the active site has failed and roles should be swapped. | 877 | indicates that decoding of the IBF on the active site has failed and roles should be swapped. |
850 | The receiving passive peer transitions into the <strong>Active Decoding</strong> state | 878 | The receiving passive peer transitions into the <strong>Expecting IBF Last</strong> state, |
851 | or into the <strong>Expecting IBF Last</strong> state depending on how many IBFs are sent. | 879 | and waits for more <em><xref target="messages_ibf" format="title" /></em> messages |
852 | FIXME: really should use two IBF message types (IBF_DATA, IBF_LAST). | 880 | or the final <em><xref target="messages_ibf_last" format="title" /></em> message to be received. |
881 | </dd> | ||
882 | <dt><em><xref target="messages_ibf_last" format="title" /></em> message:</dt> | ||
883 | <dd> | ||
884 | If an <em><xref target="messages_ibf_last" format="title" /></em> message is received this | ||
885 | indicates that the there is just one IBF slice and a direct state and role transition from | ||
886 | <strong>Passive Decoding</strong> to <strong>Active Decoding</strong> is initiated. | ||
853 | </dd> | 887 | </dd> |
854 | <dt><em><xref target="messages_done" format="title" /></em> message:</dt> | 888 | <dt><em><xref target="messages_done" format="title" /></em> message:</dt> |
855 | <dd> | 889 | <dd> |
@@ -877,15 +911,18 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
877 | <t> | 911 | <t> |
878 | In case the IBF does not successfully decode anymore, the active peer sends a new IBF to the passive client | 912 | In case the IBF does not successfully decode anymore, the active peer sends a new IBF to the passive client |
879 | and changes into <strong>Passive Decoding</strong> state. This initiates a role swap. | 913 | and changes into <strong>Passive Decoding</strong> state. This initiates a role swap. |
880 | FIXME: On what basis is the new IBF constructed? Specifically, which set is used? Do we | 914 | To reduce overhead and prevent double transmission of offers and elements the new IBF is created |
881 | wait for the completion of pending demands first? How do L/k/M change? Some of this should | 915 | on the new complete set after all demands and inquiries have been satisfied. |
882 | be detailed here, but the full details likely need a separate section on the algorithms. | 916 | |
917 | </t> | ||
918 | <t> | ||
919 | As soon as the active peer successfully finished decoding the IBF, the active peer sends a | ||
920 | <em><xref target="messages_done" format="title" /></em> message to the passive peer. | ||
883 | </t> | 921 | </t> |
884 | <t> | 922 | <t> |
885 | All other actions taken by the active peer depend on the message the active peer receives from | 923 | All other actions taken by the active peer depend on the message the active peer receives from |
886 | the passive peer. The actions are described below on a per message basis: | 924 | the passive peer. The actions are described below on a per message basis: |
887 | </t> | 925 | </t> |
888 | <!-- FIXME: Done message generation not described anywhere! --> | ||
889 | <dl> | 926 | <dl> |
890 | <dt><em><xref target="messages_offer" format="title" /></em> message:</dt> | 927 | <dt><em><xref target="messages_offer" format="title" /></em> message:</dt> |
891 | <dd> | 928 | <dd> |
@@ -894,7 +931,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
894 | the active peer. If a Inquiry has been sent and <!-- FIXME: is this indeed a condition that is checked? --> | 931 | the active peer. If a Inquiry has been sent and <!-- FIXME: is this indeed a condition that is checked? --> |
895 | the offered element is missing in the active peers set, | 932 | the offered element is missing in the active peers set, |
896 | the active peer sends a <em><xref target="messages_demand" format="title" /></em> message to the | 933 | the active peer sends a <em><xref target="messages_demand" format="title" /></em> message to the |
897 | passive peer. | 934 | passive peer. The send demand need to be added to a list with unsatisfied demands. |
935 | In the case the received offer is for an element that is already in the set of the peer the offer is ignored. | ||
898 | <!-- FIXME: what happens if the offer is for an element that is not missing? I think then we just ignore it, right? --> | 936 | <!-- FIXME: what happens if the offer is for an element that is not missing? I think then we just ignore it, right? --> |
899 | </dd> | 937 | </dd> |
900 | <dt><em><xref target="messages_demand" format="title" /></em> message:</dt> | 938 | <dt><em><xref target="messages_demand" format="title" /></em> message:</dt> |
@@ -904,23 +942,31 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
904 | the active peer. The active peer satisfies the demand of the passive peer by sending | 942 | the active peer. The active peer satisfies the demand of the passive peer by sending |
905 | <em><xref target="messages_elements" format="title" /></em> message if a offer request | 943 | <em><xref target="messages_elements" format="title" /></em> message if a offer request |
906 | for the element has been sent. | 944 | for the element has been sent. |
907 | FIXME: Do we really check that we first made an offer? FIXME: what happens if | 945 | <!-- IMPLEMENT: This is not implemented in code // Change --> |
908 | we do not have an element with the respective SHA-512 hash? | 946 | In the case the demanded element does not exist in the |
909 | FIXME: should we check that a demand cannot be sent repeatedly for the same element? | 947 | set there was probably a bucket decoded that was not really pure so potentially all <em><xref target="messages_offer" format="title" /></em> |
948 | and <em><xref target="messages_demand" format="title" /></em> messages sent after are invalid | ||
949 | in this case a role change active -> passive with a new IBF is easiest. | ||
950 | If a demand for the same element is received multiple times the demands should be | ||
951 | discarded. | ||
952 | <!-- IMPLEMENT: This is not implemented in code // Change --> | ||
953 | <!--FIXME: Do we really check that we first made an offer?--> | ||
910 | </dd> | 954 | </dd> |
911 | <dt><em><xref target="messages_elements" format="title" /></em> message:</dt> | 955 | <dt><em><xref target="messages_elements" format="title" /></em> message:</dt> |
912 | <dd> | 956 | <dd> |
913 | A element that is received is validated and saved and not further action is taken. | 957 | A element that is received is marked in the list of demanded elements as satisfied, validated and |
914 | FIXME: what if we receive elements we already know? Is that cause for failure? | 958 | saved and not further action is taken. |
915 | FIXME: Do we not need to remember that our demands were satisfied? | 959 | Elements that are not demanded or already known are discarded. |
916 | </dd> | 960 | </dd> |
917 | <dt><em><xref target="messages_done" format="title" /></em> message:</dt> | 961 | <dt><em><xref target="messages_done" format="title" /></em> message:</dt> |
918 | <dd> | 962 | <dd> |
919 | Receiving the message <em><xref target="messages_done" format="title" /></em> indicates | 963 | Receiving the message <em><xref target="messages_done" format="title" /></em> indicates |
920 | that all demands of the passive peer have been satisfied. The active peer then changes into the | 964 | that all demands of the passive peer have been satisfied. The active peer then changes into the |
921 | state <strong>Finish Closing</strong> state. | 965 | state <strong>Finish Closing</strong> state. |
922 | FIXME: We cannot really receive this message before we completed decoding the IBF and send DONE to the passive peer. | 966 | <!-- IMPLEMENT: This is not implemented in code // Change --> |
923 | So that might be an additional constraint to check here! | 967 | If the IBF is not finished decoding and the <em><xref target="messages_done" format="title" /></em> |
968 | is received the other peer is not in compliance with the protocol and the set reconciliation MUST be aborted. | ||
969 | <!-- IMPLEMENT: This is not implemented in code // Change --> | ||
924 | </dd> | 970 | </dd> |
925 | </dl> | 971 | </dl> |
926 | </dd> | 972 | </dd> |
@@ -928,7 +974,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
928 | <dd> | 974 | <dd> |
929 | <t> | 975 | <t> |
930 | In the <strong>Expecing IBF Last</strong> state the active peer continuously receives <em><xref target="messages_ibf" format="title" /></em> | 976 | In the <strong>Expecing IBF Last</strong> state the active peer continuously receives <em><xref target="messages_ibf" format="title" /></em> |
931 | messages from the passive peer. When the last <em><xref target="messages_ibf" format="title" /></em> message is received | 977 | messages from the passive peer. When the last <em><xref target="messages_ibf_last" format="title" /></em> message is received |
932 | the active peer changes into <strong>Active Decoding</strong> state. | 978 | the active peer changes into <strong>Active Decoding</strong> state. |
933 | </t> | 979 | </t> |
934 | </dd> | 980 | </dd> |
@@ -936,8 +982,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
936 | <dd> | 982 | <dd> |
937 | <t> | 983 | <t> |
938 | In this states the peers are waiting for all demands to be satisfied and for the synchronisation | 984 | In this states the peers are waiting for all demands to be satisfied and for the synchronisation |
939 | to be completed. When all demands are satisfied the peer changes into state <strong>done</strong>. | 985 | to be completed. When all demands are satisfied the peer changes into state <strong>Finished</strong>. |
940 | FIXME: I thought "done" was a message, and the final state was called "Finished"!??!? | ||
941 | </t> | 986 | </t> |
942 | </dd> | 987 | </dd> |
943 | </dl> | 988 | </dl> |
@@ -959,10 +1004,12 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
959 | <t> | 1004 | <t> |
960 | There are two main cases when a <xref target="modeofoperation_full-sync" format="title" /> | 1005 | There are two main cases when a <xref target="modeofoperation_full-sync" format="title" /> |
961 | is always used. | 1006 | is always used. |
962 | The first case is when one of the peers announces having an empty set. FIXME: HOW is this announced? | 1007 | The first case is when one of the peers announces having an empty set. This is announced by setting |
1008 | the SETSIZE field in the <em><xref target="messages_se" format="title" /></em> to 0. | ||
963 | The second case is if the application requested full synchronization explicitly. | 1009 | The second case is if the application requested full synchronization explicitly. |
964 | This is useful for testing and should not be used in production. | 1010 | This is useful for testing and should not be used in production. |
965 | </t> | 1011 | </t> |
1012 | <!-- | ||
966 | <t> | 1013 | <t> |
967 | ############# NOTE ############ | 1014 | ############# NOTE ############ |
968 | To ensure that ...... the difference is multiplied by 1.5 if there are more than 200 elements differences between the sets (WHY? line 1398). | 1015 | 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 | | |||
970 | than 25% or the set size of the receiving peer is zero. Otherwise the delta synchronisation mode is used. | 1017 | than 25% or the set size of the receiving peer is zero. Otherwise the delta synchronisation mode is used. |
971 | ############# NOTE END############ | 1018 | ############# NOTE END############ |
972 | </t> | 1019 | </t> |
1020 | --> | ||
973 | </section> | 1021 | </section> |
974 | </section> | 1022 | </section> |
975 | 1023 | ||
@@ -990,8 +1038,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
990 | This message is sent in the transition between the <strong>Initiating Connection</strong> state and the <strong>Expect SE</strong> state. | 1038 | This message is sent in the transition between the <strong>Initiating Connection</strong> state and the <strong>Expect SE</strong> state. |
991 | </t> | 1039 | </t> |
992 | <t> | 1040 | <t> |
993 | If a peer receives this message and is willing to run the protocol, it answers by sending back a Strata estimator message. | 1041 | 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. |
994 | FIXME: turn 'strata estimator' into a link! | ||
995 | Otherwise it simply closes the connection. | 1042 | Otherwise it simply closes the connection. |
996 | </t> | 1043 | </t> |
997 | </section> | 1044 | </section> |
@@ -1023,8 +1070,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1023 | </dd> | 1070 | </dd> |
1024 | <dt>OPERATION TYPE</dt> | 1071 | <dt>OPERATION TYPE</dt> |
1025 | <dd> | 1072 | <dd> |
1026 | is a 32-bit unsigned integer which describes the type of operation that should be initiated. | 1073 | is a 32-bit unsigned integer which describes the type of operation that should be initiated on the set. The filed can have three |
1027 | FIXME: unclear what this is. What operation types are there? What are the numeric values? | 1074 | different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. <!-- @Christian can you check? --> |
1075 | NONE should never occur and signals the set supports no operation and is just for local use. | ||
1076 | INTERSECTION returns only elements that are in both sets and the default case UNION, return all | ||
1077 | elements that are in at least one of the sets. | ||
1028 | </dd> | 1078 | </dd> |
1029 | <dt>ELEMENT COUNT</dt> | 1079 | <dt>ELEMENT COUNT</dt> |
1030 | <dd> | 1080 | <dd> |
@@ -1048,16 +1098,10 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1048 | </t> | 1098 | </t> |
1049 | <t> | 1099 | <t> |
1050 | The <em>IBF</em> message is sent at the start of the protocol from the initiating peer in the transaction | 1100 | The <em>IBF</em> message is sent at the start of the protocol from the initiating peer in the transaction |
1051 | between <strong>Expect SE</strong> -> <strong>Passive Decoding</strong> or when the IBF does not decode and there is a role change in the | 1101 | between <strong>Expect SE</strong> -> <strong>Expecting IBF Last</strong> or when the IBF does not |
1052 | transition between <strong>Active Decoding</strong> -> <strong>Passive Decoding</strong>. | 1102 | decode and there is a role change in the transition between <strong>Active Decoding</strong> -> <strong>Expecting IBF Last</strong>. |
1053 | </t> | 1103 | This message is only sent if there are more than one IBF slice to sent, in the case there is just |
1054 | <t> | 1104 | one slice the <xref target="messages_ibf_last" format="title" /> message is sent. |
1055 | This message is received either in the state transmission between <strong>Expecting IBF</strong> -> <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong> | ||
1056 | if multiple IBFs need to be transmitted or if only one IBF needs to be transmitted directly from | ||
1057 | <strong>Expecting IBF</strong> -> <strong>Active Decoding</strong>. Since the active and passive roles can be reversed in this | ||
1058 | protocol, receiving the <em>IBF</em> message can initiate a role change so receiving | ||
1059 | the message can initiate the transitions <strong>Passive Decoding</strong> -> <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong> and | ||
1060 | <strong>Passive Decoding</strong> -> <strong>Active Decoding</strong>. | ||
1061 | </t> | 1105 | </t> |
1062 | </section> | 1106 | </section> |
1063 | <section anchor="messages_ibf_structure" numbered="true" toc="default"> | 1107 | <section anchor="messages_ibf_structure" numbered="true" toc="default"> |
@@ -1070,7 +1114,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1070 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1114 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1071 | | OFFSET | SALT | | 1115 | | OFFSET | SALT | |
1072 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1116 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1073 | | IBF-SLICES | 1117 | | IBF-SLICE |
1074 | + / | 1118 | + / |
1075 | / / | 1119 | / / |
1076 | / / | 1120 | / / |
@@ -1098,21 +1142,36 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1098 | </dd> | 1142 | </dd> |
1099 | <dt>OFFSET</dt> | 1143 | <dt>OFFSET</dt> |
1100 | <dd> | 1144 | <dd> |
1101 | is a 32-bit unsigned integer which signals the offset of the strata estimator. ### Beser erklähren postion der nachfolgenden ibf slices im orignial | 1145 | is a 32-bit unsigned integer which signals the offset to the following ibf slices in the original. |
1102 | </dd> | 1146 | </dd> |
1103 | <dt>SALT</dt> | 1147 | <dt>SALT</dt> |
1104 | <dd> | 1148 | <dd> |
1105 | is a 32-bit unsigned integer that contains the salt which was used to create the | 1149 | is a 32-bit unsigned integer that contains the salt which was used to create the |
1106 | IBF. | 1150 | IBF. |
1107 | </dd> | 1151 | </dd> |
1108 | <dt>IBF-SLICES</dt> | 1152 | <dt>IBF-SLICE</dt> |
1109 | <dd> | 1153 | <dd> |
1110 | are variable count of slices in an array. A single slice contains out of a 64-bit Key, a | 1154 | <t> |
1111 | 32-bit Key Hash and an 8-bit count. | 1155 | are variable count of slices in an array. A single slice contains out multiple 64-bit IDSUMS, |
1156 | 32-bit HASHSUMS and 8-bit COUNTERS. In the network order the array of IDSUMS is first, followed | ||
1157 | by an array of HASHSUMS and ended with an array of COUNTERS. Length of the array is defined | ||
1158 | by MIN( 2^ORDER - OFFSET, MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as | ||
1159 | 32768 divided by the BUCKET_SIZE which is 13-byte (104-bit). | ||
1160 | </t> | ||
1161 | <t> | ||
1162 | The IDSUMS The HASHSUMS is calculated as a standard CRC32 check sum from | ||
1163 | the key of the element. | ||
1164 | <!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the | ||
1165 | salt_key function in gnunet-service-set_union.c file and the ibf_insert_into (why exponentiation? ^=) in the ibf.c | ||
1166 | The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32. | ||
1167 | --> | ||
1168 | </t> | ||
1169 | |||
1170 | <!-- | ||
1112 | FIXME: this is not sufficiently precise! How are the element IDs (and IDSUMS) computed? | 1171 | FIXME: this is not sufficiently precise! How are the element IDs (and IDSUMS) computed? |
1113 | How are the HASHes (and HASHSUMS) computed? Which byte order is used? What role does | 1172 | How are the HASHes (and HASHSUMS) computed? Which byte order is used? What role does |
1114 | the SALT have in these computations? Definitively needs DETAILED algorithm(s) and | 1173 | the SALT have in these computations? Definitively needs DETAILED algorithm(s) and |
1115 | test vectors. | 1174 | test vectors.--> |
1116 | </dd> | 1175 | </dd> |
1117 | </dl> | 1176 | </dl> |
1118 | <figure anchor="figure_ibf_slice"> | 1177 | <figure anchor="figure_ibf_slice"> |
@@ -1120,9 +1179,13 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1120 | IBF-SLICE | 1179 | IBF-SLICE |
1121 | 0 8 16 24 32 40 48 56 | 1180 | 0 8 16 24 32 40 48 56 |
1122 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1181 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1123 | | KEY | | 1182 | | IDSUMS | |
1124 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1183 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1125 | | KEY HASH | COUNT | | 1184 | | IDSUMS | |
1185 | +-----+-----+-----+-----+-----+-----+-----+-----+ | ||
1186 | | HASHSUMS | HASHSUMS | | ||
1187 | +-----+-----+-----+-----+-----+-----+-----+-----+ | ||
1188 | | COUNTERS | COUNTERS | | ||
1126 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1189 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1127 | / / | 1190 | / / |
1128 | / / | 1191 | / / |
@@ -1131,6 +1194,28 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1131 | </section> | 1194 | </section> |
1132 | </section> | 1195 | </section> |
1133 | 1196 | ||
1197 | <section anchor="messages_ibf_last" numbered="true" toc="default"> | ||
1198 | <name>IBF</name> | ||
1199 | |||
1200 | <section anchor="messages_ibf_last_description" numbered="true" toc="default"> | ||
1201 | <name>Description</name> | ||
1202 | <t> | ||
1203 | This message indicates to the remote peer that all slices of the bloom filter have been sent. | ||
1204 | The binary structure is exactly the same as the <xref target="messages_ibf_structure" format="title" /> of | ||
1205 | the message <xref target="messages_ibf" format="title" /> with a different "MSG TYPE" | ||
1206 | which is defined in <xref target="gana" format="title" /> "SETU_P2P_IBF_LAST". | ||
1207 | </t> | ||
1208 | <t> | ||
1209 | Receiving this message initiates the state transmissions | ||
1210 | <strong>Expecting IBF Last</strong> -> <strong>Active Decoding</strong>, | ||
1211 | <strong>Expecting IBF</strong> -> <strong>Active Decoding</strong> and | ||
1212 | <strong>Passive Decoding</strong> -> <strong>Active Decoding</strong>. This message | ||
1213 | can initiate a peer the roll change from <strong>Active Decoding</strong> to | ||
1214 | <strong>Passive Decoding</strong>. | ||
1215 | </t> | ||
1216 | </section> | ||
1217 | </section> | ||
1218 | |||
1134 | <section anchor="messages_elements" numbered="true" toc="default"> | 1219 | <section anchor="messages_elements" numbered="true" toc="default"> |
1135 | <name>Elements</name> | 1220 | <name>Elements</name> |
1136 | 1221 | ||
@@ -1356,8 +1441,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1356 | <t> | 1441 | <t> |
1357 | The done message is sent when all <em><xref target="messages_demand" format="title" /></em> messages | 1442 | The done message is sent when all <em><xref target="messages_demand" format="title" /></em> messages |
1358 | have been successfully satisfied and the set is complete synchronized. | 1443 | have been successfully satisfied and the set is complete synchronized. |
1359 | FIXME: we might want to consider adding an additional final checksum (XOR SHA-512 hash) over | 1444 | <!-- IMPLEMENT: This is not implemented in code // Change --> |
1360 | all elements to this message, to ensure that really both sides ended up with the same set? | 1445 | A final checksum (XOR SHA-512 hash) over all elements of the set is added to the message |
1446 | to allow the other peer to make sure that the sets are equal. | ||
1447 | <!-- IMPLEMENT: This is not implemented in code // Change --> | ||
1448 | |||
1361 | </t> | 1449 | </t> |
1362 | <t> | 1450 | <t> |
1363 | This message is exclusively sent in the <xref target="modeofoperation_individual-elements" format="title" />. | 1451 | This message is exclusively sent in the <xref target="modeofoperation_individual-elements" format="title" />. |
@@ -1371,6 +1459,8 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1371 | +-----+-----+-----+-----+ | 1459 | +-----+-----+-----+-----+ |
1372 | | MSG SIZE | MSG TYPE | | 1460 | | MSG SIZE | MSG TYPE | |
1373 | +-----+-----+-----+-----+ | 1461 | +-----+-----+-----+-----+ |
1462 | | HASH | ||
1463 | +-----+-----+-----+-----+ | ||
1374 | ]]></artwork> | 1464 | ]]></artwork> |
1375 | <!-- <postamble>which is a very simple example.</postamble>--> | 1465 | <!-- <postamble>which is a very simple example.</postamble>--> |
1376 | </figure> | 1466 | </figure> |
@@ -1384,6 +1474,11 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1384 | <dd> | 1474 | <dd> |
1385 | the type of SETU_P2P_DONE as registered in <xref target="gana" format="title" /> in network byte order. | 1475 | the type of SETU_P2P_DONE as registered in <xref target="gana" format="title" /> in network byte order. |
1386 | </dd> | 1476 | </dd> |
1477 | <dt>HASH</dt> | ||
1478 | <dd> | ||
1479 | is a 512-bit hash of the set to allow a final equality check. | ||
1480 | </dd> | ||
1481 | |||
1387 | </dl> | 1482 | </dl> |
1388 | </section> | 1483 | </section> |
1389 | </section> | 1484 | </section> |
@@ -1514,7 +1609,7 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1514 | </dd> | 1609 | </dd> |
1515 | <dt>SETSIZE</dt> | 1610 | <dt>SETSIZE</dt> |
1516 | <dd> | 1611 | <dd> |
1517 | 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 | 1612 | 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 --> |
1518 | </dd> | 1613 | </dd> |
1519 | <dt>SE-SLICES</dt> | 1614 | <dt>SE-SLICES</dt> |
1520 | <dd> | 1615 | <dd> |
@@ -1614,35 +1709,43 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
1614 | 1709 | ||
1615 | </section> | 1710 | </section> |
1616 | 1711 | ||
1712 | |||
1617 | <section anchor="performance" numbered="true" toc="default"> | 1713 | <section anchor="performance" numbered="true" toc="default"> |
1618 | <name>Performance Considerations</name> | 1714 | <name>Performance Considerations</name> |
1715 | <!-- | ||
1716 | <t> | ||
1717 | - TEXT HERE - | ||
1718 | On what basis is the new IBF constructed? Specifically, which set is used? Do we | ||
1719 | wait for the completion of pending demands first? How do L/k/M change? Some of this should | ||
1720 | be detailed here, but the full details likely need a separate section on the algorithms. | ||
1721 | </t> | ||
1722 | --> | ||
1723 | </section> | ||
1724 | |||
1725 | <section anchor="security" numbered="true" toc="default"> | ||
1726 | <name>Security Considerations</name> | ||
1727 | <!-- | ||
1728 | <section anchor="security_crypto" numbered="true" toc="default"> | ||
1729 | <name>BLAH</name> | ||
1619 | <t> | 1730 | <t> |
1620 | --- TEXT HERE --- | 1731 | Bulub. |
1621 | </t> | 1732 | </t> |
1733 | <t> | ||
1734 | Another probabilistic approach to discover bad behaving peers is sampling, in this approach the proving peer needs | ||
1735 | to prove that he is in possession of the elements he claimed to be. This is achieved by the following procedure: | ||
1736 | </t> | ||
1737 | <t> | ||
1738 | The verifying peer chooses some | ||
1739 | random salt and sends the salt to the proving peer. The proving peer salts the hash of elements with the given | ||
1740 | salt from the verifying peer. Then the proving peer calculates the new hashes modulo a number depending on the set sized difference and | ||
1741 | sends all the elements where the modulo calculation equals 0 to the verifying peer. | ||
1742 | As soon as the verifying peer receives the elements the verifying peer can verify that all the elements | ||
1743 | are valid and the modulo calculation equals 0 then the verifying peer can be assured with a high probability | ||
1744 | that the peer is honest about his remaining set size and difference. | ||
1745 | </t> | ||
1622 | </section> | 1746 | </section> |
1623 | 1747 | --> | |
1624 | <section anchor="security" numbered="true" toc="default"> | 1748 | </section> |
1625 | <name>Security Considerations</name> | ||
1626 | <section anchor="security_crypto" numbered="true" toc="default"> | ||
1627 | <name>BLAH</name> | ||
1628 | <t> | ||
1629 | Bulub. | ||
1630 | </t> | ||
1631 | <t> | ||
1632 | Another probabilistic approach to discover bad behaving peers is sampling, in this approach the proving peer needs | ||
1633 | to prove that he is in possession of the elements he claimed to be. This is achieved by the following procedure: | ||
1634 | </t> | ||
1635 | <t> | ||
1636 | The verifying peer chooses some | ||
1637 | random salt and sends the salt to the proving peer. The proving peer salts the hash of elements with the given | ||
1638 | salt from the verifying peer. Then the proving peer calculates the new hashes modulo a number depending on the set sized difference and | ||
1639 | sends all the elements where the modulo calculation equals 0 to the verifying peer. | ||
1640 | As soon as the verifying peer receives the elements the verifying peer can verify that all the elements | ||
1641 | are valid and the modulo calculation equals 0 then the verifying peer can be assured with a high probability | ||
1642 | that the peer is honest about his remaining set size and difference. | ||
1643 | </t> | ||
1644 | </section> | ||
1645 | </section> | ||
1646 | 1749 | ||
1647 | <section anchor="gana" numbered="true" toc="default"> | 1750 | <section anchor="gana" numbered="true" toc="default"> |
1648 | <name>GANA Considerations</name> | 1751 | <name>GANA Considerations</name> |
@@ -1660,8 +1763,9 @@ Type | Name | References | Description | |||
1660 | 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes match a given IBF key. | 1763 | 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes match a given IBF key. |
1661 | 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from a remote peer. | 1764 | 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from a remote peer. |
1662 | 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed | 1765 | 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed |
1663 | 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter. | 1766 | 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter Slice. |
1664 | 566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements. | 1767 | 566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements. |
1768 | 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter Last Slice. | ||
1665 | 568 | SETU_P2P_DONE | [This.I-D] | Set operation is done. | 1769 | 568 | SETU_P2P_DONE | [This.I-D] | Set operation is done. |
1666 | 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed | 1770 | 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed |
1667 | 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronization mode have been send is done. | 1771 | 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 | |||
1687 | <back> | 1791 | <back> |
1688 | <references> | 1792 | <references> |
1689 | <name>Normative References</name> | 1793 | <name>Normative References</name> |
1690 | 1794 | &RFC5869; | |
1691 | &RFC1034; | 1795 | &RFC1034; |
1692 | &RFC1035; | 1796 | &RFC1035; |
1693 | &RFC2782; | 1797 | &RFC2782; |
@@ -1696,7 +1800,6 @@ Type | Name | References | Description | |||
1696 | &RFC3686; | 1800 | &RFC3686; |
1697 | &RFC3826; | 1801 | &RFC3826; |
1698 | &RFC3912; | 1802 | &RFC3912; |
1699 | &RFC5869; | ||
1700 | &RFC5890; | 1803 | &RFC5890; |
1701 | &RFC5891; | 1804 | &RFC5891; |
1702 | &RFC6781; | 1805 | &RFC6781; |