Topic: Proof-of-Approval: A Better Blockchain Consensus Protocol (Read 1008 times)

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

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

Interesting proposal with some nice properties, although I mostly agree with monsterer that the long-range attack problem isn't fully solved. I'll look into the updated paper this week to comment on it.

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.

Created new thread for the updated paper since it may fix some previous problems but may have created some new ones.
Thread https://bitcointalksearch.org/topic/proof-of-approval-version-20-3913439

Regards,
Shunsai

I believe this to be impossible, so I await your update with the utmost enthusiasm!

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

Well, I would say more: any or almost any idea of decentralisation based on the Proof-of-Anything is vulnerable at the level of it's concept.
Because it strongly tends to concentration (i.e. centralisation) of abovementioned Anything, and thus all the consensus might be overriden; in fact, all the history might be overwritten by one who takes a control over majority of that Anything.

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

Indeed, interesting, very valid point. I suppose you mean the security rule named "validator's bond" or "security deposit", so that after "depositing" (required to become a validator) some amount of tokens, it is not possible to "withdraw" immediately.  It is not mentioned in the document, but should be easy to add in order to address the issue you mentioned.

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.

Hi Shunsai,

Very interesting article.

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 ?

 

Hi Shunsai,

The standard response that most PoS developers have given in the past is that only bootstrapping nodes would be vulnerable to such an attack because all online nodes would reject the fork because they have knowledge and timestamps for the canon chain.

However, this concession is a loss of objectivity compared to PoW, and a loss of security because of that. I see no real way to avoid Nothing at Stake in a system with no PoW - you could try something like punishment of locked up funds (ala Etherum), but that's a real mess to analyse and may be less efficient overall than PoW as well as being inelegant.

Cheers, Paul.

PoW was also attacked and actually hacked in the early days of Bitcoin.

There's no reason these new consensus algorithms can't become as secure as PoW over time.

So far, the PoS and DPOS algorithm have been operating just fine for years now with no recent hacks. I don't doubt all the blockchains using these consensus algorithms are being attacked at all angles.

Hello Bonzenboss,

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.


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

Hello Paul,


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

Hey shunsia,
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.

Could you maybe explain what permission, adversary and adversary tolerance means in the comparison chart? (I’m not a native English speaker as you can tell and translator Programm give me weird results so..)

Thanks in advance

-Bonzenboss

Hello Shunsai,

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.

Cheers, Paul.

Hello Fresheneesz,


Comparing Proof-of-Approval with 2-hop Blockchain (2-hop)
1. 2-hop uses PoW consuming resources (in addition to PoS), Proof-of-Approval has no PoW.
2. 2-hop's alternate blocks are different, one is from PoW and the next is from PoS. All Proof-of-Approval blocks are the same (but each block has 2 parts to it).
3. In 2-hop, during PoS round, the network choose one stakeholder for PoS block. In Proof-of-Approval any (or all) stakeholders approve blocks.
4. In 2-hop, fork selection is based on the longest PoW chain. In Proof-of-Approval fork selection is based on a better approval score.
5. Proof-of-Approval has 1 block finality. 2-hop's finality properties seem to be similar to PoW chains. The analysis here is more difficult since neither PoS nor PoW can be analyzed independent of each other. The PoS part of the analysis matches Cardano's Ouroboros (https://eprint.iacr.org/2016/889.pdf) static case. Since the static case isn't a reality (stakes will change during chain's lifetime), it is unclear if the PoS does add any additional security to the chain.

Hope this comparison helps.
Regards,
Shunsai

Very weak strategy to detect a node's intentional avoidance of approving peer's blocks. Nodes can simply stop supporting ICMP or manipulate it to delay response packets a few milliseconds.

Block generation has zero cost and starting a node is very cheap, a typical player can run thousands of nodes that their trivially generated blocks will be approved by a masternode which in turn will be rewarded the bonus for its fake cooperative gesture.

I don't see this 'approval rewarding' strategy a good one and I have not an alternative in hand to suggest, in this moment.

Hello fresheneesz,

Node A is allowed to not approve another node's (say B's) blocks. That also means that B is allowed to not approve A's blocks. It works both ways. To detect if it is intentional or just network, point-to-point ping and bandwidth can be measured to guess number of blocks that should have reached within the time-slot.


Yes, block approval should be incentivized. I am working on it.

Thanks,
Shunsai