Proof-of-Approval: Version 2.0

[monsterer2]

The ultimate goal, though, is to have the entire stake in the system sign every block, isn't it? I know that would be totally unfeasible because of the size of the data, but this is the security model you're aiming to approximate?

Absolutely! In addition to the size of data, nodes on slow/intermittent connections may not be able to send their approvals for each block.

In that case, I think you have succeeding in increasing the difficulty/cost of the recent history attack using old private keys, because as you say, the attacker now needs a super majority of old stake in order to pull off the attack.

But, I think its important to note that the attack *is* still possible because old private keys have little to no value.

The vulnerability in your design will be the approximation of the ideal all-stake-signs-all-blocks idea. So, as I think you've noticed, ordering by stake in the head block isn't ideal. I expect there to also be boundary issues around the edges of the epocs.

I'd like to suggest a simplifying change to your consensus design:

* Ditch the epocs
* Ditch the approvals
* Retain the block reward
* Keep all candidate blocks submitted in the chain (perhaps add a minimum stake threshold)
* Incentive uncle references (like the PoW etherum chain)
* Recursively sort by the cumulative stake

This is largely similar to the way ETH currently works, and would negate the need for epocs because you now have active history for all branches, so inserting into past history would have a similar cost to the idealised version above.

Cheers, Paul.

[shunsaitakahashi]

Hello Paul,

In that case, I think you have succeeding in increasing the difficulty/cost of the recent history attack using old private keys, because as you say, the attacker now needs a super majority of old stake in order to pull off the attack.

But, I think its important to note that the attack *is* still possible because old private keys have little to no value.

Although I have no data on hand, I don't expect a full stake churn to be in less than a month period, more likely in years time period. In such a long period, the "real" chain would have probably accumulated at least one epoch approval from 100% of the stakeholders. So, the attack chain can't win by supermajority (2/3 or 3/4 of stake), it needs 100% of the stake!

Also note that a single honest stakeholder (hodler ) holding a relatively small stake (~.1%) will make such a history attack impossible.

The vulnerability in your design will be the approximation of the ideal all-stake-signs-all-blocks idea. So, as I think you've noticed, ordering by stake in the head block isn't ideal. I expect there to also be boundary issues around the edges of the epocs.

You are correct that epochs cause edge issues (just like any other nonlinearity). Let's do some back of the napkin calculation:
1. Slot 3 sec
2. Number of slots per epoch 1200
3. Epoch period 60 min
Assuming each epoch limits max stake transfer to say <25% of total stake, the full stake transfer can only be done in 4 epochs or 4 hours. In this case, there would be at least 2 epochs without any edge issues. I'd expect >80% stake to be approving at least one of those edge issue free epochs. In other words, while there may be edge issues with epochs, they can be managed without affecting security.

* Ditch the epocs
* Ditch the approvals

1. What's the common prefix property in that case? I expect k >> 1. This property is more important for commerce than most people realize.
2. How does it defend against history attacks? Stored candidate blocks or uncle references won't defend against history attacks.

* Keep all candidate blocks submitted in the chain (perhaps add a minimum stake threshold)
* Incentive uncle references (like the PoW etherum chain)

1. What desirable property or defense against attacks do these stored candidate blocks provide? I can't think of any.
2. Same for uncle references - what desirable property or defense do they provide? Again, I can't think of any.

* Recursively sort by the cumulative stake

This is a good idea. This may help with edge condition of correct fork selection. I would definitely look more into it.

While I may be disagreeing with you on some issues, I absolutely appreciate the thoughtful questions and suggestions you are providing.

Regards,
Shunsai

[shunsaitakahashi]

Hello Yj1190590,

They could receive more approvals from using both unconflictful and conflictful contents. Isn't that right? Regardless of the benifit anyway, why does anyone doing their duty when there is no evidence and no punishment for not doing so? What if somebody use an incomplete mining application?

Note that approvers are stakeholders who have most to lose if there is even a possibility of a network compromise. If the network can be compromised, their coin holdings may not change, but value of their coins would. Assuming network stakeholders are rational, why would they do anything to harm themselves? The evidence of wrongdoing is present on the network, just not stored in the chain since it's used in the short timespans not long timespans.

As a matter of experience, >50% online stake is very unusual. The problem of getting stuck is critical because it could happen anytime and last a very long period of time, not just under network separation. Shouldn't you find a way to deal with that?

Note that stake distribution is Pareto distribution. Assuming there are approximately 10K nodes on the network, >50% of stake may be held by only ~20-50 nodes. These large stakeholders, wanting to maximize their earnings in the network, would simply operate a cloud instance. These can be as cheap as $5/month! Some of the new ICO offerings call these supernodes, but here, it's simply a self selection process incentivized by more awards (for block-approval and block-creation).

