Proof-of-Approval: Version 2.0

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

Quote

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.

Quote

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.

Quote from: monsterer2 on May 27, 2018, 03:41:01 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 05:38:21 PM

#28

Hello Paul,

Quote from: shunsaitakahashi on May 24, 2018, 04:21:13 PM

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

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 06:08:04 PM

#29

Quote from: shunsaitakahashi on May 27, 2018, 04:20:38 PM

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.

Quote

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.

Quote

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.

Quote

Quote from: shunsaitakahashi on May 27, 2018, 06:47:31 PM

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

Quote

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.

Quote

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 (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 06:47:31 PM

#30

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

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 07:41:32 PM

#31

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.

Quote

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.

Quote

3-7

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

Quote

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 (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 08:02:53 PM

#32

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

Quote from: Ix on May 27, 2018, 07:41:32 PM

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.

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 08:26:08 PM

#33

Quote from: shunsaitakahashi on May 27, 2018, 08:02:53 PM

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.

Quote

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 (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 08:50:32 PM

#34

Quote from: shunsaitakahashi on May 27, 2018, 08:02:53 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 09:05:51 PM

#35

Quote from: shunsaitakahashi on May 27, 2018, 08:02:53 PM

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.

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 27, 2018, 09:14:20 PM

#36

Quote from: shunsaitakahashi on May 27, 2018, 08:50:32 PM

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.

Quote

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.

Quote

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.

Quote

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

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 07:59:41 AM

#37

Quote from: shunsaitakahashi on May 27, 2018, 05:38:21 PM

Hello Paul,

Quote from: monsterer2 on May 27, 2018, 03:41:01 PM

Quote from: shunsaitakahashi on May 24, 2018, 04:21:13 PM

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 (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 01:13:56 PM

#38

Quote from: monsterer2 on May 28, 2018, 07:59:41 AM

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.

Quote from: monsterer2 on May 28, 2018, 07:59:41 AM

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!

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 01:33:12 PM

#39

Quote from: Ix on May 27, 2018, 09:14:20 PM

Quote

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?

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 01:59:47 PM

#40

Quote from: shunsaitakahashi on May 28, 2018, 01:13:56 PM

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

Quote from: shunsaitakahashi on May 28, 2018, 01:33:12 PM

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.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 03:39:38 PM
Last edit: May 28, 2018, 05:55:07 PM by shunsaitakahashi

#41

Quote from: shunsaitakahashi on May 28, 2018, 01:13:56 PM

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

"Weak subjectivity is the idea that subjectivity is unacceptable for short timespans, but acceptable for long timespans." https://ethereum.stackexchange.com/questions/15659/what-is-weak-subjectivity

Every stake based system that I know of (including Steem, Tezos, EOS, Cardano, Difinity) has the so called "maximum rollback slot count." That means that algorithm is unable to determine the correct fork by itself forcing rejection of a fork that otherwise would win. This results in different honest parties having different views of the chain depending upon how long they have been online. They would have to find someone "trustworthy" among supposedly "untrustworthy" parties. This is Weak Subjectivity and is highly undesirable. If one thinks that Weak Subjectivity is actually desirable, let's start another thread for that discussion.

Proof-of-Approval doesn't need Weak Subjectivity - subjectivity should never be acceptable in short timespan or long.

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

Can you point me to PoW system that does use developer checkpoint? They shouldn't need it because the external resource consumption of PoW makes it physically impossible to build chains at a faster rate than their resources would permit. With selfish mining, one can stash away mined blocks for use in attack at a later time but they would be giving up earnings now for mounting a future attack.

Quote from: shunsaitakahashi on May 28, 2018, 01:33:12 PM

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.

My quote above was in the context of a party running the node in the cloud. They do not sleep or turn off. They cost $5/month. If the benefit of additional earnings is significantly more than $5/month, a rational party would move their node to cloud.

Quote from: shunsaitakahashi on May 28, 2018, 01:13:56 PM

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.

The design in for 2018 (where cloud connectivity is at 10gbps), not for 2009 with 100mbps connectivity assumption. One can design for 100mbps connectivity but the solution would be trading off something valuable.

Regarding money distribution, I agree with Dan Larimer (https://steemit.com/cardamon/@dan/peer-review-of-cardano-s-ouroboros) that not designing for Pareto is a mistake not the other way around.

Proof-of-Approval does not require the distribution to be Pareto, but it does require the distribution to be not uniform in large group (each party holds small amount of equal stake). No cryptocurrency today has uniform distribution of stake. Proof-of-Approval is highly scalable with stake distribution of any cryptocurrency in existence today.

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 04:41:01 PM

#42

Quote from: monsterer2 on May 28, 2018, 07:59:41 AM

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.

So why wouldn't the history attacker just do exactly that, present you with an identical looking fork with a different epoc? Surely you have to pick the higher stake epoc, which has to be greater than 50%, not 99%?

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 05:05:24 PM

#43

Quote from: monsterer2 on May 28, 2018, 04:41:01 PM

So why wouldn't the history attacker just do exactly that, present you with an identical looking fork with a different epoc? Surely you have to pick the higher stake epoc, which has to be greater than 50%, not 99%?

This relates to 2.2.25 of the paper that describes the fork selection procedure. The attacker would fork from a block such that after that block there would be two possible successor blocks, one of whom is "real" and the other is the attack block.

The fork selection procedure declares winner by determining which of the forks have a higher amount of signatory stake. The real chain would have near 100% stake (assuming the block is months in past) and the attack chain will have all stake of the private keys the attacker owns. Attacker cannot copy transactions from the real chain to the attack chain since they include hash of a recent block.

Each fork must have >50% in order for blocks to be valid - that condition has to be met. But even with >50% stake, the attacker needs to exceed signatory stake that exists in the real chain. Note that signatory stake is stake of all stakeholders in a fork who have
(a) created any block, or
(b) approved any block, or
(c) approved any epoch, or
(d) signed any transaction (transferred or spent their stake) - transactions are context sensitive and contain a recent block hash

For history attack through spent keys item (d) would ensure that the signatories of the real chain hold a very high % of stake.

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 28, 2018, 06:52:33 PM

#44

Quote from: shunsaitakahashi on May 28, 2018, 03:39:38 PM

Proof-of-Approval doesn't need Weak Subjectivity - subjectivity should never be acceptable in short timespan or long.

You haven't proven that your protocol isn't subjective. In fact, you can't, or you've proved that everyone has been looking at distributed systems incorrectly forever. You must ignore all manner of attacks to do this. You would also have to disprove relativity. The distinction Vitalik and I make is weak subjectivity. e.g. It isn't that subjective, but nor is it positively deterministic, which no protocol can be anyway.

Quote

Can you point me to PoW system that does use developer checkpoint? They shouldn't need it because the external resource consumption of PoW makes it physically impossible to build chains at a faster rate than their resources would permit. With selfish mining, one can stash away mined blocks for use in attack at a later time but they would be giving up earnings now for mounting a future attack.

Bitcoin, for one.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 12:06:21 AM

#45

Quote from: Ix on May 28, 2018, 06:52:33 PM

You would also have to disprove relativity.

I was attempting for a serious and thoughtful discussion

. Not sure if we are still having that.

Quote from: Ix on May 28, 2018, 06:52:33 PM

Quote

Can you point me to PoW system that does use developer checkpoint? They shouldn't need it because the external resource consumption of PoW makes it physically impossible to build chains at a faster rate than their resources would permit. With selfish mining, one can stash away mined blocks for use in attack at a later time but they would be giving up earnings now for mounting a future attack.

Bitcoin, for one.

Here are some additional details on the developer checkpoint you provided - https://bitcoin.stackexchange.com/questions/1797/what-are-checkpoints/70824#70824

"It is a long term goal of removing the checkpoints entirely, because they are a source of confusion over the security model and power the developers have. But currently the role they serve is to prevent low difficulty header flooding attacks, and there has been no alternative solution proposed yet (that I know of)."

These checkpoints are clearly not needed for the protocol (otherwise the goal of removing them wouldn't make sense). They seem to be there because of some old software (which is being planned for update), not for protocol reasons. In other words, Bitcoin protocol doesn't need developer checkpoints and will not have any in future.

Twitter @shunsatakahashi

eli_lyd1

Sr. Member

Offline

Activity: 422
Merit: 250

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 05:48:14 AM

#46

Seems interesting, is there any project use Proof-of-Approval?

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 06:12:27 AM
Last edit: May 29, 2018, 02:14:52 PM by Ix

#47

Quote from: shunsaitakahashi on May 29, 2018, 12:06:21 AM

I was attempting for a serious and thoughtful discussion

. Not sure if we are still having that.

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.

Quote

Here are some additional details on the developer checkpoint you provided - https://bitcoin.stackexchange.com/questions/1797/what-are-checkpoints/70824#70824
"It is a long term goal of removing the checkpoints entirely, because they are a source of confusion over the security model and power the developers have. But currently the role they serve is to prevent low difficulty header flooding attacks, and there has been no alternative solution proposed yet (that I know of)."

These checkpoints are clearly not needed for the protocol (otherwise the goal of removing them wouldn't make sense). They seem to be there because of some old software (which is being planned for update), not for protocol reasons. In other words, Bitcoin protocol doesn't need developer checkpoints and will not have any in future.

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.

sapotacoin

Copper Member
Newbie

Offline

Activity: 14
Merit: 0

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 12:27:09 PM

#48

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.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 03:40:05 PM

#49

Quote from: monsterer2 on May 28, 2018, 04:41:01 PM

Quote from: shunsaitakahashi on May 28, 2018, 01:13:56 PM

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.

So why wouldn't the history attacker just do exactly that, present you with an identical looking fork with a different epoc? Surely you have to pick the higher stake epoc, which has to be greater than 50%, not 99%?

Long timespan scenario - some epochs are not common to forks

Note that there are 2 separate thresholds in play here.

1. >50% threshold for a block to be valid. If the attacker presents less stake than that, there not even an attack fork, the blocks are simply invalid.

2. When the attacker presents attack fork with valid blocks (each block having >50% approval), then the fork selection procedure comes into play. Now that procedure must choose between the real chain vs the attack fork.

3. Fork selection procedure chooses based on signatory stake. The signatory stake in the real chain would be >99% for long timespan history attacks. In order to win, the attacker must present stake greater than signatory stake in the real chain.

Short timespan scenario - epochs are common to forks

If there are no epochs contained in the attack fork, the fork with maximum approval state at the top wins. By approving a block, parties are also approving the ancestry of that block. So, the block containing the maximum stake on top wins.

Hope this explains it.

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 29, 2018, 03:47:42 PM

#50

Hello Eli_lyd1,

Quote from: eli_lyd1 on May 29, 2018, 05:48:14 AM

Seems interesting, is there any project use Proof-of-Approval?

Just started the development process.
1. It's called Takanium - agree it's a bit cheesy but will go with it for now

https://github.com/Takanium
2. One super dev on board

Looking for many many more.
3. Core would likely use Golang. Performance of C++, developer productivity of Python.
4. Smart contract white paper in process.
5. Smart contract would likely use NodeJS VM. It seems to be the best option at this time.
6. We believe in tested code. Code coverage is expected to be >90%.

Any advise you can give us is very much appreciated.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 30, 2018, 03:39:09 PM

#51

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

Quote from: sapotacoin on May 29, 2018, 12:27:09 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

May 30, 2018, 03:45:40 PM

#52

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

Twitter @shunsatakahashi

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 30, 2018, 10:17:51 PM

#53

Quote from: shunsaitakahashi on May 30, 2018, 03:39:09 PM

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. Bitcoin Cash is a fork of bitcoin that its proponents argue, subjectively, is "bitcoin". The checkpoints were hardcoded from blocks a year in the past that no one who has watched the network would argue about. The weak subjectivity that you brought up is the literally the exact same thing (except Bitcoin relies on centralized developers rather than a community), and it prevents the long-range attacks that are oft-heralded as the downfall of PoS.

The attacks that they are trying to prevent are different: for bitcoin it is primarily just a spam attack because the node can eventually objectively determine the longest chain (which is assumed to be the correct network - again Bitcoin Cash proponents would disagree), and for PoS it's rewriting the history of the network. Now while that sounds scary, the fix for both is the same, simple checkpoint. It also requires intrinsic information (stakeholder private keys) - for which you have to devise some ridiculous scenario to create an attack - vs. the extrinsic PoW which was incredibly weak at the start of Bitcoin and can be performed by anyone with a GPU.

EOS and Ripple or whatever might have different concepts of weak or regular subjectivity, but I am arguing from the perspective of my proposal which is echoed by Vitalik's blog post, and is what you referenced. And most of the "nothing at stake" issues derived from the original concepts of PoS by QuantumMechanic and implemented by SunnyKing in PPCoin, and I am admittedly not familiar enough with the newer protocols to argue for or against how they do it - but I know there is *a* way to do things safely, that asks no more of anyone than trusting the place you download the software from in the first place. Because if you can't do that, you can't ever trust that you are on the correct network. Things can only get absurd from there.

Quote

"It is a long term goal of removing the checkpoints entirely..."
Can't remove the checkpoint if it is for the protocol reasons :-)

Funny enough, I was googling to make sure these checkpoints still existed in the same way and found this coindesk article: https://www.coindesk.com/bitcoins-security-model-deep-dive/

"On a related note, every blockchain system has its genesis block hard coded into the node software. You could argue that there is a social contract to the "shared history" that is the ledger – once a block is old enough, there is an understanding amongst everyone on the network that it will never be reverted. As such, when developers take a very old block and create a checkpoint out of it, it is done more so as an agreed-upon sanity check rather than as a dictation of history."

They apparently feel the same way I do and used the same argument, the rabid "this is centralization" whiners be damned. (Not that an appeal to authority wins my argument, but I'd like to think it's an appeal to common sense, which is emboldened by other people coming up with the exact same rationale.)

Quote

This discussion is providing me new insights and I really appreciate that.

Cool, 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. It's disheartening to me to see someone spend a lot of time attempting to fix things I don't see as problematic (or have simpler solutions) that are entirely conceived of to validate proof of waste. There is *a lot* of propaganda regarding bitcoin when you start diving into the technical details. 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.

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

May 31, 2018, 09:51:39 AM

#54

Quote from: shunsaitakahashi on May 29, 2018, 03:40:05 PM

Quote from: monsterer2 on May 28, 2018, 04:41:01 PM

Quote from: shunsaitakahashi on May 28, 2018, 01:13:56 PM

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.

So why wouldn't the history attacker just do exactly that, present you with an identical looking fork with a different epoc? Surely you have to pick the higher stake epoc, which has to be greater than 50%, not 99%?

Long timespan scenario - some epochs are not common to forks

Note that there are 2 separate thresholds in play here.

1. >50% threshold for a block to be valid. If the attacker presents less stake than that, there not even an attack fork, the blocks are simply invalid.

2. When the attacker presents attack fork with valid blocks (each block having >50% approval), then the fork selection procedure comes into play. Now that procedure must choose between the real chain vs the attack fork.

3. Fork selection procedure chooses based on signatory stake. The signatory stake in the real chain would be >99% for long timespan history attacks. In order to win, the attacker must present stake greater than signatory stake in the real chain.

Short timespan scenario - epochs are common to forks

If there are no epochs contained in the attack fork, the fork with maximum approval state at the top wins. By approving a block, parties are also approving the ancestry of that block. So, the block containing the maximum stake on top wins.

Hope this explains it.

Hi Shunsai,

Why is it not possible to present two different epocs representing the same time period? That's where my attack angle was coming from.

Cheers, Paul.

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

May 31, 2018, 03:07:12 PM
Last edit: May 31, 2018, 06:25:24 PM by Traxo

#55

Quote from: Ix on May 22, 2018, 04:13:07 PM

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

Another message from @anonymint which I received in private chat.
He says that section 4.2.5 Scenario: Voices Colluding to Fork the Network is correct that with non-proof-of-work systems only the users which were online during the attack can detect malvolence and this requires bounded/partial asynchrony (i.e. not fully asynchronous as are Byteball and Hashgraph).
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.

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

May 31, 2018, 07:17:29 PM

#56

Quote from: Traxo on May 31, 2018, 03:07:12 PM

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.

I don't want to derail Shunsai's thread with my stuff unless it is a comparison with his, so after this feel free to respond in PMs or bump the Decrits thread.
No supermajority is required to be online because the order of records is determined in advance (something you went on for days about being a vulnerability - but it's not). Only some nodes are required to be online. Any nodes. The attacking nodes will be forced to fork as part of the protocol - permanently if they keep the attack going for long enough. Nodes that were not online will be required to pick a fork - my concession is that this will be big news in any kind of remotely popular network, so picking the correct network will be an easy, one time event. Because after that, all the money of the attacker's fork is destroyed, and thus the attack can't be repeated without investing a lot of money again. (Contrary to PoW and most PoS which can be repeatedly attacked.)

I also have another, whole side of making this process easier that is not documented in the whitepaper, but I'll save that for when I can alpha test.

Quote

He presumes the same vulnerability can be found in every non-proof-of-work design including Proof-of-Approval.

Probably, but I accept and embrace it.

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

May 31, 2018, 08:04:14 PM
Last edit: May 31, 2018, 09:03:54 PM by Traxo

#57

Quote from: Ix on May 31, 2018, 07:17:29 PM

my concession is that this will be big news in any kind of remotely popular network, so picking the correct network will be an easy, one time event.

This response is applicable to all nothing-at-stake systems, so I will reply in this thread.

Your reply belies the fact that @anonymint refuted it before you wrote it.
Did you not see the linked Medium post I cited for you in the prior post:

https://medium.com/@shelby_78386/the-caveat-though-is-that-when-the-attacker-can-fork-the-vested-interests-of-some-of-the-users-9340dd037a61

Public opinion can be manipulated.
Just look at every fork war that has taken place already for evidence.
There's no objectivity in public opinion.
Just a lot of chest thumping and arguments about whose furk is longer and fatter.

Quote from: Ix on May 31, 2018, 07:17:29 PM

Because after that, all the money of the attacker's fork is destroyed

Which one is the attacker's fork? Again, please read the Medium post that was cited.

Quote from: Ix on May 31, 2018, 07:17:29 PM

No supermajority is required to be online because the order of records is determined in advance

Which section of your white paper explains this?

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 06:17:44 AM
Last edit: June 01, 2018, 06:53:41 AM by d5000

#58

Hi,

I've now looked a bit into your whitepaper (the 2.0 version) and read your conversation with monsterer (the discussion with Ix is still missing, it's pretty long, but it may be worth it).

First I want to clarify that while I read a lot about cryptocurrency consensus models (specifically PoS models, as a - possible or impossible? - "solution" to the N@S problem intrigues me, e.g. Vitalik/Vlad's blogs on Casper, anonymint's and monsterer's posts etc.), I'm not a computer scientist nor a professional developer, and so maybe I am wrong in some interpretations.

Well, what I like about your protocol is that you have created something like a DPoS/BFT model without a static "delegate" set (e.g. Bitshares, Tendermint or Casper). The problem of these systems is obviously 1) the "liveness" threshold and 2) the accepted centralization which could lead to social engineering and cartel attacks. As in your system everybody can become an "approver" (of blocks or epocs), that doesn't apply. (~~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).

Some observations:

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.
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?
3) Time slots can only be orientative as timestamps can be easily faked.

I like the "delayed" epoch approvals a bit, because this way high approval rates can be reached, which make history attacks very, very difficult, although I still haven't grasped if double-voting (what monsterer mentioned) may be a problem or not (if yes, maybe a "slashing" mechanism can help). I would however make epochs pretty long (e.g. the equivalent of a day) because otherwise participation would be lower, inflation would be high, and the coin would suffer from blockchain bloat and traffic issues (imagine millions of small stakers approving multiple epochs per day ...).

Problem 1 could be mitigated with a "leasing" mechanism like in NXT or Waves that lets small stakers lease coins to big stakers with good hardware, but this has the drawback that then the social-engineering/cartel attacks like in DPoS may be possible too, only that "approval pools" would take the place of "delegates".

An interesting idea could be to only let pools approve blocks with "leased" stake but not epochs, as epochs can be approved in a delayed manner and so the participation rate would be higher.

Or, you only let stakers approve epochs, and use a more traditional PoS algorithm for the blocks.

I countinued a bit in the whitepaper and found this sentence about the double-voting problem:

Quote

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, which are unfortunately not effective (or at least, only in a small subset of problems, mainly for "unintended" forks because of network problems which get orphaned earlier by this mechanism). 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.

PS: People like @abdulkhaliq123 and @zgreenz are almost surely bots that want to achieve a higher forum rank, their posts seems to be copied-and-pasted from one of the early post in this thread. It's not necessary to answer them as machines (and more so the bots used in this forum) are still too dumb to understand consensus protocols Wink

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 01:32:20 PM
Last edit: June 01, 2018, 02:26:58 PM by Traxo

#59

Quote from: zgreenz on June 01, 2018, 01:17:56 AM

In that case, why approve blocks at all?

Who are you replying to? What specific issue are you attempting to take issue with?

Let me presume that you're trying to say that if public opinion can be ambiguous then why approve blocks at all?
If that is your point, then the answer is that proof-of-work is not ambiguous because there is an objective longest chain proven by the cumulative difficulty by adding the difficulty of all the blocks in the chain.

IOW, to avoid making posts which are noise, it is helpful to learn Bitcoin 101 before commenting here.
Anyway, educating is okay but the problem is if someone does not respond correctly, then incorrect ideas promulgate.

@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-functioning

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

Quote from: Ix on May 30, 2018, 10:17:51 PM

Well, what I like about your protocol is that you have created something like a DPoS/BFT model without a static "delegate" set (e.g. Bitshares, Tendermint or Casper).

The inviolable rule is that 100% finality of transaction confirmations can only be obtained with a permissioned validator set.
And then of course there’s the liveness issue that the chain can get stuck and require a hardfork to unstuck.
And of course what you wrote about the political corruption that results from that and/or delegating stake.
That was covered again in detail in the discussion of EOS/DPoS in @anonymint's latest blog:

https://steemit.com/cryptocurrency/@anonymint/scaling-decentralization-security-of-distributed-ledgers

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 03:52:32 PM

#60

Hello Ix,

Sorry for delay in reply

Quote from: shunsaitakahashi on May 30, 2018, 03:39:09 PM

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

Quote from: Ix on May 30, 2018, 10:17:51 PM

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.

Quote from: Ix on May 30, 2018, 10:17:51 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 04:02:33 PM

#61

Hello Paul,

Quote from: monsterer2 on May 31, 2018, 09:51:39 AM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 04:17:37 PM

#62

Hello Traxo,

Quote from: Traxo on May 31, 2018, 03:07:12 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 01, 2018, 07:42:31 PM
Last edit: June 02, 2018, 08:06:32 PM by Traxo

#63

Quote from: shunsaitakahashi on June 01, 2018, 04:17:37 PM

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

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 02, 2018, 06:28:37 PM

#64

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:

Quote

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.

Quote from: Traxo on June 01, 2018, 01:32:20 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 02, 2018, 09:48:17 PM

#65

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-functioning

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

Quote from: Traxo on June 01, 2018, 01:32:20 PM

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

Quote from: Traxo on June 01, 2018, 01:32:20 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 02, 2018, 10:09:00 PM
Last edit: June 03, 2018, 11:51:38 AM by Traxo

#66

Quote from: shunsaitakahashi on June 02, 2018, 09:48:17 PM

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

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

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 02, 2018, 10:27:10 PM

#67

Hello Traxo,

Quote from: Traxo on June 01, 2018, 07:42:31 PM

Quote from: shunsaitakahashi on June 01, 2018, 04:17:37 PM

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

Quote from: Traxo on June 01, 2018, 07:42:31 PM

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?

Quote from: Traxo on June 01, 2018, 07:42:31 PM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 02, 2018, 10:34:28 PM

#68

Hello Traxo,

Quote from: Traxo on June 02, 2018, 10:09:00 PM

Quote from: shunsaitakahashi on June 02, 2018, 09:48:17 PM

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

See 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

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 07:53:06 AM

#69

Quote from: shunsaitakahashi on June 01, 2018, 04:02:33 PM

Hello Paul,

Quote from: monsterer2 on May 31, 2018, 09:51:39 AM

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

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.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 02:31:29 PM

#70

Hello Paul,

Quote from: monsterer2 on June 03, 2018, 07:53:06 AM

Quote from: shunsaitakahashi on June 01, 2018, 04:02:33 PM

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

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 06:33:08 PM

#71

Quote from: shunsaitakahashi on June 03, 2018, 02:31:29 PM

Therefore, the signatory stake at block P is just 51%.

The honest chain wins.

Regards,
Shunsai

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.

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 07:28:00 PM
Last edit: June 04, 2018, 06:46:18 PM by Traxo

#72

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

Quote from: shunsaitakahashi on June 02, 2018, 10:27:10 PM

Definitive finality is not a function of mere majority or >2/3 but rather a property of the protocol. If the common prefix property of a protocol is probabilistic, then the finality is probabilistic and not definitive.

AFAICT, the probabilistic nature of your design is hidden in an attack on the liveness. Also there’s a synchronization (network synchrony assumption) flaw in the expiration of the slots and epochs.

The flaws in consensus systems can be very subtle. It gets quite tricky to analyze them. It seems to help in the analysis process to have a holistic conceptualization of the two major variations of Byzantine fault tolerance (BFT) which I will also explain below.

Quote

I assume this relates to finality. Ouroboros computes its common prefix property on paper's page 37 in theorem 5.2. Its common prefix is "k" with probability 1−(L/R)(CQ+CP+CG+DLS) where each of the factors are defined earlier in the paper. If I remember it correctly, I computed its k at adversarial stake of 25% and 49.5% with parameters from Cardano itself.

The comparison to Ouroboros follows in this post. I think you will see that your design shares the analogous probabilistic finality of Ouroboros. Perhaps when you quantify mathematically the flaw I have described below then you will arrive at analogous equations for your design. Although I haven’t actually dug into the nitty-gritty specifics of Ouroboros because AFAICT I don’t need to. I believe I already understand its strengths and weakness from the conceptual level, as I claim you will see below.

Quote

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

One of the drawbacks of hosting PDF files on Github the PDF can’t be objectively archived with archive.org. Thus there’s no way to capture snapshots in case the github is deleted or the edit history reverted.

I wish someone could get Github to fix that flaw. In the meantime, I wish PDFs would be alternatively hosted at a url which can be archived.

Section 1.1.1 History or Costless Simulation Attack downplays the plausibility of this quorum busting attack which AFAICT also applies to Proof-of-Approval. AFAICT, your design doesn’t eliminate this attack (c.f. near the end of this post).

I suggest that your paper should acknowledge that the attackers could have been the owners of those private keys from inception of the chain, such as for example how ICO issuers surreptiously buy the ICO from themselves awarding themselves 80+% of the token supply so they can manipulate the exchanges. That is the norm, not the exception. Or bought up at 50 satoshis per token during a cryptowinter. However, in that case you could argue that quorum busting attack is always possible at any time, and I would reply that’s true yet I think the whale oligarchs want to extract maximum rents from the system with more subtly parasitic schemes such as the following.

So selling all for BTC as they pump up the price buying from themselves on exchanges, taking leveraged short positions on exchanges, then attacking to double-spend the tokens back to themselves again which can crater the price driving up the value of their short positions. Then repeat the long-range attack as the price rises anew. Wash-rinse-repeat over and over. Nice corrupt world we live in. (Oh and don’t forget to hire some trolls to pick fights and bribe some mods to chase away those who want to write about the fraud)

Note the percentage of the stake required to attack the quorum depends on the variant of BFT employed. And for the DPoS permissioned variant then that degenerates to the quorum percentage required for electing the set of validators. Thus a DPoS system which requires only 50%+1 of majority to elect the witnesses (aka validators) degenerates from ⅔ quorums required for permissioned validation (without slashing, c.f. below). The ⅔ quorums are required for permissioned validation because alternative blocks are competing with each other due to the lack of slashing of conflicting duplicate votes (again c.f. below for the explanation of slashing). Thus a 50%+1 attack on DPoS elections can double-spent. Actually the DPoS elections are even more vulnerable than that as I explained in the EOS section of Part 1 of my latest blog.

Section 1.1.3 Nothing at Stake Attack states:

Quote

While forking attacks will be opposed by users with a
large amount of stake who will fear to lose their money, if the stake is evenly
distributed among many users, the attack is more likely to succeed.

In a consensus system with a permissionless validator set (i.e. BFT 2f + 1) and thus probabilistic finality, even if they were online at the time of the attack, users have no triangulated objectivity about which fork is the 50%+1 attacker or the “honest” fork. It’s ambiguous. Thus users they have no way to disincentivize fork attacks. A liveness attack is only by censoring blocks and/or transactions, yet the chain always moves forward if there’s at least one functioning validator. Censorship also can’t be objectively proven. Finality of a fork is measured only probabilistically. This is because it can’t be objectively proven at what time the validator set was entirely counted, because time is relative in blockchains and not absolute (i.e. not objectively triangulated) and permissionless means the validator set is not know a priori before the consensus round.

In a consensus systems with a permissioned validator set (i.e. BFT 3f + 1) and thus 100% probability of finality if the BFT ⅓-1 liveness and ⅔ safety thresholds are not exceeded, users have objectivity about forks but no objectivity about an attack on liveness. If the ⅔ safety threshold is exceeded then there's also no objectivity about forks. Censorship also can’t be objectively proven when the ⅔ safety threshold is exceeded (although it can be proven in some designs below that threshold). Finality is 100% absolute if less then ⅓ of the validator set is dishonest. If the liveness threshold is exceeded and the chain is stuck, it can’t be objectively proven if the validators are intentionally not responding.

@anonymint explained and discussed this in more detail with @Ix recently.

These are the inviolable ground rules. Any claim which doesn’t obey those rules is presumably incorrect (unless they’ve somehow derived and proven some new mathematical finding in BFT which is probably less likely than being struck by lightning).

Section 2.1 Summary states:

Quote

Approvers are allowed to approve as many blocks as they choose as
long as the approved blocks share the same parent. If not, the approvals are
considered conflicting and cannot be used.

Without clock synchronization this is the analogous flaw that I explained is in Ethereum Casper's slashing conceptualization. The conflicting approval can arrive at any time in the future. There’s no objectivity about the end of a slot or epoch unless there’s a consensus that makes the epoch final. And 100% finality requires a permissioned validator set and ⅔ quorums. Time is relative in blockchains.

The math of safety requires that (in the absence of a synchronized clock with slashing then) for a slot to be final then the quorum size must be ⅔ of the stake. @monsterer2 would be correct about the lack of safety margin in Proof-of-Approval— if not for the slashing aspect explained below. Without ⅔ quorums, the math is that there’s no safety because the overlap of dishonest validators in two elections is greater than the quorum percentage of 50%+1 and thus the finality is only probabilistic. With ⅔ quorums then the dishonest validators are at most less than ⅓ + ⅓ in any two elections which is less than the quorum size of ⅔. Again I refer readers to go read the derivation of the math which was linked already in this discussion thread already.

If you instead have assumed synchronization with an external clock (which is also a security weakness), then you can slash (delete) stake votes that vote for conflicting forks, but this converts your system to a permissioned validator set (the entire stake) and creates a liveness threshold. The 50%+1 of honest stakeholders are divided to vote on two or more block candidates such that no block attains 50%+1 because the 50%-1 attacker can choose not to vote thus making the chain stuck. If you instead only allow one block proposal per slot, the attacker can try to attack the randomization with stake grinding to always win the block election roll process. If that is proven to be intractable for the attacker (as is apparently the case in Ouroboros and Algorand), the attacker will still cause to 50%-1 of the slots to be empty. Proof-of-Approval thus does not achieve 100% finality within 1 block. So please correct your Medium post which makes that claim in comparison to Ouroboros. And the attacker can attempt to DDoS attack or bribe the roll designated block proposer for each single block for each slot. IOW, single block proposals per slot are a semi-centralized design.

Additionally the presumption of an expiration time for slots and epochs is fundamentally flawed. I (@anonymint under my other usernames such as @iamnotback or @TPTB_need_war) had discussed in 2016 why this is flawed. That discussion took place in either the decentralization thread or a thread I had created to brainstorm names for the altcoin I was developing. AFAIR, @monsterer (who is now @monsterer2) and/or @smooth had participated in that discussion. I do not have time to go digging through those long threads to find the specific posts, but from memory I recall that I had explained that there’s no way to triangulate when the end of the slot or epoch exactly occurred. Each node may have a different record of which events in the network were just before and after the expiration. There’s no possible solution, not even increasing the size of the error window that straddles the expiration tie.

Thus the slashing of votes by stake assumed by Proof-of-Approval is fundamentally flawed because it will be ambiguous which were slashed around the time of expiration. I had of course contemplated the design of Proof-of-Approval in 2015 or 2016, but discarded it as being too flawed. This is why I get frustrated w.r.t. the impact on my time (which I need for working on my project) to analyze all these various attempts to fix proof-of-stake, because they always come back to the same flaws that we had already enumerated in 2016. This is why for the past 2–3 years I have said that Vitalik et al are hyping vaporware for Ethereum scaling that can never happen. And why I have said that the DPoS that powers EOS, STEEM, CARDANO, etc can only function as an oligarchy of the stake that (often in obfuscated schemes) extracts maximum rents from the users.

Section 2.2.5 Slot states:

Quote

Each party in the network has a roughly synchronized clock that indicates
the current slot. Any discrepancies between the clocks are signifi-
cantly smaller than the length of the time represented by a slot.

This means only users that are live can know which network messages arrived within a slot and it presumes that clock synchronization can’t be attacked. It also presumes that a quorum of users observe roughly the same network synchrony and were live. Those are already notable security weaknesses (potential failure modes) which I think your design shares with Ouroboros.

Section 2.1 Summary states:

Quote

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.

Quote

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.

Quote

Epoch approvals deter History attacks.

How so? Where's the security proof?

Regarding Theorem 3.6 your paper states:

Quote

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.

Quote

Theorem 3.7 (Costless Simulation Cost). Acquiring private keys for a Costless
Simulation attack on a Proof-of-Approval chain is likely to cost dramatically
more than acquiring keys representing a simple majority in past.

Earlier in this post I provided two scenarios where the majority of the stake could be obtained for free or nearly free in the past. So why do you necessarily assume the attacker has to obtain them in the present. Proof-of-stake are oligarchy systems. The oligarchy takes ownership and then maximizes the rents extracted.

I didn’t intend to give you a bad day. Hopefully this helps you in some way not to waste time and effort. We can discuss further on Medium if you like where I am not banned. I will probably reply to one of your Medium, so you can respond to me there if you wish. Cheers also. Hopefully we’ll find a good solution for secure, decentralized, scalable consensus systems but physics may force us to pick any two of those three attributes.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 08:09:21 PM

#73

Hello Paul,

Quote from: monsterer2 on June 03, 2018, 06:33:08 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 08:35:30 PM
Last edit: June 04, 2018, 07:08:08 PM by Traxo

#74

Quote from: shunsaitakahashi on June 03, 2018, 08:09:21 PM

Quote from: monsterer2 on June 03, 2018, 06:33:08 PM

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.

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.

Quote from: monsterer2 on June 03, 2018, 08:38:17 PM

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.

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.

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 03, 2018, 08:38:17 PM

#75

Quote from: shunsaitakahashi on June 03, 2018, 08:09:21 PM

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

BitcoinSaving

Newbie

Offline

Activity: 38
Merit: 0

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 12:11:26 PM

#76

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

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 03:52:21 PM

#77

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:

Quote

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

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:

Quote

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:

Quote

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.

Quote

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

Quote from: shunsaitakahashi on June 03, 2018, 02:31:29 PM

Quote

Epoch approvals deter History attacks.

How so? Where's the security proof?

Regarding Theorem 3.6 your paper states:

Quote

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.

Quote from: Traxo on June 03, 2018, 08:35:30 PM

Quote

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 03:58:16 PM

#78

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 04:02:52 PM

#79

Hello Paul,

Quote from: monsterer2 on June 03, 2018, 08:38:17 PM

Quote from: shunsaitakahashi on June 03, 2018, 08:09:21 PM

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

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 06:19:12 PM

#80

Quote from: shunsaitakahashi on June 04, 2018, 04:02:52 PM

Hello Paul,

Quote from: monsterer2 on June 03, 2018, 08:38:17 PM

Quote from: shunsaitakahashi on June 03, 2018, 08:09:21 PM

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

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

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 06:29:30 PM

#81

Hello Paul,

Quote from: monsterer2 on June 04, 2018, 06:19:12 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 06:49:25 PM
Last edit: June 06, 2018, 09:05:37 PM by Traxo

#82

Made some edits to this posts:
https://bitcointalk.org/index.php?topic=3913439.msg39309531#msg39309531

@anonymint wrote on Medium:

Quote

Hello Shunsai Takahashi.

As you know in your bitcointalk.org thread, @‍monsterer2, others, and I discussed some vulnerabilities in your Proof-of-Approval (PoA) consensus system. Specifically I pointed out that in plausible reality there’s not 100% finality because due to the requirement for 50+% of the stake to always be online that PoA analogous to all proof-of-stake systems really only function because they’re run by a 50+% oligarchy. Proof-of-stake does not function well without an oligarchy in control. Thus the 50+% attack is the norm, not the exception. Normally the oligarchy in control is benevolent in terms of double-spending and extracts their rents via other schemes. Some typical figures I’ve seen cited for stake participation are at most 30% of the stakes. The implication of this is that the table in your blog which compares your PoA system to Nakamoto proof-of-work seems disingenuous in light of all the details as I explained. Although the end-game of proof-of-work is apparently also an oligarchy. Perhaps your table’s comparison to Ouroboros was at the time of writing this message correct to claim PoA’s advantage of one (1) block transaction confirmation finality compared to Ouroboros’ 100s of blocks because Ouroboros (in the non-delegated mode) also has the same vulnerability of requiring 50+% of the stake to always be online. I need to study Ouroboros more carefully in the future, which I may do for the upcoming Part 3 of my recent blog.

Paul explained that PoA also is vulnerable to the typical nothing-at-stake (NaS aka N@S) flaw which plagues all proof-of-stake systems. The NaS attack only applies to a 50+% attack. The problem is that although Nakamoto proof-of-work is also vulnerable to a 50+% attack, unlike NaS there’s an ongoing cost to attack proof-of-work. In theory it’s plausible to recover the costs of a rented hashrate attack by double-spending, but in practice no one thinks that is very realistic on Bitcoin with its tremendous systemic hashrate. And proof-of-work is permissionless yet proof-of-stake is not.

If we could argue that 50% of the stake is difficult for an attacker to obtain and if the slot and epoch slashing (of conflicting approvals) didn’t have the boundary ambiguity problem, then AFAICT the NaS issue would be somewhat mitigated. But unfortunately, I don’t think 50% of stake is difficult for an attacker to obtain and anyway the presumption that 100% of the stake will always be live is unrealistic.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 08:04:04 PM

#83

Hello Traxo,

Quote from: Traxo on June 04, 2018, 06:49:25 PM

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.

Quote from: Traxo on June 04, 2018, 06:49:25 PM

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.

Quote from: Traxo on June 04, 2018, 06:49:25 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 08:45:38 PM
Last edit: June 04, 2018, 09:01:41 PM by Traxo

#84

Quote from: shunsaitakahashi on June 04, 2018, 08:04:04 PM

Quote from: shunsaitakahashi on June 04, 2018, 03:52:21 PM

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.

You are quoting out-of-context. Please kindly review the context in which the above quote was written.
@anonymint knows that you currently have multiple block candidates per slot in PoA.
The reference to a single-block candidate per slot was because you must change to a single block candidate to try to fix the vulnerability he explained exists with the multiple block candidates.

This discussion is going become very confusing if quoting and responding out of context.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 09:00:37 PM

#85

Traxo,
My apologies - yes discussion can get confusion as I did get confused with that line.
Shunsai

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 09:01:47 PM
Last edit: June 04, 2018, 09:35:08 PM by Traxo

#86

@anonymint replied:

Within the bounds of stated conditions Proof-of-Approval achieves finality within 1 block.

In all due respect, I presume you have not understood the vulnerability I described which I will quote again for you because AFAICT you have not responded to the specifics of the vulnerability:

Quote from: shunsaitakahashi on June 04, 2018, 08:04:04 PM

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. [...] So please correct your Medium post which makes that claim in comparison to Ouroboros.

I think you have not yet understood that by not approving (i.e. not voting for) any candidate blocks the attacker can make the chain stuck because the honest stake will become divided-and-conquered by voting on different candidate blocks for the same slot. The vulnerability is a little bit convoluted. Do you understand now?

Thus the math of finality will relate to the relative stake of the honest and attacker and the probability of honest stake being divided on multiple block candidates.

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.

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.

Okay thanks for the clarification.

AFAICT, this does not apply to the vulnerability of multiple block candidates dividing the honest vote which I already described, except perhaps to make it worse by proliferating forks.

However, open ended slots and epochs thus make finality indefinite. There is no longer finality within any time limit. So it is deceptive to compare finality by counting blocks when blocks can be indefinitely delayed.

Also how can subsequent blocks and epochs complete when blocks may arrive late at any time in the future? Does that mean many candidate parent forks?

My intuition is afraid this is going to open many attack vectors. But we'll need to analyze in detail.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 09:27:19 PM

#87

Hello Traxo and @anonymint,

Quote from: shunsaitakahashi on June 04, 2018, 09:27:19 PM

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

Quote

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 09:31:58 PM

#88

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.

I will repeat what I wrote with emphasis:

Quote from: Traxo on June 04, 2018, 09:01:47 PM

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.

It seems your system will not converge on a single fork then. Which is the same as getting stuck.

It is impossible that you have 1 block finality and 50% quorums (in any meaningful definition of 'block'). Breaks the invariants of physics. We will find the flaw.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 09:58:02 PM

#89

Hello Traxo and @anonymint,

Quote from: Traxo on June 04, 2018, 09:31:58 PM

Quote from: Traxo on June 04, 2018, 09:01:47 PM

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

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 04, 2018, 10:06:55 PM
Last edit: June 05, 2018, 07:21:37 PM by Traxo

#90

@shunsaitakahashi, AFAICT tie breakers within a fork does not address the situation in which the stake has numerous choices of parent forks to choose from. I think the flaw will have something to do with no definite interval in which blocks can arrive for slots.

I'm afraid we are going to need to sleep and study the paper again and come back with a more detailed explanation. I think we are talking back and forth here and not really understanding each other.

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 05, 2018, 07:44:32 PM
Last edit: June 06, 2018, 08:45:10 PM by Traxo

#91

I received this reply from @anonymint. Note this is corrected from a post made several hours ago by @kennyP which was quickly (within a couple of hours) deleted when @anonymint independently discovered the holistic error in his conceptualization of PoA.
Thanks to @shunsaitakahashi for deleting his reply to that rescinded post, and apologies to him for wasting his time on that rescinded reply.

PoA whitepaper Section 2.1 Summary says:

Quote from: PoA whitepaper

A network using this protocol publishes blocks periodically at a predefined interval called slot.

“Predefined interval” implies a time interval unless otherwise stated. Yet you wrote in this thread that block approvals never expire because block proposers (aka “creators”) can continue to accept approvals for an indefinite period of time. So I was perplexed what is the meaning of “interval” in this context. But then later on I realized that slots are intended to have an expiration interval which is much longer in duration than the typical block approval completion time. Unfortunately your whitepaper didn’t make this easy for me to grok. I had to reverse engineer this understanding as you will see below as light bulb finally came on in my head as to the holistic design of your system.

I was pondering if you meant that the interval of each slot is measured as one and only one block. And by now I realize that would be an incomplete statement and instead you really mean what I wrote in the above paragraph.

Quote from: PoA whitepaper

Time is divided into discrete units called slots.

1. Each party in the network has a roughly synchronized clock that indicates the current slot. Any discrepancies between the clocks are significantly smaller than the length of the time represented by a slot.
2. The length of the time represented by a slot is significantly larger than the time needed to transmit messages or blocks from one party to the other.

The item #2 obfuscates that the real point is that the slot time is significantly greater than the typical time to approve a block. That is crucial for forming the Schelling point which makes voting incentives work correctly as I will recapitulate below.

My description of your system below might help others better understand PoA.

Quote from: PoA whitepaper

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.

Quote from: PoA whitepaper

Nodes are allowed to approve as many candidate blocks as they choose as long as they share the same parent block. In Figure 3, a node can choose to approve either D by itself or D’ and D" for the slot. But if it were to approve D as well as D’, since those don’t share the same parent, those approvals would be called “conflicted” and are rejected during validation.

The questions I originally had until I finally grokked the holistic design of PoA were as follows. How are conflicting approvals detected if they can arrive at any indefinite time in the future? How can anything ever become final if an attacker withholds a conflicting approval and broadcasts it at some indefinite time in the future? How does the chain determine which broadcast came first since network is not perfectly synchronized? IOW, it seemed to me that PoA would still need an expiration timeout on how long of a wait before the window of conflicting approvals is final. And with an expiration time the PoA design would revert back to the flaws I identified which is the ambiguity around the boundary of an expiration time.

IOW, I intially was stuck on the thought that conflicting approvals is the analogous dilemma as double-spent transactions. I thought you shifted the problem of detecting and preventing double-spent transactions into detecting and preventing double-spent approvals. And thus AFAICT made no actual progress on a viable consensus system. And I originally thought that all that has been accomplished is obfuscation of a flaw in a complex system description.

However, then the holistic understanding finally clicked into my mind as to how the security and game theory works in PoA. So now I will explain my (I am reasonably certain now) correct understanding as follows.

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

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.

Which is roughly the same outcome as DPoS. And the latency of confirmation and unsharded scalability for PoA is unlikely to be any better than DPoS when they’re both effectively running as (distributed but) entirely centralized oligarchy systems. Since PoA doesn’t currently propose sharding, we’ll not discuss the potential issues with EOS’ (centralized oligarchy) sharding here.

Quote from: PoA whitepaper

Transactions include hash of a recent block and therefore are “context sensitive”[12]. This prevents transactions from being used in an attack fork.

TaPoS is probably effective against the long-range 50%+1 attacker who had 50%+1 of the stake in the distant past, unless that attacker still maintains 50%+1 of the stake in the present. Because current hodlers of UTXO are unlikely to vote for a fork that has stolen their tokens.

Thus note that if the attacker held for example 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.

Worse yet, much of the stake may not participate in consensus voting and thus the attacker needs much less than 50%+1 of the stake in order to a 50%+1 attack on the consensus approvals. Somehow honest stakeholders must be able to delegate their stake power at all times when they are offline.

So for TaPoS to be effective is highly dependent on a non-manipulated distribution and a healthy uninterrupted market demand for the tokens, so that the normal power-law distribution of wealth with 50% held by the masses holds true. I had explained before this is usually not true in altcoins because of fraud and manipulation, such as issuers buying the ICO from themselves.

Here follows some thoughts I had before I grokked the holistic design of PoA, which have been edited to incorporate my current holistic understanding.

Quote from: PoA whitepaper

Each node collects approvals of its candidate block and computes its approval stake. Any approval with conflict or zero stake is ignored. If the node’s candidate block’s approval stake exceeds quorum, it broadcasts an approval block to the network.

Before I formed my holistic understanding, I was thinking PoA was designed with a presumption that once a block is broadcasted that it takes precedence to a block that is not yet broadcasted which receives a conflicting approval. But there’s no way to prove which block was broadcasted first without consensus about which block was first. Yet consensus is what PoA is trying to achieve. Thus I thought PoA had a hen-egg dilemma. This is what I referred to in one of my prior posts as quoted below:

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.

That is why I wrote I thought we were not understanding each other. I thought you did not fully appreciate the significance of what I wrote before. But now with the holistic understanding of the design, I realize that unless the attacker has a 50%+1 control, then a block with 50%+1 approval is final. But the flaw is that no blocks are likely to get 50%+1 approval without 50%+1 oligarchy in control! Even if you presume multiple completing staking groups vying for mining rewards, the only equilibrium is when they come together to form an oligarchy, because the oligarchy can extract more rents than they can as competing groups. This is a Prisoner’s Dilemma.

Quote from: PoA whitepaper

A node can broadcast an improved version of its approval block when it receives additional approvals or when it detects approval conflict. Receiving nodes use the approval block with the most stake to create their candidate block for the next slot.

Before I formed my correct holistic understanding, I was thinking but how can the block creators for the next slot decide which approval block has the most stake when that stake can decrease if approval conflict is later detected? And when does the block creator for the next slot begin if the finality of the winning approval block is indefinite and never final? I was incorrectly thinking that the ability to slash conflicting approvals is analogous to the ability to double-spend. That it opens a liveness vulnerability which kills any finality. That it was in essence the point I’ve been making since the prior page of this thread and since 2016.

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.

Quote from: PoA whitepaper

When the approvals exceed the required quorum stake, the block creators broadcast the collected approvals to the network.

Again here were more of my (now irrelevant) thoughts before I grokked the holistic design of PoA. How does PoA protocol force them to broadcast at that moment? What if the attacker decides to delay for an indefinite time? How does PoA penalize delays? Incentivizing with the block creation award doesn’t penalize delays because: a) block awards are never final because an attacker can send conflicting approvals at any time later, b) the attacker may not be interested in awards, because he can short the token if he can stall the progress of the chain.

The Theorem 3.2 (Weak Finality and Finality) has a correct but misleading and somewhat irrelevant (but not entirely) proof:

Quote from: PoA whitepaper

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.

~~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 honest stake is always live and always votes correctly.

Problem is that proof-of-stake does not function well without an oligarchy in control. Thus 50+% attack is the norm, not the exception. Normally the oligarchy in control is benevolent in terms of double-spending and extracts their rents via other schemes.

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 09:51:31 AM
Last edit: June 06, 2018, 02:52:42 PM by monsterer2

#92

Hi Shunsai,

I have some ideas for you which might help your NaS problem. I developed an aborted Proof of Burn concept ages ago(*) which I've recently revisited and it might have some ideas you can use:

This is a brief summary of how it works:

* Participants compete to win block reward by burning stake
* A block can be proposed when burnt stake >= block reward
* Block reward is divided out between all participants in proportion to their burnt amounts

An attacker attempting to dominate the block generation process by proposing a block containing only his burnt stake will always lose out once his block is published, because other participants can propose a better block containing his burnt stake AND their burnt stake. So, at the limit if he burnt the block reward in his private block, what he gets back is less than his burnt stake once he published his block due to the above possibility, so he will lose money this way.

In order to double spend his only option is create a massive chain of private blocks and then submit that later. But, if we instead adopt your slot mechanism, it would be impossible for this attack to succeed because he cannot propose more than 1 block at a time.

We can also employ your double voting exclusion mechanism so that if he burns on two chains at the same time, he will lose his stake completely.

The only major problem I can see here is that there is no objective way to verify a slot and the boundary(s) thereof, so we have history attack problems.

Anyway, hope that gives you some ideas

Cheers, Paul.

~~edit: I still have an open question raised by shelby, if we're discarding double votes inside a slot, why don't we just do that for double spends and scratch the entire voting process completely?~~ This is due to the subsequent invalidation cascade which would make discarded double spends cost free for the attacker

*) https://bitcointalk.org/index.php?topic=1182677.msg12446394#msg12446394

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 01:18:59 PM

#93

Hi Shunsai,

thank you for your answer and sorry for the late response. I have been trying to read through the whole discussion between you, monsterer, Traxo/anonymint, and Ix, to understand the potential and possible flaws of the proposed protocol. There are some points that I must re-read to fully grasp them (as I said I'm not really an IT guy, and English is also not my native language).

But generally, I think your proposal is a valid and interesting contribution to the proof-of-stake (or non-proof-of-work) consensus algorithm discussion. It is clear that the Nothing-at-stake problem probably cannot be fully solved without some kind of external resources consumption. But attacks on it can be made harder. Even if PoA is somewhat similar to DPoS as @anonymint notes, it is not fully permissioned (i.e. new validators can always enter, acquiring stake, and don't have to wait for a "voting cycle") so I regard it as an improvement over DPoS. The "oligarchy-rewarding-effect" is, unfortunately, a consequence of all PoS-based protocols I know.

Regarding our discussion about liveness - which in my opinion is the main challenge PoA faces: It's funny that monsterer posted a proof-of-burn-based proposal just yesterday, as I was also about to propose a proof-of-burn-related "expansion" of the protocol which could make history/N@S attacks more difficult and increase liveness. monsterer's proposal looks interesting; I have to analyze it further. I mainly know the Slimcoin protocol (very close to Iain Stewart's original PoB proposal). This protocol is more similar to traditional ("naive") proof of stake - "burners" get a score according to the quantity of burnt coins, and get the possibility to find blocks for a long time (years) - but its consequence is a relatively stable and big validator set, as "burners" will always try to be online to collect rewards because their only chance to get back the burnt stake is in the form of block rewards (it's actually very similar to "extremely long security stake deposits") . And "burners" are likely to be also "stake holders", so the inclusion of PoB would also drive liveness for block approvals - it could be a driving factor to move from the 30% "live stake" of a typical PoS coin to the 50%+ PoA requires.

The drawback of this "naive" proof-of-burn protocol is, however, that you can 51% it relatively cheaply because it's unlikely that more than 10% of the currency's supply is burnt and actively minting at the same time, and it's also vulnerable to most N@S attack variants. But what you could do is to require a minimum quantity of single PoB blocks (never more than one in a row, so 51%ing purely based on PoB becomes impossible) every X slots. Even then, the liveness-boosting effect should be achieved, and an attacker would have to care about additional double spends to create the proof-of-burn blocks he needs.

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 05:32:47 PM
Last edit: June 06, 2018, 07:47:45 PM by Traxo

#94

Even if PoA is somewhat similar to DPoS as @anonymint notes, it is not fully permissioned (i.e. new validators can always enter, acquiring stake, and don't have to wait for a "voting cycle") so I regard it as an improvement over DPoS.

My understanding and presumption based on the mentions in the whitepaper is that PoA necessarily requires that the stake ownership and newly minted stake change slowly because otherwise presumably the proofs of conflicting approvals by way of public-key signatures would not protect against the double-spending of approvals on conflicting parent blocks. Tangentially note again from my prior post that the protection is only valid if there’s no 50%+1 (aka 50+%) attacker.

Thus AFAICT in essence it’s also a permissioned system wherein if the 50% liveness threshold is exceeded then the chain becomes stuck and there’s no way for it to move forward. Even disregarding the slow moving stake change requirement, note a 50+% attacker could indefinitely stall the consensus because he can prevent 50+% approvals (i.e. approved blocks) from being obtained. The time intervals for slots are only for forming the Schelling point on approvals around the latest slot that had an approved block, can’t be a permissionless means of transitioning to a new set of approvers, because there’s no objectivity about such passage of time if no blocks have been approved in those slots. That would be a flaw in the design if that is being proposed. Stake can’t change without block approvals so I presume that isn’t being proposed.

(Btw, this is a point that really irritates me about Dan Larimer because he tries to claim that DPoS can just replace the non-responding witnesses if the liveness is exceeded by allowing the responding witnesses to vote on the new replacements, but that breaks the math on Byzantine agreement because the old witness can be lying in wait and release a conflicting fork)

Thus if the above is correct, then we can only claim PoA is less permissioned in the sense that all of the static stake can participate. But it’s not permissionless like proof-of-work where new external resources can participate without any permission. This is why proof-of-work can never get stuck and has no liveness threshold. The only analogy to a liveness threshold in proof-of-work is that a 50+% attacker can censor transactions but can’t stop the chain from producing blocks and moving forward (well perhaps an attacker could subdivide the chain into many forks to stop finality of consensus).

My definition of permissionless in this context is that the existing stakeholders can’t stop new outside resources from coming onboard to unstuck the chain. In that case, I think PoA is not permissionless. Others may define permissionless to be the likelihood that an attacker can take control and censor transactions.

I understand you are wanting to draw a distinction from DPoS’ election process which is inherently advantageous for an attacker who has less than 50+% of the stake, because most of the stake doesn’t vote in elections, and because the honest stake trusts only themselves or close friends so they often divide-and-conquer their votes on many delegate candidates they know well who do not get elected.

So PoA doesn’t have these undesireable delegation elections, but instead has virtually implausible liveness unless a vested oligarghy is involved to always be online and prevent the chain from becoming stuck.

Regarding our discussion about liveness - which in my opinion is the main challenge PoA faces

I agree that if somehow the liveness issue could be improved, then that would be a notable advantage over DPoS. I believe in even Ouroboros has a delegated mode because it also otherwise requires 50+% of the stake to live always. Perhaps PoA is superior to Ouroboros because Ouroboros has the same liveness issue but has only probabilistic confirmation whereas PoA has 1 block confirmation if not under 50+% attack? I need to check into that and correct prior misstatements if so.

And "burners" are likely to be also "stake holders", so the inclusion of PoB would also drive liveness for block approvals - it could be a driving factor to move from the 30% "live stake" of a typical PoS coin to the 50%+ PoA requires.

I think the burning needs to be lossy so that an attacker can’t get back all he burns (to mitigate the issue I discuss below). But then would anyone be motivated to burn? A lottery effect is needed but that usually only works on irrational people, not the astute businessminded who would remain online always.

However I disagree that the liveness issue is the only main challenge...

Quote from: monsterer2 on June 06, 2018, 09:51:31 AM

The "oligarchy-rewarding-effect" is, unfortunately, a consequence of all PoS-based protocols I know.

The block rewards in PoA incentivize the existence of a 50+% attacker to exist even if that attacker only uses that control to take all the block rewards for himself and not to double-spend. Remember unlike proof-of-work, there’s no cost to doing an attack once the stake is obtained and stake can be obtained at low cost. The problem is that attacker then exists and can at any time do censorship and double-spends. So it is inherently not permissionless and trustless. However, in the end-game proof-of-work must be run by an oligarchy also. Proof-of-work is a transition scheme to centralized global order, not a permanent decentralization.

We can also employ your double voting exclusion mechanism so that if he burns on two chains at the same time, he will lose his stake completely.

Burning has no well defined total burn, so the Byzantine agreement math I explained can’t be applied. You would need at least 50+% of total possible burn in order to declare finality of approval, in order to slash the double-voting of burns (for burns acting as approvals).

Burning can only function in a probabilistic finality analogous to proof-of-work. Yet without the all the positive attributes. Doesn’t burn an external resource, isn’t permissionless as I defined it above, and apparently doesn’t really solving the N@S issue.

@d5000 instead appears to be proposing burning as a means of incentivizing more of the stake to be online to try to address PoA’s liveness weakness.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 07:40:32 PM

#95

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:

Quote from: PoA whitepaper

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.

Quote from: monsterer2 on June 06, 2018, 09:51:31 AM

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

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 08:05:06 PM

#96

Hello Paul,

I have some ideas for you which might help your NaS problem. I developed an aborted Proof of Burn concept ages ago(*) which I've recently revisited and it might have some ideas you can use:

This is a brief summary of how it works:

* Participants compete to win block reward by burning stake
* A block can be proposed when burnt stake >= block reward
* Block reward is divided out between all participants in proportion to their burnt amounts

An attacker attempting to dominate the block generation process by proposing a block containing only his burnt stake will always lose out once his block is published, because other participants can propose a better block containing his burnt stake AND their burnt stake. So, at the limit if he burnt the block reward in his private block, what he gets back is less than his burnt stake once he published his block due to the above possibility, so he will lose money this way.

In order to double spend his only option is create a massive chain of private blocks and then submit that later. But, if we instead adopt your slot mechanism, it would be impossible for this attack to succeed because he cannot propose more than 1 block at a time.

We can also employ your double voting exclusion mechanism so that if he burns on two chains at the same time, he will lose his stake completely.

The only major problem I can see here is that there is no objective way to verify a slot and the boundary(s) thereof, so we have history attack problems.

Thanks for pointing it out! I have yet to fully grasp "burning" and its implications. Therefore, I need to think about it to make a half way intelligent comment on it

.

Quote from: monsterer2 on June 06, 2018, 09:51:31 AM

~~edit: I still have an open question raised by shelby, if we're discarding double votes inside a slot, why don't we just do that for double spends and scratch the entire voting process completely?~~ This is due to the subsequent invalidation cascade which would make discarded double spends cost free for the attacker

I think what you are referring to conflicting approvals that come after a block has been placed in chain. Let's use this example of two forks separated from block D.

Code:

A B C D E F G H I J
        P Q R S T U

If there are no epochs (which are not shared) in the competing forks, the preferred fork determination procedure chooses the fork with head block containing the largest approvals. If a party were to approve block E (and the approval is stored in F) and later he decides to create a conflicting approval (for some block X not shown) in an attempt to nullify his approval for E so that his attack chain (PQRSTU) can win, that approval (for X not shown) would have no effect. The fork selection procedure would compare approvals stored inside J and U. The fork with higher stored approval wins.

Regards,
Shunsai

Twitter @shunsatakahashi

Traxo

Hero Member

Offline

Activity: 568
Merit: 703

Re: Proof-of-Approval: Version 2.0

June 06, 2018, 08:30:14 PM
Last edit: June 06, 2018, 09:04:33 PM by Traxo

#97

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

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.

Actually I had asked Traxo to remove the ‘live’ then I rescinded because I was too sleepy (forehead on keyboard) to think it through. Then I forgot to come back to it.

So thinking it through now, the 50+% (aka 50%+1) threshold has to be attained for a block to be approved and proposed to be final which is what dictates the liveness issue as well, but that doesn’t guarantee all the stake is available live. Yet you’re correct that the attacker still needs to slash 25+% and have another 25% in reserve to double-spend with regardless. The decreasing amount of participation doesn’t reduce the safety. So I stand corrected on that point.

Note for readers, that your precise percentage factors in the amount of stake that is allowed to change in each slot, which is a point I mentioned in my prior post (in the part about permissioned versus permissionless). That’s why it is slightly less than 50%.

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.

That is an interesting coherent point-of-view. I did argue in this thread that will become an oligarchy because there is more profit to be made from an oligarchy that can extract maximum transaction fees. You haven’t yet explained how you can prevent transaction spam without fees. However, in your defense see the comment in my prior post where I link to a detailed explanation how proof-of-work also MUST become an oligarchy:

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

However, in the end-game proof-of-work must be run by an oligarchy also. Proof-of-work is a transition scheme to centralized global order, not a permanent decentralization.

Have you considered allowing stakeholders to delegate their approval voting powers to other stakeholders, so they can rent it out? I think that would help you achieve near 100% liveness, especially if you could make it the default and automate it somehow.

Then you could consider increasing the safety to 67% from 50%.

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.

Correction. The TaPoS is necessary so that the long-range attacker can’t rewrite the chain keeping most of the transactions but double-spending a minority of them. This prevents the divide-and-conquer strategy. With TaPoS, the attacker must take all of the history and can’t chop it up. @anonymint recently wrote a reply to Vitalik about this point.

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

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.

I still can’t grok that section of the whitepaper. What do you think is different about epochs that would increase participation? Anyway, maybe my idea above is better?

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

2. Parties are not rational.

They can be entirely rational. Their opportunity cost can be too high. We don’t have time to do everything in life. We must choose priorities. Small stake rewards is a low priority.

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

Explanation above applies here. Under the rationality and stake distribution assumption in the paper, the theorem is correct and relevant.

Okay maybe it becomes more relevant in light of this discussion now.

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

Online stake requirement (for liveness) is only >50% not 100%

Yeah that is a repeat of the error that I conceded at the top of this reply. All instances of that misstatement will be corrected.

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 12:45:21 AM

#98

Hi Traxo,

Quote from: anunymint on June 07, 2018, 01:59:10 AM

Thus if the above is correct, then we can only claim PoA is less permissioned in the sense that all of the static stake can participate. But it’s not permissionless like proof-of-work where new external resources can participate without any permission.[...]My definition of permissionless in this context is that the existing stakeholders can’t stop new outside resources from coming onboard to unstuck the chain. In that case, I think PoA is not permissionless.

Yes, there is some ambiguity about what "permissionless" means, and in general terms I support your definition. But working Proof-of-stake currencies always offer a market (otherwise they weren't currencies) where units can be traded to goods or other currencies or tokens, so in practical terms it cannot be avoided by the stakeholders that other people enter the system and become part of the validator (in this case, of the approvers) set. You are correctly pointing out that the requirement to move stake slowly means that the process is restricted. This would, however, only affect whales wanting to become part of the validator set fastly, the average user (and the average stakeholder) shouldn't be affected as the market will continue to move.

Quote

I understand you are wanting to draw a distinction from DPoS’ election process which is inherently advantageous for an attacker who has less than 50+% of the stake, because most of the stake doesn’t vote in elections, and because the honest stake trusts only themselves or close friends so they often divide-and-conquer their votes on many delegate candidates they know well who do not get elected.

So PoA doesn’t have these undesireable delegation elections, but instead has virtually implausible liveness unless a vested oligarghy is involved to always be online and prevent the chain from becoming stuck.

That's why I wrote "not fully permissioned" - in DPoS, depending on the amount of validators, a group of whales can easily obtain total control of the validator elections, while in PoA this kind of control seems theoretically possible, but very impractical - if the liveness problem can be solved. It would need a very big group (supermajority) of colluding whales to seriously restrict newcomers being part of it.

Quote

I think the burning needs to be lossy so that an attacker can’t get back all he burns (to mitigate the issue I discuss below).

I don't understand fully - if burning is only a complement of an otherwise PoS-based algorithm which has the main goal to improve liveness then I see no problem here. The necessary rule for that is that never two PoB blocks are allowed in a row, so a "PoB-only" attacker could only trick users into a double spend that wait for one single confirmation, otherwise he must obtain a majority of the stake. In this case, in PoA, the "one-block-finality" rule would have to be modified to "one-PoA-block-finality" as PoB, as you correctly write, cannot achieve 100% finality.

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 03:58:41 AM

#99

If 50% of the state becomes non-responding, then the chain can be stuck forever. No transactions will be confirmed. And thus no stake can change, not even slowly.
[...]
The accumulated lost keys over time is serious problem that needs some solution.

OK, I overlooked that problem. You're totally right that this makes the liveness problem more severe, and I agree that in this case we would very likely need a distinction between the validator set and the total "currency-holder" set.

Quote from: anunymint on June 07, 2018, 01:59:10 AM

I seem to strongly disagree with your characterization of reality. Why do you think it is impractical for an attacker to obtain 50+% of the stake?

My argumentation in this case is based on the assumption of a mature and relatively well-distributed currency with some actual real usage, at least as much as our current Bitcoin, not like an "average altcoin". You're totally right that in most current altcoins, and more so in new ones, it's relatively easy to get a high stake participation. (That's also why I'm becoming increasingly critical to ICO-distributed cryptocurrencies, and why I started this thread for example [which got buried instantly by spam, obviously].) But in a mature currency it should be very hard to get even 25%.

All cryptocurrencies have to begin at some point and so in its early phase they will be weak to attacks if using pure PoS. In my opinion, a prolonged proof-of-work phase is the way to go for current altcoins if they want to achieve some resistance to 50+1% stake attacks, if no new ideas are found for this problem. It has to be noted that a PoW phase doesn't solve everything because mining could also be centralized (e.g. like in Steem's PoW phase) and PoW 51% attacks are also not totally uncommon as we saw recently. But for now we have nothing better, afaik.

So in general terms I think we're not so much in disagreement in this point.

Quote

Firstly, my underlying point is that if PoA is 50+% attacked normally, then the attacker will also be receiving all the burned rewards. So I wanted to find a way to reduce the rewards that a 50+% attacker receives. Secondly, given that PoB can’t be 100% final, then there’s no Schelling point for the PoA block to base on, which thus breaks the game theory that I explained allows PoA to presume that all honest approvers will vote for the same parent block. In short, your idea breaks PoA. Can’t work. Let me know if I need to explain that in more detail?

I think I understand - we would be mixing a system with probabilistic finality and a system that relies on 100% finality of every block, is that right? I'll think a bit about it and try to re-read the related points in the discussion (a problem for me is that it is advancing pretty fast ...).

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 08:42:48 AM

#100

The accumulated lost keys over time is serious problem that needs some solution. That is another reason I am proposing that stake needs to opt in to participation with an extended waiting period before becoming eligible to send approvals and becomes ineligible if not participating for an extended period of time. Then must opt-in again with another extended waiting period. Note @Ix’s Decrits suggestion of having stakeholders sign their election to become eligible and reference the parent block (i.e. TaPoS) so they can’t later issue a long-range attack from a different block without having an objectively signed conflicting election, seems to be not effective because a long-range attack could generate different public keys for stake starting from a point further back in chain time.

To clarify: the security of my idea is derived from the fact that if *any* of the stakes are honest at the start of a long-range attack, the attacker can't "sign them out" (the same process for leaving as joining) so the client can detect that one network has 100% availability and the malicious would have 99% or whatever. It doesn't matter what they do with their own stakes or how many fake stakes they create. However, if they were to buy the now-defunct private keys of stakeholders that have since signed out they could achieve this attack, but they would have to buy every single one. But it is possible to thwart this attack with very simple checkpoints long in the past. At some point after network ubiquity, it would be highly improbable to ever be able to execute such an attack even if the checkpoint is never updated again (presuming the signature scheme remains unbroken).

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 09:44:16 AM
Last edit: June 07, 2018, 12:38:46 PM by Ix

#101

Quote from: anunymint on June 07, 2018, 04:13:00 AM

Again I reiterate that if the attacker knows he can increase the transaction fees to any level he wants to by eliminating the competition over blocks by attaining 50+% of the stake, then the attacker can afford to buy the stake. Are you claiming that 50+% of the stake will not sell at any price?

The issue here is economics. If there’s a huge profit incentive to 50+% attack and there’s no cost to perform an ongoing attack indefinitely into the future. Thus, the NPV is extremely high for purchasing the stake (or forming an oligarchy of stakeholders who cooperate to attack).

I've been considering a couple of ideas based on stuff I've mostly found through your links. This is all regarding an opt-in stake. 1) is a very fresh idea for me that might have interesting implications.

1) Set a maximum number of opt-in stakes (probably based on total currency supply which would monotonically increase under my system). If stakes are full and there is still demand to stake, put the stakes in a queue that freezes the money (no idea for how long yet). When new stakes open up (currency supply increase, stakers leave, or stakers may be randomly booted after serving some amount of time or are unresponsive), use a VRF to select new stakes from the queue. All other queued stakes are booted from the queue but the money won't be available until their unfreezing time (presumably at least after the next queue).
edit: To avoid discouraging people from queuing by spamming right away and making the queue huge, the queue should start with an open queue that doesn't automatically freeze, then only some of those are chosen to be frozen - probably a fixed number based on the max stake, not a % of the total queued
(this, I believe, would also solve the "everything comes down to PoW" MC=MR problem)

2) Stake PK changes would be very limited or not possible, making transfer of stakes an incredibly risky proposition for the buyer. Even with PK changes, it's still a hugely risky proposition because you would have to wait until the new pk is accepted by the network with a long delay, in the meantime the previous owner can get the stake destroyed. - You might be able to get around this with a contract, so perhaps no PK changes allowed.

3) Tx fees are fixed or only changeable with a hard fork or significant vote. This works better under a system that aims for some kind of price stability, but you'd have to imagine some kind of market competition as well that could keep fees reasonable. If tx fees are too low, stake participation simply drops until it is acceptable. If they are too high, people switch to other networks or use off-chain transactions.

1 & 2 both help against but do not prevent an oligarchy, malicious or cartel-based. But it adds quite a lot of randomness, and a decent amount of punishment for trying to spam the opt-in stake. The cartel takeover attempt would have to out-queue the honest users 2 to 1, consistently across time. Depending on how long the queue freeze penalty is, this could result in the cartel needing significantly more money frozen than it would take to take over the network.

Since there is also a maximum stake, the cartel can't push everyone else into unprofitability by simply overwhelming the stake. If the cartel starts gaining a significant portion of the stake, if stakers are randomly booted, they would still need to keep overwhelming the queue or risk losing their foothold.

Just some thoughts.

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 09:59:47 AM

Merited by shunsaitakahashi (1)

#102

Quote from: anunymint on June 07, 2018, 01:59:10 AM

@shunsaitakahashi,

Since you expect 50+% of the stake to be stable running on the cloud, my idea for entirely eliminating short-range double spends is to slash not only conflicting approvals but also slash (make ineligible) the stake public key from future slots for an extended remediation period. Also require stake public keys to be stable for extended period before they’re eligible to vote approvals.

Ineligible stake is not counted towards total stake when computing the 50+% quorum threshold. Thus I think you can remove the slow changing stake requirement from your whitepaper and set the threshold to exactly 50+%.

There are a couple of problems with that idea:

1) Bonded stake systems are subject to the 0% attack in which you bribe all the bonded stake in the system to simultaneously send a transaction to themselves (an action with seemingly no consequences). With zero bonded stake remaining in the system, the chain freezes forever.

