Hacker News new | comments | show | ask | jobs | submit login
Stellar Protocol: A Federated Model for Internet-Level Consensus (2016) [pdf] (stellar.org)
301 points by bushido 9 months ago | hide | past | web | favorite | 61 comments



I was curious about how this was different from Ripple's approach, I thought this was interesting:

> Generally, membership in Byzantine agreement systems is set by a central authority or closed negotiation. Prior attempts to decentralize admission have given up some of the benefits. One approach, taken by Ripple, is to publish a “starter” membership list that participants can edit for themselves, hoping people’s edits are either inconsequential or reproduced by an overwhelming fraction of participants. Unfortunately, because divergent lists invalidate safety guarantees [Schwartz et al. 2014], users are reluctant to edit the list in practice and a great deal of power ends up concentrated in the maintainer of the starter list. Another approach, taken by Tendermint [Kwon 2014], is to base membership on proof of stake. However, doing so once again ties trust to resource ownership. SCP is the first Byzantine agreement protocol to give each participant maximum freedom in choosing which combinations of other participants to trust.


To be more precise about this, the Ripple consensus paper (https://ripple.com/files/ripple_consensus_whitepaper.pdf) says in Section 3.3, "Since the UNLs for each server can be different, agreement is not inherently guaranteed by the correctness proof." This of course doesn't mean that Ripple is never safe if UNLs disagree. (A node's UNL in Ripple serves the same function as a node's quorum slices in SCP.) It just means that the analysis from Section 3.2 does not apply. SCP was designed to be decentralized in the sense that we assumed different nodes would want to chose different quorum slices and wanted to achieve the best possible safety for any such choice.

A particular concern with Ripple is what would happen if Ripple validators failed not by crashing, but by getting compromised and acting maliciously (so-called Byzantine failure). The Ripple paper states in Section 3.2 that "it would take (4n + 1)/5 Byzantine failures for an incorrect transaction to be confirmed" (where all nodes are assumed to have identical UNLs and n is the size of that UNL). I believe this is an error, as with a quorum size of 80% of n, it is easy to construct a counter-example. Suppose nodes v_1 and v_10 are honest, while v_2, ..., v_9 maliciously deviate from the protocol. Now consider the two 80% sets (v_1, ..., v_8) and (v_3, ..., v_10). Those two sets overlap at only malicious nodes that could prevent v_1 and v_10 from hearing about each other's transactions.

The nice thing about SCP is that it is optimally safe (Theorem 13 in the paper). That doesn't mean it guarantees safety under all possible configurations (e.g., two disjoint sets of nodes that don't know about each other). But it means that in any configuration where there exists some protocol that could guarantee safety, SCP will guarantee safety as well. That includes Byzantine failure scenarios. So you could translate UNLs into quorum slices and substitute SCP for Ripple's consensus algorithm, and if RPCA was already guaranteed safe, then SCP will be, too. The converse is not guaranteed; you could choose a configuration that is safe under SCP and risks forking under RPCA.


What part of this is interesting to you?

This paragraph does not explain how they are different from Ripple's approach only that they are in fact different.


> This paragraph does not explain how they are different from Ripple's approach only that they are in fact different.

I think the last line sums it up: "SCP is the first Byzantine agreement protocol to give each participant maximum freedom in choosing which combinations of other participants to trust."

As opposed to Ripple, where the trust is heavily biased towards the starter membership list, making it more centralized than one would want.


> As opposed to Ripple, where the trust is heavily biased towards the starter membership list, making it more centralized than one would want.

It’s biased because of a technical issue (consensus must be reached). How does the Stellar protocol solve this technical issue?


How exactly does that work?

To me, the statement says essentially "you can trust us more than Ripple" with no explanation as to why.


The explanation is in the PDF. OP was just pointing out the high-level description of how it's different. Obviously, the devil's in the details.


Your doubt is legit, afterall they may not be so different:

https://www.quora.com/Why-did-Jed-McCaleb-leave-Ripple-to-st...


Response from Jed that I stumbled on the last time I was researching this. Oddly enough, I cannot find the response on Quora anymore.

https://www.reddit.com/r/Stellar/comments/7n8ntb/david_schwa...

> David I always enjoyed working with you and I thought we had a degree of respect for each other so I'm pretty disappointed in your tone here. I don't really want to get into a big back and forth about this but this just isn't correct. When I left ripple the board was 2 people; myself and Chris.

> I left because I made the mistake of bringing Chris on as CEO and it ended up being untenable to work with him for a variety of reasons.

> I feel like I've been extremely restrained in my criticism of ripple despite the frivolous lawsuits from you guys the constant attacks on my character and my family. I know you are actually a good person but I think you are in too deep to see how horrible Chris has acted toward me.