In this respect, the word "stable" is meaningless when the onchain data could still be changed and that's why Bitcoin and Ethereum are called "nonfinality". Protocols like PBFT and Casper provide finalites by the collaboration of Valiators but I didn't see "finality" in your protocol.

PBFT may sound like a better protocol due to finality but in practice it isn't. PBFT generates consensus on transactions, which are smaller than blocks. For a large number of nodes, it is more difficult to achieve consensus on tiny transactions than larger blocks. Casper (https://arxiv.org/abs/1710.09437) does not improve short timespan finality, i.e. >6 block, its benefit is only for long timespans.

A protocol can make any number of claims but what matters is what it can deliver. For that reason, only 8% of the ICOs reach exchanges (https://news.bitcoin.com/80-of-icos-are-scams-only-8-reach-an-exchange/), other 92% claiming all sort of superiority die even before that. My intent is to have a protocol that can withstand the well known attacks as well as new ones. One cannot build another Bitcoin or Ethereum on false promises.

Regards,
Shunsai

[shunsaitakahashi]

Hello Ix,

If you're interested, you can check out my signature for a link to my whitepaper on the Decrits consensus algorithm which is relatively similar to yours (with an identical long range attack defense), and is 5+ years old.

Yes, while some parts are similar, there are large differences between DCA and Proof-of-Approval.
1. DCA's security is based on wagered stake which has opportunity cost. Proof-of-Approval doesn't require a stakeholder losing any opportunity cost.
2. Cost of attack on DCA is limited by wagered amount that is not likely to be a large percentage of total stake due to opportunity cost. Cost of attack on Proof-of-Approval is likely to be much larger.
3. If I understand correctly, all "Voices" in DCA are assumed to be honest. That assumption is probably not valid.
4. Persistence model indicates 10 blocks deposited for finality but it's unclear how "final" that is. Proof-of-Approval achieves finality after 1 block.

Regards,
Shunsai

[Ix]

Hi Shunsai, since you went through mine I will return the favor as I only scanned yours somewhat briefly before. It would be nice if you could put it on a site with a direct link to the pdf instead of behind a signup wall.

1. DCA's security is based on wagered stake which has opportunity cost. Proof-of-Approval doesn't require a stakeholder losing any opportunity cost.

I see this as a benefit. It reduces the ability of banks and exchanges and even large corporations to control large percentages of the total stake with money that may not even be theirs to stake.

2. Cost of attack on DCA is limited by wagered amount that is not likely to be a large percentage of total stake due to opportunity cost. Cost of attack on Proof-of-Approval is likely to be much larger.

(I assume you mean total coin supply in bold?) While this is true for a 33% or >50% attack, I argue that Decrits is essentially 99% attack proof. As long as there are a few honest stake holders, the network can continue honestly in the face of any level of adversity.

3. If I understand correctly, all "Voices" in DCA are assumed to be honest. That assumption is probably not valid.

See above.

4. Persistence model indicates 10 blocks deposited for finality but it's unclear how "final" that is. Proof-of-Approval achieves finality after 1 block.

The finality boils down to nodes that have seen block X at slot 0 with approvals from block X+1 through block X+10 will refuse to support any chain that approves block Y at slot 0. This allows for permanent forks to form in the face of adversaries, but it should be exceedingly unlikely in a network not under attack (under similar assumptions you use in your proposal regarding time and connectivity). This means that nodes that are not online at the time could be unsure about which fork is honest. However, I argue that 1) in a ubiquitous network this is not a problem as you could simply see what is in the news or see what an exchange says or ask a friend who maintains a full node and 2) the fork can't affect the user as they weren't online anyway. Presumably they would log in to make a transaction and the person they are transacting with can tell them which network they accept, although the transaction will most likely be approved on both anyway.

Block overhead is also very small, requiring only one signature. Compared to your system, the block overhead is bound only by the number of stakes required to reach a quorum, multiplied by the number of candidate blocks and potentially infinite number of the candidate's children. This could be quite large, and it requires a quorum to be online at all times, as well as being publicly known by IP address for messages (a DDoS vector). And unless I misunderstand your proposal, I don't see any simple finality solution. Multiple forks may compete honestly for an unbound amount of time, leaving victims of double spent transactions unable to determine whether or not their transaction is valid.

e.g. I don't believe it is dishonest for a stakeholder to approve transaction X to Y in child B and also approve transaction X to Z in child B' as both transactions are valid in those child blocks, but only one will eventually (when?) be selected. Therefore the weak finality is more nebulous than in PoW where a significant cost in hashing power is incurred for building two or more chains. My understanding of this may not be complete, however.