2) If you remove the stake transfer limit, the above becomes possible and not only that but you also weaken the history attack strength, which was near 99% attack proof due to the slow stake transfer combined with the epocs signatures.

Ix

Full Member

Offline

Activity: 218
Merit: 128

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 10:13:02 AM

#103

Quote from: monsterer2 on June 07, 2018, 09:59:47 AM

1) Bonded stake systems are subject to the 0% attack in which you bribe all the bonded stake in the system to simultaneously send a transaction to themselves (an action with seemingly no consequences). With zero bonded stake remaining in the system, the chain freezes forever.

A bond implies the money is not transferable, so I'm not sure how this attack could work.

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 07, 2018, 10:28:18 AM

#104

Quote from: Ix on June 07, 2018, 10:13:02 AM

Quote from: monsterer2 on June 07, 2018, 09:59:47 AM

1) Bonded stake systems are subject to the 0% attack in which you bribe all the bonded stake in the system to simultaneously send a transaction to themselves (an action with seemingly no consequences). With zero bonded stake remaining in the system, the chain freezes forever.

A bond implies the money is not transferable, so I'm not sure how this attack could work.

That would have to be a necessary condition. You might assume that bonded stake just has to mature for some period before it can start voting, but this is not enough as you say it must also not be transferable.

I think there is still an open question about objectively identifying double signing, though - why can't an attacker just use two different stake public keys to double sign?

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 08, 2018, 07:43:47 AM

