Proposal for Proof of Activity

I'm throwing out a new idea for an alternative to Proof of Stake, which I'm calling Proof of Activity or PoA for short. The issue with the current PoS proposals is that they create a ton of extra network traffic and cause blockchain bloat because of all the signature requirements. With PoA, we can skip the need for every stakeholder to sign every block. Instead, we randomly pick one stakeholder based on their coin holdings to be the designated signer for that block. Only this chosen person gets to "sign" and if they do, they score a reward for it. If a "51%" attack happens, the fork with the highest combined difficulty and signature blocks takes the win. That's the basic concept. I’ll break down the details below. Random Even Distribution for Stakeholders The cool thing about using randomly selected stakeholders is that if an attacker doesn't have a massive stake, they likely won't be picked to sign the blocks they create. So, their blocks would remain unsigned. That makes it tougher for them to pull off an attack against the legitimate network, which has signed blocks. To successfully attack, they'd need both a huge hash rate and a significant stake. The hash from the previous block serves as a random value that all nodes can recognize and use to choose the "lucky" stakeholder for the next block. However, to make this work, we’ve got to ensure that the random selection of stakeholders is evenly distributed and that every node can verify who the correct stakeholder is for the upcoming block.

So, one point thats a minor engineering thing but important is that you should _not_  be using the same key for currency transactions and mining, because it's reasonable and prudent to keep large volumes of coins offline or at least encrypted. There are a bunch of ways to do this (persistent delegations, one time delegations, ECC math related keys) which have different consequences; I think it's just important to do one. As far as the overall design goes, it seems to me that it has a weakness I'd call "unavailability of the preferable alternative" or a hobson's-choice-attack that I think exists in all the stochastic PoS schemes I've looked at. Lets say there exists a pair of short competing forks.  There is an earlier fork, the one you heard first and a competing later one. Network convergence demands you sign the earlier one, but you're not the chosen miner for the blocks there. You are, however, a chosen node in the weaker fork.  You (like almost all users) have no transactions that would be reversed by mining in one over the other.... so you confirm the weaker one because _doing so cost you nothing, and in the event that it does win, you get more coin that way, so doing so is the rational action_. Your choice isn't "Fork A" or "Fork B", it's "sign" or "do nothing"  _independently_ on each fork you're permitted to sign, and signing costs you nothing and has a non-zero expected return.   With PoW you're burning a finite resource on your preferred choice, and you can't simultaneously mine multiple forks without diluting your resources. This happens is because your stochastic PoS has the property that the existence of a fork expands the network wide pool of stake producing capacity. At least, opposed to some other schemes, creating that fork still requires a POW investment so at least thats good. I'd have to think harder and see more concrete details to do a real analysis, but I think if you think of this under the Byzantine Altruistic Rational model (BAR; Byzantine participants want to burn the earth, Altruistic help out at their own expense, Rational make fairly short term greedy self-interested decisions), I think your scheme defends against byzantine faults better than Bitcoin if and only if your population is very altruist heavy instead of rational. It requires participants to sign the single convergence optimal chain and only that chain, even though doing something else would make them more coin. I think altruistic-heavy is unlikely: just holding a lot of currency for the sake of being able to mine it has a real cost associated with it, so its demanding a lot of expenditure from altruists in the form of stationary funds. If instead the population is rational heavy I would expect your scheme to _increase_ the amount of time required to become confident that a reorg will not happen_ even absent a byzantine attacker_ because a shorter fork may, by luck of which users are on or offline, gather signatures faster and become the rational target for the pow workers to extend, then it's competitor could catch up when some signers wake back up, and so on.   While this instability wouldn't extend beyond your signing horizon, you'd likely lose stability within it, and it also potentially presents interesting attacks against newly bootstrapping nodes.  (e.g. a late created fork with lying timestamps with 1/3rd the POW difficulty but every single block signed because they're all held by an attacker)

There's nothing inherently wrong for someone to sign a weaker fork because he was selected as a stakeholder in that fork. If his signature helps that fork become the best chain, then that is the best chain. The point is we are trying to make it harder for a fork held in secret to outpace the main chain. For your scenario where 2 blocks were found at the same time and one of them has you as the stakeholder, then by all means, sign that block. Since you'd want that fork to win. And let fate decide which fork wins. In the end you still need PoW to build on the chain. It would take a lot of hashpower and stake for an attacker to create 3 blocks that all select the attacker as the stakeholder. I don't think that's going to be a problem. EDIT: I just reread what you wrote. It is possible for an attacker to spend the time and energy to generate tons of blocks to try to build 3 consecutive blocks with him as stakeholder and use those blocks to trick newly bootstrapping nodes. Not sure how big of an problem this is though.

