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

Hello Paul,


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

Hello Ix,

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


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


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.


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?


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.


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.


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


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.


I believe this is the correct approach.

Regards,
Shunsai

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.

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.


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.


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


See above.


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.

Hello Ix,


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

Hello Yj1190590,


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.



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



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

Hello Paul,


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.



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.



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.



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.



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

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.