Proof of Activity Proposal

[iddo]

Say for example you buy a large amount of USD and the BTC price goes up. You now regret your USD purchase and want execute a double spend.

90% of miners use my unofficial client and thus play no role in branch selection. The remaining 10% participate in the txn reversal service. The attacker pays them to withhold signatures from the good chain and only add them to his branch. The good branch will have 90% of possible signatures. The bad branch will have 100% of possible signatures. Voila double spend. The double spend is made easier by proof-of-stake.

Attacker A sends coins to merchant B, so that B waits and sees the branch where he received the coins with 6-confirms, and then B sends the merchandise (e.g. USD) to A, and then A reverses the branch so that the new winning branch doesn't have the txn that transferred the coins from A to B.
If 90% of stakeholders don't participate in the attack, the we expect that 90% (or say 90/2=45%) of the blocks in the branch that B saw were signed, while at most 10% of the attacker's secret branch were signed.
If the attacker doesn't build his branch in secret, and instead tries to build it by broadcasting his competing branch to the entire network in order to collect signatures from all the greedy stakeholders, then B can scan the network and discover the double-spend attempt, and refuse to send the merchandise to A.

[cunicula]

Say for example you buy a large amount of USD and the BTC price goes up. You now regret your USD purchase and want execute a double spend.

90% of miners use my unofficial client and thus play no role in branch selection. The remaining 10% participate in the txn reversal service. The attacker pays them to withhold signatures from the good chain and only add them to his branch. The good branch will have 90% of possible signatures. The bad branch will have 100% of possible signatures. Voila double spend. The double spend is made easier by proof-of-stake.

Attacker A sends coins to merchant B, so that B waits and sees the branch where he received the coins with 6-confirms, and then B sends the merchandise (e.g. USD) to A, and then A reverses the branch so that the new winning branch doesn't have the txn that transferred the coins from A to B.
If 90% of stakeholders don't participate in the attack, the we expect that 90% (or say 90/2=45%) of the blocks in the branch that B saw were signed, while at most 10% of the attacker's secret branch were signed.
If the attacker doesn't build his branch in secret, and instead tries to build it by broadcasting his competing branch to the entire network in order to collect signatures from all the greedy stakeholders, then B can scan the network and discover the double-spend attempt, and refuse to send the merchandise to A.

?

There is no secret branch. It is a public attack. It can begin after the seller releases the goods. The problem I'm pointing out is that the 90% may participate in the attack passively by signing all branches they see. The remaining 10% are active attackers. They only sign the attacker's branch. Causing the attacker to win.

To reiterate, the issue is that if the majority of people sign all forks in order to maximize their block reward, the resulting system is worse than proof-of-work. The majority may cast multiple contradictory votes out of greed. A small minority could then cast decisive votes for attacking forks in exchange for a bribe. This never occurs in proof-of-work because you can't vote twice without paying double.

[iddo]

There is no secret branch. It is a public attack. It can begin after the seller releases the goods. The problem I'm pointing out is that the 90% may participate in the attack passively by signing all branches they see. The remaining 10% are active attackers. They only sign the attacker's branch. Causing the attacker to win.

If it's a public attack that starts after the seller released the goods, then the branch that the seller sees has a 6-confirms head start, or even 24-confirms with Litecoin (see here). This means that the attacker will need much more than 50% hashpower, assuming for example 2x weight for signed blocks and 10% advantage in proof-of-stake signatures for the attacker's branch.

However, this entire scenario that we discussed in the last few posts doesn't jibe with PoA, because each individual stakeholder address gets the opportunity to sign only one of the competing branches (when it wins the follow-the-satoshi lottery, probability for an address to win in two concurrent branches is negligible). This means that the attacker cannot tell whether a stakeholder who accepts the bribe also participates in the honest network. Therefore, the rational behavior for all the greedy stakeholders is to accept the bribe and sign the attacker's branch when they win the lottery in his branch, and simultaneously also sign the honest branch when they win the lottery there. So the attacker won't have 10% advantage, all the stakeholders will simply snatch his bribe payments and sign both his branch and the honest branch, so the attack will fail and the attacker just loses money.

[cunicula]

There is no secret branch. It is a public attack. It can begin after the seller releases the goods. The problem I'm pointing out is that the 90% may participate in the attack passively by signing all branches they see. The remaining 10% are active attackers. They only sign the attacker's branch. Causing the attacker to win.

If it's a public attack that starts after the seller released the goods, then the branch that the seller sees has a 6-confirms head start, or even 24-confirms with Litecoin (see here). This means that the attacker will need much more than 50% hashpower, assuming for example 2x weight for signed blocks and 10% advantage in proof-of-stake signatures for the attacker's branch.

However, this entire scenario that we discussed in the last few posts doesn't jibe with PoA, because each individual stakeholder address gets the opportunity to sign only one of the competing branches (when it wins the follow-the-satoshi lottery, probability for an address to win in two concurrent branches is negligible). This means that the attacker cannot tell whether a stakeholder who accepts the bribe also participates in the honest network. Therefore, the rational behavior for all the greedy stakeholders is to accept the bribe and sign the attacker's branch when they win the lottery in his branch, and simultaneously also sign the honest branch when they win the lottery there. So the attacker won't have 10% advantage, all the stakeholders will simply snatch his bribe payments and sign both his branch and the honest branch, so the attack will fail and the attacker just loses money.

?

The bribe is paid to people who could have signed the valid chain, but chose not to. The fact that potential signatories are selected at random is irrelevant. These people can either be publicly identifiable (i.e. lottery is public) or they can announce themsevles in a verifiable way to the bribery service (i.e. lottery is private). The bribery service can wait for these people to perform the attack before paying them.

Bribery of a small minority is sufficient to obtain a majority of stake signatures. With pure PoW or joint submission PoS/PoW you can still bribe people, but you would need to bribe a majority.

The whole problem is due to the greedy stakeholders signing everything instead of being selective. Lack of selectivity is due to costless signatures. Fix is simple. Make signing stuff costly.

Sigh, why continue discussion of this proposal when I have already
a) explained why PoA, Meni's system, killerstorm's suggestions, PPCoin, etc. are critically flawed
b) suggested a solution to the problem (which is not at all new and has always been part of my proposal. The ABAB thing is a response to killerstorm's criticisms. I don't think the issue he raises is nearly as important, but it is significant enough to merit a fix.)
                                                

[iddo]

The bribe is paid to people who could have signed the valid chain, but chose not to. The fact that potential signatories are selected at random is irrelevant. These people can either be publicly identifiable (i.e. lottery is public) or they can announce themsevles in a verifiable way to the bribery service (i.e. lottery is private). The bribery service can wait for these people to perform the attack before paying them.

