Search content
Sort by
Showing 20 of 40 results by shunsaitakahashi
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
This thread has the ongoing discussion https://bitcointalk.org/index.php?topic=3913439.0
⭐ Merited by vapourminer (1)
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.
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.
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Hello D5000, I incorporated epoch approval limits in the latest version of the paper. https://github.com/Takanium/doc/blob/master/research/proof-of-approval.pdf
I am reading the whitepaper, interesting stuff and definitely looks like some good work. Has the protocol been used for a token/coin yet?
Not yet :-) I wanted to have at least a level of comfort with the protocol before launching. But the protocol is only one part. Another part that must be defined is the smart contract system. I am currently working on a white paper for that.
Thanks,
Shunsai
Hello Yj1190590,
Regards,
Shunsai
What if the block creators don't obey the rule? They could use the conflict approvals anyway and that seems better to them because more approvals means better chance to win. And more importantly, there will be no evidence while they did so. Then why does anyone obey the rule for his own benifit?
Block approvers own >50% of the stake. If they approve blocks containing conflicting approvals, that will invite many forking related attacks on the chain including double spend. Approvers can approve another block containing all valid approvals, so they don't benefit by violating the rule. Would a rational stakeholder approve a block that may lead the devaluation of their asset without providing them any benefit? I think not. (This has the same basis as PoS.)Then how to prevent getting stucked when there are not so many positive users paticipating in the competition if the quorum stake is >50%?
In absence of >50% approvals, no new blocks will be created in those slots. It may not sound that good at first but this is the best policy. It's preferable to not process any transactions than to risk the entire blockchain. Once the connectivity is restored, the stakeholders will approve (or reapprove) the set of blocks offered on top of the previously approved block.Since the "finality" is not the actual finality, what's the meaning of it? Because the data on chain is still not 100% certain.
All block based chains like Proof-of-Approval including Bitcoin and Ethereum, have the so called probabilistic finality. The newest 'n' blocks in the chains are not considered stable. For Bitcoin, users want that 'n' to be 6 blocks or more. For Proof-of-Approval, it is just 1 block. Regards,
Shunsai
The ultimate goal, though, is to have the entire stake in the system sign every block, isn't it? I know that would be totally unfeasible because of the size of the data, but this is the security model you're aiming to approximate?
Absolutely! In addition to the size of data, nodes on slow/intermittent connections may not be able to send their approvals for each block.
Hello Yj1190590,
Conflicting block approval is detected by looking at all block-approval-blocks published on the network in the same slots. It is the next block creator's responsibility to check for these conflicts and not use contents of a block-approval-block that contains such a conflict. In addition, the approvers for the next block will also check for these conflicts and would not approve blocks that contains a conflicting approval from the previous slot.
The punishment for a conflicting-approver is that they do not earn approval award since their approvals do not go in the chain.
This near instant finality helps with Bribe attack but not with History (aka Costless Simulation) attack. It is because the "finality" is in the short timespans where the stakes of the parties have not changed dramatically. History attack, on the other hand, is powered by dramatic stake changes which can only occur in the longer timespans.
Hope it helps.
Shunsai
1.According to my understanding, the approvals stored in each block-approval-block are the approvals for the current block. So where are the conflicted approvals stored? If they are not stored in the history blocks, how could you tell a stackholder approves conflicted blocks. In other words, according to what should you punish the double-approving behavior to prevent "nothing at stake" problem?
Multiple block creators publish block-approval-blocks for their own created blocks. While they are sent to all the nodes, block-approval-blocks are not stored themselves in the chain, their contents are.Conflicting block approval is detected by looking at all block-approval-blocks published on the network in the same slots. It is the next block creator's responsibility to check for these conflicts and not use contents of a block-approval-block that contains such a conflict. In addition, the approvers for the next block will also check for these conflicts and would not approve blocks that contains a conflicting approval from the previous slot.
The punishment for a conflicting-approver is that they do not earn approval award since their approvals do not go in the chain.
2. About the instant finality. If you determine the realchain so quickly, how could you prevent the blockchain from spliting into different forks for ever when there happens something that separate the network temporaryly, like intercontinental optical fiber cable fracture?
Once there is >50% stake approval on a successor block, there can only be one and only one predecessor block under the honest majority stake assumption even with network outage. If in case a block cannot receive >50% approval, then no new blocks will get published. Those slots will go empty until a >50% approval is achieved.3. About the history attacks. Why don't you just mention that the protocol has instant finality? Because that resolved all the history attacks if it works.
The protocol achieves finality after 1 block - not instant finality. PBFT and related protocols that build consensus on transaction level and publish a single block per slot have the real instant finality.This near instant finality helps with Bribe attack but not with History (aka Costless Simulation) attack. It is because the "finality" is in the short timespans where the stakes of the parties have not changed dramatically. History attack, on the other hand, is powered by dramatic stake changes which can only occur in the longer timespans.
Hope it helps.
Shunsai
Hello Ix,
I am very interested and will read it shortly. Thanks for the link.
Shunsai
If you're interested, you can check out my signature for a link to my whitepaper on the Decrits consensus algorithm which is relatively similar to yours (with an identical long range attack defense), and is 5+ years old. 
I am very interested and will read it shortly. Thanks for the link.
Shunsai
Hello Paul,
How about this?
Proof-of-Approval is a stake based protocol where every block is signed by the stake majority and every epoch is signed by almost the entire stake in the system.
Regards,
Shunsai
"Proof of approval is an approximation of a PoS chain in which every block is signed by all the stake in the system"?
How about this?
Proof-of-Approval is a stake based protocol where every block is signed by the stake majority and every epoch is signed by almost the entire stake in the system.
Regards,
Shunsai
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Hello D5000,
It is an interesting attack scenario, not sure if there is an official name for it, but let's continue calling it, profitable 50+% attack. Stake based and derivative chains are more susceptible to it because, unlike PoW, a large number of blocks can be built in a short time.
The attacker must wait for a certain degree of finality (after his stake transfer transaction is placed in the chain) before launching this attack. The more uncertain a chain's finality is, the harder it is for the attacker since they have to wait longer.
Proof-of-Approval's (v2) features that may help or hurt against this attack are
- (hurt) Near instant finality - the attacker can launch the attack quickly after transferring
- Max stake transfer is limited per block so that entire 50+% stake cannot be transferred in 1 block. If the limit is set to 0.5%of total network stake, it would take the attacker 100 or more blocks to transfer.
- If the attack fork is larger than an epoch (epoch length vs stake transfer amounts are not yet finalized), then epoch approvals in the "real" chain would be larger than that in the attack chain and the real chain wins.
- If the attack fork is smaller than an epoch, the fork determination procedure as currently specified in v2, chooses higher stored approval in the topmost block. This makes such an attack possible.
A limit that has been considered and perhaps should be included in Proof-of-Approval is the max stake transfer per epoch. If that limit is set to something like 25% of stake, then this attack cannot succeed because of epoch approvals.
So, I plan to add stake transfer limit per epoch.
Shunsai
Only a little observation (and that's why I comment here in the old thread): The attack monsterer described (old majority stakeholder(s) taking over the chain with a double spend) is essentially the same attack than a profitable 50+% PoS attack. In a profitable 50+% attack, you will wait for a few blocks selling your stake first (most likely in an altcoin exchange as they confirm the "reception" of the coins relatively fast) and only then try to "take over" the new chain with a prepared attack chain. Otherwise, very likely your stake would decrease in value. So, also in this attack, in the moment you take over, you don't own stake anymore (or at least, you aren't forced to own any stake).
The difference between "long-range attack" and "profitable 50+% attack" be the time between the actual double spend and the "takeover" (when the attack chain replaces the "honest" chain) but the attack mechanism is the same. But monsterer is absolutely right and this is the reason why PoS protocols are to be considered - until this is solved - weaker than PoW protocols. I consider this attack unpractical in a chain with many stakeholders and reorg limits or "rolling checkpoints", and it's likely to be very expensive, but it may be considerably cheaper than a PoW 50+% attack.
The difference between "long-range attack" and "profitable 50+% attack" be the time between the actual double spend and the "takeover" (when the attack chain replaces the "honest" chain) but the attack mechanism is the same. But monsterer is absolutely right and this is the reason why PoS protocols are to be considered - until this is solved - weaker than PoW protocols. I consider this attack unpractical in a chain with many stakeholders and reorg limits or "rolling checkpoints", and it's likely to be very expensive, but it may be considerably cheaper than a PoW 50+% attack.
It is an interesting attack scenario, not sure if there is an official name for it, but let's continue calling it, profitable 50+% attack. Stake based and derivative chains are more susceptible to it because, unlike PoW, a large number of blocks can be built in a short time.
The attacker must wait for a certain degree of finality (after his stake transfer transaction is placed in the chain) before launching this attack. The more uncertain a chain's finality is, the harder it is for the attacker since they have to wait longer.
Proof-of-Approval's (v2) features that may help or hurt against this attack are
- (hurt) Near instant finality - the attacker can launch the attack quickly after transferring
- Max stake transfer is limited per block so that entire 50+% stake cannot be transferred in 1 block. If the limit is set to 0.5%of total network stake, it would take the attacker 100 or more blocks to transfer.
- If the attack fork is larger than an epoch (epoch length vs stake transfer amounts are not yet finalized), then epoch approvals in the "real" chain would be larger than that in the attack chain and the real chain wins.
- If the attack fork is smaller than an epoch, the fork determination procedure as currently specified in v2, chooses higher stored approval in the topmost block. This makes such an attack possible.
A limit that has been considered and perhaps should be included in Proof-of-Approval is the max stake transfer per epoch. If that limit is set to something like 25% of stake, then this attack cannot succeed because of epoch approvals.
So, I plan to add stake transfer limit per epoch.
Shunsai
This article explains Proof-of-Approval's defense against History or Costless Simulation attacks.
https://medium.com/@shunsai.takahashi/weak-subjectivity-not-required-fb1c467bc5ad
https://medium.com/@shunsai.takahashi/weak-subjectivity-not-required-fb1c467bc5ad
Hello Paul,
Block approval award is separate from epoch approval in approximately the same amount (over an epoch). For example, let's say
1. 100 blocks in an epoch
2. block approval award 1 coin * approver's network stake fraction
3. epoch approval award 100 coins * approver's network stake fraction
So, if an approver has 10% stake in the network
1. Approving epoch awards 100 * .1 = 10 coins
2. In addition, if they approve 90 blocks in that epoch, they additionally get 90 * 1 * .1 = 9 coins
3. If they also create one or more blocks in the epoch, they get creator awards + transaction fees
Hope it makes is clearer.
Shunsai
I think Abdulkhaliq123 was talking about from an incentive PoV - why be a block approver when you can get the same reward for doing nothing, essentially?
If you reward each upoc approver the same amount as each block approver, then no one will approve blocks. On the other hand, if you divide the epoc reward between all nodes, then the amount of the reward will be zero because you can just sybil attack it.
If you reward each upoc approver the same amount as each block approver, then no one will approve blocks. On the other hand, if you divide the epoc reward between all nodes, then the amount of the reward will be zero because you can just sybil attack it.
Block approval award is separate from epoch approval in approximately the same amount (over an epoch). For example, let's say
1. 100 blocks in an epoch
2. block approval award 1 coin * approver's network stake fraction
3. epoch approval award 100 coins * approver's network stake fraction
So, if an approver has 10% stake in the network
1. Approving epoch awards 100 * .1 = 10 coins
2. In addition, if they approve 90 blocks in that epoch, they additionally get 90 * 1 * .1 = 9 coins
3. If they also create one or more blocks in the epoch, they get creator awards + transaction fees
Hope it makes is clearer.
Shunsai
Hello Abdulkhaliq123,
Approving blocks provides another very desirable property - finality. In fact, the transactions are stable once a single block has been deposited on it.
Regards,
Shunsai
In that case, why approve blocks at all?
There are two different problems that need solvin
There are two different problems that need solvin
Approving blocks provides another very desirable property - finality. In fact, the transactions are stable once a single block has been deposited on it.
Regards,
Shunsai
Re: A development company just charged me $3300 for a first call
They should have clarified their fees upfront before the start of the call. What they did is unethical.
You may be better off finding developers on your own from Github :-)
You may be better off finding developers on your own from Github :-)
Hello Paul,
1. Block approval - where faster is better. If it is slow, the blockchain will have low transaction rate.
2. Defense against History attack - where higher stake participation provides stronger defense. Since some parties will be on slow connections, they may never be able to approve blocks.
Epoch approval solves problem 2.
Yes the currency inflation rate would be higher - about 2x of what without the epoch approval. Determination of the exact reward amount needs additional work. Epoch award needs to be large enough for small stakeholders to feel that participation is worthwhile. Block approval award is mostly expected to go to large stakeholders.
Yes, epoch rewards will result in a large amount of data storage once per epoch. The epoch period does not have to be very small - it can be around 500-1000 slots.
Regards,
Shunsai
I'd like some clarification on the epoc rewards; every node on the network will receive an award for approving an epoc and said award is the same as the block approval reward?
In that case, why approve blocks at all?
There are two different problems that need solvingIn that case, why approve blocks at all?
1. Block approval - where faster is better. If it is slow, the blockchain will have low transaction rate.
2. Defense against History attack - where higher stake participation provides stronger defense. Since some parties will be on slow connections, they may never be able to approve blocks.
Epoch approval solves problem 2.
In addition, wouldn't this cause the currency to inflate out of control as everyone on the network receives the same award?
Yes the currency inflation rate would be higher - about 2x of what without the epoch approval. Determination of the exact reward amount needs additional work. Epoch award needs to be large enough for small stakeholders to feel that participation is worthwhile. Block approval award is mostly expected to go to large stakeholders.
edit: also, wouldn't evidence of the epoc rewards result in a massive amount of data (needing to be stored), since every node on the network will participate?
Yes, epoch rewards will result in a large amount of data storage once per epoch. The epoch period does not have to be very small - it can be around 500-1000 slots.
Regards,
Shunsai
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Created new thread for the updated paper since it may fix some previous problems but may have created some new ones.
Thread https://bitcointalk.org/index.php?topic=3913439.0
Regards,
Shunsai
Thread https://bitcointalk.org/index.php?topic=3913439.0
Regards,
Shunsai
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:
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
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
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Hello Aliashraf,
I believe I have a good solution to this History attack (aka Costless Simulation attack) issue. While most PoS systems are relying on the so called "Weak Subjectivity" solution, this solution is purely objective. I am writing it up now and will post it here soon for everyone's review. I can't overstate the value of the feedback provided in this forum. Thanks everyone!
Regards,
Shunsai
Shunsai,
I appreciate your hard work and feel deep sympathy with you, a person who knows something is wrong and current situation with crypto is not good enough because of the classical paradox between security and decentralization on one side and scalability on the other side.
The thing is POS, even your 2nd phase commit version, is not proved to be an answer because of problems like Nothing at Stake mentioned by Paul here and a lot more. It is not just a simple 'issue' to 'think about' it has been discussed over and over and no answer available yet, other than complicating everything to make it harder for both adversaries and innocent participants and/or leading to a sophisticated protocol vulnerable to implementation bugs and a series of other limitations. Just ugly, far from elegant solutions too complicated, too fragile.
I have gone through this before and have chosen another approach: forgetting about the answers and re-thinking questions.
For instance, let's take a look at your 'permissionless' index (whether participating in a protocol needs permission from an authority or not): What if one needs permission but not from a centralized authority but a decentralized entity like a curated list which is maintained in a classic PoW base blockchain tp participate in another protocol that carries the much burden of the transaction load, being secured by a trivial, low cost algorithm ?
See? A lot of possibilities out there and nothing is 'obvious' and, as I'm used to say, you shouldn't stick with common sense.
I believe I have a good solution to this History attack (aka Costless Simulation attack) issue. While most PoS systems are relying on the so called "Weak Subjectivity" solution, this solution is purely objective. I am writing it up now and will post it here soon for everyone's review. I can't overstate the value of the feedback provided in this forum. Thanks everyone!
Regards,
Shunsai
Hello Paul,
Any single person owning (or colluding with) a quorum (majority) stake is a problem because that person (or colluders) can rewrite the chain as they choose. This situation is essentially the same as an adversary owning a quorum stake which is the limit of the protocol.
This is not how I would categorise the presented scenario. This is the NaS problem in it's essence. The attacker, as a historical majority stakeholder, can still take over the blockchain at any point in the future after he has sold his stake. So, at the current block height, said attacker owns 0 stake, yet he can still rewrite the entire chain due to this NaS problem.
You are correct in pointing out an issue here which must be solved. I'd describe the issue slightly differently even without any single party holding a quorum stake.
An adversary buys empty private keys (with zero current stake) that once upon a time did hold a quorum stake in the blockchain. That adversary can start rewriting blocks from the time the keys did hold the quorum stake to the present - completely rewriting all the transactions.
I do need to think about this problem. Thanks for pointing it out.
Regards,
Shunsai
In the following example, say I had a majority of stake at block A. Then at B0, C0 all the way up to head block H0, I sell off my majority of stake, understanding that there is an upper limit on stake transfer.
Then, I create a double spend of my stake using the historical private keys, which I still own, thus sending it to myself in a fork continuing fork B1 - C1 - D1 that I create and approve myself (majority stakeholder).
This is not a 50% attack, because I don't own the value held in the private keys anymore, the cost for doing this is nothing.
Why doesn't the network just accept this fork as canon, given that its the same length (or longer if I chose) than the genuine fork?
Code:
A - B0 - C0 - D0 - H0
\ B1 - C1 - D1 - H1
\ B1 - C1 - D1 - H1
Then, I create a double spend of my stake using the historical private keys, which I still own, thus sending it to myself in a fork continuing fork B1 - C1 - D1 that I create and approve myself (majority stakeholder).
This is not a 50% attack, because I don't own the value held in the private keys anymore, the cost for doing this is nothing.
Why doesn't the network just accept this fork as canon, given that its the same length (or longer if I chose) than the genuine fork?
Any single person owning (or colluding with) a quorum (majority) stake is a problem because that person (or colluders) can rewrite the chain as they choose. This situation is essentially the same as an adversary owning a quorum stake which is the limit of the protocol.
This is not how I would categorise the presented scenario. This is the NaS problem in it's essence. The attacker, as a historical majority stakeholder, can still take over the blockchain at any point in the future after he has sold his stake. So, at the current block height, said attacker owns 0 stake, yet he can still rewrite the entire chain due to this NaS problem.
You are correct in pointing out an issue here which must be solved. I'd describe the issue slightly differently even without any single party holding a quorum stake.
An adversary buys empty private keys (with zero current stake) that once upon a time did hold a quorum stake in the blockchain. That adversary can start rewriting blocks from the time the keys did hold the quorum stake to the present - completely rewriting all the transactions.
I do need to think about this problem. Thanks for pointing it out.
Regards,
Shunsai
Shunsai,
I appreciate your hard work and feel deep sympathy with you, a person who knows something is wrong and current situation with crypto is not good enough because of the classical paradox between security and decentralization on one side and scalability on the other side.
The thing is POS, even your 2nd phase commit version, is not proved to be an answer because of problems like Nothing at Stake mentioned by Paul here and a lot more. It is not just a simple 'issue' to 'think about' it has been discussed over and over and no answer available yet, other than complicating everything to make it harder for both adversaries and innocent participants and/or leading to a sophisticated protocol vulnerable to implementation bugs and a series of other limitations. Just ugly, far from elegant solutions too complicated, too fragile.
I have gone through this before and have chosen another approach: forgetting about the answers and re-thinking questions.
For instance, let's take a look at your 'permissionless' index (whether participating in a protocol needs permission from an authority or not): What if one needs permission but not from a centralized authority but a decentralized entity like a curated list which is maintained in a classic PoW base blockchain tp participate in another protocol that carries the much burden of the transaction load, being secured by a trivial, low cost algorithm ?
See? A lot of possibilities out there and nothing is 'obvious' and, as I'm used to say, you shouldn't stick with common sense.
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Hello Slava79,
Comparing Proof-of-Approval with Tendermint
1. Tendermint is a PBFT (http://pmg.csail.mit.edu/papers/osdi99.pdf) like algorithm where all nodes together agree on transactions and their order that would be put in a block. Therefore, all nodes together come up with a single block to be inserted in the blockchain. In Proof-of-Approval, just like Bitcoin, individual nodes bundle transactions on their own and the network chooses one of those bundles.
2. The "validators" in Tendermint volunteer to put some of their money as collateral that will earn them rewards but could also be confiscated. Validators are similar to those in Casper the Finality Gadget of Ethereum (https://arxiv.org/pdf/1710.09437.pdf). This article compares the two https://blog.cosmos.network/consensus-compare-casper-vs-tendermint-6df154ad56ae.
3. Tendermint a single "proposer" who proposes the blocks. The proposer is selected by some process from the validators in round robin.
4. Tendermint transactions achieve instant finality while Proof-of-Approval takes 1 block to finality.
5. Tendermint is likely to have less "liveness" than a block creating protocol like Bitcoin or Proof-of-Approval.
6. The amount need to takeover Tendermint is 1/3 of the collateral amount while the amount to takeover Proof-of-Approval blockchain would be almost half (just under half) of the value of the blockchain.
Regards,
Shunsai
Did you read Tendermint white paper ? I scanned article and the core of it looks quite similar to Tendermint's PBFT consensus. Could you please provide a comparison ?
Comparing Proof-of-Approval with Tendermint
1. Tendermint is a PBFT (http://pmg.csail.mit.edu/papers/osdi99.pdf) like algorithm where all nodes together agree on transactions and their order that would be put in a block. Therefore, all nodes together come up with a single block to be inserted in the blockchain. In Proof-of-Approval, just like Bitcoin, individual nodes bundle transactions on their own and the network chooses one of those bundles.
2. The "validators" in Tendermint volunteer to put some of their money as collateral that will earn them rewards but could also be confiscated. Validators are similar to those in Casper the Finality Gadget of Ethereum (https://arxiv.org/pdf/1710.09437.pdf). This article compares the two https://blog.cosmos.network/consensus-compare-casper-vs-tendermint-6df154ad56ae.
3. Tendermint a single "proposer" who proposes the blocks. The proposer is selected by some process from the validators in round robin.
4. Tendermint transactions achieve instant finality while Proof-of-Approval takes 1 block to finality.
5. Tendermint is likely to have less "liveness" than a block creating protocol like Bitcoin or Proof-of-Approval.
6. The amount need to takeover Tendermint is 1/3 of the collateral amount while the amount to takeover Proof-of-Approval blockchain would be almost half (just under half) of the value of the blockchain.
Regards,
Shunsai
Re: Proof-of-Approval: A Better Blockchain Consensus Protocol
Hello Bonzenboss,
Adversary - A party or a group of parties that are trying to take unfair advantage of the blockchain e.g. spending the same coins multiple times. Such adversarial actions are called "attacks" and blockchains should be able to deter them.
Adversary tolerance - Power of the adversary's attacks increases as he/she accumulates more and more of the resource critical to the blockchain. For Bitcoin, this resource is mining power. For Proof-of-Approval, this resource is the stake in the network. Adversary tolerance is the maximum amount of adversarial power a blockchain can deter.
Regards,
Shunsai
I read your technical paper and from what I understood it seems to be quite a good idea but of course as all protocols it first needs to be tested in action to see how good it actually works.
You are 100% correct that the testing with implementation is required. It turns out that even that isn't sufficient since an adversary will keep his/her attack vectors hidden till the blockchain actually succeeds when the attacks can earn him/her maximum profit. I think a peer review (what's being conducted here) can bring out many issues that a testing without serious adversarial attacks may not find.Could you maybe explain what permission, adversary and adversary tolerance means in the comparison chart?
Permission - A party (node) needs some kind of authorization before it can join the protocol execution. In permissionless environment (e.g. Bitcoin), any party can download code and start a computer to join the protocol execution.Adversary - A party or a group of parties that are trying to take unfair advantage of the blockchain e.g. spending the same coins multiple times. Such adversarial actions are called "attacks" and blockchains should be able to deter them.
Adversary tolerance - Power of the adversary's attacks increases as he/she accumulates more and more of the resource critical to the blockchain. For Bitcoin, this resource is mining power. For Proof-of-Approval, this resource is the stake in the network. Adversary tolerance is the maximum amount of adversarial power a blockchain can deter.
Regards,
Shunsai