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

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.

Hello Shelby,

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.



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

Regards,
Shunsai

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.


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

Regards,
Shunsai

Hello Shelby,

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.



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

Regards,
Shunsai

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

Hi Shunsai,

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.

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.

Hello D5000,

Agree this is a problem that needs a solution.



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

Hello Shelby,

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



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.



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.



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

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

Hello D5000,

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.



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.



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

Regards,
Shunsai

Hello Traxo and Shelby,

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.



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.



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.

Regards,
Shunsai

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.

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.

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

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

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?

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?

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

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.

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.