Proof-of-Approval: Version 2.0

[shunsaitakahashi]

Hello Shelby,

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.

[1713871907]

1713871907

[1713871907]

1713871907

[1713871907]

1713871907

[shunsaitakahashi]

Hello Shelby,

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

[shunsaitakahashi]

Hello Paul,

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

[monsterer2]

Hello Paul,

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]

Hello Shelby,

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.

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.

As you stated in one of your previous posts above (posted by Traxo), the safety and liveness are maximized at safety threshold around 50%. I completely agree with that and, therefore, PoA's analysis assumes such a setting. With that setting in place, the protocol is unable to defend against an attacker holding more than 50% stake. I must have missed understanding the countermeasures you are talking about in this thread, therefore, I'd reread the tread. While safety beyond 50% is extremely desirable, a protocol with just 50% safety threshold is not only feasible but perhaps among the best of the breed protocols available today.

My subsequent proposals were about having stake elect to be live and eligible, so as to solve the liveness problem especially with stake that has lost their private keys (which is always growing over time, but you do have minted rewards in your design so perhaps that outstrips the lost keys in your design but I wouldn’t have minted rewards in my reformulation of PoA combined with the consensus system I had been developing).

I believe lost keys is a very serious problem which must be addressed. Although I am not sure if the consensus is the best place to address the lost key problem. I wonder if some sort of tooling (i.e. an application providing an API for the rest of the system to use) can be designed to not only hide the private key (thus protect) but to also create ways to recover it (no idea how). It could also prevent signature sequence that can expose the private key.

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.

One might argue that the centralization of delegation is better for your design than risking that liveness threshold not being met and the chain getting stuck.

My subsequent proposals were about having stake elect to be live and eligible, so as to solve the liveness problem especially with stake that has lost their private keys (which is always growing over time, but you do have minted rewards in your design so perhaps that outstrips the lost keys in your design but I wouldn’t have minted rewards in my reformulation of PoA combined with the consensus system I had been developing).

I think I probably agree that making it easy for n00bs to rent out their stake (thus be manipulated) is going to increase the likelihood of a quorum busting attacker. So for that reason and others, I would prefer my idea to your current formulation of PoA.

Agree with you that if insufficient stake resides on cloud (thus affecting liveness), the possible options are
1. Increase block rewards so that more stake moves to cloud
2. Some sort of delegation
Out of these two solutions, I prefer increasing the block rewards in the early months/years of the network because they can be easily reduced later. I consider delegation to be the solution of the last resort.

Epochs are very long, perhaps 1 hour or more. Any party can get a message through in that long a period.

My point was that still doesn’t increase participation amongst the apathetic or those with small stake who have a higher opportunity cost.

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.
[…]

The attacker has 51% stake (at block D) that he sells off in the honest chain

I had already stated up-thread that example doesn’t apply to the case where the attacker had 50+% a long time ago and is rewinding the chain and performing a long-range (aka History) attack from that distant past.

AFAICT, your example presumes that attacker’s fork starts from P, but the attacker may start from arbitrarily far back where he can even change the public keys which are used to compare for conflicting approvals. Thus we lose all objectivity. That is the nothing-at-stake issue and it is why proof-of-stake is so very insecure against oligarchies. And why I have stated that TaPoS is so important.

Hope my updated description answers these, otherwise, I will address them with a more thorough example.

Regards,
Shunsai

[shunsaitakahashi]

Hello Shelby,

There’s two ways to attack the liveness threshold: a) don’t send approval confirmations; or b) split approval confirmations between blocks with different parents.

