commit aab0ce19452466c8290c700f1f6fddefa1c12ec2
parent f5d269f37c7b1c3b65921b3f02e1b1713a227004
Author: Christian Grothoff <christian@grothoff.org>
Date: Sat, 12 Jun 2021 16:09:21 +0200
generate files do not belong into git
Diffstat:
1 file changed, 0 insertions(+), 2856 deletions(-)
diff --git a/draft-summermatter-set-union.txt b/draft-summermatter-set-union.txt
@@ -1,2856 +0,0 @@
-
-
-
-
-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]