#105

I look forward to what you guys can come up with. Although, I have to say I'm extremely sceptical of any trustless design claiming to have no incentive system.

IMO, the 0% attack is more dangerous than just the not responding attack, because at first glance there should be no reason to expect that sending yourself a transaction could have consequences, so why would someone refuse being paid for doing so?

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 08, 2018, 10:32:27 AM
Last edit: June 08, 2018, 11:40:05 AM by d5000

#106

Quote from: anunymint on June 07, 2018, 04:13:00 AM

Specifically every slot of PoA relies on the prior approved block being 100% final and the only choice from the nearest prior slot that had an approved block.

Thanks anunymint, the explanation was good, and that was also what I understood approximately.

A way to collect PoB approvals (and reward them for better liveness) without having to include entire PoB blocks that break the PoA model could be to include the approvals into a PoA block, in a similar way that TaPoS "collects" "stake approvals" in transactions (or maybe as an alternative way for epoch approvals), but before I seriously begin to think about that and if this even makes sense, I'll re-read the rest of your discussion this weekend (yesterday I had only time for participation in the "lighter" sections of this forum). It's possible that it's better to base the reward system only on "live stake".

Regarding the probability of a 50% attack on a mature currency because of the expectation of rewards/fees, I am not entirely convinced of your pessimistic view on it (my first thought being: why would the users of the chain accept extremely high fees and not change to a competing chain - or in an extreme case, hard fork the attacker away? wouldn't that break the goal of the attack?). But you are totally right that if there is a solution that avoids that "game" that forms a rent-maximizing oligarchy or 50% attacker it should be at least tried - I am eager to know more about your solution (Cred). About ...

Quote

That is why I am proposing changes to the design that entirely eliminate the possibility of attacking. Have you seen my suggestions on that?

... I'm not aware of it at this moment as I didn't re-read the discussion, so if you want (and have time) you can show me a direct link to it.

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 09, 2018, 03:13:18 PM

#107

Quote from: anunymint on June 08, 2018, 09:14:23 PM

I presume you are referring to the current PoA design and not my proposal because it does not seem to apply anymore in my proposed change.

I was referring to your proposal with the staking keys.... I'm going to stop clogging up this thread with conjecture and wait for Shunsai to add some more details.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 10, 2018, 08:50:39 PM

Merited by vapourminer (1)

#108

Hello All,

Sorry for being out for a couple of days. I attempted to write a better summary of the protocol (below). I will rewrite protocol description shortly as well. I haven't yet caught up with the discussion, will reply to them separately.

Regards,
Shunsai

Proof-of-Approval Overview:

Proof-of-Approval protocol uses stakes of the parties for consensus and defense against the attacks. Since the parties' stakes are recorded on the chain itself, such systems are inherently different from Proof-of-Work (PoW) like systems where the defense is provided by some external resource requirement. Proof-of-Approval, like other stake based protocols, may also seem overly complex riddled with seemingly unnecessary rules. These rules are required to defend against conditions that cannot occur in a PoW system.

Trade-offs for the protocol participants also differ dramatically compared to those in PoW. While PoW participants benefit from large computational power, additional computational power (beyond a minimum) offers no advantage to participants of most stake based protocols. In Proof-of-Approval, participants benefit not from computational power but from the high performance network connectivity--low latency and high transmission speeds.

Participants of the PoW systems may benefit from specialized computer systems typically housed at their own premises. In Proof-of-Approval, on the other hand, participants benefit from locating their nodes closest to the Internet backbone. Proof-of-Approval nodes, especially for larger stakeholders, are more likely to reside in cloud than on their own premises.

In a typical operation of a blockchain, participants agree on the honest chain up to some blocks below the top. While this concurrence is present implicitly, it is typically not recorded on the chain. As a result, an attacker using History or Costless Simulation attack, may be able to offer an attack chain that can beat the protocol's rules and win. Proof-of-Approval records this concurrence in "epoch approvals." An attacker's attack chain, in addition to beating the protocol rules, must present a higher amount of concurrence in order to win.

Nodes, housed at owners' premises, may face power or network outages or slow connections resulting in fewer stakeholders being live at any time. On the other hand, nodes hosted on cloud, are mostly free of power or network outages and are more likely to be live at any time. Cost of hosting a node on the cloud, although greater than zero, is very small--as low as $5-10/month. Proof-of-Approval benefits from more stakeholders being live at any time. To incentivize nodes to move to cloud, Proof-of-Approval offers block approval award. To win block approval award, a node must be able to quickly send its approvals to the block producers. Block approval award more than offsets cloud hosting cost and is difficult to win without cloud hosting. As a result, Proof-of-Approval expects more than a quorum stake be hosted on cloud and be live for block approvals.

Participants of Proof-of-Approval are expected to have stake distribution like that of other public blockchains. Such distribution is typically modeled by Pareto distribution where a large portion of wealth is held by a small fraction of the population. Proof-of-Approval's incentive system works best for such real world stake distributions and may not work well for a hypothetical near-equal stake distributed over a large population.

The goal of the protocol is to choose a single block in each slot to be placed in the chain. There are many ways of accomplishing this goal, the simplest one being selecting a single party to produce a block. Unfortunately this method results in low liveness of the chain. This protocol chooses multiple parties to produce candidate blocks. The consensus must pick one out of these candidates to be placed in the chain. For security, the protocol also requires that a quorum of stakeholders approve a block. While it is possible to converge a quorum stake to a single block through multiple rounds of voting in one slot, the protocol uses an alternate system--multivoting. This multivoting system requires only one round of voting per slot but it delays its decision by one block. In other words, the stakeholders choose multiple acceptable blocks belonging to the same parent, effectively voting for a single parent. The parent block is a Focal Point or Schelling Point where the stakeholders are expected to converge to thus avoiding splitting of the honest stake among multiple blocks. These approvals are stored on the chain inside the successor block.

The protocol offers block creation award to the winning block in addition to the transaction fees stored in the block. The protocol also offers two additional awards, block approval and epoch approval, to anyone who participates in them in proportion to their stake.

The protocol makes the following assumptions:

1. Stake distribution among parties is like that of other public blockchains (Pareto like).
2. Epoch approval award is large enough to motivate even the smallest stakeholders to participate and requires little computation or network performance.
3. Block approval award is not likely won by nodes not hosted in cloud.
4. Block approval award for some minimum stake, same as the stake needed for block creation, is more than sufficient to cover cloud hosting cost.
5. The combined stake of parties holding that minimum stake is significantly larger than a quorum.
6. All stake hosted in cloud is live all the time.
7. A slot period is sufficiently large for parties to validate candidate blocks and communicate approvals.
8. Adversarial stake is slightly below quorum and the honest stake is larger than quorum.

And the protocol expects the following behavior from its participants:
1. Almost all nodes try winning epoch approval award.
2. Most parties holding some minimum stake are hosted in cloud.
3. At least a quorum stake is live at all times.

Under these conditions, the protocol achieves high liveness and finality after one block. In addition, History or Costless Simulation attack requires nearly all stake at some time in past to win.

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 10, 2018, 09:27:46 PM

#109

Hello Traxo and Shelby,

Quote from: Traxo on June 06, 2018, 08:30:14 PM

So thinking it through now, the 50+% (aka 50%+1) threshold has to be attained for a block to be approved and proposed to be final which is what dictates the liveness issue as well, but that doesn’t guarantee all the stake is available live.

The assumption of sufficient stake being live comes from block rewards incentivizing parties holding larger stake to move to cloud. There is also assumption that they constitute >50% stake. This would hold for pareto like distribution but not for some odd looking ones.

Quote from: Traxo on June 06, 2018, 08:30:14 PM

Quote from: Traxo on June 06, 2018, 08:30:14 PM

However, in the end-game proof-of-work must be run by an oligarchy also. Proof-of-work is a transition scheme to centralized global order, not a permanent decentralization.

Have you considered allowing stakeholders to delegate their approval voting powers to other stakeholders, so they can rent it out? I think that would help you achieve near 100% liveness, especially if you could make it the default and automate it somehow.

Here are my concerns regarding delegation.
1. It's further centralization
2. How does an honest party really know that the other party (it is delegating to) is really honest? Adversarial colluders know each other and delegation may make their job even easier.
But in the end, delegation may be the only way.

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

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.

Correction. The TaPoS is necessary so that the long-range attacker can’t rewrite the chain keeping most of the transactions but double-spending a minority of them. This prevents the divide-and-conquer strategy. With TaPoS, the attacker must take all of the history and can’t chop it up. @anonymint recently wrote a reply to Vitalik about this point.

Quote from: shunsaitakahashi on June 06, 2018, 07:40:32 PM

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.

I still can’t grok that section of the whitepaper. What do you think is different about epochs that would increase participation? Anyway, maybe my idea above is better?

Epochs are very long, perhaps 1 hour or more. Any party can get a message through in that long a period. To give the full overview of how TaPoS and epoch approval work together, I am going to repeat the example I had given you earlier. See if it makes sense.

Quote

Code:

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.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 10, 2018, 10:26:05 PM

#110

Hello D5000,

Thus if the above is correct, then we can only claim PoA is less permissioned in the sense that all of the static stake can participate. But it’s not permissionless like proof-of-work where new external resources can participate without any permission.[...]My definition of permissionless in this context is that the existing stakeholders can’t stop new outside resources from coming onboard to unstuck the chain. In that case, I think PoA is not permissionless.

Yes, there is some ambiguity about what "permissionless" means, and in general terms I support your definition. But working Proof-of-stake currencies always offer a market (otherwise they weren't currencies) where units can be traded to goods or other currencies or tokens, so in practical terms it cannot be avoided by the stakeholders that other people enter the system and become part of the validator (in this case, of the approvers) set. You are correctly pointing out that the requirement to move stake slowly means that the process is restricted. This would, however, only affect whales wanting to become part of the validator set fastly, the average user (and the average stakeholder) shouldn't be affected as the market will continue to move.

I consider permissioned vs permissionless more in terms of PBFT vs Bitcoin. In PBFT, some kind of authority (single point of entry) needs to let you in while in bitcoin, even though you have to buy expensive equipment, there are multiple sources and one isn't dependent on a single source to let them through.

The PoA transfer limits are not unlike bank's daily transfer limits etc, they should have no impact in a typical operation, only under attack scenarios. Delaying stake participation has a slightly different effect. Transfer limits don't affect smaller stakeholders while the delayed participation affects all.

Quote

So PoA doesn’t have these undesireable delegation elections, but instead has virtually implausible liveness unless a vested oligarghy is involved to always be online and prevent the chain from becoming stuck.

That's why I wrote "not fully permissioned" - in DPoS, depending on the amount of validators, a group of whales can easily obtain total control of the validator elections, while in PoA this kind of control seems theoretically possible, but very impractical - if the liveness problem can be solved. It would need a very big group (supermajority) of colluding whales to seriously restrict newcomers being part of it.

PoA essentially needs to pay-up some stakeholders (typically larger ones) to operate on cloud. If the stake distribution is too "uniform" among the parties, the award needs to be increased resulting in increased inflation.

Quote from: anunymint on June 07, 2018, 01:59:10 AM

Quote

I think the burning needs to be lossy so that an attacker can’t get back all he burns (to mitigate the issue I discuss below).

I don't understand fully - if burning is only a complement of an otherwise PoS-based algorithm which has the main goal to improve liveness then I see no problem here. The necessary rule for that is that never two PoB blocks are allowed in a row, so a "PoB-only" attacker could only trick users into a double spend that wait for one single confirmation, otherwise he must obtain a majority of the stake. In this case, in PoA, the "one-block-finality" rule would have to be modified to "one-PoA-block-finality" as PoB, as you correctly write, cannot achieve 100% finality.

I don't fully understand this one - thinking more on it.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 11, 2018, 03:41:34 PM

#111

Hello All,

Just updated the paper to include (hopefully) better description and increased penalty for nothing-at-stake (N@S) attack. Description is sections 2.1 and 2.2, conflicting approval penalties section 2.3.19.

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

Will continue catching up with the thread

.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 11, 2018, 04:40:41 PM

#112

Hello Shelby,

Since you expect 50+% of the stake to be stable running on the cloud, my idea for entirely eliminating short-range double spends is to slash not only conflicting approvals but also slash (make ineligible) the stake public key from future slots for an extended remediation period. Also require stake public keys to be stable for extended period before they’re eligible to vote approvals.

Actually I think that's the most feasible slashing idea I have ever seen (and believe it or not) I put something similar in the paper even before reading this post (Section 2.3.19 https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf).

Quote from: anunymint on June 07, 2018, 01:59:10 AM

Ineligible stake is not counted towards total stake when computing the 50+% quorum threshold. Thus I think you can remove the slow changing stake requirement from your whitepaper and set the threshold to exactly 50+%.

AFAICT, this should entirely eliminate any short-range double-spending. Because proof-of-conflicting approvals are entirely objective without any consensus, because they requires the offender(s) to double-sign. And there’s never any valid reason to vote for more than one block in any slot number.

I don't feel that the slow changing stake is a big problem since the stake is large enough to affect only oligarchs and not most participants. But I will continue thinking about it.

Quote from: anunymint on June 07, 2018, 01:59:10 AM

So then the only vulnerabilities that remain are the long-range attack and the oligarchy incentive to maximize transaction fees and capture all the block rewards.

I don't believe oligarchy incentive can be avoided. Every scenario I can think of requires "linear" incentive system, i.e., incentives are proportional to stake. Only a PoW can avoid that which causes other problems that we are trying to solve.

Quote from: anunymint on June 07, 2018, 01:59:10 AM

So then the only vulnerabilities that remain are the long-range attack ...

The maximum defense against any attack in a stake based system can only be 100% stake (unless the system is a hybrid system). For a typical long range attack scenario which is likely to go back several months to fork off, the honest chain will be able to accumulated near 100% signatory stake. Why? (Section 2.3.26)

1. Transacting parties become signatories because of TaPoS. I did argue earlier that it may not be needed but, the more I think about it, the more I get convinced that it is needed. If a party was trying to avoid becoming a signatory by not signing blocks or epochs, this is the trap they fall into. Even if the party transacts even a tiny stake from their holdings, their entire stake holding at the time of fork off is the signatory stake.

2. Block approvals make signatories in each block >50%. There would be some different block approvers over the period of the long range attack. Therefore, the union of all block approver stake is likely to be larger than >50%.

3. Epoch approvals are for parties with smaller stakes. There is a minimum stake threshold where the block approval incentive will the cover cloud hosting costs. Below that threshold, block approval incentive will be too small to cover the cost. The only thing the protocol wants from these parties is to periodically attest the honest chain. The incentive is expected to be large enough to motivate even a single coin holder to periodically attest the chain. Not all stakeholders need to approve every epoch - but the union of the stakeholders attesting honest chain is likely to be near 100% over a period of a few months.

Adversary's attack chain need to show a higher signatory stake (not sure what should happen if the signatory stake were equal down to the smallest fraction). Adversary may be able to collect private keys that held different stake at different points in time. But in order to succeed, the adversary needs to find a point in time from where they can build an attack chain containing a higher signatory stake. I believe it is a very large hurdle for the adversary.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 11, 2018, 07:56:08 PM

#113

Hello D5000,

Quote from: d5000 on June 07, 2018, 03:58:41 AM

Quote from: anunymint on June 07, 2018, 01:59:10 AM

If 50% of the state becomes non-responding, then the chain can be stuck forever. No transactions will be confirmed. And thus no stake can change, not even slowly.
[...]
The accumulated lost keys over time is serious problem that needs some solution.

OK, I overlooked that problem. You're totally right that this makes the liveness problem more severe, and I agree that in this case we would very likely need a distinction between the validator set and the total "currency-holder" set.

Agree this is a problem that needs a solution.

Quote from: d5000 on June 07, 2018, 03:58:41 AM

Quote from: shunsaitakahashi on June 11, 2018, 07:56:08 PM

I seem to strongly disagree with your characterization of reality. Why do you think it is impractical for an attacker to obtain 50+% of the stake?

My argumentation in this case is based on the assumption of a mature and relatively well-distributed currency with some actual real usage, at least as much as our current Bitcoin, not like an "average altcoin". You're totally right that in most current altcoins, and more so in new ones, it's relatively easy to get a high stake participation. (That's also why I'm becoming increasingly critical to ICO-distributed cryptocurrencies, and why I started this thread for example [which got buried instantly by spam, obviously].) But in a mature currency it should be very hard to get even 25%.

All cryptocurrencies have to begin at some point and so in its early phase they will be weak to attacks if using pure PoS. In my opinion, a prolonged proof-of-work phase is the way to go for current altcoins if they want to achieve some resistance to 50+1% stake attacks, if no new ideas are found for this problem. It has to be noted that a PoW phase doesn't solve everything because mining could also be centralized (e.g. like in Steem's PoW phase) and PoW 51% attacks are also not totally uncommon as we saw recently. But for now we have nothing better, afaik.

So in general terms I think we're not so much in disagreement in this point.

I agree that an initial PoW phase would provide some relief from attacks in the early period. How does the PoW phase exist criteria work? Are those exit criteria algorithmic or is it some kind of a soft fork?

Regards,
Shunsai

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 12, 2018, 08:05:10 AM

Merited by achow101 (1)

#114

Hi Shunsai,

I'm sure you are aware of this, but I just wanted to point out that the punishment incurred by abusers of the signing processes is still only opportunity cost. Really, to be at parity with PoW and to be fully rid of NaS this has to be converted into realised cost somehow.

The trouble is, it is very hard to see all the attack angles when you have NaS looming in the background, so, although you've gone to great lengths to narrow them all down and implement counter measures you can never really be sure the gremlin of NaS has truly been banished.

Cheers, Paul.

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 13, 2018, 05:41:00 AM
Last edit: June 13, 2018, 05:55:09 AM by d5000

Merited by shunsaitakahashi (1)

#115

Hi Shunsai,

I agree that an initial PoW phase would provide some relief from attacks in the early period. How does the PoW phase exist criteria work? Are those exit criteria algorithmic or is it some kind of a soft fork?

I haven't thought extensively about that. I know protocols like Peercoin where there is less incentive to produce PoW blocks once the value/difficulty of the coin goes up because the block reward decreases with difficulty, but these mechanisms probably can't be easily applied to PoA because they rely on the "probabilistic finality" Bitcoin blockchain model. In PoA, instead, we would need to define a block height for the change (or use a soft fork - Edit: although a soft fork has the disadvantage that it can be blocked by miners like we saw with Segwit.).

A possible model (quick thought, so may be flawed):
- set a minimum and a maximum block height for the transition from PoW to PoA
- and set a "desired difficulty", corresponding to a desired level of PoW security (simulation).
- Change from PoW to PoA once the minimum block height and the desired difficulty is reached;
- in case the desired difficulty is not reached, change at the maximum block

I think the minimum block height for the transition is necessary to ensure a minimally desirable distribution of the coin units, because otherwise a large miner/miner cartel could instantly change to PoA at the first block - or after they have ensured they have mined a large majority of the coins, so they could instantly 50%+1 attack it. Obviously that doesn't solve the problem that the cartel can 50%+ attack in the whole phase to get most of the rewards, but solving that is impossible.

Regarding the proposal including Proof of Burn: I'm currently re-reading the thread (currently on page 5) and slowly understanding the protocol better (and also understood my misunderstanding of Traxo/Anonymint's post about "permissionlessness"). As such a proposal would be related to the problems regarding liveness and voting, I would like to read the remaining posts and your new version of the paper to see if there is a way Proof of Burn can help with the liveness issue/participation rate. Need to think a bit more about it ...