Additionally, your nothing-at-stake defense is quite weak as it only removes the block award from a stake holder. Adversarial stake holders are free to continue interrupting the network for as long as they like. With the DCA proposal, a voice creating two blocks for the same slot is considered in violation of the protocol and will have its stake destroyed rather than just losing out on rewards. A group of voices that continue to build on a fork will eventually have their stakes destroyed as well (each fork will destroy the stakes of the other). This is much more damaging to an attacker than losing block rewards.

A downside of DCA is that if a given stakeholder is not online for its slot, the network will have no approvals for transactions it was assigned to approve for that slot. However, it trades this for high bandwidth efficiency and true and fast finality.

[monsterer2]

Also note that a single honest stakeholder (hodler ) holding a relatively small stake (~.1%) will make such a history attack impossible.

Hi Shunsai,

I'm not totally sure I follow how that is possible. Lets discuss this before I get into any of your other questions

Cheers, Paul.

[shunsaitakahashi]

Hello Ix,

It would be nice if you could put it on a site with a direct link to the pdf instead of behind a signup wall.

Done. Moved to https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf

2. Cost of attack on DCA is limited by wagered amount that is not likely to be a large percentage of total stake due to opportunity cost. Cost of attack on Proof-of-Approval is likely to be much larger.

(I assume you mean total coin supply in bold?) While this is true for a 33% or >50% attack, I argue that Decrits is essentially 99% attack proof. As long as there are a few honest stake holders, the network can continue honestly in the face of any level of adversity.

By cost of attack, I mean something similar to this https://www.reddit.com/r/ethereum/comments/8m3lpo/an_ethereum_classic_51_attack_would_only_cost_55/. It is the total money an attacker would have to spend for a successful attack. If only a small percentage of stake is wagered (say 5-10%), the cost of a successful attack on that network is likely to be about 5-10% of the total value of the network. For Proof-of-Approval, this is approximately 50%.

I argue that Decrits is essentially 99% attack proof. As long as there are a few honest stake holders, the network can continue honestly in the face of any level of adversity.

That is a very strong statement. There is no protocol in existence today that tolerates adversarial power >=50%. I would love to read the proof if one is available.

4. Persistence model indicates 10 blocks deposited for finality but it's unclear how "final" that is. Proof-of-Approval achieves finality after 1 block.

The finality boils down to nodes that have seen block X at slot 0 with approvals from block X+1 through block X+10 will refuse to support any chain that approves block Y at slot 0. This allows for permanent forks to form in the face of adversaries, but it should be exceedingly unlikely in a network not under attack (under similar assumptions you use in your proposal regarding time and connectivity). This means that nodes that are not online at the time could be unsure about which fork is honest. However, I argue that 1) in a ubiquitous network this is not a problem as you could simply see what is in the news or see what an exchange says or ask a friend who maintains a full node and 2) the fork can't affect the user as they weren't online anyway. Presumably they would log in to make a transaction and the person they are transacting with can tell them which network they accept, although the transaction will most likely be approved on both anyway.

The persistence and finality for blockchains are defined (by the research community) from point of view of nodes that are online and honest. For all honest online nodes, the Proof-of-Approval chain will have at most the top block different (finality of 1 block). Is this property for DCA 10 or less?

Block overhead is also very small, requiring only one signature. Compared to your system, the block overhead is bound only by the number of stakes required to reach a quorum, multiplied by the number of candidate blocks and potentially infinite number of the candidate's children. This could be quite large, and it requires a quorum to be online at all times, as well as being publicly known by IP address for messages (a DDoS vector). And unless I misunderstand your proposal, I don't see any simple finality solution. Multiple forks may compete honestly for an unbound amount of time, leaving victims of double spent transactions unable to determine whether or not their transaction is valid.

Proof-of-Approval is designed for a mathematical proof of the stated properties. I could not achieve a mathematical proof with less approvals. If you can, I would love to read the proof.

e.g. I don't believe it is dishonest for a stakeholder to approve transaction X to Y in child B and also approve transaction X to Z in child B' as both transactions are valid in those child blocks...

That is a rule, just like sports or organizations have rules e.g. http://www.gssasoccer.com/Default.aspx?tabid=169249. An action is valid or invalid purely because the rules of that sport/activity/organization say so.

but only one will eventually (when?) be selected.

In the very next block. Please see proof of the common prefix property in the paper.

Additionally, your nothing-at-stake defense is quite weak as it only removes the block award from a stake holder. Adversarial stake holders are free to continue interrupting the network for as long as they like. With the DCA proposal, a voice creating two blocks for the same slot is considered in violation of the protocol and will have its stake destroyed rather than just losing out on rewards. A group of voices that continue to build on a fork will eventually have their stakes destroyed as well (each fork will destroy the stakes of the other). This is much more damaging to an attacker than losing block rewards.