Well I guess it's aimed primarily at byzantine attackers, at expense of higher small-scale reorgs. Also, doing calculated double-spends might be harder due to chaotic environment, but opportunistic double-spends might be easier.

I like the idea of probabilistic PoS. I think the motivating problem is exaggerated but this could have other advantages too. I don't think satoshis are tracked the way you think they do. If there's a 50 BTC coinbase which is split to two addresses you can't say "this satoshi went to output A and this satoshi went to output B". Not a major problem though, if you agree on a randomness seed (deterministically from the blockchain) you can simply trace the chain forward, in each step choosing a random output weighted by number of coins.

Hello gmaxwell, With delegations, it has to involve linkage of the two pubkeys at some block on the chain, and all nodes would continuously have to look at the old block where the linkage was established to verify it. With ECC math related keys, did you mean something similar to type-2 deterministic wallet? Meaning that the seed is blank or known to all, everyone can derive pubkey2 from pubkey1, but only the person who holds privkey1 can derive privkey2 and then use privkey2 (stored unencrypted) to create PoS signatures? This idea is actually quite neat, like deterministic wallet it's secure as long as the PRF is pesudorandom, and there's no need to bloat the blockchain with linkages. Edit: Hmm, I was wrong. If the seed is known to all, privkey2 is stored unencrypted, and some hacker steals wallet.dat and obtains privkey2, then he can simply do privkey2-hash(seed,...) to get privkey1 and spend the coins. gmaxwell, what did you mean by ECC math related keys? But isn't it true that in coblee's proposal you would see both "Fork A" and "Fork B", because the protocol allows for a time period (120 blocks in his example) in which you may do your PoS? Perhaps it might be a good idea for the protocol to enforce that you also wait at least N<120 blocks before you are allowed do your PoS (i.e. spend your reward in this proposal), to avoid the default behavior of stakeholders who'd sign too quickly the first fork that they see, which might not be the best fork because of network propagation/isolation issues ? This idea is supposed to provide security from an attacker who only has large hashpower, so his fork would lose because he doesn't control the privkeys that should do the PoS by spending the rewards. If I understand correctly, you agree that this protocol gives better security from attackers who only have large hashpower, but claim that there are new risks that involve malicious stakeholders who could try to attack? Edit: what I wrote here is nonsense, it applies to Meni's protocol, not to lottery-based protocols. The correct answer is in post #82 etc.

Satoshis are not tracked that way, but you could track it that way. You just need a deterministic way to do it. So just map every satoshi in the input to a satoshi in the output using an ordered 1 to 1 mapping. So for example, if you are looking at a transaction with an input of 50 BTC and 2 outputs of 25 BTC each and you are tracking the a satoshi that is located at 26.11111111 of 50 BTC, then you would follow the 1.11111111 satoshi in the 2nd output. Does that make sense?

Yes, you could do that. You need to be very careful though not only with the order of inputs and outputs, but also with the order of transactions in a block since the satoshi can end up as a tx fee. Essentially this is equivalent to how I suggested to look at it.

There is a standard ordering of transactions in blocks, right? If not, having it alphabetized by address is fine. As long as all the nodes use the same deterministic way, we are good. Satoshi ending up as a fee is fully supported. Since those will just be sent to the miner's block reward and it can continue follow the path. The only catch is it's possible for a miner to destroy coins by not redeeming the full 50 btc in the coinbase. When that happens to our tracked satoshi, maybe we decide that there's no stakeholder for the next block.

I think it would help to clarify about what kinds of attacks it is designed to protect against. 51% attack does not say me anything, what is motive? I guess it's obvious that this scheme simply cannot help against double-spends induced by small-scale (e.g. ~10 blocks) reorgs. In fact, coblee's proposal makes them much simpler. To a larger degree than he thinks. He thinks that large stake is necessary to help yourself to do a double-spend. But this misses the fact that attacker can simply bribe people to make signatures for his double-spending fork. For example, I would announce that if someone adds a signing txn to my chain instead of main chain, I would double his reward. Reward is will be paid in a fork, so if forking is not successful, reward isn't paid. (It's essentially a kickback from double-spend.) Rational entities would prefer 2x reward to 1x reward, so my work will statistically get more signatures if we assume rationality, so double-spending is trivial if you have some fraction of hashpower to mine blocks from time to time (20% of hashpower is enough for 10-block reorg) and you can pay an interesting reward. If you introduce lag, signatures won't help against small-scale reorgs at all. They might help against malicious history rewrites which aim to discredit currency as a whole. (Or a variant of this: an attacker who mines empty blocks.) If this is true, it should be tuned towards this goal: introduce a big enough lag, low X value would be better.