So some stakeholder with say 10,000 BTC will identify himself to the attacker's bribe service by signing with the privkeys that control the 10,000 BTC and promising that he won't sign the honest chain whenever the attacker declares that a double-spending attack begins. The attacker verifies that this stakeholder doesn't sign in the honest chain whenever an attack is in progress. If the attacker tries to double-spend all the time, then this stakeholder shouldn't sign on the honest chain at all. In your scenario there are many stakeholders such as this one, who provided verifiable evidence that proves that they participate in the double-spending bribe service, so the total stake used by the bribes service is e.g. 10%. Furthermore, the honest chain will have a head start of 6-confirms or 24-confirms, because the attacker also needs signatures from all the other stakeholders to get 10% advantage over the honest chain.
What incentive does the attacker have to pay these 10% of stakeholders after the attack succeeds?
Wouldn't these 10% of stakeholders earn more coins by signing the honest chain?
Shouldn't stakeholders be worried of retaliation if there's verifiable evidence that they participate in double-spending-bribes service, e.g. the other 90% of stakeholders could decide that those 10% of stakeholders diminish the value of the cryptocurrency and therefore their stake should be blacklisted ?
Wouldn't the attacker need to sustain more than 50% hashpower for a long period of time until his chain wins? The honest miners won't help the attackers while his chain is small, even if it's public, so if it's 2x weight for a signed block and there's e.g. 12 blocks gap to close, the attacker has 10% advantage in signing and an advantageous signed block closes 2 blocks in the gap instead of 1 block, so overall we'd say that the attacker needs to close a gap of about 10 blocks as if he didn't have any advantage in signing?

Sigh, why continue discussion of this proposal when I have already
a) explained why PoA, Meni's system, killerstorm's suggestions, PPCoin, etc. are critically flawed
b) suggested a solution to the problem (which is not at all new and has always been part of my proposal. The ABAB thing is a response to killerstorm's criticisms. I don't think the issue he raises is nearly as important, but it is significant enough to merit a fix.)

You explanation of why PoA is (critically) flawed isn't convincing yet.
I think that we should also discuss your system, the ABAB idea looks promising.
Maybe we should also discuss a hybrid of your system and PoA, similar to what you suggested in post #43. We can also look at from the perspective of extending PoA, i.e. the signed block should be supplement with PoW hash of certain difficult, to make it costly for stakeholders to sign blocks. It's still unclear to me whether that'd be a good idea. I hope that as a result of these discussions we will converge to one proof-of-stake system in the end. For actually implementing some system in Litecoin, there should be bias towards simplicity, which is point (7) in your list of objectives.

[cunicula]

What incentive does the attacker have to pay these 10% of stakeholders after the attack succeeds?
Wouldn't these 10% of stakeholders earn more coins by signing the honest chain?

The same reason that a silk road vendor sends the product after he receives coins. He needs repeat business. If you hire miners and don't pay them, then you won't be able to hire them again.

Think about the following attack scenario. Suppose that normally all blocks receive signatures. This happens on every fork because miners are rational/

He wants to double-spend a txn located in block 1. His fork will always be 100% fully signed. He won't be able to create as much work as the main chain, but he's going to compensate by weaking the stake signatures in the main chain so that he can double-spend. His fork will have 100% singed blocks. The main chain will have a sequence of unsigned blocks.

The attacker can ask his 10% of signers to carry out the following orders.

1) Please do not sign at block 1.
2) Please do not sign at block 2. However, if block 2 is signed, then give up and sign at block 1.
3) Please do not sign at block 3. However, if block 1 or block 2 are signed, then give up and sign at blocks 1,2, and/or 3.

If 10% of miners are participating in the attack service, then you get three participants in a row once ever 1000 blocks. If you don't get three participants in a row, then the attack is called off ex-post. There is no attack, but the malicious miners don't pay any penalty either. They still get their full reward for stake signatures. If the attacker links three blocks in a row with no stake signature, then the attack is in motion. We assume that the attacker is completely sure that with 3 unsigned blocks in a row on the main chain, then he can execute a successful attack. If the attacker is not certain, then just increase his advantage to 4 unsigned blocks in a row (once every 10k blocks). Then, the attackers employees lose nothing from conducting the attack relative to just mining the main chain.

In this scenario, the malicious stakeholders lose absolutely nothing as a consequence of the attack. If the attacker pays them 0.01 BTC each as a bribe, then they have a net gain of 0.01 BTC each.

[cunicula]

Maybe we should also discuss a hybrid of your system and PoA, similar to what you suggested in post #43.

The problem with the hybrid scenario in post #43 is that it does not satisfy constant returns to scale. Under the hybrid, 2% stake and 2% work yields more than twice as many blocks as 1% stake and 1% work.

I haven't yet figured out how to achieve the following three objectives simultaneously:
a) use a lottery to determine the the stake signatory
b) require work to accompany all stake signatures
c) maintain constant returns to scale (i.e. so that simultaneously doubling stake and hashing power just doubles output [at least to a close approximation])

I'd be happy with the hybrid if it satisfied constant returns to scale.

Of (a), (b), and (c), I would say that (b) and (c) are important whereas (a) is not necessary.

[iddo]

Hello cunicula,

Regarding ABAB:
I'm not so sure whether ABAB gives better protection from attacker with 50% hashpower who tries to double-spend by doing 6-block reorg, compared to the Bitcoin pure-PoW protocol.
Let's assume type-A is pure-PoW and type-B is heavily weighted towards proof-of-stake (for example as you said 0.9 stake weighting and a 0.1 work weighting).
Without going into the exact calculations, let's just say that if the attacker has 1% of the active network stake which he divides equally among 3 addresses, and he waits for about one week, then with his hashpower he can generate 3 consecutive type-B blocks ahead of the distributed network. Since he has 50% of the entire network hashpower, he can also generate the 3 interleaved type-A blocks, and thereby create 6-block reorg and double-spend.
So the only difference between the pure-PoW protocol and ABAB with respect to attacker with 50% hashpower is that the attacker has to sit idle for a while (one week or some different time frame, depending on the other parameters) before launching his double-spending attack? Am I missing something here?

Interestingly, I think that the type-B blocks (or simply your original protocol) offer good protection from attacker who wishes denies txns and destroy the network, because he couldn't generate all the type-B blocks once he runs out of coin-confirms.

I mentioned in post #31 another advantage that the double-spending attacker has: if the honest participants divide their stake among e.g. 10 addresses on average, and the attacker divides his stake among 3 addresses, then it's advantageous for the attacker in order to achieve 3 consecutive type-B blocks, because his coin-confirms will be concentrated in 3 addresses instead of 10 addresses and therefore carry more weight in the difficulty calculation, compared to the average miner. An honest miner who divides his stake among 10 address (so not to put all his eggs in one basket) would do hash attempts with only one of his 10 addresses while trying to solve the current block, it's pointless for him to do 10 different attempt concurrently because that's the same as having 10x less hashpower. So for double-spend attacks the optimal number of addresses should be the same as the length of the reorg, which doesn't necessarily coincide with the number of addresses that an honest miner would choose to have.

