Proof of Activity Proposal

[cunicula]

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.

I think T needs to be much higher, or the system won't have much to distinguish itself from PoW.

1) Attacker wins if (1+pT+sT) w > (1+pT)(1-w) [this describes the worst case scenario.]

Say p=1/10 and s=1/10. I think this reasonably describes an absolute worst case scenario. I am hoping that signing can be made safe and rewarding enough that we can guarantee p>=0.1. I'm sure that we can guarantee s<0.1. It does not make any sense whatsoever to attack with high s. The attacker would face huge personal losses. The attacker wins if w>0.46. That is fine.

2) If T=2, p=1, s=0, and all stakeholders are honest (absolute best case scenario), then the attacker wins if w > (1+2T)(1-w). That is if w>0.75. Thus, absolute ideal performance with these parameters improves the work requirements for attack from 50.1% to 75.1%. I do not like these odds at all. My demand for the best case scenario was 99.9%.

3) We can increase T to meet my best case scenario demand that w=0.999. Then, T=499. Now consider the first scenario again. p=1/10 and s=1/10. Then the attacker needs w>0.34. That is not that much worse than w>0.46.  Say we take it a step further increase my best case scenario demand to w=1. w = (T+10)/(3T+20). lim T->∞ w =0.33. Thus if you are going in this direction, and you can p>=0.1, you might as well make T=∞. That isn't much worse, so why not increase T to ∞?

What does it mean if T is ∞? The only sensible interpretation is that blocks require PoA signatures in order to be extended.

Can this work with mining pools? Sure, why not?

1) Mining pool generates block and adds it to blockchain.
2) If block gets signature, then it can be extended. Mining pool gets reward.
3) If block does not get signature, then it cannot be extended. Go to step 1.

This means that there will be multiple blocks stored in memory while they are waiting for signatures, e.g. at any point in time nodes will have info like this.
Let's suppose we start from a highly confused situation with a lot of these blocks and no signatures. Wi is a block waiting for a signature and the memory pool stores up to n blocks.


H-W1
H-W2
...
H-Wi
...
H-Wn


Suppose that several of the blocks get signed, but others don't.

H-W1
H-W2-s
...
H-Wi-s
...
H-Wn

After a time interval (say 1 minute after discovery), the unsigned chains can be removed from memory. If we hear about them again later, we can add them back in.

[]
H-W2-s
[]
H-Wi-s
[]
[]

Then miners can pick from the signed chains to work on extensions.

Suppose a new block is found, for one of the two extensions. Then the memory pool looks like this.

[]
H-W2-s
[]
H-Wi-s-Wi2
[]
[]

Now block Wi2 will either get a signature, or it won't. Say it doesn't get a sig. In the meantime, miners may have been finding other blocks that extend W2-s and Wi-s.
They found H-Wi-s-Wi3 and H-W2-s-W23
Pools will want to wait a bit before spending work on this (say a minute) because the blocks will likely be orphaned if Wi2 gets a signature.
[]
H-Wi-s-Wi2
H-Wi-s-Wi3
H-W2-s-W23
[]
H-W2-s-W2n

One of these blocks gets signed, say H-W2-s-W23, and the other blocks are cleared from memory after a time interval, so we are left with.

[]
[]
[]
H-W2-s-W23-s
[]
[]

We can see that the system has achieved consensus about H-W2. There is no point in revisiting this history, it would clearly be a waste of work.

I think a good system is to make an ABAB chain where all of the blocks have PoA signatures. So the chain can look like AsBsAsBs.

Double-spending is extremely difficult because the s signatures make secret chain extensions very hard. You could publicly flood the chain with empty blocks. However, because of the B blocks, you will
quickly run out of coin-confirmations when you try to do this unless you have s>0.5. PoW miners and Pools are still happy because they can still generate A blocks and capture block reward. Both A and B blocks share some of the txn fees with the block signers. The txn fees are distributed from a long-run average fund, so it is not feasible to offer bribes to fork the chain.

The only weakness occurs if p falls to a very low level. Stake signing needs to be made safe in order to prevent this. This means their needs to be a specialized signing private key with limited spending functionality. I discussed how to do this in the previously linked thread: https://bitcointalk.org/index.php?topic=115608.msg1319612#msg1319612