A double spend kind of needs to be done in secret. If it's out in the open, then the entity (like an exchange) that you are trying to double spend against will see that you are trying to perform a double spend attack and they won't let you withdraw. And since stakeholders are chosen at random, you would not be able to tell who to bribe unless you announce your fork and your bribe to everyone.

OK, here's a full description of attacks which, I think, prove that PoA is not useful for anything, and is, in fact, harmful. A. For-profit double-spending. So I want to do for-profit double-spending. If I don't have all resources myself, I'll announce it as a double-spending service. It is a legitimate business in the cryptocurrency world. I need three things: 1. A steady source of double-spend transactions. I announce that I'll include double-spends into my chain for a kickback. I've outline process in details here: https://bitcointalk.org/index.php?topic=101820.msg1119119#msg1119119 (ppcoin thread) I assume that double-spend txns are submitted to me secretly so mechants do not know about them. 2. A source of PoA block signatures. Note that it is not necessary to have a full block to make a signature. I'll just announce hashes of my blocks as well as whatever is necessary for a signature, but not transactions in those blocks. It's possible to implement it as an add-on for a client software which submits these signatures in hope to get reward. 3. A source of hashing power. This is more complex, but one thing is that less than 50% is necessary, and another thing is that if there is certainty that my service works miners would be eager to use my mining pool because their rewards in main chain will be wiped with a reorg. Again, no full knowledge of blocks is necessary, miners only see hashes. I can temporary buy hashing power to bootstrap the thing. So here's how I'll overpower the network: rational entities would submit their signatures both for main chain and into my fork-chain. But they are interested into waiting as long as possible to submit signature into main chain because my chain pays higher reward (from double-spend kickbacks). In any cases, people do not lose their money: if fork works, they get twice the reward. If it fails, they still get reward in the main chain. So, statistically, I'll get somewhat more signatures because main chain would be starved of signatures for some time. (It depends on people getting rewards in both chains within a certain window. This happens from time to time, especially for people with a lot of money.) Thus, I need less than 50% of hashing power to perform a commercial double-spend. B. Malicious 51% attack aimed to destroy a chain. A malicious entity would pay for PoA block signatures for his alternative chain. He needs to pay in a different currency, obviously. Essentially, it would be like a self-fulfilling prophecy: if people know that attacker has enough hashing power, they will trade their Litecoin savings for reward denominated in Bitcoin. ---- So what we get is that this PoA can make it cheaper to perform both for-profit and destructive attacks on a chain due to profit motives. It can only work if majority of nodes are altruistic.

Hello killerstorm, What do you mean by "it is not necessary to have a full block to make a signature" ? In coblee's protocol, the winning address (that should provide the PoA signature by spending the reward) is derived from the block hash, so how could you provide the PoA signature before you solved the block? Are your concerns also apply to canicula and Meni's protocols? So far it seems to me that the only relevant distinction in Meni's protocol is that he proposed voting weights for PoS signatures, which have the property that we can penalize an address that attempted to sign more than one fork, by zeroing its weight. Implementing voting weights is complex and probably involves computationally intensive calculations by all the network nodes. But it might be possible just to penalize an address that attempted to provide PoA signatures in more than one fork, by including the evidence that it signed another fork in the blockchain (same issue arises with Meni's voting weights idea). This idea should be investigated if there plausible attack scenarios (perhaps your scenario). We shouldn't assume that the majority of stakeholders is malicious, but we should assume that the majority is rational.

I'd like to raise two additional issues that weren't mentioned in coblee's OP, mainly because we missed gmaxwell's suggestion to use the key homomorphism feature of ECDSA to delegate signing keys. In terms of economics/philosophy, maybe it's preferable that stakeholders are taxed instead of rewarded, meaning that (say) 0.5 coins of the block reward is taken from the address of the stakeholder, unless he provides the PoA signature. Technically this can be implemented by creating the coinbase txn (e.g. after 120 blocks) that spends those 0.5 coins, simply as a rule that the distributed network follows, without requiring the stakeholder's privkey. We might wish to require that the PoA txn of the stakeholder references the block that he signs, otherwise an attacker could include txn by this stakeholder in his competing fork (if the attacker was lucky enough to derive this stakeholder address in his fork). If the stakeholders participate and provide their PoA signatures, then they aren't taxed. If we delegate signing keys, there's a security risk (that coblee raised) where people would give their signing key to some central entity that would do the signing for them, either because they don't run a node on their computer 24/7, or because the central entity offers them financial benefits. The central entity could then use its signing power for double-spending attacks. Opinions?

