Cardano’s Ouroboros

I’m loathe to attempt to explain in detail the fairly complex Ouroboros consensus system because as noted in follow-up comments that it’s not trivial to quantify, fully characterize, and compare distinct complex dynamic systems with probabilistic eventual consistency (aka eventual 100% finality/irreversibility).

Cardano has roughly the same performance and the same flaws as DFINITY which was covered in Part 3. However note that DFINITY’s actual safety threshold (or is it the liveness threshold?) is at high probabilities only up to roughly 33% instead of 50+% for Ouroboros, although finality is significantly delayed for Ouroboros as the attacker approaches 50%.

Essentially the original Ouroboros also employs (unbias-able?) secure multi-party randomness analogous (but as a shared secret instead of an independently verifiable randomness function) to DFINITY’s random beacon (BLS threshold signature scheme) but the choice “SCRAPE: Scalable Randomness Attested by Public Entities” is much slower and completes every epoch instead of every slot. However this doesn’t necessarily make finality of transactions much delayed compared to DFINITY, although AFAICT the DFINITY whitepaper lacks the rigor to help me analyze the comparison in the non-ideal, adversarial case. The model for attaining and deciding on finality for Ouroboros is different and significantly more complex to explain in the idealized, non-adversarial model than for DFINITY. And I really don’t find any value for non-expert readers in understanding the arcane minutiae. Suffice it to say that both Ouroboros and DFINITY are roughly equivalent in terms of what they offer to users, especially since they all have the “Past Majority Attacks” and other flaws of nothing-at-stake which means they’re (along with all extant non-proof-of-work consensus systems) really only secure as oligarchy clusterfucks. Although perhaps in certain specialized use cases (e.g. specialized private use by banks and not wide deployment to the public Internet) there might be some significant distinction between the two, but I haven’t identified those cases.

Additionally there’s a new variant of Ouroboros named Praos which employs a verifiable randomness function, but AFAICT it doesn’t have the DFINITY’s concept of notarization for witnessing finality (although I’m not sure that makes any quantitative difference because DFINITY didn’t analyze with rigor to quantify its eventual consistency in the non-ideal, adversarial case). Apparently the main improvement of this Praos variant is foiling an adaptive adversary.

Use Cases

I want to make it very clear that as discussed in the comment section, Ouroboros (and I believe also DFINITY) provably provides consensus within the 50+% Byzantine fault tolerance safety threshold and a separate liveness tolerance threshold. They provably solve a specific aspect of the overall set of issues with consensus systems. These systems may already be sufficient for some use cases. We should separate our analysis of these consensus systems from their application to projects that exist in cryptocurrency speculation markets.

So that's dandy minutiae on the provably secure proof-of-stake within the presumed tolerances, except I’m still focused on the following bottom line…

I want to raise a separate point which is the political-economic power vacuum problem when these consensus systems are widely deployed to the Internet such as is the case with the abject failure of Steem. In that case, the presumption that the adversary is not able to exceed the 50+% safety threshold is not a valid assumption for non-proof-of-work systems.

I’m also loathe to expend more effort explaining the nuances of various proof-of-stake consensus systems because they are nonviable for wide deployment to the Internet due to the nothing-at-stake vulnerability which I explained for DFINITY. I recapitulated the summary of this issue in the comment section below.

Thus my opinion on the speculation markets for non-proof-of-work projects is characterized as follows…

More Proof-of-Stake “Shitcoins”

I’m also loathe to expend more effort explaining proof-of-stake consensus systems because they are nonviable for wide deployment to the Internet due to the nothing-at-stake vulnerability which I explained for DFINITY.

These extant proof-of-stake systems only function because an oligarchy is in control milking the users. The oligarchy prevents the “Past Majority Attacks” yet extracts maximum rents in other numerous ways, such as monopolizing the rewards, fees, and doing market price manipulation.

That’s why I won’t waste more of my time analyzing the underlying proof-of-stake consensus component of more “shitcoins” mine-the-speculator FOMO schemes such as:

