5 ms·

Brief review I did of the paper a while back: Forkable strings (a la Ouroboros) makes unrealistic assumptions. Ouroboros is a Proof-of-Stake altcoin that come

Brief review I did of the paper a while back: Forkable strings (a la Ouroboros) makes unrealistic assumptions. Ouroboros is a Proof-of-Stake altcoin that comes with a security proof based on the idea of "forkable strings". As a brief introduction: each round/epoch consists of a sequence (of length n) of leaders, each chosen from a set of stakeholders, that have the authority to decide between multiple valid branches of a fork. They model this, using a concept they invent called a "forkable string", and prove various security properties about it. The full definition can be read in page 16 of the Ouroboros paper. One key assumption is that they assume all the honest leaders (say, at indexes H = [i], a subsequence of the full sequence [0, 1, ..., n-1]), will only commit to chains that have increasing depth, as i increases. For example, suppose that our sequence of leaders is 5 stakeholders long [s1 ... s5], and stakeholders s2, s3, s5 are honest. Suppose we start off at block O. Then suppose that s2 commits a new block B 2 blocks away from O: O <-- ? <-- B[s2] (The arrows go in the opposite direction in the paper, but I prefer it this way because that is how the references go. ? knows about O, O doesn't know about ?.) Then a "forkable string" assumes that s3 knows about B[s2], and since s3 is honest (as we assumed for our scenario) she will commit her new block C, >2 blocks away from O. Suppose she commits it 3 blocks away: O <-- ? <-- ? <-- C[s3] Then s5 knows about C[s3], and being honest, will commit his new block E, >3 blocks away from O: O <-- ? <-- ? <-- ? [..] <-- E[s5] Using this property (and others) of forkable strings, the authors then go on to prove various security properties about Ouroboros. As you might have noticed already, this property assumes that all honest nodes can reliably receive all other honest nodes' blocks. The paper in fact freely admits this in various places, e.g. on page 10 and page 16. I was already skeptical when reading that, but the fact that this assumption forms such a key requirement of their security proof raised my eyebrow(s) even further. If every honest node can reliably receive all honest nodes' blocks, we don't need any complex leadership selection algorithm nor the idea of forkable strings. Everyone can just sync (union) their view of what blocks they've seen with each other via this magical "reliable channel", and run a deterministic pure algorithm like `sort | head -n1` to disambiguate any forks! The whole point of a maxvalid() algorithm (e.g. PoW in bitcoin) is to secure the case where nodes including honest ones, don't have reliable channels to each other e.g. because they are under attack, or because of pervasive network latency. As soon as you assume they already have a reliable channel to everyone else, you have already "begged the question", and anything you build on top of this (like `sort | head -n1`) is guaranteed to "work". (Another strange thing, is that the authors allow the attacker to selectively show different honest nodes different stuff [1], but for some reason is not able to prevent honest nodes from seeing all other honest nodes' stuff.) [1] e.g. page 17 "the honest player associated with the third slot is shown a chain of length 1 produced by the adversarial player of slot 2" but is unable to see the other (2) node, that eventually forms the ^t chain ("tine").

deleted 9y ago
[deleted]
foobar4123 9y ago
> [1] e.g. page 17 "the honest player associated with the third slot is shown a chain of length 1 produced by the adversarial player of slot 2" but is unable to see the other (2) node, that eventually forms the ^t chain ("tine"). This could be explained by the adversarial player creating two blocks very close to the end of the round during slot 2. If the third player creates his block near the beginning of his round, then he would be unaware of the other (2) node. To your main point: > As you might have noticed already, this property assumes that all honest nodes can reliably receive all other honest nodes' blocks. The paper in fact freely admits this in various places, e.g. on page 10 and page 16. I was already skeptical when reading that, but the fact that this assumption forms such a key requirement of their security proof raised my eyebrow(s) even further. Even in bitcoin, all nodes must eventually be able to communicate with the p2p network (and therefore be able to receive all other nodes' blocks, honest or otherwise). How could you tell if there is a fork, otherwise? The assumptions are explained in page 6, under Diffuse functionality: Additionally, parties can instruct the functionality to diffuse a message, in which case the message will be appended to each party’s incoming string... The adversary, when activated, may also interact with the functionality and is allowed to read all inboxes and all diffuse requests and deliver messages to the inboxes in any order it prefers. In other words, the adversary is allowed to send individual messages to individual parties, but not prevent a party from receiving any other party's message within a round (which corresponds to the time between blocks). An adversary could send a message to a slot leader and perform a DOS attack to prevent him from receiving other messages from other parties, and this seems to be an overlooked attack vector. Although, on the other hand, I'm not sure how the adversary would know which ip address to perform the DOS attack on. Just knowing the stake address wouldn't reveal that information. So unless the adversary has the power to DDOS a large percentage of the network, they couldn't do this. > If every honest node can reliably receive all honest nodes' blocks, we don't need any complex leadership selection algorithm nor the idea of forkable strings. If there is no leadership selection, there is no way to throttle the speed that blocks are received, and the system could simply be DOS'ed by overloading it with blocks. > Everyone can just sync (union) their view of what blocks they've seen with each other via this magical "reliable channel", and run a deterministic pure algorithm like `sort | head -n1` to disambiguate any forks! The point is to prevent long running forks. "sort | head -n1" would work if the branches were all static, but not if an adversary with a large, but not majority stake, saved both branches and then added a block to them, the new longer branch would be preferred. If an adversary could do this, they could create a long standing fork, lasting indefinitely. pg 15 (in the below text, a w of 1 indicates an adversarial node, and a w of 0 indicates an honest node): We start with some intuition on our approach to analyze the protocol. Let w ∈ {0, 1}n be a characteristic string for a sequence of slots S. Consider two observers that (i.) go offline immediately prior to the commencement of S, (ii.) have the same view C 0 of the current chain prior to the commencement of S, and (iii.) come back online at the last slot of S and request an update of their chain. A fundamental concern in our analysis is the possibility that such observers can be presented with a “diverging” view over the sequence S: specifically, the possibility that the adversary can force the two observers to adopt two different chains C 1 , C 2 whose common prefix is C 0 . > The whole point of a maxvalid() algorithm (e.g. PoW in bitcoin) is to secure the case where nodes including honest ones, don't have reliable channels to each other e.g. because they are under attack, or because of pervasive network latency. As soon as you assume they already have a reliable channel to everyone else, you have already "begged the question", and anything you build on top of this (like `sort | head -n1`) is guaranteed to "work". The point of the maxvalid() algorithm is to prevent the doublespend attack. Handling the case where all nodes don't have reliable channels to each other is overkill. You just need to handle cases where some nodes don't have reliable channels.

deleted 9y ago

[deleted]

foobar4123 9y ago

> [1] e.g. page 17 "the honest player associated with the third slot is shown a chain of length 1 produced by the adversarial player of slot 2" but is unable to see the other (2) node, that eventually forms the ^t chain ("tine"). This could be explained by the adversarial player creating two blocks very close to the end of the round during slot 2. If the third player creates his block near the beginning of his round, then he would be unaware of the other (2) node. To your main point: > As you might have noticed already, this property assumes that all honest nodes can reliably receive all other honest nodes' blocks. The paper in fact freely admits this in various places, e.g. on page 10 and page 16. I was already skeptical when reading that, but the fact that this assumption forms such a key requirement of their security proof raised my eyebrow(s) even further. Even in bitcoin, all nodes must eventually be able to communicate with the p2p network (and therefore be able to receive all other nodes' blocks, honest or otherwise). How could you tell if there is a fork, otherwise? The assumptions are explained in page 6, under Diffuse functionality: Additionally, parties can instruct the functionality to diffuse a message, in which case the message will be appended to each party’s incoming string... The adversary, when activated, may also interact with the functionality and is allowed to read all inboxes and all diffuse requests and deliver messages to the inboxes in any order it prefers. In other words, the adversary is allowed to send individual messages to individual parties, but not prevent a party from receiving any other party's message within a round (which corresponds to the time between blocks). An adversary could send a message to a slot leader and perform a DOS attack to prevent him from receiving other messages from other parties, and this seems to be an overlooked attack vector. Although, on the other hand, I'm not sure how the adversary would know which ip address to perform the DOS attack on. Just knowing the stake address wouldn't reveal that information. So unless the adversary has the power to DDOS a large percentage of the network, they couldn't do this. > If every honest node can reliably receive all honest nodes' blocks, we don't need any complex leadership selection algorithm nor the idea of forkable strings. If there is no leadership selection, there is no way to throttle the speed that blocks are received, and the system could simply be DOS'ed by overloading it with blocks. > Everyone can just sync (union) their view of what blocks they've seen with each other via this magical "reliable channel", and run a deterministic pure algorithm like `sort | head -n1` to disambiguate any forks! The point is to prevent long running forks. "sort | head -n1" would work if the branches were all static, but not if an adversary with a large, but not majority stake, saved both branches and then added a block to them, the new longer branch would be preferred. If an adversary could do this, they could create a long standing fork, lasting indefinitely. pg 15 (in the below text, a w of 1 indicates an adversarial node, and a w of 0 indicates an honest node): We start with some intuition on our approach to analyze the protocol. Let w ∈ {0, 1}n be a characteristic string for a sequence of slots S. Consider two observers that (i.) go offline immediately prior to the commencement of S, (ii.) have the same view C 0 of the current chain prior to the commencement of S, and (iii.) come back online at the last slot of S and request an update of their chain. A fundamental concern in our analysis is the possibility that such observers can be presented with a “diverging” view over the sequence S: specifically, the possibility that the adversary can force the two observers to adopt two different chains C 1 , C 2 whose common prefix is C 0 . > The whole point of a maxvalid() algorithm (e.g. PoW in bitcoin) is to secure the case where nodes including honest ones, don't have reliable channels to each other e.g. because they are under attack, or because of pervasive network latency. As soon as you assume they already have a reliable channel to everyone else, you have already "begged the question", and anything you build on top of this (like `sort | head -n1`) is guaranteed to "work". The point of the maxvalid() algorithm is to prevent the doublespend attack. Handling the case where all nodes don't have reliable channels to each other is overkill. You just need to handle cases where some nodes don't have reliable channels.