To compare two chains of the same difficulty, just use length (ignoring unsigned blocks at the end)
To compare two chains of varying difficulty:
Total Chain Difficulty = (0.5 * Total A Chain Difficulty^r + 0.5*Total B Chain Difficulty^r)^(1/r) where r is some negative number. Say -5.
The function ensures that you can't get very far at all in replacing one chain with another unless you can simultaneously increase both difficulty levels. Increasing just one will not cut it.

[iddo]

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

I don't understand why you're talking about 54% hashpower, given that I assumed that the attacker even hash 99% hashpower.
Suppose that the attacker generates blocks in public, and it takes the attacker 10 minutes to generate each block. When the 5th block is generated, the lucky stakeholder is derived from that hashes of the last 5 blocks, so this stakeholder's client could notify him, and now this stakeholder can create the 7th block (2 blocks after this 5th block) without any PoW effort. If this lucky stakeholder creates the 7th block and broadcasts it in less than 10 minutes, then the distributed network will accept it as a valid extension of the chain, and the attacker will be forced to continue to extend the chain from the 8th block.

Actually, xor'ing the last 5 blocks was a bad idea, because the attacker could generate 4 blocks in public and then re-solve the 5th block repeatedly until he derives himself as the chosen stakeholder. One better way to do it would be something like this: suppose that the total number of satoshis minted so far is bounded by 2^x (say x=30), then each of the 5 block hashes derives x/5 bits (independently of the other 4 blocks), and the xor'd hash of all the 5 blocks derives a permutation out of the 5! or possible permutations. This should make it nearly impossible for the attacker to derive a satoshi that belongs to him by re-solving only the 5th block.
I still suspect that I'm missing more elegant (crypto oriented) ways to rely on all of the last 5 blocks in order to derive a uniform-random number. Suggestions?

Anyway, in practice we can easily overcome this issue by using scrypt with many iteration and a large memory buffer to derive the chosen stakeholder. Then the attacker couldn't afford repeated attempts to re-derive the stakeholder even if he has 99% hashpower, because the honest network with 1% hashpower only needs to derive the stakeholder once.

[cunicula]

If this lucky stakeholders creates the 7th block and broadcasts it in less than 10 minutes, then the distributed network will accept it as a valid extension of the chain, and the attacker will be forced to continue to extend the chain from the 8th block.

You need a rule to compare two chains. If the longest chain wins for example, then the attacker does not need to include any of the PoA generated blocks provided that he has 54% of hashing power.

[cunicula]

Suggestions?

As suggested before, for each block,

1) Require the selection of multiple winners who sign in sequence. Thus the attacker chances of selecting himself become (s)^n, where n is the length of the sequence and 0<s<1 is the attackers share of stake.

2) Do not make these XOR'd blocks or whatever optional. Make them mandatory.

[iddo]

If this lucky stakeholders creates the 7th block and broadcasts it in less than 10 minutes, then the distributed network will accept it as a valid extension of the chain, and the attacker will be forced to continue to extend the chain from the 8th block.

You need a rule to compare two chains. If the longest chain wins for example, then the attacker does not need to include any of the PoA generated blocks provided that he has 54% of hashing power.

Yes, longest chain wins. This new idea that I described in posts #97 and #102 is independent of PoA, you can apply it to pure-PoW in order to get protection from an attacker who generates empty blocks.
I still don't understand why you're talking about 54% hashpower instead of 99% hashpower. Because of the difficulty adjustments, even with 99% hashpower the attacker needs 10mins to generate each block, while the chosen stakeholder can generate the (say) 7th block instantly, just by signing it. Am I missing something here? Please take another look at posts #97 and #102 to make sure that you understand this protocol?

[cunicula]

If this lucky stakeholders creates the 7th block and broadcasts it in less than 10 minutes, then the distributed network will accept it as a valid extension of the chain, and the attacker will be forced to continue to extend the chain from the 8th block.

You need a rule to compare two chains. If the longest chain wins for example, then the attacker does not need to include any of the PoA generated blocks provided that he has 54% of hashing power.

