 Show Posts
|
|
Pages: « 1 [2] 3 4 5 »
|
Hello Traxo and @anonymint, I must admit that language and writing have never been my forte and the paper can benefit from improved writing  . And I do appreciate your writing of the alternate summary + explanation which would definitely help. Good summary of approval process in PoA:If we can guarantee that all honest approvers will always vote on the same fork (i.e. never vote for candidate blocks with different parents), then at any quorum approval threshold choice above 50%, then assuming the attacker possesses less approval control than the threshold, a conflicting block can’t be produced which ends up with a higher approval at any time in the future. Thus for a 50%+1 quorum, the attacker must possess at least 50%+1 approval control in order to slash 25%+1 with conflicting approvals and approve of the attacking block with attacker’s remaining 25%. In that case, the double-spent block has 25%-1 of the remaining 75%-1 total approval and the attackers winning block has 25% of that 75%-1 total approval. There can’t exist another block that has a higher approval because the attacker controls 50%+1 which was expended. Increasing the quorum threshold above 50% increases the safety because the attacker will need to control more than the threshold, but it reduces the liveness. For example a 80%+1 quorum, the attacker must possess at least 80%+1 approval control in order to slash 70%+1 with conflicting approvals and approve of the attacking block with attacker’s remaining 10%. In that case, the double-spent block has 10%-1 of the remaining 30%-1 total approval and the attackers block has 10% of that 30%-1 total approval. Liveness is maximized at the 50% quorum threshold because up to 50%-1 of the control can be non-responding. The incentive mechanism in PoA posits to disincentivize honest approvers from choosing from candidate blocks with different parents. The choice of parent block is apparently dictated by network synchrony in that the live nodes will tend to have a Schelling point around approving all candidate blocks with the parent being the last approved block they saw that had met the quorum threshold. Presuming the slot interval expiration time is much larger than typical time to approve a block, then all or nearly all live nodes should have the same Schelling point choice for parent block. The tie breaker rules in Section 2.2.22 Approval Tie-Breaking Procedure A(·) are employed so that multiple competing approved blocks in a slot have only one Schelling point parent block. The network synchrony assumption and Schelling point appear to maybe be what differentiates the incentive mechanism in PoA from Byteball’s 100% asynchronous incentive mechanism which allows Byteball to get stuck with competing witness groups even with no 50%+1 attacker. Also I need more study to determine if Byteball could ameloriate additional posited vulnerabilities when the quorum threshold is greater than 50%+1. It was originally (earlier in this thread) my lack of holistic understanding of this PoA incentive mechanism and Schelling point that caused me to believe PoA would also need ⅔ quorums for 100% finality. Same as for Nakamoto proof-of-work, there’s no Schelling point nor Nash Equilibrium in PoA if the attacker has more than the 50% threshold control. PoA’s rules of conflicting approvals force the honest nodes to accept the attacker’s fork because the attacker records the conflicting approvals in his block that orphans the conflicting block(s). Even the attacker can’t bribe by eliding conflicting approvals of those approvers who defect to his block, because the honest conflicting block will contain the objective evidence of those signed conflicting approvals, which any node can verify thus objectively choosing the honest block as the winner (that is unless the attacker has the sufficient 50%+1 control, in which case the attacker doesn’t need to elide the conflicting approvals). The 100% finality after one block is dependent on the attacker not having 50%+1 control of live stake.
Correction, the assumption is that attacker has <50% (more accurately <(ρ − δ − νc − νa − νe)) of the total stake. The 100% finality after one block is dependent on the attacker not having 50%+1 control of live stake. Additionally, not only can live stake be much less than total stake of the money supply, but I earlier in this thread pointed out reasons that stake can be nearly cost-free to obtain and attack with. Also @monsterer2 has pointed out that unlike proof-of-work which burns external resources, it costs nearly nothing ongoing to sustain a 50%+1 stake attack (other than the opportunity cost of holding that stake but the attacker can offset that cost with profits due to attacking, such as taking all the newly minted money supply rewards, double-spending, and/or shorting the token on exchange).
Thus it is disingenuous to compare this claimed one block 100% finality to Nakatomo proof-of-work probabilistic finality. In essense, the finality of PoA is either fragile or dependent on a benevolent attacker (oligarchy) which collects parastic rents in ways other than double-spending. For example, DPoS has elections for the delegate witnesses and to set their compensation. An oligarchy controls the elections and can extract the maximum rents the system can bear. And STEEM (running DPoS) and PoA can enable an oligarchy domination of the newly minted money supply. A 50%+1 attacker in PoA need not double-spend, he can just make sure he only includes his own approvers in blocks so that he takes all the minted tokens for the coin rolls consensus process.
Also there is no way that 100% of the stake will be participating. Thus, no blocks are likely to get 50%+1 approval! Thus the attacker will need much less than 50%+1 of the stake. Thus the presumption of 100% finality is not true in reality unless the system is run by an oligarchy which has 50%+1 of the control, and in which case the oligarchy can revert finality at-will.
The protocol desires that 50%+1 stake be online all the time. (If not, slots would be missing blocks.) The only way to achieve 50%+1 stake to be online is to have that stake in cloud. The PoA incentivizes all larger stakeholders to move to cloud through block rewards. (Block rewards would be difficult to receive without node being hosted in cloud.) If the parties are rational and the incentive exceeds the cost (of moving to cloud), then a quorum stake would likely be online all the time. The cost of cloud hosting at this time can be as low as $5-10/month ( https://www.digitalocean.com/pricing/). Note that this situation is completely different from PoW protocols. In PoW, a large mining equipment is typically housed on premises of the owner and the communication latency and speed are not relevant for the rewards. Such large mining equipment couldn't be hosted in cloud or would cost a prohibitive amount. In PoA, on the other hand, a computation node with low latency and high speed wins the most rewards. A much larger computation node is unlikely to win additional rewards. The PoA tradeoff are completely different from PoW. Due to these different tradeoffs (compared to PoW) and block rewards, I do expect most larger stakeholders to operate on cloud and be available for block approvals. In conclusion the major flaw in PoA is that it rewards all the minted money supply to the oligarchy that otherwise hopefully benevolently controls 50%+1 of the stake.
That is correct. To my understanding, that is the basis of Proof-of-Stake. Thus note that if the attacker held 80 or 90% of the stake at inception or anytime in the distant past, then the attacker could long-range double-spend 30 or 40% of it and still defeat the TaPoS protection.
Long rage history attack defense uses more than just TaPoS, it uses epoch and block approvals. It can be argued that TaPoS is not even needed for PoA since epoch approvals are likely to cover a large percentage of stake in the transactions. But then I realized you had side-stepped the valid concerns I had by presuming that nearly 100% of the stake would participating in all approvals. And that is sort of disingenuous assumption and circumvention of the invariants I was holding in my head. Yeah you get your 100% finality in 1 block, but effectively only under oligarchy control of the system. But that is sort of dubious because centralized systems are short-term final and long-term anti-fragile.
PoA expect near all stake participation in epoch approvals but not in block approvals. Epoch are expected to be 3+ order of magnitude larger than slots to achieve such a high participation. PoA expects block approval rewards to be large enough that a single roll owner would benefit from moving to cloud. Therefore, most of stakeholders owning larger stake than a roll would likely move to cloud. Assuming a Pareto like distribution, that should constitute >50% stake online to approval blocks. The conditions to make online stake smaller than quorum would be (failure conditions) 1. Stake distribution is too uniform. In that case, the incentive provided by block rewards may not cover cloud hosting cost. 2. Parties are not rational. 3. The block reward is too small to cover cloud hosting cost. In that case, the reward would have to be increased. The Theorem 3.2 (Weak Finality and Finality) has a correct but misleading and irrelevant proof: Proof. Theorem 3.1 shows that all honest parties have the common chain prefix for k ≥ 1. Therefore, any transaction in a block buried by one or more blocks is held by all chains of all honest parties. Therefore, any honest party will report that transaction after one or more blocks have been deposited on top of the block containing the target transaction.
The problem is that the finality of a single block may never be achieved without an oligarchy in control but an oligarchy in control breaks the security assumptions. So the problem is that the definition of finality as measured by a single block is not the complete story. Thus the proof is correct but only because it’s framed out-of-context of the flaws which make the proven theorem less relevant. Explanation above applies here. Under the rationality and stake distribution assumption in the paper, the theorem is correct and relevant. Another summary: The significant weakness is the presumption that 100% of the stake will be live. Otherwise the attacker needs much less than 50+%. Also the finality of blocks can”t be attained if there is not 50+% live. So there needs to be a 50+% attacker just for it to become final, unless 50+% of stake is always live and always votes correctly.
Online stake requirement (for liveness) is only >50% not 100% and the attacker still needs more than (ρ − δ − νc − νa − νe) stake to be able to win. Blocks containing approvals below quorum are simply invalid. Attacker can own the stake for approving invalid blocks or bribe other stakeholders. Either way, the attacker needs to control an amount > (ρ − δ − νc − νa − νe) to win. Regards, Shunsai |
|
|
|
Hello Traxo and @anonymint, Remember that because you slash (delete) votes for duplicate candidates with different parents, then honest stake cannot vote for all candidates. They must choose. But how can they objectively choose? They can't.
Paper's sections 2.2.20 and 2.2.22 describe that honest parties choose the parent (whose descendants to approve) as follows 1. Block with the higher approval stake, even to the smallest fractional coins, wins. 2. If the approval stakes match exactly, then the block with fewer approving parties wins. This discourages parties to split their stakes in multiple accounts. 3. If approval stakes match and the number of parties match, the block containing the smallest approval signature wins. While the approval signatures are not manipulatable, a party may benefit by splitting its stake into multiple accounts. But the previous step would discourage such an action. Since the procedure even includes a tie-breaker, honest parties will choose one parent or the other. The honest stake does not split. Regards, Shunsai |
|
|
|
Hello Traxo and @anonymint, 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.
Just a few lines before the above sentence, you had quoted from the paper 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. The honest >50% stake is not divided as you say, since they are allowed to vote for as many of the valid blocks they want with the same ancestry. It is not 1 vote per stake or party, it is multi-vote process. In fact, multiple blocks will get a quorum stake votes and the winner would be the one that got the most stake. The chain wouldn't get stuck at all. Regards, Shunsai |
|
|
|
|
Traxo,
My apologies - yes discussion can get confusion as I did get confused with that line.
Shunsai
|
|
|
|
Hello Traxo, IOW, single block proposals per slot are a semi-centralized design.
Proof-of-Approval has a limited number (10-50) but > 1 number of block producers per slot. The number is limited only to control the network traffic. Additionally the presumption of an expiration time for slots and epochs is fundamentally flawed. ...
In Proof-of-Approval, there is no slot expiration time deadline. There was deadline in version 1 of the protocol, but not in version 2. A block creator can wait as long as they want to receive approvals to proceed to the next step of publishing approvals. Approvals received too late will be ignored. 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. ...
Protocol uses the approvals stored inside the blocks that are candidates for the current slot. Parties may be looking at approvals outside of blocks (and storing them locally) in order to prepare for the block creation but the consensus uses only the approvals stored inside blocks. Perhaps the language in the paper can be improved to avoid such confusion. I assume the rest of the comments in the post relate to the previous set of questions that I answered. Shunsai |
|
|
|
Hello Paul, Won't this decrease the overall network participation rate, as accidental violations will naturally occur due to latency and connectivity issues?
The scheme would have to take that into account and avoid false positives. Shunsai |
|
|
|
Hello Paul, One possible solution can be to temporarily blacklist the offender and not award them for x number of blocks or epochs. A problem with it that the offender can transfer their stake to a brand new party. Perhaps temporarily blacklisting that stake no matter who owns it for x number of blocks or epochs may work better. It adds additional housekeeping but might work.
I am going to work on "temporary blacklisting of stake" that violates the protocol including storing their offenses on chain. Let's see if that does turn out to be feasible. Regards, Shunsai |
|
|
|
Hello Traxo, AFAICT, the slashing protection only works against a short-term double-spend. Thus AFAICT the long-range attacker who has 50%+1 can rewrite the entire chain, thus doesn’t have any hindrance due to the epoch window. The 50%+1 attacker can in theory divide-and-conquer the vested interests. Thus the 50%+1 attacker doesn’t even have the opportunity cost that @monsterer2 is writing about. Explanation of defense of the history attack is in my previous post to you and @anonymint. Regards, Shunsai |
|
|
|
Hello Traxo and @anonymint, I appreciate your taking time to read the paper and provide feedback - it's extremely valuable to me. Section 1.1.1 History or Costless Simulation Attack downplays...
Section 1.1.3 Nothing at Stake Attack ...
Introduction sections 1.X.X are certainly not meant to be an exhaustive discussion on the subject - I appreciate your providing additional details. 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. I believe there are two (or perhaps more) things being considered together which perhaps are better discussed separately. Item 1 - Clock synchronizationDiscussed below in this post. Item 2 - Delayed approvalConflicted approval arriving late does not affect consensus since the consensus picks the block with most stored approval on top of the chain. Protocol assumes that approvals apply to a block and as well as its ancestry. Delayed approvals do not alter the consensus chain, they end up being ignored. Item 3 - FinalityA protocol's stated properties hold within the bounds of the stated conditions. Let's discuss the cases (within the bounds of conditions and outside those bounds) separately. For reference, PBFT conditions 1. <1/3 adversarial nodes - no limit on stake 2. Synchrony required for liveness Proof-of-Approval conditions 1. <50% adversarial stake - no limit on nodes 2. Synchrony required for liveness - chain freezes otherwise Within the bounds of stated conditions Proof-of-Approval achieves finality within 1 block. PBFT achieves finality instantaneously within those bounds and even outside of them. While a claim can be made that makes PBFT far superior for that reason, perhaps the situation should be explored a bit more. Is finality really relevant when the content of the chain cannot be trusted? A quick calculation regarding adversarial cost for taking over a PBFT chain follows. The adversarial cost consists of 2 costs - cost of unpermissioned nodes and the cost of getting the permission. Unpermissioned node cost is about ~$70/hour per 10,000 nodes which is negligible. The permission mechanism can be endorsement, locked-up deposit, PoW puzzle or a certification by an authority - each can be converted to cost - cost to create a fake identity, cost of resources for PoW, cost of deposit or cost to bribe an otherwise honest node. If the permission cost is set to ~$100 per node, a network of 10,000 nodes can essentially be taken over by a mere $1million. In order to achieve $50million cost of taking over the chain, at 10,000 nodes, the permission cost must be set to ~$5,000 per node. I don't believe that is practical. Let's compare that to Proof-of-Approval. It achieves finality in 1 block (within the bounds). Adversarial cost to go beyond its bounds (~50% stake) is likely to be pretty high. 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. In Proof-of-Approval, there is no validator set. Approvals are created by the entire set of stakeholders. Since all stakeholders are validators in all slots and the adversarial stake is bounded <50%, a quorum of just >50% is sufficient. 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. The clock synchronization has 2 components - the clock period and the clock offset. Parties can rely on their own clocks for the period. The clock offset is used for 1. Determining if a block presented is a future block and should be rejected 2. When to publish a new block Item 1 is solvable by choosing a more complex chain height determination method based on the chains presented by nodes representing a majority of stake. The complexity comes from the fact that the stake must be determined from the chain itself. Item 2 is fairly easy and can simply use a running offset from observed block publications on the network. Clock offset is not required for determination of validity of messages - block publishers use all (valid) approvals before they have to publish approval block for the next block creators. The protocol does assume that during normal operation, a quorum of stakeholders is live. The incentive system of the protocol is designed to make larger stakeholders choose to operate on cloud. This is possible when the stake distributions are not too even (pareto like, similar to cryptocurrencies today) and parties are rational. 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. Theorem 3.12 shows defense against stake grinding attacks. To summarize here, the only option a "stake grinder" has is to drop some approvals from the block they are creating. That puts the newly created block at a disadvantage compared to other blocks and is likely to be not chosen (and defeats the entire grinding attempt). 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. Section 2.2.25 Preferred Fork Determination Procedure describes how epoch approvals work. Perhaps this example (quoted below) I provided to Paul may help.
A B C D E F G H I J K L
P Q R S T U V W
Let's try with an example. The attacker has 51% stake (at block D) that he sells off in the honest chain (starting from block E) and then creates an attack fork from block D. Transferring attacker's stake takes more than one epoch due to epoch stake transfer limit. In this scenario, the attack fork wins only if the first block of the attack fork (block P) has more signatory stake than the first block of honest fork (E).
Let's count signatory stake at block E.
1. The attacker made a transfer in the honest chain. His 51% is signatory in honest chain.
2. The honest chain got some block approvals from some stakeholders in addition to the attacker. Let's assume additional stakeholders constitute 10+% stake.
3. The honest chain got epoch approvals. Let's assume those are additional stakeholders representing additional 35+% stake.
Total signatory stake at block E = 96+%
Let's count signatory stake at block P.
1. Attacker's own keys - 51%
2. Other block approvals? Not without bribing other stakeholders.
3. Other epoch approvals? Not without bribing other stakeholders.
4. Copying transactions from honest chain? Not possible since they have a recent block signature. (Only transactions that have hashes of unshared blocks are counted as signatory stake).
Therefore, the signatory stake at block P is just 51%.
The honest chain wins.
Hope this example explains that the proof is correct. 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. Agree that the attacker may not need to acquire keys in the present and the wording in the paper should be changed to reflect that. Still, for a history attack to succeed, the attacker needs to have access to keys representing nearly all stake, not just 51%. Acquiring that stake under pareto like stake distribution is far more difficult and costly than just 51% stake. Regards, Shunsai |
|
|
|
Hello Paul, However, I've been thinking about this design some more and I think you still have a NaS problem, because a 51% attack doesn't cost the attacker(s) anything except the block rewards they would have otherwise earned for playing along with the protocol; i.e. they lose nothing, instead they stop gaining, so its opportunity cost rather than realised cost.
I have been debating it as well if the deterrence provided in protocol is strong enough. For example, in the scenario described in my previous answer to you, at what cost can the parties be swayed to approve an attack chain. If the parties can be swayed rather inexpensively, then there is a NaS problem. Does loss of one reward per misdeed provide enough deterrence? Also, should the misdeeds be recorded on chain? Other deterrent schemes require loss of locked up stake. I feel that locked up stake causes more problems than the solutions it provides. Someone's stake can't be locked up without their consent. Therefore, it must be an opt-in, which in turn means that not all stake will be approving blocks or epochs. That makes the protocol's defenses against attacker much weaker. One possible solution can be to temporarily blacklist the offender and not award them for x number of blocks or epochs. A problem with it that the offender can transfer their stake to a brand new party. Perhaps temporarily blacklisting that stake no matter who owns it for x number of blocks or epochs may work better. It adds additional housekeeping but might work. Any suggestions? Shunsai |
|
|
|
Hello Paul, If I understand correctly, the scenario would be like the following
A B C D E F G H I J K L
P Q R S T U V W
Block P starts an attack chain by forking from D and subsequent blocks form one or more epochs separate from the "real" chain.
I'm still wresting with how you'd need 99% stake in order to win this forking battle and not 51%? Let's try with an example. The attacker has 51% stake (at block D) that he sells off in the honest chain (starting from block E) and then creates an attack fork from block D. Transferring attacker's stake takes more than one epoch due to epoch stake transfer limit. In this scenario, the attack fork wins only if the first block of the attack fork (block P) has more signatory stake than the first block of honest fork (E). Let's count signatory stake at block E. 1. The attacker made a transfer in the honest chain. His 51% is signatory in honest chain. 2. The honest chain got some block approvals from some stakeholders in addition to the attacker. Let's assume additional stakeholders constitute 10+% stake. 3. The honest chain got epoch approvals. Let's assume those are additional stakeholders representing additional 35+% stake. Total signatory stake at block E = 96+% Let's count signatory stake at block P. 1. Attacker's own keys - 51% 2. Other block approvals? Not without bribing other stakeholders. 3. Other epoch approvals? Not without bribing other stakeholders. 4. Copying transactions from honest chain? Not possible since they have a recent block signature. (Only transactions that have hashes of unshared blocks are counted as signatory stake). Therefore, the signatory stake at block P is just 51%. The honest chain wins. Regards, Shunsai |
|
|
|
Hello Traxo, Proof-of-Approval also offers definitive 100% finality albeit with 1 block delay. And it offers a lot higher adversarial tolerance ~50% stake.
@anonymint says that is impossible. You would be defying the inviolable mathematics of BFT systems. He says there's a flaw somewhere in your conceptualization of your design. But he does not have time to help find it. But that math is inviolable. He is going to add this link to footnote 7 on that Part 2 of the blog: fork*-consistencySee also this exchange between @Fuseleer and @Come-from-Beyond. Perhaps you can read section 3.3.1 of https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf yourself. I am not saying that errors are not possible, but I have taken every care I could think of to avoid errors. Math is fairly straight forward as well. Thanks again for yet another great read Regards, Shunsai |
|
|
|
Hello Traxo, Proof-of-Approval does require majority to be online but not supermajority.
Then the transactions are only probabilistically final, not 100% final. 100% finality requires 2/3 of the validators to approve of the epoch. I am sorry but I am not understanding something here. Are you saying that 1. By having 2/3 stake, each protocol automatically achieves definitive 100% finality, and 2. Somehow that definitive 100% finality is not possible with mere >50% stake? 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. If the common prefix property is definitive then the protocol achieves definitive finality after the number of blocks determined by the common prefix property. Proof-of-Approval achieves definitive finality after 1 block - see section 3.3.1 of the paper (updated link https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf). Your blog is in error to claim you have an advantage over Ouroboros in this respect. 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. Did you arrive at different values for k for Ouroboros? If yes, I would love to see your calculations. Or do you believe it is definitive? Your blog is in error to claim you have an advantage over Ouroboros in this respect. You can find links to the "math of safety and liveness" in @anonymint's latest blog. See also this post Thanks for pointing them out, I am reading them Regards, Shunsai |
|
|
|
Hello Traxo, @d5000, I think you may remember the discussion you had last year with @anonymint (under one of his former pseudonyms) in Theymos' thread about altcoins. So it seems the points you are making here are reiterating some of that discussion about nothing-at-stake. @anonymint wrote down his analysis of the nothing-at-stake issue which will seem to apply to all of these non-proof-of-work consensus systems: https://gist.github.com/shelby3/e0c36e24344efba2d1f0d650cd94f1c7#oligarchy-if-pos-is-functioningHe does not think there will be any non-proof-of-work design that escapes from the nothing-at-stake problem except under the conditions he already mentioned when a super majority of the users are always online and network remains within a bounded asynchrony. He is confident a nothing-at-stake vulnerability can be identified in Proof-of-Approval. But who has the time to find the nothing-at-stake flaw in all of these non-proof-of-work designs? It is like everyone wants to try to reinvent the wheel of nothing-at-stake finding some way to blind themselves to the fact their design is also vulnerable. I read Shelby's paper above and I do agree with his analysis regarding PoS system and oligarchy. Although I'd put it slightly differently - stake based system requires unequal (pareto like) stake distribution in order to function correctly. Perhaps I took a different journey than Shelby but I did arrive at almost a similar conclusion. In order for Proof-of-Approval to have high liveness, >50% stake must be online. That can only happen if those stakeholders are on cloud, which, in turn, requires ongoing expenses. How can stakeholders be incentivized to pay ongoing expenses? By rewarding them more than their expenses. If a large number of parties hold about the same amount of stake, either all of them have to be awarded to pay for cloud (leading to inflation) or they will not be on cloud resulting in low liveness. Unequal stake distribution solves this problem. ... when a super majority of the users are always online and network remains ...
Just minor correction in your quote - you mentioned "super majority" while Shelby uses simple "majority." The inviolable rule is that 100% finality of transaction confirmations can only be obtained with a permissioned validator set.
Yes PBFT achieves 100% instant (0 block delay) finality only if the adversary is bounded typically to 1/3 of nodes. Unfortunately their adversarial tolerance is rather weak. The adversarial cost consists of 2 costs - cost of unpermissioned nodes and the cost of getting the permission. Unpermissioned node cost is about ~$70/hour per 10,000 nodes which is negligible. The permission mechanism can be endorsement, locked-up deposit, PoW puzzle or a certification by an authority - each can be converted to cost - cost to create a fake identity, cost of resources for PoW, cost of deposit or cost to bribe an otherwise honest node. If the permission cost is set to ~$100 per node, a network of 10,000 nodes can essentially be taken over by a mere $1million. If a PoS system requires $50million to attack, the corresponding permission cost would have to be raised to ~$5,000 per node. Not sure how many nodes will actually join such a network. Proof-of-Approval also offers definitive 100% finality albeit with 1 block delay. And it offers a lot higher adversarial tolerance ~50% stake. Thanks for pointing out @anonymint's paper https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers - I am still reading it. Regards, Shunsai |
|
|
|
Hello D5000, (However, you create another threshold as you pre-select some stakers to create blocks; if all block creators go offline, the blockchain stops this is probably wrong as simply the next slot would be chosen, but the problem persists in that it's likely that in some periods with low participation the block production will be slow).
Yes, there is a tradeoff between liveness and the amount of communication the network can tolerate in a slot. Options considered are, starting from the extreme 1. Everyone including those without stake can create blocks. This fails because someone can create a large number of nodes rather cheaply and flood out other creators. 2. Everyone with any (even the smallest stake) can create blocks. This also puts extreme burden on the network since this number can be very large. 3. Somehow limit which parties can create blocks in a slot. This is what I have been trying to achieve without inviting stake grinding (precompute) attack. The solution which I feel would work is a. Id the currency. That immediately requires a larger bundle (called roll) since individual ids are too expensive to store. b. Select some coin rolls - targeting about 10-50 stakeholders. c. If the coin roll is large enough that the additional block reward would more than offset the cloud server cost, then most of those coin roll holders will be online (since cloud never sleeps). It is the 3.c. assumption, if holds, will drive liveness. 1) It seems that it will be very difficult to reach the quorum of 50% for block approvals. I think this was also mentioned by Ix. In Nxt for example, which even has "stake leasing", about 30% participate in forging.
That is obviously something of great concern. The entire reward system is thought of from that perspective. 1. Assumption is that the stake distribution is not too uniform and is closer to pareto distribution (like every cryptocurrency that exists today). 2. Award system incentivizes larger stakeholders to move to cloud and stakeholders are rational. 3. Stake distribution is chunky enough (like every cryptocurrency that exists today) that cloud nodes constitute >50% stake. If these assumptions hold, then it works, not otherwise. 2) If I understand it right, "block creators" compete to create blocks after a new time slot has begun. Isn't this Proof of Work, as the fastest block creator with the best Internet connections would have most chances to win? Wouldn't that lead to an arms race like in Bitcoin?
Yes, better network connection benefits block creators - yet another incentive to move to cloud. It does use external resource (communication), which does distinguish one party from another (e.g. proximity in network hops to a majority of stakeholders). Is it PoW? Possibly but it does not incentivize parties to burn a lot of resources or use specialized equipment like Bitcoin/Eth PoW. Is it fair to all parties? Not sure of that either. Probably fairer to nodes on cloud than otherwise. 3) Time slots can only be orientative as timestamps can be easily faked.
True. Version 2 got rid of timestamps, now it wants only the target slot id. Each party should ignore all blocks targeted for future slots. (Was this the concern?) I countinued a bit in the whitepaper and found this sentence about the double-voting problem: Proof-of-Approval provides award for valid approvals, even on multiple
blocks, as long as they are not in conflict, i.e., they share the same parent. An
approver’s award is maximized when they approves all non-conflicting blocks.
But if they approves any conflicting blocks, the award vanishes.
This looks like "duplicate stake detection" mechanisms in today's PoS coins... This mechanism in essence is approving a single parent (although the approvals go to the child). Why the charade and not simply approve the child? The problem is that in order to get a majority approval on a single block, multiple iterations have to be performed. The protocol gets around that problem by using multi-voting (multiple blocks with the same parent). The cost is that finality is delayed by 1 block. The problem is the following: If you want to double spend, then you will publish your "conflicting chain" with the double-spend several blocks/slots after you forked it from the "honest" chain. Now if the staker has already received the reward for the approved block on the main chain (and maybe he has exchanged it for a good or another altcoin) then he can safely approve the attacker's second chain. And as timestamps can be faked, it's no issue to do that after some time. This seems only be (somewhat) solvable with "slasher"-like designs. There may be some protection against this problem because of your "block creator selection" process, but I think an attacker with 50% stake could game it, or at least keep trying until he succeeds. Maybe here I'm wrong however. Let's go through all the scenarios an attacker (with colluders) can try. To avoid text repetition, here are some common rules used in scenarios. a. Each slot defines coin roll owner who can create a block. This mechanism is not considered a security mechanism (not been analyzed for security) but it does not provide help to attacker. b. An attacker requires >50% approval for creating more than 1 block. (The first block stores previous block's approval which they can get from the honest chain.) c. Stake transfer per epoch is limited to <25% of total. d. Fork selection procedure changes if one or more epochs have passed since the forks separated. In that case, forks' signatory stake determines the winning fork. e. Transactions are context sensitive (hold a recent block hash). They cannot be copied from honest fork to attack fork (without attacker having the private key). Scenarios: 1. Attacker holds a small stake and doesn't care about the network. Attacker needs to bribe near 50% stake in order to succeed. This is not much different from an attacker bribing near 50% stakeholders during consensus. It's the security limit of the protocol in the short timespan. 2. Attacker with colluders has stake less than max transfer stake allowed in an epoch (<25%). Attacker wants to mount attack after transferring his own stake and fork from a block before his stake transfer started (but no epochs have passed). The attacker needs to bribe (majority - own stake) for blocks to become valid in the attack fork and for attacker to win. Again, the total attack stake is majority - same as the protocol limit. 3. Attacker with colluders has majority stake and mounts attack after transferring their entire stake. Epoch stake transfer limit would ensure that at least 2 epochs pass before attacker has transferred their entire stake. The attack fork would start before the stake transfer started. In this scenario, the honest chain would have epoch approval and the attacker needs to exceed epoch (signatory) stake in honest fork to win. Signatory stake would be much larger than the majority stake. There can be combinations of these scenarios but the result is either the short timespan protocol limit of ~50% or exceeding epoch (signatory) stake in honest fork. Regards, Shunsai |
|
|
|
Hello Traxo, So if those assumptions for super majority of users being online and bounded network asynchrony are not fulfilled, then security deposits are insufficient for security, although they might or might not help rate limit. So without any effective penalty on malevolence there's no cost to attacking it regardless if the validator set is permissionless or permissioned. He presumes the same vulnerability can be found in every non-proof-of-work design including Proof-of-Approval. Proof-of-Approval does require majority to be online but not supermajority. That would not be possible without larger stakeholders being on cloud. Furthermore, parties would not move to cloud unless they have an incentive for it. Proof-of-Approval's incentive for moving to cloud is block-approval award. It would be difficult, for parties to win block approval from non-cloud system. The assumption there is that once larger stakeholders move to cloud (some protocols call them supernodes), they are always online and provide security and liveness to the chain. The big assumptions here are 1. Some parties have large enough stake that moving to cloud is profitable for them (due to block-approval award). 2. Parties actually act rationally and do move to cloud. If these assumptions hold, Proof-of-Approval would be secure. Regards, Shunsai |
|
|
|
Hello Paul, Why is it not possible to present two different epocs representing the same time period? That's where my attack angle was coming from.
If I understand correctly, the scenario would be like the following
A B C D E F G H I J K L
P Q R S T U V W
Block P starts an attack chain by forking from D and subsequent blocks form one or more epochs separate from the "real" chain. This scenario is called long timespan scenario and the winner fork is determined which (of E or P) represents higher signatory stake. Signatory stake, as described earlier, are all the block creators, approvers, epoch approvers, transaction signers of the forks that start with E and P. Was this your question? Shunsai |
|
|
|
Hello Ix, Sorry for delay in reply Hard-coded means that each node would see the genesis block identical - they have no choice but to accept the genesis block. That is not subjective, it is purely objective. It's all just different types of subjectivity. Nomenclature aside, all blockchains are solutions to The Byzantine Generals Problem ( https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf). The goal of a solution is to not have to trust any single party, or at least have as few instances of having to trust one or more of them. Of all the public blockchains today, PoW blockchains place fewest trust requirements from the parties joining the network. Most (all?) public stake based systems require parties to trust more of others more often. I believe, for that reason, PoW is the winner today (although some of it may be historic). I know I can be an overly argumentative and strongly opinionated ass, but I have been studying this stuff and devising alternative systems since 2011 so I've had a lot of time to work some things out.
The knowledge shows through and is appreciated. I am *finally* putting my money where my mouth is and working on my own protocol full-time, but based on some of what you've said, we might disagree on my economic notions more than technical ones. Looking forward to more discussions in near future :-) Regards, Shunsai |
|
|
|
Hello Sapotacoin, The developers provided a solution to an attack that requires subjectivity. You asked, I provided. I'm not sure how you presume this applies to old software or that it isn't for protocol reasons, as both of these presumptions are incorrect. If new hardware was created that was an order of magnitude faster than today's hardware, you can damn well bet the bitcoin devs would be adding another checkpoint to the software tout de suite, still wondering what the solution to this problem is. The genesis block is hard-coded into the software and is therefore subjective itself, so the entire notion of any network starts with subjectivity. Extending that subjectivity to avoid simple but damaging attacks is hardly a crime.
See the answers in reply to Ix. Regards, Shunsai |
|
|
|
Hello Ix, Light can travel around the Earth around 7 times a second. That means the minimum latency between two peers on opposite sides of the Earth is roughly 1s/7/2 or 71ms. This is only one order of magnitude less than your 1s block confirmation times. Now, add in the fact that real latency is not the speed of light and that order of magnitude all but disappears. The point is, maybe reductio ad absurdum but maybe not, is that you have no control over any node's subjective view of the network. Weak subjectivity is a stronger principle than subjectivity. You can not eliminate subjectivity, and my snarky point doesn't invalidate the rest of what I said. Fault tolerance can't be hidden away by rationalizing actors, it is at the forefront of distributed networking.
You are absolutely correct that 1 sec did assume closer proximity of >50% of stakeholders. The slot period is expected to be small by design - to make it difficult for nodes not on cloud to compete for block approvals. The genesis block is hard-coded into the software and is therefore subjective itself, so the entire notion of any network starts with subjectivity.
Hard-coded means that each node would see the genesis block identical - they have no choice but to accept the genesis block. That is not subjective, it is purely objective. The developers provided a solution to an attack that requires subjectivity. You asked, I provided.
Yes, I did not know of it before. Appreciate that I'm not sure how you presume this applies to old software ...
Git blame shows that code being older than 4 years old - it could actually be older since I didn't go all the way back. ...that it isn't for protocol reasons, as both of these presumptions are incorrect.
"It is a long term goal of removing the checkpoints entirely..."Can't remove the checkpoint if it is for the protocol reasons :-) If new hardware was created that was an order of magnitude faster than today's hardware, you can damn well bet the bitcoin devs would be adding another checkpoint to the software tout de suite, still wondering what the solution to this problem is.
Agree. If there was an unexpected breakthrough that made PoW dramatically easier to solve, all PoW protocols have to take some preventive measures. This discussion is providing me new insights and I really appreciate that. Shunsai |
|
|
|
|
