[Hyperledger Project TSC] Project Proposal: Consensus Platform


Hart Montgomery
 

Hi Martin,

 

Is there a reason this hasn’t been submitted to a conference for peer review?  I’d highly recommend doing so—you’ll have a lot more credibility with regards to people believing the protocol if you can get it published in some conference proceedings.  If you need help, I bet there are people on this list who would be happy to point you in the right direction.

 

As it is, I’d be wary of accepting any new crypto or consensus into Hyperledger that hasn’t been published in a reputable conference or heavily reviewed and documented by outsiders.  It sets the precedent that the TSC or other members of the community would have to be academic-style crypto reviewers in order to properly assess new contributions.  While some of us may be, it puts an impossible burden on those that are not, and the appropriate place for new research to be evaluated (which new crypto or consensus is) is an academic conference anyways.  Additionally, to be truly safe, lots of time and review is needed for protocols that will be critical to systems.  For instance, the SHA-3 competition and review process took five years.  While we don’t need that much time for new consensus algorithms, I think this is still an area where it is much better to be safe than sorry.

 

Thanks for your time, and have a great day.

 

Hart

 

From: hyperledger-tsc-bounces@... [mailto:hyperledger-tsc-bounces@...] On Behalf Of Martin Arrivets via hyperledger-tsc
Sent: Tuesday, June 27, 2017 9:55 AM
To: Christian Cachin <cca@...>
Cc: Martin Arrivets via hyperledger-tsc <hyperledger-tsc@...>; Giacomo Puri Purini <giacomo@...>
Subject: Re: [Hyperledger Project TSC] Project Proposal: Consensus Platform

 

Thanks for the links,

 

Indeed the problem cannot be solved with a deterministic protocol

 

But there are ways to circumvent the FLP theorem by sacrificing determinism

cf Rabin, M.O. (1983) ‘Randomized Byzantine generals’ for example.

 

It is possible for a nondeterministic system to achieve consensus with probability

one.

 

That is what the Hashgraph does and that is what I meant when I wrote that participants 

will "eventually" (with probability one) know the exact location of a transaction in history.

 

The Hasgraph algorithm introduces periodic 'coin-rounds' where witnesses vote randomly. This

defends against attackers that control the internet and want to partition the network.

 

Martin

-----Original message-----
From: Christian Cachin
Sent: Tuesday, June 27 2017, 6:09 pm
To: Martin Arrivets
Cc: Martin Arrivets via hyperledger-tsc; David Huseby; Christopher Ferris; Giacomo Puri Purini
Subject: Re: [Hyperledger Project TSC] Project Proposal: Consensus Platform

Martin,

I've understood that there exists a white paper, yes.

But perhaps you should be aware that mathematically, in a "fully asynchronous
system" as you describe below, with < 1/3 faulty nodes (that crash or
act maliciously), or even with just one node that may crash, the "consensus
problem" cannot be solved with a deterministic protocol.

This is a famous result in distributed systems:
"Impossibility of Distributed Consensus with One Faulty Process" usually
just called "FLP impossibility".

See more:
  https://en.wikipedia.org/wiki/Consensus_(computer_science)
  https://en.wikipedia.org/wiki/Byzantine_fault_tolerance
or a textbook I co-authored - www.distributedprogramming.net - although the
FLP result is not explained in there.

What you describe seems equivalent to this well-understood consensus problem.

In contrast to hashgraph, PBFT has been peer-reviewed and widely understood
to achieve consensus in the appropriate model (eventual synchrony, not
asynchrony).

Regards,

      Christian



On 27 Jun 2017 12:03:06 +0000, Martin Arrivets <martin@...> wrote:
> Hi Christian,
>
> The system achieves consensus in the sense that a participant will
> eventually know the exact location of a transaction in history and have
> a mathematical guarantee of finality (that this is the consensus order).
> The knowledge is not probabilistic but a mathematical guarantee.
>
> The proofs in the whitepaper
> <http://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf>; make the
> standard assumptions:
>
> More than 2/3 of the computers are "honest", which means they follow the
> algorithm correctly and are available. Although an honest computer may
> go down for a while (and stop communicating) as long as they eventually
> come back up.
>
> Nodes can collude and are allowed to mostly control the internet . Their
> only limit on control on the internet is that if Alice repeatedly sends
> Bob messages they must eventually allow Bob to receive one.
>
> The proofs are for a fully asynchronous system. There is no assumption
> that an honest node will always respond within a certain interval. If
> all the nodes go to sleep, then progress continues as soon as they come
> back up. In normal conditions with a small number of nodes, consensus
> can happen in less than a second.
>
> I am not aware of any third-party reviews of the whitepaper. 
>
> The concepts are very similar to other voting-based BFT algorithms
> except the voting is "virtual". If the security of those systems (like
> PBFT or Tendermint...) has been vetted by the schemes you mention then
> perhaps they could be applied to Hashgraph as well.
>
> Hope this answers you questions.
>
> Regards,
> Martin
> -----Original message-----
> From: Christian Cachin
> Sent: Tuesday, June 27 2017, 11:43 am
> To: Martin Arrivets via hyperledger-tsc
> Cc: Martin Arrivets; David Huseby; Christopher Ferris; Giacomo Puri
> Purini Subject: Re: [Hyperledger Project TSC] Project Proposal:
> Consensus Platform
>
>
> Martin,
>
> Can you point to any independent analysis of the properties achieved by
> Swirlds consensus?  In which sense does it reach "consensus"?  Are there
> any peer-reviewed publications or other third-party endorsements
> available?
>
> In analogy with cryptography, where such issues have been discussed at
> large, and over many decades, the security of a system should be based
> on well-established and widely agreed-on schemes.
>
> (FYI - I'm a cryptographer and also working on consensus protocols...)
>
> Regards,
>
>     Christian
>
>
> ---
> Christian Cachin                           email: cca@...
> <mailto:cca@...> IBM Research -
> Zurich                           tel: +41-44-724-8989 Säumerstrasse 4
> CH-8803 Rüschlikon, Switzerland       http://www.zurich.ibm.com/˜cca
> <http://www.zurich.ibm.com/˜cca>;
>
>
>

Join tsc@lists.hyperledger.org to automatically receive all group messages.