Proof of Activity Proposal

[cunicula]

I was looking for concrete attacks on simple-PoA, after thinking about it a bit more I'll describe now what seems to me to be the general framework of how an attack looks like, though I'll use specific parameters for simplicity:
Let's assume 3-fold PoA weight (meaning that a signed block is worth the same as 3 unsigned blocks), and let's assume that the attacker controls 20% of the total stake. This 20% is either the attacker himself, or malicious stakeholders that help the attacker, or rational stakeholders that were recruited by the attacker in secret and their actions must be hidden from the rest of the network.
Let's assume that half of the blocks get signed by the honest network, and those 20% of stakeholders who collude with the attacker still also participate in the honest network (edit: if they don't contribute to the honest network during the attack then on average 40% of the honest branch gets signed, so the merchant's client might wait longer for approval and it'd make the attack even more difficult).
For the attacker to succeed in double-spending via 6-block reorg, he repeatedly attempts to mine his secret branch from the current block. Assuming that the next 6 blocks of the honest network will have 3 signed blocks out of the 6, the attacker needs (at least) 4 consecutive signed block in order to win, so with 20% stake this happens with probability (1/5)^4, meaning that he has to wait 625 blocks (4.3 days, assuming 10min blocks) on average until this event occurs. Note that the attacker wastes some of his hashpower while waiting (whenever he starts extending his secret branch), and that he has to broadcast the double-spending txn to the honest network each time (I was wrong in post #75 about including his txn in the 2nd block of the honest network), so an example scenario would be that the attacker does many purchases of dollars with his BTC, and once every 625 purchases his double-spending could succeed. Therefore, such an attacker needs to generate 4 PoW blocks to compete with 6 PoW blocks of the honest network, i.e. he needs 40% of the total network hashpower. The merchant decrease the attacker's probability of success by waiting for more than 3-out-of-6 signed blocks, e.g. 5-out-of-10 implies that the attacker needs 7 consecutive blocks, which means one double-spending attempt once every 542 days while having 7/17=41% of the total hashpower. If we look at the current state of Bitcoin, I doubt that a single entity could have 20% of all the bitcoins under its control (about 2 million BTC). So I like these odds.

I'm still very interested to hear about other concrete attacks, maybe there are better ways to attack simple-PoA ?

I think you need to prepare for an environment where the total network has only 30 Gigahashes and contains $100 million USD. That is what the network will look like without block reward. The numbers might not be quite good enough for this situation.

I wouldn't worry about double spends coming from someone with USD$20 million of bitcoin. He will be scrambling to keep the network secure and his fortune safe. Only an idiot would try to double spend from this position.

Worry about someone who owns 300 Gigahashes double-spending. 300 gigahashes costs less than $0.5 million USD to acquire. This is far less than the $20 million necessary for stake.

Moreover, the GPUs might retain significant resale value in the event of a devastating successful attack. The bitcoin would not.

[iddo]

How would the miner include that generation txn? The stakeholder has to send this txn request to the miner, otherwise the miner wouldn't know about it? But the incentive of the miner is not to include that txn, because he then gets less reward?

The interest would be a block validity rule. The stake signature indicates the public key that is owed interest. The miner has to include generation sent to this address for the block to be valid. (i.e. the miner looks up 500 blocks back in the blockchain to see who is owed money). People checking block validity make sure this debt was paid, and reject the block if it was not paid.

This sounds like a computationally infeasible task, though maybe I misunderstand what the task is. Could you describe the algorithm that the miners use to decide which interest-payment txns should be included in the blocks?

I was looking for concrete attacks on simple-PoA, after thinking about it a bit more I'll describe now what seems to me to be the general framework of how an attack looks like, though I'll use specific parameters for simplicity:
Let's assume 3-fold PoA weight (meaning that a signed block is worth the same as 3 unsigned blocks), and let's assume that the attacker controls 20% of the total stake. This 20% is either the attacker himself, or malicious stakeholders that help the attacker, or rational stakeholders that were recruited by the attacker in secret and their actions must be hidden from the rest of the network.
Let's assume that half of the blocks get signed by the honest network, and those 20% of stakeholders who collude with the attacker still also participate in the honest network (edit: if they don't contribute to the honest network during the attack then on average 40% of the honest branch gets signed, so the merchant's client might wait longer for approval and it'd make the attack even more difficult).
For the attacker to succeed in double-spending via 6-block reorg, he repeatedly attempts to mine his secret branch from the current block. Assuming that the next 6 blocks of the honest network will have 3 signed blocks out of the 6, the attacker needs (at least) 4 consecutive signed block in order to win, so with 20% stake this happens with probability (1/5)^4, meaning that he has to wait 625 blocks (4.3 days, assuming 10min blocks) on average until this event occurs. Note that the attacker wastes some of his hashpower while waiting (whenever he starts extending his secret branch), and that he has to broadcast the double-spending txn to the honest network each time (I was wrong in post #75 about including his txn in the 2nd block of the honest network), so an example scenario would be that the attacker does many purchases of dollars with his BTC, and once every 625 purchases his double-spending could succeed. Therefore, such an attacker needs to generate 4 PoW blocks to compete with 6 PoW blocks of the honest network, i.e. he needs 40% of the total network hashpower. The merchant decrease the attacker's probability of success by waiting for more than 3-out-of-6 signed blocks, e.g. 5-out-of-10 implies that the attacker needs 7 consecutive blocks, which means one double-spending attempt once every 542 days while having 7/17=41% of the total hashpower. If we look at the current state of Bitcoin, I doubt that a single entity could have 20% of all the bitcoins under its control (about 2 million BTC). So I like these odds.

I'm still very interested to hear about other concrete attacks, maybe there are better ways to attack simple-PoA ?

I think you need to prepare for an environment where the total network has only 30 Gigahashes and contains $100 million USD. That is what the network will look like without block reward. The numbers might not be quite good enough for this situation.

I wouldn't worry about double spends coming from someone with USD$20 million of bitcoin. He will be scrambling to keep the network secure and his fortune safe. Only an idiot would try to double spend from this position.

Worry about someone who owns 300 Gigahashes double-spending. 300 gigahashes costs less than $0.5 million USD to acquire. This is far less than the $20 million necessary for stake.

Moreover, the GPUs might retain significant resale value in the event of a devastating successful attack. The bitcoin would not.

This may all be true, but it's an argument why PoA isn't good enough, rather than an argument why PoA is worse than pure-PoW Bitcoin. The PoW attacker will need (say) 66% of the total hashpower with PoA, instead of 50% with pure-PoW. I agree that it'd be much better if PoA could be improved upon, for example combining PoA with ABAB seems to be a straightforward way to get protection from both double-spending attackers and denial-of-service attackers, I've been thinking about these kinds of ideas. However, I'm still trying to figure out whether there are certain kinds of attacks where PoA is more vulnerable than pure-PoW.

I'm attempting to convince you (see next post) that simple-PoA is a Nash equilibrium for the PoW miners, meaning that it's better for miners to generate blocks in the honest network than it is to generate a competing branch. I agree that it's better for stakeholders to sign all the branches that they see, but if the PoW attacker wouldn't generate his branch in the first place then we're good.

I understand what you are saying. The PoW guys will sign one chain only. I agree with that, but the problems don't end there. If the PoA guys are truly willing to sign everything, then the resulting scheme becomes less secure than pure PoW. The PoA guys can now influence chain selection through corrupt signature behavior. An attacker can send the PoA guys small bribes to influence their signing behavior (i.e. to deny signatures to the main chain). The attacker can then use his own work to attack the main chain. He requires much less work than before because the PoA guys are helping him.

With simple-PoA (post #75), the PoW miners don't sign any blocks. Basically what I'm claiming is that if the competing branches are public then that's fine (everyone should contribute his PoW effort and/or his PoA signature to whichever branch he wishes, and may the best branch win), and if one competing branch is secret then it's useless for double-spending attacks because it couldn't get anywhere near enough PoA signatures while it was secret, and by the time it goes public the needed PoA signatures would be invalid in this branch. Therefore, PoA is gives better security against double-spending by an attacker with large hashpower, because the nature of double-spending attacks is that they need to stay secret at the first stage, and they couldn't get enough PoA signatures at the first stage.

I'd still like to solicit concrete attacks on simple-PoA (attacks that couldn't be carried out just as easily with pure-PoW, I didn't look into your "double double spend" thread closely enough yet).

[cunicula]

This sounds like a computationally infeasible task, though maybe I misunderstand what the task is. Could you describe the algorithm that the miners use to decide which interest-payment txns should be included in the blocks?

No it is not a computational task at all. It operates just like regular old block reward.

The miner looks up in the block chain who signed the block 500 blocks past, block t-500. There is a record of public keys there. At the time of signing, each public key had a certain amount of coins. This indicates the principal owned by each signatory, P_i, indexing the 5-10 signatories by i. The coins also had a certain amount of age (i.e. blocks since they had last been spent or received an interest payment). This indicates the # of blocks for which the coins are owed interest, T_i. T_i is in units of 52560 blocks (i.e. years). Finally, blocks t-491, t-492, ..., t-500 have a total number of signatures on them. The total # of signatures (between 50 and 100) determines the interest rate to be used, r=0.015*(S/100)-0.0075. Now the amount due to each signatory is P_i*(exp(r*T_i)-1); round down to the nearest satoshi. The block simply prints money and sends it to the signatories keys. If it fails to do this, then it is not a valid block and all the clients, miners, will reject it. You could still seek out signatories for it, but no one can build on it, so it drops out of the chain.

With simple-PoA (post #75), the PoW miners don't sign any blocks. Basically what I'm claiming is that if the competing branches are public then that's fine (everyone should contribute his PoW effort and/or his PoA signature to whichever branch he wishes, and may the best branch win),

Here is how it works. Assume people sign everything they can by default. I have 50% of hashing power.

I spend at time t in the main branch and I want to revoke this spend. I wait for 6 confirmations in the main branch. The guy I am ripping off delivers the goods. Meanwhile I build a 6 block long secret branch from t-1, eg. t* t+1* t+2* t+3* t+4* t+5* t+6*. The block at t* contains my double spend.

Now I announce my secret chain which has 6 unsigned blocks. According to your rules, every block on my secret chain is currently eligible for a signature. By assumption, the regular PoA guys immediately give me their signatures. Once that happens I can continue extending my attack chain.

There is also the main chain. I should be even with it because I have 50% of hashing power. By assumption, the main chain also has full signatures up to this point.

Now normally, I would have a 50-50 chance of winning vs. the PoW miners. I still do. However, I can tip this 50% into my favor. I announce publicly that I will send bribes to whoever refuses to sign the main chain. I am assuming the identity of the public keys who should sign the main chain is public knowledge (i.e. the lottery winners are public knowledge even before they claim their prize). In the attack fork, I send the keys that should be signing the main chain small amounts of money. The owners of these keys now have a good reason to withhold their signatures from the main chain.

Of course, I could bribe people via PoW too, but that is much less efficent. To execute a PoW bribe, I include a big txn fee in blocks within the attack chain. In expectation, this bribe is divided evenly among all possible miners. By comparison, the PoA bribe is targeted at exactly the key I need to bribe. Thus, the PoW bribe will need to be many times larger than the PoA bribe. The cheaper bribe makes double-spends easier. More generally I can use these targeted bribes to win with just a minority of hashing power.

You can avoid this by requiring the signatures to come before the block enters the chain. In this case, you won't know who to bribe until it is too late to bribe them.



 

[iddo]

I spend at time t in the main branch and I want to revoke this spend. I wait for 6 confirmations in the main branch. The guy I am ripping off delivers the goods. Meanwhile I build a 6 block long secret branch from t-1, eg. t* t+1* t+2* t+3* t+4* t+5* t+6*. The block at t* contains my double spend.

Now I announce my secret chain which has 6 unsigned blocks. According to your rules, every block on my secret chain is currently eligible for a signature.

No, according to simple-PoA rules, your block t* isn't eligible because the PoA for it cannot be put inside block t+7*, only your blocks t+1* t+2* t+3* t+4* t+5* t+6* are eligible. Therefore, if the merchant saw your txn at block t was signed and then saw that the next 6 blocks t+1 t+2 t+3 t+4 t+5 t+6 were all signed, he would then send you the merchandise, and now you make your secret branch public, but you can get signatures for only 6 out of the first 7 blocks that you generated, while the honest network has 7-out-of-7 signed block there. Assuming 3-fold PoA weight, it means that the honest network is effectively ahead of by 2 blocks (your t* is has weight=1, the honest t has weight=3).
If the merchant didn't see 6 consecutive signed blocks, then he waits the safety length of up to 12 blocks so that half of them are signed (assuming the incentives for stakeholders are in place so that at least half the blocks get signed on average). When you release your secret branch after 12 blocks, only the last 6 blocks in your branch are eligible for PoA signature, so the honest branch of 12 blocks where half are signed wins again.
Edit: a better way to describe it without getting into indexing troubles is simply to say that the merchant waits for 7 signed blocks (starting from the block where the relevant txn resides), so when the attacker releases his secret branch (of whichever length) only the last 6 blocks of it would be eligible for PoA signature, so the honest chain wins, unless the attacker has huge hashpower and he generated significantly more (unsigned) blocks than the honest network. And the only other thing that's left to say is that waiting for 7 signed blocks would take less than 14 block on average.

[cunicula]

No, according to simple-PoA rules, your block t* isn't eligible because the PoA for it cannot be put inside block t+7*, only your blocks t+1* t+2* t+3* t+4* t+5* t+6* are eligible. Therefore, if the merchant saw your txn at block t was signed and then saw that the next 6 blocks t+1 t+2 t+3 t+4 t+5 t+6 were all signed, he would then send you the merchandise, and now you make your secret branch public, but you can get signatures for only 6 out of the first 7 blocks that you generated, while the honest network has 7-out-of-7 signed block there. Assuming 3-fold PoA weight, it means that the honest network is effectively ahead of by 2 blocks (your t* is has weight=1, the honest t has weight=3).
If the merchant didn't see 6 consecutive signed blocks, then he waits the safety length of up to 12 blocks so that half of them are signed (assuming the incentives for stakeholders are in place so that at least half the blocks get signed on average). When you release your secret branch after 12 blocks, only the last 6 blocks in your branch are eligible for PoA signature, so the honest branch of 12 blocks where half are signed wins again.
Edit: a better way to describe it without getting into indexing troubles is simply to say that the merchant waits for 7 signed blocks (starting from the block where the relevant txn resides), so when the attacker releases his secret branch (of whichever length) only the last 6 blocks of it would be eligible for PoA signature, so the honest chain wins, unless the attacker has huge hashpower and he generated significantly more (unsigned) blocks than the honest network. And the only other thing that's left to say is that waiting for 7 signed blocks would take less than 14 block on average.

Sorry about the indexing problem.

It doesn't matter which branch wins after 6 or 7 or 12 confirms. It matters which branch wins in the end. Simple PoA is delaying resolution of voting into the future. This opens up a time window when we know the exact identity of the signatories and can bribe these individuals to vote for one branch or another. This means the attacker can win easily even if he is behind when the secret branch is announced.

If you require PoA signature(s) to be submitted in conjunction with each mined block, then you eliminate the time window. This solves the bribery problem. You won't know the identity of the person you need to bribe until it is too late to bribe them.

[cunicula]

A very simple, radically different, and secure PoS algorithm is to appoint an elected committee that controls all txns.

Say there are 9 public keys that belong to committee members. These can start out as some founding fathers of the coin.
Any valid txn block must be signed by 5 out of committee 9 keys. This solves the consensus problem.

The committee could be corrupt. Thus they need to be voted in and out of office.

Any coin holder can destroy 100 coins in order to mine a voting block, i.e. he sends them to a destruction address. The voting block does not include txns, just votes.
The coin holder proposes the removal of one committee member (public key) and the addition of another committee member (public key). Normally, I think you would nominate yourself.

He then draws and announces a random number (he can control the random number seed, it won't really matter). The random number is then hashed 10,000 times to draw a random electorate.
The electorate is drawn randomly from satoshis that have moved within the last year (thus avoiding the problem of dead voters). Major stakeholders would get to vote more than once.

The voters then either vote yes, no, or fail to vote. People who fail to vote are assumed to vote no.
If a block eventually gets 5,001 yes votes, then it enters the blockchain and a committee member is replaced. His signing key no longer affects block validity.

The voting blocks are valid even if they are not signed by any committee members. Voting blocks only enter the block chain if they pass.

There is no single point of failure here. If a committee member gets compromised or fails to perform his duties, he gets replaced.
The committee can also perform useful functions such as levying txn fees to fund development work or any other public good.
If someone don't like this they can vote the bastards out.

[iddo]

If you require PoA signature(s) to be submitted in conjunction with each mined block, then you eliminate the time window. This solves the bribery problem. You won't know the identity of the person you need to bribe until it is too late to bribe them.

Not so clear even for PoA submitted in conjunction with each mined block: the miners have to broadcast the blocks that they solved so that the stakeholders would attach their signature to those blocks, therefore the attack can listen and bribe these stakeholders too, no? If the attacker puts the bribe in his branch only after the stakeholder already forfeited his opportunity in the honest chain (to make sure that stakeholders don't cheat on him), then stakeholders have to trust that the attacker will deliver the bribe, both here and with PoA, so I don't see much of a difference. If the attacker puts the bribe in his branch immediately (so the stakeholders can cheat on him), then I also don't see much of a difference here versus PoA.

It doesn't matter which branch wins after 6 or 7 or 12 confirms. It matters which branch wins in the end. Simple PoA is delaying resolution of voting into the future. This opens up a time window when we know the exact identity of the signatories and can bribe these individuals to vote for one branch or another. This means the attacker can win easily even if he is behind when the secret branch is announced.

So basically we have reduced the problem from the scenario where there was a secret branch being generated, to the more straightforward scenario where the attacker simply has a shorter branch than the honest branch, and he's trying to use bribes in order to get his branch to win. This public branch of the attacker can even be of length 0 (if he's trying to bribe miners), or length 1 (if he's trying to bribe stakeholders). The first question that springs to mind: do you claim that PoA is less secure than Bitcoin because of this scenario? I'm curious to know what's your answer to this question. It seems to me that the answer is "no", with pure-PoW bitcoin the attacker can simply put high txn-fees in his branch, to encourage the miners to switch to him. The earlier advantage of pure-PoW over PoA that we discussed doesn't apply here, namely the advantage where PoW miners would lose if the attack fails, while PoA stakeholders wouldn't lose because they signed both branches (here the stakeholder who colludes with the attacker would lose the follow-the-satoshi lottery reward that he would have received in the honest chain, if the attacker fails).

Anyway, either with pure-PoW or with PoA, I'm not so sure that we should consider this public bribes scenario to be an "attack" that demonstrates a weakness of the protocol. Wouldn't you agree that this is simply a free-market issue, meaning that if the txn-fees on the honest chain are large enough then the miners or stakeholders (recall that in PoA the lucky stakeholder gets e.g. 10% of the total txn-fees) will prefer the honest chain over the attacker's shorter chain, and if the txn-fees are too low then double-spending attacks could be carried out because it might be rational for miners/stakeholders to help the attack? I'm not even sure if we should call this "double-spending", maybe we can use "public-double-spending" to differentiate, and I'm also not so sure if the entity who tries to carry out public-double-spending should be called an "attacker", it seems to me that all the participants in this scenario are acting legitimately rather than fraudulently (it's arguable, even for regular double-spending). But anyway this is just semantics, we agree that we should assume that the (majority of the) participants are acting rationally, and that's all that matters.

BTW from the point of view of the atomistic miner/stakeholder, it's not so clear why it's rational to help the attacker, given that the honest chain is longer and therefore if he's the only one who helps the attack then he would lose.

If you insist that this public bribes scenario is likely to be a problem, then which protocol to you propose to overcome this (perceived) problem? I'm not sure whether you'll manage to convince me that the likelihood of this problem is high, but if there's a good protocol that defeats this kind of attackers who offer public bribes then it'd be worthwhile to consider.

In any case, the main issue that concerns me is still whether some aspect of simple-PoA is weaker than pure-PoW, concrete attacks please? If it becomes more clear that simple-PoA is sound, then I'll move on to consider what's the best way to extend simple-PoA to handle attackers who generate empty blocks. But I'm happy to also discuss other protocols at the same time.

[cunicula]

Simple Attack where PoA is worse then PoW (no bribery):

All chains are signed by default if stakeholder participates. A fraction p of stakeholders participate. Attacker owns positive stake share, 0<s<1  and 0<p+s<1.  Attacker has workshare 0<w<1 of aggregate hash rate and the extra weight on signed blocks T. Attacker uses his stake to swing things in his favor.  Attacker wins if (1+pT+sT) w > (1+pT)(1-w) or if w/(1-w) > (1+pT)/(1+pT+sT). If T=0 (i.e. pure PoW) then the right hand side is equal to 1. If T>0, then the right hand side is less than 1, indicating that the attack becomes easier. In practice, however, the difference is really small unless p is small and s is large. Just provide incentives to keep p high and you should be fine. I'm much more worried about bribery than this.

Stuff you can do about bribery (in order of perceptive importance):
1) The reward system should discourage people from signing multiple chains (i.e. the coin-age scheme and/or ABAB scheme). Bribes would still work, but you could never get away with bribing a very small minority. You would need to bribe the majority. This is potentially difficult (I don't really think everyone is going to accept a bribe).

2) Remember that the feasibility of bribery depended on the attacker mining a one-block long secret fork. Without the secret fork, all the bribes can be stolen and then ignored. A simple defense is to make secret blocks computationally infeasible.

Consider the scheme with 5 sequential signatures. If the attacker has 1% of stake, he needs to mine 10 billion blocks just to construct a one-block long secret fork. It is reasonable to assume that the reward from mining 100,000 blocks on the main chain exceeds the reward from theft (I can't really say 10 billion because the attacker dies first). If you just do 1 signature, then the attacker with 1% stake needs to mine 100 blocks to get the one-block long secret fork. That still would help to discourage him, but I think you need at least 2 signatures -> 10,000 blocks for this to become really effective.

[You could put double-spends in a public fork and then issue bribes to extend the public fork. Thus, it makes sense to prevent double-spends in public forks. I think you can do this by requiring the miner to announce his tentative block to any signatory who requests it. The peers can just pass around the block header and the miner's IP address. The signatories can check if they are designated signers based on the block header. If they are, they can request full txn information from the miner's IP address. Once they have verified the txns are valid, they can sign the txn information and the block header, and submit this back to the miner. The miner can then send the updated data to the next signatory. After the fifth signature, the miner and the fifth signatory can announce the full block on the P2P network.]

[cunicula]

In any case, the main issue that concerns me is still whether some aspect of simple-PoA is weaker than pure-PoW, concrete attacks please? If it becomes more clear that simple-PoA is sound, then I'll move on to consider what's the best way to extend simple-PoA to handle attackers who generate empty blocks. But I'm happy to also discuss other protocols at the same time.

If you want to suggest the ABAB system with PoA added on top, that is fine with me. If you want to do just PoA alone, then I don't understand. PoA is not very strong against someone with a lot of work, i.e. it is not strong without substantial block reward.

[iddo]

Simple Attack where PoA is worse then PoW (no bribery):

All chains are signed by default if stakeholder participates. A fraction p of stakeholders participate. Attacker owns positive stake share, 0<s<1  and 0<p+s<1.  Attacker has workshare 0<w<1 of aggregate hash rate and the extra weight on signed blocks T. Attacker uses his stake to swing things in his favor.  Attacker wins if (1+pT+sT) w > (1+pT)(1-w)

But what is the nature of the attack here? If the attacker is mining in secret then the LHS is (1+sT)w instead of (1+pT+sT)w, and if the attacker is mining in public then he's simply helping to generate the honest branch.

[iddo]

This sounds like a computationally infeasible task, though maybe I misunderstand what the task is. Could you describe the algorithm that the miners use to decide which interest-payment txns should be included in the blocks?

No it is not a computational task at all. It operates just like regular old block reward.

The miner looks up in the block chain who signed the block 500 blocks past, block t-500. There is a record of public keys there. At the time of signing, each public key had a certain amount of coins. This indicates the principal owned by each signatory, P_i, indexing the 5-10 signatories by i. The coins also had a certain amount of age (i.e. blocks since they had last been spent or received an interest payment). This indicates the # of blocks for which the coins are owed interest, T_i. T_i is in units of 52560 blocks (i.e. years). Finally, blocks t-491, t-492, ..., t-500 have a total number of signatures on them. The total # of signatures (between 50 and 100) determines the interest rate to be used, r=0.015*(S/100)-0.0075. Now the amount due to each signatory is P_i*(exp(r*T_i)-1); round down to the nearest satoshi. The block simply prints money and sends it to the signatories keys. If it fails to do this, then it is not a valid block and all the clients, miners, will reject it. You could still seek out signatories for it, but no one can build on it, so it drops out of the chain.

Ahh, sorry, I was under the impression that all stakeholders are entitled to receive interest-payments, not just stakeholders who sign blocks. I've look at your previous posts and indeed when you were consistent when describing the interest-payment system, so I was just confused. I think that the post that got me confused is this:

if I understand correctly the purpose here is (supposedly) that stakeholders wouldn't want to sign the attacker's branch because we expect that the attacker's branch will get only 5 signatures or so, while we expect that the branch of the honest network will get 10 signatures, and stakeholders receive larger rewards if there are more signatures. But isn't there a problem with your suggestion because a particular stakeholder who got chosen in the attacker's branch doesn't also get chosen in the honest branch (except for with negligible probability), so it would be rational for this particular stakeholder to sign that attacker's branch in order to have a chance to get his individual reward (in the honest branch he wasn't chosen and wouldn't get any reward). Maybe the way to fix this issue is that the individual stakeholders never get any reward for the signature that they provide, and instead just have the rule that if more signatures are provided (closer to 10 instead of 5) then all the stakeholders are rewarded collectively, via lower rate of inflation or some other kind of reward?

You are not getting a direct reward from signing. You can claim your interest in any case, just at a later date.

Could you explain what you meant here? It seems that this interest-payments system is giving a direct reward to the stakeholder who signed, it's just that the reward is delayed by 500 blocks instead of being given immediately. How could you claim your interest if you haven't won the follow-the-satoshi lottery?

Edit: looking at your other comment:

Winning the lottery frequently does not directly affect the amount of coins you earn. The lottery win allows you to withdraw early without facing an early withdrawal penalty (foregone interest). Winning frequently increases liquidity of your savings, but does not give you a bigger monetary reward. It is a very very small advantage.

I think that maybe you meant that you can move some of your old coins and therefore still continue to earn interest on the coins that you haven't moved, but still to actually receive the interest-payment you have to win the lottery?

[cunicula]

Simple Attack where PoA is worse then PoW (no bribery):

All chains are signed by default if stakeholder participates. A fraction p of stakeholders participate. Attacker owns positive stake share, 0<s<1  and 0<p+s<1.  Attacker has workshare 0<w<1 of aggregate hash rate and the extra weight on signed blocks T. Attacker uses his stake to swing things in his favor.  Attacker wins if (1+pT+sT) w > (1+pT)(1-w)

But what is the nature of the attack here? If the attacker is mining in secret then the LHS is (1+sT)w instead of (1+pT+sT)w, and if the attacker is mining in public then he's simply helping to generate the honest branch.

I'm assuming that he was mining in secret, but then he revealed his secret chain to the world. Due to promiscuous signing (if I can call it that), the secret chain can catch up with less than 50% work.

[cunicula]

Could you explain what you meant here? It seems that this interest-payments system is giving a direct reward to the stakeholder who signed, it's just that the reward is delayed by 500 blocks instead of being given immediately. How could you claim your interest if you haven't won the follow-the-satoshi lottery?

You can't claim interest until you win the lottery. But you get to claim more interest if win the lottery later. The purpose of this is to provide an incentive to sign only the most plausible winning chain.

You can think of it like this. 1) You always have some potential interest reward in the chain. 2) You are trying to claim this interest reward by signing. 3) When you sign it is a speculative bet on which chain other people will sign. 4) If you bet on a chain that is unlikely to win, but this chain wins anyway, then you only get a portion of your interest reward and forfeit the rest. 5) If you wait to sign until later when your number comes up in a chain that is likely to win, then you get to receive your full interest reward + any additional interest you have accumulated in the interim.


