Topic: Proof of Activity Proposal - page 10. (Read 34062 times)

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

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

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.

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

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?

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.

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://bitcointalksearch.org/topic/m.1119119 (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.

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.

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.

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.

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.

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?

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.

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.

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.

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.

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)

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.