Proof of Activity Proposal

I'd like to put out a alternative Proof of Stake proposal that I'm calling Proof of Activity or PoA for short. The problem with the few PoS proposals floating out there right now is that there's a lot of extra network traffic and block chain bloat to propagate and store all those signatures. With PoA, there's no need for stakeholders to sign all the signature blocks. Instead, one stakeholder is randomly chosen (and evenly distributed by coins held) to be the lucky representative of that block. And only he gets a chance to "sign" the block. If he signs the block, he will get a reward for it. And in the case of a "51%" attack, the fork that has a more aggregate difficulty and signature blocks wins out. That's the general idea. I will explain the details below.

Random Evenly Distributed Stakeholder

The reason why using random evenly distributed stakeholders works is because if the attacker does not have a huge stake, chances are he will not be selected in the blocks he generates. So his blocks will be unsigned. It would be harder for him to mount an attack against the real network with signed blocks. So in order for the attack to succeed, the attacker must have a huge hash rate and a huge stake.

The hash of the previous block is a random enough value that every node knows and can be used to select the "lucky" stakeholder for the next block. But in order to make this work, we need to be able to pick the random stakeholders with an even distribution and every node must be able to verify which is the correct stakeholder for the next block.  If person A has 200 coins spread out in multiple addresses and person B has 100 coins spread out in multiple address, person A should be exactly twice as likely to be selected as person B to be the stakeholder for the next block. One way to do is to figure out all unspent outputs and randomly pick one with an even distribution. You can mod the previous block hash by total satoshis ever produced up to this point,  and have the remaining value deterministically pinpoint an address from a ordered list of all unspent outputs.

Another way (not sure if easier are harder to calculate) is to have the mod of the previous block hash deterministically pinpoint a single satoshi from a coinbase transaction. Then follow that satoshi as it travels from transaction to transaction until it reaches an unspent output. Then that output address will be selected as the next stakeholder. You can do this deterministically. Since the initial satoshi picked from a coinbase output is evenly distributed, the eventual selection will be evenly distributed also. I can explain more if people are interested in how this will work.

Note that when nodes get a new block, they can start calculating the next stakeholder right away. And when the next block is announced, they just need to check to make sure that the block contains the right stakeholder. So even if calculating the next stakeholder may be a cpu intensive calculation, it won't affect node performance much because it can be done asynchronously. And it's not a new vector for a DoS attack. Though initial block download will be slower when it verifies each stakeholder of a block.

Rewarding Proof of Activity

The easiest way to reward PoA stakeholders is to send them coins in the coinbase. Stakeholders and miners will split the 50 generated coins in the coinbase transaction. I think giving stakeholders 10% (5 coins) is a good enough amount to entice stakeholders to sign the block yet not take away too much from the miners. This number is up for debate.

We could dynamically increase/decrease this ratio based on how many stakeholders have signed previous blocks. For example, we can do it during the diff retarget and try to reach of target of 50% signed blocks. If there are less than 50% signed blocks in the previous 2016 blocks, then pay the stakeholders more in the next 2016 blocks. And vice versa.

Block Signing

Block signing is achieved by spending the PoA coinbase output. When the selected stakeholder spends that coinbase output, he is effectively "signing" that block. He is telling the network that he agrees that this chain is the true chain.

In order for this to work, stakeholders must sign the block within a certain window. Because signing a block from a month ago really does nothing to protect the network. So we want to make these coinbase transactions expire after a certain period. Let's say 120 blocks for now, but that's adjustable. So if the stakeholder broadcasts a transaction to spend the coinbase output after 120 blocks has passed, this transaction will be deemed invalid and will be rejected by other nodes.

Unclaimed PoA coinbase outputs can be reclaimed or just left as is and considered part of natural coin destruction that happens. Note that due to coin destruction, there will be blocks that are unsignable. This happens when we randomly select a stakeholder address that is lost.

Best Chain

Signed blocks should have a weighted value that is more than unsigned blocks when trying to figure out the best chain. Currently we are doing sum(diff) and the chain with the larger sum(diff) wins. With PoA, signed blocks would be counted X times the normal diff value. If we choose X=2, then signed blocks would be worth twice as much as unsigned blocks with respect to calculating the best chain. So a chain with 6 signed blocks is "longer" than a chain with 11 unsigned blocks of the same difficulty.

I'm proposing we use X=5. The reason why I chose 5 is because if we assume that on the real network we have half the blocks signed, then an attacker with no stake would need 75% of total network hash rate in order to perform the "51%" attack. The way to calculate this is if the network hashrate hashes 10 blocks and half of those blocks are signed, then the strength of chain is 5 (unsigned) + 5*5 (signed) = 30 effective blocks. The attacker needs to match that hashrate with unsigned blocks, so he needs a hashrate that can produce 30 blocks in the same time when the main network is producing 10 blocks. 30 / (30 + 10) = 75%.

There's an attack vector where lucky stakeholders might withhold their signatures in order for them to try to perform a double spend. They could hash in secret and find a block with their signature. When they do, they send a transaction to the real network that they plan to double spend and then release their fork which will be "longer" due to their signed block. The solution to this is to allow a signature (only found in one fork) to also be used to sign the signature block on the other fork if applicable. For example, if both forks have the same signature block (i.e. the fork happened after it) and the signature is only found on one fork, then both fork gets 5xdiff for that signature block.

Another attack vector is the attacker can mine blocks until they find a block that hashes to something that will select themselves as the next stakeholder. When they find that block, they keep it a secret and then start building their fork on top of that block and include their signature transaction. This way, they can launch a double spend with a large stake and only ~15% of the network hash rate. A solution to this is to increase the weight of the signed block based on how deep the signature transaction is in the block chain. So the attacker is forced to build more blocks on top and needs to outpace the main network's blocks, which would likely have more signatures.

Conclusion

Proof of Activity provides the benefit of Proof of Stake without the added network traffic and block chain bloat. It makes it harder for an attacker to perform a "51%" attack. In order to perform a successful attack, he would need a huge hashrate and a huge stake.

The nice thing about this proposal is that you would only need to change 5 things:
- Nodes need to calculate and verify next stakeholder
- New coinbase output for PoA
- PoA coinbase spends will mark blocks signed
- Invalidate transactions that are trying to spend expired PoA coinbase
- New best chain calculation

It would of course be a chain forking change that needs to be scheduled for sometime in the future.

Thoughts?

EDIT: Thanks a lot to iddo for helping me flesh out this proposal.