The issue of waiting e.g. one week before launching the double-spending attack occurs because of the coin-confirms property of the difficulty calculation. The PoA scheme doesn't use coin-confirms, so this wait-one-week-to-double-spend issue doesn't occur there. On the other hand, the PoA scheme as it is doesn't handle the attacker-who-denies-txns issue at all. I'm still hoping that we could refine all the ideas and converge to some superior scheme.

[cunicula]

Hello cunicula,

Regarding ABAB:
I'm not so sure whether ABAB gives better protection from attacker with 50% hashpower who tries to double-spend by doing 6-block reorg, compared to the Bitcoin pure-PoW protocol.
Let's assume type-A is pure-PoW and type-B is heavily weighted towards proof-of-stake (for example as you said 0.9 stake weighting and a 0.1 work weighting).
Without going into the exact calculations, let's just say that if the attacker has 1% of the active network stake which he divides equally among 3 addresses, and he waits for about one week, then with his hashpower he can generate 3 consecutive type-B blocks ahead of the distributed network. Since he has 50% of the entire network hashpower, he can also generate the 3 interleaved type-A blocks, and thereby create 6-block reorg and double-spend.
So the only difference between the pure-PoW protocol and ABAB with respect to attacker with 50% hashpower is that the attacker has to sit idle for a while (one week or some different time frame, depending on the other parameters) before launching his double-spending attack? Am I missing something here?

Interestingly, I think that the type-B blocks (or simply your original protocol) offer good protection from attacker who wishes denies txns and destroy the network, because he couldn't generate all the type-B blocks once he runs out of coin-confirms.

No you aren't missing anything. The idea is just to preserve the 50% work requirement for an attack, but also protect the network from denial of txns. I guess you could say the goal is to make something strictly better than proof-of-work. In the sense that it offers complete proof-of-work protection + additional protection.

I'll think about an ABAB pattern, where the stake block is Colbee's proof-of-activity lottery. I think the proof-of-stake reward should be as in PPCoin. PPCoin is also a lottery BTW. It should be like interest, so that you get more reward if you have to wait longer to find a block. The proof-of-stake lottery guys would always be indifferent to rewriting history, which I see as a big problem. However, you could fix this by giving a larger reward to people who wait longer to find blocks (i.e. interest accumulates as a superexponential function instead of an exponential one)

superexponential means where t and T are two time points both greater than 0.
f(t)f(T)<F(t+T) [you get more finding one block at time T+t than you would finding one block at time t and one block at time T]
where with normal exponential growth rate of interest accumulation
f(t)f(T)=f(t+T) [this means you get just as much finding one block at time t and one block at time T as you would finding one block at time t+T]

This would mean that you get a larger reward if you find a later block. Finding a block is a lottery. You could write an alternate history at an earlier date where you also win the lottery.
However, since you earn less by winning the earlier lottery you will never want to write this alternate history. You don't want to wait forever either. Because it is a lottery and you might die before you ever win. I think you could just give all the txn fees to the work miners and pay out stake miners using inflation (say 1% year as in PPCoin; though it would be variable if interest is superexponential [more inflation when there is more hoarding])

It is a bit confusing however so I need to think about it more.

[sorry this is disjointed; ask a question and I'll clarify when I have more time]

[cunicula]

On the other hand, the PoA scheme as it is doesn't handle the attacker-who-denies-txns issue at all.

Could you elaborate on this issue? I don't understand what you mean.

[iddo]

On the other hand, the PoA scheme as it is doesn't handle the attacker-who-denies-txns issue at all.

Could you elaborate on this issue? I don't understand what you mean.

I meant that with PoA (or Meni's scheme etc.) where the miners first generate the blocks and only later the stakeholders add their signatures (that correspond to blocks that were already generated), an attacker with huge hashpower and without any stake could paralyze the network by excluding all txns in the blocks that he generates. Because stakeholders would only see the attacker's winning branch, no other branches will ever be generated, so they could only sign the attacker's branch. With PoA the attacker might wish to include the signature txns in his branch (depending on the rule for competing branches with same signed/unsigned prefix, post #47), but it doesn't matter because if signature txns are the only txns that are included then the network will be destroyed anyway.

Your idea about larger rewards for later blocks sounds interesting, but it's still vague. Does it involve the blocks timestamps, or just branch length is enough?

[cunicula]

Okay here is a proposal which mixes my ideas with colbees ideas. You can think of this as proof-of-public broadcast. Miners search for the seed to a number sequence that indexes the coins of several connected network peers. If they are not connected to the network it is impossible to successfully mine. The stake component in the initial block is just there to prevent denial of service by mining empty blocks.

The proposal aims to achieve 3 things [in my perceived order of importance]:
1) To make sustained denial of service by mining empty blocks exceptionally difficult (i.e. at least 20% stake and 90% work is required for example)
2) Make hidden extension of a chain to double spend almost impossible, i.e. for it to require something like 99.99% of work rather than just 51%, even for people who hold 10% stake.
3) To provide an incentive for stake providers to vote only once rather than multiple times.

The rules work as follows.

1) Mixed Stake/Work miner finds a tentative block. The work target is difficulty/coin-age.
2) The work submitted in this tentative block produces a sequence of lottery draws, randomly drawing an ordered sequence of 10 satoshis that are lottery winners.
3) The tentative block is transmitted in the network soliciting signatures from the lottery winners. The lottery winners must sign the block in sequence.
4) If a tentative block acquires a sequence of five consecutive signatures, it becomes a full block and can be extended. If not, then go to (1).
5) If a tentative block acquires five signatures, then a new tentative block can be mined. Mining this block requires hashing together the past proof of work block and the 5th, 6th, 7th, 8th, 9th, or 10th stake signature. Accordingly, you cannot begin looking for this block until the fifth signature is found. [Edited: to reflect iddo's comment]
6) Before the next block is found, signatures 6-10 can be added. These signatures increase block stability and miners will want to incorporate them if they become aware of them before finding a new block.
7) The chain with the highest total number of lottery-selected signatures is the valid chain. Highest difficulty can be used as a tie breaker.
Only the block itself includes txns. The blocks are timed for once every 10 minutes.

Notes:
a) It is almost impossible to get five randomly selected signatures in secret and hope to win. Thus objective 2 is achieved.

b) Objective 1 is achieved by the use of stake in step 1. You will run out of coin-age and no longer be able to deny service.

c) We still have the remain problem of stake-holders participating in multiple lotteries. Step (6) is combined with a reward scheme to address this.

