Proof-of-Approval: Version 2.0

[shunsaitakahashi]

Hello,

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

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

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

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

Regards,
Shunsai

[monsterer2]

Hi 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? In addition, wouldn't this cause the currency to inflate out of control as everyone on the network receives the same award?

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?

Cheers, Paul

[shunsaitakahashi]

Hello Paul,

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 solving

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

[shunsaitakahashi]

Hello Abdulkhaliq123,

In that case, why approve blocks at all?
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

[monsterer2]

Hello Abdulkhaliq123,

In that case, why approve blocks at all?
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

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.

[shunsaitakahashi]

Hello Paul,

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.

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

[shunsaitakahashi]

This article explains Proof-of-Approval's defense against History or Costless Simulation attacks.

https://medium.com/@shunsai.takahashi/weak-subjectivity-not-required-fb1c467bc5ad

[monsterer2]

Hi Shunsai,

Thanks for the clarification.

So I can better understand the way this works, am I right to make the following simplifying statement:

"Proof of approval is an approximation of a PoS chain in which every block is signed by all the stake in the system"?

Cheers, Paul.

[Ix]

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.

[shunsaitakahashi]

Hello Paul,

"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

[shunsaitakahashi]

Hello Ix,

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

[yj1190590]

Hi 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?

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?  

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.

[monsterer2]

Hello Paul,

"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

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?

[shunsaitakahashi]

Hello Yj1190590,

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

[shunsaitakahashi]

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.

[yj1190590]

Hi Shunsai:

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.

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?

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.

Then how to prevent getting stucked when there are not so many positive users paticipating in the competition if the quorum stake is >50%?

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.

Since the "finality" is not the actual finality, what's the meaning of it? Because the data on chain is still not 100% certain.

[shunsaitakahashi]

Hello Yj1190590,

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

[marcotheminer]

I am reading the whitepaper, interesting stuff and definitely looks like some good work. Has the protocol been used for a token/coin yet?

[shunsaitakahashi]

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

[yj1190590]

Hi Shunsai,

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

What I mean was the block creators benifit from violating the rule, not the approvers. They could receive more approvals from using both unconflictful and conflictful contents. Isn't that right? Regardless of the benifit anyway, why does anyone doing their duty when there is no evidence and no punishment for not doing so? What if somebody use an incomplete mining application?

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.

As a matter of experience, >50% online stake is very unusual. The problem of getting stuck is critical because it could happen anytime and last a very long period of time, not just under network separation. Shouldn't you find a way to deal with that?

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.  

In this respect, the word "stable" is meaningless when the onchain data could still be changed and that's why Bitcoin and Ethereum are called "nonfinality". Protocols like PBFT and Casper provide finalites by the collaboration of Valiators but I didn't see "finality" in your protocol.