> Stellar hasn't abandoned the idea of distributing the lumens widely and the original facebook distribution was actually a success but the software/ecosystem wasn't ready for it at the time so we stopped it. We will do something similar in the future. I don't think any attempt at an internet level protocol like stellar or ripple can be widely adopted with a for profit company owning the majority of the tokens.

> Stellar has always been focused on cross border payments so the IBM announcement isn't a pivot by any means.

> Stellar and ripple are going after two completely different use cases as far as I can tell so I don't understand the continued hostility.


"... gives maximum freedom ..." nice way of putting the fact that there's basically no consensus; i've got even better idea, with more freedom - everybody can write whatever they want into append only database and they have freedom to choose which bits make sense.


That sounds like secure scuttlebutt.

Secure Scuttlebutt is a database protocol for unforgeable append-only message feeds.

"Unforgeable" means that only the owner of a feed can update that feed, as enforced by digital signing (see Security properties). This property makes Secure Scuttlebutt useful for peer-to-peer applications. Secure Scuttlebutt also makes it easy to encrypt messages.

https://scuttlebot.io/more/protocols/secure-scuttlebutt.html


This is a very lucid description of how Secure Scuttlebutt works.

SSB is deliberately “against consensus”, which makes it useless as a trustless decision-making tool. So I take your point that this property of Stellar seems to make Stellar useless for its stated purpose. (I haven't read the paper, so I may be very wrong.)


Multiple commenters here are saying that Stellar has no consensus. Is that true? How could such a big issue be overlooked?


> Is that true?

No.

If you’re worried about it, read the linked paper. The mechanics (and assumptions) are covered in painstaking detail.


So, IOTA?


IOTA is not decentralized. Although it allegedly will be in the future.


Eli5 please ! ;-)


In other words you can implement arbitrary dynamic trust, Opening up the possibility of arbitrary hierarchies, and much more efficient and robust mechanisms of establishing truth. Authorities could be designed arbitrarily and evolve on top of this core protocol. This so far sounds closer to tcp/ip foundation. Bitcoin would be more like Series of children with a dynamic system of never ending strings and Styrofoam cups.

I bet there is already CS research theory ready to apply to this design. (Easier said than done and I am just guessing really).


Somehow I don't think you've met very many 5-year-olds.


There’s a great, three year old HN thread about the Stellar protocol, starting with a critique by Gregory Maxwell (nullc) here: https://news.ycombinator.com/item?id=9342348


I’m not sure that post is about SCP? “Three years old” predates the publication of this protocol.


Stellar was re-written in 2015, so I suspect this critique will be of the legacy Ripple protocol


The linked comment thread is on this post announcing SCP:

https://www.stellar.org/blog/stellar-consensus-protocol-proo...


Leader election in distributed systems is still an unresolved problem AFAIK except for proof of work. The problem is what does the leader have to give up to be a leader? The economic value of being the leader must be balanced by the work to become the leader otherwise there is an opportunity for arbitrage. For instance, if the value of leadership is X and the cost to do a Sybil or other attack is X/10 the network will be eventually attacked that way.


In distributed ledgers, it doesn't matter who the leader is. The system only has to ensure that leadership is distributed in such a way that it is statistically infeasible or economically unprofitable to rewrite history.

PoW distributes the leadership (block creation) via crypto puzzles. PoS tries to use economic incentives to make bad behavior more expensive than good.

There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example). The basis of such a system is going to be the creation of non-biasable pseudo-random number generation.

Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS.

Edit: for clarity