Perhaps an extended example will help:

Suppose I have principal A and I earn a fraction f(F) of A per block in interest. The fraction f is an increasing functoin of the # of signatures, F, in the current and subsequent 9 blocks. I start out with 99 blocks in accumulated interest and the next block will give me 100 block of accumulated interest.

Now the chain forks into two valid blocks at history H as shown below. I've indicated places where I could sign are marked with "*", and other people's signatures with "b"

H-b-b-b-b-*

H-b-b-b-b-b-b-b

Suppose that 90% of people obey the rule and do not sign a block that is behind. Should I also obey this rule?

Obey Case:

Suppose I obey the rule just like the good 90% of stakeholders. Then the top sequence cannot be extended and will orphan.

The bottom sequence will be extended. Say that I win the lottery 300 blocks later.

H-b-b-b-b-b-b-b-(300 blocks)-b-b-b-b-*1

By now I have accumulated 400 blocks of interest. This is the only chain and I sign it. If I do so, then I earn 400AE[f_*1] in interest where E[f_*1] is the expected value of f_*1 when I sign at *1.

Disobey Case:

Suppose that I sign the top fork and this fork wins (if it fails to win, then the outcome is the same as before). When this occurs the top fork will win with low signatures.
Remember that 90% of stakeholders would refuse to sign the top fork as long as it is behind. Until it catches up it will have the bare minimum of signatures. The only plausible catchup process
is a lucky mining draw as shown below. (It is not clear why a miner would extend the top fork instead of working on the bottom one, but suppose they he does so out of ignorance)

