From 90c4bf1f53a952919f814d1d1b6307db0e357611 Mon Sep 17 00:00:00 2001 From: Elias Summermatter Date: Sat, 23 Jan 2021 13:35:51 +0100 Subject: Fixed some stuff --- draft-summermatter-set-union.xml | 324 ++++++++++++++++++++++++++------------- 1 file 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 @@ Our primary envisioned application domain is the distribution of revocation messages in the GNU Name - System (GNS) . In GNS, + System (GNS) . 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,8 +96,8 @@ 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 which + secure multiparty computations are 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 @@ -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. + implementation of a proposal by Eppstein. @@ -382,9 +382,9 @@ hashSum | HASHSUM | HASHSUM | HASHSUM | HASHSUM | H.. +-------------+-------------+-------------+-------------+ count | 0 | 0 | 0 | 0 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0000 | 0000 | 0000 | + idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0000 | 0000 | 0000 | +hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | +-------------+-------------+-------------+-------------+ ]]> @@ -395,9 +395,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | +-------------+-------------+-------------+-------------+ count | 0 | 1 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0x0102 | 0000 | 0x0102 | + idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -408,9 +408,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 1 | 2 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | + idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0101 | 0x4343 | 0000 | 0x4242 | +hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -433,9 +433,9 @@ hashSum | 0101 | 0x4343 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 1 | 2 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | + idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | +hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -446,9 +446,9 @@ hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 0 | 1 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0x0102 | 0000 | 0x0102 | + idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -530,9 +530,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 1 | 2 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | + idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | +hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -546,9 +546,9 @@ hashSum | 0x0101 | 0x4343 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 0 | 1 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0x0102 | 0000 | 0x0102 | + idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -563,9 +563,9 @@ hashSum | 0000 | 0x4242 | 0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 0 | 0 | 0 | 0 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0000 | 0000 | 0000 | + idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0000 | 0000 | 0000 | +hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 | +-------------+-------------+-------------+-------------+ ]]> @@ -603,9 +603,9 @@ hashSum | 0000 | 0000 | 0000 | 0000 | +-------------+-------------+-------------+-------------+ count | 1 | 2 | 0 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0x0304 | 0x0206 | 0000 | 0x0102 | + idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -616,9 +616,9 @@ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 0 | 1 | 1 | 1 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0x0102 | 0x1345 | 0x0102 | + idSum | 0x0000 | 0x0102 | 0x1345 | 0x0102 | +-------------+-------------+-------------+-------------+ -hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 | +hashSum | 0x0000 | 0x4242 | 0x5050 | 0x4242 | +-------------+-------------+-------------+-------------+ ]]> @@ -629,9 +629,9 @@ hashSum | 0000 | 0x4242 | 0x5050 | 0x4242 | +-------------+-------------+-------------+-------------+ count | 1 | 1 | -1 | 0 | +-------------+-------------+-------------+-------------+ - idSum | 0000 | 0x0304 | 0x1345 | 0000 | + idSum | 0x0304 | 0x0304 | 0x1345 | 0x0000 | +-------------+-------------+-------------+-------------+ -hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | +hashSum | 0x0101 | 0x0101 | 0x5050 | 0x0000 | +-------------+-------------+-------------+-------------+ ]]> @@ -641,7 +641,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | removed by the set difference operation (bit-4). -
@@ -691,8 +690,117 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | also again a reasonable size for many CPU architectures. +
+ ID Calculation + + The ID is generated as 64-bit output from a HKDF construction + with HMAC-SHA512 as XTR and HMAC-SHA256 as PRF and salt is set to the unsigned 64-bit equivalent of 0. + The output is then truncated to 64-bit. + Its important that the elements can be redistributed over the buckets in case the IBF does not + decode, that's why the ID is salted with a random salt given in the SALT field of this message. + Salting is done by calculation the a random salt modulo 64 (using only the lowest 6-bits of the salt) + and do a bitwise right rotation of output of KDF by the 6-bit salts numeric representation. + + + Representation in pseudocode: + +
+ > s) | (k << (64 - k)) + return key + + +# INPUTS: +# element: Element to calculated id from. +# salt: Salt of the IBF +# OUTPUT: +# value: the ID of the element + +FUNCTION id_calculation (element,ibf_salt): + salt = 0 + XTR=HMAC-SHA256 + PRF=HMAC-SHA256 + key = HKDF(XTR, PRF, salt, element) + key = key modulo 2^64 // Truncate + return salt_key(key,ibf_salt) + + + ]]> +
+
+
+ Mapping Function + + The mapping function M as described above in the figure + decides in which buckets the ID and HASH have to be binary XORed to. In practice + there the following algorithm is used: + + + The first index is simply the HASH modulo the IBF size. The second + index is calculated by creating a new 64-bit value by shifting the 32-bit + value left and setting the lower 32-bit to the number of indexes already processed. From the + resulting 64-bit value a CRC32 checksum is created the second index is now the modulo of the + CRC32 output this is repeated until the predefined amount indexes is generated. + In the case a index is hit twice, which would mean this bucket could not get pure again, + the second hit is just skipped and the next iteration is used as. + +
+ +
+
+
+ HASH calculation + + The HASH is calculated by calculating the CRC32 checksum of the 64-bit ID value + which returns a 32-bit value. +
+
Strata Estimator @@ -1056,7 +1164,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1121,7 +1228,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1161,67 +1267,17 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | 32768 divided by the BUCKET_SIZE which is 13-byte (104-bit). - The ID is generated as 64-bit output form a KDF (HMAC-SHA512 as XTR and HMAC-SHA256 as PRF, - the output from SHA-512 is then truncated to 64 bits, salt of the KDF is always set to = 0). - Its important that the elements can be redistributed over the buckets in case the IBF does not - decode, that's why the ID is salted with a random salt given in the SALT field of this message. - Salting is done by calculation the a random salt modulo 64 (using only the lowest 6-bits of the salt) - and do a bitwise right rotation of output of KDF by the 6-bit salts numeric representation. To - get the IDSUM field all IDs who hit a bucket are added up with a binary XOR operation. + To get the IDSUM field, all IDs who hit a bucket are added up with a binary XOR operation. + See for details about ID generation. - The HASH is calculated by calculating the CRC32 checksum of the 64-bit ID value - which returns a 32-bit value. To get the HASHSUM field all IDs are added - up with a binary XOR operation. - + The calculation of the HASHSUM field is done accordingly to the calculation of the IDSUM field: + all HASHes are added up with a binary XOR operation. + The HASH value is calculated as described in detail in section . - To decide in which buckets the ID and HASH have to be added up there is the following - algorithm used: The first index is simply the HASH modulo the IBF size. The second - index is calculated by creating a new 64-bit value by shifting the 32-bit - value left and setting the lower 32-bit to the number of indexes already processed. From the - resulting 64-bit value a CRC32 checksum is created the second index is now the modulo of the - CRC32 output this is repeated until the predefined amount indexes is generated. - In the case a index is hit twice, which would mean this bucket could not get pure again, - the second hit is just skipped and the next iteration is used as. - - + The algorithm to find the correct bucket in which the ID and the HASH have to be added + is described in detail in section . where:
@@ -1374,7 +1429,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1423,7 +1477,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | IBF KEY | +-----+-----+-----+-----+-----+-----+-----+-----+ ]]> - where:
@@ -1470,7 +1523,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1519,7 +1571,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | HASH +-----+-----+-----+-----+ ]]> - where:
@@ -1563,7 +1614,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | MSG SIZE | MSG TYPE | +-----+-----+-----+-----+ ]]> - where:
@@ -1605,7 +1655,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | MSG SIZE | MSG TYPE | +-----+-----+-----+-----+ ]]> - where:
@@ -1652,7 +1701,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1726,7 +1774,6 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | / / / / ]]> - where:
@@ -1828,11 +1875,6 @@ Type | Name | References | Description 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronization mode have been send is done. 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full synchronization mode. - - - - - ]]>
@@ -1877,6 +1919,49 @@ Type | Name | References | Description + + + Cryptographically Secure, DistributedElectronic Voting + + Technische Universität München + + + + + + + + A Censorship-Resistant, Privacy-Enhancing andFully Decentralized Name System + + Technische Universität München + + + Technische Universität München + + + Technische Universität München + + + + + + + What’s the Difference? Efficient Set Reconciliation without Prior Context + + U.C. Irvine + + + U.C. Irvine + + + U.C. San Diego + + + U.C. San Diego + + + + A Censorship-Resistant, Privacy-Enhancing and Fully Decentralized Name System @@ -2007,8 +2092,41 @@ Type | Name | References | Description --> - +
+ Test Vectors +
+ Map Function + + INPUTS: + + + key: 0xFFFFFFFFFFFFFFFF (64-bit)
+ number_of_buckets_per_element: 3
+ ibf_size: 300 + + + OUTPUT: + + + ["222","32","10"] + +
+
+ ID Calculation Function + + INPUTS: + + + element: 0xadadadadadadadad + ibf_salt 0x3F (6-bit) + + + OUTPUT: + + + 0xFFFFFFFFFFFFFFFF + +
+
-- cgit v1.2.3