[Trans] Design of gossip

Watson Ladd <watsonbladd@gmail.com> Sat, 27 September 2014 17:42 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: trans@ietfa.amsl.com
Delivered-To: trans@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 7DA3C1A6F22 for <trans@ietfa.amsl.com>; Sat, 27 Sep 2014 10:42:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.6
X-Spam-Status: No, score=-0.6 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 2LzxXZpX4e62 for <trans@ietfa.amsl.com>; Sat, 27 Sep 2014 10:42:31 -0700 (PDT)
Received: from mail-yh0-x22d.google.com (mail-yh0-x22d.google.com [IPv6:2607:f8b0:4002:c01::22d]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4B5231A6F1E for <trans@ietf.org>; Sat, 27 Sep 2014 10:42:31 -0700 (PDT)
Received: by mail-yh0-f45.google.com with SMTP id a41so4507614yho.4 for <trans@ietf.org>; Sat, 27 Sep 2014 10:42:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=w4yum4R8DrYQTqL1huroZs9YvH1AelImoENV9tBq9x0=; b=Q8AncWY1Dlx1whmdBkcFzkIMpEn2dQcaMXDXz/4sDZxW+cB+SS2BZszDbHFy9IVxUb ft1Iw+0dh+hkngIk0ZYw0w4MmQPS+n+lT+SokxZQMIR2v6IRCwy48eA36by+sMOtBPSo SpNVHypfuxmzx3UpK3JbVCULoveJSzDKjk0uC5xI3nvqcH8o3dPv1VDQeX+0izFPgoXR EP2LgHwyAucFOBEflRFOqNyMGQv/1XYqXeMIPZXypVD77xrTSXRo1jdFRhmmqSTs9x9Q VSHxxDWaDMJwO+GSTWJBsFQhTQmxqCQesGB830GwCcp44iskFeI+U1XcGsSQp3UxFhsZ f0TQ==
MIME-Version: 1.0
X-Received: by with SMTP id s3mr37260344yhk.69.1411839750503; Sat, 27 Sep 2014 10:42:30 -0700 (PDT)
Received: by with HTTP; Sat, 27 Sep 2014 10:42:30 -0700 (PDT)
Date: Sat, 27 Sep 2014 10:42:30 -0700
Message-ID: <CACsn0c=NDRnVUE0APeoYq2AL4hsX6nOQXnzGaJcP2vrNYJBduw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "trans@ietf.org" <trans@ietf.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/trans/J-oBoRol5Bt9lyvsR5_RsR9UOCo
Subject: [Trans] Design of gossip
X-BeenThere: trans@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Public Notary Transparency working group discussion list <trans.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/trans>, <mailto:trans-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/trans/>
List-Post: <mailto:trans@ietf.org>
List-Help: <mailto:trans-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/trans>, <mailto:trans-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sat, 27 Sep 2014 17:42:32 -0000

Dear all,

As has been noted a lot depends on the gossip protocol, and there
isn't a lot said about it right now. I'd like to kick that off by
outlining some of the fundamental choices that need to be made, and
what I think (possibly wrongly) their implications are.

The first choice is what to gossip: tree heads and proofs or certs.
Both have privacy implications: while certs more directly reveal which
sites are visited, it's possible that tree heads will be unique per
cert due to the impact of adding to a tree one cert at a time, so each
precert will end up showing a different head. This is a tricky issue.

The second choice is what gossip produces. In particular do we push
consistency proofs towards clients, or pull the heads towards
monitors? Either approach can work, but the first approach could save
bandwidth: a consistent head does not need to be reported. The first
also enables remembering what has been recorded. The second approach
is simpler for gossipers.

The third choice is how to gossip. Probably the best approach is some
sort of peer-to-peer network, with the possibility of using other
servers if the P2P approach doesn't work. However, gossip needs to be
censorship resistant, which can be a bit tricky. We also want gossip
to deal with a small fraction of malicious nodes, which means some
approaches are tricky: in particular nodes can't stop if some nodes
say "we've heard it before".

We also need to make sure we don't lose submitted heads, even as old
heads grow in number. Using consistency proofs to reduce the number of
heads helps with this problem.

DHTs may be a workable approach, but I don't know of Byzantine proof
ones. Flood-fill on random graphs scales if you make it publish only,
but dealing with old data gets tricky: we want new nodes to learn it,
without having to send it unnecessarily. Showing the result of an
audit and backfilling can work, but we need to think about the details
and try some experiments.

Watson Ladd