H-b-b-b-b-*2-H-b-b-b-b-b

H-b-b-b-b-b-b-b

Now the top fork is ahead and everyone will sign it exclusively. I will get a reward of 100AE[f_*2] where E[f_*2] is the expected value of f_*2 when I sign at *2. Note that the block I signed has the minimum number of signatures, so E[f_2*]<E[f_1*]

Now extend this another 299 blocks and suppose I win the lottery again at *3. (I might win at another time, but this case is the easiest to explain)

H-b-b-b-b-*2-H-b-b-b-b-b-(299 blocks)-b-b-b-b-*3

This is the only chain and I sign it. If I do so, then I earn 300AE[f_*3] in interest where E[f_*3] is the expected value of f_*3 when I sign at *3. This case is identical to the obey case, so we can assume that E[f_*3]=E[f_1*].

What is my total payoff if I disobey? 100AE[f_2*]+300AE[f_*3]

Since [f_2*]<[f_3*]=[f_1*], the payoff I get if I disobey is smaller than the payoff I get if I obey. Compare,

100AE[f_2*]+300AE[f_*3] <  400AE[f_*1]

Therefore, if a positive fraction of other stakeholders obey, it is a nash equilibrium for me to obey also.

[iddo]

Simple Attack where PoA is worse then PoW (no bribery):

