 Show Posts
|
|
Pages: [1] 2 3 4 5 »
|
|
Not sure why - I'd love to explain anything and repost my replies as needed.
|
|
|
|
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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
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 |
|
|
|
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 AttacksNetwork 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. |
|
|
|
Hello Shelby, 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. 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 |
|
|
|
Hello Paul, ... 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. 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 |
|
|
|
Hello Shelby, 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. 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 |
|
|
|
Hello D5000, 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. 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 |
|
|
|
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). 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. 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. 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 |
|
|
|
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. 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. 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 |
|
|
|
Hello Traxo and Shelby, 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. 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. 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. 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. 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 |
|
|
|
|
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.
|
|
|
|
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 . 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. 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 |
|
|
|
|