It may be of interest to see what causes nothing-at-stake in the first place. Nothing-at-stake is caused by incorrect incentive system of some early PoS systems that benefited rule violators. Proof-of-Approval removes that incentive, rule violators are punished and violators are incentivized to follow the rules. Is this punishment strong enough? It is if prevents the problem from happening. It is similar to real life - is fine/jail for a crime is sufficient or does it need to be harsher.

A downside of DCA is that if a given stakeholder is not online for its slot, the network will have no approvals for transactions it was assigned to approve for that slot. However, it trades this for high bandwidth efficiency and true and fast finality.

I believe this is the correct approach.

Regards,
Shunsai

[shunsaitakahashi]

Hello Paul,

Also note that a single honest stakeholder (hodler ) holding a relatively small stake (~.1%) will make such a history attack impossible.

I'm not totally sure I follow how that is possible. Lets discuss this before I get into any of your other questions

This is in context of long timespan History attack where an attacker acquires private keys of accounts that no longer have stake. The owners of those keys may not have much incentive to keep them private since they themselves have nothing to lose. Therefore, an attacker can acquire them relatively inexpensively. In most stake based systems, these keys must form a majority stake at some point in time. Since creating blocks for PoS doesn't require large computation, the attacker can create a large number of blocks in his favor very quickly and overtake the "real" chain.

Note that this scenario depends upon how frequently the stakes are changing in the network (churn rate). For a typical network, change of 100% network stake from one group of parties to another group is likely to take over several months if not years.

Proof-of-Approval incorporates several features that make the attacker's task difficult.

1. The chain length is counted as the number of slots spanned, not the number of blocks in it. A "real" chain is a lot more likely to have missing blocks than the attack chain. With this rule, the real chain is not penalized.

2. Epoch approvals incentivize even the smallest stakeholder (say a single coin) to participate in epoch approval. Although no claims can be made for the participation rate of epochs, it is highly likely that over a period of month or so, almost all stakeholder would have approved at least one epoch. Over a period of several months or years, it would be even larger.

3. For fork selection with epochs, stakes of all signatories (block creator, block approver, epoch approver, stake transferer) are considered. This is likely to be very close to 100% over a period of months or years.

4. If a 100% churn did occur in the period, all original stakeholders have become signatories for the real chain (100% stake!).

An attack chain can only win by exceeding signatory stake in the "real" chain. If an honest "hodler" is holding .1% stake, it isn't possible for the attacker to acquire the private keys representing the needed stake.

Regards,
Shunsai

[Ix]

By cost of attack, I mean something similar to this https://www.reddit.com/r/ethereum/comments/8m3lpo/an_ethereum_classic_51_attack_would_only_cost_55/. It is the total money an attacker would have to spend for a successful attack. If only a small percentage of stake is wagered (say 5-10%), the cost of a successful attack on that network is likely to be about 5-10% of the total value of the network. For Proof-of-Approval, this is approximately 50%.

Right, I was trying to clarify the terminology you used because it is ambiguous. "Total stake" should mean the "currency used to protect network / total currency". It is a dubious claim that this would be anywhere near 50% for proof of approval because that would require a quorum of 50% of the total currency. That is not scalable as you've described your protocol. The stake must be a subset of the total currency. Prior proof of stake implementations got around the scalability problem by the "stake grinding" type system.

That is a very strong statement. There is no protocol in existence today that tolerates adversarial power >=50%. I would love to read the proof if one is available.

I am much more programmatically inclined than mathematically. Proofs are not infallible, and lack of proofs does not imply lack of provability, as I'm sure you know.

BFT implies that the network must eventually come to a complete consensus. Bitcoin and essentially every other blockchain protocol presumes that this must happen in a completely deterministic way for the sake of network cohesion of offline nodes. I disagree. Under the assumption that network connectivity is reasonably always available, it is possible for all honest online nodes know for certain which of two or more forks is the correct one to use under my system because the creators of blocks is known well in advance. By discarding and destroying any stake that provides more than one history, and by using small subsets of BFT to determine which of two or more small forks to proceed with, online nodes can create a cohesive but not necessarily deterministic history for offline nodes.

As a very large adversary can also create a cohesive but dishonest history, offline nodes will require human input to determine the correct chain. I think this is a more than acceptable tradeoff because the dishonest history will have its stake destroyed which means the attack cannot be performed again without great cost, and therefore will likely never be performed in the first place.

In the case of a partition of the internet, the network must have a voting system to recombine the network after it has been reconnected. This is another caveat. However, this caveat exists in a similar way under bitcoin and others in that transactions are not final, it just takes less effort to recombine the network.