Rewards:
1) The mixed stake/work miner is rewarded with txn fees. Double-spenders need a work advantage of many orders of magnitude. Difficulty can be extremely low without posing a security risk. Therefore energy efficiency can be very high and txn fees can stay very low forever (ignoring bandwidth and storage problems).

2) The signatories are rewarded with inflation. Their rewards are delayed until 500 blocks in the future. These operate like rewards in PPC coin. The signatories are allowed to submit coin-age in exchange for interest.  Submission is done at least 500+x blocks after the signature occurs. Submitted coins must have sat still for more than 500+x blocks to be eligible for interest. Perhaps, Age on coins is capped at one year (not sure if this is necessary).

3) The annual interest rate varies from 0 and 1.5%. Thus the annual money supply growth rate is between 0 and 1.5%. The interest rate increases with the number of signatures in the block that the lottery winner signed and also in the subsequent 9 blocks. Say there are a total of s sigs on these 10 blocks. S can vary between 50 and 100. The interest rate will be r=0.015*(s/50-1). You cannot know your interest rate in advance because it depends on future outcomes. You get high interest by signing chains which you expect to be widely signed. You get low or no interest by signing chains that have suspiciously few signatures (e.g. the bare minimum). Such low signature chains are nearly certain to be attack chains.

Note:
This reward system encourages signatories to bet on a single chain which they expect has the widest consensus support.  If you provide a marginal vote that helps an attack chain, then you get punished with forgone interest. This accomplishes point (3).

Final Note:
There is a lot of message relaying going on here. If a fraction p of stake is connected to the network, then the number of blocks you need to relay before finding a valid block is 1/p^5. If p is 0.5, then this is about 32 blocks. It is probably easier to have nodes keep track of which stakes are connected to the network, rather than have them send out every block attempt they see. The system maintains a list of nodes that were recently connected to the network (signatures in past blocks). It would be simple to take the list of 5,000-10,000 signatories from the last 1000 blocks and only relay blocks that matched say 3 out of 5 these signatories. Thus network traffic could be limited to blocks that were highly likely to obtain signatures. More generally, success probability can be predicted based on blockchain history using linear regression and only block attempts above a certain minimum success probability are worth transmitting.

The cap on age for interest purposes provides an incentive to participate and thus keep p high. If you don't participate at least once a year, you forfeit rewards. Even if you participated receently,
you still have some incentive to participate because this extends your interest exipration. It is like airline miles that expire. The participation incentive strengthens as the network grows in size. It is almost certainly nonlinear in coin-holdings. Very large holdings lead to positive, but weak incentives to participate [i.e. the age cap will rarely bind, so you can participate infrequently and be fine]. Moderate holdings lead to positive, strong incentives to participate [the age cap is likely to bind without frequent participation]. Very low holdings should not participate at all [the age cap is likely to bind even with frequent participation]. People with very low holdings should deposit their holdings in an online wallet, which would participate for them and offer them interest on savings. Even without the cap, there are weak incentives for participation. I think the cap is a good idea, however.

[iddo]

I think that there's a mixup between (a) and (b), objective 2 is achieved by (a) and objective 1 is achieved by (b) ?

I think that the core of your new idea is very intriguing. Instead of PoA where miners generate PoW blocks and stakeholders (derived deterministically from block hash with follow-the-satoshi) may or may not sign those blocks later (so signature for an earlier block appears in a later block), I think that a simplified version of your new idea can be described as follows: the miner who solved a block according to the current difficulty doesn't win yet, he has to broadcast the block that he solved to the network, and then the deterministically chosen stakeholder according to the hash of this solved block has to sign it, then announce to the network that the block is now valid, and now the blockchain can be extended from this block, by incorporating the hash of that stakeholder's signature in the next block.
This core idea might be cleaner than PoA, because now all the blocks are always signed, so we don't need to have questionable rules to decide the winning branch.

