Hacker News new | past | comments | ask | show | jobs | submit login
Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol [pdf] (2019) (iacr.org)
90 points by dgellow 33 days ago | hide | past | favorite | 70 comments



Proof of Stake not only replicates the same dynamics that Bitcoin was designed to eliminate (more wealth -> more power in system) but also can only be made secure against a maximum of ⅓ byzantine actors, compared to Proof of Work's superior ½.

As for using it for Layer 1 systems, Andrew Poelstra nailed it in his conclusion [0]:

"We showed that by depending only on resources within the system, proof of stake cannot be used to form a distributed consensus, since it depends on the very history it is trying to form to enforce loss of value."

Proof of Stake might be useful at Layer 2 (becoming equivalent to voting stock in a company), but not as a base-layer consensus mechanism.

[0]: https://download.wpsoftware.net/bitcoin/pos.pdf


There's a couple things wrong here:

> Proof of Stake not only replicates the same dynamics that Bitcoin was designed to eliminate (more wealth -> more power in system)

There is no legitimate sense in which PoS _is_ an instance of "rich have more power and get richer" but PoW is not. In fact, PoW is _worse_ than PoS in this regard, because PoW has economies of scale (if someone with a $100k investment earns $10k/year, someone with a $100m investment can earn significantly more than $10m/year). PoS on the other hand is much closer to a clean "what you earn is proportional to what you put in" design, which is realistically the best that you can do in an anonymous system where users can generate as many independent identities as they want.

> can only be made secure against a maximum of ⅓ byzantine actors, compared to Proof of Work's superior ½.