Ardor’s child-chains, c.f. also.
BurstCoin’s proof-of-capacity.
Decred’s staking, i.e. insecurity of combining proof-of-stake with proof-of-work.
NEM’s proof-of-importance, c.f. also.
Peercoin’s coin age.

Skycoin’s Obelisk

So I guess by accident we save the most intriguing gem amongst extant consensus systems for last.

I haven’t been this intrigued about a consensus system since I read the Byteball whitepaper. I remember telling various friends on bitcointalk.org to buy some Byteball back when the market cap was only $1 million. Unfortunately for me, I couldn’t be bothered with trying to figure out how to get registered on an exchange to buy it at that time because I was preoccupied with the horrific delirium of my chronic illness (c.f. also). Like Byteball, Skycoin’s Obelisk has some warts and problems though.

I had been following Skycoin since 2015 and apparently at that time (or later in 2016 and then gotten confused about the two different whitepapers) only read what I thought to be the original consensus system whitepaper (although it’s dated 2016) which was not worthy of my attention. I think I may have read the June 2015 whitepaper later in 2015 or 2016, but remember it was approximately June 2017 that my health went into a tailspin and by August I was down to 50 kilos in body weight. So given the very intense delirium I was experiencing at that time, I vaguely remember dismissing that June 2015 whitepaper as being culpable to web-of-trust manipulation as I explained in Part 3 for Stellar SCP—and analogous to how the politics of voting is manipulated as I explained about DPoS. At that time in Q3 2015, I apparently didn’t have the mental concentration or energy to either fully understand the whitepaper, or moreover other possible ramifications of it.

Almost Totally Ordered

The June 2015 Skycoin whitepaper summarizes in §2 Related Work: Cryptocurrency on pg. 3 the non-antifragile, potential collapse of web-of-trust in Stellar SCP:

Stellar [32] also use a relationship based solution to resist Sybil attack similar to ours, however, their algorithm has a major defect that it relies on the assumption that for a node, if 80% of its followees agree on a opinion, then 80% of all nodes agrees on the same opinion, but the assumption only stands when a node follows an overwhelming majority of all nodes.

Stellar SCP enforces a total order such there’s no convergence on consensus unless all non-faulty (i.e. non-Byzantine) nodes will have the same correct consensus but apparently that only holds for assumptions about the web-of-trust as quoted above. Whereas, Obelisk forsakes total consensus for an accepted error rate for non-Byzantine nodes that will be fooled into having the incorrect consensus. By allowing for some nodes to be fooled by their inadequate choices of trust, the overall consensus system becomes more robust and it’s much more likely that the rest of the non-Byzantine nodes will not have a catastrophic failure of liveness nor incorrect consensus.

The downside though is that for an “acceptable” 5% error rate, the safety threshold is 87+%. I remember that was one of the reasons I originally thought the design would be unacceptable because it’s possible some small percent of the users won’t have an objective consensus even if they’re always online. I still think that’s a significant problem, but it does put the onus on users to establish reasonably wide and very reliable web-of-trust choices, because they won’t be able to lazily presume they can piggyback on the entire network only converging on a single total order as is the case for Stellar SCP.

So significant error rates will have to accepted if users are making poor trust choices and the adversary is able to garnish more than 13% of the nodes. What I find particularly interesting is that if we relax the error rate to ≤50%, the resistance against an adversary is presumably (and I didn’t compute it) impregnable, although I don’t think such a setting would be useful in the context of being the cryptocurrency consensus system. Even more intriguing in the context of another possible application of the Obelisk concept, is how significantly the math for the safety threshold would improve if some significant percentage of the non-Byzantine nodes are always online observing some synchrony driven truth about consensus about which they’re always unequivocally decided.

IOW, Stellar SCP ties every node’s fate to the fate and trust choices of the other nodes— which has the omnipresent and insoluble failure modes of voting as aforementioned in the context of DPoS. Whereas, Obelisk enables the reliable trust in the network to route away from the unreliable trust and partition the consensus into two competing partial orders. So this is more akin to self-responsibility. All non-Byzantine nodes to some greater extent than Stellar SCP, pay for their own mistakes in choices of trust, instead of causing others to suffer with all their shoelaces tied together in “One for all, all for one.”.