Regarding your particular suggestion of deriving 10 stakeholders deterministically via follow-the-satoshi instead of just 1 stakeholder, with the threshold of having the 5 first-derived stakeholders provide signatures before the block becomes valid (BTW it isn't so clear where these signatures should reside, they aren't inside the current block and won't be in subsequent blocks, so I guess they should be wrapped together with the current block as an extended data structure), 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?

I wonder if adjusting for 10 minutes block time is possible with this scheme, because of the dependency on the currently active stakeholders. There might also be new kinds of attacks by stakeholders, for examples stakeholders who collude by withholding the 5th signature, then releasing it at the same time in order to split the chain and create chaos?

I don't understand how trading coin-age for interest is supposed to work, could you elaborate?

From an economic perspective, I hope that objectives (1)+(2)+(3) can be achieved without a protocol that requires infinite monetary inflation. Maybe we could attempt to design two different protocols, one with infinite inflation, and one without, so that later the better protocol could be decided by also taking economic considerations into account. What do you think?

Regarding the complexity issues, indeed those might be a huge problem. Even just attaching 10 ECDSA signatures to each block is quite huge (extra 640 bytes per block). Having a good solution for delegating signing-keys might also be highly significant, and possibly add even more complexities. One major advantage of PoA is simplicity. We should try to simplify and minimize complexities wherever possible...

[cunicula]

I think that there's a mixup between (a) and (b), objective 2 is achieved by (a) and objective 1 is achieved by (b) ?

Yes. Fixed that. Good eye.

I think that the core of your new idea is very intriguing. Instead of PoA where miners generate PoW blocks and stakeholders (derived deterministically from block hash with follow-the-satoshi) may or may not sign those blocks later (so signature for an earlier block appears in a later block), I think that a simplified version of your new idea can be described as follows: the miner who solved a block according to the current difficulty doesn't win yet, he has to broadcast the block that he solved to the network, and then the deterministically chosen stakeholder according to the hash of this solved block has to sign it, then announce to the network that the block is now valid, and now the blockchain can be extended from this block, by incorporating the hash of that stakeholder's signature in the next block.
This core idea might be cleaner than PoA, because now all the blocks are always signed, so we don't need to have questionable rules to decide the winning branch.

Yes. It can be simplified. In fact it could look just like PoA except that you must find one signer before beginning the next block. The simple system would probably work pretty well. However, the complexity incorporates added security features. There is a trade-off. If you want simple, I prefer the ABAB system discussed earlier. I could understand why someone would prefer the ABAB system to this. The ABAB system seems inferior, but it is very simple to implement and understand.

Regarding your particular suggestion of deriving 10 stakeholders deterministically via follow-the-satoshi instead of just 1 stakeholder, with the threshold of having the 5 first-derived stakeholders provide signatures before the block becomes valid

The five stakeholder threshold just makes overwhelming work majorities almost useless for competition with the main chain. It might be overkill (i.e. large signature requirements pose communication problems). I'm not sure. Clearly 100 sigs is not feasible. 1 may be too few (double-spends will be too easy). 3 is probably enough.

(BTW it isn't so clear where these signatures should reside, they aren't inside the current block and won't be in subsequent blocks, so I guess they should be wrapped together with the current block as an extended data structure),

I think you have pointed out a significant problem here. The solution is simple though. Just allow the next block to be built off the signature in any block from 5-10. Thus all signatures go in to blocks and you will have to add them before the next block is found. Block miners will extend the chain using the highest signature number. High sig numbers decrease the probability that the block will be orphaned. You could add dangling signatures to old blocks, but signers wouldn't want to do this because signing minority chains exposes them to risk of forgone interest.

I don't understand how trading coin-age for interest is supposed to work, could you elaborate?

As far as trading coin-age for interest. It should be really simple. The public key you sign with has a balance and the coins associated with this key have not been spent or won the lottery for a known time period (call this age). Age is measured in years (units of 52560 blocks). Call age a, the balance b, and the interest rate r, 0<r<0.015. 500 blocks after you sign, the miner includes a generation txn which sends b*(exp(a*r)-1) to this public key.  

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. If you expect to win only extremely rarely, you will probably keep your coins in an online wallet. The online wallet can manage the mining for you. If you hold a large balance, then you will win frequently and can manage the coins yourself. Most of the wealth will be in large balances (wealth distributions are always highly unequal, e.g. in the US it is something like the top 1% has 40% of the wealth. The top 1% can handle their own mining. Everyone else could delegate.)

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. You expect well-signed chains to remain well-signed. If you sign a well-signed chain, your expected interest rate is higher. If you sign a poorly-signed chain, your expected interest rate is lower. Therefore you are forgoing a benefit if you sign a poorly-signed chain (attack chain).  It only makes sense to do this if you need to move your coins very soon and prefer no interest to a penalized amount of interest. In this case you sign everything you see. I assume that a substantial number of stake holders (it does not even have to be the majority) will prefer to wait in order to earn a higher rate of interest. These only sign well-signed chains. They will rationally reject a lottery win in an attack chain. It is fine if 90% of people sign everything and 10% sign selectively. I think it will be the other way around though.

Why are attack chains weakly signed? Attack chains are mined privately using an overwhelming amount of work. An attacker will only want to generate 5 signature long sequence because (for an attacker) this is orders of magnitude easier than generating 6 7 8 9 or 10 signature long sequences. If you try to help him out by signing his chain, then you will get penalized.

The idea is that people begin in default behavior, signing one chain only. If you deviate from default behavior, but some strictly positive fraction of people remain in default mode, then you will get penalized for the deviation. Thus default behavior is a nash equilibrium. This differs from PoA where default behavior is not a nash equilibrium.

I wonder if adjusting for 10 minutes block time is possible with this scheme, because of the dependency on the currently active stakeholders. There might also be new kinds of attacks by stakeholders, for examples stakeholders who collude by withholding the 5th signature, then releasing it at the same time in order to split the chain and create chaos?

Yes, you can withhold the fifth signature, but then some other block will be found and built upon. You will need to add the fifth signature and then secretly find a new block. Secretly finding a new block is nearly impossible.

From an economic perspective, I hope that objectives (1)+(2)+(3) can be achieved without a protocol that requires infinite monetary inflation. Maybe we could attempt to design two different protocols, one with infinite inflation, and one without, so that later the better protocol could be decided by also taking economic considerations into account. What do you think?

This is not really inflation at all. A small amount of new money is printed, but it is distributed proportionally evenly among people who already have money. Say productivity grows by 1% a year.
In this case, prices will remain close to constant in the long-run, but your $1.00 will slowly turn into $1.01 each year. [productivity growth shows up as an increase in your balance instead of falling prices]
With bitcoin, prices fall by 1% each year, and your $1.00 balance remains as $1.00. [productivity growth shows up as falling prices]
The two situations are almost equivalent.

The difference is that there is an implicit tax on txns. You are penalized via loss of interest if you move your coins. The penalty is very small. Think of buying a television for US$400.
You have a choice. Do I buy it now, or do I wait 6 months to earn interest and then buy it? At most, 6 months of waiting could decrease the price by US$6. In practice, however effects will be much smaller than this. You could hold your money in an online wallet. They would store 90% of their holdings to earn interest and handle liquidity needs with the remaining 10% (just like a normal bank, except with a 100% reserve).
The loss of interest would then be reduced to $0.60. I don't think you will delay your television purchase for 6 months to save 0.15% off the purchase price. The implict txn tax will be really really tiny.

Regarding the complexity issues, indeed those might be a huge problem. Even just attaching 10 ECDSA signatures to each block is quite huge (extra 640 bytes per block).

640 bytes per block is very little in additional storage. The main issue is how much extra info has to be transmitted. The bandwidth requirement is more worrying because you need to transmit more than you store.

It sounds really difficult and taxing on the network, but I think that it could actually be much easier than it sounds. The miners don't actually need to transmit a large number of tentative blocks. They just need to search for blocks that match keys that have recently signed the blockchain. i.e. they search for historically active keys. They discard potentially valid blocks with keys that are rarely seen in signatures. They then transmit blocks that historically active keys can sign. These tentative blocks are likely to become valid. The final signatures in the sequence allow the blockchain to constantly update the record of historical activity. [These final signatures are increasingly random rather than miner selected, particularly sigs 6-10.] Thus, by referring to the blockchain, the miners always know approximately what type of sequence they are looking for.

This search might sound hard, but really it isn't. You are most likely searching for the public keys of Mt. Gox, Bitinstant, Bill Gates, blockchain.info, etc. A small number of people will hold a huge amount of stake. Searching for a small number of keys is not that difficult. Searching for the key to an average person's wallet is probably not worth the time.

Have a good solution for delegating signing-keys might also be highly significant, and possibly add even more complexities. One major advantage of PoA is simplicity. We should try to simplify and minimize complexities wherever possible...

Yes delegation is essential and limited functionality singing-keys are also essential. You want blockchain.info to be able to participate using its users' money. We've discussed before that bitcoin could really benefit from limited-spend keys. The inability to make low-risk spend keys is a security risk. Atm cards have withdrawal limits for a reason. You shouldn't have to expose your entire bank account to the internet in order to send $10. It is silly.

[iddo]

I haven't read carefully the last post yet (I will a bit later), but I would like to ask again regarding PoA:

Let's consider this simple PoA protocol:
*) stakeholder who won the follow-the-satoshi lottery is allowed to provide his signature txn only in the next 6 blocks to win his reward (the rule is that his signature txn is invalid from the 7th block onwards, so it wouldn't be included in the 7th block by miners who follow the protocol).
**) the recommended safe length to protect yourself from doubles-spending attacks is between 6 signed blocks and 12 unsigned blocks.
***) the weight of each signed block is for example 2x or 5x the weight of an unsigned block, and this weight goes into effect immediately.
****) there aren't any other special rules to determine the winning branch, simply the branch with highest difficulty (adjusted by PoA weights) wins.