@anonymint: Read your proposal, looks good on a first glance - after I read the rest of the posts I may comment it.

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

d5000

Legendary

Offline

Activity: 3892
Merit: 6006

Decentralization Maximalist

Re: Proof-of-Approval: Version 2.0

June 13, 2018, 10:02:39 PM

#116

Hello Shunsai,

I got now a little bit of time to read the rest of the thread and so I want to explain the Proof of burn idea. (I don't know if you know the Proof of Burn concept so I elaborate a bit on it, if you already know, no problem

)

Proof of burn works approximately this way: participants can destroy coins and these are transformed into a "score" which determines the probability to validate a block. There are some variants of the concept, in some the "score" lasts only for a block, in others for various blocks or like in Slimcoin (the only implementation so far) for more than a year although the score in this variant "decays" continuously.

PoB has a nice property: it forces "burners" to participate in validation almost 24/7 to get enough block rewards to compensate for the coins that they destroyed - otherwise they would work at a loss. It's not only opportunity cost that they lose (like in PoS or PoA) but real money they burnt, so I believe the incentive being stronger. That was the initial reason why I proposed to add proof of burn validators - to improve participation in the PoA process. "Burners" would almost always be also "stakeholders", and so they could be crucial in reaching the 50% threshold.

Now as @anonymint correctly writes, there is no threshold for burners which would guarantee to achieve finality, because everybody can burn as many coins as he wants and so the number of "burnt coins" would be varying greatly, so we cannot say "50%+1 of burnt coins must approve a block".

