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

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.


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 ?

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)

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

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

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?

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:


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:


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.

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

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.

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:


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:


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?

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.

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.

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

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.


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.

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.

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.

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.

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.


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.



 

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.

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


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.


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.

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.

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.

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.