mazieres

How is Stellar still "in the gate," more than two years after deploying their decentralized Byzantine agreement algorithm?

Ripple has only just now, in 2018, published their decentralized consensus algorithm (Cobalt), which as far as I know is not even in production use yet, and doesn't provide optimal safety. (In settings where Cobalt is guaranteed Safe, SCP would be too, but not vice versa.) Their production network still uses a protocol that, by Ripple's own analysis (https://arxiv.org/pdf/1802.07242), fails to guarantee safety without >90% agreement on the UNL.

Note that in general there is no way to name a particular branch of a blockchain fork. In cases with a protocol change coordinated well in advance, a counterparty anticipating the fork could announce that their tokens on one branch will be useless. However, if you just have two competing mining pools duking it out with the same protocol, there will be no way to name the branches ahead of time.

What's worse is that colored coins could distort the incentive structure to make it profitable to bribe miners, because the benefit to an attacker of subverting consensus could far outweigh the value of 12.5 BTC/block.

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.

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.

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.

Well for safety it's a logical AND, not an OR. But for liveness you'd most likely you'd have some threshold. For example, you might that at least 34 of the 50 are honest.

At it's core, the question of whom to trust is of course crucial, as there are clearly at least straw-man answers that have undesirable effects. But the trust topology affects more than safety, it affects the scenarios in which a consensus protocol is useful. E.g., if I issue some scrip and trade it on the Stellar network, I don't necessarily want to depend on mining rigs in other parts of the world for my ledger safety. I want to tell people "trust whomever you want, but be sure to include me as well, because I won't let you redeem the scrip if you don't have it on my ledger."

Part of the goal of SCP is to leave such policy questions up to the market and see what kind of architecture emerges. Our hope is that this flexibility combined with the lower barrier to entry will lead to greater financial inclusion as people build on our platform. But if we add too many policy restrictions, we risk heading off unanticipated innovations. (Heck, someone might literally replicate the Bitcoin policy and configure their quorum slices to trust 67% of whoever mined a Bitcoin block in the past week. That wouldn't really make sense, but it's possible.)

That said, what you're getting at is that with flexibility comes risk. We can't a priori rule out the possibility that organizations will choose bad quorum slices that violate safety. But we need to ask under what circumstances people care about safety and why. People obviously won't care about forks if one of the branches is purely a Sybil attack. But they likely will care if "real organizations" diverge, for some notion of that term. The reason, again, is that at some point the "real organizations" will affect one another in the network, however indirectly--maybe after a chain of five payments. That kind of indirect link is precisely what FBA quorums capture in the transitive closure of slices. So if everyone depends on the financial institutions they expect to do business with, and the whole economy is in fact interconnected, then Stellar will be safe.

I obviously believe such interdependence exists, and fully expect Stellar to be safe, but I can't predict exactly what the network will look like. Nor do I want to, as this could limit innovation. Only time will tell how this plays out.

So first, a lot of problems with Internet routing do not really affect SCP's safety--for example bogus route announcements. Part of the reason is that SCP depends on transitive reachability. And of course part of the reason is that SCP is built on top of the Internet, so can already assume a basically running network underneath.

I can't predict the future, but I do think it is likely that a bunch of de facto important players will emerge and have fairly complete pairwise dependencies. One reason is that Stellar follows a gateway model, where counterparties issue credits. So for example, down the line people might want to store their money as Chase or Citibank USD credits. So people will already have some notion that some participants are trustworthy enough to hold their USD deposits, and these institutions will emerge as important. If I'm a Citibank customer and you send me money, I obviously won't consider the payment complete until Citibank says it is. And of course Citibank is likely to want to depend on a bunch of institutions they do business with, so even just one bank should give me good transitive reachability.

But the nice thing about safety is that you can reduce any individual party's trust by depending on more people. So for example Stellar will run a validator node for the foreseeable future, and their incentives are different from Citibank's. To gain more trust in the system, I might want to wait for both Stellar and Citibank to agree before considering any payment fully settled.

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.

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.

No. At least for the moment, the proofs are English language only.

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 that nobody trusts. The attackers' 100 nodes might of course diverge if they are so configured, but nobody will care.

A priori, we cannot definitively answer what kind of topology will emerge. But there is certainly precedent for building a robust network out of pairwise relationships, namely inter-domain routing on the Internet.