[lsd0003] branch master updated: fix introduction

[gnunet]

This is an automated email from the git hooks/post-receive script.

grothoff pushed a commit to branch master
in repository lsd0003.

The following commit(s) were added to refs/heads/master by this push:
     new 64eb8f9  fix introduction
64eb8f9 is described below

commit 64eb8f92d160be6384333705d094328f3d0aa702
Author: Christian Grothoff <christian@grothoff.org>
AuthorDate: Wed Jan 13 22:45:33 2021 +0100

    fix introduction
---
 draft-summermatter-set-union.xml | 119 +++++++++++++++++++++++++++++----------
 1 file changed, 89 insertions(+), 30 deletions(-)

diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index a12fee4..f39a4dc 100644
--- 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>
 

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.