[2014-06-20] Proof of Activity: Extending Bitcoin's Proof of Work via POS

[LiteCoinGuy]

Proof of Activity: Extending Bitcoin's Proof of Work via Proof of Stake

 
Open letter about the 51% problem and a solution.

Iddo Bentov
Computer Science Dept., Technion
idddo@cs.technion.ac.il

Charles Lee
Litecoin Project
coblee@litecoin.org

Alex Mizrahi
chromawallet.com
alex.mizrahi@gmail.com

Meni Rosenfeld
Israeli Bitcoin Association
meni@bitcoin.or

http://eprint.iacr.org/2014/452.pdf

[dNote]

Hi, i would like to introduce an approach we are (XDN-project dev team) going to implement on the top of DigitalNote XDN blockchain http://digitalnote.org & http://digitalnote.org/whitepaper.
1. We want to implement PoA in XDN, rather than PeerCoin PoS, because we consider PoA is safer. It is truly HYBRID protocol: we need both PoW and PoS elements to produce a block, so 51% attack is harder. Remember, XDN has an ASIC-resistant proof-of-work.
2. Original protocol doesn't suit for an anonymous CryptoNote transactions. So we had 2 options:
2.1. Research and develop the new PoA scheme for XDN. That is a long and unpredictable way.
2.2. Implement a useful blockchain based feature (called deposits) and then apply the PoA based on blockchain deposits. So we chose it and made blockchain deposits based on multi-sigs a part of DigitalNote XDN.
3. Now we have deposits (check https://github.com/xdn-project/digitalnote), now we are ready to implement Proof-of-activity. Before that we want to discuss PoA with all interested parties.
4. Also we noticed a possible problem with the original PoA. ONLY the "last" "stakeholder" can set transactions for a new block. When done, he signs and broadcasts a new block to the network. Seems nothing wrong here, but "last" "stakeholder" can produce as many valid blocks as he needs by changing transactions set. So he can split the blockchain and make a double spend. In that case we are planning to give a right of setting up a block to the Proof-of-work miners.

[BitDreams]

Thinking about all the services and incentives this allows - following.

[iddo]

4. Also we noticed a possible problem with the original PoA. ONLY the "last" "stakeholder" can set transactions for a new block. When done, he signs and broadcasts a new block to the network. Seems nothing wrong here, but "last" "stakeholder" can produce as many valid blocks as he needs by changing transactions set. So he can split the blockchain and make a double spend. In that case we are planning to give a right of setting up a block to the Proof-of-work miners.

He can split but not double-spend (if you meant 0-confirmation then it doesn't really make sense because it's better to just re-broadcasting competing transaction as in Bitcoin, unlike the last stakeholder who cannot offer a higher fee to all the miners). The last stakeholder can be an attacker who produces many valid blocks, but it isn't much different than attempting DoS on the Bitcoin network, it's discussed in section 5.1 of the PoA paper.

Maybe you meant that the last stakeholder could try to create many valid blocks where each block pays a reward to a known PoW-miner address (by somehow sending the block to each miner directly to avoid blacklisting by other nodes), and this way get miners to work on different blocks. But it isn't important whether miners try to extend the single block that the attacker signed, or different blocks that the attacker signed. In fact, an attacker can do the same thing more easily in Bitcoin, by broadcasting conflicting transactions that pay to known miners addresses, so when one miner solves a block that includes the extra payment transaction, the other miners might prefer to continue to try to solve their old block.

BTW it's also possible to confiscate the reward of the last stakeholder when he double-signs, see for example section 2.2 of CoA (http://arxiv.org/abs/1406.5694).

In PoA, the reason for letting stakeholders (rather than miners) decide which transactions to include in blocks is that otherwise an external hashpower (without any stake) can attempt to attack by excluding transactions in the blocks, so it's better to give this decision power to entities who have an incentive to keep the network secure.

[dNote]

PoA stakeholder can pretty easy split the network and make a double-spend (?) :

1. he makes one  block with his own transaction to merchant and sends this block to the merchant.
2 immediately creates the second block with a double-spend transaction and sends it to other peers.
3. The first block will be orphaned with a high probability, so as merchant's tx.
So we are planning to return the ability of choosing the tx set back to PoW miner. Can you, please, comment it? Thank you.

Also much appreciate any other ideas to implement on the top of XDN blockchain and deposits. Now we are ASIC-resistant PoW with an original PoW initial distribution, but PoA will make XDN much stronger against 51% attack, but we should consider all options.

[dNote]

The last stakeholder can be an attacker who produces many valid blocks, but it isn't much different than attempting DoS on the Bitcoin network, it's discussed in section 5.1 of the PoA paper.

What if the last stakeholder will send lots of valid blocks. Like he will connect to all peers and send them different, but valid blocks (the "cost" of this kind of action is comparatively low).
How they can choose the "right" one?

[iddo]

1. he makes one  block with his own transaction to merchant and sends this block to the merchant.
2 immediately creates the second block with a double-spend transaction and sends it to other peers.
3. The first block will be orphaned with a high probability, so as merchant's tx.

If the merchant accepts then it's 0-conf security, a sensible merchant will wait for additional confirmations. I tried to explain to you why what you say doesn't make sense, because it's easier to double-spend by offering a higher fee reward to everyone at once.

What if the last stakeholder will send a valid blocks. Like he will connect to all peers and send them different, but valid blocks (the "cost" of this kind of action is comparatively low).
How they can choose the "right" one?

If all these different valid blocks don't offer any particular reward to specific addresses, then it's just DoS attack as discussed in section 5.1 of the PoA paper. If the attacker does wish to mix things up by incentivizing different participants to work on diffferent forks, then I tried to explain to you how to accomplish this attack more easily in Bitcoin.


If you disagree or don't understand something specific in my reply, then please refer to the text that I wrote and specify why you think that it's wrong, or what's unclear about it.

[dNote]

If the merchant accepts then it's 0-conf security

He accepts a block with the transaction. It is 1 conf, but not 0-conf

If all these different valid blocks don't offer any particular reward to specific addresses, then it's just DoS attack as discussed in section 5.1 of the PoA paper. If the attacker does wish to mix things up by incentivizing different participants to work on diffferent forks, then I tried to explain to you how to accomplish this attack more easily in Bitcoin.

The paper says that nodes "ban all blocks (blockheaders) with the last Nth stakeholders",  but that can happen only if they will discover such headers. Imagine:
All nodes are connected as bipartite graph (every "red" node is connected to a "blue" node, but there is no "red"-"red" or "blue"-"blue" connections)
Attacker sends different blocks to all red nodes, remember, there is no connection between red-red nodes, so red nodes relay blocks only to blue nodes. Each blue node will ban this header. But how can red nodes know about it?
We will need to implement some kind of alert system to avoid new DoS attack vectors. Can you ban the node for sending 2nd, 3rd, 4th ... block with the same header?

I don`t think that system with a user, who can create unlimited number of blocks "for free" will run perfectly.
Can see a problems here and solutions can cause new problems.
I think  that future DIgitalNote type of PoA implementation will have no such a treat.
Thank you for answers and your work, please, comment any possible issues with XDN PoA idea.

[iddo]

He accepts a block with the transaction. It is 1 conf, but not 0-conf

It's 0-PoW-conf, I tried to explain to you in post #4 why the merchant would consider this 0-PoW-conf to be inferior superior to 0-conf in Bitcoin, but still inferior to a single PoW confirmation.

The paper says that nodes "ban all blocks (blockheaders) with the last Nth stakeholders",  but that can happen only if they will discover such headers. Imagine:
All nodes are connected as bipartite graph (every "red" node is connected to a "blue" node, but there is no "red"-"red" or "blue"-"blue" connections)
Attacker sends different blocks to all red nodes, remember, there is no connection between red-red nodes, so red nodes relay blocks only to blue nodes. Each blue node will ban this header. But how can red nodes know about it?
We will need to implement some kind of alert system to avoid new DoS attack vectors. Can you ban the node for sending 2nd, 3rd, 4th ... block with the same header?

I don`t think that system with a user, who can create unlimited number of blocks "for free" will run perfectly.
Can see a problems here and solutions can cause new problems.

What problems specifically? Maybe what you don't understand is that what you describe is exactly the same situation as with Bitcoin right now, the red miner picks transactions as he wishes and tries to solve a red block, the blue miner picks other transactions (in particular a different coinbase) and tries to solve a blue block, and so on, and we get convergence because of the PoW component, both in Bitcoin and in PoA. I tried to show to you in post #4 how "it isn't important whether miners try to extend the single block that the attacker signed" if the objective of the attack is to create netsplits, because it'd be easier to do the attack with regular transactions as in Bitcoin.

[dNote]

We are working on Proof-of-activity in DigitalNote XDN http://digitalnote.org/whitepaper.pdf and i think it will be ready in September 2015.

EDIT: The trick for us is XDN private structure. So we made blockchain bank deposits, a new instance for building POA on the top of it.