diff options
author | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-01-23 13:35:51 +0100 |
---|---|---|
committer | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-01-23 13:35:51 +0100 |
commit | 90c4bf1f53a952919f814d1d1b6307db0e357611 (patch) | |
tree | be1bbe848138ad654472e5b0e00e6557c4077cdc | |
parent | 05b35b44d9de5b5c535d3e46652734c048674d48 (diff) | |
download | lsd0003-90c4bf1f53a952919f814d1d1b6307db0e357611.tar.gz lsd0003-90c4bf1f53a952919f814d1d1b6307db0e357611.zip |
Fixed some stuff
-rw-r--r-- | draft-summermatter-set-union.xml | 324 |
1 files changed, 221 insertions, 103 deletions
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml index 1eb7a0d..8e30e09 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) <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/gns2014wachs.pdf -->. In GNS, | 84 | System (GNS) <xref target="GNUNET" format="default" />. 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,8 +96,8 @@ | |||
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 <!-- TODO: citate: https://git.gnunet.org/bibliography.git/plain/docs/ba_dold_voting_24aug2014.pdf --> various E-voting | 99 | secure multiparty computations are various E-voting |
100 | protocols which | 100 | protocols <xref target="CryptographicallySecureVoting" format="default"/> 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 |
@@ -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. <!-- TODO: citate: https://www.ics.uci.edu/~eppstein/pubs/EppGooUye-SIGCOMM-11.pdf --> | 128 | implementation of a proposal by Eppstein.<xref target="Eppstein" format="default" /> |
129 | </t> | 129 | </t> |
130 | 130 | ||
131 | <t> | 131 | <t> |
@@ -382,9 +382,9 @@ hashSum | HASHSUM | HASHSUM | HASHSUM | HASHSUM | H.. | |||
382 | +-------------+-------------+-------------+-------------+ | 382 | +-------------+-------------+-------------+-------------+ |
383 | count | 0 | 0 | 0 | 0 | | 383 | count | 0 | 0 | 0 | 0 | |
384 | +-------------+-------------+-------------+-------------+ | 384 | +-------------+-------------+-------------+-------------+ |
385 | idSum | 0000 | 0000 | 0000 | 0000 | | 385 | idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | |
386 | +-------------+-------------+-------------+-------------+ | 386 | +-------------+-------------+-------------+-------------+ |
387 | hashSum | 0000 | 0000 | 0000 | 0000 | | 387 | hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | |
388 | +-------------+-------------+-------------+-------------+ | 388 | +-------------+-------------+-------------+-------------+ |
389 | ]]></artwork> | 389 | ]]></artwork> |
390 | </figure> | 390 | </figure> |
@@ -395,9 +395,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
395 | +-------------+-------------+-------------+-------------+ | 395 | +-------------+-------------+-------------+-------------+ |
396 | count | 0 | 1 | 0 | 1 | | 396 | count | 0 | 1 | 0 | 1 | |
397 | +-------------+-------------+-------------+-------------+ | 397 | +-------------+-------------+-------------+-------------+ |
398 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | | 398 | idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | |
399 | +-------------+-------------+-------------+-------------+ | 399 | +-------------+-------------+-------------+-------------+ |
400 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | 400 | hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | |
401 | +-------------+-------------+-------------+-------------+ | 401 | +-------------+-------------+-------------+-------------+ |
402 | ]]></artwork> | 402 | ]]></artwork> |
403 | </figure> | 403 | </figure> |
@@ -408,9 +408,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | |||
408 | +-------------+-------------+-------------+-------------+ | 408 | +-------------+-------------+-------------+-------------+ |
409 | count | 1 | 2 | 0 | 1 | | 409 | count | 1 | 2 | 0 | 1 | |
410 | +-------------+-------------+-------------+-------------+ | 410 | +-------------+-------------+-------------+-------------+ |
411 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | | 411 | idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | |
412 | +-------------+-------------+-------------+-------------+ | 412 | +-------------+-------------+-------------+-------------+ |
413 | hashSum | 0101 | 0x4343 | 0000 | 0x4242 | | 413 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | |
414 | +-------------+-------------+-------------+-------------+ | 414 | +-------------+-------------+-------------+-------------+ |
415 | ]]></artwork> | 415 | ]]></artwork> |
416 | </figure> | 416 | </figure> |
@@ -433,9 +433,9 @@ hashSum | 0101 | 0x4343 | 0000 | 0x4242 | | |||
433 | +-------------+-------------+-------------+-------------+ | 433 | +-------------+-------------+-------------+-------------+ |
434 | count | 1 | 2 | 0 | 1 | | 434 | count | 1 | 2 | 0 | 1 | |
435 | +-------------+-------------+-------------+-------------+ | 435 | +-------------+-------------+-------------+-------------+ |
436 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | | 436 | idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | |
437 | +-------------+-------------+-------------+-------------+ | 437 | +-------------+-------------+-------------+-------------+ |
438 | hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | 438 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | |
439 | +-------------+-------------+-------------+-------------+ | 439 | +-------------+-------------+-------------+-------------+ |
440 | ]]></artwork> | 440 | ]]></artwork> |
441 | </figure> | 441 | </figure> |
@@ -446,9 +446,9 @@ hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | |||
446 | +-------------+-------------+-------------+-------------+ | 446 | +-------------+-------------+-------------+-------------+ |
447 | count | 0 | 1 | 0 | 1 | | 447 | count | 0 | 1 | 0 | 1 | |
448 | +-------------+-------------+-------------+-------------+ | 448 | +-------------+-------------+-------------+-------------+ |
449 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | | 449 | idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | |
450 | +-------------+-------------+-------------+-------------+ | 450 | +-------------+-------------+-------------+-------------+ |
451 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | 451 | hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | |
452 | +-------------+-------------+-------------+-------------+ | 452 | +-------------+-------------+-------------+-------------+ |
453 | ]]></artwork> | 453 | ]]></artwork> |
454 | </figure> | 454 | </figure> |
@@ -530,9 +530,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | |||
530 | +-------------+-------------+-------------+-------------+ | 530 | +-------------+-------------+-------------+-------------+ |
531 | count | 1 | 2 | 0 | 1 | | 531 | count | 1 | 2 | 0 | 1 | |
532 | +-------------+-------------+-------------+-------------+ | 532 | +-------------+-------------+-------------+-------------+ |
533 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | | 533 | idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | |
534 | +-------------+-------------+-------------+-------------+ | 534 | +-------------+-------------+-------------+-------------+ |
535 | hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | 535 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | |
536 | +-------------+-------------+-------------+-------------+ | 536 | +-------------+-------------+-------------+-------------+ |
537 | ]]></artwork> | 537 | ]]></artwork> |
538 | </figure> | 538 | </figure> |
@@ -546,9 +546,9 @@ hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | | |||
546 | +-------------+-------------+-------------+-------------+ | 546 | +-------------+-------------+-------------+-------------+ |
547 | count | 0 | 1 | 0 | 1 | | 547 | count | 0 | 1 | 0 | 1 | |
548 | +-------------+-------------+-------------+-------------+ | 548 | +-------------+-------------+-------------+-------------+ |
549 | idSum | 0000 | 0x0102 | 0000 | 0x0102 | | 549 | idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | |
550 | +-------------+-------------+-------------+-------------+ | 550 | +-------------+-------------+-------------+-------------+ |
551 | hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | 551 | hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | |
552 | +-------------+-------------+-------------+-------------+ | 552 | +-------------+-------------+-------------+-------------+ |
553 | ]]></artwork> | 553 | ]]></artwork> |
554 | </figure> | 554 | </figure> |
@@ -563,9 +563,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | | |||
563 | +-------------+-------------+-------------+-------------+ | 563 | +-------------+-------------+-------------+-------------+ |
564 | count | 0 | 0 | 0 | 0 | | 564 | count | 0 | 0 | 0 | 0 | |
565 | +-------------+-------------+-------------+-------------+ | 565 | +-------------+-------------+-------------+-------------+ |
566 | idSum | 0000 | 0000 | 0000 | 0000 | | 566 | idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | |
567 | +-------------+-------------+-------------+-------------+ | 567 | +-------------+-------------+-------------+-------------+ |
568 | hashSum | 0000 | 0000 | 0000 | 0000 | | 568 | hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | |
569 | +-------------+-------------+-------------+-------------+ | 569 | +-------------+-------------+-------------+-------------+ |
570 | ]]></artwork> | 570 | ]]></artwork> |
571 | </figure> | 571 | </figure> |
@@ -603,9 +603,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | | |||
603 | +-------------+-------------+-------------+-------------+ | 603 | +-------------+-------------+-------------+-------------+ |
604 | count | 1 | 2 | 0 | 1 | | 604 | count | 1 | 2 | 0 | 1 | |
605 | +-------------+-------------+-------------+-------------+ | 605 | +-------------+-------------+-------------+-------------+ |
606 | idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | | 606 | idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | |
607 | +-------------+-------------+-------------+-------------+ | 607 | +-------------+-------------+-------------+-------------+ |
608 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | | 608 | hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | |
609 | +-------------+-------------+-------------+-------------+ | 609 | +-------------+-------------+-------------+-------------+ |
610 | ]]></artwork> | 610 | ]]></artwork> |
611 | </figure> | 611 | </figure> |
@@ -616,9 +616,9 @@ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | | |||
616 | +-------------+-------------+-------------+-------------+ | 616 | +-------------+-------------+-------------+-------------+ |
617 | count | 0 | 1 | 1 | 1 | | 617 | count | 0 | 1 | 1 | 1 | |
618 | +-------------+-------------+-------------+-------------+ | 618 | +-------------+-------------+-------------+-------------+ |
619 | idSum | 0000 | 0x0102 | 0x1345 | 0x0102 | | 619 | idSum | 0x0000 | 0x0102 | 0x1345 | 0x0102 | |
620 | +-------------+-------------+-------------+-------------+ | 620 | +-------------+-------------+-------------+-------------+ |
621 | hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 | | 621 | hashSum | 0x0000 | 0x4242 | 0x5050 | 0x4242 | |
622 | +-------------+-------------+-------------+-------------+ | 622 | +-------------+-------------+-------------+-------------+ |
623 | ]]></artwork> | 623 | ]]></artwork> |
624 | </figure> | 624 | </figure> |
@@ -629,9 +629,9 @@ hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 | | |||
629 | +-------------+-------------+-------------+-------------+ | 629 | +-------------+-------------+-------------+-------------+ |
630 | count | 1 | 1 | -1 | 0 | | 630 | count | 1 | 1 | -1 | 0 | |
631 | +-------------+-------------+-------------+-------------+ | 631 | +-------------+-------------+-------------+-------------+ |
632 | idSum | 0000 | 0x0304 | 0x1345 | 0000 | | 632 | idSum | 0x0304 | 0x0304 | 0x1345 | 0x0000 | |
633 | +-------------+-------------+-------------+-------------+ | 633 | +-------------+-------------+-------------+-------------+ |
634 | hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | 634 | hashSum | 0x0101 | 0x0101 | 0x5050 | 0x0000 | |
635 | +-------------+-------------+-------------+-------------+ | 635 | +-------------+-------------+-------------+-------------+ |
636 | ]]></artwork> | 636 | ]]></artwork> |
637 | </figure> | 637 | </figure> |
@@ -641,7 +641,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
641 | removed by the set difference operation (bit-4). | 641 | removed by the set difference operation (bit-4). |
642 | </t> | 642 | </t> |
643 | </section> | 643 | </section> |
644 | |||
645 | </section> | 644 | </section> |
646 | 645 | ||
647 | <section anchor="ibf_format" numbered="true" toc="default"> | 646 | <section anchor="ibf_format" numbered="true" toc="default"> |
@@ -691,8 +690,117 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
691 | also again a reasonable size for many CPU | 690 | also again a reasonable size for many CPU |
692 | architectures. | 691 | architectures. |
693 | </t> | 692 | </t> |
693 | <section anchor="ibf_format_id_generation" numbered="true" toc="default"> | ||
694 | <name>ID Calculation</name> | ||
695 | <t> | ||
696 | The ID is generated as 64-bit output from a <relref section="2" target="RFC5869" displayFormat="of">HKDF construction</relref> | ||
697 | with HMAC-SHA512 as XTR and HMAC-SHA256 as PRF and salt is set to the unsigned 64-bit equivalent of 0. | ||
698 | The output is then truncated to 64-bit. | ||
699 | Its important that the elements can be redistributed over the buckets in case the IBF does not | ||
700 | decode, that's why the ID is salted with a random salt given in the SALT field of this message. | ||
701 | Salting is done by calculation the a random salt modulo 64 (using only the lowest 6-bits of the salt) | ||
702 | and do a bitwise right rotation of output of KDF by the 6-bit salts numeric representation. | ||
703 | </t> | ||
704 | <t> | ||
705 | Representation in pseudocode: | ||
706 | </t> | ||
707 | <figure anchor="ibf_format_id_generation_pseudo_code"> | ||
708 | <artwork name="" type="" align="left" alt=""><![CDATA[ | ||
709 | # INPUTS: | ||
710 | # key: Pre calculated and truncated key from id_calculation function | ||
711 | # ibf_salt: Salt of the IBF | ||
712 | # OUTPUT: | ||
713 | # value: salted key | ||
714 | FUNCTION salt_key(key,ibf_salt): | ||
715 | s = ibf_salt % 64; | ||
716 | k = key | ||
717 | |||
718 | /* rotate ibf key */ | ||
719 | k = (k >> s) | (k << (64 - k)) | ||
720 | return key | ||
721 | |||
722 | |||
723 | # INPUTS: | ||
724 | # element: Element to calculated id from. | ||
725 | # salt: Salt of the IBF | ||
726 | # OUTPUT: | ||
727 | # value: the ID of the element | ||
728 | |||
729 | FUNCTION id_calculation (element,ibf_salt): | ||
730 | salt = 0 | ||
731 | XTR=HMAC-SHA256 | ||
732 | PRF=HMAC-SHA256 | ||
733 | key = HKDF(XTR, PRF, salt, element) | ||
734 | key = key modulo 2^64 // Truncate | ||
735 | return salt_key(key,ibf_salt) | ||
736 | |||
737 | |||
738 | ]]></artwork> | ||
739 | </figure> | ||
740 | </section> | ||
741 | <section anchor="ibf_format_bucket_identification" numbered="true" toc="default"> | ||
742 | <name>Mapping Function</name> | ||
743 | <t> | ||
744 | The mapping function M as described above in the figure <xref target="bf_mapping_function_math" format="default" /> | ||
745 | decides in which buckets the ID and HASH have to be binary XORed to. In practice | ||
746 | there the following algorithm is used: | ||
747 | </t> | ||
748 | <t> | ||
749 | The first index is simply the HASH modulo the IBF size. The second | ||
750 | index is calculated by creating a new 64-bit value by shifting the 32-bit | ||
751 | value left and setting the lower 32-bit to the number of indexes already processed. From the | ||
752 | resulting 64-bit value a CRC32 checksum is created the second index is now the modulo of the | ||
753 | CRC32 output this is repeated until the predefined amount indexes is generated. | ||
754 | In the case a index is hit twice, which would mean this bucket could not get pure again, | ||
755 | the second hit is just skipped and the next iteration is used as. | ||
756 | </t> | ||
757 | <figure anchor="ibf_format_bucket_identification_pseudo_code"> | ||
758 | <artwork name="" type="" align="left" alt=""><![CDATA[ | ||
759 | # INPUTS: | ||
760 | # key: Is the ID of the element calculated in the id_calculation function above. | ||
761 | # number_of_buckets_per_element: Pre-defined count of buckets elements are inserted into | ||
762 | # ibf_size: the size of the ibf (count of buckets) | ||
763 | # OUTPUT: | ||
764 | # dst: Array with bucket IDs to insert ID and HASH | ||
765 | |||
766 | FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size) | ||
767 | bucket = CRC32(key) | ||
768 | |||
769 | i = 0 | ||
770 | filled = 0 | ||
771 | WHILE filled < number_of_buckets_per_element | ||
772 | |||
773 | element_already_in_bucket = false | ||
774 | j = 0 | ||
775 | WHILE j < filled | ||
776 | IF dst[j] == bucket modulo ibf_size THEN | ||
777 | element_already_in_bucket = true | ||
778 | ENDIF | ||
779 | j++ | ||
780 | ENDWHILE | ||
781 | |||
782 | IF !element_already_in_bucket THEN | ||
783 | dst[filled++] = bucket modulo ibf_size | ||
784 | ENDIF | ||
785 | |||
786 | x = (bucket << 32) | i | ||
787 | bucket = CRC32(x) | ||
788 | |||
789 | i++ | ||
790 | ENDWHILE | ||
791 | return dst | ||
792 | ]]></artwork> | ||
793 | </figure> | ||
794 | </section> | ||
795 | <section anchor="ibf_format_HASH_calculation" numbered="true" toc="default"> | ||
796 | <name>HASH calculation</name> | ||
797 | <t> | ||
798 | The HASH is calculated by calculating the CRC32 checksum of the 64-bit ID value | ||
799 | which returns a 32-bit value. | ||
800 | </t> | ||
694 | </section> | 801 | </section> |
695 | </section> | 802 | </section> |
803 | </section> | ||
696 | 804 | ||
697 | <section anchor="se" numbered="true" toc="default"> | 805 | <section anchor="se" numbered="true" toc="default"> |
698 | <name>Strata Estimator</name> | 806 | <name>Strata Estimator</name> |
@@ -1056,7 +1164,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1056 | / / | 1164 | / / |
1057 | / / | 1165 | / / |
1058 | ]]></artwork> | 1166 | ]]></artwork> |
1059 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1060 | </figure> | 1167 | </figure> |
1061 | <t>where:</t> | 1168 | <t>where:</t> |
1062 | <dl> | 1169 | <dl> |
@@ -1121,7 +1228,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1121 | / / | 1228 | / / |
1122 | / / | 1229 | / / |
1123 | ]]></artwork> | 1230 | ]]></artwork> |
1124 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1125 | </figure> | 1231 | </figure> |
1126 | <t>where:</t> | 1232 | <t>where:</t> |
1127 | <dl> | 1233 | <dl> |
@@ -1161,67 +1267,17 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1161 | 32768 divided by the BUCKET_SIZE which is 13-byte (104-bit). | 1267 | 32768 divided by the BUCKET_SIZE which is 13-byte (104-bit). |
1162 | </t> | 1268 | </t> |
1163 | <t> | 1269 | <t> |
1164 | The ID is generated as 64-bit output form a KDF (HMAC-SHA512 as XTR and HMAC-SHA256 as PRF, | 1270 | To get the IDSUM field, all IDs who hit a bucket are added up with a binary XOR operation. |
1165 | the output from SHA-512 is then truncated to 64 bits, salt of the KDF is always set to = 0). | 1271 | See <xref target="ibf_format_id_generation" format="title" /> for details about ID generation. |
1166 | Its important that the elements can be redistributed over the buckets in case the IBF does not | ||
1167 | decode, that's why the ID is salted with a random salt given in the SALT field of this message. | ||
1168 | Salting is done by calculation the a random salt modulo 64 (using only the lowest 6-bits of the salt) | ||
1169 | and do a bitwise right rotation of output of KDF by the 6-bit salts numeric representation. To | ||
1170 | get the IDSUM field all IDs who hit a bucket are added up with a binary XOR operation. | ||
1171 | </t> | 1272 | </t> |
1172 | <t> | 1273 | <t> |
1173 | The HASH is calculated by calculating the CRC32 checksum of the 64-bit ID value | 1274 | The calculation of the HASHSUM field is done accordingly to the calculation of the IDSUM field: |
1174 | which returns a 32-bit value. To get the HASHSUM field all IDs are added | 1275 | all HASHes are added up with a binary XOR operation. |
1175 | up with a binary XOR operation. | 1276 | The HASH value is calculated as described in detail in section <xref target="ibf_format_HASH_calculation" format="title" />. |
1176 | |||
1177 | </t> | 1277 | </t> |
1178 | <t> | 1278 | <t> |
1179 | To decide in which buckets the ID and HASH have to be added up there is the following | 1279 | The algorithm to find the correct bucket in which the ID and the HASH have to be added |
1180 | algorithm used: The first index is simply the HASH modulo the IBF size. The second | 1280 | is described in detail in section <xref target="ibf_format_bucket_identification" format="title" />. |
1181 | index is calculated by creating a new 64-bit value by shifting the 32-bit | ||
1182 | value left and setting the lower 32-bit to the number of indexes already processed. From the | ||
1183 | resulting 64-bit value a CRC32 checksum is created the second index is now the modulo of the | ||
1184 | CRC32 output this is repeated until the predefined amount indexes is generated. | ||
1185 | In the case a index is hit twice, which would mean this bucket could not get pure again, | ||
1186 | the second hit is just skipped and the next iteration is used as. | ||
1187 | |||
1188 | <!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the | ||
1189 | salt_key function in gnunet-service-set_union.c file | ||
1190 | |||
1191 | CG: Eh, you should really read in setu/, not in set/. Alas, this function is the same. | ||
1192 | |||
1193 | The goal of salt_key is to modify a given IBF key based on the salt (so we | ||
1194 | end up with different material depending on the salt). We only use the | ||
1195 | lowest 6 bits of the salt (hopefully enough!): | ||
1196 | |||
1197 | int s = salt % 64; | ||
1198 | uint64_t x = k_in->key_val; // that's the real input: at 64 bit value | ||
1199 | |||
1200 | /* rotate ibf key */ | ||
1201 | x = (x >> s) | (x << (64 - s)); // We simply to a bit rotation by 's' | ||
1202 | k_out->key_val = x; // That's the final output. | ||
1203 | |||
1204 | In some languages, this would simply be: | ||
1205 | result = (input <<< salt); // bit rotation operator | ||
1206 | |||
1207 | @Christian and the ibf_insert_into (why exponentiation? ^=) in the ibf.c | ||
1208 | |||
1209 | CG: ^= is XOR in C (A ^=B; is basically "A := A XOR B"), _not_ exponentiation! | ||
1210 | |||
1211 | The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32. | ||
1212 | |||
1213 | Not just. We take the 64-bit ID value. First, using 'CRC32' to compute | ||
1214 | a 32-byte value. Take that modulo % buckets to get a bucket index. | ||
1215 | Then shift the 32 bits high, or with 'i' (loop!) to set 32 low bits, | ||
1216 | and again CRC32 to compute the next bucket. *IF* this formula returns | ||
1217 | the same bucket twice, skip (so we guarantee hash_num disjoint buckets). | ||
1218 | Note that the code had a bug, pushing a fix now: | ||
1219 | |||
1220 | if (dst[j] == bucket) | ||
1221 | must be | ||
1222 | if (dst[j] == bucket % ibf->size) | ||
1223 | |||
1224 | --> | ||
1225 | </t> | 1281 | </t> |
1226 | 1282 | ||
1227 | <!-- | 1283 | <!-- |
@@ -1306,7 +1362,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1306 | / / | 1362 | / / |
1307 | / / | 1363 | / / |
1308 | ]]></artwork> | 1364 | ]]></artwork> |
1309 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1310 | </figure> | 1365 | </figure> |
1311 | <t>where:</t> | 1366 | <t>where:</t> |
1312 | <dl> | 1367 | <dl> |
@@ -1374,7 +1429,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1374 | / / | 1429 | / / |
1375 | / / | 1430 | / / |
1376 | ]]></artwork> | 1431 | ]]></artwork> |
1377 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1378 | </figure> | 1432 | </figure> |
1379 | <t>where:</t> | 1433 | <t>where:</t> |
1380 | <dl> | 1434 | <dl> |
@@ -1423,7 +1477,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1423 | | IBF KEY | | 1477 | | IBF KEY | |
1424 | +-----+-----+-----+-----+-----+-----+-----+-----+ | 1478 | +-----+-----+-----+-----+-----+-----+-----+-----+ |
1425 | ]]></artwork> | 1479 | ]]></artwork> |
1426 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1427 | </figure> | 1480 | </figure> |
1428 | <t>where:</t> | 1481 | <t>where:</t> |
1429 | <dl> | 1482 | <dl> |
@@ -1470,7 +1523,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1470 | / / | 1523 | / / |
1471 | / / | 1524 | / / |
1472 | ]]></artwork> | 1525 | ]]></artwork> |
1473 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1474 | </figure> | 1526 | </figure> |
1475 | <t>where:</t> | 1527 | <t>where:</t> |
1476 | <dl> | 1528 | <dl> |
@@ -1519,7 +1571,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1519 | | HASH | 1571 | | HASH |
1520 | +-----+-----+-----+-----+ | 1572 | +-----+-----+-----+-----+ |
1521 | ]]></artwork> | 1573 | ]]></artwork> |
1522 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1523 | </figure> | 1574 | </figure> |
1524 | <t>where:</t> | 1575 | <t>where:</t> |
1525 | <dl> | 1576 | <dl> |
@@ -1563,7 +1614,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1563 | | MSG SIZE | MSG TYPE | | 1614 | | MSG SIZE | MSG TYPE | |
1564 | +-----+-----+-----+-----+ | 1615 | +-----+-----+-----+-----+ |
1565 | ]]></artwork> | 1616 | ]]></artwork> |
1566 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1567 | </figure> | 1617 | </figure> |
1568 | <t>where:</t> | 1618 | <t>where:</t> |
1569 | <dl> | 1619 | <dl> |
@@ -1605,7 +1655,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1605 | | MSG SIZE | MSG TYPE | | 1655 | | MSG SIZE | MSG TYPE | |
1606 | +-----+-----+-----+-----+ | 1656 | +-----+-----+-----+-----+ |
1607 | ]]></artwork> | 1657 | ]]></artwork> |
1608 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1609 | </figure> | 1658 | </figure> |
1610 | <t>where:</t> | 1659 | <t>where:</t> |
1611 | <dl> | 1660 | <dl> |
@@ -1652,7 +1701,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1652 | / / | 1701 | / / |
1653 | / / | 1702 | / / |
1654 | ]]></artwork> | 1703 | ]]></artwork> |
1655 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1656 | </figure> | 1704 | </figure> |
1657 | <t>where:</t> | 1705 | <t>where:</t> |
1658 | <dl> | 1706 | <dl> |
@@ -1726,7 +1774,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1726 | / / | 1774 | / / |
1727 | / / | 1775 | / / |
1728 | ]]></artwork> | 1776 | ]]></artwork> |
1729 | <!-- <postamble>which is a very simple example.</postamble>--> | ||
1730 | </figure> | 1777 | </figure> |
1731 | <t>where:</t> | 1778 | <t>where:</t> |
1732 | <dl> | 1779 | <dl> |
@@ -1828,11 +1875,6 @@ Type | Name | References | Description | |||
1828 | 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronization mode have been send is done. | 1875 | 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronization mode have been send is done. |
1829 | 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full synchronization mode. | 1876 | 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full synchronization mode. |
1830 | 1877 | ||
1831 | |||
1832 | |||
1833 | |||
1834 | |||
1835 | |||
1836 | ]]></artwork> | 1878 | ]]></artwork> |
1837 | </figure> | 1879 | </figure> |
1838 | </section> | 1880 | </section> |
@@ -1877,6 +1919,49 @@ Type | Name | References | Description | |||
1877 | </front> | 1919 | </front> |
1878 | </reference> | 1920 | </reference> |
1879 | 1921 | ||
1922 | <reference anchor="CryptographicallySecureVoting" target="https://git.gnunet.org/bibliography.git/plain/docs/ba_dold_voting_24aug2014.pdf"> | ||
1923 | <front> | ||
1924 | <title>Cryptographically Secure, DistributedElectronic Voting</title> | ||
1925 | <author initials="F." surname="Dold" fullname="Florian Dold"> | ||
1926 | <organization>Technische Universität München</organization> | ||
1927 | </author> | ||
1928 | </front> | ||
1929 | </reference> | ||
1930 | |||
1931 | |||
1932 | <reference anchor="GNUNET" target="https://git.gnunet.org/bibliography.git/plain/docs/gns2014wachs.pdf"> | ||
1933 | <front> | ||
1934 | <title>A Censorship-Resistant, Privacy-Enhancing andFully Decentralized Name System</title> | ||
1935 | <author initials="M." surname="Wachs" fullname="Matthias Wachs"> | ||
1936 | <organization>Technische Universität München</organization> | ||
1937 | </author> | ||
1938 | <author initials="M." surname="Schanzenbach" fullname="Martin Schanzenbach"> | ||
1939 | <organization>Technische Universität München</organization> | ||
1940 | </author> | ||
1941 | <author initials="C." surname="Grothoff" fullname="Christian Grothoff"> | ||
1942 | <organization>Technische Universität München</organization> | ||
1943 | </author> | ||
1944 | </front> | ||
1945 | </reference> | ||
1946 | |||
1947 | <reference anchor="Eppstein" target="https://doi.org/10.1145/2018436.2018462"> | ||
1948 | <front> | ||
1949 | <title>What’s the Difference? Efficient Set Reconciliation without Prior Context</title> | ||
1950 | <author initials="D." surname="Eppstein" fullname="David Eppstein"> | ||
1951 | <organization>U.C. Irvine</organization> | ||
1952 | </author> | ||
1953 | <author initials="M." surname="Goodrich" fullname="Michael T. Goodrich"> | ||
1954 | <organization>U.C. Irvine</organization> | ||
1955 | </author> | ||
1956 | <author initials="F." surname="Uyeda" fullname="Frank Uyeda"> | ||
1957 | <organization>U.C. San Diego</organization> | ||
1958 | </author> | ||
1959 | <author initials="G." surname="Varghese" fullname="George Varghese"> | ||
1960 | <organization>U.C. San Diego</organization> | ||
1961 | </author> | ||
1962 | </front> | ||
1963 | </reference> | ||
1964 | |||
1880 | <reference anchor="GNS" target="https://doi.org/10.1007/978-3-319-12280-9_9"> | 1965 | <reference anchor="GNS" target="https://doi.org/10.1007/978-3-319-12280-9_9"> |
1881 | <front> | 1966 | <front> |
1882 | <title>A Censorship-Resistant, Privacy-Enhancing and Fully Decentralized Name System</title> | 1967 | <title>A Censorship-Resistant, Privacy-Enhancing and Fully Decentralized Name System</title> |
@@ -2007,8 +2092,41 @@ Type | Name | References | Description | |||
2007 | </front> | 2092 | </front> |
2008 | </reference>--> | 2093 | </reference>--> |
2009 | </references> | 2094 | </references> |
2010 | <!-- Change Log | 2095 | <section anchor="test_vectors" numbered="true" toc="default"> |
2011 | v00 2017-07-23 MS Initial version | 2096 | <name>Test Vectors</name> |
2012 | --> | 2097 | <section anchor="test_vectors_map_function" numbered="true" toc="default"> |
2098 | <name>Map Function</name> | ||
2099 | <t> | ||
2100 | INPUTS: | ||
2101 | </t> | ||
2102 | <t> | ||
2103 | key: 0xFFFFFFFFFFFFFFFF (64-bit)<br/> | ||
2104 | number_of_buckets_per_element: 3<br/> | ||
2105 | ibf_size: 300 | ||
2106 | </t> | ||
2107 | <t> | ||
2108 | OUTPUT: | ||
2109 | </t> | ||
2110 | <t> | ||
2111 | ["222","32","10"] | ||
2112 | </t> | ||
2113 | </section> | ||
2114 | <section anchor="test_vectors_id_function" numbered="true" toc="default"> | ||
2115 | <name>ID Calculation Function</name> | ||
2116 | <t> | ||
2117 | INPUTS: | ||
2118 | </t> | ||
2119 | <t> | ||
2120 | element: 0xadadadadadadadad | ||
2121 | ibf_salt 0x3F (6-bit) | ||
2122 | </t> | ||
2123 | <t> | ||
2124 | OUTPUT: | ||
2125 | </t> | ||
2126 | <t> | ||
2127 | 0xFFFFFFFFFFFFFFFF | ||
2128 | </t> | ||
2129 | </section> | ||
2130 | </section> | ||
2013 | </back> | 2131 | </back> |
2014 | </rfc> | 2132 | </rfc> |