All chains are signed by default if stakeholder participates. A fraction p of stakeholders participate. Attacker owns positive stake share, 0<s<1  and 0<p+s<1.  Attacker has workshare 0<w<1 of aggregate hash rate and the extra weight on signed blocks T. Attacker uses his stake to swing things in his favor.  Attacker wins if (1+pT+sT) w > (1+pT)(1-w)

But what is the nature of the attack here? If the attacker is mining in secret then the LHS is (1+sT)w instead of (1+pT+sT)w, and if the attacker is mining in public then he's simply helping to generate the honest branch.

I'm assuming that he was mining in secret, but then he revealed his secret chain to the world. Due to promiscuous signing (if I can call it that), the secret chain can catch up with less than 50% work.

Yes, interesting.
So basically what happens here is that attacker has to wait the safe double-spend length before making his branch public, and simple-PoA guarantees that when the attacker's branch goes public it will be shorter (with less signatures) than the honest branch, but if your equation holds then eventually the attacker's branch will win.
Let's consider this attack with particular parameters. Since wer're interested in the case where pure-PoW is safe and simple-PoA is vulnerable, and since an attacker with 51% hashpower can defeat pure-PoW, the interesting case is when the attacker has less than 50% hashpower, so let's say he has 40%, and that the PoA weight is 3-fold (so T=2) and half of the rational stakeholders paricipate (so p=1/2).
We get (1+1+2s)4/10>(1+1)6/10, meaning that we need s=1/2
Therefore the attacker needs half of activate stake under his malicious control in order to carry out this attack. In Bitcoin terms, if the total stake is about 10 million BTC, then the active stake would be 5 million BTC, so the attacker would need 2.5 million BTC and 40% of the total hashpower. So as with the previous attack, I like these odds.

