[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] 01/02: Added some stuff
|
From: |
gnunet |
|
Subject: |
[lsd0003] 01/02: Added some stuff |
|
Date: |
Wed, 09 Jun 2021 09:09:45 +0200 |
This is an automated email from the git hooks/post-receive script.
elias-summermatter pushed a commit to branch master
in repository lsd0003.
commit dc5c89dbe55665153cd8b4bd3b2cad156d2dffda
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Wed Jun 9 09:06:47 2021 +0200
Added some stuff
---
draft-summermatter-set-union.pdf | Bin 0 -> 489183 bytes
draft-summermatter-set-union.txt | 2856 ++++++++++++++++++++
draft-summermatter-set-union.xml | 5 +-
statemaschine/differential_state_machine | 1 +
statemaschine/differential_state_machine.png | Bin 0 -> 105665 bytes
statemaschine/differential_state_machine.svg | 3 +
...l_state_maschine.png => full_state_machine.png} | Bin
...l_state_maschine.svg => full_state_machine.svg} | 0
...l_state_maschine.xml => full_state_machine.xml} | 0
statemaschine/state_machine_full | 1 +
statemaschine/state_machine_full.png | Bin 0 -> 56892 bytes
statemaschine/state_machine_full.svg | 3 +
12 files changed, 2867 insertions(+), 2 deletions(-)
diff --git a/draft-summermatter-set-union.pdf b/draft-summermatter-set-union.pdf
new file mode 100644
index 0000000..779b351
Binary files /dev/null and b/draft-summermatter-set-union.pdf differ
diff --git a/draft-summermatter-set-union.txt b/draft-summermatter-set-union.txt
new file mode 100644
index 0000000..eba95b8
--- /dev/null
+++ b/draft-summermatter-set-union.txt
@@ -0,0 +1,2856 @@
+
+
+
+
+Independent Stream E. Summermatter
+Internet-Draft Seccom GmbH
+Intended status: Informational C. Grothoff
+Expires: 16 September 2021 Berner Fachhochschule
+ 15 March 2021
+
+
+ Byzantine Fault Tolerant Set Reconciliation
+ draft-schanzen-gns-01
+
+Abstract
+
+ This document contains a protocol specification for Byzantine fault-
+ tolerant Set Reconciliation.
+
+Status of This Memo
+
+ This Internet-Draft is submitted in full conformance with the
+ provisions of BCP 78 and BCP 79.
+
+ Internet-Drafts are working documents of the Internet Engineering
+ Task Force (IETF). Note that other groups may also distribute
+ working documents as Internet-Drafts. The list of current Internet-
+ Drafts is at https://datatracker.ietf.org/drafts/current/.
+
+ Internet-Drafts are draft documents valid for a maximum of six months
+ and may be updated, replaced, or obsoleted by other documents at any
+ time. It is inappropriate to use Internet-Drafts as reference
+ material or to cite them other than as "work in progress."
+
+ This Internet-Draft will expire on 16 September 2021.
+
+Copyright Notice
+
+ Copyright (c) 2021 IETF Trust and the persons identified as the
+ document authors. All rights reserved.
+
+ This document is subject to BCP 78 and the IETF Trust's Legal
+ Provisions Relating to IETF Documents (https://trustee.ietf.org/
+ license-info) in effect on the date of publication of this document.
+ Please review these documents carefully, as they describe your rights
+ and restrictions with respect to this document. Code Components
+ extracted from this document must include Simplified BSD License text
+ as described in Section 4.e of the Trust Legal Provisions and are
+ provided without warranty as described in the Simplified BSD License.
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 1]
+
+Internet-Draft Set Union March 2021
+
+
+Table of Contents
+
+ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
+ 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 5
+ 2.1. Bloom Filters . . . . . . . . . . . . . . . . . . . . . . 5
+ 2.2. Counting Bloom Filter . . . . . . . . . . . . . . . . . . 7
+ 3. Invertible Bloom Filter . . . . . . . . . . . . . . . . . . . 8
+ 3.1. Structure . . . . . . . . . . . . . . . . . . . . . . . . 8
+ 3.2. Operations . . . . . . . . . . . . . . . . . . . . . . . 9
+ 3.2.1. Insert Element . . . . . . . . . . . . . . . . . . . 9
+ 3.2.2. Remove Element . . . . . . . . . . . . . . . . . . . 10
+ 3.2.3. Decode IBF . . . . . . . . . . . . . . . . . . . . . 11
+ 3.2.4. Set Difference . . . . . . . . . . . . . . . . . . . 13
+ 3.3. Wire format . . . . . . . . . . . . . . . . . . . . . . . 15
+ 3.3.1. ID Calculation . . . . . . . . . . . . . . . . . . . 15
+ 3.3.2. Mapping Function . . . . . . . . . . . . . . . . . . 16
+ 3.3.3. HASH calculation . . . . . . . . . . . . . . . . . . 17
+ 4. Strata Estimator . . . . . . . . . . . . . . . . . . . . . . 18
+ 4.1. Description . . . . . . . . . . . . . . . . . . . . . . . 18
+ 5. Mode of operation . . . . . . . . . . . . . . . . . . . . . . 18
+ 5.1. Full Synchronisation Mode . . . . . . . . . . . . . . . . 19
+ 5.2. Delta Synchronisation Mode . . . . . . . . . . . . . . . 20
+ 5.3. Combined Mode . . . . . . . . . . . . . . . . . . . . . . 23
+ 6. Messages . . . . . . . . . . . . . . . . . . . . . . . . . . 23
+ 6.1. Operation Request . . . . . . . . . . . . . . . . . . . . 23
+ 6.1.1. Description . . . . . . . . . . . . . . . . . . . . . 24
+ 6.1.2. Structure . . . . . . . . . . . . . . . . . . . . . . 24
+ 6.2. IBF . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
+ 6.2.1. Description . . . . . . . . . . . . . . . . . . . . . 24
+ 6.2.2. Structure . . . . . . . . . . . . . . . . . . . . . . 25
+ 6.3. IBF . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
+ 6.3.1. Description . . . . . . . . . . . . . . . . . . . . . 26
+ 6.4. Elements . . . . . . . . . . . . . . . . . . . . . . . . 26
+ 6.4.1. Description . . . . . . . . . . . . . . . . . . . . . 27
+ 6.4.2. Structure . . . . . . . . . . . . . . . . . . . . . . 27
+ 6.5. Offer . . . . . . . . . . . . . . . . . . . . . . . . . . 28
+ 6.5.1. Description . . . . . . . . . . . . . . . . . . . . . 28
+ 6.5.2. Structure . . . . . . . . . . . . . . . . . . . . . . 28
+ 6.6. Inquiry . . . . . . . . . . . . . . . . . . . . . . . . . 28
+ 6.6.1. Description . . . . . . . . . . . . . . . . . . . . . 28
+ 6.6.2. Structure . . . . . . . . . . . . . . . . . . . . . . 29
+ 6.7. Demand . . . . . . . . . . . . . . . . . . . . . . . . . 29
+ 6.7.1. Description . . . . . . . . . . . . . . . . . . . . . 29
+ 6.7.2. Structure . . . . . . . . . . . . . . . . . . . . . . 29
+ 6.8. Done . . . . . . . . . . . . . . . . . . . . . . . . . . 30
+ 6.8.1. Description . . . . . . . . . . . . . . . . . . . . . 30
+ 6.8.2. Structure . . . . . . . . . . . . . . . . . . . . . . 30
+ 6.9. Full Done . . . . . . . . . . . . . . . . . . . . . . . . 30
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 2]
+
+Internet-Draft Set Union March 2021
+
+
+ 6.9.1. Description . . . . . . . . . . . . . . . . . . . . . 31
+ 6.9.2. Structure . . . . . . . . . . . . . . . . . . . . . . 31
+ 6.10. Request Full . . . . . . . . . . . . . . . . . . . . . . 31
+ 6.10.1. Description . . . . . . . . . . . . . . . . . . . . 31
+ 6.10.2. Structure . . . . . . . . . . . . . . . . . . . . . 32
+ 6.11. Strata Estimator . . . . . . . . . . . . . . . . . . . . 32
+ 6.11.1. Description . . . . . . . . . . . . . . . . . . . . 32
+ 6.11.2. Structure . . . . . . . . . . . . . . . . . . . . . 32
+ 6.12. Strata Estimator Compressed . . . . . . . . . . . . . . . 33
+ 6.12.1. Description . . . . . . . . . . . . . . . . . . . . 33
+ 6.13. Full Element . . . . . . . . . . . . . . . . . . . . . . 33
+ 6.13.1. Description . . . . . . . . . . . . . . . . . . . . 33
+ 6.13.2. Structure . . . . . . . . . . . . . . . . . . . . . 33
+ 7. Performance Considerations . . . . . . . . . . . . . . . . . 34
+ 7.1. Formulas . . . . . . . . . . . . . . . . . . . . . . . . 34
+ 7.1.1. Operation Mode . . . . . . . . . . . . . . . . . . . 34
+ 7.1.2. Full Synchronisation: Decision witch peer sends
+ elements first . . . . . . . . . . . . . . . . . . . 35
+ 7.1.3. IBF Parameters . . . . . . . . . . . . . . . . . . . 36
+ 8. Security Considerations . . . . . . . . . . . . . . . . . . . 36
+ 8.1. Generic functions . . . . . . . . . . . . . . . . . . . . 37
+ 8.1.1. Duplicated or Missing Message detection . . . . . . . 37
+ 8.1.2. Store Remote Peers Element Number . . . . . . . . . . 38
+ 8.2. States . . . . . . . . . . . . . . . . . . . . . . . . . 38
+ 8.2.1. Expecting IBF . . . . . . . . . . . . . . . . . . . . 38
+ 8.2.2. Full Sending . . . . . . . . . . . . . . . . . . . . 42
+ 8.2.3. Expecting IBF Last . . . . . . . . . . . . . . . . . 43
+ 8.2.4. Active Decoding . . . . . . . . . . . . . . . . . . . 43
+ 8.2.5. Finish Closing . . . . . . . . . . . . . . . . . . . 44
+ 8.2.6. Finished . . . . . . . . . . . . . . . . . . . . . . 44
+ 8.2.7. Expect SE . . . . . . . . . . . . . . . . . . . . . . 44
+ 8.2.8. Full Receiving . . . . . . . . . . . . . . . . . . . 45
+ 8.2.9. Passive Decoding . . . . . . . . . . . . . . . . . . 45
+ 8.2.10. Finish Waiting . . . . . . . . . . . . . . . . . . . 46
+ 9. GANA Considerations . . . . . . . . . . . . . . . . . . . . . 46
+ 10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 47
+ 11. Normative References . . . . . . . . . . . . . . . . . . . . 47
+ Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 50
+ A.1. Map Function . . . . . . . . . . . . . . . . . . . . . . 50
+ A.2. ID Calculation Function . . . . . . . . . . . . . . . . . 50
+ Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 50
+
+1. Introduction
+
+ This document describes a Byzantine fault-tolerant set reconciliation
+ protocol used to efficient and securely synchronize two sets of
+ elements between two peers.
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 3]
+
+Internet-Draft Set Union March 2021
+
+
+ This Byzantine fault-tolerant set reconciliation protocol can be used
+ in a variety of applications. Our primary envisioned application
+ domain is the distribution of revocation messages in the GNU Name
+ System (GNS) [GNUNET]. 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 offline or
+ the network might have been partitioned, there is a need to reconcile
+ revocation lists whenever network partitions are healed or peers go
+ online. The GNU Name System uses the protocol described in this
+ specification to efficiently distribute revocation messages whenever
+ network partitions are healed. Another application domain for the
+ protocol described 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
+ [CryptographicallySecureVoting] which use a bulletin board to share
+ the votes and intermediate computational results. We note that for
+ such systems, the set reconciliation protocol is merely a component
+ of a multiparty consensus protocol, such as the one described in
+ (FIXME-CITE: DOLD MS Thesis! Which paper is his MS thesis on
+ fdold.eu).
+
+ The protocol described in this report is generic and suitable for a
+ wide range of applicaitons. As a result, the internal structure of
+ the elements in the sets must be defined and verified by the
+ application using the protocol. This document thus does not cover
+ the element structure, except for imposing a limit on the maximum
+ size of an element.
+
+ The protocol faces an inherent trade-off between minimizing the
+ number of network round-trips and the number of bytes sent over the
+ network. Thus, for the protocol to choose the right parameters for a
+ given situation, applications using the protocol must provide a
+ parameter that specifies the cost-ratio of round-trips vs. bandwidth
+ usage. Given this trade-off factor, the protocol will then choose
+ parameters that minimize the total execution cost. In particular,
+ there 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.[Eppstein]
+
+ We say that our set reconciliation protocol is Byzantine fault-
+ tolerant because it provides cryptographic and probabilistic methods
+ to discover if the other peer is dishonest or misbehaving.
+
+ The objective here is to limit resources wasted on malicious actors.
+ Malicious actors could send malformed messages, including malformed
+ set elements, claim to have much larger numbers of valid set elements
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 4]
+
+Internet-Draft Set Union March 2021
+
+
+ than the actually hold, or request the retransmission of elements
+ that they have already received in previous interactions. Bounding
+ resources consumed by malicous actors is important to ensure that
+ higher-level protocols can use set reconciliation and still meet
+ their resource targets. This can be particularly critical in multi-
+ round synchronous consensus protocols where peers that cannot answer
+ in a timely fashion would have to be treated as failed or malicious.
+
+ To defend against some of these attacks, applications need to
+ remember the number of elements previously shared with a peer, and
+ offer a means to check that elements are well-formed. Applications
+ may also be able to provide an upper bound on the total number of
+ valid elements that may exist. For example, in E-voting, the number
+ of eligible voters could be used to provide such an upper bound.
+
+ This document defines the normative wire format of resource records,
+ resolution processes, cryptographic routines and security
+ considerations for use by implementors. SETU requires a
+ bidirectional secure communication channel between the two parties.
+ Specification of the communication channel is out of scope of this
+ document.
+
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
+ document are to be interpreted as described in[RFC2119].
+
+2. Background
+
+2.1. Bloom Filters
+
+ A Bloom filter (BF) is a space-efficient datastructure to test if am
+ element is part of a set of elements. Elements are identified by an
+ element ID. Since a BF is a probabilistic datastructure, it is
+ possible to have false-positives: when asked if an element is in the
+ set, the answer from a BF is either "no" or "maybe".
+
+ A BF consists of L buckets. Every bucket is a binary value that can
+ be either 0 or 1. All buckets are initialized to 0. A mapping
+ function M is used to map each the ID of each element from the set to
+ a subset of k buckets. M is non-injective and can thus map the same
+ element multiple times to the same bucket. The type of the mapping
+ function can thus be described by the following mathematical
+ notation:
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 5]
+
+Internet-Draft Set Union March 2021
+
+
+ ------------------------------------
+ # M: E->B^k
+ ------------------------------------
+ # L = Number of buckets
+ # B = 0,1,2,3,4,...L-1 (the buckets)
+ # k = Number of buckets per element
+ # E = Set of elements
+ ------------------------------------
+ Example: L=256, k=3
+ M('element-data') = {4,6,255}
+
+
+ Figure 1
+
+ A typical mapping function is constructed by hashing the element, for
+ example using the well-known Section 2 of HKDF construction
+ [RFC5869].
+
+ To add an element to the BF, the corresponding buckets under the map
+ M are set to 1. To check if an element may be in the set, one tests
+ if all buckets under the map M are set to 1.
+
+ Further in this document a bitstream outputted by the mapping
+ function is represented by a set of numeric values for example (0101)
+ = (2,4). In the BF the buckets are set to 1 if the corresponding bit
+ in the bitstream is 1. If there is a collision and a bucket is
+ already set to 1, the bucket stays 1.
+
+ In the following example the element M(element) = (1,3) has been
+ added:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 2
+
+ Is easy to see that the M(element) = (0,3) could be in the BF bellow
+ and M(element) = (0,2) can't be in the BF bellow:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ | 1 | 0 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 3
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 6]
+
+Internet-Draft Set Union March 2021
+
+
+ The parameters L and k depend on the set size and must be chosen
+ carefully to ensure that the BF does not return too many false-
+ positives.
+
+ It is not possible to remove an element from the BF because buckets
+ can only be set to 1 or 0. Hence it is impossible to differentiate
+ between buckets containing one or more elements. To remove elements
+ from the BF a Counting Bloom Filter is required.
+
+2.2. Counting Bloom Filter
+
+ A Counting Bloom Filter (CBF) is an extension of the Bloom Filters.
+ In the CBF, buckets are unsigned numbers instead of binary values.
+ This allows the removal of an elements from the CBF.
+
+ Adding an element to the CBF is similar to the adding operation of
+ the BF. However, instead of setting the bucket on hit to 1 the
+ numeric value stored in the bucket is increased by 1. For example if
+ two colliding elements M(element1) = (1,3) and M(element2) = (0,3)
+ are added to the CBF, bucket 0 and 1 are set to 1 and bucket 3 (the
+ colliding bucket) is set to 2:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ | 1 | 1 | 0 | 2 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 4
+
+ The counter stored in the bucket is also called the order of the
+ bucket.
+
+ To remove an element form the CBF the counters of all buckets the
+ element is mapped to are decreased by 1.
+
+ Removing M(element2) = (1,3) from the CBF above:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ | 1 | 0 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 5
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 7]
+
+Internet-Draft Set Union March 2021
+
+
+ In practice, the number of bits available for the counters is usually
+ finite. For example, given a 4-bit counter, a CBF bucket would
+ overflow once 16 elements are mapped to the same bucket. To
+ efficiently handle this case, the maximum value (15 in our example)
+ is considered to represent "infinity". Once the order of a bucket
+ reaches "infinity", it is no longer incremented or decremented.
+
+ The parameters L and k and the number of bits allocated to the
+ counters should depend on the set size. An IBF will degenerate when
+ subjected to insert and remove iterations of different elements, and
+ eventually all buckets will reach "infinity". The speed of the
+ degradation will depend on the choice of L and k in relation to the
+ number of elements stored in the IBF.
+
+3. Invertible Bloom Filter
+
+ An Invertible Bloom Filter (IBF) is a further extension of the
+ Counting Bloom Filter. An IBF extends the Counting Bloom Filter with
+ two more operations: decode and set difference. This two extra
+ operations are useful to efficiently extract small differences
+ between large sets.
+
+3.1. Structure
+
+ An IBF consists of a mapping function M and L buckets that each store
+ a signed counter and an XHASH. An XHASH is the XOR of various hash
+ values. As before, the values used for k, L and the number of bits
+ used for the signed counter and the XHASH depend on the set size and
+ various other trade-offs, including the CPU architecture.
+
+ If the IBF size is to small or the mapping function does not spread
+ out the elements uniformly, the signed counter can overflow or
+ underflow. As with the CBF, the "maximum" value is thus used to
+ represent "infinite". As there is no need to distinguish between
+ overflow and underflow, the most canonical representation of
+ "infinite" would be the minimum value of the counter in the canonical
+ 2-complement interpretation. For example, given a 4-bit counter a
+ value of -8 would be used to represent "infinity".
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+-------
+ count | COUNTER | COUNTER | COUNTER | COUNTER | C...
+ +-------------+-------------+-------------+-------------+------
+ idSum | IDSUM | IDSUM | IDSUM | IDSUM | I...
+ +-------------+-------------+-------------+-------------+------
+ hashSum | HASHSUM | HASHSUM | HASHSUM | HASHSUM | H..
+ +-------------+-------------+-------------+-------------+-------
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 8]
+
+Internet-Draft Set Union March 2021
+
+
+ Figure 6
+
+3.2. Operations
+
+ When an IBF is created, all counters and IDSUM and HASHSUM values of
+ all buckets are initialized to zero.
+
+3.2.1. Insert Element
+
+ To add an element to a IBF, the element is mapped to a subset of k
+ buckets using the mapping function M as described in the Bloom
+ Filters section introducing BFs. For the buckets selected by the
+ mapping function, the counter is increased by one and the IDSUM field
+ is set to the XOR of the element ID and the previously stored IDSUM.
+ Furthermore, the HASHSUM is set to the XOR of the hash of the element
+ ID and the previously stored HASHSUM.
+
+ In the following example, the insert operation is illustrated using
+ an element with the ID 0x0102 and a hash of 0x4242, and a second
+ element with the ID 0x0304 and a hash of 0x0101.
+
+ Empty IBF:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 7
+
+ Insert first element: [0101] with ID 0x0102 and hash 0x4242:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 8
+
+ Insert second element: [1100] with ID 0x0304 and hash 0101:
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 9]
+
+Internet-Draft Set Union March 2021
+
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 9
+
+3.2.2. Remove Element
+
+ To remove an element from the IBF the element is again mapped to a
+ subset of the buckets using M. Then all the counters of the buckets
+ selected by M are reduced by one, the IDSUM is replaced by the XOR of
+ the old IDSUM and the ID of the element being removed, and the
+ HASHSUM is similarly replaced with the XOR of the old HASHSUM and the
+ hash of the ID.
+
+ In the following example the remove operation for the element [1100]
+ with the hash 0x0101 is demonstrated.
+
+ IBF with encoded elements:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 10
+
+ Remove element [1100] with ID 0x0304 and hash 0x0101 from the IBF:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 11
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 10]
+
+Internet-Draft Set Union March 2021
+
+
+ Note that it is possible to "remove" elements from an IBF that were
+ never present in the IBF in the first place. A negative counter
+ value is thus indicative of elements that were removed without having
+ been added. Note that an IBF bucket counter of zero no longer
+ warrants that an element mapped to that bucket is not present in the
+ set: a bucket with a counter of zero can be the result of one element
+ being added and a different element (mapped to the same bucket) being
+ removed. To check that an element is not present requires a counter
+ of zero and an IDSUM and HASHSUM of zero --- and some assurance that
+ there was no collision due to the limited number of bits in IDSUM and
+ HASHSUM. Thus, IBFs are not suitable to replace BFs or IBFs.
+
+ Buckets in an IBF with a counter of 1 or -1 are crucial for decoding
+ an IBF, as they might represent only a single element, with the IDSUM
+ being the ID of that element. Following Eppstein (CITE), we will
+ call buckets that only represent a single element pure buckets. Note
+ that due to the possibility of multiple insertion and removal
+ operations affecting the same bucket, not all buckets with a counter
+ of 1 or -1 are actually pure buckets. Sometimes a counter can be 1
+ or -1 because N elements mapped to that bucket were added while N-1
+ or N+1 different elements also mapped to that bucket were removed.
+
+3.2.3. Decode IBF
+
+ Decoding an IBF yields the HASH of an element from the IBF, or
+ failure.
+
+ A decode operation requires a pure bucket, that is a bucket to which
+ M only mapped a single element, to succeed. Thus, if there is no
+ bucket with a counter of 1 or -1, decoding fails. However, as a
+ counter of 1 or -1 is not a guarantee that the bucket is pure, there
+ is also a chance that the decoder returns an IDSUM value that is
+ actually the XOR of several IDSUMs. This is primarily detected by
+ checking that the HASHSUM is the hash of the IDSUM. Only if the
+ HASHSUM also matches, the bucket could be pure. Additionally, one
+ should check that the IDSUM value actually would be mapped by M to
+ the respective bucket. If not, there was a hash collision.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 11]
+
+Internet-Draft Set Union March 2021
+
+
+ The very rare case that after all these checks a bucket is still
+ falsely identified as pure must be detected (say by determining that
+ extracted element IDs do not match any actual elements), and
+ addressed at a higher level in the protocol. As these failures are
+ probabilistic and depend on element IDs and the IBF construction,
+ they can typically be avoided by retrying with different parameters,
+ such as a different way to assign element IDs to elements, using a
+ larger value for L, or a different mapping function M. A more common
+ scenario (especially if L was too small) is that IBF decoding fails
+ because there is no pure bucket. In this case, the higher-level
+ protocol also should retry using different parameters.
+
+ Suppose the IBF contains a pure bucket. In this case, the IDSUM in
+ the bucket identifies a single element. Furthermore, it is then
+ possible to remove that element from the IBF (by inserting it if the
+ counter was negative, and by removing it if the counter was
+ positive). This is likely to cause other buckets to become pure,
+ allowing further elements to be decoded. Eventually, decoding should
+ succeed with all counters and IDSUM and HASHSUM values reaching zero.
+ However, it is also possible that an IBF only partly decodes and then
+ decoding fails after yielding some elements.
+
+ In the following example the successful decoding of an IBF containing
+ the two elements previously added in our running example.
+
+ IBF with the two encoded elements:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 12
+
+ In the IBF are two pure buckets to decode (bit-1 and bit-4) we choose
+ to start with decoding bucket 1, we decode the element with the hash
+ 1010 and we see that there is a new pure bucket created (bit-2)
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 12]
+
+Internet-Draft Set Union March 2021
+
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0102 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 13
+
+ In the IBF only pure buckets are left, we choose to continue decoding
+ bucket 2 and decode element with the hash 0x4242. Now the IBF is
+ empty (all buckets have count 0) that means the IBF has successfully
+ decoded.
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x0000 | 0x0000 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 14
+
+3.2.4. Set Difference
+
+ Given addition and removal as defined above, it is possible to define
+ an operation on IBFs that computes an IBF representing the set
+ difference. Suppose IBF1 represents set A, and IBF2 represents set
+ B. Then this set difference operation will compute IBF3 which
+ represents the set A - B --- without needing elements from set A or
+ B. To calculate the IBF representing this set difference, both IBFs
+ must have the same length L, the same number of buckets per element k
+ and use the same map M. Given this, one can compute the IBF
+ representing the set difference by taking the XOR of the IDSUM and
+ HASHSUM values of the respective buckets and subtracting the
+ respective counters. Care should be taken to handle overflows and
+ underflows by setting the counter to "infinity" as necessary. The
+ result is a new IBF with the same number of buckets representing the
+ set difference.
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 13]
+
+Internet-Draft Set Union March 2021
+
+
+ This new IBF can be decoded as described in section 3.2.3. The new
+ IBF can have two types of pure buckets with counter set to 1 or -1.
+ If the counter is set to 1 the element is missing in the secondary
+ set, and if the counter is set to -1 the element is missing in the
+ primary set.
+
+ To demonstrate the set difference operation we compare IBF-A with
+ IBF-B and generate as described IBF-AB
+
+ IBF-A containing elements with hashes 0x0101 and 0x4242:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0304 | 0x0206 | 0x0000 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0101 | 0x4343 | 0x0000 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 15
+
+ IBF-B containing elements with hashes 0x4242 and 0x5050
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 1 | 1 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0000 | 0x0102 | 0x1345 | 0x0102 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0000 | 0x4242 | 0x5050 | 0x4242 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 16
+
+ IBF-AB XOR value and subtract count:
+
+ bucket-0 bucket-1 bucket-2 bucket-3
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 1 | -1 | 0 |
+ +-------------+-------------+-------------+-------------+
+ idSum | 0x0304 | 0x0304 | 0x1345 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+ hashSum | 0x0101 | 0x0101 | 0x5050 | 0x0000 |
+ +-------------+-------------+-------------+-------------+
+
+ Figure 17
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 14]
+
+Internet-Draft Set Union March 2021
+
+
+ After calculating and decoding the IBF-AB its clear that in IBF-A the
+ element with the hash 0x5050 is missing (-1 in bit-3) while in IBF-B
+ the element with the hash 0101 is missing (1 in bit-1 and bit-2).
+ The element with hash 0x4242 is present in IBF-A and IBF-B and is
+ removed by the set difference operation (bit-4).
+
+3.3. Wire format
+
+ To facilitate a reasonably CPU-efficient implementation, this
+ specification requires the IBF counter to always use 8 bits. Fewer
+ bits would result in a paritcularly inefficient implementation, while
+ more bits are rarely useful as sets with so many elements should
+ likely be represented using a larger number of buckets. This means
+ the counter of this design can reach a minimum of -127 and a maximum
+ of 127 before the counter reaches "infinity" (-128).
+
+ For the "IDSUM", we always use a 64-bit representation. The IDSUM
+ value must have sufficient entropy for the mapping function M to
+ yield reasonably random buckets even for very large values of L.
+ With a 32 bit value the chance that multiple elements may be mapped
+ to the same ID would be quite high, even for moderately large sets.
+ Using more than 64 bits would at best make sense for very large sets,
+ but then it is likely always better to simply afford additional round
+ trips to handle the occasional collision. 64 bits are also a
+ reasonable size for many CPU architectures.
+
+ For the "HASHSUM", we always use a 32-bit representation. Here, it
+ is mostly important to avoid collisions, where different elements are
+ mapped to the same hash. However, we note that by design only a few
+ elements (certainly less than 127) should ever be mapped to the same
+ bucket, so a small number of bits should suffice. Furthermore, our
+ protocol is designed to handle occasional collisions, so while with
+ 32-bits there remains a chance of accidental collisions, at 32 bit
+ the chance is generally believed to be sufficiently small enough for
+ the protocol to handle those cases efficiently for a wide range of
+ use-cases. Smaller hash values would safe bandwidth, but also
+ drastically increase the chance of collisions. 32 bits are also again
+ a reasonable size for many CPU architectures.
+
+3.3.1. ID Calculation
+
+ The ID is generated as 64-bit output from a Section 2 of HKDF
+ construction [RFC5869] 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
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 15]
+
+Internet-Draft Set Union March 2021
+
+
+ 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:
+
+ # INPUTS:
+ # key: Pre calculated and truncated key from id_calculation function
+ # ibf_salt: Salt of the IBF
+ # OUTPUT:
+ # value: salted key
+ FUNCTION salt_key(key,ibf_salt):
+ s = ibf_salt % 64;
+ k = key
+
+ /* rotate ibf key */
+ k = (k >> 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)
+
+
+
+ Figure 18
+
+3.3.2. Mapping Function
+
+ The mapping function M as described above in the figure Figure 1
+ 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
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 16]
+
+Internet-Draft Set Union March 2021
+
+
+ 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.
+
+ # INPUTS:
+ # key: Is the ID of the element calculated in the id_calculation function
above.
+ # number_of_buckets_per_element: Pre-defined count of buckets elements are
inserted into
+ # ibf_size: the size of the ibf (count of buckets)
+ # OUTPUT:
+ # dst: Array with bucket IDs to insert ID and HASH
+
+ FUNCTION get_bucket_id (key, number_of_buckets_per_element, ibf_size)
+ bucket = CRC32(key)
+
+ i = 0
+ filled = 0
+ WHILE filled < number_of_buckets_per_element
+
+ element_already_in_bucket = false
+ j = 0
+ WHILE j < filled
+ IF dst[j] == bucket modulo ibf_size THEN
+ element_already_in_bucket = true
+ ENDIF
+ j++
+ ENDWHILE
+
+ IF !element_already_in_bucket THEN
+ dst[filled++] = bucket modulo ibf_size
+ ENDIF
+
+ x = (bucket << 32) | i
+ bucket = CRC32(x)
+
+ i++
+ ENDWHILE
+ return dst
+
+ Figure 19
+
+3.3.3. HASH calculation
+
+ The HASH is calculated by calculating the CRC32 checksum of the
+ 64-bit ID value which returns a 32-bit value.
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 17]
+
+Internet-Draft Set Union March 2021
+
+
+4. Strata Estimator
+
+4.1. Description
+
+ Strata Estimators help estimate the size of the set difference
+ between two set of elements. This is necessary to efficiently
+ determinate the tuning parameters for an IBF, in particular a good
+ value for L.
+
+ Basically a Strata Estimator (SE) is a series of IBFs (with a rather
+ small value of L) in which increasingly large subsets of the full set
+ of elements are added to each IBF. For the n-th IBF, the function
+ selecting the subset of elements should sample to select
+ (probabilistically) 1/(2^n) of all elements. This can be done by
+ counting the number of trailing bits set to "1" in an element ID, and
+ then inserting the element into the IBF identified by that counter.
+ As a result, all elements will be mapped to one IBF, with the n-th
+ IBF being statistically expected to contain 1/(2^n) elements.
+
+ Given two SEs, the set size difference can be estimated by trying to
+ decode all of the IBFs. Given that L was set to a rather small
+ value, IBFs containing large strata will likely fail to decode. For
+ those IBFs that failed to decode, one simply extrapolates the number
+ of elements by scaling the numbers obtained from the other IBFs that
+ did decode. If none of the IBFs of the SE decoded (which given a
+ reasonable choice of L should be highly unlikely), one can retry
+ using a different mapping function M.
+
+5. Mode of operation
+
+ The set union protocol uses IBFs and SEs as primitives. Depending on
+ the state of the two sets there are different strategies or operation
+ modes how to efficiently determinate missing elements between the two
+ sets.
+
+ The simplest mode is the "full" synchronization mode. The idea is
+ that if the difference between the sets of the two peers exceeds a
+ certain threshold, the overhead to determine which elements are
+ different outweighs the overhead of sending the complete set. In
+ this case, the most efficient method can be to just exchange the full
+ sets.
+
+ Link to statemachine diagram
+ (https://git.gnunet.org/lsd0003.git/plain/statemaschine/
+ full_state_maschine.jpg)
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 18]
+
+Internet-Draft Set Union March 2021
+
+
+ The second possibility is that the difference of the sets is small
+ compared to the set size. Here, an efficient "delta" synchronization
+ mode is more efficient. Given these two possibilities, the first
+ steps of the protocol are used to determine which mode should be
+ used.
+
+ Thus, the set synchronization protocol always begins with the
+ following operation mode independent steps.
+
+ The initiating peer begins in the *Initiating Connection* state and
+ the receiving peer in the *Expecting Connection* state. The first
+ step for the initiating peer in the protocol is to send an _Operation
+ Request_ to the receiving peer and transition into the *Expect SE*
+ state. After receiving the _Operation Request_ the receiving peer
+ transitions to the *Expecting IBF* state and answers with the _Strata
+ Estimator_ message. When the initiating peer receives the _Strata
+ Estimator_ message, it decides with some heuristics which operation
+ mode is likely more suitable for the estimated set difference and the
+ application-provided latency-bandwidth tradeoff. The detailed
+ tradeoff between the Full Synchronisation Mode and the Delta
+ Synchronisation Mode is explained in the section Combined Mode.
+
+5.1. Full Synchronisation Mode
+
+ When the initiating peer decides to use the full synchronisation mode
+ and the set of the initiating peer is bigger than the set of the
+ receiving peer, the initiating peer sends a _Request Full_ message,
+ and transitions from *Expecting SE* to the *Full Receiving* state.
+ If the set of the initiating peer is smaller, it sends all set
+ elements to the other peer followed by the _Full Done_ message, and
+ transitions into the *Full Sending* state.
+
+ Link to statemachine diagram
+ (https://git.gnunet.org/lsd0003.git/plain/statemaschine/
+ full_state_maschine.jpg)
+
+ *The behavior of the participants the different state is described
+ below:*
+
+ *Expecting IBF:* If a peer in the *Expecting IBF* state receives a
+ _Request Full_ message from the other peer, the peer sends all the
+ elements of its set followed by a _Full Done_ message to the other
+ peer, and transitions to the *Full Sending* state. If the peer
+ receives an _Full Element_ message, it processes the element and
+ transitions to the *Full Receiving* state.
+
+ *Full Sending:* While a peer is in *Full Sending* state the peer
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 19]
+
+Internet-Draft Set Union March 2021
+
+
+ expects to continuously receive elements from the other peer. As
+ soon as a the _Full Done_ message is received, the peer
+ transitions into the *Finished* state.
+
+ *Full Receiving (In code: Expecting IBF):* While a peer is in the
+ *Full Receiving* state, it expects to continuously receive
+ elements from the other peer. As soon as a the _Full Done_
+ message is received, it sends the remaining elements (those it did
+ not receive) from its set to the other peer, followed by a _Full
+ Done_. After sending the last message, the peer transitions into
+ the *Finished* state.
+
+5.2. Delta Synchronisation Mode
+
+ When the initiating peer in the *Expected SE* state decides to use
+ the delta synchronisation mode, it sends a _IBF_ to the receiving
+ peer and transitions into the *Passive Decoding* state.
+
+ The receiving peer in the *Expecting IBF* state receives the _IBF_
+ message from the initiating peer and transitions into the *Expecting
+ IBF Last* state when there are multiple _IBF_ messages to sent, when
+ there is just a single _IBF_ message the reviving peer transitions
+ directly to the *Active Decoding* state.
+
+ The peer that is in the *Active Decoding*, *Finish Closing* or in the
+ *Expecting IBF Last* state is called the active peer and the peer
+ that is in either the *Passive Decoding* or the *Finish Waiting*
+ state is called the passive peer.
+
+ Link to statemachine diagram
+ (https://git.gnunet.org/lsd0003.git/plain/statemaschine/
+ full_state_maschine.jpg)
+
+ *The behavior of the participants the different states is described
+ below:*
+
+ *Passive Decoding:* In the *Passive Decoding* state the passive peer
+ reacts to requests from the active peer. The action the passive
+ peer executes depends on the message the passive peer receives in
+ the *Passive Decoding* state from the active peer and is described
+ below on a per message basis.
+
+ _Inquiry_ message: The _Inquiry_ message is received if the
+ active peer requests the SHA-512 hash of one or more elements
+ (by sending the 64 bit element ID) that are missing from the
+ active peer's set. In this case the passive peer answers with
+ _Offer_ messages which contain the SHA-512 hash of the
+ requested element. If the passive peer does not have an
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 20]
+
+Internet-Draft Set Union March 2021
+
+
+ element with a matching element ID, it MUST ignore the inquiry.
+ If multiple elements match the 64 bit element ID, the passive
+ peer MUST send offers for all of the matching elements.
+
+ _Demand_ message: The _Demand_ message is received if the active
+ peer requests a complete element that is missing in the active
+ peers set. If the requested element is valid the passive peer
+ answers with an _Elements_ message which contains the full,
+ application-dependent data of the requested element. If the
+ passive peer receives a demand for a SHA-512 hash for which it
+ has no element, a protocol violation is detected and the
+ protocol MUST be aborted. Implementations MAY strengthen this
+ and forbid demands without previous matching offers.
+
+ _Offer_ message: The _Offer_ message is received if the active
+ peer has decoded an element that is present in the active peers
+ set and may be missing in the set of the passive peer. If the
+ SHA-512 hash of the offer is indeed not a hash of any of the
+ elements from the set of the passive peer, the passive peer
+ MUST answer with a _Demand_ message 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.
+
+ _Elements_ message: When a new element message has been received
+ the peer checks if a corresponding _Demand_ for the element has
+ been sent and the demand is still unsatisfied. If the element
+ has been demanded the peer checks the element for validity,
+ removed it from the list of pending demands and then then saves
+ the element to the the set otherwise the peer rejects the
+ element.
+
+ _IBF_ message: If an _IBF_ message is received, this indicates
+ that decoding of the IBF on the active site has failed and
+ roles should be swapped. The receiving passive peer
+ transitions into the *Expecting IBF Last* state, and waits for
+ more _IBF_ messages or the final _IBF_ message to be received.
+
+ _IBF_ message: If an _IBF_ message is received this indicates
+ that the there is just one IBF slice and a direct state and
+ role transition from *Passive Decoding* to *Active Decoding* is
+ initiated.
+
+ _Done_ message: Receiving the _Done_ message signals the passive
+ peer that all demands of the active peer have been satisfied.
+ Alas, the active peer will continue to process demands from the
+ passive peer. Upon receiving this message, the passive peer
+ transitions into the *Finish Waiting* state.
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 21]
+
+Internet-Draft Set Union March 2021
+
+
+ *Active Decoding:* In the *Active Decoding* state the active peer
+ decodes the IBFs and evaluates the set difference between the
+ active and passive peer. Whenever an element ID is obtained by
+ decoding the IBF, the active peer sends either an offer or an
+ inquiry to the passive peer, depending on which site the decoded
+ element is missing.
+
+ If the IBF decodes a positive (1) pure bucket, the element is
+ missing on the passive peers site. Thus the active peer sends an
+ _Offer_ to the passive peer. A negative (-1) pure bucket
+ indicates that a element is missing in the active peers set, so
+ the active peer sends a _Inquiry_ to the passive peer.
+
+ In case the IBF does not successfully decode anymore, the active
+ peer sends a new IBF to the passive client and changes into
+ *Passive Decoding* state. This initiates a role swap. To reduce
+ overhead and prevent double transmission of offers and elements
+ the new IBF is created on the new complete set after all demands
+ and inquiries have been satisfied.
+
+ As soon as the active peer successfully finished decoding the IBF,
+ the active peer sends a _Done_ message to the passive peer.
+
+ All other actions taken by the active peer depend on the message
+ the active peer receives from the passive peer. The actions are
+ described below on a per message basis:
+
+ _Offer_ message: The _Offer_ message indicates that the passive
+ peer received a _Inquiry_ message from the active peer. If a
+ Inquiry has been sent and the offered element is missing in the
+ active peers set, the active peer sends a _Demand_ message to
+ the passive peer. The send demand need to be added to a list
+ with unsatisfied demands. In the case the received offer is
+ for an element that is already in the set of the peer the offer
+ is ignored.
+
+ _Demand_ message: The _Demand_ message indicates that the passive
+ peer received a _Offer_ from the active peer. The active peer
+ satisfies the demand of the passive peer by sending _Elements_
+ message if a offer request for the element has been sent. In
+ the case the demanded element does not exist in the set there
+ was probably a bucket decoded that was not really pure so
+ potentially all _Offer_ and _Demand_ messages sent after are
+ invalid in this case a role change active -> passive with a new
+ IBF is easiest. If a demand for the same element is received
+ multiple times the demands should be discarded.
+
+ _Elements_ message: A element that is received is marked in the
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 22]
+
+Internet-Draft Set Union March 2021
+
+
+ list of demanded elements as satisfied, validated and saved and
+ not further action is taken. Elements that are not demanded or
+ already known are discarded.
+
+ _Done_ message: Receiving the message _Done_ indicates that all
+ demands of the passive peer have been satisfied. The active
+ peer then changes into the state *Finish Closing* state. If
+ the IBF is not finished decoding and the _Done_ is received the
+ other peer is not in compliance with the protocol and the set
+ reconciliation MUST be aborted.
+
+ *Expecing IBF Last* In the *Expecing IBF Last* state the active peer
+ continuously receives _IBF_ messages from the passive peer. When
+ the last _IBF_ message is received the active peer changes into
+ *Active Decoding* state.
+
+ *Finish Closing* / *Finish Waiting* In this states the peers are
+ waiting for all demands to be satisfied and for the
+ synchronisation to be completed. When all demands are satisfied
+ the peer changes into state *Finished*.
+
+5.3. Combined Mode
+
+ In the combined mode the Full Synchronisation Mode and the Delta
+ Synchronisation Mode are combined to minimize resource consumption.
+
+ The Delta Synchronisation Mode is only efficient on small set
+ differences or if the byte-size of the elements is large. Is the set
+ difference is estimated to be large the Full Synchronisation Mode is
+ more efficient. The exact heuristics and parameters on which the
+ protocol decides which mode should be used are described in the
+ Performance Considerations section of this document.
+
+ There are two main cases when a Full Synchronisation Mode is always
+ used. The first case is when one of the peers announces having an
+ empty set. This is announced by setting the SETSIZE field in the
+ _Strata Estimator_ to 0. The second case is if the application
+ requested full synchronization explicitly. This is useful for
+ testing and should not be used in production.
+
+6. Messages
+
+6.1. Operation Request
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 23]
+
+Internet-Draft Set Union March 2021
+
+
+6.1.1. Description
+
+ This message is the first message of the protocol and it is sent to
+ signal to the receiving peer that the initiating peer wants to
+ initialize a new connection.
+
+ This message is sent in the transition between the *Initiating
+ Connection* state and the *Expect SE* state.
+
+ If a peer receives this message and is willing to run the protocol,
+ it answers by sending back a _Strata Estimator_ message. Otherwise
+ it simply closes the connection.
+
+6.1.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | ELEMENT COUNT |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | APX
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/
+ / /
+ / /
+
+ Figure 20
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_OPERATION_REQUEST as registered in
+ GANA Considerations, in network byte order.
+
+ ELEMENT COUNT is the number of the elements the requesting party has
+ in its set, as a 32-bit unsigned integer in network byte order.
+
+ APX is a SHA-512 hash that identifies the application.
+
+6.2. IBF
+
+6.2.1. Description
+
+ The IBF message contains a slice of the IBF.
+
+ The _IBF_ message is sent at the start of the protocol from the
+ initiating peer in the transaction between *Expect SE* -> *Expecting
+ IBF Last* or when the IBF does not decode and there is a role change
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 24]
+
+Internet-Draft Set Union March 2021
+
+
+ in the transition between *Active Decoding* -> *Expecting IBF Last*.
+ This message is only sent if there are more than one IBF slice to
+ sent, in the case there is just one slice the IBF message is sent.
+
+6.2.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE |ORDER| PAD |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | OFFSET | SALT |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | IBF-SLICE
+ + /
+ / /
+ / /
+
+ Figure 21
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_REQUEST_IBF as registered in GANA
+ Considerations in network byte order.
+
+ ORDER is a 8-bit unsigned integer which signals the order of the
+ IBF. The order of the IBF is defined as the logarithm of the
+ number of buckets of the IBF.
+
+ PAD is 24-bit always set to zero
+
+ OFFSET is a 32-bit unsigned integer which signals the offset to the
+ following ibf slices in the original.
+
+ SALT is a 32-bit unsigned integer that contains the salt which was
+ used to create the IBF.
+
+ IBF-SLICE are variable count of slices in an array. A single slice
+ contains out multiple 64-bit IDSUMS, 32-bit HASHSUMS and 8-bit
+ COUNTERS. In the network order the array of IDSUMS is first,
+ followed by an array of HASHSUMS and ended with an array of
+ COUNTERS. Length of the array is defined by MIN( 2^ORDER -
+ OFFSET, MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is
+ defined as 32768 divided by the BUCKET_SIZE which is 13-byte
+ (104-bit).
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 25]
+
+Internet-Draft Set Union March 2021
+
+
+ To get the IDSUM field, all IDs who hit a bucket are added up with
+ a binary XOR operation. See ID Calculation for details about ID
+ generation.
+
+ 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 HASH calculation.
+
+ The algorithm to find the correct bucket in which the ID and the
+ HASH have to be added is described in detail in section Mapping
+ Function.
+
+ IBF-SLICE
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | IDSUMS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | IDSUMS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASHSUMS | HASHSUMS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | COUNTERS | COUNTERS |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 22
+
+6.3. IBF
+
+6.3.1. Description
+
+ This message indicates to the remote peer that all slices of the
+ bloom filter have been sent. The binary structure is exactly the
+ same as the Structure of the message IBF with a different "MSG TYPE"
+ which is defined in GANA Considerations "SETU_P2P_IBF_LAST".
+
+ Receiving this message initiates the state transmissions *Expecting
+ IBF Last* -> *Active Decoding*, *Expecting IBF* -> *Active Decoding*
+ and *Passive Decoding* -> *Active Decoding*. This message can
+ initiate a peer the roll change from *Active Decoding* to *Passive
+ Decoding*.
+
+6.4. Elements
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 26]
+
+Internet-Draft Set Union March 2021
+
+
+6.4.1. Description
+
+ The Element message contains an element that is synchronized in the
+ Delta Synchronisation Mode and transmits a full element between the
+ peers.
+
+ This message is sent in the state *Active Decoding* and *Passive
+ Decoding* as answer to a _Demand_ message from the remote peer. The
+ Element message can also be received in the *Finish Closing* or
+ *Finish Waiting* state after receiving a _Done_ message from the
+ remote peer, in this case the client changes to the *Finished* state
+ as soon as all demands for elements have been satisfied.
+
+ This message is exclusively sent in the Delta Synchronisation Mode.
+
+6.4.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | E TYPE | PADDING |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | E SIZE | AE TYPE | DATA
+ +-----+-----+-----+-----+ /
+ / /
+ / /
+
+ Figure 23
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_ELEMENTS as registered in GANA
+ Considerations in network byte order.
+
+ E TYPE element type is a 16-bit unsigned integer witch defines the
+ element type for the application.
+
+ PADDING is 16-bit always set to zero
+
+ E SIZE element size is 16-bit unsigned integer that signals the size
+ of the elements data part.
+
+ AE TYPE application specific element type is a 16-bit unsigned
+ integer that is needed to identify the type of element that is in
+ the data field
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 27]
+
+Internet-Draft Set Union March 2021
+
+
+ DATA is a field with variable length that contains the data of the
+ element.
+
+6.5. Offer
+
+6.5.1. Description
+
+ The offer message is an answer to an _Inquiry_ message and transmits
+ the full hash of an element that has been requested by the other
+ peer. This full hash enables the other peer to check if the element
+ is really missing in its set and eventually sends a _Demand_ message
+ for that a element.
+
+ The offer is sent and received only in the *Active Decoding* and in
+ the *Passive Decoding* state.
+
+ This message is exclusively sent in the Delta Synchronisation Mode.
+
+6.5.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 24
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_OFFER as registered in GANA
+ Considerations in network byte order.
+
+ HASH is a SHA 512-bit hash of the element that is requested with a
+ inquiry message.
+
+6.6. Inquiry
+
+6.6.1. Description
+
+ The Inquiry message is exclusively sent by the active peer in *Active
+ Decoding* state to request the full hash of an element that is
+ missing in the active peers set. This is normally answered by the
+ passive peer with _Offer_ message.
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 28]
+
+Internet-Draft Set Union March 2021
+
+
+ This message is exclusively sent in the Delta Synchronisation Mode.
+
+ NOTE: HERE IS AN IMPLEMENTATION BUG UNNECESSARY 32-BIT PADDING!
+
+6.6.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | SALT |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | IBF KEY |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+
+ Figure 25
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_INQUIRY as registered in GANA
+ Considerations in network byte order.
+
+ IBF KEY is a 64-bit unsigned integer that contains the key for which
+ the inquiry is sent.
+
+6.7. Demand
+
+6.7.1. Description
+
+ The demand message is sent in the *Active Decoding* and in the
+ *Passive Decoding* state. It is a answer to a received _Offer_
+ message and is sent if the element described in the _Offer_ message
+ is missing in the peers set. In the normal workflow the answer to
+ the demand message is an _Elements_ message.
+
+ This message is exclusively sent in the Delta Synchronisation Mode.
+
+6.7.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 26
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 29]
+
+Internet-Draft Set Union March 2021
+
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_DEMAND as registered in GANA
+ Considerations in network byte order.
+
+ HASH is a 512-bit Hash of the element that is demanded.
+
+6.8. Done
+
+6.8.1. Description
+
+ The done message is sent when all _Demand_ messages have been
+ successfully satisfied and the set is complete synchronized. A final
+ checksum (XOR SHA-512 hash) over all elements of the set is added to
+ the message to allow the other peer to make sure that the sets are
+ equal.
+
+ This message is exclusively sent in the Delta Synchronisation Mode.
+
+6.8.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 27
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_DONE as registered in GANA
+ Considerations in network byte order.
+
+ HASH is a 512-bit hash of the set to allow a final equality check.
+
+6.9. Full Done
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 30]
+
+Internet-Draft Set Union March 2021
+
+
+6.9.1. Description
+
+ The full done message is sent in the Full Synchronisation Mode to
+ signal that all remaining elements of the set have been sent. The
+ message is received and sent in in the *Full Sending* and in the
+ *Full Receiving* state. When the full done message is received in
+ *Full Sending* state the peer changes directly into *Finished* state.
+ In *Full Receiving* state receiving a full done message initiates the
+ sending of the remaining elements that are missing in the set of the
+ other peer.
+
+6.9.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 28
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_FULL_DONE as registered in GANA
+ Considerations in network byte order.
+
+ HASH is a 512-bit hash of the set to allow a final equality check.
+
+6.10. Request Full
+
+6.10.1. Description
+
+ The request full message is sent by the initiating peer in *Expect
+ SE* state to the receiving peer if the operation mode "Full
+ Synchronisation Mode" is determined as the better Mode of operation
+ and the set size of the initiating peer is smaller than the set size
+ of the receiving peer. The initiating peer changes after sending the
+ request full message into *Full Receiving* state.
+
+ The receiving peer receives the Request Full message in the
+ *Expecting IBF*, afterwards the receiving peer starts sending its
+ complete set in Full Element messages to the initiating peer.
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 31]
+
+Internet-Draft Set Union March 2021
+
+
+6.10.2. Structure
+
+ 0 8 16 24 32
+ +-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE |
+ +-----+-----+-----+-----+
+
+ Figure 29
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_REQUEST_FULL as registered in GANA
+ Considerations in network byte order.
+
+6.11. Strata Estimator
+
+6.11.1. Description
+
+ The strata estimator is sent by the receiving peer at the start of
+ the protocol right after the Operation Request message has been
+ received.
+
+ The strata estimator is used to estimate the difference between the
+ two sets as described in section 4.
+
+ When the initiating peer receives the strata estimator the peer
+ decides which Mode of operation to use for the synchronization.
+ Depending on the size of the set difference and the Mode of operation
+ the initiating peer changes into *Full Sending*, *Full Receiving* or
+ *Passive Decoding* state.
+
+6.11.2. Structure
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | SETSIZE
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ SETSIZE | SE-SLICES
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 30
+
+ where:
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 32]
+
+Internet-Draft Set Union March 2021
+
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_SE as registered in GANA
+ Considerations in network byte order.
+
+ SETSIZE is a 64-bit unsigned integer that is defined by the size of
+ the set the SE is
+
+ SE-SLICES is variable in size and contains the same structure as the
+ IBF-SLICES field in the IBF message.
+
+6.12. Strata Estimator Compressed
+
+6.12.1. Description
+
+ The Strata estimator can be compressed with gzip to improve
+ performance. For details see section Performance Considerations.
+
+ Since the content of the message is the same as the uncompressed
+ Strata Estimator, the details aren't repeated here for details see
+ section 6.11.
+
+6.13. Full Element
+
+6.13.1. Description
+
+ The full element message is the equivalent of the Elements message in
+ the Full Synchronisation Mode. It contains a complete element that
+ is missing in the set of the peer that receives this message.
+
+ The full element message is exclusively sent in the transitions
+ *Expecting IBF* -> *Full Receiving* and *Full Receiving* ->
+ *Finished*. The message is only received in the *Full Sending* and
+ *Full Receiving* state.
+
+ After the last full element messages has been sent the Full Done
+ message is sent to conclude the full synchronisation of the element
+ sending peer.
+
+6.13.2. Structure
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 33]
+
+Internet-Draft Set Union March 2021
+
+
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | E TYPE | PADDING |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | SIZE | AE TYPE | DATA
+ +-----+-----+-----+-----+
+ / /
+ / /
+
+ Figure 31
+
+ where:
+
+ MSG SIZE is 16-bit unsigned integer in network byte order witch
+ describes the message size in bytes and the header is included.
+
+ MSG TYPE the type of SETU_P2P_REQUEST_FULL_ELEMENT as registered in
+ GANA Considerations in network byte order.
+
+ E TYPE element type is a 16-bit unsigned integer witch defines the
+ element type for the application.
+
+ PADDING is 16-bit always set to zero
+
+ E SIZE element size is 16-bit unsigned integer that signals the size
+ of the elements data part.
+
+ AE TYPE application specific element type is a 16-bit unsigned
+ integer that is needed to identify the type of element that is in
+ the data field
+
+ DATA is a field with variable length that contains the data of the
+ element.
+
+7. Performance Considerations
+
+7.1. Formulas
+
+7.1.1. Operation Mode
+
+ The decision which mode of operations is used is described by the
+ following code:
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 34]
+
+Internet-Draft Set Union March 2021
+
+
+ The function takes as input the initial the local setsize, the remote
+ setsize, the by the strata estimator calculated difference, a static
+ boolean that enforces full synchronisation mode of operation and the
+ bandwith/roundtrips tradeoff. As output the function returns "FULL"
+ if the full synchronisation mode should be used and "DIFFERENTIAL" if
+ the differential mode should be used.
+
+ # INPUTS:
+ # initial_local_setsize: The initial local setsize
+ # remote_setsize: The remote setsize
+ # set_diff: the set difference calculated by the strata estimator
+ # force_full: boolean to enforce FULL
+ # ba_rtt_tradeoff: the tradeoff between round trips and bandwidth defined
by the use case
+ # OUTPUTS:
+ # returns: the decision (FULL or DIFFERENTIAL)
+
+ FUNCTION decide_operation_mode(initial_local_setsize, remote_setsize,
set_diff, force_full, ba_rtt_tradeoff)
+ IF set_diff > 200
+ set_diff = set_diff * 3 / 2
+ ENDIF
+ IF force_full || ( set_diff > initial_local_setsize / 4 ) ||
remote_setsize = 0
+ return "FULL"
+ ENDIF
+ return "DIFFERENTIAL"
+
+
+ Figure 32
+
+7.1.2. Full Synchronisation: Decision witch peer sends elements first
+
+ The following function determinate which peer starts sending its full
+ set in full synchronisation mode of operation.
+
+ The function takes as input the initial local setsize (set size of
+ the first iteration) and the remote setsize and returns as output the
+ decision "REMOTE" or "LOCAL" to determinate if the remote or the
+ local peer starts sending the full set.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 35]
+
+Internet-Draft Set Union March 2021
+
+
+ # INPUTS:
+ # initial_local_setsize: The initial local setsize
+ # remote_setsize: The remote setsize
+ # OUTPUTS:
+ # returns: the decision (LOCAL or REMOTE)
+
+ FUNCTION decide_full_sending(initial_local_size, remote_setsize)
+ IF ( initial_local_size <= remote_setsize ) || ( remote_setsize = 0 )
+ return LOCAL
+ ELIF
+ return REMOTE
+
+
+ Figure 33
+
+7.1.3. IBF Parameters
+
+ The following function calculate the required parameter to create an
+ optimal sized IBF. These parameter are the number of buckets and the
+ number of buckets a single element is mapped to.
+
+ The function takes as input the setsize and returns a array with two
+ numbers the total number of buckets and the number of buckets a
+ single element is mapped to.
+
+ FUNCTION (setsize):
+ number_of_bucket_per_element = 4
+ total_number_of_buckets = setsize
+ return [ total_number_of_buckets, number_of_bucket_per_element ]
+
+
+ Figure 34
+
+8. Security Considerations
+
+ The security considerations in this document focus mainly on the
+ security goal of availability, the primary goal of the protocol is
+ prevent an attacker from wasting cpu and network resources of the
+ attacked peer.
+
+ To prevent denial of service attacks its vital to check that peers
+ can only reconcile a set once in a pre defined time span. This is a
+ predefined values and need to be adapted on per use basis. To
+ enhance reliability and to allow failures in the protocol its
+ possible to introduce a threshold for max failed reconciliation ties.
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 36]
+
+Internet-Draft Set Union March 2021
+
+
+ The formal format of all messages needs to be properly validated,
+ this is important to prevent many attacks on the code. The
+ application data should be validated by the application using the
+ protocol not by the implementation of the protocol. In case the
+ format validation fails the set operation MUST be terminated.
+
+ To prevent an attacker from sending a peer into a endless loop
+ between active and passive decoding a limitation for active/passive
+ roll switches in required. This can be implemented by a simple
+ counter which terminates the operation after a predefined count of
+ switches. The count of switches needs to be defined as such that its
+ very undroppable that more switches are required an the malicious
+ intend of the other peer can be assumed.
+
+ Its important to close and purge connections after a given timeout to
+ prevent draining attacks.
+
+8.1. Generic functions
+
+ Some functions are used in most of the messages described in the
+ State section.
+
+8.1.1. Duplicated or Missing Message detection
+
+ Most of the messages received need to be checked that they are not
+ received multiple times this is solved with a global store (message)
+ and the following code
+
+ # Initially creates message store
+ FUNCTION createStore()
+ store = {}
+ return store
+
+ # Returns adds a message to the store
+ FUNCTION addMessageToStore(store, message)
+ key = hash(sha512, message)
+ IF store.get(key) != NULL
+ return FALSE
+ store.set(key) = 1
+ return TRUE
+
+ # Returns the count of message received
+ FUNCTION getNumberOfMessage(store)
+ return store.size()
+
+ Figure 35
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 37]
+
+Internet-Draft Set Union March 2021
+
+
+8.1.2. Store Remote Peers Element Number
+
+ To prevent an other peer from requesting the same set multiple times
+ its important to memorize the number of elements a peer had in
+ previous reconciliation sessions.
+
+ FUNCTION number_elements_last_sync(client_id)
+ IF number_store.get(clientID)
+ return number_store.get(client_id)
+ ENDIF
+ return 0
+
+ FUNCTION saveNumberOfElementsLastSync(client_id, remote_setsize)
+ number_store.update(clientID, remote_setsize)
+
+ Figure 36
+
+8.2. States
+
+ In this section the security considerations for each valid message in
+ all states is described, if any other message is received the peer
+ MUST terminate the operation.
+
+8.2.1. Expecting IBF
+
+ Security considerations for received messages:
+
+ Request Full It needs to be checked that the full synchronisation is
+ plausible according to the formula deciding which operation mode
+ is applicable this is achieved by calculating the upper and lower
+ boundaries of the number of elements in the other peers set. The
+ lower boundary of number of elements can be easily memorized as
+ result from the last synchronisation and the upper boundary can be
+ estimated with prior knowledge of the maximal plausible increase
+ of element since the last reconciliation and the maximal plausible
+ number of elements.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 38]
+
+Internet-Draft Set Union March 2021
+
+
+ # INPUTS:
+ # client_id: The initial local setsize
+ # remote_setsize: The remote setsize
+ # local_setsize: The local setsize
+ # initial_local_size: The initial local setsize
+ # set_diff: the set difference calculated by the strata estimator
+ # OUTPUTS:
+ # returns: the decision
+
+ FUNCTION validate_messages_request_full(client_id, remote_setsize,
local_setsize, initial_local_size, set_diff)
+
+ last_setsize = getNumberOfElementsLastSync(clientId)
+ IF remote_setsize > last_setsize
+ return FALSE
+ ENDIF
+
+ # Update number of elements in store
+ saveNumberOfElementsLastSync(client_id, remote_setsize)
+
+ # Check for max plausible set size as defined on use case basis (can
be infinite)
+ plausible_setsize = getMaxPlausibleSetSize()
+ IF remote_setsize > plausible_setsize
+ return FALSE
+ ENDIF
+
+ # Check for correct operation mode operation_mode function is
described in performance section
+ IF decide_operation_mode(initial_local_size, remote_setsize,
set_diff) != "FULL"
+ return FALSE
+ ENDIF
+
+ # Check that the other peer is honest and we should send our set
+ IF decide_full_sending(local_size, initial_remote_setsize ) !=
"LOCAL"
+ return FALSE
+ ENDIF
+
+ return TRUE
+
+ Figure 37
+
+ IBF Its important do define a threshold to limit the maximal number
+ of IBFs that are expected from the other peer. This maximal
+ plausible size can be calculated with the known inputs: number of
+ elements in my set and the pre defined applications upper limit as
+ described in the performance section. That the other peer chooses
+ the correct mode of operation MUST be checked as described in the
+ section above.
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 39]
+
+Internet-Draft Set Union March 2021
+
+
+ FUNCTION validate_messages_ibf(remote_setsize, local_setsize,
initial_local_size, set_diff, ibf_msg)
+ IF is_undefined(number_buckets_left)
+ number_buckets_left = get_bucket_number(remote_setsize,
local_setsize, initial_local_size, set_diff, ibf_msg)
+ ENDIF
+ number_buckets_left --
+ IF number_buckets_left < 0
+ return FALSE
+ return TRUE
+
+
+ # Security check executed when first ibf message is received
+ FUNCTION get_bucket_number(remote_setsize, local_setsize,
initial_local_size, set_diff, ibf_msg)
+
+ # Check for max plausible set size as defined on use case basis (can
be infinite)
+ max_plausible_setsize = getMaxPlausibleSetSize()
+ IF remote_setsize > max_plausible_setsize
+ return 0
+ ENDIF
+
+ # Check for correct operation mode operation_mode function is
described in performance section
+ IF decide_operation_mode(initial_local_size, remote_setsize,
set_diff) != "DIFFERENTIAL"
+ return 0
+ ENDIF
+
+ ibf_params = calculate_optimal_IBF_params(local_setsize)
+ total_number_of_buckets = ibf_params[0]
+ number_of_bucket_per_element = ibf_params[0]
+ IF ( 2^(ibf.order) != total_number_of_buckets ) ||
+ (ibf.number_of_bucket_per_element !=
number_of_bucket_per_element)
+ return 0
+
+ return total_number_of_buckets
+
+ Figure 38
+
+ Full Element If a full element is received the set of the other peer
+ is smaller than the set of the peer in the *Expecting IBF* state
+ and the set difference is smaller than threshold for full
+ synchronisation as described in the performance section. This can
+ be verified by calculating the plausible upper and lower
+ boundaries of the number of elements in the other peers set as
+ described in the first section.
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 40]
+
+Internet-Draft Set Union March 2021
+
+
+ FUNCTION validate_messages_full_element(client_id, remote_setsize,
local_setsize, initial_local_size, set_diff, message)
+
+ # On first run create store and make initial checks
+ IF is_undefined(store)
+ full_element_msg_store = createStore()
+ IF ! validate_messages_full_element_init(client_id,
remote_setsize, local_setsize, initial_local_size, set_diff)
+ return FALSE
+ ENDIF
+
+ # Prevent duplication of received message
+ IF ! addMessageToStore(full_element_msg_store, message)
+ return FALSE
+ ENDIF
+
+ # Prevent to receive more elements than the remote peer has
+ number_received_messages = getNumberOfMessage(full_element_msg_store)
+ IF ( number_received_messages > remote_setsize )
+ return FALSE
+
+ return TRUE
+
+
+ # INPUTS:
+ # client_id: The initial local setsize
+ # remote_setsize: The remote setsize
+ # local_setsize: The local setsize
+ # initial_local_size: The initial local setsize
+ # set_diff: the set difference calculated by the strata estimator
+ # OUTPUTS:
+ # returns: the decision
+
+ FUNCTION validate_messages_full_element_init(client_id, remote_setsize,
local_setsize, initial_local_size, set_diff)
+
+ last_setsize = getNumberOfElementsLastSync(clientId)
+ IF remote_setsize < last_setsize
+ return FALSE
+ ENDIF
+
+ # Update number of elements in store
+ saveNumberOfElementsLastSync(client_id, remote_setsize)
+
+ # Check for max plausible set size as defined on use case basis (can
be infinite)
+ plausible_setsize = getMaxPlausibleSetSize()
+ IF remote_setsize > plausible_setsize
+ return FALSE
+ ENDIF
+
+ # Check for correct operation mode operation_mode function is
described in performance section
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 41]
+
+Internet-Draft Set Union March 2021
+
+
+ IF decide_operation_mode(initial_local_size, remote_setsize,
set_diff) != "FULL"
+ return FALSE
+ ENDIF
+
+ # Check that the other peer is honest and he should send us his set
+ IF decide_full_sending(local_size, initial_remote_setsize ) !=
"REMOTE"
+ return FALSE
+ ENDIF
+
+ return TRUE
+
+
+ Figure 39
+
+8.2.2. Full Sending
+
+ Security considerations for received messages:
+
+ Full Element When receiving full elements there needs to be checked
+ that every element is a valid element, no element is resized more
+ than once and not more or less elements are received as the other
+ peer has committed to in the beginning of the operation. Detail
+ pseudocode implementation can be found in Expecting IBF
+
+ Full Done When receiving the full done message its important to
+ check that not less elements are received as the other peer has
+ committed to send. The 512-bit hash of the complete reconciled
+ set contained in the full done message is required to ensures that
+ both sets are truly identical. If the sets differ a
+ resynchronisation is required. The count of possible
+ resynchronisation MUST be limited to prevent resource exhaustion
+ attacks.
+
+ FUNCTION validate_messages_full_done(full_done_message,
full_element_msg_store, remote_setsize, local_set)
+
+ # Check that correct number of elements has been received
+ number_received_messages = getNumberOfMessage(full_element_msg_store)
+ IF ( number_received_messages != remote_setsize )
+ return FALSE
+ IF local_set.getFullHash() != full_done_message.fullSetHash
+ return FALSE
+ return TRUE
+
+
+ Figure 40
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 42]
+
+Internet-Draft Set Union March 2021
+
+
+8.2.3. Expecting IBF Last
+
+ Security considerations for received messages:
+
+ IBF When receiving multiple IBFs its important to check that the
+ other peer can only send as many IBFs as expected. The number of
+ expected IBFs can be calculated with the knowledge of the set
+ difference as described in the performance section.
+
+ Use pseudocode of the function "validate_messages_ibf" as
+ described in Expecting IBF section.
+
+8.2.4. Active Decoding
+
+ In the Active Decoding state its important to prevent an attacker
+ from generating and passing unlimited amount of IBF that do not
+ decode or even worse generate an IBF that is constructed to sends the
+ peers in an endless loop. To prevent an endless loop in decoding a
+ loop detection should be implemented the simplest solution would be
+ to prevent decoding of more than a given amount of elements, a more
+ robust solution is to implement a algorithm that detects a loop by
+ analyzing past partially decoded IBFs to detect cycles. This can be
+ archived by saving the hash of all prior partly decoded IBFs hashes
+ in a hashmap and check for every inserted hash if it is already in
+ the hashmap.
+
+ If the IBF decodes more or less elements than are plausible the
+ operation MUST be terminated. The upper and lower threshold for the
+ decoded elements can be calculated with the peers set size and the
+ other peer committed set sizes from the *Expecting IBF* State.
+
+ Security considerations for received messages:
+
+ Offer If an offer for an element that never has been requested by an
+ inquiry or if an offer is received twice the operation MUST be
+ terminated. This requirement can be fulfilled by saving lists
+ that keeps track of the state of all send inquiries and offers.
+ When answering offers these lists MUST be checked.
+
+ (Artwork only available as : No external link available, see
+ draft-schanzen-gns-01.html for artwork.)
+
+ Figure 41
+
+ Elements If an element that never has been requested by a demand or
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 43]
+
+Internet-Draft Set Union March 2021
+
+
+ is received double the operation MUST be terminated. This
+ requirement can be fulfilled by a simple table that keeps track of
+ the state of all send demands. If an invalid element is received
+ the operation has failed and the MUST be terminated.
+
+ Demand For every received demand a offer has to be send in advance.
+ If an demand for an element is received that never has been
+ offered or the offer already has been answered with a demand the
+ operation MUST be terminated. Its required to implement a list
+ which keeps track of the state of all send offers and received
+ demands.
+
+ Done The done message is only received if the IBF has been finished
+ decoding and all offers have been sent. If the done message is
+ received before the decoding of the IBF is finished or all open
+ offers and demands have been answered the operation MUST be
+ terminated. The 512-bit hash of the complete reconciled set
+ contained in the done message is required to ensures that both
+ sets are truly identical. If the sets differ a resynchronisation
+ is required. The count of possible resynchronisation MUST be
+ limited to prevent resource exhaustion attacks.
+
+8.2.5. Finish Closing
+
+ In case not all sent demands or inquiries have ben answered in time a
+ pre defined timeout the operation has failed and MUST be terminated.
+
+ Security considerations for received messages:
+
+ Elements Checked as described in section Active Decoding.
+
+8.2.6. Finished
+
+ In this state the connection is terminated, so no security
+ considerations are needed.
+
+8.2.7. Expect SE
+
+ Security considerations for received messages:
+
+ Strata Estimator In case the Strata Estimator does not decode the
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 44]
+
+Internet-Draft Set Union March 2021
+
+
+ operation MUST be terminated to prevent to get to a unresolvable
+ state. The set difference calculated from the strata estimator
+ needs to be plausible, to ensure this multiple factors need to be
+ considered: The absolute plausible maximum of elements in a set
+ which has to be predefined according to the use case and the
+ maximal plausible element increase since the last successful set
+ reconciliation which should be either predefined or can be
+ calculated with the gaussian distribution function over all passed
+ set reconciliations.
+
+ In case of compressed strata estimators the decompression
+ algorithm has to be protected against decompression memory
+ corruption (memory overflow).
+
+8.2.8. Full Receiving
+
+ Security considerations for received messages:
+
+ Full Element The peer in *Full Receiving* state needs to check that
+ exactly the number of elements is received from the remote peer as
+ he initially committed too. If the remote peer transmits less or
+ more elements the operation MUST be terminated.
+
+ Full Done When the full done message is received from the remote
+ peer all elements that the remote peer has committed to needs to
+ be received otherwise the operation MUST be terminated. After
+ receiving the full done message no future elements should be
+ accepted. The 512-bit hash of the complete reconciled set
+ contained in the full done message is required to ensures that
+ both sets are truly identical. If the sets differ a
+ resynchronisation is required. The count of possible
+ resynchronisation MUST be limited to prevent resource exhaustion
+ attacks.
+
+8.2.9. Passive Decoding
+
+ Security considerations for received messages:
+
+ IBF In case an IBF message is received by the peer a active/passive
+ role switch is initiated by the active decoding remote peer. In
+ this instance the peer should wait for all open offers and demands
+ to be fulfilled to prevent retransmission before switching into
+ active decoding operation mode. A switch into active decoding
+ mode should only be permitted for a predefined number of times as
+ described in the top section of the security section.
+
+ Inquiry A check needs to be in place that prevents receiving a
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 45]
+
+Internet-Draft Set Union March 2021
+
+
+ inquiry for an element multiple times or more inquiries than are
+ plausible. The amount of inquiries that is plausible can be
+ estimated by considering known values as the remote set size, the
+ local set size, the predefined absolute maximum of elements in the
+ set which is defined by real world limitations. To implement this
+ restrictions a list with all received inquiries should be stored
+ and new inquiries should be checked against.
+
+ Demand Same action as described for demand message in section Active
+ Decoding.
+
+ Offer Same action as described for offer message in section Active
+ Decoding.
+
+ Done Same action as described for done message in section Active
+ Decoding.
+
+ Elements Same action as described for element message in section
+ Active Decoding.
+
+8.2.10. Finish Waiting
+
+ In case not all sent demands or inquiries have ben answered in time
+ the operation has failed and MUST be terminated.
+
+ Security considerations for received messages:
+
+ Elements Checked as described in section Active Decoding.
+
+9. GANA Considerations
+
+ GANA is requested to amend the "GNUnet Message Type" registry as
+ follows:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 46]
+
+Internet-Draft Set Union March 2021
+
+
+ Type | Name | References | Description
+
--------+----------------------------+------------+--------------------------
+ 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of
the other peer
+ 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole
element from the other peer, given only the hash code.
+ 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to
send us a list of hashes that match an IBF key.
+ 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer
which hashes match a given IBF key.
+ 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union
operation from a remote peer.
+ 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator
uncompressed
+ 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter
Slice.
+ 566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements.
+ 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter
Last Slice.
+ 568 | SETU_P2P_DONE | [This.I-D] | Set operation is done.
+ 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator
compressed
+ 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full
synchronization mode have been send is done.
+ 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element
in full synchronization mode.
+
+
+ Figure 42
+
+10. Contributors
+
+ The original GNUnet implementation of the Byzantine Fault Tolerant
+ Set Reconciliation protocol has mainly been written by Florian Dold
+ and Christian Grothoff.
+
+11. Normative References
+
+ [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
+ Key Derivation Function (HKDF)", RFC 5869,
+ DOI 10.17487/RFC5869, May 2010,
+ <https://www.rfc-editor.org/info/rfc5869>.
+
+ [RFC1034] Mockapetris, P., "Domain names - concepts and facilities",
+ STD 13, RFC 1034, DOI 10.17487/RFC1034, November 1987,
+ <https://www.rfc-editor.org/info/rfc1034>.
+
+ [RFC1035] Mockapetris, P., "Domain names - implementation and
+ specification", STD 13, RFC 1035, DOI 10.17487/RFC1035,
+ November 1987, <https://www.rfc-editor.org/info/rfc1035>.
+
+ [RFC2782] Gulbrandsen, A., Vixie, P., and L. Esibov, "A DNS RR for
+ specifying the location of services (DNS SRV)", RFC 2782,
+ DOI 10.17487/RFC2782, February 2000,
+ <https://www.rfc-editor.org/info/rfc2782>.
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 47]
+
+Internet-Draft Set Union March 2021
+
+
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", BCP 14, RFC 2119,
+ DOI 10.17487/RFC2119, March 1997,
+ <https://www.rfc-editor.org/info/rfc2119>.
+
+ [RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO
+ 10646", STD 63, RFC 3629, DOI 10.17487/RFC3629, November
+ 2003, <https://www.rfc-editor.org/info/rfc3629>.
+
+ [RFC3686] Housley, R., "Using Advanced Encryption Standard (AES)
+ Counter Mode With IPsec Encapsulating Security Payload
+ (ESP)", RFC 3686, DOI 10.17487/RFC3686, January 2004,
+ <https://www.rfc-editor.org/info/rfc3686>.
+
+ [RFC3826] Blumenthal, U., Maino, F., and K. McCloghrie, "The
+ Advanced Encryption Standard (AES) Cipher Algorithm in the
+ SNMP User-based Security Model", RFC 3826,
+ DOI 10.17487/RFC3826, June 2004,
+ <https://www.rfc-editor.org/info/rfc3826>.
+
+ [RFC3912] Daigle, L., "WHOIS Protocol Specification", RFC 3912,
+ DOI 10.17487/RFC3912, September 2004,
+ <https://www.rfc-editor.org/info/rfc3912>.
+
+ [RFC5890] Klensin, J., "Internationalized Domain Names for
+ Applications (IDNA): Definitions and Document Framework",
+ RFC 5890, DOI 10.17487/RFC5890, August 2010,
+ <https://www.rfc-editor.org/info/rfc5890>.
+
+ [RFC5891] Klensin, J., "Internationalized Domain Names in
+ Applications (IDNA): Protocol", RFC 5891,
+ DOI 10.17487/RFC5891, August 2010,
+ <https://www.rfc-editor.org/info/rfc5891>.
+
+ [RFC6781] Kolkman, O., Mekking, W., and R. Gieben, "DNSSEC
+ Operational Practices, Version 2", RFC 6781,
+ DOI 10.17487/RFC6781, December 2012,
+ <https://www.rfc-editor.org/info/rfc6781>.
+
+ [RFC6895] Eastlake 3rd, D., "Domain Name System (DNS) IANA
+ Considerations", BCP 42, RFC 6895, DOI 10.17487/RFC6895,
+ April 2013, <https://www.rfc-editor.org/info/rfc6895>.
+
+ [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature
+ Algorithm (DSA) and Elliptic Curve Digital Signature
+ Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August
+ 2013, <https://www.rfc-editor.org/info/rfc6979>.
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 48]
+
+Internet-Draft Set Union March 2021
+
+
+ [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
+ for Security", RFC 7748, DOI 10.17487/RFC7748, January
+ 2016, <https://www.rfc-editor.org/info/rfc7748>.
+
+ [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
+ Signature Algorithm (EdDSA)", RFC 8032,
+ DOI 10.17487/RFC8032, January 2017,
+ <https://www.rfc-editor.org/info/rfc8032>.
+
+ [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for
+ Writing an IANA Considerations Section in RFCs", BCP 26,
+ RFC 8126, DOI 10.17487/RFC8126, June 2017,
+ <https://www.rfc-editor.org/info/rfc8126>.
+
+ [GANA] GNUnet e.V., "GNUnet Assigned Numbers Authority (GANA)",
+ April 2020, <https://gana.gnunet.org/>.
+
+ [CryptographicallySecureVoting]
+ Dold, F., "Cryptographically Secure, DistributedElectronic
+ Voting",
+ <https://git.gnunet.org/bibliography.git/plain/docs/
+ ba_dold_voting_24aug2014.pdf>.
+
+ [GNUNET] Wachs, M., Schanzenbach, M., and C. Grothoff, "A
+ Censorship-Resistant, Privacy-Enhancing andFully
+ Decentralized Name System",
+ <https://git.gnunet.org/bibliography.git/plain/docs/
+ gns2014wachs.pdf>.
+
+ [Eppstein] Eppstein, D., Goodrich, M., Uyeda, F., and G. Varghese,
+ "What's the Difference? Efficient Set Reconciliation
+ without Prior Context",
+ <https://doi.org/10.1145/2018436.2018462>.
+
+ [GNS] Wachs, M., Schanzenbach, M., and C. Grothoff, "A
+ Censorship-Resistant, Privacy-Enhancing and Fully
+ Decentralized Name System", 2014,
+ <https://doi.org/10.1007/978-3-319-12280-9_9>.
+
+ [R5N] Evans, N. S. and C. Grothoff, "R5N: Randomized recursive
+ routing for restricted-route networks", 2011,
+ <https://doi.org/10.1109/ICNSS.2011.6060022>.
+
+ [Argon2] Biryukov, A., Dinu, D., Khovratovich, D., and S.
+ Josefsson, "The memory-hard Argon2 password hash and
+ proof-of-work function", March 2020,
+ <https://datatracker.ietf.org/doc/draft-irtf-cfrg-
+ argon2/>.
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 49]
+
+Internet-Draft Set Union March 2021
+
+
+ [MODES] Dworkin, M., "Recommendation for Block Cipher Modes of
+ Operation: Methods and Techniques", December 2001,
+ <https://doi.org/10.6028/NIST.SP.800-38A>.
+
+ [ed25519] Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B.
+ Yang, "High-Speed High-Security Signatures", 2011,
+ <http://link.springer.com/
+ chapter/10.1007/978-3-642-23951-9_9>.
+
+Appendix A. Test Vectors
+
+A.1. Map Function
+
+ INPUTS:
+
+ key: 0xFFFFFFFFFFFFFFFF (64-bit) number_of_buckets_per_element: 3
+ ibf_size: 300
+
+ OUTPUT:
+
+ ["222","32","10"]
+
+A.2. ID Calculation Function
+
+ INPUTS:
+
+ element: 0xadadadadadadadad ibf_salt 0x3F (6-bit)
+
+ OUTPUT:
+
+ 0xFFFFFFFFFFFFFFFF
+
+Authors' Addresses
+
+ Elias Summermatter
+ Seccom GmbH
+ Brunnmattstrasse 44
+ CH-3007 Bern
+ Switzerland
+
+ Email: elias.summermatter@seccom.ch
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 50]
+
+Internet-Draft Set Union March 2021
+
+
+ Christian Grothoff
+ Berner Fachhochschule
+ Hoeheweg 80
+ CH-2501 Biel/Bienne
+ Switzerland
+
+ Email: grothoff@gnunet.org
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Summermatter & Grothoff Expires 16 September 2021 [Page 51]
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index cef2baa..8a55878 100644
--- a/draft-summermatter-set-union.xml
+++ b/draft-summermatter-set-union.xml
@@ -1239,8 +1239,9 @@ FUNCTION get_bucket_id (key,
number_of_buckets_per_element, ibf_size)
<t>
are variable numbers of slices in an array. A
single slice contains multiple 64-bit IDSUMS,
32-bit HASHSUMS and 1-64bit COUNTERS of
variable size. In the network order the array of IDSUMS is first, followed
- by an array of HASHSUMS and ended with an
array of COUNTERS. Length of the array is defined
- by MIN( SIZE - OFFSET,
MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as
+ by an array of HASHSUMS and ended with an
array of COUNTERS (details are described in section
+ <xref
target="performance_counter_variable_size" format="default"/>). Length of the
array is
+ defined by MIN( SIZE - OFFSET,
MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as
32768 divided by the BUCKET_SIZE which is
13-byte (104-bit).
</t>
diff --git a/statemaschine/differential_state_machine
b/statemaschine/differential_state_machine
new file mode 100644
index 0000000..9b4e16d
--- /dev/null
+++ b/statemaschine/differential_state_machine
@@ -0,0 +1 @@
+<mxfile host="app.diagrams.net" modified="2021-06-09T07:04:52.109Z" agent="5.0
(X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.77
Safari/537.36" etag="EjBRg3J6DuL3UCMJqSll" version="14.7.6"
type="device"><diagram id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">7V1bk6O4Ff41rtqkyhRCSILHvs3sJJ1ktno3s/vIGNomsY0H07f59SsuAkvINuCDW06mX9rIILB0zqfv3MQE36xeP6bBZvGPJIyWE8cOXyf4duI4jk0d/i9veStbEMKobJmncVi1NQ0P8feoarSr1qc4jLbSiVmSLLN4IzfOkvU6mmVSW5CmyYt82mOylO+6CeZRq+FhFizbrV/iMFt
[...]
\ No newline at end of file
diff --git a/statemaschine/differential_state_machine.png
b/statemaschine/differential_state_machine.png
new file mode 100644
index 0000000..29f5ee3
Binary files /dev/null and b/statemaschine/differential_state_machine.png differ
diff --git a/statemaschine/differential_state_machine.svg
b/statemaschine/differential_state_machine.svg
new file mode 100644
index 0000000..284ca1d
--- /dev/null
+++ b/statemaschine/differential_state_machine.svg
@@ -0,0 +1,3 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd";>
+<svg xmlns="http://www.w3.org/2000/svg";
xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="974px"
height="781px" viewBox="-0.5 -0.5 974 781" content="<mxfile
host="app.diagrams.net" modified="2021-06-09T07:05:12.668Z"
agent="5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko)
Chrome/91.0.4472.77 Safari/537.36" etag="z64y_82akE6YHg7AOlcM"
version="14.7.6" type="device"><diagram
id="C5RBs43oDa [...]
\ No newline at end of file
diff --git a/statemaschine/full_state_maschine.png
b/statemaschine/full_state_machine.png
similarity index 100%
rename from statemaschine/full_state_maschine.png
rename to statemaschine/full_state_machine.png
diff --git a/statemaschine/full_state_maschine.svg
b/statemaschine/full_state_machine.svg
similarity index 100%
rename from statemaschine/full_state_maschine.svg
rename to statemaschine/full_state_machine.svg
diff --git a/statemaschine/full_state_maschine.xml
b/statemaschine/full_state_machine.xml
similarity index 100%
rename from statemaschine/full_state_maschine.xml
rename to statemaschine/full_state_machine.xml
diff --git a/statemaschine/state_machine_full b/statemaschine/state_machine_full
new file mode 100644
index 0000000..dd6b21a
--- /dev/null
+++ b/statemaschine/state_machine_full
@@ -0,0 +1 @@
+<mxfile host="app.diagrams.net" modified="2021-06-09T06:52:44.377Z" agent="5.0
(X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.77
Safari/537.36" etag="pelenmTsAhDcsqPl0I7k" version="14.7.6"
type="device"><diagram id="C5RBs43oDa-KdzZeNtuy"
name="Page-1">5Vtdc6M2FP01nml3Jow+kIDHfDjbbbftdtM27SMxis0WIy/gJM6vrwAJI4RdAjhLpvuy6CKu4d6jo3MlZYYv10/vE3+z+pkHLJohEDzN8NUMIQQoEv/lll1pgZB6pWWZhIG07Q034TOTRiCt2zBgqdYx4zzKwo1uXPA4ZotMs/lJwh/1bvc80n914y+ZYbhZ+JFpvQ2DbCWtlNj7Gz+
[...]
\ No newline at end of file
diff --git a/statemaschine/state_machine_full.png
b/statemaschine/state_machine_full.png
new file mode 100644
index 0000000..395a21c
Binary files /dev/null and b/statemaschine/state_machine_full.png differ
diff --git a/statemaschine/state_machine_full.svg
b/statemaschine/state_machine_full.svg
new file mode 100644
index 0000000..f3d4b43
--- /dev/null
+++ b/statemaschine/state_machine_full.svg
@@ -0,0 +1,3 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd";>
+<svg xmlns="http://www.w3.org/2000/svg";
xmlns:xlink="http://www.w3.org/1999/xlink"; version="1.1" width="752px"
height="531px" viewBox="-0.5 -0.5 752 531" content="<mxfile
host="app.diagrams.net" modified="2021-06-09T06:55:05.725Z"
agent="5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko)
Chrome/91.0.4472.77 Safari/537.36" etag="Ho4LXeUk9jqtwfKfm4ic"
version="14.7.6" type="device"><diagram
id="C5RBs43oDa [...]
\ No newline at end of file
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.