This protocol doesn't attempt (yet) to help with an attacker who generates empty blocks to destroy the network.

I claim that w.r.t. double-spending attacks, this protocol is more secure than pure-PoW, assuming that the majority of stakeholders isn't malicious.

Suppose merchant A receives the coins payment of the buyer B at block n, and listens on the network for double-spending attempts until reaching block n+6 (or up to n+12 if all blocked were unsigned), and only then sends the merchandise to B. The double-spending attacker cannot prepare a secret fork of 6 blocks and then announce it to stakeholders to get their signatures, because their signatures will be invalid after 6 blocks. If the attacker makes his fork public from the start, then the merchant's client will detect the double-spending attempt. So waiting for 6 signed blocks is enough, and e.g. if 2nd block wasn't signed by the honest network and the attacker released his secret fork after 6 blocks then this 2nd block can still be signed by the lucky stakeholder in the 7th block and thereby give more weight to the attacker's branch, so waiting up to 12 blocks (depending on how many were signed) is safe.

Let's consider the attack vector raised by coblee where the attacker waits until he's the lucky winner of a block that he mined and lets the honest network extend this block without providing his signature txn, while preparing a secret fork in which he includes his signature txn. Note that the txn that he plans to double-spend doesn't need to be in the initial block that he mined, he can put this txn in the 2nd block of the honest network that extends his initial block. So he has an advantage of one signed block in his secret fork (i.e. the block that he mined initially), and the honest network won't be able to include the signature of that block if he releases his fork after at least 6 blocks. Still, if the reward for the stakeholders is big enough so that at least half of the blocks get signed on average, then the attacker's branch will have only one signed block in the first 6 blocks, and the honest branch will have about 3 signed blocks. So I don't think that this attack vector is a problem, unless less than 1/6 of all blocks get signed on average.

The double-spending-bribes service cannot operate with this protocol, this service had to keep the fork secret for 6 blocks before soliciting signatures from stakeholders, so that the merchant won't detect it, but now those signatures would be invalid.

The reward for stakeholders should probably be big (for example 10% of the block reward), because they must provide their signature in the next 6 blocks. This is also related to signing-key delegation, i.e. whether stakeholders can use encrypted wallets.

So when comparing with pure-PoW, the only disadvantage is that the merchant might have to wait for more than 6 blocks (but less than 12), depending on how many blocks were signed? The advantage is of course that PoW-only attacker will fail against the honest network.

Assuming the the incentives for stakeholders would work (maybe by adjusting their reward with the difficulty retarget window), do you think that this protocol is good, and we could try to extend it to handle attackers who generate empty blocks? Or am I missing possible attacks on this protocol?

[cunicula]

I haven't read carefully the last post yet (I will a bit later), but I would like to ask again regarding PoA:

Let's consider this simple PoA protocol:
*) stakeholder who won the follow-the-satoshi lottery is allowed to provide his signature txn only in the next 6 blocks to win his reward (the rule is that his signature txn is invalid from the 7th block onwards, so it wouldn't be included in the 7th block by miners who follow the protocol).
**) the recommended safe length to protect yourself from doubles-spending attacks is between 6 signed blocks and 12 unsigned blocks.
***) the weight of each signed block is for example 2x or 5x the weight of an unsigned block, and this weight goes into effect immediately.
****) there aren't any other special rules to determine the winning branch, simply the branch with highest difficulty (adjusted by PoA weights) wins.

Issues:
1) A modest Proof-of-work advantage (2-fold or 5-fold with 100% participation; less with partial participation) still allows you to double-spend or deny service. This is not adequate for a world with just pure fees and no block subsidy. If someone could perform a 51% attack, I can't see why they couldn't also perform a 76% attack. Get into the 99%+ range and I'll be satisfied.

Possible Resolutions:
a) The best way of preventing denial of service is to make the source block depend on the miner's personal proof of stake. You can use multiple block types if you want to preserve pure proof-of-work blocks.
b) Require all blocks to be signed before they can be added to. (i.e. you need a signature for a valid block and you have to get that before the process can move on) Just one signature per block would help a lot. Miners could no longer mine in secret without stake. Even with 10% of stake and just 1 signature, attackers would need 10 times as much hashing power in order to compete with the main chain.

2) There is no clear plan for rewarding signatories in the long-term. If you use simple txn fees to reward stakeholders, then txn fees become a bribery vector. Simply including a txn with large fees on an attack chain induces rational stakeholders to join the attack.

Possible Resolutions:
a) Use permanent inflation to reward stakeholders. [See for example PPCoin]
b) Use a long-run average of historical txn fees to reward stakeholders. Whenever a block is mined, give 10% of txn fees directly to the miner. Send the other 90% of txn fees to a fund that rewards signatories. Distribute 0.001% of this fund to stakeholders in each block. With this, system current miners could not influence signature payouts to any meaningful degree (i.e. including 100,000 times the regular fee in a block increases stakeholder rewards by just 1%). [This is conceptually similar to PPCoin; a txn tax rewards stakeholders; the miner has no influence over the tax; here, the txn tax does not operate through inflation] An added bonus is that this method incentivizes the transmission of txn data.

3) For atomistic stakeholders, the unique nash equilibirum is to sign every single fork you see.

Possible Resolutions:
a) Include a mechanism to penalize signatures on blocks with low consensus. There are at least two things you could do:
       i) Make signature rewards increase with the degree of stakeholder consensus. You can adapt this to a txn fee system with no inflation. Alternatively you can use inflation. Ask if you are curious.
       ii) use inflation to reward stake holders and make their holdings grow at a hyperexponential rate. You can ask about this if you are curious. I think both (i) and (ii) are much better ideas though.
b) Do not use a lottery at all and go with a protocol like ABAB coin as described above.

[iddo]

As far as trading coin-age for interest. It should be really simple. The public key you sign with has a balance and the coins associated with this key have not been spent or won the lottery for a known time period (call this age). Age is measured in years (units of 52560 blocks). Call age a, the balance b, and the interest rate r, 0<r<0.015. 500 blocks after you sign, the miner includes a generation txn which sends b*(exp(a*r)-1) to this public key.  

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?

Could you please explain what is the reasoning behind trading coin-age for interest? I mean, what are the particular benefits of using this reward scheme over other reward schemes.