Also, I still take issue with your initial assumtion:

All chains are signed by default if stakeholder participates.

Using the terminology from post #47, we could say that h of the stakeholders are honest which means that they'll use a client that follows the protocol so they'll only sign the longest branch, r of the stakeholders are rational so they'll use a modified client and sign all branches, m of the stakeholders are malicious stakeholders that are under the control of the attacker and they'll only sign his shorter branch, and h+r+m <= 1
Now the equation is (1+mT+rT)w > (1+hT+rT)(1-w)
Wouldn't you agree that h>0 ? Simply because some stakeholders care about the health of the cryptocurrency network and wouldn't want to see double-spending attacks take place. Actually I know that h>0 because I personally would prefer to use a client that follows the protocol rather than the "rational" client. Also, we can have non-protocol methods to deal with rational stakeholders who care about their own reputation rather than the health of the network, for example some website could listen on the network and record addresses of stakeholder who sign short branches, so if some stakeholder does it repeatedly he would gain a bad reputation.

BTW just to make it clear why the m fraction of stakeholders aren't behaving rationally, note that if they win the follow-the-satoshi lottery on the honest branch then they refuse to sign and thereby forfeit their reward, even though the honest branch is longer.

Regarding my dream objective, it's probably just wishful thinking to hope that we could have a proof-of-stake protocol that is always at least as safe as pure-PoW. In reality it'd always be a game of trade-offs that depend on variables that describe the underlying assumptions. I hoped that the assumption that 50% of the stakeholders aren't malicious would be enough, but if we look again at your attack with say w=45% hashpower, h=0, r=1/2, T=2, then we'd get m<1/2 and therefore to guarantee m>=1/2 we'd need for example T=1 (i.e. 2-fold PoA weight). But anyway the attack described in post #78 works with m<1/2 and T=1  (for example).