Yes, longest chain wins. This new idea that I described in posts #97 and #102 is independent of PoA, you can apply it to pure-PoW in order to get protection from an attacker who generates empty blocks.
I still don't understand why you're talking about 54% hashpower instead of 99% hashpower. Because of the difficulty adjustments, even with 99% hashpower the attacker needs 10mins to generate each block, while the chosen stakeholder can generate the (say) 7th block instantly, just by signing it. Am I missing something here? Please take another look at posts #97 and #102 to make sure that you understand this protocol?

In bitcoin, an attacker with 51% of hashing power can refuse to build on other people's chains. His chain will always be the longest.

In your case, there is an optional PoA block after every 6th block. Since this block is optional (not a good idea), the attacker can also refuse to build on top of it. He can construct a long chain which does not include any PoA blocks. This is the key point. The attacker is not required to pay any attention to these optional blocks.

The legitimate chain will get an PoA extra block every 6 blocks, giving it a small length advantage. The attacker can overcome this small advantage by having 54% of hashing power instead of 50.1%.

If you make the PoA block mandatory this problem is fixed. This is the reasoning behind the ABABAB system. The key point is that the block ordering is deterministic. The advantages to deterministic ordering apply to PoA as well. Alternate designs such as in PPCoin allow for random orderings of PoW and PoS blocks. This is bad. It allows attackers to win using just one block type. In PPCoin the duration during which attackers can win is limited through difficulty adjustments. This is useless in the short-run, but provides some long-run protection. In your case there is no difficulty adjustment for PoA blocks, so the attacker can win forever.

This is also the most important reason why I object to simple PoA. The PoA protection will be extremely weak unless the signatures are mandatory. Make them mandatory. Why not?

[iddo]

Right, oops, my mind was messed up and I forgot that the block is optional.
Need to consider what'd be the best way to deal with inactive stakeholders, instead of simply saying that the block is optional (which was a very bad idea).
Having significantly higher PoW difficulty for this block (if the lucky stakeholder is absent) is one option. Making the block mandatory so that the earlier block would have to be re-solved is another option. Maybe there are better options...

Edit: if the winning satoshi is R then we could have something like R_n=hash(R,n) (mod X) where X is the total amount of satoshis minted until this block, n=1,2,3,... represented number of minutes, and if you're the R_n stakeholder then you may generate the block if you attach to it a PoW proof that'd take n minutes to generate according to the current difficulty.

[cunicula]

Right, oops, my mind was messed up and I forgot that the block is optional.
Need to consider what'd be the best way to deal with inactive stakeholders, instead of simply saying that the block is optional (which was a very bad idea).
Having significantly higher PoW difficulty for this block (if the lucky stakeholder is absent) is one option. Making the block mandatory so that the earlier block would have to be re-solved is another option. Maybe there are better options...

Edit: if the winning satoshi is R then we could have something like R_n=hash(R,n) (mod X) where X is the total amount of satoshis minted until this block, n=1,2,3,... represented number of minutes, and if you're the R_n stakeholder then you may generate the block if you attach to it a PoW proof that'd take n minutes to generate according to the current difficulty.

I would just say orphan the block if the stakeholder is missing. A new block can be built which maps to a new stakeholder. Any non-mandatory solution will only work over a long time interval (like a difficulty adjustment).

You can deal with missing stakeholders as follows:

1) Include an optional signature which maps to a random stakeholder. Offer a reward for this signature.
2) If that signature isn't delivered in a timely fashion, there will be a record of it in the chain (this signature is optional).
3) Do not ask this public key to sign any blocks in the future. If a subsequent 'follow the satoshi' lottery maps to this key, then hash this draw again to get a new draw. Iterate if necessary.
4) The coins can reactivate themselves by getting moved to a new public key that hasn't been 'deactivated'.

If you do this then the lottery will constantly be updated to include only active participants.

[iddo]

3) We can increase T to meet my best case scenario demand that w=0.999. Then, T=499. Now consider the first scenario again. p=1/10 and s=1/10