The idea is that people begin in default behavior, signing one chain only. If you deviate from default behavior, but some strictly positive fraction of people remain in default mode, then you will get penalized for the deviation. Thus default behavior is a nash equilibrium. This differs from PoA where default behavior is not a nash equilibrium.

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 wonder if adjusting for 10 minutes block time is possible with this scheme, because of the dependency on the currently active stakeholders. There might also be new kinds of attacks by stakeholders, for examples stakeholders who collude by withholding the 5th signature, then releasing it at the same time in order to split the chain and create chaos?

Yes, you can withhold the fifth signature, but then some other block will be found and built upon. You will need to add the fifth signature and then secretly find a new block. Secretly finding a new block is nearly impossible.

I'm still not so sure. Maybe some small fraction of the stakeholders could increase the number of splits, say by synchronizing to provide their 5th signature only at round minutes (if they see that they're the lottery winner of 5th signature at 11:00:05 PM then they'll broadcast their signature at 11:01:00 PM). BTW my concerns here would be the same if it was the simplified core idea with a single signature instead of 5-10 signatures.

I think that the core idea of requiring PoW+lottery_PoA_signature before the block becomes valid raises interesting issues.
As a miner, if you solved the block and you're waiting for the stakeholder to broadcast his signature (and so far he doesn't), do you sit idle, or do you attempt to re-solve the block while waiting? Since if you manage to re-solve then maybe the 2nd stakeholder will provide his signature, while the 1st stakeholder wouldn't.

BTW there are also interesting issues with protocols like your ABAB where the miner must use his privkey to generate the block. Specifically, you couldn't use mining pools, so maybe a variation of p2pool has to be an integral part of the protocol. This is actually a great feature rather than a drawback, because centralized mining pools are a security risk (can be DoS attacked, unlike p2pool, etc.) I don't remember whether I discussed it with you before, but I did raise this issue at #bitcoin-dev about one year ago (link).

From an economic perspective, I hope that objectives (1)+(2)+(3) can be achieved without a protocol that requires infinite monetary inflation. Maybe we could attempt to design two different protocols, one with infinite inflation, and one without, so that later the better protocol could be decided by also taking economic considerations into account. What do you think?

This is not really inflation at all. A small amount of new money is printed, but it is distributed proportionally evenly among people who already have money. Say productivity grows by 1% a year.
In this case, prices will remain close to constant in the long-run, but your $1.00 will slowly turn into $1.01 each year. [productivity growth shows up as an increase in your balance instead of falling prices]
With bitcoin, prices fall by 1% each year, and your $1.00 balance remains as $1.00. [productivity growth shows up as falling prices]
The two situations are almost equivalent.

The difference is that there is an implicit tax on txns. You are penalized via loss of interest if you move your coins. The penalty is very small. Think of buying a television for US$400.
You have a choice. Do I buy it now, or do I wait 6 months to earn interest and then buy it? At most, 6 months of waiting could decrease the price by US$6. In practice, however effects will be much smaller than this. You could hold your money in an online wallet. They would store 90% of their holdings to earn interest and handle liquidity needs with the remaining 10% (just like a normal bank, except with a 100% reserve).
The loss of interest would then be reduced to $0.60. I don't think you will delay your television purchase for 6 months to save 0.15% off the purchase price. The implict txn tax will be really really tiny.

I don't dispute (nor approve) any of that, I always use the phrase "monetary inflation" to be clear. Not sure how the 90%,10% online wallet example works, you don't really need to allocate 10% that sits idle because you can always transfer coins and forfeit some interest reward? But I guess that you would still want to tell your customers that their withdrawals cannot bypass the 10% limit unless they meet some requirements?

It sounds really difficult and taxing on the network, but I think that it could actually be much easier than it sounds. The miners don't actually need to transmit a large number of tentative blocks. They just need to search for blocks that match keys that have recently signed the blockchain. i.e. they search for historically active keys. They discard potentially valid blocks with keys that are rarely seen in signatures. They then transmit blocks that historically active keys can sign. These tentative blocks are likely to become valid. The final signatures in the sequence allow the blockchain to constantly update the record of historical activity. [These final signatures are increasingly random rather than miner selected, particularly sigs 6-10.] Thus, by referring to the blockchain, the miners always know approximately what type of sequence they are looking for.

This search might sound hard, but really it isn't. You are most likely searching for the public keys of Mt. Gox, Bitinstant, Bill Gates, blockchain.info, etc. A small number of people will hold a huge amount of stake. Searching for a small number of keys is not that difficult. Searching for the key to an average person's wallet is probably not worth the time.

At first glance this doesn't sound good at all to me. Why would we want to encourage wealth concentration by having the miners behave in the way that you describe? Don't you agree that having only a few stakeholders is a major security risk? I suppose that we agree that the network is more secure when the PoW hashpower is more distributed, so why wouldn't you agree that the same is true for distributed stake?

[iddo]

1) A modest Proof-of-work advantage (2-fold or 5-fold with 100% participation; less with partial participation) still allows you to double-spend or deny service. This is not adequate for a world with just pure fees and no block subsidy. If someone could perform a 51% attack, I can't see why they couldn't also perform a 76% attack. Get into the 99%+ range and I'll be satisfied.

I'm gonna use 3-fold in my example (see next), which means that pure-PoW attacker would need 75% of the total hashpower if all the blocks get signed (edit: 66% of the total hashpower assuming that on average half of the blocks get signed). That ain't 99%, but if we use a higher multiplier than 3x (say 100x) then the attacker would always need just one more block than half of the double-spending safety length (see next).

2) There is no clear plan for rewarding signatories in the long-term. If you use simple txn fees to reward stakeholders, then txn fees become a bribery vector. Simply including a txn with large fees on an attack chain induces rational stakeholders to join the attack.

I don't see how a large txn fees bribe is a problem with simple-PoA: if the attacker's branch is public then stakeholders would just grab the extra coins that he offers them and make his branch the winning branch (double-spending wouldn't occur, so the attacker loses his coins), and if the attacker's branch is secret then neither the stakeholders nor the attacker can benefit from the large txn fees bribe that he attempted to offer them, because when he reveals his secret branch after 6 blocks the stakeholders can no longer participate because their signatures would already be invalid.

b) Use a long-run average of historical txn fees to reward stakeholders. Whenever a block is mined, give 10% of txn fees directly to the miner. Send the other 90% of txn fees to a fund that rewards signatories. Distribute 0.001% of this fund to stakeholders in each block. With this, system current miners could not influence signature payouts to any meaningful degree (i.e. including 100,000 times the regular fee in a block increases stakeholder rewards by just 1%). [This is conceptually similar to PPCoin; a txn tax rewards stakeholders; the miner has no influence over the tax; here, the txn tax does not operate through inflation] An added bonus is that this method incentivizes the transmission of txn data.

Interesting idea, I'll keep that in mind.


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 can 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 signed 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 ?

[cunicula]