So we now have two concrete attacks (your attack at post #88 and my attack at post #78) that demonstrate the trade-offs. When setting particular parameters, it seems to me that simple-PoA is advantageous (by far) over pure-PoW.

Regarding bribe attacks, I haven't fully thought it through yet. Could you please reply to the previous question that I was curious about, namely whether you think that simple-PoA is less secure than pure-PoW because of the bribes attack? I explained why I think that the answer is "no" in post #87.

Edit: I'm also curious to hear your answer regarding the game-theory aspect of the bribes attack:

BTW from the point of view of the atomistic miner/stakeholder, it's not so clear why it's rational to help the attacker, given that the honest chain is longer and therefore if he's the only one who helps the attack then he would lose.

To elaborate a bit: when the attacker sees that a stakeholder won the follow-the-satoshi lottery on the honest branch, he puts a txn in his public shorter branch that gives this stakeholder even more coins (either the attacker puts the txn immediately so he has to trust the stakeholder not to sign the honest branch, or promises to put the txn after the 6-block validity length so that the stakeholder has to trust the attacker). So if this particular stakeholder is the only one who colludes with the attacker, then the attack would most probably fail and this stakeholder would lose the lottery reward that he would have received on the honest branch. Can you please explain why it's rational for the atomistic stakeholder to collude with the attacker by accepting the bribe? I suppose that the bribes will have to be very large in order to provide an incentive for stakeholders to collude with the attack, which implies that the double-spending txn is even larger.

[iddo]

Regarding whether protection from attackers who deny service (by generating empty blocks) can be incorporated into PoA:

I think that the objective that we should aspire to achieve is something like: an attacker couldn't deny "too many" txns unless he controls at least 50% of the active stake and a huge amount (say 90%) of the total hashpower.
Let's take some simple example that shows why ABAB (posts #53, #68) achieves this objective. Suppose there're 20 honest stakeholders with 5 BTC each, they can do round-robin to generate the type-B blocks, i.e. each stakeholder waits 20 turns so he'd have 20*5=100 coin-confirms and then try to generate type-B block, or they could all try to generate the type-B block simultaneously i.e. each stakeholder with 5 coin-confirms trying to meet the difficulty/5 threshold, and their combined difficulty will still be (1/20)*(difficulty/5) for each type-B block. So effectively the distributed honest network always has 100 coin-confirms. Now if the attacker has 50% of the total stake, i.e. 100 coins, then with his huge hashpower he will defeat the honest network by generating all (or more than 90%) the blocks. If for example the attacker had only 50 coins, then he would only generate every 2nd type-B block, and therefore at least 1/4 of all the blocks will be generated by the honest network, and we're good.

However, ABAB has highly significant implications, in particular: no mining pools are possible for type-B blocks (post #80).

We could instead try to incorporate BDD into the winning branch calculation (given the rationale in post #71), meaning that we look at the coin-confirms of the txns inside the block, instead of the coin-confirms of the stakeholder who signed the block. However, it's unlikely that we could meet the objective of requiring the attacker to have 50% of the total stake, because it's unreasonable to expect that anything near 50% of the total stake will be used in the txns inside the blocks that the honest network generates, and therefore the attacker could defeat the honest network with much less than 50% stake.

How about using something like AAAAAAAAABAAAAAAAAAB (abbrev A9BA9B) ? The rule would be: at every type-B block increment by 1 the coin-confirms of every coin, and when some coins are used to sign type-B block we reset the coin-confirms of those coins back to 1. As mentioned in the example, if the attacker has 25% of the total stake then he'll only be able to generate every 2nd type-B block, so we are guaranteed that 1/20 of all the blocks are generated by the honest network. Is that good enough? Here mining pool could still generate 90% of all the blocks.

simple-PoA can be used together with A9BA9B to provide much better protection from double-spending attacks.

Though I guess that we could come up with better ideas than A9BA9B, any suggestions?

[cunicula]

However, ABAB has highly significant implications, in particular: no mining pools are possible for type-B blocks (post #80).

...

How about using something like AAAAAAAAABAAAAAAAAAB (abbrev A9BA9B) ?
...


simple-PoA can be used together with A9BA9B to provide much better protection from double-spending attacks.

Though I guess that we could come up with better ideas than A9BA9B, any suggestions?

Do you like A9BA9B because of reduced variance of A block arrival times?
Or is it about distributing a larger share of rewards to A block miners?

If it is the former, that then A9BA9B is fine with me. Reduced variance (a la litecoin) has some advantages. If it is the latter, I don't agree. I think rewards should be split 50-50 between A and B blocks. Increasing rewards for A blocks will increase PoW participation. PoW miners need to compensated for electricity and hardware and will drop out without this compensation. Likewise, increasing rewards for B blocks will increase PoS participation. PoS miners need to be compensated for keeping their computers on and exposed to the network. They are facing a significant risk of theft. There is a trade off here. A 50-50 split seems reasonable to me. I think you can reward the miners of A and B blocks with an evenly divided long-run average of txn fees.


I think double-spend protection is completely fine with either ABAB or A9BA9B. I agree that adding simple PoA could improve things from say "completely fine" to "excellent." There is also a small chance it could make things worse. PoA's effectiveness depends on how it is used. The best case scenario is that everyone participates in PoA and everyone signs one chain only. Then PoA will make the network very secure. The middle case is that everyone participates in PoA, but everyone signs every chain they see. Then PoA will be neither beneficial nor harmful. The worst case scenario is that hardly anyone participates in PoA. Then PoA opens up a weak point for attack.

In simple PoA, the "promiscuous signing" troubles me somewhat, but it's not be a make it or break it issue. Likewise bribery is a little troubling, but not a make it or break it issue. I'd be more worried about these if there were no ABAB system in place. The most serious danger  is non-participation. There needs to be some reward offered to encourage people to participate. I could accept the 'fancy' variable interest reward that discourages "promiscuous signing" or a simple share of the long-run average txn fee which encourages "promiscuous signing". I'm willing to believe that many people will sign honestly out of altruism. It doesn't need to be everyone. Due to bribery concerns, I don't think a highly variable txn fee reward is a good idea.

For both B blocks and PoA, it is important to mitigate risks for signatories. This is almost as important for participation as the reward. Signatories need to store unecrypted private keys online. For a large balance, this is much too risky. There needs to be some redesign of the protocol to mitigate (but not remove) the theft risk. I proposed an idea for a hard fork modification for PPCoin here:
https://bitcointalk.org/index.php?topic=115608.msg1319290#msg1319290
https://bitcointalk.org/index.php?topic=115608.msg1319612#msg1319612 (I suggested something else too, but the linked proposal is much better)
My gut feeling is that mitigation of theft risk will be well-received. Users worry a lot more about personal theft risk than they do about collective network security.

[iddo]

Hello cunicula,

I'll respond to your other posts soon, but I've come up with a new idea that deals with attackers who generate empty blocks, different than ABAB, so I'd like to throw it out there.

This idea is more in the spirit of PoA and it doesn't interfere with mining pools. Suppose the attacker who wishes to generate empty blocks has 99% of the total hashpower. Our objective is to let the honest network generate every (say) 7th block, instead of every 100th block that the 99% malicious hashpower implies. The protocol rule is that at every 5th block we xor the hashes of the last 5 blocks, then derive from the xor'd result an address of a uniform-random stakeholder via follow-the-satoshi technique, and this lucky stakeholder is allowed to create the 7th block (i.e. two blocks after the current 5th block) just by collecting the txns that he wishes to put inside the block and signing it with his privkey, without doing any PoW, The protocol still allows this 7th block to be generated in the regular fashion by anyone else via PoW according to the current difficulty, in case the lucky stakeholder isn't active.
Comments please?

Edit: I'll mention why I think that security against an attacker who generates empty blocks to destroy the network is important. It's possible to say that if the attacker has 99% hashpower then still every 100th block on average will be generated by the honest network, and since the attacker wastes his resources while generating empty blocks the network can survive with 1/100 of the blocks until the attacker gives up. However, the attack could quite plausibly have a snowball effect, meaning that more and more honest miners will quit as confidence in the network is being lost. With the idea above, the stakeholders would control one block at predictable short intervals (every 7th block in the example), so the network could continue to function, which might discourage the attacker from wasting his resources on this kind of attack.

Let me mention that in general I'm trying to come up with the most simple (to implement, as well as to analyze) protocol change so that we could hardfork Litecoin. If it'd be successful then maybe Bitcoin could incorporate or refine these ideas next. However, if you'd like to design an even better protocol (that wouldn't have mining pools), maybe with the intention of starting a new alternate cryptocurrency and try it out, then I'll be happy to participate in that effort too (initially the most interesting aspect for me would be to analyze the advantages of this protocol over simple-PoA etc.)

[cunicula]

Hello cunicula,

I'll respond to your other posts soon, but I've come up with a new idea that deals with attackers who generate empty blocks, different than ABAB, so I'd like to throw it out there.

This idea is more in the spirit of PoA and it doesn't interfere with mining pools. Suppose the attacker who wishes to generate empty blocks has 99% of the total hashpower. Our objective is to let the honest network generate every (say) 7th block, instead of every 100th block that the 99% malicious hashpower implies. The protocol rule is that at every 5th block we xor the hashes of the last 5 blocks, then derive from the xor'd result an address of a uniform-random stakeholder via follow-the-satoshi technique, and this lucky stakeholder is allowed to create the 7th block (i.e. two blocks after the current 5th block) just by collecting the txns that he wishes to put inside the block and signing it with his privkey, without doing any PoW, The protocol still allows this 7th block to be generated in the regular fashion by anyone else via PoW according to the current difficulty, in case the lucky stakeholder isn't active.
Comments please?

Let me mention that in general I'm trying to come up with the most simple (to imlpement, as well as to analyze) protocol change so that we could hardfork Litecoin. If it'd be successful then maybe Bitcoin could incorporate or refine these ideas next. However, if you'd like to design an even better protocol (that wouldn't have mining pools), maybe with the intention of starting a new alternate cryptocurrency and try it out, then I'll be happy to participate in that effort too (initially the most interesting aspect for me would be to analyze the advantages of this protocol over simple-PoA etc.)

In terms of analytical simplicty
ABAB much simpler than PoA.  [promiscuous signing is very complicated to deal with analytically.]

In terms of implementation (my strong expectation)
ABAB much simpler than PoA.

In terms of alienating mining pools (apparently a concern for you [I could care less])
Miners/pools just care about getting their coins. Just give the A block guys 100% of block reward and 50% fees. Give the B block guys 0% of block reward and 50% of fees.
The miners/pools don't care about fees, so they will go along with it.
You should also alter the fee structure to make txn fee-based bribes less feasible. (i.e. pay a long-run average of txn fees)

[iddo]

In terms of analytical simplicty
ABAB much simpler than PoA.  [promiscuous signing is very complicated to deal with analytically.]

So far I'm quite happy with the analysis of simple-PoA, though I'm still waiting for your answers to the two questions that I asked in post #94 regarding bribe attacks (at the end). Any other comments are also welcome, of course.

In terms of alienating mining pools (apparently a concern for you [I could care less])
Miners/pools just care about getting their coins. Just give the A block guys 100% of block reward and 50% fees. Give the B block guys 0% of block reward and 50% of fees.

I thought that our focus should be on the environment after the block reward ended (post #81).
How can you give the miner+stakeholder who solved some type-B block anything other than all then txn-fees of that block? Who will get the rest of the txn-fees in this case? Or maybe there wouldn't be any txn-fees and instead you recommend using a reward system of one of the other kinds that you mentioned?


BTW, instead of ABAB, we could also have just one single block type that combines both, for example the miner+stakeholder first uses his privkey to sign and solve for a block hash according to coin-confirms difficulty, and then he concatenates the hash he found to the block, and hashes the result to solve according to pure-PoW difficulty. It means having a shorter safe double-spending interval, but adjusting the two difficulties independently might be problematic, and there'd be other security implications that should be considered (and mining pools will be impossible).

Are you sure that ABAB is what you consider to be the best protocol? Nothing is left to refine?
What about security against double-spending attacks? ABAB doesn't offer better double-spending security than pure-PoW, and users have to wait twice longer than pure-PoW in order to get the same level of security that pure-PoW provides.

Any comments regarding my new idea in post #97 ?

[cunicula]

Edit: I'll mention why I think that security against an attacker who generates empty blocks to destroy the network is important. It's possible to say that if the attacker has 99% hashpower then still every 100th block on average will be generated by the honest network, and since the attacker wastes his resources while generating empty blocks the network can survive with 1/100 of the blocks until the attacker gives up. However, the attack could quite plausibly have a snowball effect, meaning that more and more honest miners will quit as confidence in the network is being lost. With the idea above, the stakeholders would control one block at predictable short intervals (every 7th block in the example), so the network could continue to function, which might discourage the attacker from wasting his resources on this kind of attack.

Yes, I completely agree with this. This was my motivation for interest in proof-of-stake in the first place. I had no initial interest in preventing double spends. I was mostly concerned with empty blocks and the snowball effect. Combined these suggest that you only have to apply 51% of hashing power for a brief interval to permanently destroy the network.

Recall that the attacker can refuse to build on other chains. Therefore with 51% he can generate 100% of blocks. Acquiring 99% does not offer any additional advantage.

As far as generating a random minter every seventh block. I need to know what the rule to evaluate the winning chain is. If it is simply longest chain, then 1 out of every 7 blocks is a trivial obstacle for the attacker. His chain could simply never make use of these blocks. This would mean that instead of 50.1%, he needs 54%. That doesn't raise the bar much at all.

Is the rule that the chain with the most random minters wins? This raises the bar substantially. To minimize ambiguity, I feel that the rules should map directly to chain length.
To do this you should not allow the chain to be extended unless the random block is constructed.