I attempted to explain in post #78 why the non-public double-spending attack implies that big T such as T=499 is a bad idea.
Let's use your suggested p=s=1/10 and let's assume for example that the attacker has 20% of the total hashpower.
Suppose the attacker wishes to do 20-blocks reorg. He has 1/4 of the total hashpower, so he will generate 5 blocks in secret while the honest network generates 20 blocks. Because p=1/10, only 2 out of the 20 honest blocks will be signed, so the honest branch has 2T+negligible effective length. Therefore, the task of the attacker is to get 3 signed blocks in his 5 blocks branch. His success probability is 0.00856 according to binomial distribution with success probability s=1/10, meaning that once every 117 blocks he could do 20-blocks reorg (once every 19.5 hours with 10mins block-time).

[iddo]

Right, oops, my mind was messed up and I forgot that the block is optional.
Need to consider what'd be the best way to deal with inactive stakeholders, instead of simply saying that the block is optional (which was a very bad idea).
Having significantly higher PoW difficulty for this block (if the lucky stakeholder is absent) is one option. Making the block mandatory so that the earlier block would have to be re-solved is another option. Maybe there are better options...

Edit: if the winning satoshi is R then we could have something like R_n=hash(R,n) (mod X) where X is the total amount of satoshis minted until this block, n=1,2,3,... represented number of minutes, and if you're the R_n stakeholder then you may generate the block if you attach to it a PoW proof that'd take n minutes to generate according to the current difficulty.

I would just say orphan the block if the stakeholder is missing. A new block can be built which maps to a new stakeholder. Any non-mandatory solution will only work over a long time interval (like a difficulty adjustment).

You can deal with missing stakeholders as follows:

1) Include an optional signature which maps to a random stakeholder. Offer a reward for this signature.
2) If that signature isn't delivered in a timely fashion, there will be a record of it in the chain (this signature is optional).
3) Do not ask this public key to sign any blocks in the future. If a subsequent 'follow the satoshi' lottery maps to this key, then hash this draw again to get a new draw. Iterate if necessary.
4) The coins can reactivate themselves by getting moved to a new public key that hasn't been 'deactivated'.

If you do this then the lottery will constantly be updated to include only active participants.

This sounds computationally intensive, because the blacklisted addresses will be scattered in different places in the blockchain. Also, it's unclear how the nodes could verify that the blacklisted address wasn't added maliciously, and it's unclear what'd be the incentive to put the blacklisted addresses in the blockchain. Maybe this idea can be refined, though in the spirit of PoA I'm striving for a protocol that's as simple as possible.

Do you think that there's something inherently wrong with my R_n=hash(R,n) suggestion, or that it's just redundant? If the miners have to go several blocks back and re-solve, then there's a lot of unpredictability involved, with regard to how long it takes until some stakeholder will finally be found?
Maybe we could come up with more elegant ideas than that hash(R,n) suggestion.

Edit: on second thought, hash(R,n) can be attacked, the attacker can try to increment n until he derives himself as the stakeholder, then solve the block in n minutes. If the attacker has huge hashpower, maybe he could do it in secret, before revealing the (say) 5th block.

[cunicula]

3) We can increase T to meet my best case scenario demand that w=0.999. Then, T=499. Now consider the first scenario again. p=1/10 and s=1/10

I attempted to explain in post #78 why the non-public double-spending attack implies that big T such as T=499 is a bad idea.
Let's use your suggested p=s=1/10 and let's assume for example that the attacker has 20% of the total hashpower.
Suppose the attacker wishes to do 20-blocks reorg. He has 1/4 of the total hashpower, so he will generate 5 blocks in secret while the honest network generates 20 blocks. Because p=1/0, only 2 out of the 20 honest blocks will be signed, so the honest branch has 2T+negligible effective length. Therefore, the task of the attacker is to get 3 signed blocks in his 5 blocks branch. His success probability is 0.00856 according to binomial distribution with success probability s=1/10, meaning that once every 117 blocks he could do 20-blocks reorg (once every 19.5 hours with 10mins block-time).

You are assuming that unsigned blocks are permitted. That is a bad idea. Make signing mandatory. The perceived issue disappears.
Tolerating unsigned blocks has a wide array of negative consequences.

In particular, you stick yourself with the following tradeoff.
1) Protection is very weak.
or
2) There can be periodic long reorgs.
or
3) Some combination of (1) and (2)