I thought a bit about it and there may be a possible solution: PoA approvers could select a set of "burners" at a fixed point in time and include their addresses in one of the approval blocks every X slots, for example, the first of every epoch. Then, a random function (e.g. including transaction data, addresses of PoA validators in previous blocks etc.) selects a slot for a PoB block. Almost all PoB participants will be eager to be online at this block to get the reward.

So we could have two advantages: 1) higher PoA participation and 2) more objectivity, as there are two distinct validator sets (which overlap of course, but not 100%). The "PoB slot" may be even an opportunity to create at least one block in the case the chain becomes stuck because of low participation (however, this could add new attack risks, I haven't thought thoroughly about that).

But I'm a bit in doubt if that would not decrease the security of PoA, because just before the "burner selection" by PoA approvers an attacker could burn 50%+1 of the coins burnt before. That would be expensive, but less expensive as a PoS/PoA 50%+ attack. As there is only one PoB block per X slots allowed, an attacker would not be able to create a "PoB attack chain", but he could get a block more for a low cost when burning participation is low.

As anonymint wrote, there may be also a conflict with TaPoS - I believe he means that this could be the case if "burners" approve another fork than the majority of TaPoS signatories are on ...

So at the end, I don't know if this proposal is of any value for the PoA concept, maybe it is not. Maybe PoA block approver rewards are enough for the incentive to participate.

By the way, I have a question about one point in your summary which may be a (minor) flaw:

Quote

In Proof-of-Approval, on the other hand, participants benefit from locating their nodes closest to the Internet backbone.

That may have undesired consequences: Wouldn't that mean that the optimal network layout for the "oligarchy" (=whales with 50%+ stake) would be that all are located on a single datacenter? Wouldn't that create a centralization problem and a possible single point of failure? That incentive would be strong, above all, for stakers trying to get block creator rewards as these benefit most from an excellent connection (similar to fintechs which are eager to locate their machines next to those of stock exchanges ...).

I have noted, for example, that many altcoin projects recommend to host a node at one of the biggest providers (Digital Ocean, Amazon). For a good decentralization, this is not desirable, and the block approver selection would most likely incentive that (all whales using the same cloud service).

Could there be a solution for that? For example, is there a way to ensure that a "good" connection is advantageous, but an "excellent" connection is not better than a "good" one, e.g. introducing some kind of delay for block producers?

Regards, d5000

Quote from: anunymint on June 13, 2018, 06:35:36 AM

I’m not participating in this thread anymore.

I expect this account to be banned very soon.

That would be a pity. Your writing style may be a bit harsh sometimes (but you are by far not the only forum participant with that "problem"), but your contributions are among the most interesting and insightful in the whole forum, not only the altcoin area. I hope at least Traxo stays here Wink

█▀▀▀
█
█
█
█
█
█
█
█
█
█
█
█▄▄▄

▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄

▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄

▀▀▀█
█
█
█
█
█
█
█
█
█
█
█
▄▄▄█

▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
░▀▀██▀▀

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 14, 2018, 08:48:40 PM

#117

Hello Shelby,

Quote from: anunymint on June 12, 2018, 03:27:54 AM

Quote from: shunsaitakahashi on June 11, 2018, 04:40:41 PM

Quote from: anunymint on June 07, 2018, 01:59:10 AM

So then the only vulnerabilities that remain are the long-range attack and the oligarchy incentive to maximize transaction fees and capture all the block rewards.

I don't believe oligarchy incentive can be avoided. Every scenario I can think of requires "linear" incentive system, i.e., incentives are proportional to stake. Only a PoW can avoid that which causes other problems that we are trying to solve.

I am missing something regarding how the rewards are non-linear with the increasing stake. (If they were to be non-linear, the parties may benefit by splitting or joining as the case may be for non-linearity.

Quote from: anunymint on June 12, 2018, 03:27:54 AM

Quote from: shunsaitakahashi on June 11, 2018, 04:40:41 PM

The maximum defense against any attack in a stake based system can only be 100% stake (unless the system is a hybrid system). For a typical long range attack scenario which is likely to go back several months to fork off, the honest chain will be able to accumulated near 100% signatory stake. Why? (Section 2.3.26)

It’s arduous to read that section of your whitepaper because you jump directly into detailed specification without providing an explanation of the essence of what you’re accomplishing with the details. Also I find your explanation of that section to be lacking clarity (same as my complaint earlier when I via @Traxo re-summarized the Schelling point essence of your system in one paragraph). The part of about unshared and shared and which blocks or epochs get counted and what is the point of 1(a)(b)(c)(d). Seems incomplete or incoherent to me. Maybe it is just me having difficulty grokking that.

I am going to take another attempt at rewriting this section.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 14, 2018, 08:52:07 PM

#118

Hello Paul,

Quote from: monsterer2 on June 12, 2018, 08:05:10 AM

... the punishment incurred by abusers of the signing processes is still only opportunity cost. Really, to be at parity with PoW and to be fully rid of NaS this has to be converted into realised cost somehow.

Isn't it also just an opportunity cost in PoW as well? If a miner devotes half of his equipment to an alternate fork, he may lose additional earnings but his mining equipment remains intact.

Quote from: monsterer2 on June 12, 2018, 08:05:10 AM

The trouble is, it is very hard to see all the attack angles when you have NaS looming in the background, so, although you've gone to great lengths to narrow them all down and implement counter measures you can never really be sure the gremlin of NaS has truly been banished.

Agree. That's just like bugs in software - gotta keep catching them and squashing them!

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 14, 2018, 09:48:40 PM

#119

Hello Shelby,

Quote from: anunymint on June 13, 2018, 06:35:36 AM

I found a flaw in your design of the slots which enables the 50+% to recover the nothing-at-stake attack and make as many long-range (aka history attack) forks as he wants of which offline users can’t objectively distinguish between them. Specifically if the attacker wants 3 forks (with 2 of them hidden until he’s ready to orphan the honest fork) then he will only approve a block in every 3rd slot of each fork, where each fork is staggered so attacker does not have to sign duplicate approvals for the same slot. Slashing by duplicate approvals for the same slot number will not objectively slash the attacker’s approvals and detect the honest fork. It’s not possible to trace stake back through all spends, because this would slash the stake of those who obtained from an attacker. Thus PoA retains the nothing-at-stake problem which plagues all proof-of-stake systems.

Sorry I didn't completely understand. Does the adversary have 50+% stake ownership at the present time? If that is the case, since it is beyond the protocol's capability, he can double-spend at will - he/she wouldn't even need to mount a N@S attack.

Quote from: anunymint on June 13, 2018, 06:35:36 AM

Also I realized the original flaw I had mentioned about the propagation race condition at the boundary time of a slot can cause finality to be delayed by an extra slot but not an extra approved block. The block creator can sign and broadcast an approved block at the instant of the slot expiration time which has more approval, and thus cause the Schelling point for choosing the parent of the next slot to be split. But the Schelling point for the next slot will not be split, unless a block creator for the expired slot can pretend there was network delay and another block with higher approval is broadcast at that instant. But even so, if the number of block creators per slot is finite, the this delaying tactic can prevent 100% finality from being attained after several slots.

Your description does sound plausible - I need to think a bit more on it.

Regards,
Shunsai

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 15, 2018, 06:27:24 PM

#120

Quote from: shunsaitakahashi on June 14, 2018, 08:52:07 PM

Isn't it also just an opportunity cost in PoW as well? If a miner devotes half of his equipment to an alternate fork, he may lose additional earnings but his mining equipment remains intact.

This is a common misconception. Although the miners equipment stays intact, they always lose cost of mining to electricity, and, on average this loss is equal to the block reward.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 16, 2018, 06:37:41 PM

#121

Hello Shelby,

Quote from: shunsaitakahashi on June 14, 2018, 08:48:40 PM

Quote from: anunymint on June 12, 2018, 03:27:54 AM

Quote from: shunsaitakahashi on June 11, 2018, 04:40:41 PM

The maximum defense against any attack in a stake based system can only be 100% stake (unless the system is a hybrid system). For a typical long range attack scenario which is likely to go back several months to fork off, the honest chain will be able to accumulated near 100% signatory stake. Why? (Section 2.3.26)

It’s arduous to read that section of your whitepaper because you jump directly into detailed specification without providing an explanation of the essence of what you’re accomplishing with the details. Also I find your explanation of that section to be lacking clarity (same as my complaint earlier when I via @Traxo re-summarized the Schelling point essence of your system in one paragraph). The part of about unshared and shared and which blocks or epochs get counted and what is the point of 1(a)(b)(c)(d). Seems incomplete or incoherent to me. Maybe it is just me having difficulty grokking that.

I am going to take another attempt at rewriting this section.

I wrote the following description for the fork selection. I'd update the paper shortly.

Regards,
Shunsai

Fork Selection and Defense Against Attacks

Network participants may receive different forks from other participants and have to choose the preferred fork to build upon. This can happen when a party joins the network for the first time or after a hiatus. It can also happen when an adversary offers an attack fork to the network. An honest party, in any of these situations, must determine which one of the forks is the honest fork.

The protocol makes the following assumptions about the characteristics of the honest fork vs. attack forks and uses these treatments to give preference to the honest fork:

1. The honest fork is more likely to miss blocks compared to attack forks. Therefore, to put the honest fork at an equal footing, the protocol measures fork length as the number of slots spanned, not the number of blocks in it.

2. The branch-off of forks is recent if the forks do not span the entire length of a full epoch. The protocol assumes that the stakes and approvals in such forks are comparable. The protocol also assumes that the block approvals represent approval for the block as well as its ancestry. Therefore, such forks can be compared with approval stake stored in their head blocks.

If the forks have branched off recently, then the fork holding the most approvals in the head block is preferred by the network and is the honest fork.

3. The branch-off is considered long timespan if the unshared part of the forks span at least one whole epoch. In the long timespan, an adversary can manipulate stakes resulting in stakes and approvals in forks to be not comparable. In this case, they are compared for "signatory" stake (described below) in the first block after the branch-off.

There may be accounts on chain that once held large stakes but hold little or no stakes at present. An adversary may be able to acquire private keys of such accounts rather inexpensively. Using these old accounts, they can build attack forks starting a long time in the past and manipulate stakes in them. Therefore, the signatory stake, in the first block after the branch-off, better represents the network's preferences for the forks.

Signatory stake calculation, for each pair of forks, considers only the blocks not shared between them. During the normal operation of the network, some parties have performed some actions requiring them to sign hashes of these unshared blocks. Such actions include:
1. Creating a block.
2. Approving a block.
3. Approving an epoch.
4. Performing a spending transaction, requiring signing hash of an unshared block.

These actions cannot be created without the party's consent or copied to an attack fork. Through these actions, the parties and their entire stake holdings are indicating their testimonials of the corresponding fork.

The signatory stake is the combined stake, of all parties who performed any action requiring their signature, at the first block after the fork branch-off. Note that any testimonial action performed by any party in any successor block adds that party's stake (that it held at the first block after branch-off) to the signatory stake.

If the pair of forks being compared branched-off several weeks or months ago, the honest fork would accumulate testimonials from a large percentage of total stake. With each passing week, more and more parties and their stakes would become signatories on the honest fork. Over time such signatory stake would approach 100%. Note that if parties, that purposely avoid creating or approving blocks, transfer their stake, the very action of transferring their stake makes them signatories.

In long timespan fork comparison, the fork containing the most signatory stake wins. If the branch-off occurred several weeks or months ago, the honest fork would have nearly the entire stake (at the time of branch-off) as the signatory stake. And adversary must control private keys of nearly all stakeholders, at the branch-off time, in order to present a larger signatory stake in their attack fork.

This signatory stake comparison rule makes Proof-of-Approval's defense, against History or Costless Simulation attack, stronger than any other stake based protocol.

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 16, 2018, 11:41:57 PM

#122

Hello Shelby,

Quote from: anunymint on June 07, 2018, 11:20:45 PM

Note I have offered @shunsaitakahashi to collaborate with me on my CRED project and incorporate the best of his PoA with the best of my consensus algorithm in order to create the nearly perfect decentralized ledger. I’ve received his first reply and now waiting to see how further discussions go. Learning about each other. Hope we can accelerate this to implementation. I think I have all the issues already sorted out in my head now.

My wife is back in town, my cold is better and my day job is less crazy now

. Trying to catch up all the links you provided so I can ask intelligent questions.

Regards,
Shunsai

Twitter @shunsatakahashi

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 16, 2018, 11:46:01 PM

#123

Hello Paul,

Quote from: monsterer2 on June 08, 2018, 07:43:47 AM

IMO, the 0% attack is more dangerous than just the not responding attack, because at first glance there should be no reason to expect that sending yourself a transaction could have consequences, so why would someone refuse being paid for doing so?

Could you point me to some link or more info on 0% attack? (Not sure if it was part of the thread, if it is, I'd reread the thread).

Regards,
Shunsai

Twitter @shunsatakahashi

monsterer2

Full Member

Offline

Activity: 351
Merit: 134

Re: Proof-of-Approval: Version 2.0

June 17, 2018, 06:01:12 AM

#124

Quote from: shunsaitakahashi on June 16, 2018, 11:46:01 PM

Hello Paul,

Quote from: monsterer2 on June 08, 2018, 07:43:47 AM

IMO, the 0% attack is more dangerous than just the not responding attack, because at first glance there should be no reason to expect that sending yourself a transaction could have consequences, so why would someone refuse being paid for doing so?

Could you point me to some link or more info on 0% attack? (Not sure if it was part of the thread, if it is, I'd reread the thread).

Regards,
Shunsai

It's described in the thread - basically it applies to bonded stake systems, where the stake is still allowed to be transferred after it becomes 'bonded'. If you bribe 100% of bonded stake to send a transaction to themselves at the same time, the network becomes forever stalled as there is no bonded stake left in the system with which to produce blocks.

shunsaitakahashi (OP)

Member

Offline

Activity: 94
Merit: 16

Research, Analyze and Invent Crypto Systems

Re: Proof-of-Approval: Version 2.0

June 17, 2018, 05:28:02 PM

#125

Hello Shelby,

Quote from: anunymint on June 10, 2018, 09:43:34 PM

Quote from: shunsaitakahashi on June 10, 2018, 08:50:39 PM

An attacker's attack chain, in addition to beating the protocol rules, must present a higher amount of concurrence in order to win.
[…]
The protocol makes the following assumptions:
[…]
8. Adversarial stake is slightly below quorum and the honest stake is larger than quorum.

In addition to the liveness issues which were discussion up-thread which I presume you’ll be replying to, the above assumption and the nothing-at-issue for a quorum busting attacker (i.e. above the safety threshold of 50%) is the one that is insufficient for me based on my political-economics reasoning which I discussed with @d5000 up-thread. Thus I have advocated additional countermeasures up-thread.

However, I prefer to take further development and discussion of those countermeasures in closed source for the time being. Y’all of course may continue without me if you wish. I’ll be back to open source hopefully soon.