Stellar Consensus Protocol: Proof and Code

Read section 3 and 4 of the whitepaper - the whole trust a quorum model is directly aimed at Sybil-style attacks. The key argument here is that the way they do group membership prevents these attacks by using a trusted quorum. This seems like a key place to focus attention for outside analysis of the properties of this protocol. If the assertions about this are incorrect, then the whole thing breaks down. As the Sybil paper points out, membership is critical for consensus. As a common-sense thing, "we have agreed" is super dependent on who "we" is.

As for eclipse, the model is so fundamentally different that it's not clear that there is a direct analogy for those network attacks. What do you have in mind? I'm not saying that it's obviously safe, just that attacks on the network protocol would have a very different flavor.

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.

(disclaimer: I had early access to the white paper for review)

Sybil attacks are not really directly applicable here since each node in the system picks its own quorum slices (basically the set of nodes that it trusts). There is no notion of global reputation and nodes do not need to know every other nodes to participate. Looking at the definition of quorum intersection[0] section 4.1 should give you a sense of the conditions that are required on the choice of quorum slices for the network to function properly (quorum intersection ensures safety)

The proof exposed in the paper guarantees safety and liveness for the network provided a certain number of reasonable conditions are held true. What that means is that an attacker cannot force on intact nodes (definition p14) invalid transactions nor prevent the network from making progress.

That being said, (at least in the version I reviewed) there is no guarantee provided with respect to ensuring that all valid transaction will eventually make it into the network. Indeed a set of highly trusted nodes (present in a lot of quorum slices) could attempt to preempt a specific set of transactions X (originated by edge nodes) by opportunistically broadcasting valid transaction set V_i for each successive ledger entry i that explicitly do not include the targeted set of transactions X. Under raw SCP as described in the paper and for certain topologies this preemption could be real and this is the closest I can think of a Sybil attack. It's important to note that we still have liveness and safety in that case.

I believe the same kind of attacks to be plausible with the Bitcoin network and I know protection mechanisms against it are currently being evaluated by David, Jed and the rest of the team. I will let them share their progress when they think it's right. I also hope they will correct me if I stated anything inaccurate here!

[0] https://www.stellar.org/papers/stellar-consensus-protocol.pd...

"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 effective centralized admission to the consensus in the system to ensure a uniform topology.

The (generalized) ripple "as-advertised"* consensus model can only be safe if the participants trust is sufficiently overlapping. In spite of requests by myself and several others (E.g. Andrew Miller) Ripple never formalized the topology requirement, much less how users are to go about achieving it. This paper goes forward in formalizing it, but still provides no guidance on achieving it; and absent that the only reliably way I know to achieve it is to have a central authority dictate trust. (*Ripple, as-deployed, centrally administers the "trust"; and Stellar faulted when it failed to do so and switched to a fully centralized approach (at least temporarily))

Consider a trivial example of two fully meshed subgraphs of 100 nodes each with an overlap of a single node. Assuming that each nodes behavior is tolerant to at least one ill behaved node, then both of the subgroups can come to a consensus (achieving at least 99 out of 100) about mutually exclusive state, and this can happen spontaneously without any attacker. More complicated partitioning-- ones involving many nodes in the min-cut, or more than two partitions-- are possible, to avoid it there must be 'sufficient' overlap.

Deciding on what the 'trust' topology must be to achieve safety requires non-local (and presumably private) information about what everyone else in the network trusts. The required minimum set of additional edges to make any particular natural trust topology into a safe one may have no relationship to whom anyone actually finds trustworthy in the real world. As far as I can tell no mechanism is proposed to establish a safe topology; just "the responsibility of each node".

To me that sounds a lot like saying "It is the responsibility of each node to not connect to any faulty nodes." Its a very strong assumption.

Separately, this system proposes a kind of consensus which is weaker with respect to blocking than e.g. Bitcoins. This is perhaps made most obvious by the point at the end about being unable to use the consensus to safely arbitrate global parameters (like system settings or version upgrades), something we do regularly in Bitcoin. It isn't clear to me why the authors believe that the system is fit for cryptocurrency use when it cannot guarantee eventual agreement about _all_ of the state. In Bitcoin the transaction 'light-cone' from coins splitting and merging appears to grow exponentially for most coins, so a failure to reach consensus on one transaction would eventually block most transactions. It's not clear to me if all participants could reliably detect stuck statuses and avoid dependance on them (if they could, why cant consensus continue). I'll need to read more carefully to understand this point.

It's interesting how this suddenly shifts into "journalistic independence" territory - what about who reports on that? What if some influential source would receive some financial aid for proper reporting?