Subject: [Ilc] Clarifications and thoughts purpose of ILC list

From: [email-masked]
Date: Thu, 16 Feb 2017 13:58:42 -0800

The fact that the term consensus has a colloquial meaning may be
generating confusion among some members of the list.  As intended in the
list name, the term consensus refers to a narrow distributed systems
definition, namely the problem for a group of nodes to pick an input
value such that there is both agreement (all nodes output the same
value) and validity (the output equals one of the valid inputs, ruling
out vacuous solutions like always outputting zero).  This is not to be
confused with other meanings of the word, as in "rough consensus and
running code," or consensus in any kind of a governance context.

Many kinds of distributed system leverage some a consensus mechanism.
At a high level, one of the things we might want to discuss in this list
is whether it could be beneficial for the IETF to standardize some kind
of consensus protocol or service.  Such an effort could provide a useful
building block for new or enhanced applications such as Internet
payments, auditable software packages, end-to-end email encryption, and
probably more things I haven't thought of yet.  The goal of this list is
certainly not to replace existing protocols or to change Internet
governance.

While obviously consensus mechanisms have been around for decades, one
recent development has been the advent of so-called permissionless
consensus mechanisms with open membership.  These mechanisms allow new
types of system, for instance ones in which mutually distrustful parties
with no pre-existing relationship can execute atomic transactions
together.  If we abstract the Internet slightly (maybe pretending some
centralized IANA-controled identifiers are public keys anyone could have
unilaterally allocated), the Internet, too, starts to look like a
permissionless system.  That's where this idea of "Internet-level"
consensus originates.  Does it make sense to leverage the permissionless
aspects of the Internet to implement some sort of permissionless
consensus mechanism?  Should the IETF be undertaking efforts along these
lines?  Could such efforts benefit existing IETF efforts or solve
existing challenges?  If the answer to any of these questions is yes,
then this mailing list is the place to start throwing out ideas...

David

---

From: Tao Effect <[email-masked]>
Date: Thu, 16 Feb 2017 14:14:00 -0800

> generating confusion among some members of the list.

Which members? Bang them! >:-D

> As intended in the

I'm told they're fully aware of that.

> of consensus protocol or service.

As stated before on this list [1, 2], and as stated elsewhere on the web in semi-mathematical form [3,4], if such a consensus protocol or service is used with Certificate Transparency or anything else related to DNS, that would be to kill the Internet.

But you're welcome to work on a consensus-agnostic protocol if your intentions are benevolent.

- Greg

[1] https://mailarchive.ietf.org/arch/msg/ilc/BmFgooRm5GikT6mwhx9yOZgL1G8 <https://mailarchive.ietf.org/arch/msg/ilc/BmFgooRm5GikT6mwhx9yOZgL1G8>
[2] https://mailarchive.ietf.org/arch/msg/ilc/tUirMiYqzIogI1S14qRKhY8Fz0E <https://mailarchive.ietf.org/arch/msg/ilc/tUirMiYqzIogI1S14qRKhY8Fz0E>
[3] https://blog.bigchaindb.com/the-dcs-triangle-5ce0e9e0f1dc#.24dexymvl <https://blog.bigchaindb.com/the-dcs-triangle-5ce0e9e0f1dc#.24dexymvl>
[4] https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2016/blob/master/topics-and-advance-readings/Slepaks-Triangle.pdf <https://github.com/WebOfTrustInfo/rebooting-the-web-of-trust-fall2016/blob/master/topics-and-advance-readings/Slepaks-Triangle.pdf>

--
Please do not email me anything that you are not comfortable also sharing with the NSA.

> On Feb 16, 2017, at 1:58 PM, [email-masked] <mailto:[email-masked]> wrote:
> 
> _______________________________________________
> Ilc mailing list
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/ilc

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 21 Feb 2017 23:09:58 -0800

On Thu, Feb 16, 2017 at 1:58 PM, <[email-masked]> wrote:

> out vacuous solutions like always outputting zero).
>

I strongly agree it's important to look at traditional definitions of
consensus, particularly ideas like byzantine fault tolerance and CAP
theorem/partition tolerance.

> Does it make sense to leverage the permissionless aspects of the Internet
> to