I don't see how a large txn fees bribe is a problem with simple-PoA: if the attacker's branch is public then stakeholders would just grab the extra coins that he offers them and make his branch the winning branch (double-spending wouldn't occur, so the attacker loses his coins), and if the attacker's branch is secret then neither the stakeholders nor the attacker can benefit from the large txn fees bribe that he attempted to offer them, because when he reveals his secret branch after 6 blocks the stakeholders can no longer participate because their signatures would already be invalid.

Since txn fee bribes are feasible in bitcoin as well I posted a new topic on it here:  https://bitcointalk.org/index.php?topic=122291.msg1315784#msg1315784

The bribe would work the same way with PoA. i.e. you make a one block long secret fork (secretly loading your bribes in this fork), send a real txn and put the bribe elsewhere on the main chain, wait for the txn to go through, and then bribe people to extend the fork you started. The bribes are only valid if the attack chain becomes valid, otherwise they are rejected as double spends.

You need to be much more cautious about bribery when you use PoS. With PoW there are significant costs for dishonest miners in the event that the attack fails.
The attacker needs to pay compensation for that. With PoS, there are no costs for the dishonest miners if the attack fails. Thus you don't need to pay any compensation.
As I noted though you can build some costs in with a funky reward structure. This should help some.

To the degree that you incorporate PoS in any mechanism, bribing people becomes easier.  

The limiting feature on bribery though is that you need to personally make at least one secret block to get the bribery process started. Without the secret block, the bribe can get stolen (like you mention).
The signature sequence mechanism that I described makes secret mining extremely costly. Even mining just one secret block is infeasible without significant ownership (say 10% of all active stake minumum).
Ownership of 10% of stake removes attack incentives to begin with. So secret mining and associated double spends become solved problems.

[cunicula]

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.

Could you please explain what is the reasoning behind trading coin-age for interest? I mean, what are the particular benefits of using this reward scheme over other reward schemes.

If you have a fixed reward in a PoA style scheme (e.g. txn fees or block reward), then stakeholders should sign all chains to maximize their expected return. The coin-age scheme with fixed interest means that your expected reward does not increase when you sign additional chains. Signing additional chains might allow you to access the reward earlier, but it does not increase your expected reward. The coin-age scheme with variable interest causes your expected reward to decrease if you sign minority chains. Under this scheme, stakeholders (at least most of them) will strictly prefer to sign only one chain, the chain with the strongest consensus.

This issue of signing every chain you see only comes up when stake submission is not accompanied by work submission. It is not relevant to my ABAB style chain.

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.

I'm still not so sure. Maybe some small fraction of the stakeholders could increase the number of splits, say by synchronizing to provide their 5th signature only at round minutes (if they see that they're the lottery winner of 5th signature at 11:00:05 PM then they'll broadcast their signature at 11:01:00 PM). BTW my concerns here would be the same if it was the simplified core idea with a single signature instead of 5-10 signatures.

Yes, the 5th signatory can withhold his signature, then split off the chain, and building a one block fork. The fork cannot be extended past one block, however. This is only dangerous if you accept one confirmation txns. There is no danger at all if you require two confirmations. I didn't promise that I could make one confirm txns secure.

I think that the core idea of requiring PoW+lottery_PoA_signature before the block becomes valid raises interesting issues.
As a miner, if you solved the block and you're waiting for the stakeholder to broadcast his signature (and so far he doesn't), do you sit idle, or do you attempt to re-solve the block while waiting? Since if you manage to re-solve then maybe the 2nd stakeholder will provide his signature, while the 1st stakeholder wouldn't.

You re-solve the block while waiting. Recall that blocks with less than 5 sigs can never be recorded. You can't predict which blocks will succeed ahead of time. Meeting the difficulty target is just the first hurdle. Even with 50% participation, only about 1 in 30 blocks that meet the difficulty target will actually get 5 signatures. Many of these blocks will be obvious failures even before you transmit them (the signatories are obviously not participating based on the blockchain record). You would want to discard these without even bothering to transmit them. Other blocks will have a good chance. You want to transmit all blocks that have a good chance.

In the event of a contentious fork, you may also choose not to sign anything at all to avoid risk of loss, alternatively you may pick a chain which you strongly expect to win. This is good. It means that the choice between two public chains of equal length will fall upon the PoW miner. He will only be able to extend one chain. There won't be any ambiguity any more. Perhaps ask more questions about this because it is somewhat complex and may still be unclear.

BTW there are also interesting issues with protocols like your ABAB where the miner must use his privkey to generate the block. Specifically, you couldn't use mining pools, so maybe a variation of p2pool has to be an integral part of the protocol. This is actually a great feature rather than a drawback, because centralized mining pools are a security risk (can be DoS attacked, unlike p2pool, etc.) I don't remember whether I discussed it with you before, but I did raise this issue at #bitcoin-dev about one year ago (link).

Yes, I think it should be a limited spend privkey to allow for a more acceptable risk level. Yes, you can't use mining pools. Besides this there is no motivation to use a pool, rewards have low variance even though you don't use a pool. You just mine occasionally once you have accumulated enough coin-age to mine successfully, and then shut down once you succeed. If you have a very large stake, you can mine continuously. P2Pool could be used to allocate hashing power intelligently across stakes and divide the rewards among all participants.

I don't dispute (nor approve) any of that, I always use the phrase "monetary inflation" to be clear. Not sure how the 90%,10% online wallet example works, you don't really need to allocate 10% that sits idle because you can always transfer coins and forfeit some interest reward? But I guess that you would still want to tell your customers that their withdrawals cannot bypass the 10% limit unless they meet some requirements?

Yes, something like that. Recall that PPCoin uses coin-age based interest to reward proof of stake. There is talk of doublec's exchange collecting interest for people with balances there and distributing it to users. I don't think the details of how this will work are that important at this point.

At first glance this doesn't sound good at all to me. Why would we want to encourage wealth concentration by having the miners behave in the way that you describe? Don't you agree that having only a few stakeholders is a major security risk? I suppose that we agree that the network is more secure when the PoW hashpower is more distributed, so why wouldn't you agree that the same is true for distributed stake?

It does not encourage wealth concentration except to a negligible degree. For me wealth concentration is a fairness issue, not a security issue. I see wealth concentration as improving security.

I don't think it will be 'a few major stakeholders'. It will be more like there are 10 huge stakeholders holding (2.5% stake each), 100 large stakeholders holding (0.25% stake each), 1000 medium stakeholders (0.025% stake each), and 10,000 small stakeholders (0.0025% stake each). Wealth distributions always look like this (pareto). I'm sure bitcoin's does to. I don't see this as a security risk. In fact, I think security gets much stronger as wealth gets more concentrated. The huge stakeholders have major holdings and will be completely fucked if the network gets exploited. They will work hard to protect the network. The 10,000 small  don't have any incentive to protect the network proactively. It will be to much trouble for them.