Topic: Proof-of-Approval: Version 2.0 - page 4. (Read 1860 times)

Won't this decrease the overall network participation rate, as accidental violations will naturally occur due to latency and connectivity issues?

Hello Paul,


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,


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.

Introduction sections 1.X.X are certainly not meant to be an exhaustive discussion on the subject - I appreciate your providing additional details.



I believe there are two (or perhaps more) things being considered together which perhaps are better discussed separately.

Item 1 - Clock synchronization
Discussed below in this post.

Item 2 - Delayed approval
Conflicted 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 - Finality
A 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.



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.



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.



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).
 


Section 2.2.25 Preferred Fork Determination Procedure describes how epoch approvals work. Perhaps this example (quoted below) I provided to Paul may help.

Hope this example explains that the proof is correct.



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

It looks like a great solution for 51% attack problem.  

I'm afraid I have none. I have the same misgivings about locked up stake as you, along with the ensuing mess of fraud proofs and counter proofs makes the entire problem very hard to reason about and that loss of elegance is to be feared and avoided.

I'd like to draw a comparison to bitcoin if I may; as it stands the NaS problem you're facing is equivalent to what would happen if bitcoin always payed a block reward for every block, regardless of whether it was orphaned or not, making makes 51% attacks costless.

AFAICT, the slashing protection is only intended to be effective against a short-term double-spend, but it's flawed anyway.
Thus AFAICT the long-range attacker who has 50%+1 can rewrite the entire chain, thus wouldn’t have any hindrance due to the epoch window even if it wasn't flawed.
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.


Concur and concur.

---

Note the NaS 50%+1 attack issue is separate from the liveness and probabilistic finality issues that @anonymint has explained in my prior post.

Hello Paul,

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

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.}


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.


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:


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.


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.


How so? Where's the security proof?

Regarding Theorem 3.6 your paper states:


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.


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.

Hi Shunsai

Thanks for the detail, that clears it up completely. The key is the per-epoc stake transfer limit.

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.

In PoW this is quite different; indeed, the cost of pulling off a 51% attack is that the attackers actually lose money to electricity equivalent in value to the block reward, so if their attack does not succeed, they lose money overall, whereas with proof of approval, a failed attack costs nothing, as I understand it.

Cheers, Paul.

Hello Paul,

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

Hi Shunsai

I'm still wresting with how you'd need 99% stake in order to win this forking battle and not 51%?

Cheers, Paul.

Hello Traxo,


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,

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).


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?


Thanks for pointing them out, I am reading them

Regards,
Shunsai

@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*-consistency

See also this exchange between @Fuserleer and @Come-from-Beyond.

Hello Traxo,

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.


Just minor correction in your quote - you mentioned "super majority" while Shelby uses simple "majority."


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,

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.

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.


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.


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?)


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.


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

Then the transactions are only probabilistically final, not 100% final.
100% finality requires 2/3 of the validators to approve of the epoch.
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

Hello Traxo,


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,

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