This is the same thing that happens with ABAB blocks if you allow for random ordering (e.g. AABBBBABBAA instead of ABABAB). The same principle is at work here. Deterministic ordering is the solution.

[iddo]

Regarding signing-key / limited-withdrawal delegation:

Before getting into more useful/complex limited-withdrawal schemes, I'd first like to consider what'd be the least bloated way to implement key delegation.

We could have a single bit in each address that specifies whether it's a regular address or a delegated address. The protocol rule could be that a delegated address can only spend (say) 5 coins at each block. Another protocol rule would be that a delegated address is only allowed to receive coins once (except for winning the follow-the-satoshi lottery), and the delegated address is allowed to transfer all of its coins back to the address from which it received coins. In other words, the txn in which the regular address sends coins to the delegated address is where the linkage is established in the blockchain. Whenever someone tries to send coins to a delegated address (i.e. an address in which the delegate bit is set), we have to verify that this delegated address has never received coins before. When the delegated address wishes to restore all the coins back to its linked regular address, we have to look at the linkage txn in the blockchain, i.e. verify that the regular address was indeed the address that sent coins to this delegated address.
If the amount of coins that this kind of delegated address is large enough relative to expected stakeholder signing reward, then it'd discourage the stakeholders from selling their delegated addresses to the attacker. Whenever the delegated address spends coins, the stakeholder could receive notification via the client or via blockexplorer website, so in case the address was compromised he could withdraw the rest of his coins back to the linked address.
Could key delegation be implemented in a more simple way than this?

[iddo]

You are assuming that unsigned blocks are permitted. That is a bad idea. Make signing mandatory. The perceived issue disappears.

How to make signing mandatory? Do you mean post #72 and #73, i.e. the miner broadcasts his solved block and then the stakeholder has to sign it, before the chain could be extended from this block? That's quite different than PoA, and I think that your analysis in post #101 was about PoA, right?

I think that PoA with T=2 is conservative, meaning that it isn't less secure than pure-PoW, but it doesn't offer double-spending protection from attackers with 99% hashpower, only from attackers with 66% hashpower etc.

[iddo]

Any non-mandatory solution will only work over a long time interval

This comment actually appears to be the elegant solution that I was looking for: every 5th block combines the 4 blocks before it to derives the lucky stakeholder address, and this lucky stakeholder may create the 105th block (i.e. 100 blocks after this 5th block) without any PoW effort, instead of the 7th block that I said earlier. So blocks 5,10,15,20,25,... specify the lucky stakeholders for blocks 105,110,115,120,125,... and we get that every 5th block is generated by the stakeholders to thwart the empty blocks attack, which is even better than every 7th block. Therefore we can have the protocol rule of allowing the 105th block (and so on) to be generated in the regular fashion via PoW according to the current difficulty, to deal with inactive stakeholders. As an added bonus, the stakeholders rather than the attacker control the 5th blocks (unless we have an inactive stakeholder), so the attacker couldn't try to control the xor in order to derive himself as the next stakeholder. In fact, we might need to be worried about a malicious stakeholder who tries to derive himself as the next stakeholder (100 blocks later) by doing many signature attempts, so having the 5th block control only x/5 bits of the derived satoshi as in post #102 (or some other idea) can be useful.

Edit: an interesting thought experiment is to consider what would happen if we allow stakeholders to generate every block instead of every (say) 5th block, i.e. blocks 101,102,103 and so on instead of blocks 105,110,115 and so on. If the safe double-spending distance is 6, then the stakeholders who were chosen to generate the blocks 101,102,103,104,105,106,107 could collude by including the txn that they wish to reverse in block 101, then extend the chain until block 106 and thereby get the merchant to send the merchandise, and then instantly release an alternative branch 101*,102*,103*,104*,105*,106*,107* where block 101* doesn't contain the relevant txn. If stakeholders blocks are at every 5th block, then the stakeholder who was chosen for block 100 will have to generate blocks 101*,102*,... via PoW, he could only collude with the next stakeholder at block 105, so I suppose that it's better to have the interval between stakeholders blocks longer than the safe double-spend distance, so for example every 10th block instead of every 5th block.