The persistence and finality for blockchains are defined (by the research community) from point of view of nodes that are online and honest. For all honest online nodes, the Proof-of-Approval chain will have at most the top block different (finality of 1 block). Is this property for DCA 10 or less?

Well the research community must take into account how offline nodes can determine the correct chain, otherwise they are susceptible to being defrauded.

e.g. I don't believe it is dishonest for a stakeholder to approve transaction X to Y in child B and also approve transaction X to Z in child B' as both transactions are valid in those child blocks...

That is a rule, just like sports or organizations have rules e.g. http://www.gssasoccer.com/Default.aspx?tabid=169249. An action is valid or invalid purely because the rules of that sport/activity/organization say so.

I meant I don't believe it is dishonest under your protocol as you've described it. From page 4:

"Approvers are allowed to approve as many blocks as they choose as long as the approved blocks share the same parent."

In the very next block. Please see proof of the common prefix property in the paper.

I don't believe you've shown this property at all. In fact, you describe many scenarios where there are forks that are multiple blocks deep. If finality is determined in the very next block, how can there be multiple chains extending multiple blocks? That is not finality. Additionally, an adversary has no requirement to sign multiple chains, it may only sign the one it wants, and thus no quorum is achieved.

Presumably block creators do not sign the block approvers' messages in the block, or else the block must be reconstructed every time a new approval is received. Therefore block approvers' messages are received in an ad-hoc manner. This is problematic as it is very non-deterministic. Page 20:

"Even if all corrupt parties approve conflicting blocks, and newly acquired stakeholders vote for their candidate fork, at least one honest party is still required to achieve quorum. Since the honest parties would have chosen a candidate fork based on slot sl r , they will approve only one candidate fork.
Therefore, only one of the Br+1, B*r+1, B**r+1 etc. will be valid and, therefore, there will be only one persistent fork."

This implies the honest quorum agrees on which of the three chains to approve, which I don't see how this is in any way a certainty, and it conflicts with the page 4 quote regarding what approvers can approve.

It may be of interest to see what causes nothing-at-stake in the first place. Nothing-at-stake is caused by incorrect incentive system of some early PoS systems that benefited rule violators. Proof-of-Approval removes that incentive, rule violators are punished and violators are incentivized to follow the rules. Is this punishment strong enough? It is if prevents the problem from happening. It is similar to real life - is fine/jail for a crime is sufficient or does it need to be harsher.

Nothing-at-stake is an unintended consequence of a system that was not thought out fully, it is not a rule violation. The problem with it is that presumably honest nodes have an incentive to work on multiple chains as it maximizes their profit potential. Network attackers could abuse this.

Almost all of these problems arise in the case of double spending which you do not seem to have addressed in your protocol. Double spending is not a rule violation either, as the two spends are valid as they appear in two forks.

I think unfortunately in your attempt to ameliorate long range and nothing at stake issues, you have missed the forest for the trees.

[shunsaitakahashi]

Hello Ix,

Perhaps we are thinking from slightly different points of view. Individual items that we differ on are likely outcome of the same difference. My point of view follows and I am open to adopting your point of view should I find deficiencies in my thinking.