I meant that attacker will reveal only block hashes or block headers, but not transactions in blocks. I don't quite understand cunicula's protocol, but it seems to be vulnerable. I think this fixes this problem. In general, I think proof-of-stake can work only if there is some form of punishment for malicious activity. If there is no punishment then one can experiment with malicious activity without repercussions. (It's also worth noting that Meni's protocol does not help against Denial of Service. But it makes bribery for DoS harder, I think.) Well, instead of using weights we can just ban whole address so he won't be able to spend his coins, is that what you've meant? I also considered use of distinct type of addresses for transactions and for stake signing (i.e. you can have your money either on transactions, or on interest-earning account and moving between them takes some time), it might make banning easier. (i.e. we can ban money which is sitting on time deposit account.)

killerstorm, I don't think your attack scenario is feasible. If he can pull of the double spends, the value of the currency will drop significantly. The attacker has to entice more than 50% of all stakeholders (in terms of coins held) to agree to sign his blocks in addition to the main chain. Why would the largest shareholders be interested in helping with a double spend attack. Also remember that the largest stakeholders will be the exchanges and if they are acting rationally, they would sign all the blocks on the main chain and would not sign any of the attacker's chain. I think your attack is theoretically possible but not practical.

Nice idea Coblee!  My first thought was Democritus.  Sign your block, it's like jury duty   I suppose when a block comes up for signature and is not signed by the designated block chain citizen, the block doesn't pass.  So there would be incentive for folks to keep their coins online in citizen groups to make sure to get that reward for when their time is called.  The ecosystem would be very different.  What gmaxwell said.    My reservations here are similar to those with PoX (X!=W) ideas in general:  I'm not sure what the problem is for this solution. Are we going for: 1) a more energy efficient mining process  OR 2) a way to eliminate double spending attacks entirely  OR 3) a way to make double spending attacks more expensive OR 4) something else I'm missing?  There will always be a way for an attacker to spend Z units to get Y in return, when Z>>Y.  That is really hard to stop!   The problem in the system arises when these attacks become feasible for Z~Y or even Z<Y.  One way to prevent this and secure the system is to make sure Z is very big.  Another way is to make sure Y is small.  If the problem in need of solution is double spending, a simple solution exists:  minimize Y.  Don't accept transactions in such a way that the costs of a double spend attack can be regained.  Wait for more blocks if more money is changing hands, don't automate large transactions, keep track of pool percentages, cap your overall outputs, etc. etc.  I guess I just haven't been convinced that this 51% threat is such a huge one, but I suppose eventually we will see some big ones go down.  That being said, I like the idea.  Another alt-coin please

If we assume efficient markets, it will drop significantly once you announce that you want to include a feature which worsens protection against double-spends Also, I don't think you should depend on the fact that stake holders will be reluctant to participate in attacks which decrease exchange rate: "intuitively optimal" solutions can be very different from Nash equilibrium produced by independent rational players. I believe that double-spending with proof-of-stake can be quite like prisoner's dilemma where Nash equilibrium is the worst option. (Which, basically, means that one shouldn't include this feature.) No. You forget that this is a stochastic process: number of signatures available in different forks is a random variable with large variance. Attacker does not need to win all the time, he doesn't need to win most of the time. He needs to win from time to time. Since variance is high from time to time his chain would win in a number of signatures and double-spend would be successful. For example, if attacker has access to 25% of stake he'll get three signatures for three blocks in 1.5% of cases. So at least one double-spend per day. Also note that legitimate stake holders do not always sign blocks immediately, they don't really have an incentive for it. Delayed signing will further shift probability towards attacker (stakeholders who work for attacker have higher motivation to sign ASAP). Maybe. Its feasibility depends on particular economic conditions and altruism/laziness among stakeholders. But why would you make your blockchain theoretically weaker? I really see no reason for it, it doesn't really prevent any kind of attack...

We could have the reward decay the longer it takes users to sign blocks. But that only alleviates the issue. Point taken. Do you see a way to fix up this proposal so that it's not theoretically weaker?

If you want a really good challenge to work on, I suggest: 4) eliminate the need for hard-coded timing parameters, such as 10 minutes in between blocks, or the 2 hour window for rejecting timestamps, or the 2 weeks in between difficulty adjustments. The reason why this problem is worth solving is that you cannot evaluate the soundness of the protocol just by looking at the code itself. You must also make quantitative assessments about the current state of the world's technology and the latency of the internet. There is no objective way to determine if the parameters are configured appropriately. This is an extremely difficult and subtle problem. A sign that you're working on the right problem is if you're considering a 33% attack rather than a 49% attack (in other words, the attacker must be weaker than half the network you know about, but network delays may cause you to underestimate the actual size of the network). This is what it would take to make a theoretically stronger block-chain.