implement some sort of permissionless consensus mechanism?

While I think that would be interesting, the existing solutions in this
space, namely Bitcoin-style proof-of-work chains, corrupt data under
network partitions (so-called "blockchain forks", see also eclipse attacks)
meaning they are not partition tolerant and therefore have neither CP nor
AP semantics under CAP theorem (although CP semantics would be desirable),
and have formally been demonstrated not to have the properties of byzantine
fault tolerance[1] (BFT) or byzantine fault detection (BFD), which I would
consider necessary in any sort of federated consensus system.

Though the notion of "Satoshi consensus" has garnered a bit of attention
due to Bitcoin, I hope any effort in this space is held to higher and more
traditional standards of what "consensus" actually means in traditional
distributed systems contexts, which includes not corrupting data in the
presence of network partitions, and ideally possessing BFT or BFD
semantics. So far, I am not aware of any feature-complete/deployed
"permissionless" system that provides these properties. That's not saying
they're impossible, but there's much groundwork that still needs to be done.

Though I don't speak for Stellar (but have observed they appear to behind
this BoF), I think they have been doing interesting work in this space with
SCP, even if it compromises on the so-called "permissionless" aspect. That
said, the Internet itself is a "permissioned" system (ASes can't peer willy
nilly) as are many of the core protocols the Internet has been built on,
and so far the sky hasn't fallen like certain chicken littles would tell
you it will.

Meanwhile the only "permissionless" system of note, Bitcoin, is having
system-crippling issues with both scalability and governance, and appears
to largely be under the control of mining cartels, so I'm not sure
"permissionless" systems are necessarily a good idea or if they actually
live up to the ideals of removing control of the system from a central
cabal.

At the end of the day systems need operators, and the operators will always
be able to exert some degree of control.

[1]: https://eprint.iacr.org/2014/765.pdf

-- 
Tony Arcieri

---

From: David Mazieres <[email-masked]>
Date: Wed, 22 Feb 2017 10:25:10 -0800

> they're impossible, but there's much groundwork that still needs to be done.

Well, there are a bunch of different variants of Satoshi consensus.
Some of them, like peercoin and tendermint, look more like traditional
BFT, only where participants are elected based on some other criterion
such as stake in a cryptocurrency.

> ...

I suppose one way of looking at the issue is that *all* consensus
systems start to misbehave when owners of more then some fraction of
some resource start misbehaving.  Bitcoin breaks once about 1/3 of
hashing power is controlled by someone with incentive to undermine the
system.  BFT breaks when 1/3 of nodes are malicious.  Proof of stake
breaks once too many coins elect Byzantine nodes.  So maybe the question
shouldn't be whether a system is permissioned or permissionless, but
rather along what axis the permission lies.  Another related question is
how to balance safety (meaning agreement and validity, or roughly "CP
semantics") against liveness (or "AP semantics" in CAP parlance)--as you
can trade one off for the other--and how does that trade-off get
decided.

For better or for worse, the "currency" driving Internet change seems to
be market clout.  This is soft of a simplification of the point made by
Clark et al. in "Tussle in Cyberspace," but basically change can happen
because millions of end users adopt some protocol, or because
systemically important ISPs unilaterally implement some change.  The
Stellar consensus protocol, SCP, was inspired by this model.  It relies
on something akin to market clout for consensus--individual nodes make
their own trust decisions, and so "transitive trust" is really the
resource that could allow someone to undermine the system.

Not all aspects of the Internet are as robust as the ideal market-driven
"tussle space."  For example, TLS certificates have a disjunctive
property, where a single CA can cause headaches for entities with much
greater market clout.  Moreover, it is difficult for individuals to
adopt a CA for a particular purpose (like some set of websites) without
it bleeding over into other purposes.  Obviously the trans working group
is improving the situation.  Similarly, once you choose an email
provider, your privacy is at the whim of that email provider even if, in
aggregate, email providers would like to provide greater privacy.
Finally, some things like payments between participants with no
preexisting relationship just don't work today.  This is one of the
reasons Stellar developed SCP, and why I personally believe that some
sort of standard Internet-level consensus would spur innovation that
promotes financial inclusion.

David

---

From: Ben Laurie <[email-masked]>
Date: Thu, 23 Feb 2017 11:15:43 +0000

> then this mailing list is the place to start throwing out ideas...

Sorry to be a bit late to the party here, but I feel this narrow
approach is not for the best, for various reasons.

a) IMO, it is still not proven that permissionless consensus with open
membership is actually possible - as I've argued before, the examples
we have now actually rest on an underlying permissioned consensus with
somewhat closed membership (e.g. the major mining pools or the code
developers), and claims that the permissionless versions are actually
not subvertible rely on somewhat weak economic arguments.