Thus penalizing non-response (i.e. for case #a) isn’t a sufficient mechanism to penalize an intentional attack on liveness.

And without any other information, there’s no objectivity about which of the parents is a dishonest choice. Even if we proposed to accept all blocks that don’t have conflicting transactions, the attacker could plant conflicting transactions in the candidate blocks.

I have an idea for a potential solution to this problem, although it will either require some trust or longer delays in the exceptional case of a liveness attack. Note trust is also the means by which Stellar SCP resolves the liveness attack. Yet if I am correct then I think I have pretty much eliminated the 50+% attack on liveness and double-spends. Meaning a even higher level of safety than Nakamoto proof-of-work.

I would be slightly (perhaps more than slightly) concerned about the requirement of trust but delays should be completely acceptable. Would love to know more when you are ready .

Readers note that it’s already not possible in PoA to double-spend in the short-term attack with even 100% of the stake. And I have claimed that TaPoS is a robust (but not immune to an attacker that has closer to 100% of the stake) protection against the long-range attack.

Correction - double spend protection is only 50% stake in short term (under one epoch period). An adversary can build and approve his chain with 50% approvals (assuming he chooses to not approve any of the other forks).

Regards,
Shunsai

[Ix]

I believe lost keys is a very serious problem which must be addressed. Although I am not sure if the consensus is the best place to address the lost key problem.

I may be in a minority opinion here, but the solution is simple: destroy unspent currency after X amount of time. X can be on the order of 10-20 years, but it should not be infinite. This notion that you pay nothing for security for all time is inane. Asking people to ping the network once a decade is hardly an onerous task.

[monsterer2]

I would be slightly (perhaps more than slightly) concerned about the requirement of trust but delays should be completely acceptable.

And rightly so. After all, I know of a way to prevent 100% attacks, both contemporary and historical. Its called VISA.

[shunsaitakahashi]

Hello D5000,

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.

...

PoB is a very interesting concept and I have been trying to wrap my head around it. Here's an example that I came up with - not sure if it is entirely valid. Assume someone has $100K in a bank account that has no fees but gives 1% interest.

Case 1: The bank offers him to upgrade his account to a premium account that gives 2% interest but charges $5/month. In addition, the premium account gives him voting capability to the bank's operation in the amount of his deposit (100K).

Case 2: The bank offers him a 1 year CD for 10K returning 11% interest rate. The CD cannot be cashed before its term. The CD would also provide him voting capability to the bank's operation in the amount (10K).

Case 1 is closer to PoA where the incentives are provided without any lockup or risk. Someone can make a simple calculation when it's beneficial for them to upgrade to the premium account (>$6K) without any other risk.

Case 2 is closer to PoB where the rewards may be similar but part of the account is locked up (or burned) and is recovered only after some time (although the return in PoB is actually an annuity, not a lump sum payout). Here, in addition to incentives, the lockup part also involves risk - what if he needs money when it's locked up in the CD. A higher risk taker may put all his money into CD and earn a lot more return (and a lot more control over the bank). Not sure if it benefits adversary since he can put all his attack money to work here.

No conclusion yet - I am still going through all the scenarios.

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

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

You are correct. It is a small flaw that would benefit all users who locate their nodes in the same datacenter that hosts the most stake in the system. I don't have a solution for it yet.

Regards,
Shunsai

[shunsaitakahashi]

Hello Paul,

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.

Yes, you are right - I didn't think of the electricity cost. In PoA nothing at stake defense is structured as

1. No rewards for a predefined period - opportunity cost

2. Lock up of principal for a predefined period. I believe this is more than just the opportunity cost although I can't really put a cost number to it. If the stake were to be locked up forever - that would be equivalent to the loss of the principal. But since the lockup is for a short period - not exactly sure how to calculate it's effect.

Regards,
Shunsai

[monsterer2]

Hello Paul,

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.

Yes, you are right - I didn't think of the electricity cost. In PoA nothing at stake defense is structured as

1. No rewards for a predefined period - opportunity cost

2. Lock up of principal for a predefined period. I believe this is more than just the opportunity cost although I can't really put a cost number to it. If the stake were to be locked up forever - that would be equivalent to the loss of the principal. But since the lockup is for a short period - not exactly sure how to calculate it's effect.

Regards,
Shunsai

Hi Shunsai,

It's hard to see how it can be anything more than opportunity cost, because no coins are ever lost. The only loss is future earnings, from either the block reward, or other possible investments that could have been undertaken with said coins.

I'm no economist, but personally, I don't see removing liquidity as being a realised cost.

Cheers, Paul.

[d5000]

Hello Shunsai,

PoB is a very interesting concept and I have been trying to wrap my head around it. Here's an example that I came up with - not sure if it is entirely valid. Assume someone has $100K in a bank account that has no fees but gives 1% interest.

Case 1: The bank offers him to upgrade his account to a premium account that gives 2% interest but charges $5/month. In addition, the premium account gives him voting capability to the bank's operation in the amount of his deposit (100K).

Case 2: The bank offers him a 1 year CD for 10K returning 11% interest rate. The CD cannot be cashed before its term. The CD would also provide him voting capability to the bank's operation in the amount (10K).
[...]
Case 2 is closer to PoB where the rewards may be similar but part of the account is locked up (or burned) and is recovered only after some time (although the return in PoB is actually an annuity, not a lump sum payout). Here, in addition to incentives, the lockup part also involves risk - what if he needs money when it's locked up in the CD.

Case 2 would be similar to the typical "security-deposit-PoS", e.g. Casper. PoB, as the deposit will never be returned, makes the risk even greater, more so in the cryptocurrency space where one never knows if the coin will exist (or be of value) when the break-even (measured in coins) is reached.

One of the participants in an old Proof of Burn discussion had compared PoB to a lottery, and "probabilistic PoB" (modelled after Bitcoin's PoW, like in Slimcoin) is indeed a bit similar to a luck-based game. This is similar to Nakamoto's PoW, like Iain Stewart (inventor of PoB) has expressed it in his analogy "burnt coins are mining rigs": PoB is a simulation of mining in the blockchain - instead of burning coins on hardware, you burn coins on the blockchain.

However, one can also imagine a non-probabilistic PoB with a fixed reward each time a block is approved by a "Burner" (=annuity). In this case, risk would become much more predictable, and it would be probably also more suitable as a complement to PoA.

A quick thought (which may be flawed) about a possible merger of PoB and PoA: One could use the "burnt coins score" as a multiplier of the PoA "approver" reward. So for example, if you haven't burnt any coins, you get a "base interest rate" of 2% each year, and for each 1000 coins you burnt you get one percentage-point more. The amounts obviously have to be adjusted according to a simulation taking into account things like the expected supply inflation and the RoI of a burner.

In this case, burners do not really add "objectivity", as their participation in the decision-making process does not depend on burnt coins but only on their stake ("burnt" stake perhaps could be added, however). The only function of the PoB reward here would be the incentive scheme to improve participation and thus, liveness.

A higher risk taker may put all his money into CD and earn a lot more return (and a lot more control over the bank). Not sure if it benefits adversary since he can put all his attack money to work here.

That is true, it's in my opinion a fatal weakness that makes a "pure PoB" based cryptocurrency unviable. As everything is recorded on the blockchain, an attacker can know at any time which amount he must invest to control the decision-making process, and the amount will always be less than the amount required to 50+1% attack a PoW or PoS chain.

Regards, d5000

[Bindu124]

Hello,

Article: https://medium.com/@shunsai.takahashi/proof-of-approval-a-better-blockchain-consensus-protocol-b19a55dc331b
Paper: https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf (Updated June 9, 2018)

The previous version of this paper was discussed here https://bitcointalk.org/index.php?topic=3125137.0. This version builds upon the previous version and (to my understanding) fixes flaws that were pointed out. It achieves:

• Defense against attacks known as Costless Simulation, History or Long Range - much stronger than Weak Subjectivity https://blog.ethereum.org/2014/11/25/proof-stake-learned-love-weak-subjectivity/.
• Defense against Nothing at Stake attack.
• As before, does not consume physical resources.
• As before, achieves near instant finality.
• Updated reward system that rewards approvers.
• Updated creator selection (previous version didn't have any) to reduce number of proposed blocks in a slot and prevent network from being bogged down.
• Added attacks defense discussion.
• Added glossary for easier reading.

This article explains how Proof-of-Approval defends against History or Costless Simulation attack https://medium.com/@shunsai.takahashi/weak-subjectivity-not-required-fb1c467bc5ad .
Looking forward to your feedback.

Regards,
Shunsai

hi, Shunsai
  its very good article and its very usefull..good keeit

[cryenthu]

Very interesting concept! I look forward to further developments. This could be it.

A few thoughts. Block rewards would most likely go to those whom host on the cloud? In the case of Bitcoin, Satoshi knew that manufacturers would eventually develop specialized hardware to compete against others and try to garner as much coin as possible. It started out as using idle CPU time and then became increasingly more difficult for the 'little guy' to compete. Satoshi even advocated in delaying the 'arms race' as much as possible.

Are these valid concerns for PoA?


Thank you!

[shunsaitakahashi]

Hello Ix,

I believe lost keys is a very serious problem which must be addressed. Although I am not sure if the consensus is the best place to address the lost key problem.

I may be in a minority opinion here, but the solution is simple: destroy unspent currency after X amount of time. X can be on the order of 10-20 years, but it should not be infinite. This notion that you pay nothing for security for all time is inane. Asking people to ping the network once a decade is hardly an onerous task.

You solution may be the right solution. Even banks send the accounts not operated for years to the state.

Regards,
Shunsai

[Traxo]

Every post from @anunymint apparently was deleted. The thread is now very difficult to understand because a significant portion of the discussion is missing.

Some of this thread was archived here and here.

[shunsaitakahashi]

Not sure why - I'd love to explain anything and repost my replies as needed.

[Traxo]

Not sure why

aliashraf implies it was mtwerp.

[Ix]

Not sure why - I'd love to explain anything and repost my replies as needed.

Because btctalk management is petty beyond belief. Banning is one thing, but deleting posts is a whole other order of extremism reserved for the most petulant (and deleting RESPONSES!). Especially in thoughtful discussions.

[Traxo]

Not sure why - I'd love to explain anything and repost my replies as needed.

Because btctalk management is petty beyond belief. Banning is one thing, but deleting posts is a whole other order of extremism reserved for the most petulant (and deleting RESPONSES!). Especially in thoughtful discussions.

I noticed mtwerp vandalized the entire thread which you and @aklan participated in about DFINITY:

http://archive.is/https://bitcointalk.org/index.php?topic=4479703.0;all

I have created a new thread for it for you guys:

https://bitcointalk.org/index.php?topic=4666282