And as described in §9 Discussion and Limitations: Distributed Oracles on pg. 15, fooled nodes can rectify their mistaken trust choices (although not retroactively undo any double-spending losses already suffered as a payee) and semi-objectively (via triangulation of community oracles) move back to what they perceive to be the majority consensus. Although I argued that community oracles can be gamed by an adversary, that wouldn’t be the case if the reliable trust converged with “objective” (i.e. subjective but a triangulated decentralized) majority. IOW, an adversary can fool some of the people (and especially when the adversary controls or bribed centralized trusted community entities such as politicians, foundations, banks, and major companies), some of the time, but not a majority of the decentralized first hand observations all of the time. The partial orders of Obelisk’s web-of-trust theoretically (as modeled and simulated) enables the reliable trust to fork off instead of catastrophic failure and loss of “objectivity”. Nevertheless the currently application of Obelisk as the entire consensus system is not perfect in this regard.

Simulated Annealing

The convergence on consensus propagates somewhat analogously to a the wave in stadium audience crowd. The nodes propagate their best estimates (aka trial guesses) of the consensus and then as these guesses circulate, the nodes continue to refine their guesses and propagate them. So the gradient changes in guesses reduce until an equilibrium is formed. If that equilibrium is a live-lock of repeating oscillation that doesn’t progress or a dead-lock of no change in estimate but for which nodes do not share a consensus, then we can conclude that the consensus diverged instead.

I’m impressed that Obelisk incorporates §5.2 Simulated Annealing Model into the “sky” model variant of mean field theory (MFT) for opinion dynamics. Simulated annealing is how the molecules in slowly cooled ice are able to optimally pack themselves based of small localized gradients allowed because the global temperature gradient is slow. Whereas, if ice is cooled too fast, cracks develop because the molecules weren’t given sufficient time to experiment on random gradients to self-organize the optimal packing.

As Fig. 3 on pg. 10 shows:

The simulated annealing by itself converges too slowly because it is oscillating too much between trial gradients, but when combined in the “sky” model with the more aggressive §5.1 Majority Rule Model (which doesn’t always converge by itself because it’s too aggressive and over-commits thus getting stuck as shown above), the convergence is more optimal as shown above.

No Instant Confirmations

The downside of Obelisk is that consensus convergence requires 10+ rounds. Presumably each round will consume “a few seconds”.

Also I have not reviewed their scalability plans such as sharding if any. But I didn’t also for DFINITY. Nevertheless the slow confirmations remain regardless of any orthogonal work on scalability.

But I would rather have slower confirmations than the oligarchy clusterfucks of extant proof-of-stake systems!

Not Entirely Trustless

Analogous to Stellar SCP, there’s no explicit reward as an incentive mechanism to motivate nodes to be honest and make the wisest web-of-trust choices. However, unlike Stellar SCP unless they’re bribed by an adversary, the non-Byzantine nodes have the implicit incentive to not end up fooled and on the incorrect partial order. And unlike Stellar SCP, Obelisk nodes aren’t required to have their web-of-trust to encompass 80% of nodes, thus trust choices need not exceed the Dunbar limit. Nevertheless, non-Byzantine nodes remain vulnerable to transitivity in failures of web-of-trust.

Disclaimer

I haven’t verified the math, the mean field theory, nor the simulations cited in Skycoin’s whitepaper. It’s not beyond the boundaries of plausibility that it could all be a grand hoax. I’m becoming more suspicious the more I dig in Skycoin’s history. However, the whitepaper is listed on Professor Jiwu Shu’s website. But its so called claim development team is non-existent even though there’s real code and coding activity ongoing on Skycoin’s Github.

The linked webpages and whitepapers cited in this blog have been archived at archive.is and/or archive.org.

Scaling, Decentralization, Security of Distributed Ledgers (part 4)