b) CT, for example, needs an internet-wide consensus, in effect, but
is not permissionless. At least some variants of the things you
mention above that would benefit from consensus are also not
permissionless (e.g. auditable Linux distros).

I don't object to those who believe in permissionless trying to work
out how to do that, but those of us who don't also need these
protocols and I think the IETF should address our needs, too.

> [email-masked]

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 23 Feb 2017 09:35:49 -0800

> such as stake in a cryptocurrency.

Like many things in this space, "Satoshi consensus" is an ill-defined
buzzword. In part I think it means incorporating programs into the
consensus decision, which seems like fairly novel and interesting work to
me (and somewhat similar to e.g. Trillian's "personalities"). In this
space, yes incorporating consensus programs into (P)BFT-like schemes such
as Tendermint is interesting.

However, above I was using it specifically to refer to the proof-of-work
scheme for consensus. "CP" versus "AP" of course both assume "P", a
property Bitcoin (and systems using a similar proof-of-work consensus
model) do not have. Under a network partition in Bitcoin, the system will
both make progress and be available for reading (where CP systems will fail
closed if they can't reach a quorum). When the partition is healed,
acknowledge writes are lost and data is clobbered. Systems which truly
uphold "CP" or "AP" semantics do not clobber data this way.

This sort of split-brain behavior can be exploited by attackers who are
able to arbitrarily create network partitions. Eclipse attacks are a common
example.

-- 
Tony Arcieri

---

From: David Mazieres <[email-masked]>
Date: Thu, 23 Feb 2017 10:35:56 -0800

> not subvertible rely on somewhat weak economic arguments.

Well, there's at least one existence proof, which is the SCP protocol we
use at Stellar.  SCP changes the question slightly from whether the
system is subvertible to who is being subverted, because it depends on
whom people trust.  E.g., if you trust TurkTrust and I trust the
conjunction of the ACLU and Google, you might get subverted because
TurkTrust has been known to issue bad certificates.  On the other hand,
even if Google somehow gets compromised, that won't subvert my view of
the world so long as the ACLU remains honest.

> permissionless (e.g. auditable Linux distros).

Well, maybe SCP shows that permissionless is not a binary setting.  It's
important that the ACLU be able to participate in consensus without any
existing participant's permission, and that people have the option to
depend on the ACLU for safety should they so desire.  However, unless
and until people do decide to wait for the ACLU for consensus, the ACLU
will not have any power.

I think this model is very Internet-like, in that it promotes "tussle
spaces" that resolve issues by market forces.  Though ultimately I'd
defer to you on what is and is not workable for CT, it seems to me that
SCP's model would in fact be good for some future CT 2.0, as well as
other transparency efforts such as software distribution.  In
particular, with CT you have a bunch of CAs, and even though not
everyone agrees on who is and is not a valid CA, there's significant
transitive overlap.  Moreover, independent third parties should be able
to audit the system, with end users able to depend on these parties.
That way, even if some extremely powerful attacker subverts all the
major players, people can survive by additionally depending on
independent players (e.g., now to fool me it's not enough to subvert
Google, you also have to subvert the ACLU).

> protocols and I think the IETF should address our needs, too.

Well, two things.  First, thanks for joining the conversation, because
of course any IETF-based consensus effort should address your needs.  At
the very least, an IETF-sanctioned "permissionless" consensus protocol
should probably support a degenerate "permissioned" configuration that
can serve CT's needs (or those of some future CT 2.0).

Second, the state of the art in decentralized Byzantine agreement may be
more advanced than a lot of IETF attendees are aware.  Hence, please
keep an open mind about what is and is not already possible.  Stellar's
payment network is an existence proof of a production system using this
technology today.  Since deploying Stellar, several people have people
approached us with other compelling applications, including package
management and end-to-end email encryption.

CT is perhaps a bit different in that it has an unusual requirement to
"fail open"--e.g., I don't want to stop seeing new web sites just
because the ACLU's server is down.  That could mean my intuition is not
right about what is and is not workable for a hypothetical CT 2.0.
However, there's a good possibility that if, either on this list or in
Chicago, we hash out a set of requirements for an ideal CT 2.0 consensus
mechanism, we will find ourselves a lot closer to the ideal than you
might think.

David

---

From: David Mazieres <[email-masked]>
Date: Thu, 23 Feb 2017 11:25:43 -0800

> as Tendermint is interesting.

Okay, then by that definition, "Satoshi consensus" is only one possible
approach among several to realizing Internet-level consensus.

> uphold "CP" or "AP" semantics do not clobber data this way.

I agree about CP, but not AP.  AP systems are not safe, and hence will
clobber data.

Perhaps CAP is not the best way to categorize these systems, though.  It
may be better just to assume an asynchronous communication model (which
subsumes temporary partitions as equivalent to slow nodes).  Then we can
just talk about safety (agreement + validity), liveness (termination),
and fault tolerance.

> able to arbitrarily create network partitions. Eclipse attacks are a common

Right, so basically you are saying any Internet-level consensus
mechanism should guarantee safety even in an asynchronous communication
model where you can't distinguish slow from failed nodes.  I agree,
personally.  However, reasonable people might push for greater
availability.  It would be interesting to see if list members have
"rough consensus" (non-technical meaning) on this point, or
alternatively if makes sense to layer a less safe but more available
"short-term" system on top of one that guarantees safety for long-term
events (e.g., for certificates issued over a week ago).  We may want to
revisit this question down the line after discussing more applications.

David

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 23 Feb 2017 11:38:18 -0800

> I agree about CP, but not AP.  AP systems are not safe, and hence will

Correctly designed AP systems support a merge operation to reconcile
disparate states. CRDTs are an example of a system that can always merge
data automatically in a conflict-free manner. In absence of that you need a
domain-specific user defined merge function.

That said Last Writer Wins is a popular strategy in systems describing
themselves as AP, and exhibits this sort of data clobbering behavior. I'm
not sure such systems should describe themselves as partition tolerant,
though.

> revisit this question down the line after discussing more applications.

The main option, which is particularly applicable to systems which publish
to read-only clients, is to allow stale reads. This flips the semantics
from CP to AP, allowing inconsistent views of the current state of the data
(i.e. sacrificing consistency for availability), but should be safe if data
being read is not incorporated into subsequent writes (i.e. stale reads are
only allowed by truly read-only clients)

-- 
Tony Arcieri

---

From: [email-masked]
Date: Thu, 23 Feb 2017 12:03:36 -0800

Tony Arcieri <[email-masked]> writes:

> data automatically in a conflict-free manner...
>
> ...
>

Ah, so I agree with the points you are making, I just think they are at
a different level of abstraction from the consensus mechanism.  In other
words, I can take a safe consensus protocol and use it to implement a
secure read-only log.  That log abstraction might support an operation
along the lines of "verify that some log prefix satisfies some
predicate," which one might then use to check that a particular
transaction committed, or to get a recent value of some variable without
necessarily knowing the latest.

So the question is not "are weak consistency models useful for systems?"
to which the answer would be an obvious yes.  The question is what, if
any, support would weakly consistent systems require from an underlying
Internet-level consensus protocol?  My preference would be to answer
"none," because I worry such support would complicate reasoning about
the safety of strongly consistent systems.  But that's obviously a good
topic for discussion on this list.

David

---

From: Ben Laurie <[email-masked]>
Date: Thu, 23 Feb 2017 22:37:58 +0000

> the world so long as the ACLU remains honest.

OK, so here's where I get to confess that I don't understand Stellar,
and, worse, I don't know anyone who does.

Is there an idiot's guide somewhere?

That said, the properties you claim are also trivially obtainable with
a CT-like system, so I totally buy it can be done. But I don't see how
this corresponds to the popular notion of "permissionless"? Not that I
actually care, btw.

> Google, you also have to subvert the ACLU).

I totally agree with all of this, but have two comments:

a) it seems utterly disconnected with the standard view of
"permissionless", so I think real care is needed with the charter.

b) whilst I think everyone should choose who they trust, in practice
this is mostly totally unusable. The ability to do it is not a system
problem: you have an answer in Stellar, I have one in CT/Trillian.
Others exist, I am sure. The problem is usability. Who chooses the CAs
you trust, for example? Not you (for most values of "you"), that's for
sure.

> management and end-to-end email encryption.

Of course, this is exactly what Trillian
(https://github.com/google/trillian) is all about.

> mechanism, we will find ourselves a lot closer to the ideal than you

I dunno, I'm feeling pretty positive right now. :-)

---

From: David Mazieres <[email-masked]>
Date: Thu, 23 Feb 2017 15:06:54 -0800

> Is there an idiot's guide somewhere?

Well, there is a cartoon guide, but I don't actually think it will be
useful in this context:

        https://www.stellar.org/stories/adventures-in-galactic-consensus-chapter-1/

The canonical guide is of course the whitepaper, which is probably hard
to read:

        https://www.stellar.org/papers/stellar-consensus-protocol.pdf

Maybe the most accessible rendition right now is my Google tech talk:

        http://www.scs.stanford.edu/~dm/20160606-scp-talk.pdf
        https://www.youtube.com/watch?v=vmwnhZmEZjc&feature=youtu.be

> this corresponds to the popular notion of "permissionless"? Not that I

My understanding of CT may be out of date, but I thought CT was a
disjunctive system, as in any log can vouch for a certificate.  As I
envision Internet-level consensus, you could insist on, say, 7 out of 10
log authorities signing off something that guarantees publication of the
certificate.

> "permissionless", so I think real care is needed with the charter.

I think the term permissionless may just not be useful in this context,
because even though it has been used to describe systems related to
Internet-level consensus, there are other potential solutions that don't
fit the permissioned/permissionless binary model.

> you trust, for example? Not you (for most values of "you"), that's for

Well, in my ideal world the browser vendors would ship some reasonable
default, but if I'm paranoid, I can add the ACLU and EFF, etc.  More
importantly, it should not be a pure disjunction where any CA can issue
any certificate, but rather should require some threshold.  Here we are
veering into CT 2.0 territory, because that's not how certificates
currently work, but there are other transparency applications that could
use such a threshold model from the start.

What consensus mechanism does Trillian plug into?  I had assumed
Trillian was what an individual authority would do, but I could probably
use some education about the bigger picture.

Thanks,
David

---

From: Ben Laurie <[email-masked]>
Date: Sun, 26 Feb 2017 21:25:23 +0000

>         https://www.stellar.org/stories/adventures-in-galactic-consensus-chapter-1/

Well, its fun.

>         https://www.youtube.com/watch?v=vmwnhZmEZjc&feature=youtu.be

OK, this was very helpful.

I was struck by your remark that enumerating the set of bad things
that might happen to you is exponential time. At least, I think you
said that. That doesn't seem like a great security property.

> log authorities signing off something that guarantees publication of the

In practice, this is how CT works - Chrome has a policy on what logs
must be used, for example. Full details here:
https://www.chromium.org/Home/chromium-security/certificate-transparency.

Obviously, if you are Joe Random, you can insist on some other policy.
But the world is unlikely to provide it for you.

> fit the permissioned/permissionless binary model.

Agree.

> use such a threshold model from the start.

OK, I am up for some kind of pluggable "what is the consensus"
infrastructure, but what you propose here is a major departure from
how things work right now. Such departures are hard.

> use some education about the bigger picture.

You are correct that Trillian is infrastructure. My vision is that
logs would log each other's tree heads. Obviously this is unlikely to
be universal, so is in some way the dual of your quorum slices.

---

From: David Mazieres <[email-masked]>
Date: Mon, 27 Feb 2017 18:22:34 -0800

> said that. That doesn't seem like a great security property.

I don't remember exactly what I said, but this is a general property of
threshold systems.  For example, in f-out-of-3f+1 PBFT, the number of
failure modes is going to be approximately (3f+1)!.  But that's okay
because there's a symmetry to it.  Similarly, if you say, "I'm
vulnerable if every bank at which I have deposits and 2/3 of the other
big banks act maliciously," that might be a reasonable policy even if
it's hard to enumerate all the subsets matching that criterion.

Another thing I might have said is that if you got a global snapshot of
arbitrary quorum slice choices and wanted to decide if there was quorum
intersection, that would be akin to deciding satisfiability (best known
algorithm exponential).  But A) quorum slices shouldn't be arbitrary,
and B) not all forks are bad from ever individual node's
perspective--the important thing is to avoid being forked from people
you consider important.