This is also not true. The 1/3 bound is for safety-under-asynchrony (a form of safety for which PoW's security margin is zero). If you assume synchrony, then PoS protocols' safety approaches 50% much like PoW does. Protocols like Casper FFG combine the "best of both worlds", giving you both of those security guarantees (50% BFT if the network is good, 33% BFT if the network is terrible) at the same time.


> There is no legitimate sense in which PoS _is_ an instance of "rich have more power and get richer" but PoW is not.

In PoW, miners must sell their tokens to buy capital-intensive mining equipment and power to stay competitive. In PoS, stakers have no incentive to sell enough tokens to anyone who could turn around and stake them as a competitor, since that would cut into the seller's future staking rewards.

> The 1/3 bound is for safety-under-asynchrony (a form of safety for which PoW's security margin is zero). If you assume synchrony, then PoS protocols' safety approaches 50% much like PoW does.

First, consensus protocols can be trivially safe regardless of the network's behavior -- you simply require a majority vote for any proposed agreement. Second, any consensus protocol can only remain live as long as there are no more than f faults out of 3f+1 replicas. This is again irrespective of the network model -- Leslie Lamport's proofs do not make any assumptions about the network.


> Second, any consensus protocol can only remain live as long as there are no more than f faults out of 3f+1 replicas. This is again irrespective of the network model

We actually know of consensus protocols that require synchrony including between participants and clients that go up to 99% fault tolerance for both liveness and safety; in fact Lamport himself described one in his original paper (remember that it's "written messages" and not "oral messages" in his vocab that's the relevant category; these days public key cryptography is cheap and uncontroversial so there's no need to care about the "oral" case). There's also a table on page 291 in the 1988 DLS paper (see https://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf, the "authenticated byzantine" row and the "synchronous" column) that gives an overview of the fault tolerance levels in various different cases.

The original definition of consensus did not have a notion of passive clients needing to learn the result, so the "active participants synchronous, passive clients asynchronous" model common in blockchain land was not really analyzed well back then. It turns out that with a synchronous network, the passive client requirement is what brings safety and liveness down from 99% to 50%. And it also happens that the 50% fault tolerance protocols are less fragile in the case that the synchrony assumption breaks temporarily.


> We actually know of consensus protocols that require synchrony including between participants and clients that go up to 99% fault tolerance for both liveness and safety; in fact Lamport himself described one in his original paper (remember that it's "written messages" and not "oral messages" in his vocab that's the relevant category; these days public key cryptography is cheap and uncontroversial so there's no need to care about the "oral" case)

The "written messages" protocol does not tell the whole story. If you go back and re-read Lamport '82 [1], the assumptions that make the SM(m) algorithm ("written messages") work at all also make it a practically useless result. In particular, assumption A4(b) (top of page 391) requires that anyone can authenticate any general's messages at all times. How the generals are supposed to learn each other's public keys _without_ an instance of SM(m) is not addressed, but presumably they would need to fall back to OM(m) ("oral messages") to do so. So if you take a BFT system as a whole, where you can't assume the existence of a magical fool-proof way for generals to learn each other's keys a priori, my original claim stands.

> The original definition of consensus did not have a notion of passive clients needing to learn the result, so the "active participants synchronous, passive clients asynchronous" model common in blockchain land was not really analyzed well back then.

Prior literature doesn't consider "passive clients" because they're not protocol participants in the first place. Clients do not participate in deciding agreement; otherwise they wouldn't be called clients.

Last I checked this is very much still the case in blockchain-land. Your wallet (client) does not do anything to help miners/stakers determine the best chain tip or the next block, for example.

So, I'm not sure what you're trying to say here?

> It turns out that with a synchronous network, the passive client requirement is what brings safety and liveness down from 99% to 50%. And it also happens that the 50% fault tolerance protocols are less fragile in the case that the synchrony assumption breaks temporarily.

Unless you're assuming the existence of the magic fool-proof public-key distribution mechanism required for SM(m) to work, you're not going to get liveness unless you're either (a) assuming nodes do not exhibit arbitrary failure modes, or (b) requiring at least 2/3+e nodes are honest.

[1] https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf

EDIT: wrong date for Lamport


Oooh. Its the man himself!

Curious about what you think about ourboros/cardano! Pros cons vs eth?


When I last looked at Ouroboros it still had the property that there's only "one confirmation per slot", so you need to wait ~log(n) slots before an attacker has a <1/n probability of reversing the chain. I personally think that a good PoS system should strive to have hundreds of confirmations per slot the way eth2's LMD GHOST does. That said, it's very possible that there's an improved version of Ouroboros that already does this and I just haven't caught up to it yet.


Is it realistic, assuming a heterogenous network the Internet, for having high percentage of block dissemination and 100 confirmations in almost every node in 12 seconds (and how many peer connections are assumed per node?) Would not that segment the network? Sorry, I am just asking as I have no knowledge how ETH 2.0 and its LMD GHOST works.


Hey Vitalik, looking to really get into the weeds of blockchain like you. There seems to be a barrier between new folks and engaging fully in learning material. Just too much of a learning curve, got my hands on everything I could find but am now stuck, where do you suggest I find the most information on especially the math behind it all?


FYI - this is the founder of Ethereum


Sorry, but for me, there are no idols and gods exist, but simply fallible humans, with no exception.


Not sure if you are claiming that BTC currently solves the "more wealth -> more power in system" problem but it clearly doesn't. The current state of affairs is more wealth -> more ASICS R&D and infrastructure budget -> more hash power -> more power in the system.


There's a difference. You can't physically centralize energy production. Local energy price will increase when more energy is used. This ensures that no one can get in a position of control. In PoS, it's possible to get > 50% ownership, and it's game over.


Aren't 65% of all bitcoin miners in China? Couldn't the CCP sabotage the network at any time? Say, a month before the launch of their digital currency?

https://cbeci.org/mining_map


This specific visualization is limited to 37% of the hash power on the network. It's possible that it is a representative sample, but I don't think we can assume that.


Even better, it is limited to pools that primarily operate in China. I really wish someone would turn off that link. It is really awkwardly bad and mis-quoted a lot.


With proof of work you have economy of scale working in your favor. You'll get different deals on asic, power, server farms, etc. the more you buy.

PoW by design leads to centralization and we can see it happening live with bitcoin mining. At least with proof of stake there's no economy of scale. Everyone can participate fairly easily.


> You can't physically centralize energy production.

But you can centralize ownership of energy production.


Is 70% of Bitcoin mining still in China?


Does it matter? As long as there is enough mining that isn't controlled by a single entity (mining in China isn't a single entity), then the network is secure.


That is true, but its easy to centralize private ASIC designs or in a more extreme case the underlying chip fabs. If TSMC wanted to control the Bitcoin network they'd have a fair shot given they have by far and away the best fabrication technology for high performance chips


You hit the nail on the head.

TSMC, Samsung and GlobalFoundries are the centralization points of all of mining because they produce the chips.

Good thing they like money and they are global corporations.


This doesn't work for ETH1, which is PoW, but memory hard, which ties the network to GPUs over ASICs due to the cost structure of producing ASICs. It is cheaper to buy an off the shelf GPU than it is to buy an ASIC.

You also have to factor in the fact that the latest GPUs are not necessarily the best ROI. If you can get lower speed GPUs for a fraction of the cost, then your return on that is much faster. Of course, that is starting to change now that mining is becoming so profitable again. But regardless, you are still tied to GPUs, so anything you can get there is good.


> It is cheaper to buy an off the shelf GPU than it is to buy an ASIC.

Ahh I guess all the people making/buying ETH mining ASICs must be out of their minds then? First result I found: https://www.coindesk.com/linzhi-rollout-long-awaited-ethereu...


You know how much that costs? I specifically mentioned ROI.

If you did the research into that one, it also only has 4.4gigs of ram. It will also slow down (aka: zombie mode) starting early November 2021 once the DAG gets large enough.

https://minerstat.com/dag-size-calculator

It takes about an hour of running it, just to start mining because the DAG generation takes so long.

By the way, Linzhi only sells to large customers because they've taken so long to produce this thing (years now) that they don't have enough money to front the production run.

They are also a super sketchy company. You should have seen the stuff they pulled during the ProgPoW debate.

Disclosure: I'm a very very large GPU miner and I'm deeply involved in this business.


Matthew principle strikes again.


The Ouroboros paper seems to say that it is 50% resistant. See the parts highlighted here and the additional comments in this forum thread: https://forum.cardano.org/t/is-cardano-51-attack-resistant/1....


> only be made secure against a maximum of ⅓ byzantine actors

What is the threat model here, and in particular what is the outcome of a successful attack?

For example, if the only "power in the system" the attacker has is the ability to prevent transactions from occurring, then the attacker is damaging the value of their own coins. The honest majority could, as a last resort, also decide to manually fork the currency to invalidate the attacker's coins.

Assuming the ⅓ number is weighted by stake, the attacker is potentially risking billions of dollars in order to carry out this short-term attack. With that amount of money it would be cheaper to locate and destroy the major bitcoin mining farms.


There are concerns (or concern trolls) about an attacker buying old keys for almost nothing, trashing the chain, then profiting by shorting. And there are concerns that the honest majority can't figure out how to switch to the honest fork.


>And there are concerns that the honest majority can't figure out how to switch to the honest fork.

If that's always an option why bother with proof of stake in the first place? Just let it do whatever and switch to the "correct" fork once in a while!


Why not have the Supreme Court resolve every dispute? Because it's too expensive. Ultimately you can't exempt yourself from the judgement of society and the market. If you commit to a "most-work chain wins no matter what" policy it doesn't mean that chain will win economically.


That's why there are KES keys.


For people like me who haven't heard of this feature: https://docs.cardano.org/projects/cardano-node/en/latest/sta... It's true that this prevents an attacker from using current keys to perform a long-range attack but old keys can still be used for attacks.


Afaik, long range attack is eliminated by bootstrapping from genesis, where the densest chain is selected.


> Proof of Stake not only replicates the same dynamics that Bitcoin was designed to eliminate (more wealth -> more power in system)

Bitcoin may have been _aimed_ at eliminating the "rich get richer" system, but in fact it failed at it, as others comment below. It has been formally shown [1] that investors who have enough money to buy the most efficient ASICs out there earn disproportionately more, compared to smaller investors who can only afford less efficient ASICs/GPUs; in contrast, in PoS every investor has a fixed ROI for each one of their $ (regardless of their total investment); as also shown in that paper, this is the best you can hope for in an anonymous system. In other words, unless you can authenticate users and distribute rewards in a democratic (and possibly egalitarian) manner, the rich will always get richer, and the rate with which this happens is actually worse in PoW than PoS.

[1] https://arxiv.org/pdf/1907.02434.pdf


It's true that PoS requires subjectivity to prevent long-range attacks, but everyone is already using subjectivity so this is not an additional constraint. (People say that, in theory, new users might not use subjectivity in PoW but this is not actually true in practice.)


Fundamentally Proof-of-Work relies on the laws of thermodynamics and mathematics to secure the network.

Fundamentally Proof-of-Stake relies on a high-level abstract game theory of social interactions between selfish players.

One of these is not like the other.


wmf's snarky comment aside, I think there is something important here. What's the big markets story this week and last? A bunch of people intentionally acting "irrationally" fuelled by their spite. How much "smash the system" energy can PoS systems accept?


Yep, one's destroying the planet and the other isn't.


What is your point? One wrote something 5-years ago, when Ouroborus was not even invented at all, does it mean is it still hold?

Or do you want to believe that's still true because it would be very inconvenient to your biases (we all have our own biases) otherwise?

Sorry, I really did not want to be rude, just tried to find out whether you're trying to seek for the truth or just want to be right.


No distributed consensus algorithm can tolerate more than f faults with 3f+1 replicas and maintain liveness. This includes Bitcoin (replace "replicas" with "hashes per unit time").


Check out Polkadot - They NPOS system works and not how you described.


I wasn't familiar with Polkadot, but this documentation page seems to be a good introduction to how its "Nominated Proof-of-Stake" system works:

https://wiki.polkadot.network/docs/en/learn-staking


was this submitted to any crypto journals for peer review (CCS, Eurocrypt) or did the author arrive at this conclusion in isolation?


Ouroboros Genesis ? Yes : CCS 2018.


Important paper here because almost all the next gen blockchains will be using POS. Ethereum is trying to switch mid-flight (yikes) but others like Cardano have incorporated it foundationally.

If you're a no-coiner or Bitcoin maximalist, none of this really matters. But if you accept the premise that the future of financial infrastructure is moving towards decentralized, blockchain based systems, then a secure, scalable, performant, and energy efficient approach like this is pretty darn awesome.


Ethereum's PoS is a completely new chain that's currently running in parallel. After watching it run in production for about a year they'll merge in the old chain.


What is running in parallel is just a heartbeat chain that doesn't do anything of what ETH1 does (no EVM).

It will be much longer than a year. 2-3, at best.


Yes but what's running now is the hard part. Fundamentally, once you have reliable consensus, the data you reach consensus on is just an extra hash in each block.

There's software engineering to merge the client software, but from a research perspective it's not a big deal at all.


The hard part? Oh god no. Not even close. Have you seen V's roadmap? [0]

One major hard part, imho, is the zkSNARKs. Nobody is talking about the fact that they are hardware dependent because they are so computationally expensive. My guess right now is that we're going to need (or they will get developed some how)... ASIC's. Talk about kicking the puck down the road.

The other hard part is that this is a decentralized development project managed by humans. What happens when someone wants to flip the switch on billions of value? The ProgPoW debate proved how contentious decisions turn into a total clusterf*ck. You want to trust your funds to that?

Finally, the best one. There is insane pressure to rush eth2 out now that billions of value is locked up. 737 max levels of pressure.

I love ETH and ETH2. More than anything I want to see it happen. I'm just in the camp that we should have worked on ETH 1.5 first.

[0] https://twitter.com/VitalikButerin/status/133392262085774540...


Yes I've seen the roadmap. Pay attention to the arrows; there are just two items before the merge, both partly complete. Neither involves zksnarks, which are only mentioned in the roadmap under "advanced research," which is meant to follow the full ETH2 rollout. (However, zksnark-based layer-2 systems are in production already.)

I'm not worried about the social aspects at all, but in the context of an Ouroboros discussion I don't really want to get into a broad Ethereum debate.


> Ethereum is trying to switch mid-flight (yikes) but others like Cardano have incorporated it foundationally.

Why yikes? If its a legacy transition, with a flight plan and testing, then it should be fine.


Well, as one example, what happens to all the miners and their infrastructure? Seems like they get hung out to dry.

Second, the technical complexity involved seems challenging. I'm not a dev, and I'm not saying it's impossible, but making substantial core changes on a live, decentralized system running all sort of layer two infrastructure seems really dicey.


As a very large GPU miner, I'm excited for ETH2. The hardware investment can be sold off, used for other chains (with ETH1 gone, another chain will take its place as the dominant GPU chain), there is also all the upcoming fields of ai/ml/rendering/gaming and other computationally intensive workloads.

This is really the beauty of ethash being asic resistant and gpu friendly. I have so much computational power built up, that someone will always be available to buy it. It isn't e-waste. We already run on older generation GPU's because they are higher ROI, which proves that they have useful life, even as they age.


The whole project is a technical beast. I think blockchain related topics don't get much attention here. Glad to see the paper on the front page.


You may also want to see this video from 2018 where the paper is presented by Christian Badertscher: https://www.youtube.com/watch?v=TCA0h73q3qQ&list=PLnPTB0CuBO...


Unfortunately, the introduction of the presentation took too much time, so the novel part of the presentation is very hand-wavy.


How does this compare to the current implementation of proof of stake in Ethereum 2.0?


They claim (via formal verification, I cannot speak to their threat model with much accuracy) that they are able to achieve the same or better security properties as ETH 2.0 without lockups (staked funds earning income are like demand deposits) or slashing (penalties for bad behavior / bad network performance).

The project as a whole (Cardano) has some other notable advantages. Personally, it has a built in governance system which actively funds projects / improvement proposals paid for by some of the block rewards & fees. Cardano just had their first round of voting and funding which gave in aggregate $250k to a variety of projects [0]. Funding batch sizes are expected to grow to $10 million dollars a year in 2021 (at current prices). This is where I'd draw the largest difference between ETH 2.0 and Cardano (the project which developed and uses Ouroboros)

[0] https://iohk.io/en/blog/posts/2021/01/12/project-catalyst-th...


Without slashing, I'm wondering whether they've adequately accounted for attacks motivated by extraneous factors, rather than simply for profit within the system. The abstract says "we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium," but does that still hold if an attacker has shorted the coin?

With slashing, even if someone finds it advantageous to attack, you quickly take away their ability to attack.

(I haven't yet read past the abstract, so for all I know they do address this.)


It is much more complicated. First, Cardano use in-house built pull based network layer, so the attacker cannot exhaust your node even cannot do some resource attack against it, and even if some attacker is connected to your node and do some nasty stuff that causes protocol violation, it is just simply discomnected and dropped out of the 1000 cold list of other nodes in the aueue, and needs to wait a lot of time to rebuild its reputation. Anyway, it is very complex with a lot of mitigations of these kind of attacks. Secondly, you need money lot of money and bribe almost 500 pools (assuming nash) to be successfully alter the chain, it is like bribe 500 bitcoin miner pool from a theoretical 1000 evenly distributed hashpowers bitcoin miners/pools.


Admittedly I skimmed the paper but didn’t see any comparison with state of the art. How does this differ from Tezos’ implementation?



Thank you!


While Cardano is interesting, I believe IOTA's implementation of a ledger using a directed acyclic graph is much more interesting/scalable.

In addition IOTA's focus on micro-transactions / the machine economy seems like a no brainer and something that cryptocurrencies generally neglect..


Has IOTA gotten rid of its centralized server that 'approves' transactions?

Have they figured out how to stop spamming from making the network unusable?


Lol.

IOTA is a scam.


I have the tingling feeling that one could think of a better name for a blockchain protocol.


It's a great name because PoS doesn't require using outside resources (e.g. energy). Once the system gets going it secures itself.


craig wright is NOT satoshi nakamoto




Applications are open for YC Summer 2021

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

Search: