commit 64eb8f92d160be6384333705d094328f3d0aa702
parent cb349049b411a5a58635b156a94abab26922eb2f
Author: Christian Grothoff <christian@grothoff.org>
Date: Wed, 13 Jan 2021 22:45:33 +0100
fix introduction
Diffstat:
1 file changed, 89 insertions(+), 30 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -72,48 +72,94 @@
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
<t>
- This document describes the Byzantine Fault Tolerant Set Reconciliation used to efficient and securely
- synchronize two sets of elements in a peer-to-peer network. It provides cryptographic and
- probabilistic proceedings to discover dishonest and bad behaving peers.
+ This document describes a Byzantine fault-tolerant set reconciliation protocol used to efficient and securely
+ synchronize two sets of elements between two peers.
</t>
<t>
- The Protocol should prevent bad acting peers from waisting resources by sending wrong formed elements, pretending to have a multiple
- of elements or request more elements than the size of the full set. This is achieved by
- saving the count of already sent elements and plausibility checks on how many elements are possible by some real world
- limiting factor. In E-Voting this is for example the count of people who are permitted to vote.
+ 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) (FIXME-CITE: some paper on GNS...). In GNS,
+ key revocation messages are usually flooded across the
+ peer-to-peer overlay network to all connected peers
+ whenever a key is revoked. However, as peers may be
+ 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 (FIXME-CITE DOLD BS-thesis, etc...) 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!).
</t>
<t>
- Another probabilistic approach to discover bad behaving peers is sampling, in this approach the proving peer needs
- to prove that he is in possession of the elements he claimed to be. This is achieved by the following procedure:
+ 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 elemtn
+ structure, except for imposing a limit on the maximum
+ size of an element.
</t>
<t>
- The verifying peer chooses some
- random salt and sends the salt to the proving peer. The proving peer salts the hash of elements with the given
- salt from the verifying peer. Then the proving peer calculates the new hashes modulo a number depending on the set sized difference and
- sends all the elements where the modulo calculation equals 0 to the verifying peer.
- As soon as the verifying peer receives the elements the verifying peer can verify that all the elements
- are valid and the modulo calculation equals 0 then the verifying peer can be assured with a high probability
- that the peer is honest about his remaining set size and difference.
+ 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. (FIXME-CITE!).
</t>
- <t>
- The Byzantine Fault Tolerant Set Reconciliation can be used in a variety of different fields of application,
- primarily in Bulletin Boards where multipart computation is required.
- Some real world applications are the distributed revocations in the GNS peer-to-peer network
- or it can be used as a central component in distributed E-Voting systems to exchange the votes between peer
- who do not trust each other (Zero-Trust).
+
+ <t>
+ 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.
</t>
<t>
- The internal structure of the elements in the set is handheld by the application using the protocol and is not
- described more in detail than known limitations.
+ 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 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.
</t>
<t>
- The protocol should minimize network round-trips and bytes send over the network at the
- expense of CPU operations. The tradeoff between round-trips and network bytes is specified by
- the application and depends on field of application and the environment.
-
- The protocol uses some heuristics to determinate if sending the full set of elements or just sending the elements
- that differ in the set is cheaper.
+ 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.
</t>
+
<t>
This document defines the normative wire format of resource records, resolution processes,
cryptographic routines and security considerations for use by implementors.
@@ -1373,6 +1419,19 @@
<t>
Bulub.
</t>
+ <t>
+ Another probabilistic approach to discover bad behaving peers is sampling, in this approach the proving peer needs
+ to prove that he is in possession of the elements he claimed to be. This is achieved by the following procedure:
+ </t>
+ <t>
+ The verifying peer chooses some
+ random salt and sends the salt to the proving peer. The proving peer salts the hash of elements with the given
+ salt from the verifying peer. Then the proving peer calculates the new hashes modulo a number depending on the set sized difference and
+ sends all the elements where the modulo calculation equals 0 to the verifying peer.
+ As soon as the verifying peer receives the elements the verifying peer can verify that all the elements
+ are valid and the modulo calculation equals 0 then the verifying peer can be assured with a high probability
+ that the peer is honest about his remaining set size and difference.
+ </t>
</section>
</section>