That said, the stellar-core sotware does have some options like
"--inferquorum", "--checkquorum", and "--graphquorum" that print a
sample quorum or show quorums based on actual history (which is
obviously much smaller than every hypothetical potential history).  Such
options are useful to spot-check one's intuition about policy, but they
aren't comprehensive.

> But the world is unlikely to provide it for you.

What you say necessary for certificate transparency because CT has to
"fail open" in the sense that logging is required while auditing the
logs is optional.  That is absolutely the correct design for TLS
certificates right now.

However, there are other potential applications where auditing should be
mandatory.  If is, then it becomes possible for Joe Random to insist on
another policy.

Here's an example:  Suppose RedHat and Debian start keeping logs of
every package they release, including package revocation messages for
packages found to have a vulnerabilities after they are released.
Furthermore, RedHat and Debian collaborate on some Internet-level
consensus to guarantee that their logs are append only.  Now suppose Joe
Random doesn't trust either RedHat or Debian.  Fortunately, the EFF
unilaterally decides to participate in consensus to help validate these
package logs.  By trusting a conjunction of RedHat, Debian, and the EFF,
Joe Random can gain greater assurance that he is not installing some
secret Trojan package that wasn't part of a mainstream Debian or RedHat
release.

> how things work right now. Such departures are hard.

