I am repeating here verbatium what I received from @anonymint in chat, because I don't claim sufficient expertise to judge whether the following is correct or not...
I (@anonymint) quickly read most of the Proof-of-Approval paper. And I’m nearly certain I found the specific flaw.
In a sane world @Traxo wouldn’t have to relay this and make a disclaimer, but this can be (in other threads) at times a very special forum.
Definitive finality is not a function of mere majority or >2/3 but rather a property of the protocol. If the common prefix property of a protocol is probabilistic, then the finality is probabilistic and not definitive.
AFAICT, the probabilistic nature of your design is hidden in an attack on the liveness. Also there’s a synchronization (network synchrony assumption) flaw in the expiration of the slots and epochs.
The flaws in consensus systems can be very subtle. It gets quite tricky to analyze them. It seems to help in the analysis process to have a holistic conceptualization of the two major variations of Byzantine fault tolerance (BFT) which I will also explain below.
I assume this relates to finality. Ouroboros computes its common prefix property on paper's page 37 in theorem 5.2. Its common prefix is "k" with probability 1−(L/R)(CQ+CP+CG+DLS) where each of the factors are defined earlier in the paper. If I remember it correctly, I computed its k at adversarial stake of 25% and 49.5% with parameters from Cardano itself.
The comparison to Ouroboros follows in this post. I think you will see that your design shares the analogous probabilistic finality of Ouroboros. Perhaps when you quantify mathematically the flaw I have described below then you will arrive at analogous equations for your design. Although I haven’t actually dug into the nitty-gritty specifics of Ouroboros because AFAICT I don’t need to. I believe I already understand its strengths and weakness from the conceptual level, as I claim you will see below.
One of the drawbacks of hosting PDF files on Github the PDF can’t be objectively archived with
archive.org. Thus there’s no way to capture snapshots in case the github is deleted or the edit history reverted.
I wish someone could get Github to fix that flaw. In the meantime, I wish PDFs would be alternatively hosted at a url which can be archived.
Section
1.1.1 History or Costless Simulation Attack downplays the plausibility of this quorum busting attack which AFAICT also applies to Proof-of-Approval. AFAICT, your design doesn’t eliminate this attack (c.f. near the end of this post).
I suggest that your paper should acknowledge that the attackers could have been the owners of those private keys from inception of the chain, such as for example how ICO issuers surreptiously buy the ICO from themselves awarding themselves 80+% of the token supply so they can manipulate the exchanges. That is the norm, not the exception. Or bought up at 50 satoshis per token during a cryptowinter. However, in that case you could argue that quorum busting attack is always possible at any time, and I would reply that’s true yet I think the whale oligarchs want to extract maximum rents from the system with more subtly parasitic schemes such as the following.
So selling all for BTC as they pump up the price buying from themselves on exchanges, taking leveraged short positions on exchanges, then attacking to double-spend the tokens back to themselves again which can crater the price driving up the value of their short positions. Then repeat the long-range attack as the price rises anew. Wash-rinse-repeat over and over. Nice corrupt world we live in. (Oh and don’t forget to hire some trolls to pick fights and bribe some mods to chase away those who want to write about the fraud)
Note the percentage of the stake required to attack the quorum depends on the variant of BFT employed. And for the DPoS permissioned variant then that degenerates to the quorum percentage required for electing the set of validators. Thus a DPoS system which requires only
50%+1 of majority to elect the witnesses (aka validators) degenerates from
⅔ quorums required for permissioned validation (without slashing, c.f. below). The
⅔ quorums are required for permissioned validation because alternative blocks are competing with each other due to the lack of slashing of conflicting duplicate votes (again c.f. below for the explanation of slashing). Thus a
50%+1 attack on DPoS elections can double-spent. Actually the DPoS elections are even more vulnerable than that as I explained in the EOS section of
Part 1 of my latest blog.
Section
1.1.3 Nothing at Stake Attack states:
While forking attacks will be opposed by users with a
large amount of stake who will fear to lose their money, if the stake is evenly
distributed among many users, the attack is more likely to succeed.
In a consensus system with a permissionless validator set (i.e. BFT
2f + 1) and thus probabilistic finality, even if they were online at the time of the attack, users have no triangulated objectivity about which fork is the
50%+1 attacker or the “honest” fork. It’s ambiguous. Thus users they have no way to disincentivize fork attacks. A liveness attack is only by censoring blocks and/or transactions, yet the chain always moves forward if there’s at least one functioning validator. Censorship also can’t be objectively proven. Finality of a fork is measured only probabilistically. This is because
it can’t be objectively proven at what time the validator set was entirely counted, because time is relative in blockchains and not absolute (i.e. not objectively triangulated) and permissionless means the validator set is not know a priori before the consensus round.
In a consensus systems with a permissioned validator set (i.e. BFT
3f + 1) and thus 100% probability of finality if the BFT
⅓-1 liveness and
⅔ safety thresholds are not exceeded, users have objectivity about forks but no objectivity about an attack on liveness. If the
⅔ safety threshold is exceeded then there's also no objectivity about forks. Censorship also can’t be objectively proven when the
⅔ safety threshold is exceeded (although it can be proven in some designs below that threshold). Finality is 100% absolute if less then
⅓ of the validator set is dishonest. If the liveness threshold is exceeded and the chain is stuck, it can’t be objectively proven if the validators are intentionally not responding.
@anonymint
explained and discussed this in more detail with @Ix recently.
These are the inviolable ground rules. Any claim which doesn’t obey those rules is presumably incorrect (unless they’ve somehow derived and proven some new mathematical finding in BFT which is probably less likely than being struck by lightning).
Section
2.1 Summary states:
Approvers are allowed to approve as many blocks as they choose as
long as the approved blocks share the same parent. If not, the approvals are
considered conflicting and cannot be used.
Without clock synchronization this is the analogous flaw that I
explained is in Ethereum Casper's slashing conceptualization. The conflicting approval can arrive
at any time in the future. There’s no objectivity about the end of a slot or epoch unless there’s a consensus that makes the epoch final. And 100% finality requires a permissioned validator set and
⅔ quorums. Time is relative in blockchains.
The math of safety requires that (in the absence of a synchronized clock with slashing then) for a slot to be final then the quorum size must be
⅔ of the stake. @monsterer2
would be correct about the lack of safety margin in Proof-of-Approval— if not for the slashing aspect explained below. Without
⅔ quorums, the math is that there’s no safety because the overlap of dishonest validators in two elections is greater than the quorum percentage of
50%+1 and thus the finality is only probabilistic. With
⅔ quorums then the dishonest validators are at most less than
⅓ + ⅓ in any two elections which is less than the quorum size of
⅔. Again I refer readers to go read the derivation of the math which was linked already in this discussion thread already.
If you instead have assumed synchronization with an external clock (which is also a security weakness), then you can slash (delete) stake votes that vote for conflicting forks, but this converts your system to a permissioned validator set (the entire stake) and creates a liveness threshold. The
50%+1 of honest stakeholders are divided to vote on two or more block candidates such that no block attains
50%+1 because the
50%-1 attacker can choose not to vote thus making the chain stuck. If you instead only allow one block proposal per slot, the attacker can try to attack the randomization with stake grinding to always win the block election roll process. If that is proven to be intractable for the attacker (as is apparently the case in Ouroboros and Algorand), the attacker will still cause to
50%-1 of the slots to be empty. Proof-of-Approval thus does not achieve 100% finality within 1 block. So please correct your Medium post which makes that claim in comparison to Ouroboros. And the attacker can attempt to DDoS attack or bribe the roll designated block proposer for each single block for each slot. IOW, single block proposals per slot are a semi-centralized design.
Additionally the presumption of an expiration time for slots and epochs is fundamentally flawed. I (@anonymint under my other usernames such as @iamnotback or @TPTB_need_war) had discussed in 2016 why this is flawed. That discussion took place in either the
decentralization thread or a thread I had
created to brainstorm names for the altcoin I was developing. AFAIR, @monsterer (who is now @monsterer2) and/or @smooth had participated in that discussion. I do not have time to go digging through those long threads to find the specific posts, but from memory I recall that I had explained that there’s no way to triangulate when the end of the slot or epoch exactly occurred. Each node may have a different record of which events in the network were just before and after the expiration. There’s no possible solution, not even increasing the size of the error window that straddles the expiration tie.
Thus the slashing of votes by stake assumed by Proof-of-Approval is fundamentally flawed because it will be ambiguous which were slashed around the time of expiration. I had of course contemplated the design of Proof-of-Approval in 2015 or 2016, but discarded it as being too flawed. This is why I get frustrated w.r.t. the impact on my time (which I need for working on my project) to analyze all these various attempts to fix proof-of-stake, because they always come back to the same flaws that we had already enumerated in 2016. This is why for the past 2–3 years I have said that Vitalik et al are hyping vaporware for Ethereum scaling that can never happen. And why I have said that the DPoS that powers EOS, STEEM, CARDANO, etc can only function as an oligarchy of the stake that (often in obfuscated schemes) extracts maximum rents from the users.
Section
2.2.5 Slot states:
Each party in the network has a roughly synchronized clock that indicates
the current slot. Any discrepancies between the clocks are signifi-
cantly smaller than the length of the time represented by a slot.
This means only users that are live can know which network messages arrived within a slot and it presumes that clock synchronization can’t be attacked. It also presumes that a quorum of users observe roughly the same network synchrony and were live. Those are already notable security weaknesses (potential failure modes) which I think your design shares with Ouroboros.
Section
2.1 Summary states:
When the approvals exceed the required quorum stake, the block creators
broadcast the collected approvals to the network. Creators of the next block
would place these approvals inside the blocks they create.
Thus your consensus system has probabilistic finality analogous to Ouroboros. And unless your design has the cryptographically secure randomization that Ouroboros employs, then your design is not provably secure and is prone to the typical attacks on proof-of-stake such as stake grinding.
The approval stake
stored inside a block also determines the owners of which coin rolls are allowed
to create the next block. For every slot, the block creators build on the
block containing the highest stored approval stake.
I don’t see the cryptographic proof that this is sufficient randomization to avoid all proof-of-stake attacks, especially the stake-grinding attack which causes a proof-of-stake to degenerate into proof-of-work unless an oligarchy of stake is in control. Ouroboros apparently has a formal proof that their cryptographic randomization is complete and secure.
Epoch approvals deter History attacks.
How so? Where's the security proof?
Regarding
Theorem 3.6 your paper states:
Proof. Proof-of-Approval incorporates epoch approvals that are signed testimonials
of the stakeholders for a chain. Since epoch approvals are non-competitive,
provide large award and require little or no computation, all rational stakeholders
would collect this reward and in process, sign their acceptance of the
chain. Even if some parties are temporarily unable to participate due to network
issues, the fork selection process looks at union of all epoch approvers
between the competing forks. As a result, the “real” fork would have epoch
approval from nearly the entire stake and an attacker can win only by exceeding
it in their attack fork.
The long-range attack is a quorum bust (e.g.
50%+1) attack. Thus they can re-sign the epochs they need to. Thus this proof is incorrect.
Theorem 3.7 (Costless Simulation Cost). Acquiring private keys for a Costless
Simulation attack on a Proof-of-Approval chain is likely to cost dramatically
more than acquiring keys representing a simple majority in past.
Earlier in this post I provided two scenarios where the majority of the stake could be obtained for free or nearly free in the past. So why do you necessarily assume the attacker has to obtain them in the present. Proof-of-stake are oligarchy systems. The oligarchy takes ownership and then maximizes the rents extracted.
I didn’t intend to give you a bad day. Hopefully this helps you in some way not to waste time and effort. We can discuss further on Medium if you like where I am not banned. I will probably reply to one of your Medium, so you can respond to me there if you wish. Cheers also. Hopefully we’ll find a good solution for secure, decentralized, scalable consensus systems but physics may force us to pick any two of those three attributes.
