Live data from Hacker News

Stellar Consensus Protocol: Proof and Code

stellar.org

31–40 of 99 posts

Re: Stellar Consensus Protocol: Proof and Code

#31
post #6

Earlier quoted context omitted.

Graydon also created monotone, which was a big influence on git. http://www.monotone.ca/monotone.pdf https://en.wikipedia.org/wiki/Monotone_%28software%29#Monoto...

I think Monotone was an alternative to BitKeeper and BitKeeper was the inspiration of Git and Mercurial. It even seems to suggest that in the link you posted.

[deleted]

Re: Stellar Consensus Protocol: Proof and Code

#32
post #18

"It is the responsibility of each node v to ensure Q(v) does not violate quorum intersection". ::Sigh:: This sounds like it does not even speak to one of the major fundamental issues of their approach; which I pointed out in 2013 ( https://bitcointalk.org/index.php?topic=144471.msg1548672#ms... ) and appeared to play a critical role in Stellar's spontaneously faulting, and has been avoided in ripple by using effectiv…

You are correct that safety requires overlapping quorums. However, the trust decisions are public, as this is what allows participants to discover quorums. The scenario you describe of two groups of 100 participants overlapping at one node might or might not be a problem. The most likely cause of such a topology is a Sybil attack, in which an attacker with one seat at the table gloms an extra 99 nodes onto the system…

The attackers' 100 nodes might of course diverge if they are so configured, but nobody will care.

The person who is being attacked cares, right? Is there a way for a Stellar node to realize that it has been partitioned from the real network?

Re: Stellar Consensus Protocol: Proof and Code

#33
post #8

Is this protocol isomorphic to bitshare's Delegated Proof of Stake (DPOS) [1]? Seems to have the same qualities. *[1] https://bitshares.org/delegates

Bitshares is more democratic than decentralized. Basically people vote their stakes to elect 100 nodes that ensure consensus, but everyone knows who the 100 nodes are. By contrast, the FBA trust model is completely independent of coin holdings, and just depends on pairwise relationships between the validator nodes. The resulting quorum structure is unlikely to look like a single fully-connected group.

Re: Stellar Consensus Protocol: Proof and Code

#34

I'm getting very frustrated by this presentation, it's all "This is so amazing, it satisfies so many criteria, there's a big problem with financial institutions" I can only read those lines so much before I get the feeling of being whitewashed. How does it work? Where is the data? I'm reading the white paper now, but I felt compelled to post this comment after I read through yet another 10 paragraphs of exactly what…

Did you read the whitepaper? It's much more technical. Link: https://www.stellar.org/papers/stellar-consensus-protocol.pd...

Re: Stellar Consensus Protocol: Proof and Code

#35
post #32

Earlier quoted context omitted.

You are correct that safety requires overlapping quorums. However, the trust decisions are public, as this is what allows participants to discover quorums. The scenario you describe of two groups of 100 participants overlapping at one node might or might not be a problem. The most likely cause of such a topology is a Sybil attack, in which an attacker with one seat at the table gloms an extra 99 nodes onto the system…

The attackers' 100 nodes might of course diverge if they are so configured, but nobody will care. The person who is being attacked cares, right? Is there a way for a Stellar node to realize that it has been partitioned from the real network?

Yes, and this is kind of the whole point of the protocol. It just hinges on defining the real stellar network. An analogous question is, "Is there a way for a computer to realize it has been partitioned from the real Internet?" Well, sure. Pick 50 web sites you think are really important--maybe a bunch from Alexa, plus your bank, employer, etc.--and make sure you can reach the vast majority of them (using https, of course, so no one can impersonate them).

There's one sense in which FBA is stronger than the Internet analogy, however, it that is is actually testing transitive reachability. So instead of just making sure you can talk to those 50 web sites, you actually make sure all of those 50 web sites can talk to all the sites they consider important, and so on, until you get the transitive closure, which is basically the notion of an FBA quorum.

Re: Stellar Consensus Protocol: Proof and Code

#36

Are they talking about computer verified proofs? I wonder, are researchers able to prove the correctness of distributed algorithms the same way they would prove sequential algorithms (for instance, using some type of Hoare logic and sat solver/ proof assistant).

You may be interested in this[0] paper outlining AWS use of TLA+ to formally prove its systems. Also previous discussion here[1].

[0] http://research.microsoft.com/en-us/um/people/lamport/tla/fo...

[1] https://news.ycombinator.com/item?id=8096185

Re: Stellar Consensus Protocol: Proof and Code

#37

Are they talking about computer verified proofs? I wonder, are researchers able to prove the correctness of distributed algorithms the same way they would prove sequential algorithms (for instance, using some type of Hoare logic and sat solver/ proof assistant).

If anyone's interested in proving distributed algorithms correct, they should check out the Verdi project (https://github.com/uwplse/verdi), which has proved Raft correct in Coq. I imagine handling Byzantine faults and the full complexity of SCP would be quite a bit harder, but probably doable.

To me, though, it would be more interesting to prove the implementation correct. Rather than trying to prove an existing C++ implementation correct, it's probably more feasible to reimplement the algorithm within Coq and extract to runnable code. Verdi already supports that, but unfortunately it doesn't support disk state.

Re: Stellar Consensus Protocol: Proof and Code

#38

I'm finding the graphic novel explaining federated consensus to be really entertaining: https://www.stellar.org/stories/adventures-in-galactic-conse...

Joyce from Stellar here. Thanks! As we were working on the white paper, we realized how difficult it was to explain complex concepts like federated Byzantine agreement.

We know it’s part of our jobs to make these ideas understandable. That way more people can join the dialogue and think of ways this infrastructure can be used to build services for their communities, which may be really far from the nearest computer science program. So we decided to add a lighter approach in hopes of making it fun for people to learn.

Re: Stellar Consensus Protocol: Proof and Code

#39
post #25
post #21

I'm excited for the ideas here and have been following Stellar. But I'm hugely disappointed to see that they went with C and C++ for their new core codebase. This is the kind of code that needs strong safety, security, and correctness guarantees, and here in 2015 we have several mature languages with better safety & correctness guarantees. C# and Java are both mature and mainstream, and either would have been a sane…

If a program is formally proven to be correct, it doesn't matter what language it's written in.

Agreed, but that's not what they did here. They didn't prove the program is correct, they proved the algorithm is correct. It remains to be seen how closely the program actually implements the algorithm in the paper.

Re: Stellar Consensus Protocol: Proof and Code

#40
post #22
post #19

Earlier quoted context omitted.

> I believe the same kind of attacks to be plausible with the Bitcoin network This isn't anyone elses understanding. Can you suggest a mechanism by which it would be possible for a minority conspiracy to perpetually exclude a transaction in Bitcoin?

Well in bitcoin, of course, trust would map to computing power.

If you had a prisoner's dilemma game where people were trading and anyone could create currency then all would defect and create currency. By making substantial expenditure of energy the cost of defecting, the game loses its prisoner's dilemma quality. This is what makes bitcoin unique IMHO. Other systems have no structured way to create currency that doesn't rely on a particular party not defecting. There's tit-for-tat, but increasing the price to defect works so much more neatly.
Post reply on HN