[cunicula]

As long as the blocks are optional the attacker can just bypass them. They have to be mandatory to be useful. It will not help to link the 5th block to the 105th block. The 105th block can simply be ignored. If the 105th block is mandatory, then you would have to orphan the entire 100 block sequence whenever the 105th block's stakeholder is found. It is better to just make it the next block, then you only have to orphan one PoW block.

Why does it matter if the implementation differs from PoA? PoA is weak and ineffective.
PPCoin has already implemented a far superior (though still imperfect) solution. If you don't try to improve on PPCoin then what is the point?

[iddo]

As long as the blocks are optional the attacker can just bypass them. They have to be mandatory to be useful. It will not help to link the 5th block to the 105th block. The 105th block can simply be ignored. If the 105th block is mandatory, then you would have to orphan the entire 100 block sequence whenever the 105th block's stakeholder is found. It is better to just make it the next block, then you only have to orphan one PoW block.

Right, sorry, it was a dumb idea. The attacker could simply create PoW blocks around the 105th block.
Unfortunately, so far it seems to me that inactive stakeholders make this idea quite problematic.

As mentioned in your post #100, one option to to give high weight to the stakeholders blocks. This can be viewed as keeping the chain interval for which the winning stakeholder was absent, and just extending the chain afterwards (because the weight of the interval without stakeholder block is negligible). Though we could try to fine-tune the weights, so that PoW weights aren't so negligible when compared to stakeholders block weight. This approach opens the door to double-spending attacks by miners who collude with some lucky stakeholder who will reveal his non-PoW block later, which would cause a reorg because his block has high weight.

The other approach is to require that the stakeholders block will be generated. Suppose we want security against attacker with 99% hashpower who generates empty blocks. This attacker is almost 100 times faster than the honest miners. Let's use your frequent assumption that in the worst case the attacker still has less than 10% of the total stake (note: total stake, not active stake). If we go with my R_n=hash(R,n) idea in order to generate a new stakeholder if the previous stakeholder turned out to be inactive, it will take the attacker 10 attempts of hash(R,n) on average until he derives himself as the winning stakeholder, because he has 1/10 of the total stake. If we say that with n=1 you should attach PoW proof that's equivalent to generating 10 blocks according to the current difficulty, with n=2 you need PoW proof of 20 blocks, etc., then on average the attacker will win the lottery at hash(R,10) so he will have to submit PoW proof that's equivalent to generating 100 blocks, which is slower than the honest miners, and therefore he will fail if he tries to ignore the stakeholders block by generating PoW proof instead. We would also need to make sure that it isn't easier to go back (say) 5 blocks and extend the chain again in order to derive a new random stakeholder, so if stakeholders blocks are at every 5th block then we could say that the next stakeholder is derived from last (say) 15 blocks, and because those blocks contain 3 stakeholders blocks that the attack cannot generate himself via PoW, it'd be futile for him to try to reverse the chain. Deriving from the last 10 blocks (even if there weren't stakeholders blocks among them) is also good enough, because the attacker would need to generate 10 PoW blocks in order to get a single attempt at deriving himself as the random stakeholder.

Why does it matter if the implementation differs from PoA? PoA is weak and ineffective.

So far I think that simple-PoA is effective in preventing double-spending attacks. I'm still curious to hear your answers regarding the bribe attack (end of post #94). Regarding the empty blocks attack, the jury is still out, I'm still vague on what'd be the best option. The PoA-style idea seems to be inelegant so far, maybe I'm missing something and it could be improved. Helpful comments would be very much appreciated.

PPCoin has already implemented a far superior (though still imperfect) solution. If you don't try to improve on PPCoin then what is the point?

Is there a post that describes the PPCoin protocol?
I've tried to search a little now and I see for example this post that you've made: https://bitcointalk.org/index.php?topic=101820.msg1302737#msg1302737
Nobody answered your post there. Maybe the person who coded PPCoin has never participated in this forum, I doubt whether the proponents of PPCoin here actually understand the protocol. Also, if the source code hasn't been reviewed then quite possibly there would be messy mistakes in it.
Do you know whether PPCoin offers security against double-spending attacks?
Probably only killerstorm and you understand the PPCoin protocol, so maybe one of you could summarize how it works?