1. PoW has provided the most robust consensus to date. Bitcoin has withstood assaults from all sides and survived.
2. All PoS systems and their derivatives are not fully trusted by investors. It is reflected in the prices of those tokens. The most valuable tokens are still PoW.
3. PoW burns power. So much power that miners are unprofitable if Bitcoin is below $8,050.
4. The normal supply curve (https://en.wikipedia.org/wiki/Supply_and_demand) does not apply for cryptocurrencies. Bitcoin being below $8,050 doesn't just make some miners unprofitable, it probably makes all miners unprofitable.
5. The normal demand curve also doesn't apply to cryptocurrencies. If the mining permanently stops, all current coins become worthless (because no future transactions will be added to the chain). In similar scenarios, value of other goods drops but not so dramatically.
6. A stake based system, has a break-even price near $0 (compared to Bitcoin's $8,050).
7. If a robust stake based system can be implemented and if it were to be so robust that it can survive all attacks then the investors would trust it and bring it in the same category as Bitcoin and Eth. Or maybe Eth would adopt that stake based system finally (they haven't so far because no system has proven to be robust enough).

That's why I am so focused on robustness. Regarding scaling, I have modeled Proof-of-Approval and counted the bytes transferred and stored. While it does store more than a typical blockchain, and transfers more data, it can easily run at 1sec slot period at today's technology.

Regards,
Shunsai

[Ix]

1. PoW has provided the most robust consensus to date. Bitcoin has withstood assaults from all sides and survived.

I'd argue that PoW is not particularly robust. Bitcoin gold was just attacked to the tune of $15m in losses. https://www.cryptoglobe.com/latest/2018/05/bitcoin-gold-hit-with-51-and-double-spend-attacks-18-million-stolen/

The reductio ad absurdum is that bitcoin requires >50% of all the energy in the universe to be secure. That's silly.

2. All PoS systems and their derivatives are not fully trusted by investors. It is reflected in the prices of those tokens. The most valuable tokens are still PoW.

There are a lot more factors at play. Stellar is in the top 10 and does not use any form of PoW that I'm aware of (but I'll admit I don't keep up with the various alts).

As far as PoS not being trusted, there has been no breach of trust in the various PoS type chains that I know of. Bitcoin proponents have a vested, multi-hundred-billion dollar interest in spreading doubt about PoS which is where arguments like "nothing at stake" come from (I've been around BCT for a very long time). That's not to say that nothing-at-stake is an irrelevant problem, however it is very likely less relevant than PoW's >50% attack vulnerability. Intrinsic attack areas are, in my opinion, obviously less significant than extrinsic (as you noted), so the default question should be to question the integrity of PoW, not PoS. BCT has a warped view of reality, however.

3-7

All these are again relatively obvious problems that PoS improves upon over PoW.

That's why I am so focused on robustness. Regarding scaling, I have modeled Proof-of-Approval and counted the bytes transferred and stored. While it does store more than a typical blockchain, and transfers more data, it can easily run at 1sec slot period at today's technology.

If that is the case I would be interested in your numbers and assumptions. At least we can start at a single point and determine the (subjective) scalability of your proposal before proceeding on more technical details. This would help clarify where I am getting it wrong, too. Because in my understanding, a simple back of the envelope calculation assuming even 100k accounts interested in participating in the quorum is 100k*64 bytes (ECDSA sig)*1 sec slot = 6.4MB/s for data not including transactions. Maybe half for 50% quorum.

[shunsaitakahashi]

Just to make sure it's the right version of the protocol - https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf.

If that is the case I would be interested in your numbers and assumptions. At least we can start at a single point and determine the (subjective) scalability of your proposal before proceeding on more technical details. This would help clarify where I am getting it wrong, too. Because in my understanding, a simple back of the envelope calculation assuming even 100k accounts interested in participating in the quorum is 100k*64 bytes (ECDSA sig)*1 sec slot = 6.4MB/s for data not including transactions. Maybe half for 50% quorum.

Here are the assumptions.
1. About 10-50 stakeholders get to create a block in any slot. This number can be tweaked using coin roll selection predicate.
2. Stake distribution is Pareto. The protocol is optimized for Pareto distribution.
3. I expect a quorum to be achieved typically by around ~50 large stakeholders. It is slightly more distributed than bitcoin mining pools where just 2-3 form a majority.

[Ix]

2. Stake distribution is Pareto. The protocol is optimized for Pareto distribution.

This is an untenable assumption. Given that the Pareto distribution is some kind of law (a highly questionable assumption - it may be that the existing monetary system has properties that lead to this distribution, not that it is some natural order of things), it may take decades or more for it to be realized from the network's initial stake. In the mean time, you would probably have 1 or 2 exchanges serving as your quorum.

3. I expect a quorum to be achieved typically by around ~50 large stakeholders. It is slightly more distributed than bitcoin mining pools where just 2-3 form a majority.

Even if this is the case, it is in a block creator's best interest to include signatures from small stakes as well because of the tiebreaking procedures. "Slightly more" distributed is not convincing to me, either. A protocol should strive for as much decentralization as possible where possible, not settle for something because it may be slightly better - in my opinion.

This also doesn't answer the question of how a quorum is decided if a large enough percentage of the large stakeholders are not online. Assuming that they will always be online in perpetuity to provide network security is another untenable assumption.

You may want to look into Larimer's DPOS (Bitshares, EOS) which has a limited, elected number of voters that determine consensus. It's not particularly decentralized either, but it is scalable.

[shunsaitakahashi]

2. Stake distribution is Pareto. The protocol is optimized for Pareto distribution.

This is an untenable assumption. Given that the Pareto distribution is some kind of law (a highly questionable assumption - it may be that the existing monetary system has properties that lead to this distribution, not that it is some natural order of things), it may take decades or more for it to be realized from the network's initial stake. In the mean time, you would probably have 1 or 2 exchanges serving as your quorum.

Bitcoin wealth distribution seems to be Pareto as well. https://medium.com/bambouclub/are-you-in-the-bitcoin-1-a-new-model-of-the-distribution-of-bitcoin-wealth-6adb0d4a6a95. Most researchers seem to agree that Pareto distribution is the correct distribution for wealth. Building a protocol designed for another distribution of wealth would simply be a poor design.

"Slightly more" distributed is not convincing to me, either. A protocol should strive for as much decentralization as possible where possible, not settle for something because it may be slightly better - in my opinion.

True but no one has been able to achieve it including in cryptocurrency world.

This also doesn't answer the question of how a quorum is decided if a large enough percentage of the large stakeholders are not online. Assuming that they will always be online in perpetuity to provide network security is another untenable assumption.

It is a self-selection process incentivized by block approvals. Let's say someone owns s% stake. They can earn epoch approvals by using their home computer or mobile device easily. But for ~$5/month (using a cloud server), they can double their earnings by participating in block approvals. If the increase in earnings is larger than the cost of cloud server, they are likely to choose cloud server. A cloud server is likely to have a very high uptime >99.99%.

You may want to look into Larimer's DPOS (Bitshares, EOS) which has a limited, elected number of voters that determine consensus. It's not particularly decentralized either, but it is scalable.

I have looked deep into DPOS. In my opinion, all of them (Bitshares, Steem, EOS) they are extremely weak. My first article has some details on them https://medium.com/@shunsai.takahashi/proof-of-approval-a-better-blockchain-consensus-protocol-b19a55dc331b (but note that post is not updated for protocol version 2).

[shunsaitakahashi]

2. Stake distribution is Pareto. The protocol is optimized for Pareto distribution.

This is an untenable assumption. Given that the Pareto distribution is some kind of law (a highly questionable assumption - it may be that the existing monetary system has properties that lead to this distribution, not that it is some natural order of things), it may take decades or more for it to be realized from the network's initial stake. In the mean time, you would probably have 1 or 2 exchanges serving as your quorum.
...

You may want to look into Larimer's DPOS (Bitshares, EOS) which has a limited, elected number of voters that determine consensus. It's not particularly decentralized either, but it is scalable.

Note that Dan Larimer himself believes that the stake distribution is Pareto. https://steemit.com/cardamon/@dan/peer-review-of-cardano-s-ouroboros.

[Ix]

Bitcoin wealth distribution seems to be Pareto as well. https://medium.com/bambouclub/are-you-in-the-bitcoin-1-a-new-model-of-the-distribution-of-bitcoin-wealth-6adb0d4a6a95. Most researchers seem to agree that Pareto distribution is the correct distribution for wealth. Building a protocol designed for another distribution of wealth would simply be a poor design.

Glancing through the article shows a tautological explanation. "Power Law exists therefore bitcoin distribution is Power Law." Not convincing in the least. And, as the article accepts and accounts for, bitcoin's initial distribution is highly skewed.

True but no one has been able to achieve it including in cryptocurrency world.

I would argue that the simple PoS designs that already exist do a better job than PoW at decentralization and scalability. There are some faults but they are not critical, and a smarter protocol could be designed around it to reduce the area of the remaining theoretical problems.

It is a self-selection process incentivized by block approvals. Let's say someone owns s% stake. They can earn epoch approvals by using their home computer or mobile device easily. But for ~$5/month (using a cloud server), they can double their earnings by participating in block approvals. If the increase in earnings is larger than the cost of cloud server, they are likely to choose cloud server. A cloud server is likely to have a very high uptime >99.99%.

You can't design a fault-tolerant, distributed system based on best-case scenarios. It must be resilient in the face of adversity, one of which will be an insufficient online stake. You are giving up the ghost here.

I have looked deep into DPOS. In my opinion, all of them (Bitshares, Steem, EOS) they are extremely weak. My first article has some details on them https://medium.com/@shunsai.takahashi/proof-of-approval-a-better-blockchain-consensus-protocol-b19a55dc331b (but note that post is not updated for protocol version 2).

I'll check out your article later. I'm not convinced on DPOS either but I've done little research on it.

[monsterer2]

Hello Paul,

Also note that a single honest stakeholder (hodler ) holding a relatively small stake (~.1%) will make such a history attack impossible.

I'm not totally sure I follow how that is possible. Lets discuss this before I get into any of your other questions

This is in context of long timespan History attack where an attacker acquires private keys of accounts that no longer have stake. The owners of those keys may not have much incentive to keep them private since they themselves have nothing to lose. Therefore, an attacker can acquire them relatively inexpensively. In most stake based systems, these keys must form a majority stake at some point in time. Since creating blocks for PoS doesn't require large computation, the attacker can create a large number of blocks in his favor very quickly and overtake the "real" chain.

Note that this scenario depends upon how frequently the stakes are changing in the network (churn rate). For a typical network, change of 100% network stake from one group of parties to another group is likely to take over several months if not years.

Proof-of-Approval incorporates several features that make the attacker's task difficult.

1. The chain length is counted as the number of slots spanned, not the number of blocks in it. A "real" chain is a lot more likely to have missing blocks than the attack chain. With this rule, the real chain is not penalized.

2. Epoch approvals incentivize even the smallest stakeholder (say a single coin) to participate in epoch approval. Although no claims can be made for the participation rate of epochs, it is highly likely that over a period of month or so, almost all stakeholder would have approved at least one epoch. Over a period of several months or years, it would be even larger.

3. For fork selection with epochs, stakes of all signatories (block creator, block approver, epoch approver, stake transferer) are considered. This is likely to be very close to 100% over a period of months or years.

4. If a 100% churn did occur in the period, all original stakeholders have become signatories for the real chain (100% stake!).

An attack chain can only win by exceeding signatory stake in the "real" chain. If an honest "hodler" is holding .1% stake, it isn't possible for the attacker to acquire the private keys representing the needed stake.

Regards,
Shunsai

If you're presented with two identical looking epocs, with the same blocks and different epoc signatories with equal stake, how do you pick between them?

What you're claiming is that you have a 99% attack proof protocol, because, objectively there is no difference between a history attack and an attack happening 'now'.

[shunsaitakahashi]

If you're presented with two identical looking epocs, with the same blocks and different epoc signatories with equal stake, how do you pick between them?

If two competing forks (with epochs) have absolutely equal stake (even to the billionth fraction) at the first separating block, that may result in forking the chain itself. I can't think of a solution for such a situation other than forking the chain.

What you're claiming is that you have a 99% attack proof protocol, because, objectively there is no difference between a history attack and an attack happening 'now'.

Nope. The strength of anything is determined by its weakest link. The weakest link is the short timespan consensus. The protocol can handle just under 50% (49.5% from example settings https://medium.com/@shunsai.takahashi/proof-of-approval-a-better-blockchain-consensus-protocol-b19a55dc331b). There is no protocol in existence today that can handle >=50% adversarial power.

The weakest link for a typical stake based protocol, however, is the long timespan history attack scenario. Which is the reason why all stake based protocols rely on Weak Subjectivity (https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/). Proof-of-Approval does not need Weak Subjectivity!

[shunsaitakahashi]

It is a self-selection process incentivized by block approvals. Let's say someone owns s% stake. They can earn epoch approvals by using their home computer or mobile device easily. But for ~$5/month (using a cloud server), they can double their earnings by participating in block approvals. If the increase in earnings is larger than the cost of cloud server, they are likely to choose cloud server. A cloud server is likely to have a very high uptime >99.99%.

You can't design a fault-tolerant, distributed system based on best-case scenarios. It must be resilient in the face of adversity, one of which will be an insufficient online stake. You are giving up the ghost here.

Not sure how does incentivizing nodes to achieve certain behavior, which is the very basis of the blockchains, can be considered only as the "best-case scenario."

If parties are willing to forego a large income, significantly more than the cost, they are simply not rational. Proof-of-Approval, just like every single blockchain protocol, does assume that the parties are rational. If parties are not rational, what would be motivating them to join the network and buy stake in the first place?

[Ix]

The weakest link for a typical stake based protocol, however, is the long timespan history attack scenario. Which is the reason why all stake based protocols rely on Weak Subjectivity (https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/). Proof-of-Approval does not need Weak Subjectivity!

The problem with existing PoS protocols is that they do not have weak subjectivity, as Vitalik calls it (NB: Vitalik posted this several weeks after I released my whitepaper and well over a year after this was discussed in my Decrits thread).

Vitalik:
"Fortunately, for them, the solution is simple: the first time they sign up, and every time they stay offline for a very very long time, they need only get a recent block hash from a friend, a blockchain explorer, or simply their software provider, and paste it into their blockchain client as a “checkpoint”. They will then be able to securely update their view of the current state from there."

Decrits whitepaper:
"In a ubiquitous network that Decrits would hope to be, if you don’t know what happened, then your friend or your neighbor does, or the mom and pop shop down the street does. Calling for common-sense, human input is a small concession to make when the benefit is the impossibility of double spending and true security of transactions."

PoW uses a similar scheme to prevent long-range attacks: developer checkpoints. It's another form non-algorithmic consensus (weak subjectivity).

Not sure how does incentivizing nodes to achieve certain behavior, which is the very basis of the blockchains, can be considered only as the "best-case scenario."

If parties are willing to forego a large income, significantly more than the cost, they are simply not rational. Proof-of-Approval, just like every single blockchain protocol, does assume that the parties are rational. If parties are not rational, what would be motivating them to join the network and buy stake in the first place?

You are presuming that not creating or approving blocks is only for irrational reasons. There are plenty of rational ones - like wanting turning off your computer. And uncontrollable ones like internet connectivity.

In any case, the design is very unscalable and can only be square pegged into scalability by making huge assumptions about the money distribution of the network. The more assumptions you have to make, the less powerful your algorithm is.