A lottery-based system works because the "winning numbers" (imagine a winner being a node whose public key when XOR'd with the winning number is below a certain value) are known to all (a protocol like randhound ensures that all nodes know the winning number). A winner's bundle of transactions are validated as his/her's by cryptograpic signature (which can be verified using the same public key that is used to confirm this person is truly a winner). Those are the broad strokes. Obviously there's a lot more to getting it to work. I've been working on it for months and still haven't gotten around to putting it down on paper.

[0]: https://arxiv.org/abs/1607.01341

[1]: https://eprint.iacr.org/2016/1067.pdf


> There's work being done (which I personally believe is the right way to go) in using a leader election-based system that works like a lottery (Algorand[0] is an example).

Probably what you meant but I still wanted to mention it: Bitcoin (or most PoW schemes) work like a lottery. Think of each attempt at generating a nonce below the required difficulty as a lottery ticket. The more nonces you generate (the more hashes per second you compute) the higher your chance of winning. The system works because people who spent lots of money on lottery tickets in the past (and maybe won one or two times) are incentivized to keep the lottery running in an honest manner (so their prize keeps its value - if they haven't spent it).

> Along these lines one of the more intriguing projects is called RandHound[1]. It's a way of creating distributed randomness (according to the paper's title). I think chains secured via lottery leader selection protocol has more promise than PoS.

Another notable mention is dfinity (dfinity.org). They have a very interesting technology stack and I'm hoping for discussions about it in the future on HN.


Yes and no. A true lottery predictably periodic - it happens in rounds. PoW puzzles are async and so the chain can fork. The second property of the crypto puzzle kicks in here - the statistically predictable number of hashes necessary to solve the puzzle which can then be used to calculate an average time necessary to create a valid block. With a forking chain, it's this time gap that secures the chain against rewrites. So yes, PoW is used to distribute block creation among the network but it differs from a true lottery system in that it is not synchronized into rounds.


Ah, I see now how the terminology is applied. Thanks for the clarification.


Isn't the problem with random selection, that if there's very little cost to enter then a bad actor can flood lottery with entries?


My understanding is they try to mitigate this by having a minimum account balance to participate.


That's one way to introduce proof-of-stake.


What's interesting is that SCP implements consensus without electing a leader. There are, of course, numerous asynchronous protocols that do this, like Ben Or, Rabin, Mostéfaoui, and most recently HoneyBadger, but is rarer for synchronous protocols like SCP. However, it is necessary for SCP's setting, because if you don't even have agreement among nodes over what nodes do and don't exist in the system, how could you hope to elect a leader.

One way to view how SCP avoids leader election is to consider that it is effectively emulating the leader. SCP has two phases, a nomination and a balloting phase. The nomination phase is effectively like one or more instances of an asynchronous broadcast protocol (which don't require a leader since multiple nodes can choose to broadcast). The balloting phase is like Paxos, except that the value to propose is embedded in the ballot number so nodes don't require a leader to tell them what is being proposed--they can each emulate the leader themselves.


You seem to use a very narrow definition of "distributed system" compared to most people. Could you explicitly state your assumptions? Your "distributed system" seems to coontain assumtions such as trustlessness and openness towards new participants. (No sybil attacks with fixed entities)


Yes, I was assuming a cryptocurrency situation in which the system is open, new participants can join, and it must work under byzantine fault-tolerant conditions. In a system such as RAFT or PAXOS this isn't the case and thus these systems can properly elect leaders.


Stellar is one of the robust and undervalued asset. It has great potential and I think this year we will see lots of intereting things built on top of Stellar.


But why should XLM have any value? Isn’t it just a means to transfer other things?


Because any value that is not directly cashed out of XLM stays in XLM.

One application that uses XLM as its native currency is SatoshiPay[0] (that's how I got to know Stellar).

[0]: https://satoshipay.io/


[deleted]


Could you post your transaction IDs? I've never heard of anything like this.



When I read white papers, there is only one question I need answered and I feel that the Stellar whitepaper just dances around that question:

Does the algorithm fundamentally require that every transaction have to eventually pass through every node in the network?

The idea of quorum slices seems to imply 'no' but the whitepaper doesn't appear to make any attempt to connect the concept of quorum slices with actual transactions.

Can anyone answer that question?


Yes. Every validator in Stellar has a copy of the complete ledger. However, different validators may be authoritative for different types of token. Say bank_A runs a validator and issues digital dollars on Stellar, while bank_B runs a validator and issues digital euros on Stellar. Each validator will store both banks' token holdings and prevent double spends. However bank_A should offer to redeem its digital dollars for real currency only when the redemption transaction commits on its own validator, and similarly for bank_B.

Running a validator protects a token issuer against double redemptions, as might happen in a mining-based blockchain where anonymous miners fork the blockchain and thus create twice as many tokens. That's fine for pure crypto tokens, where you can create Ethereum [classic] or Bitcoin cash out of thin air. But if you were using colored coins or ERC20 tokens to represent claims on bank deposits, these forks would be a problem.


AFAIK the current implementation of Stellar has every "full node" record every transaction. In general, consensus and scaling should be orthogonal so you should be able to combine SCP with something like sharding if you think that's a good idea.


Where can one actually buy some? I have some BTC/LTC I'd like to trade for stellar but it seems all of the reputable exchanges that trade it are closed to new registrants. Any suggestions?


I'm not a financial advisor but you can get them on Binance.

If you look at the market tab of this site, it gives you an idea of current and old exchanges for that instrument.

https://coinmarketcap.com/currencies/stellar/#markets


BTC/ETH can also be traded on Stellar's Distributed Exchange. One of the easier to use exchanges that provides a bridge for this is Stronghold.co (US/SFO based)


Stronghold[0] works great with me.

[0]: https://stronghold.co/


Trading into a very thin market there, though.


Bittrex has it, and that's where I've been buying it.


poloniex.com


When Stellar's codebase was still just a fork of Ripple (entire codebase was completely re-written from scratch in 2015), it experienced many divergent forks of the network due to weaknesses in the Ripple consensus protocol. Those weaknesses have been eliminated in the new SCP described in this paper, but AFAIK Ripple still has these systemic problems. The new Stellar codebase is actually a joy to work with.


I know their api is really nice and I was surprised how easy was to work with it, whether it is a test net or public.


Thanks for the kind words! (disclosure: I designed most of the API)

We're not done yet. IMO it's still not easy enough to build great software on top of our work.


Are there future plans to add smart contracts (with a "Turing-complete" virtual machine) to Stellar? I think that the Stellar consensus protocol with its speed would be perfect for overcoming the current limitations of Ethereum.


I hope not. Stellar's appeal is its simplicity, and shipping a full programming environment with all the baggage of maintenance over time seems overly complex, and prone to causing issues down the line. There's very likely a way to achieve similar smart contracts, albeit without network consensus à la Ethereum, in the current Stellar world.


Not so much concrete plans around smart contracts (that I know of); I would characterize stellar as having aspirations and some early stage work and research with the intentions of enabling smart contracts on top of stellar. For example, we've done some work on "simple contracts" as described here: https://www.stellar.org/blog/multisig-and-simple-contracts-s....

Rant Incoming:

I don't think building a turing-complete VM into stellar anytime soon is prudent. The work the ethereum folks have done is crazy impressive, and certainly it is beyond anything I myself could create, but IMO they are also too cavalier. I don't think we (programmers in general) have the collective smarts, wisdom, discipline, and ethical codes needed to build a safe "world computer" yet, and I don't think we've got a good grasp of the potential ramifications of an unsafe solution. I imagine there are many unknown unknowns to encounter as the world stumbles in the dark, greedily, from where we are today in the direction of skynet.

All that said, I'd really like to see a world with more decentralizing forces and where decentralized applications can more feasibly compete with centralized services. I think stellar can help make this happen one day. I'm sick of being forced to trust the googles and facebooks of the world with my personal data while not having viable alternatives, and I think one way to work towards breaking their outsized influence on humanity's digital culture is to enable and make accessible more decentralized interactions of increasing richness. Instead of building one turing-complete decentralized protocol to rule them all, I'd love to see us continue to develop a constellation of focused decentralized systems that we can consider/develop/verify/maintain in isolation first. Then, as our comfort with each system grows, we can work to carefully combine and layer them in increasingly useful ways. There's such a long way to go.

On a related note, IMO we too often think that what we're doing on a day to day basis is just computer science and don't often enough consider the social science-y aspects of our work. From how we structure our APIs to how we communicate with users about the responsibilities involved with participating in decentralized systems, we have tons of soft problems to overcome that can't easily be fed into a compiler or reasoned about formally to determine the quality of our solutions. For evidence, look at what occurred recently with the parity wallet/solidity or -- an example that hits closer to home for me -- the snafus around the account recovery system in stellar's original web client.

---

Please take the above with a grain of salt. I realize that the above isn't supported with citations and in the end I'm just some random fuckhead coder. I'm sure plenty of people here can point to why my thoughts on the subject are wrong and why ethereum is taking the correct approach to smart contracts; I don't pretend to be able to hang with the big brains of the cryptocurrency space.

All of the above is also not representative of stellar's official positions... these opinions are 100% my own.


Turing completeness is not a virtue in a smart contracts language.


Whoa, awesome, well, thank you personally. I find it surprising the UI is pretty rudimentary taking into account how API is easy to work with.

I am looking to do something, not 100% what on Stellar Network, mostly due to the fact that I am familiar with it and I like api among other things.


Seriously: Stellar is _by far_ the easiest asset exchange platform I've ever worked with. It's completely silly, but it took me five minutes to create an IOU for a beer and send it to a friend (which they can "withdraw" as a free beer IRL at any time).

I'm deeply skeptical of most altcoins, but Stellar is going places.


Fine comment, but you can't make an account with a trollish name, even when it's the local superego you're trolling. If you want to participate on HN in good faith, that's great, but then please really do so. Continued abuse of HN will eventually get your main account banned too, so please just don't.


Can Stellars be mined? I received some before 2015 when they were giving it away for free. Now I'm happy that I can turn them into BTC and withdraw cash...


> Can Stellars be mined?

No.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: