Does anybody understand Ouroboros?

English Education
1

I’ve noticed POS is taking alot of heat lately all around, and wanted to go deeper, and not just assume it’s all POW sentimentality.

Our whitepaper is a bit much for me (and 99.999% of others I guess), but if our algorithm is provably secure, can someone break it down for me in plain English (complex English is good too :slight_smile: ) how exactly do we get there?

Points that I’ve found raised around the cryptosphere :

  • How does our POS handle network partitioning? Can we ensure that there is always only one valid chain? how?

  • What measures are taken to protect the past? If major holders’ keys are stolen etc. what other measures are taken to protect the chain from being rewritten besides requiring to hold 51%* of stake?

I’m sure there are other issues and would love other members of the forum to raise such.

Also placing a link to an article hailed on reddit which claims the following :

What are those guys missing?

6 Likes
2

As not only you will going to read (and hopefully comment and enrich) this thread, I would recommend reading through this steps of articles/documents, in order to get an idea of the POW/POS drawbacks and challenges

Short overview of both approaches. How they work, on what they rely on, and - probably - describing the point of knowledge and departure when the Cardano project started in 2015

The above article is a recap of this paper who goes more in details and also mentions distributed PoS

The next link is a blog post and an answer to some accusations regarding the Ouroboros PoS approach. It gives some answers to your questions based on the understanding of the challenges mentioned above
https://iohk.io/blog/on-the-ouroboros-design-how-rigour-and-engineering-are-essential-for-critical-infrastructure/

There are also other, more technical/mathematical based challenges like “nothing at stake”

But there are also some philosophical/economical thought as you can read here, basically stating that rich stakeholders get more rich over time.


This will remember you to some other threads here where people ‘discussed’ about different believings and approaches to fund such crypto projects and if the biggest initial coin offerers (whales) could become a security and reliability threat to a PoS based ecosystem.

8 Likes
4

I found this video for a little history.:wink:

5 Likes
5

From what I know about Ouroboros, I can with relative certainty say that out of all attacks described here: Home - Cryptowiki

Not relevant for Ouroboros:

Attack from afar (long range)

In a system with PoS-agreement, an attacker with sufficient computing power can try to build an alternative blockchain, starting with the first unit.

Afaik, cannot be performed in Ouroboros in the same sense, since each slot is already assigned to a specific leader starting with the genesis-block. May be performed only by compromising private keys of known historical slot-leaders.

Why I don’t see it as a problem - this attack is a subtype of a 51% attack, cuz if you have an ability to compromise slot-leader’s private keys you may just compromise >51% of current leaders and do whatever. Compromising only keys of historical leaders (like, some historical block-producers may try to sell their keys afterwards) is not effective, cuz you would not be able to rebuild the current tail of the chain.

Also, as I understand - the Ouroboros’s rule is that node always trusts first version of a block for a specific slot that he has received, so if I get it right: if current chain tail is the block X, and you’re the malicious slot-leader on the X+1 slot - previous leader hands you a chain and you try to replace the whole chain so that it now ends in block X’ and you build on top of it. Well if you broadcast it - previous leader would just reject the whole chain, cuz he already signed and verified the block X and the chain behind it that was already signed by slot-leaders. And so would do all the other nodes that’ve already received block X.

But as I said - long range is a 51% attack in Ouroboros, so if you can build a longer chain - you can just ignore everyone else.

In comparison - Casper FFG tries to solve exactly this problem in Ethereum, and their solution is a set of validators that put on-chain vote for a specific branch each 50 blocks also referencing their own previous vote. So after 100 block chain gets completely finalised and 51% PoW attack cannot rebuild long-range, but rather only after last hard checkpoint (100 blocks). But if I understand it correctly the whole thing can also be easily compromised by stealing private keys of 66% of validators. Because anything in blockchain may be broken by stealing private keys.

Attack by precomputing (grinding)

Not relevant, since Ouroboros uses distributed coin-tossing for randomness. Afaik, you can only affect it (with a point) by compromising 100% of tossing participants, since even if you own 99 out of 100 nodes - the last node will still produce an unpredictable randomness, so grinding is still impossible.

Kinda relevant for Ouroboros:

DoS attack

Sending a large number of “garbage” data node that handles the transaction may complicate its work.

Fees? :slight_smile:

But I don’t really know if and how any network could protect it’s nodes from being DoSed with a bunch of invalid transactions that they still need to process in order to reject. But it seems that it’s still not a protocol issue as described here: How are we going to mitigate DDoS Attacks in Proof of Stake? - Ethereum Stack Exchange

Attack by bribes (short range)

Send transaction to exchange. Receive goods. Bribe some miners to recreate past history and revert the transaction.

Well, again, it seems to be the same issue as with stealing private keys - if you control >51% of slots you may just don’t care what everyone else thinks, but then network would not cost really much )

In more practical sense:

  1. Option 1 would be to try to actually recreate last blocks. This would fail for the reason described above - other nodes would already have a version of a block at slot X, signed by a valid leader for that slot. When they receive new version of the block for the same slot, signed by the same key - they not only ignore it, but they also immediately assume the this leader is compromised, since there’s a proof of double-sign.

  2. Option 2 would be possible if a malicious party control a significant number of slots in a row. In this case they could selectively miss some blocks, to make main chain shorter, and at the same time prepare in background a parallel chain of the greater length where double-spend transaction is executed, and at some point subvert main chain by this fork. A situation like this could easily be explained by honest network problems.

The last option is in my opinion actually the scariest thing that may happen in Ouroboros, but it’s kinda solved by these things:

  1. Attack like this would require a fair bit of preparation, and in the Ouroboros Praos, if I’m not mistaken, slot-leader list is already encrypted (or at least there was a definite plan from IOHK to make it encrypted at some point), so no slot-leader would know ahead of time that he’s controlling a particular block. This would prevent a malicious party from a) knowing that they will have a long-strip of slots under control; and b) knowing which node to corrupt, in order to gain access to a particular slot. The more power malicious party gets - the more chance it has to get a long chunk of slots and to perform a double-spend, so it’s kinda also moves towards a 51% problem that should be solved by honest majority. Also there’s this pic from the Prof. Aggelos’ slides: https://i.imgur.com/HLG3xqo.jpg It shows that a malicious party needs to control at least 40% of all stake in order to have a slightest chance to do anything bad.

  2. Wait for confirmations as described here: https://cardanodocs.com/cardano/transaction-assurance/

  3. Trust latest history even less if there’re visible missing nodes or forks

  4. There actually could be a software solution that would confirm that a transaction was successfully validated by a % of nodes, so the closer this number gets to the 100% - the lower the chance that there could be a double-spend.

I would be really grateful for anyone to guide me to some additional info on how Ouroboros solves this particular last problem.

6 Likes
6

In addition to my previous post. I ignored the classic “Nothing at stake” cuz usually it is described as: “miner may produce multiple blocks simultaneously and either send those to different nodes, or keep some for later in order to perform long-range”.

Short-range and long-range attacks already include nothing-at-stake when discussed in context of stake, cuz with naive PoS algorithm you don’t need to have a 51% of stake to perform long-range.

In Ouroboros classic nothing-at-stake is not relevant for the same main reason - each slot has preassigned block-producer. In this system other nodes may not only verify that block complies with “blockchain rules” (like, referencing the right genesis, not having double-spends, etc), but also may verify that if was produced by valid person.

As the result - after a node have seen a first properly signed block for a particular slot, he afterwards gonna reject any other block for the same slot, and also additionally immediately assume slot-leader to be compromised. Any particular slashing\punishment is not yet confirmed by IOHK (afaik), but it’s not that hard to do, in comparison to some other stuff they deal with :slight_smile:

So even if your malicious party controls a long-enough string of slots, and able to detect it (in encrypted environment), and able to decide to perform an attack - the only actual option for you is to miss some slots, cuz this cannot be proven to be a malicious action (since network connectivity problems may actually regularly cause some short forks).

4 Likes
7

Thanks for the detailed reply :slight_smile:
Always a good sign when somebody writes

Every 5 lines. My turn :wink:

So if I understand correctly, preselection of slot leaders is crucial.
Another important point I feel hasn’t been mentioned is holding stake hostage for a while in order to punish dishonest slot leaders (any ideas how we implement this?)

Not sure I understand exactly what you say about branching, but it’s good to hear we should have ways to deal with network partitioning :smile:

Grazi!

8

Hello, @rin9s! Thank you for continuing this awesome discussion!

Yes, and that’s what allows Ouroboros to really just forget about some possible attacks.

Yes, possible slashing\punishments was mentioned\discussed multiple times, but nothing is confirmed yet (afaik). Ethereum already published some work about provable slashing conditions in their Casper: Minimal Slashing Conditions. Last week Yoichi released a blog post… | by Vitalik Buterin | Medium. Some of those are not applicable (yet) to Ouroboros, and in my understanding main “evil” things to watch out are:

  1. Slot leader signs two blocks of the same height. Easily provable.
  2. Slot leader misses slot completely. Hard to prove malice.
  3. Slot leader submits block in last seconds, so only part of network accepts it. Hard to prove malice.

Some possible slashing conditions in my understanding are (and what I’ve heard Charles speculate about):

  1. Slash stake. May be applied to only certainly provable malice (tho, Casper FFG is proposed to perform slashing for some behaviour that I think is not provable malice) and requires some mechanism to perform automatic on-chain slashing. So would require to lock your stake in some public contract, where coins might be burned without your signature. Afaik, it contradicts Charles’ words about how stake and delegation would work.

  2. Slash presence. Charles mentioned a couple of times that a bad node (not necessarily malicious) may be punished by reducing it’s participation in the network. So, for example, if you miss a lot of slots in one epoch - that could be taken in consideration in slot-leaders selection for the next epoch, and so your node would be punished by reducing the amount of your slots. On one side that could incentivise big pools to DDoS small pools, so they would fail to perform and get slashed. On the other hand, tho, even if we had a relatively small number of stable nodes - that would make chain more safe, than a lot of nodes that miss slots. It sounds kinda sad, but agains - the missing blocks is the main bad thing that can happen, since it may allow for transaction-revert. This is a complex issue, and that’s why Prof. Koutsoupias solves it, and not I :slight_smile:

  3. Slash reputation. If slot-leader is proven to perform a double-sign, idk, I would immediately automatically close it until further investigation, and return all delegated stake back to people, with maybe allowing pool later to explain its actions and later perform a public vote that would allow it to resume it’s functionality. But that’s the easy one. If node does other bad stuff, like misses slots, or delivers late blocks - then it’s “reputation” might be slashed, like there could be a regular automatic report on which nodes\pools performed better in the last month\epoch and which was missing a lot. Basically, that’s exactly why we have voting\delegation, so people could govern this whole thing, and vote out nodes that make them wait for extra confirmations, because of missing blocks.

You may also watch this great presentation from Prof. Koutsoupias, about what thinking and consideration is required to build a system of incentives and disincentives: https://www.youtube.com/watch?v=MeNJoJOgMHU

That’s a thing that Prof. Kiayias explains in this video: https://iohk.io/blog/on-the-ouroboros-design-how-rigour-and-engineering-are-essential-for-critical-infrastructure/

Basic idea is the same as with PoW in bitcoin-mining where two or more miners may produce a block at the same time, and when they start to propagate those blocks to the rest of the network - some nodes receive one block first, and some nodes - the other. This causes the whole network to split into a “fork”, where part of miners are building on top of one tail-block, and the other part is building on top of another tail-block. The longest chain wins in the result.

In Ouroboros forks may happen if slot-leader X does not see the block in slot X-1, but some nodes in the network see it. For example:

  1. Node in slot A created a tail-block and propagated it

  2. Node in slot B received the block A, built on top of it, and propagated

  3. Because of some network issue node in slot C does not see B, but he see A. In the result he assumes that slot B is missed and builds on top of A.

  4. Now node in slot D sees two chains: [A->B] and [A->C]. Both of them have the same length, so he cannot use the “longest chain” rule, and neither of them have a double-sign, so any of them is valid. Now, here, my understanding is kinda splits, because:

    1. I have heard mentions about the “first received block” rule, and I don’t know whether it only applies to the double-sign, or to missing slots also. If node would use the “first received block” rule here - then he will build on top of the [A->B] chain, and so the fact that there was some network problems between B and C - slot C gets missing in the end result, which may seem kinda weird. And additionally it opens a possibility for a “forward short-range” attack, when node B specifically waits for a long before releasing his block, and then sends it to other nodes, but not to the node C, so C thinks B is missing. This problem should be solved by encrypted slot-leaders set that I have mentioned, so B would not be able to know, who exactly is the next leader.

    2. Nodes may be incentivised to wait for the block from immediate preceding slot. In that case leader D would prioritise slot C over B, and so he would build on top of [A->C] chain. On one hand - it produces a chain where slot B is missing, which may be right, cause slot-leader B could have been waiting too long to produce a block. But on the other hand, it is impossible to prove, that node C really did not see block B. In reality he just may want to perform a short-range attack, so he receives [A->B] chain, ignores B, builds on top of A, and then just says that he didn’t receive B. This type of attack is more possible than “forward short-range” so this options is probably will not be implemented.

    3. There’s an additional issue of time. Each slot needs to produce and to propagate a block in it’s slot time (20 seconds for now, and may be shorter later). There’s always a possibility that a node would not be able to produce or (more often) propagate a block in that time, so other nodes would receive it too late. There ought to be a mechanism for nodes to decide, whether a block is produced in time or not. For example there is possible scenario in which node B produces a block on the 19th seconds of his slot and then tries to propagate it. Node C does not receive block B in time and builds on top of block A, but while he’s doing it - node D receives block B. Is there a verifiable mechanism for him to decide, whether B was produced in valid time, or was it too late? And should it count as valid at all, to produce a block on the 19th second of a slot?

Once more that shows what a complex issue it really is to come up with a system that would more or less “fairly” resolve any forks. In my best try I may assume that the rules are as follows:

  1. Each node counts down each slot. So like, slot X starts… count 20 seconds… slot X closes.
  2. If node receives block X in that window - it gets accepted. If node receives block X even 1 second later - it gets rejected as too late. Node assumes locally that valid chain is X-1.
  3. Then node proceeds to count slot X+1 in the same manner. And in if it receives a block in this period, it would check one of two thinks: it’s either built on top of X-1 (valid local tail), or it’s build on top of a block that’s build on top of X-1.
  4. So new chain might include a block for a latest slot that local node was considering as missing, but in any case it MUST be build in top of the same block in X-1, cuz this block was already validly signed.

That’s where the “longest chain” rules comes in play.

3 Likes
9

This sounds right. First block logic is problematic in this case.

The punitive hirarchy you describe makes sense -
slash rep → slash participation → slash stake
with some offenses going straight to hard punishments.

Not sure that’s a privilege we have… The algorithm is the only real arbitrator we can afford, no?
Auto-release of stake is also very problematic from a legal standpoint, intervening in contracts between pool and stakeholder…

Thank you so much for putting in the time to educate the rest of us, I think I’ll go delve into Prof. Koutsoupias’ work a little :wink:

2 Likes
10

No, my final idea was that first-block logic is exactly the right way, despite all the tradeoffs. If node D did see block B in right time-slot, and then he receives chain [A->C] from node C - he ignores the latter and builds on top of the former, and C gets missing from the final chain. It seems harsh to punish C for network problems between him and B, but I think the main idea is that the whole thing is a gossip-network, so you’re not only talking with preceding node, and if majority of nodes have received B successfully, and you didn’t - it might be your problem.

This is in my limited understanding. And I’m super-hyped to see what solutions IOHK will propose in the end.

Well, yeah… but it seem kinda harsh to just shut the whole pool down immediately :slight_smile:

By “further investigation” I mostly meant just that pool gets immediately automatically banned, with no right to sign any more blocks, and a public vote have a right to revoke the ban. So the pool could submit a vote-request with their explanation on why exactly this could happen, and then other members of the network could provide a “review” on that explanation.

Idk, just starting to speculate on the whole idea of governance :slight_smile:

Yeah, but as a part of any public pool contract there could be the default condition that if pool gets banned - the whole stake is automatically revoked. Tho, I agree that it could cause problems with a cold stake, where people just stake their stash and forget about it for many years, but then they find out that pool was banned and then unbanned, but their stake was revoked and never returned back to the pool, so they lost profits. So maybe there just could be an instant notification to all delegates that their pool is banned, so their stake is not in the game anymore, but they have the whole right to re-delegate it.

3 Likes
11

A little addition, is that (as I described above, but kinda scattered the whole idea) in encrypted environment:

  1. Node C can maliciously ignore block B
  2. Node B cannot maliciously censor specifically node C from receiving block B

So just that fact makes “first received chain” rule more appropriate.

2 Likes
12

Wanted to add something about double-sign provability. If my node already stores a local chain C that contains block B in slot S and ends in tail-block T in slot TS. Then I receive new chain C’ that ends in slot TS+1 but isn’t built on top of the block T.

Axiom: any two chains that refer the same genesis must have a single block P that is the last common “parent” of both chains. And the block P is >= the genesis.

In this case there are two possibilities:

  1. New received chain is valid fork and does not contain any double-sign. In that case - for each block in C’ that are > P there must be an empty slot in C. In that case C’ is a valid chain and then chain with max(len(C), len(C')) is retained as local.

  2. New received chain contains a block B’ in slot S that is > P and not equal to block B in chain C, but yet is a valid block in itself (validly signed). In that case chain C’ is not a valid chain. Block B was received by me earlier, so I reject block B’ and chain C’ consequently.

The problem now is that in the seconds case I have the hard proof that slot-leader S produced at least two signed blocks of the same height, but also block B’ is not included in the retained chain C, so everyone else will not see it. And this might be solved by addition of a special transaction type:

MultiSignProofTx = (
  slot : Number,
  author : NodeAddress,
  witness : NodeAddress,
  proof : List[BlockSignature]
)

Where:

  1. slot = height of the double-signed blocks (the same as global number of the slot)
  2. author = address of the blamed node who signed multiple blocks (slot leader S)
  3. witness = address of my node, who witnessed the multi-sign (basically, my signature)
  4. proof = the duplicate block-signatures of the slot-leader S for the blocks B and B’

The main problem here if, of course, with the “proof” signature. It must provide these properties:

  1. Definitely proves that it’s signed by S
  2. Definitely proves that it was blocks for the same slot
  3. Cannot be forged by any other node

Unfortunately, for now, I cannot say with certainty, whether there’s already a part of a standard block in Cardano SL that may be used as this small provable signature (still learning the system), but I will try to speculate that for at least one reason known to me - block in Cardano SL must include the global slot identifier (pair [epoch, slot]).

So the structure of a block may allow us to have an encrypted message that:

  1. Includes global slot identifier
  2. Signed by a block-creator (and may be verified)

So the mere existence of two messages like this, that would contain the same slot ID and are verifiably signed by the same key - is enough proof of a double-sign.

So when my node detects that other chain contains different blocks for the slots in which local valid chain already have valid blocks - it creates a proof-transaction for each pair of valid-invalid blocks and sends it to the network.

The next slot-leader that have received these transactions - includes them into the main chain. And so now any node when receiving a block from a slot-leader S may verify that there’s an existing proof on the chain and reject the block for the reason of the slot-leader being banned.

1 Like
13

There’s another possibility - my local chain C may contain an empty slot S, but then I’m receiving a chain C’ where there’s a block B’ in the slot S. The chain C’ is valid, but shorter - so I ignore id. But then I receive a chain C’’ where there’ a block B’’ in the same slot S and B’ != B’'.

In this case - there’s no block in the main live chain C, but the double-sign still can be proven just by existence of two verifiably signed messages. The only problem is that my node could ignored the block B’ in the first received chain C’, and not remember about it when C’’ is received.

But this problem might be solved by additional rule - that node must additionally store all received blocks for the missed slots off-chain, so that if double-sign for the same block is ever received - it could be proven.

I don’t know if actual Cardano SL nodes perform the double-spend proof described in previous post, but I also don’t know why wouldn’t they.

The case described in this post is, of course, a weird one, and there’s like a one in a million chance that stuff like this could happen, so I can’t seriously estimate the need to implement stuff like this. Also it would depend on the retaining of all the same nodes in the system. I mean if your nodes store off-chain blocks, and then your gradually “restart” the network (for each closed node - one new fresh node appears, until no old nodes are retained) - then this off-chain data is lost anyways :slight_smile:

14

Here, I found best explanation of Ouroboros POS algorithm.

1 Like