[iddo]

Actually, xor'ing the last 5 blocks was a bad idea, because the attacker could generate 4 blocks in public and then re-solve the 5th block repeatedly until he derives himself as the chosen stakeholder. One better way to do it would be something like this: suppose that the total number of satoshis minted so far is bounded by 2^x (say x=30), then each of the 5 block hashes derives x/5 bits (independently of the other 4 blocks), and the xor'd hash of all the 5 blocks derives a permutation out of the 5! or possible permutations. This should make it nearly impossible for the attacker to derive a satoshi that belongs to him by re-solving only the 5th block.
I still suspect that I'm missing more elegant (crypto oriented) ways to rely on all of the last 5 blocks in order to derive a uniform-random number. Suggestions?

Anyway, in practice we can easily overcome this issue by using scrypt with many iteration and a large memory buffer to derive the chosen stakeholder. Then the attacker couldn't afford repeated attempts to re-derive the stakeholder even if he has 99% hashpower, because the honest network with 1% hashpower only needs to derive the stakeholder once.

One other way to derive x-bits pseudorandom number from the last 5 block hashes: derive x pseudorandom bits from the first block hash and store them in R, then derive log(5)*x pseudorandom bits from the 2nd block hash and view it as base5 number of 30 digits (e.g. 3402104...), and if the ith digit of this base5 number is 0 then flip the ith bit of R, meaning that we flip each bit with 1/5 probability. Do the same with the 3rd,4th,5th block hashes as we did with the 2nd block hash.

[iddo]

Actually, there is a substantive difference between adding empty blocks security (via lottery) to pure-PoW versus adding it to simple-PoA. The difference is that with simple-PoA the attacker cannot keep his branch secret for too long, because he wouldn't accumulate PoA signatures so the honest branch will have more weight multipliers. We'd need to tweak the previous idea in order to take advantage of simple-PoA. The problem earlier was that if the (say) 5th block was a stakeholders block that some lucky stakeholder may create, then the attacker could simply generate the 1st,2nd,3rd blocks in public, and then generate the 4th,5th blocks in secret and reveal them together (if the lucky stakeholder could see the 4th block then he would generate the 5th block much faster than the attacker, but if he only sees the 3rd block then he cannot). Instead, we can view the blockchain as batches of 5 blocks, each batch of 5 blocks derives the pseudorandom stakeholder, and this lucky stakeholder may create a block (without PoW effort) in any place at the next batch of 5 blocks. Actually, it could be useful to use my botched idea from post #114 and introduce some large gap, for example the 1st batch of 5 blocks derives a lucky stakeholder for the 200th batch (i.e. 1000 blocks later), so that the lucky stakeholder will be notified early (unlike simple-PoA signatures where we cannot do it), and this might increase stakeholders participation. With the large gap, we cannot do hash(R,n) as in post #116 etc., so the protocol rule can be that if the first 4 blocks in each batch of 5 blocks didn't include a stakeholders block, then to generate the 5th block via PoW you'd need to meet a higher difficulty. The weight of a stakeholders block can be the same as the weight of a signed simple-PoA block, or higher/lower.

Let's try an example with specific numbers. Batches of 5 blocks as above, simple-PoA with 5-fold weight multiplier (T=4, as in coblee's OP). Note that to get security against double-spending with 5-fold you can still wait for 5-out-of-10 signed blocks and the attacker would need 7 secret consecutive signed blocks (see post #78). Let's assume that 75% of all stakeholders blocks will be created (large gap for notification, and the lucky stakeholder gets the entire reward of the block that he created, unlike when he provides PoA signatures and gets 10% of the reward). Therefore, we can set the PoW difficulty of generating the 5th block of a batch with no stakeholders block to be 4 times harder. This means that in 3/4 of the time the batch will have one block that is generated instantly, and in 1/4 of the time the batch will have a block that takes 4 times longer to generate, so on average we didn't decrease the performance. Let's assume that the weight of a stakeholder block is 10-fold, i.e. twice more than the weight of PoA signed block. Let's assume that on average half of the regular blocks get signed via simple-PoA.  Now, an honest batch of 5 blocks will have weight 10+5+5+1+1=22, and the secret branch of the PoW attacker has weight=1 in each block. This means that while the honest network generates 4 blocks to gain weight=22, the attacker will need to generate 23 consecutive blocks in order to outcompete the honest batch of 5 blocks, but among those 23 blocks there were 4 blocks that he had to generate with 4-fold increased difficulty. To sum up, the attackers needs to generate 35 blocks to outcompete 4 honest blocks, so his hashpower has to be 8.75 times faster than the honest miners, meaning that he has nearly 90% of the total hashpower in order to generate empty blocks continuously.

What might be sketchy with those specific numbers is giving twice more weight to the stakeholders block, so the lucky stakeholder could try to collude with miners and double-spend, though his weight advantage wouldn't be so big. One simple way approach to avoid this is to increase the simple-PoA multiplier to a little more than 5-fold, but then users might have to wait for a little more than 5-out-10 signed blocks to get security from double-spending, which would be fine with 2.5min block time. However, all of this assumes that half of the stakeholders provide PoA signatures, hopefully the incentives could be put in place for that.

Edit: 4-fold higher difficulty for 5th PoW block is good for the empty blocks attack, but bad for double-spending attacks, because the malicious stakeholder who was chosen in the lottery and creates a secret branch with his stakeholders block will also have time to create 4 additional blocks ahead of the honest network. Repeating the previous example with the same numbers and with regular PoW difficulty instead of 4-fold difficulty, we get that the attacker who generates empty blocks will need 85.2% of the total hashpower.

[iddo]

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.

Shouldn't all voting nominations and electorate votes be added to the chain without the central committee signatures? Otherwise the committe could block the votes?

If the majority of the central committee wishes to abuse their power, what could they do exactly? Only withhold txns? Maybe offer some type of insider trading bribes regarding which txns will be included and at what time? Could they try to do double-spending by signing two conflicting blocks with their 5 signatures, and then broadcast the two blocks to different parts of the network at the same time? Any other ideas for attacks by the central committee?

I'm biased against this kind of protocol, because the centralized entity would have too much power that it could abuse, and it'd take a long time to replace the centralized entity. So the central committee could boost confidence by behaving flawlessly until more participants use the network, then more and more money can be influenced by the central committee members, and then they might begin to abuse their power.

Maybe you should start a thread to discuss this kind of protocol, my biased opnion here is probably not so useful.

[cunicula]

Hey iddo,

Ignore the committee idea. I wasn't entirely serious. It is just seemed amusing that election of dictators solved problems.

I think it would be useful to recap my views. I think going into details can sometimes be distracting. It might be helpful to look at things from an outline perspective at this point.
Once we agree on the outline, then we can move on to details. I think it is best to discuss one point at a time though. Otherwise we may just jump around without ever reaching consensus.

1) some signatures on should be mandatory

mandatory sigs make secret PoW attacks very, very hard

2) there should be also be optional signatures

optional signatures create a record of nonparticipating stakeholders and allow them to be removed from the lottery. Without this, lost coins would eventually become a problem.

3) Allow random lottery winners to generate mandatory blocks is a good idea

The mandatory blocks prevent PoW denial of service. With this taken care of, my system of proof-of-stake becomes redundant and can be dropped. This simplifies things.

4) Signing Participation should be addressed by offering rewards and reducing costs

This is at least a three-pronged problem. 1) Provide adequate rewards for signatories. 2) Provide adequate security from theft for signatories. 3) Try to keep bandwidth requirements reasonable.

5) Fee payments need to be specified in the protocol. The txn fee system in bitcoin is very strange. Future txn fees are more or less completely unpredictable. This is not good. We should be able to predict (at least approximately) what rewards will be at any point in time. Just setting a fee = 0.01 won't cut it. Since price moves, this can mean anything and would need to be constantly readjusted. Secondly, freely adjustable fees provide a plausible bribe vector. I don't like this either.

I favor a fee or reward system based on coin-age. Options are 1) Inflation based on miners/signers coin-age. (fees are destroyed) 2) txn fees based on senders coin-age (coins are given to miner/signer).