To be clear, the last thing I am arguing for is in any way holding back
or changing the current design and deployment of CT.  However, for other
applications with fewer legacy requirements, it would be possible to get
stronger consensus.  And if such a consensus infrastructure works out,
it might be something appealing to CT in the future, or maybe some
auditing facility implemented on top of CT.  That's what I mean by the
vague term "CT 2.0."

> be universal, so is in some way the dual of your quorum slices.

So again, without advocating actually changing current CT efforts, what
if at some point we wanted to standardize not just the logging of
certificates but their auditing.  The idea would be that if, say, Google
legitimately obtains a second certificate from a different CA such as
TurkTrust before their first certificate expires, they submit to the
audit infrastructure a message signed by their old key saying that this
was a valid second certificate.  Otherwise, the auditing facility flags
the new certificate in such a way that browser users get a nasty pop-up
saying "Either this domain has a new owner, or they lost their key, or
this is a MITM attack."

This would obviously be a very long-term project, but it could improve
security over the status quo, and by letting any organization replicate
the auditing process, would allow Joe Random to customize his choice of
trusted auditors to some conjunction of parties he trusts and the rest
of the world trusts.

David

---

From: Ben Laurie <[email-masked]>
Date: Tue, 28 Feb 2017 21:04:13 +0000

> secret Trojan package that wasn't part of a mainstream Debian or RedHat

OK, but that seems equally doable with a CT-like mechanism. The EFF
either constructs its own version of the RedHat and Debian logs, or,
much more efficiently, keeps a log of their log heads...

>>> any certificate, but rather should require some threshold.

Thinking about this again, I'm not quite sure what you mean here: a
threshold of what? Logs of certificate issuance? I don't see how that
would prevent a CA issuing any cert it wants?

>>>  Here we are

Global consensus would help CT by providing a mechanism that prevents
CT logs forking.

> saying "Either this domain has a new owner, or they lost their key, or

This screws people who lost their keys, though - and, as you say, new
owners of domains. And since those will be the usual cases, the only
person it doesn't screw is the MITM.

And is pretty much orthogonal to consensus (other than the log forking problem).