Proof of Activity Proposal

[iddo]

If the stakeholders block is mandatory then it indeed provides excellent security against the empty blocks attack. The problem is what to do with inactive stakeholders (because of lost coins among other reasons). One way is to backtrack and re-generate an entirely new interval of the chain, it probably has to be an interval instead of just a single block because the lucky stakeholder should get early notification instead of being forced to generate the next block immediately after the last block was generated. This option isn't so elegant, neither for the users nor for the security analysis. Another option is the hash(R,n) idea, in post #116 I described what parameters we'd need for security against an attacker with 99% of the total hashpower and 10% of the total stake, namely the performance of the network degrades and becomes 10 times slower whenever the lucky stakeholder is absent. We could degrade the performance to be only 5 times slower etc., and then get security only against less powerful attackers. I'd be very much interested to hear about other ideas to deal with inactive stakeholders in the case of mandatory lottery blocks.

Correct me if I'm wrong, but I think that the question of whether we blacklist inactive stakeholders is orthogonal to to whether the stakeholders block is mandatory or optional. If it's mandatory then the fact that we have to re-derive the winning stakeholder handles inactive stakeholders. If it's optional then that in and of itself handles inactive stakeholders. The incentives structure should adjust so that the active stakeholders fraction is above some threshold, and dead/lost stake would be factored into this. Blacklisting is just an extra feature, I mentioned in post #110 why it seems problematic to me, but maybe it could be refined.

If the stakeholder blocks are optional, then we have trade-off between the effectiveness of empty blocks protection and the effectiveness of double-spending protection. The relevant parameters that affect the trade-off are the length of the batch that needs to include one stakeholders block (longer length provides better security against double-spending, but 99% PoW-only attacker would then generate a higher ratio of empty blocks), PoW difficulty multiplier in case the lucky stakeholder is absent, and the weight of the stakeholders block. When we increase these last two parameters we get better security against the empty blocks attack, but worse security against double-spending (end of post #118). In fact, in order for the stakeholders block to be completely neutral for double-spending attacks we need to give it zero weight. Then in the example in post #118 we have that the honest network generates 4 blocks to gain 0+1+1+5+5=12 weight, so the PoW attacker would need to generate 13 blocks versus 4 honest blocks, i.e. he needs 76.3% of the total hashpower, as opposed to 90% in the initial example.

I'm also open to debate whether something like ABAB or A9BA9B (+ simple-PoA) is better than "lottery empty blocks security" + simple-PoA. Maybe you even claim that double-spending security isn't important, so ABAB is enough, but still if we could devise a protocol that offers both empty blocks security and double-spending security then that would be better (at the very least from a PR standpoint). However, if we talk about too many issues simultaneously then it's easier to lose track, so I'd prefer that we first discuss what'd be the best way to do the "lottery empty blocks security".

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

Please explain these two options in more details. Does option (1) imply infinite monetary inflation? Please also explain in more details why having optional txn fees so that the security properties of the network are set by the free market is a bad idea. I'm not saying that you're wrong, I'm just hoping that you could make your arguments more clear.

[1715390303]

1715390303

[1715390303]

1715390303

[1715390303]

1715390303

[cunicula]

I'm going to hold off on the other questions because I want to focus on what I think is the #1 issue here.

Why does the stakeholder need any advance notice at all (either to generate a block or provide a signature)? Stakeholders in PPCoin (for example) are always ready to generate blocks. It seems to work fine.

If the stakeholder does not need advance notice, I don't see what the problem is. Just orphan blocks that identify missing stakeholders.

Could you explain why you feel advance notice is necessary (or even just helpful in some way)?

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

Actually, this appears to be quite bad if the attacker has a significant amount of stake. Let's say the total stake is 2^30 satoshis, and the attacker has 1/2^3=1/8 of the total stake. The probability that the Hamming ball of weight 6 around some (pseudo)random number contains a satoshi that belongs to the attacker (assuming that his satoshis are uniformly distributed) is 1-product[1-2^6/(2^30-k), k=0...2^27-1] > 1-(1-2^6/2^30)^2^27 = 0.9996, so the attacker could still re-solve the last block via PoW until he derives himself as the lucky stakeholder. The optimal way to rely on the entire history of the previous blocks (instead of just the last block) is to derive a single bit from each block, so we'd need to rely of 30 blocks (which is ok because those 30 blocks may include previous stakeholders blocks among them).

I'll also mention the simple argument why we cannot use commitment schemes etc. to force everyone to re-solve the last (say) 5 blocks, under the assumption that the hash function is a random oracle. If it was true that we have to re-solve all of the 5 blocks to derive a new winning stakeholder, then it implies that after solving the 1st block (in 10 minutes on average because of the difficulty adjustments) each of the next 4 blocks must have only one particular solution (because the random oracle is used to derive the winning stakeholder). So solving each of the next 4 blocks is equivalent to doing pre-image attack on the hash function, which is an infeasible task, as opposed to a task that takes 10 minutes. QED.

If the stakeholder does not need advance notice, I don't see what the problem is. Just orphan blocks that identify missing stakeholders.

Could you explain why you feel advance notice is necessary (or even just helpful in some way)?

The advance notice is just a feature that would hopefully increase the stakeholders' participation. We agree that the protocol becomes more secure when more stakeholders are encouraged to participate. The same issue exists with simple-PoA, meaning that if the simple-PoA rule is that you may provide your signature only in the next 3 blocks (instead of 6 blocks) after you were derived as the winning stakeholder, then attack scenarios such as the double-spending bribes service become more difficult for the the attacker, because his secret branch will have fewer opportunities to gather signatures from non-honest rational stakeholders when he goes public. The reason for specifying (say) 6 blocks instead of (say) 3 blocks as the limit in simple-PoA is to encourage stakeholders' participation by giving them more time. So it's a trade-off between two desirable properties. As I mentioned, the thing is that for the empty blocks security it's fine to give an advance notice of (say) 1000 blocks, while for the simple-PoA double-spending security we cannot give an advance notice that's longer than the safe double-spending distance because of those attack scenarios with the bribes service and so on.

But maybe it'd be better forget about the advance notice for the empty blocks security, we should consider to pros/cons of doing that. If we have mandatory stakeholders blocks and there's no advance notice, then the protocol would be for example that every 5th block derives the identity of the lucky stakeholder who must create the 6th block. In order to deal with an attacker who has 99% hashpower, we can have scrypt based derivation function to choose the lucky stakeholder which takes (say) 3 minute to calculate. Now, if an attacker who has 10% of the total stake tries to re-solve the 5th block in order to derive himself as the winning stakeholder, then he will need 30 extra minutes on average. So if the block time is 2.5 minutes, we're good.

Edit: even though the 99% attacker is 100 times faster than the honest hashpower, the fact that the scrypt derivation function is sequential means that he wouldn't have advantage over an honest miner who solves the block, so the penalty for the honest network when the lucky stakeholder is absent would also be (say) 3 minutes, which is good. However, there is a huge problem here, because nodes will have to spend 3 minutes to verify each stakeholders block. So if a new user download the blockchain (with e.g. 250,000 blocks) for the first time, it will take him weeks to verify it. So this is another reason why the advance notice and derving the winning stakeholder from the last several blocks is useful, unless we find a way around this problem.

[cunicula]

In order to deal with an attacker who has 99% hashpower, we can have scrypt based derivation function to choose the lucky stakeholder which takes (say) 3 minute to calculate.
Edit: even though the 99% attacker is 100 times faster than the honest hashpower, the fact that the scrypt derivation function is sequential means that he wouldn't have advantage over an honest miner who solves the block, so the penalty for the honest network when the lucky stakeholder is absent would also be (say) 3 minutes, which is good. However, there is a huge problem here, because nodes will have to spend 3 minutes to verify each stakeholders block. So if a new user download the blockchain (with e.g. 250,000 blocks) for the first time, it will take him weeks to verify it. So this is another reason why the advance notice and derving the winning stakeholder from the last several blocks is useful, unless we find a way around this problem.

I feel like you are trying to address an imaginary problem. Why not just have people continuously try to find and broadcast new block candidates until one of these block candidates gets signed and can be built upon? This is like how PoW mining operates currently except there is an additional hurdle to meet before you move on to mining the next block. Why wouldn't this work?

What concern are you trying to address with the special scrypt function (i.e. I don't see why it would be helpful)?

[The above questions are all basically the same, but I am rephrasing them in case one of the versions is easier to understand than the others.]

[iddo]

I feel like you are trying to address an imaginary problem. Why not just have people continuously try to find and broadcast new block candidates until one of these block candidates gets signed and can be built upon? This is like how PoW mining operates currently except there is an additional hurdle to meet before you move on to mining the next block. Why wouldn't this work?

If an attacker (who wishes to generate empty blocks) with 99% hashpower and 10% of the total stake isn't imaginary, then this problem isn't imaginary. This attacker can generate 99 PoW blocks while the honest network generates 1 PoW block during the same time. If the identity of the lucky stakeholder is derived just from the last single PoW block, then this attacker can afford to do 99 attempts at deriving himself as the lucky stakeholder, and having 10% stake implies that he only needs 10 attempts on average. In other words, an attacker with 99% hashpower and 1% stake could destroy the network.

Suppose we go by my suggestion of deriving the identity of the winning stakeholder from the last (say) 30 blocks by doing something like deriving a pseudorandom index j between 1 and 30 from each of the last 29 blocks and flipping the jth bit and hashing the final result. An attacker with 10% stake could get 16 attempts to derive himself by generating different derived bits for the last 4 blocks in secret, meaning that he will need to generate 30 blocks in secret (full binary tree of depth 4 without the root). Here simple-PoA can help, e.g. with 5-fold and 50% stakeholders' participation, because the attacker would need to generate 30 secret blocks to gain weight=4, while the honest network gains weight=1+1+5+5=12 when it generates 4 blocks. If we're generous and say the attacker with 10% stake gains 1 PoA signature when he generates 8 blocks, he'll still need to generate 60 blocks to gain weight=1+1+1+1+1+1+1+5=12, so he has to be 60/4=15 times faster than the honest network, meaning that he has 93.75% of the total hashpower. I'm assuming that the stakeholders won't provide their PoA signatures for empty blocks, because there's no reward there. Does that sound good?

Edit: actually that doesn't sound so good, even when deriving the identity just from the last block, an attacker with 10% stake needs 91% of the total hashpower.

Any better ideas on how to do empty blocks security via lottery, or via other methods?

[cunicula]

I think you are referring to the DoS problem, where the attacker can submit empty blocks. You could also be referring to the double-spending problem.

It doesn't matter. In either case, there are two simple options. Please pick an option. If you do not like either option, please explain why.

Denial of Service:

a) accept that an attacker with 91% of hashing power and 10% of stake will succeed [this is fine with me, but I prefer b]
b) select n random stakeholders who will mine mandatory blocks in sequence. Say n=3. These blocks can be mined immediately. Then our hypothetical 10% stake attacker would need to mine 1,000 blocks before he could draw his own stake three times in a row. Thus he would need 99.9% of hashing power to deny service, rather than just 91%.


Double-Spending:

a) accept that an attacker with 91% of hashing power and 10% of stake will succeed [this is fine with me, but I prefer b]
b) select n random stakeholders to sign each block. Say n=3. Then our hypothetical 10% stake attacker would need to mine 1,000 blocks before he could draw his own stake three times in a row. Thus he would need 99.9% of hashing power to double-spend, rather than just 91%.

Note: When I say 10% stake, I am referring to 10% of participating stake, which is likely less than 10% of total stake.

[iddo]

Denial of Service:

b) select n random stakeholders who will mine mandatory blocks in sequence. Say n=3. These blocks can be mined immediately. Then our hypothetical 10% stake attacker would need to mine 1,000 blocks before he could draw his own stake three times in a row. Thus he would need 99.9% of hashing power to deny service, rather than just 91%.

Interesting.
The first thing that springs to mind is that the 3 lucky stakeholders could collude with malicious miners to carry out double-spending, but we can easily take care of that by giving weight=0 to a stakeholders block (with weight=1 the safe double-spending length would decrease from 6 to 3 when the 3 stakeholders are corrupt, or maybe you'd refer to them as rational).
Another issue is that we might have to limit the txn-fees reward of each of the 3 consecutive stakeholders blocks to 1/3 of the average reward, otherwise the two latter stakeholders will sit idle and wait to collect txn-fees (assuming that monetary inflation has ended).
This idea would probably be more sensitive to the stakeholders' participation. With 50% participation, it will take 8 PoW solutions until the 3 consecutive stakeholders blocks will be created. So the performance of the network degrades, in particular in terms of double-spending security if weight=0 is used. How much degradation depends on the gap until the next stakeholders blocks.

Maybe n=2 would make more sense than n=3. I wonder if some of the parameters that we discuss should be dynamically adjusted by the protocol, but for this n=3 parameter we probably cannot adjust by detecting empty blocks, because the attacker could generate almost empty blocks etc.

Double-Spending:

a) accept that an attacker with 91% of hashing power and 10% of stake will succeed [this is fine with me, but I prefer b]
b) select n random stakeholders to sign each block. Say n=3. Then our hypothetical 10% stake attacker would need to mine 1,000 blocks before he could draw his own stake three times in a row. Thus he would need 99.9% of hashing power to double-spend, rather than just 91%.

Are you talking about the derived stakeholders for simple-PoA signatures, or the stakeholders who were derived to create a stakeholders block? Not sure what kind of double-spending attack you have in mind. The purpose of simple-PoA is to reduce the risk of double-spending, and with weight=0 the stakeholders blocks become neutral to double-spending attacks, so they just degrade the network performance.

[cunicula]

This idea would probably be more sensitive to the stakeholders' participation. With 50% participation, it will take 8 PoW solutions until the 3 consecutive stakeholders blocks will be created. So the performance of the network degrades, in particular in terms of double-spending security if weight=0 is used. How much degradation depends on the gap until the next stakeholders blocks.

Gradual degradation of network performance can be resolved by removing inactive public keys from the lottery list. We can talk about this once we have the block mining order and signature requirements fixed.

So the performance of the network degrades, in particular in terms of double-spending security if weight=0 is used. How much degradation depends on the gap until the next stakeholders blocks.

I'm not sure what you mean by weight. The key characteristic of these blocks is that they are mandatory and occur at deterministic intervals.

I feel like we should ignore any possibility for collusion right now and maybe revisit it later. In any consensus system, there are so many ways people can collude that it is very difficult to defend against. The best defense is probably just a) ensuring that collusion requires cooperation from many different people, and b) ensuring that the set of people is difficult to predict beforehand.

Maybe n=2 would make more sense than n=3.

I would prefer n=3.

Are you talking about the derived stakeholders for simple-PoA signatures, or the stakeholders who were derived to create a stakeholders block? Not sure what kind of double-spending attack you have in mind. The purpose of simple-PoA is to reduce the risk of double-spending, and with weight=0 the stakeholders blocks become neutral to double-spending attacks, so they just degrade the network performance.

Okay, let me review this to see if we are communicating. I'm only trying to describe the block ordering and not rewards etc. We should tentatively agree on the block ordering if possible.

Block 1: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 1 and block 5c.
Block 3: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 2 and block 6.
Block 4: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 3 and block 7.
Block 5: PoW Block is mined, 3 random stakeholders are drawn.
Block 5a: Random stakeholder block 1
Block 5b: Random stakeholder block 2
Block 5c: Random stakeholder block 3
Block 6: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 6 and block 10c.
...
Block 10: PoW Block is mined, 3 random stakeholders are drawn.
Block 10a: Random stakeholder block 1
Block 10b: Random stakeholder block 2
Block 10c: Random stakeholder block 3
...

Say the blocks have a 2.5 minute interval on average, so a full sequence 1-5 occurs about once every 15 minutes. The stakeholder blocks would appear almost instantly since they don't require work.

Is that correct? I think it would work fine this way.

[iddo]

I'm not sure what you mean by weight.

I meant the weight for deciding the winning branch among competing branches. It'd be weight=1 for unsigned regular PoW blocks, (say) weight=5 for signed PoW blocks via simple-PoA, and weight=0 for stakeholders blocks. The branch with the highest weight wins. Also, because the PoW block the precedes and derives the stakeholders blocks is significantly more reversible than other PoW blocks, it should also have weight=0 until all of the consecutive stakeholders blocks were created (so it'd be weight=1 or weight=5 for the batch that consists of this PoW block together with the consecutive stakeholders blocks that follow it).

In other words, we wouldn't rely on blocks that the stakeholders create in order to provide double-spending security. Or maybe we could somewhat rely on stakeholders blocks by giving them some weight, if the security analysis of the various possible scenarios would make sense. This would be similar to the situation we have with ABAB, where the type-A PoW blocks provide double-spending security, and the type-B stakeholders blocks provide empty-blocks-DoS security.

BTW regarding ABAB, post #68 was probably a bit too optimistic. If the attacker waits (say) several weeks so that he could generate (say) 3 type-B blocks much faster than the active stakeholders, then even if he has less than 50% hashpower he could outcompete the honest network by generating the 3 interleaved type-A blocks a little slower than the honest network, but overall his secret branch of 3+3 blocks wil be generated faster than 6 blocks of the honest network. We should have more exact analysis, but it seems to make sense that an attacker with less than 50% hashpower could double-spend if he waits for enough coin-confirms before he starts the attack.

Block 1: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 1 and block 5c.
Block 3: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 2 and block 6.
Block 4: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 3 and block 7.
Block 5: PoW Block is mined, 3 random stakeholders are drawn.
Block 5a: Random stakeholder block 1
Block 5b: Random stakeholder block 2
Block 5c: Random stakeholder block 3
Block 6: PoW Block is mined, random stakeholder is drawn. This random stakeholder is able to deliver an optional signature any time between block 6 and block 10c.
...
Block 10: PoW Block is mined, 3 random stakeholders are drawn.
Block 10a: Random stakeholder block 1
Block 10b: Random stakeholder block 2
Block 10c: Random stakeholder block 3
...

Yes, this appears to be fine. But the particular variables should be considered. For simple-PoA signatures, the protocol could specify for example that you're allowed to provide your signature in the next x blocks, where x>6 is disallowed, initially x=3, and at the difficulty re-adjustment we do x=x-1 or x=x+1 depending on whether there was at least 50% stakeholders' participation in the last retarget window.

Deciding the gap between stakeholders blocks (the gap between 5a,5b,5c and 10a,10b,10c) seems to be more problematic. Ideally, I wish that we could devise some protocol rule so that in the default state the empty-blocks security is disabled (i.e. blocks 5a,5b,5c won't be created), and at the difficulty re-adjustment we detect whether empty-blocks security should be enabled for the next retarget window, maybe by looking at the coin-age that was used in the last retarget window relative to the retarget window before it (so for example coins that were created during the last retarget window will be insignificant). But could the attacker exploit this kind of protocol rule to deny service while keeping the empty-blocks security disabled, by transferring his own stake between addresses that he controls? If we cannot enable/disable, then maybe we could re-adjust the gap. If that's also insecure, then we'd have to picky some constant gap, probably higher than 5 if there'd be 3 consecutive stakeholders blocks.

I'm worried about the rewards that the stakeholders should collect. The stakeholders provide a useful function for the security of the network, so they probably should receive some reward, in particular if they take a risk by using unencrypted wallet or limited-withdrawal wallet. But it's arguable, we could claim that the stakeholders have an interest to protect their stake by keeping the network secure, so maybe it's appropriate that they receive little or no reward. This is also related to whether the reward should be determined by the free-market with stakeholders-fees, or enforced by the protocol so that the security would be more predictable. The issue the worries me is that if for example the simple-PoA fee is 10% of the block reward, and with 3 consecutive stakeholders blocks this 10% figure becomes even higher, then we can take some extreme scenario where a stakeholder who has 10% of the total stake doesn't spend his coins and waits until the other 90% spend their coins to collect 1/10 of that 90% so now he'd have close to 20% stake, then wait again until the 80% spend their coins to collect 2/10 of the 80% so he'd now have about 35% of the total stake, etc.

[cunicula]

I meant the weight for deciding the winning branch among competing branches. It'd be weight=1 for unsigned regular PoW blocks, (say) weight=5 for signed PoW blocks via simple-PoA, and weight=0 for stakeholders blocks. The branch with the highest weight wins. Also, because the PoW block the precedes and derives the stakeholders blocks is significantly more reversible than other PoW blocks, it should also have weight=0 until all of the consecutive stakeholders blocks were created (so it'd be weight=1 or weight=5 for the batch that consists of this PoW block together with the consecutive stakeholders blocks that follow it).

In other words, we wouldn't rely on blocks that the stakeholders create in order to provide double-spending security. Or maybe we could somewhat rely on stakeholders blocks by giving them some weight, if the security analysis of the various possible scenarios would make sense. This would be similar to the situation we have with ABAB, where the type-A PoW blocks provide double-spending security, and the type-B stakeholders blocks provide empty-blocks-DoS security.

You cannot "not rely" on the stakeholder generated blocks for double-spend prevention. These are mandatory components of the block chain. If you cannot create them, you cannot double-spend. In fact, these blocks will always be the primary obstacle to double-spending. The weights for mandatory blocks are more or less meaningless. Anything mandatory implicitly has effectively infinite weight. By comparison, voluntary components (whether signatures or blocks) have only a minor impact on double-spending.

I would recommend a weight of 1 for unsigned blocks and a weight of 2 for signed blocks. If you raise the weight to try to make voluntary signatures matter more, you are opening the door to long, unpredictable reorganizations. That is highly undesirable. I see the voluntary signatures as stakeholder heartbeats. Their most important use is providing a record of which stakeholder participation.

BTW regarding ABAB, post #68 was probably a bit too optimistic. If the attacker waits (say) several weeks so that he could generate (say) 3 type-B blocks much faster than the active stakeholders, then even if he has less than 50% hashpower he could outcompete the honest network by generating the 3 interleaved type-A blocks a little slower than the honest network, but overall his secret branch of 3+3 blocks wil be generated faster than 6 blocks of the honest network. We should have more exact analysis, but it seems to make sense that an attacker with less than 50% hashpower could double-spend if he waits for enough coin-confirms before he starts the attack.

Let's just drop my ABAB type blocks. The proof-of-stake blocks are redundant if random stakeholders can generate blocks. Complex nested systems should be avoided (unless they are necessary). Analysis becomes more complex in the nested system.

I'm worried about the rewards that the stakeholders should collect. The stakeholders provide a useful function for the security of the network, so they probably should receive some reward, in particular if they take a risk by using unencrypted wallet or limited-withdrawal wallet. But it's arguable, we could claim that the stakeholders have an interest to protect their stake by keeping the network secure, so maybe it's appropriate that they receive little or no reward. This is also related to whether the reward should be determined by the free-market with stakeholders-fees, or enforced by the protocol so that the security would be more predictable. The issue the worries me is that if for example the simple-PoA fee is 10% of the block reward, and with 3 consecutive stakeholders blocks this 10% figure becomes even higher, then we can take some extreme scenario where a stakeholder who has 10% of the total stake doesn't spend his coins and waits until the other 90% spend their coins to collect 1/10 of that 90% so now he'd have close to 20% stake, then wait again until the 80% spend their coins to collect 2/10 of the 80% so he'd now have about 35% of the total stake, etc.

Let's hold off on this. We need to understand the blockchain structure first. Everything is interrelated, so you cannot usefully analyze one thing at a time without holding other aspects of the system fixed.
Thus we need to fix some things before moving on.

[iddo]

You cannot "not rely" on the stakeholder generated blocks for double-spend prevention.

Let me try to explain what I meant.
Let's disregard PoA signatures and have weight=1 for every PoW block, and assume that after 6 blocks the merchant's client displays some green signal which means that it's safe to assume that the txn from 6 blocks earlier won't be reversed.
Suppose the the chain is: P0 --> S1 --> S2 --> S3 --> P1 --> P2 --> P3 --> P4 --> P5 --> P6
Where P0 is the PoW block that derived the three stakeholders blocks S1,S2,S3, and P1,P2,P3,P4,P5,P6 are regular PoW blocks.
Suppose that S1 is the block that included the txn that's relevant for the merchant.
If S1 has weight=1 and S2 has weight=1 and S3 has weight=1, then the merchant's client will display the green signal when it sees that the block P3 was generated, and then the merchant will send the merchandise to the double-spending attacker. Now, in order to reverse the txn, if the attacker controls (or colludes with) the stakeholders S1,S2,S3 then he could have prepared his secret branch by instantly generating 3 new blocks S1*,S2*,S3* that don't include the relvenat txn, and then use his hashpower to generate only 3 PoW blocks P1*,P2*,P3*, instead of having to generate 6 PoW blocks. So the attacker only needs to generate 3 PoW blocks to outcompete the honest branch, if he bribes the malicious/rational stakeholders to collude with him.
However, if we have weight=0 for the blocks S1,S2,S3, then the merchant's client will display the green signal only after seeing that P6 was generated, and we're good.
Does this make sense?

[cunicula]

You cannot "not rely" on the stakeholder generated blocks for double-spend prevention.

Let me try to explain what I meant.
Let's disregard PoA signatures and have weight=1 for every PoW block, and assume that after 6 blocks the merchant's client displays some green signal which means that it's safe to assume that the txn from 6 blocks earlier won't be reversed.
Suppose the the chain is: P0 --> S1 --> S2 --> S3 --> P1 --> P2 --> P3 --> P4 --> P5 --> P6
Where P0 is the PoW block that derived the three stakeholders blocks S1,S2,S3, and P1,P2,P3,P4,P5,P6 are regular PoW blocks.
Suppose that S1 is the block that included the txn that's relevant for the merchant.
If S1 has weight=1 and S2 has weight=1 and S3 has weight=1, then the merchant's client will display the green signal when it sees that the block P3 was generated, and then the merchant will send the merchandise to the double-spending attacker. Now, in order to reverse the txn, if the attacker controls (or colludes with) the stakeholders S1,S2,S3 then he could have prepared his secret branch by instantly generating 3 new blocks S1*,S2*,S3* that don't include the relvenat txn, and then use his hashpower to generate only 3 PoW blocks P1*,P2*,P3*, instead of having to generate 6 PoW blocks. So the attacker only needs to generate 3 PoW blocks to outcompete the honest branch, if he bribes the malicious/rational stakeholders to collude with him.
However, if we have weight=0 for the blocks S1,S2,S3, then the merchant's client will display the green signal only after seeing that P6 was generated, and we're good.
Does this make sense?

I don't think that P6 is the appropriate time to send the green signal. I believe you should wait for 2 full cycles of stake blocks to be completed before sending the green signal.

P0 --> S1 --> S2 --> S3 --> P1 --> P2 --> P3 --> P4 --> P5 --> S4 --> S5 --> S6 --> P6--> P7 --> P8 --> P9 --> P10 --> S7 --> S8 --> S9 --> P11

If the txn enters at S1, then I think you should wait to give the green signal until after P11 is found. That is after 11 PoW blocks. If each PoW block comes at 2.5 minute intervals on average and the stake blocks are very fast (say 20 seconds each), this is a total time of about 30 minutes.

[iddo]

Hello cunicula,
I'm not sure if you noticed it, but your last post raises a very interesting option. If the gap between stakeholders blocks is short (say 5 as in the example), then maybe we don't need simple-PoA at all, meaning that we don't need to derive lucky stakeholders who would provide their signature for an earlier PoW block. Instead, using lottery to derive lucky stakeholders who create blocks on their own, we get double-spending security (because the gap is short and therefore merchant can wait until the stakeholders act) and empty-blocks security.

Let's consider your example with an attacker who wishes to double-spend and has 99% hashpower and 10% stake. If he wishes to reverse the txn that entered S1, then he would need stakeholders S1,S2,S3,S4*,S5*,S6*,S7*,S8*,S9* to collude with him until his secret branch would reach P11. If the merchant's client listens and tries to detect double-spending attempts, then this collusion has to kept secret. In other words, the attacker's double-spending service couldn't be public, otherwise the merchat's client would also connect to the attacker's service and detect the double-spending attempt. This means that the attacker has to re-solve P5 about 1000 times on average (assuming that he controls 10% of the total stake), while the honest network with (say) 50% stakeholders' participation only needs 2^3=8 attempts on average, where each attempt is 99 times slower than the attacker's, so effectively less than 800 attempts. Same is true for P10, and the attacker would probably also need to re-solve P0.
What do you think?

[cunicula]

Hello cunicula,
I'm not sure if you noticed it, but your last post raises a very interesting option. If the gap between stakeholders blocks is short (say 5 as in the example), then maybe we don't need simple-PoA at all, meaning that we don't need to derive lucky stakeholders who would provide their signature for an earlier PoW block. Instead, using lottery to derive lucky stakeholders who create blocks on their own, we get double-spending security (because the gap is short and therefore merchant can wait until the stakeholders act) and empty-blocks security.

I did notice this and I agree completely. To me the most elegant solution is just to generate one PoW block and then have 3 random stakeholders generate blocks, i.e.

P0-S01-S02-S03-P1-S11-S12-S13-P2-...

Comparison of chains could be based purely on the sum of all blocks PoW difficulty, just as in bitcoin.  

However, voluntary signatures still have a strong use case. There could just be one voluntary signature per PoW block. The signatures would be valid if they are submitted up to say 20 PoW blocks after the voluntary signatory is selected. These signatures do not need to be directly rewarded and they do not need to influence chain selection in any way. Instead, the voluntary signatures would provide 'heartbeats' permanently recording stakeholders who failed to keep their stake online. Providing a heartbeat makes you eligible to win the lottery. It is kind of like a lottery ticket (except you can't have more than one). If you fail to provide a heartbeat, you lose your lottery ticket until you indicate 'resurrection' by moving your coins to a new address.

Heartbeats are useful for the following reasons:

Problem:  data transmission could get unmanageable if participation levels are too low.
With 100% participation every block meeting the difficulty target will be built on using three stake blocks and therefore enter the blockchain. With full participation, the data transmission is not significantly larger than bitcoin, litecoin etc.
With 50% participation, one out of every 1/(0.5^3)=8 blocks meeting the difficulty target will be built on. This is considerably more data transmission, but it should be easily manageable.
With 10% participation, one out of every 1/(0.1^3)=1000 blocks meeting the difficulty target will be built on. If we are talking about blocks up to 1 MB, that is 1 GB of data passing through the network every time a PoW block is mined. That seems like much too much and we should do something about this.

How Heartbeats help:
1) If someone fails to provide a heartbeat, we can guess that they are frequently not online. I call these guys 'dead' stakeholders. It is wasteful to transmit blocks that identify 'dead' stakeholders as block constructors. 'dead' stakeholders would burden the system. Therefore, blocks that map to 'dead' stakeholders should be invalid. Such invalid blocks would not need to be passed around from peer to peer. This means that, at least in the long-run, data transmission requirements would not be affected by participation levels. If only 10% of people participated, then only 1 out of 1000 blocks would be potentially valid. However, the 999 out of 1000 blocks could be immediately discarded. In effect difficulty would be 1000 times higher than the recorded value. The invalid blocks mapping to dead people would not need to be passed from peer to peer.
2) 'Dead' stakeholders could be a source of fees. The details are not that important here. I'll defer description of fee collection until later.
2a) One very cool thing about extracting fees from the 'dead' is that it increases the motivation to stay active. If participation fell, then the amount revenue collected from the 'dead' would grow. This would increase rewards from participation. This creates a negative feedback cycle stabilizing participation.
2b) Another cool thing about grabbing fees from the dead is that it provides a noninflationary and demand-sensitive source of revenue. If 100% of people are participating, then there is nothing to collect from the 'dead'. That is good. If 100% of people are participating there is no need to reward participation. It doesn't make sense to issue significant fees to stakeholders if stakeholders are willing to work for free. The PoW guys still need some money of course, but we can postpone how to pay them till later.

[iddo]

P0-S01-S02-S03-P1-S11-S12-S13-P2-...

Maybe, this maximizes the reliance on stakeholders. Obviously we cannot be even more extreme and ditch the PoW blocks completely, because then lucky stakeholders attempts will be derived at blazing speeds with no difficulty adjustments (and no good way to mint coins, because I think that only PoW blocks should get newly minted coins). If the reliance on stakeholders is so frequent, then it might involve an exccesive amount of fees that go to stakeholders. Maybe your previous suggestion of 5 consecutive PoW blocks makes more sense, we need a more clean understanding of the pros/cons of doing that.

Also, if we compare timestamps at the boundaries of the difficulty retarget window, then the time difference would be affect both by total hashpower flucuation, and stakeholder's participation level. This might be another reason why having (say) 5 consecutive PoW blocks is useful, because now we can distinguish between regular PoW blocks and PoW blocks that derive stakeholders, and deduce the PoW difficulty and the stakeholder's participation level separately from each other.

I wonder what'd the best way to devise an incentives structure that keeps the stakeholders' participation above some threshold (say 50% participation). We could split the newly minted coins of the PoW blocks with stakeholders blocks when we're below the threshold, but this doesn't specify what to do when block reward is based entirely on fees, assuming finite monetary inflation. Without a convincing incentives structure, mandatory lottery blocks would be a hard sell, meaning that people might be afraid that their txn will get stuck because of inactive stakeholders. From a purely theoretical perspective the situation isn't really different than pure-PoW, i.e. with pure-PoW their txn can also get stuck if all the miners are extremely unlucky and don't generate a block that meets the current difficulty, and similarly if we assume that stakeholders' participation is always above some threshold (because there's a re-adjusting incentive for stakeholders to participate), then deriving active stakeholders is similar to generating a regular PoW block.
Any other ideas on how to create incentives that keep stakeholders participation above some predictable threshold?

With 10% participation, one out of every 1/(0.1^3)=1000 blocks meeting the difficulty target will be built on. If we are talking about blocks up to 1 MB, that is 1 GB of data passing through the network every time a PoW block is mined. That seems like much too much and we should do something about this.

You don't need to transfer 1 MB blocks before it's evident that the 3 consecutive stakeholders are active. The protocol can say that the 1st stakeholder creates S01 and broadcasts h01 and sgn01=sign(hash(PO)|h01), then the 2nd stakeholder creates S02 and broadcasts h02 and sgn02=sign(h01|h02), the the 3rd stakeholder creates S03 and broadcasts h03 and sgn03=sign(h02|h03), and then the miners wait until the blocks S01,S02,S03 themselves are sent by the stakeholders and verify that h01=hash(S01),h02=hash(S02),h03=hash(S03), and now the chain can become P0-->(S01,sgn01)-->(S01,sgn02)-->(S03,sgn03)-->P1, where the P1 block includes h03, and so on.


About heartbeats, I agree that the features that you describe could be highly beneficial, but how would the nodes manage the list of dead stakeholders? I'm worried that this idea would be way too complex in practice, could you please describe the most simple implementation that you can think of?

[cunicula]

Maybe, this maximizes the reliance on stakeholders. Obviously we cannot be even more extreme and ditch the PoW blocks completely, because then lucky stakeholders attempts will be derived at blazing speeds with no difficulty adjustments (and no good way to mint coins, because I think that only PoW blocks should get newly minted coins). If the reliance on stakeholders is so frequent, then it might involve an exccesive amount of fees that go to stakeholders. Maybe your previous suggestion of 5 consecutive PoW blocks makes more sense, we need a more clean understanding of the pros/cons of doing that.

[begin tirade]
My ideal is to ditch PoW completely, but I don't know how so I accept PoW as a necessity. There needs to be a hard to manipulate random number seed. I don't know how to create this without PoW. I am also fine with PoW miners getting all of the block subsidy. The initial distribution needs to be diverse and PoW with scrypt accomplishes this. I feel that initial distribution should be greatly accelerated (for example 100% completed in 1 year's time). I am very much opposed to PoW miners receiving a large share of txn fees. I think they should get no more than 20%. The long-run efficiency of the system depends on minimizing the use of PoW to the fullest extent possible. PoW miners are parasites. They take out of the pockets of legitimate users and use it to pay for electricity and electronics. There is no point in overpaying them. Cryptocurrency was not created to subsidize Exxon, PG&E, and AMD. If you pay money to PoS miners you add value to the currency. If you pay that money to PoW miners, you destroy the same value. There is no point in destroying wealth unnecessarily. I think once people realize that they can earn txn fees just by investing and then leaving their computers on they will quickly realize that PoW was a horrible idea. In any case, if it turns out that you paid PoW guys too much, then someone can just modify the code and pay them less. The new currency will have lower effective txn fees and therefore be better all around. We should not leave space open for competitors to do this.
[/end tirade]

As far as block structure goes, I don't care much. I am fine with the either structure. Let's just go with regular PoW blocks and PoW -> lottery draw blocks.

Downside: With two block types, you need to wait for type B blocks to be found before you are safe from double-spends. The type A blocks just provide bitcoin-level security. Thus, if you have a large number of type A blocks before every type B block, then you have to wait longer.

Upside: Since the stake blocks are minted immediately, many of these blocks are likely to be empty or nearly empty. This is wasted space. Type A blocks are more efficient as far as storage and bandwidth requirements. I think 4A1B is a reasonable balance. By 4A1B, I mean P01-P02-P03-P04-P05-S05a-S05b-S05c-P06-P07-P08-P09-P10-S10a-S10b-S10c... The type B blocks P05 and P10 will take longer to mine than the type A blocks P01-P04 and P06-P09. To avoid this, there should probably be two difficulty levels (one for each block type). Chain validity should be determined by aggregate difficulty for type B blocks. Aggregate difficulty for type A blocks should only be consulted as a tie-breaker.

Also, if we compare timestamps at the boundaries of the difficulty retarget window, then the time difference could be affect either by total hashpower flucuation, or stakeholder's participation level. This might be another reason why having (say) 5 consecutive PoW blocks is useful, because now we can distinguish between regular PoW blocks and PoW blocks that derive stakeholders, and deduce the PoW difficulty and the stakeholder's participation level separately from each other.

Stakeholder participation would be measured directly via heartbeats. If you offer a heartbeat, it is safe to assume that you are willing to mine blocks using your stake.
You can also measure it using difficulty like you say. However, this measurement will not tell you who is responsible for low participation. It does not provide a mechanism to punish people for
low participation.

Any other ideas on how to create incentives that keep stakeholders participation above some predictable threshold?

I elaborate on my idea below after I describe heartbeats.

You don't need to transfer 1 MB blocks before it's evident that the 3 consecutive stakeholders are active. The protocol can say that the 1st stakeholder creates S01 and broadcasts h01 and sgn01=sign(hash(PO)|h01), then the 2nd stakeholder creates S02 and broadcasts h02 and sgn02=sign(h01|h02), the the 3rd stakeholder creates S03 and broadcasts h03 and sgn03=sign(h02|h03), and then the miners wait until the blocks S01,S02,S03 themselves are sent by the stakeholders and verify that h01=hash(S01),h02=hash(S02),h03=hash(S03), and now the chain can become P0-->(S01,sgn01)-->(S01,sgn02)-->(S03,sgn03)-->P1, where the P1 block includes h03, and so on.

Right, this is a good idea. The issue still applies though (# of messages blows up as participation approaches 0).

About heartbeats, I agree that the features that you describe could be highly beneficial, but how would the nodes manage the list of dead stakeholders? I'm worried that this idea would be way too complex in practice, could you please describe the most simple implementation that you can think of?
[/quote]
I think you need a database to implement a lottery. As I see it, this is just a minor addition to this database.
To construct the lottery, I think you need an ordered list of all public keys and their current balances.
Each client constructs this from the blockchain during the initial verificatoin. Then the database is updated every time a block is mined or orphaned.

Suppose this is our lottery database

Public Key       Linked Stake Public key         Balance  Cumulative Balance
A                             As                              1                1
B                             Bs                             2.5             3.5
C                             Cs                              3              6.5

The lottery draw would map to a uniform distribution on the support (0,6.5). Let x be the realization of the draw. If 6.5>x>=3.5, indicates C; 3.5>x>=1 indicates B; 1>x>0 indicates A.
Signatures can be provided either

  
To incorporate hearbeats, we just add a different column. Heartbeat? 1 = Yes , 0 = No. By default, every address that is in the blockchain has a heartbeat. As you make the database,
you record public keys that failed to provide voluntary heartbeats. These public keys lose their heartbeats forever. To show this, the heartbeat indicator switches from 1 to 0.

Public Key       Linked Stake Public key         Balance  Cumulative Balance  Heartbeat?
A                             As                              1                1                        1
B                             Bs                             2.5             3.5                        0
C                             Cs                              3              6.5                        1

Now 3.5>x>=1 indicates an invalid block. B is simply not allowed to mint any stake blocks.

The final thing that I want incorporated in the database is coin-age. Coin-age is used to calculate fees. Since PoW miners need to be paid regardless of participation, I think everyone should have to pay these fees. Coin-age is the weighted average age on coins held by a public key. It can be measured in blocks, but conversion to years is more intuitive. (e.g. if I received 10 coins 2 year ago and they haven't moved and if I received 10 coins 1 year ago and they haven't moved, then coin-age is 1.5 years. If coins have been sent or a block has been mined, coin age is reset to 0.)

Again, this can be updated everytime a block is mined.
If no send, Coin-age_t = Coin-age_t-1 + 1.
If send, Coin_age_t = 1.
If send and receipt of coins, Coin_age_t = 1.
If receipt of coins but no send, Coin_age_t = [Coin_age_(t-1)*balance_(t-1)+received coins]/balance(t)

Public Key       Linked Stake Public key         Balance  Cumulative Balance  Heartbeat?         Coin-age (really measured in blocks but years are more intuitive here)
A                             As                              1                1                        1               0.03 years
B                             Bs                             2.5             3.5                        0               0.1 years
C                             Cs                              3              6.5                        1               0.2 years

As far as fees go, my proposal is simply to make them an increasing function of coin age. You essentially pay an annual 5% tax on your balance, which is forgiven if you participate.
Mandatory Fee =  0.05 * balance * (Coin-age in years) / 1 year. )

This can be derived from other information in the chart. It is not necessary to put in the database.

Public Key       Linked Stake Public key         Balance  Cumulative Balance  Heartbeat?         Coin-age          Mandatory fee
A                             As                              1                1                        1               0.03 years              0.015
B                             Bs                             2.5             3.5                        0               0.1 years               0.0125
C                             Cs                              3              6.5                        1               0.2 years               0.03

There are two incentives to participate:
1) If you participate, then your mandatory fee will be reset to 0 every time you mine a block. Thus participation allows you to avoid txn fees.
2) If you participate, then you will get a share of the fees from people who don't participate. Thus participation allows you to accumulate coins.

Let's neglect the rewards for PoW miners (who will share in the fees) and think about stakeholder incentives:

Say you have 1 coin and 90% of people participate. Participants will accumulate 5% of the balances from the other 10% of stakeholders each year.
In other words, if you participate with 1 coin that 1 coin will have an expected value of 1.0055 coins after 1 year. If you do not participate, you will have 1 coin and will need to pay a fee of 0.05 coins to use that coin, so you effectively have 0.95 coins. This is a much smaller incentive. But a small incentive is adequate if the participation rate is high.

Say you have 1 coin and only 10% of people participate. The 10% of participants will accumulate 5% of the balances from the other 90% of stakeholders each year.
If you participate, in one year, you will expect 1.45 coins. If you do not participate, you will effectively have 0.95 coins. This is a big incentive. But such an incentive is needed to keep participation from dropping too low.

Say you have 1 coin and only 1% of people participate. The 1% of participants will accumulate 5% of the balances from the other 99% of stakeholders each year.
If you participate, in one year, you will expect 5.95 coins. If you do not participate, you will effectively have 0.95 coins. This is a tremendous incentive. It is like a pirate style scheme (3% interest/week)!
But such huge incentives are needed to guarantee a minimum level of participation.

Additionally, heartbeats provide a disincentive to mine attack chains. You will not want to accept a chain where you don't have your heartbeat recorded.

Participation should also be kept safe. Safe participation effectively keeps txn fees low. However, let's discuss the above first, before moving on to discussion of the Linked Stake Public Keys.

[iddo]

My intuition still says that heartbeats/blacklisting addresses is infeasible. I'll be happy to learn that I'm wrong if you or someone else could convince me otherwise, because the features that you describe would be great to have. Suppose you need one database entry per satoshi. This entry specifies the pubkey that controls this satoshi, and the rest of the data that you mentioned. With 2,100,000,000,000,000 satoshis, if each entry occupied 1 byte, then the size of the database can be about 1910 terabytes. If each entry holds two pubkeys and other information, the total database size is say 1000 times bigger. If it's Litecoin instead of Bitcoin, then it's 4 times bigger on top of that. All the nodes that verify the blockchain need to be able to derive this database in an unambiguous way. With the blockchain we have txn-fees that restrain the total size by discouraging too much fragmentation. With such a database it isn't even clear if having one entry per satoshi is enough, or maybe we need 2^160 entries (=addresses) or 2^256 entries (=pubkeys). These worst-case numbers could be exploited by attackers who wish to bloat the database. The operations that this database (or another data structure) need to support include (1) if optional winning address which was derived via follow-the-satoshi didn't provide the heartbeat then you have to discover all the other satoshis that are controlled by this address and mark them as blacklisted in the database, and (2) whenever someone transfers his coins to a blacklisted address we should blacklist those newly transferred coins too. So I wonder if we could have some data structure with which these operations would be feasible. I admit that I haven't fully thought it through yet, but it seems infeasible to me.

Additionally, heartbeats provide a disincentive to mine attack chains. You will not want to accept a chain where you don't have your heartbeat recorded.

Could you elaborate? If it's a double-spending attacker who creates a short competing branch, then there's a negligible probability that his branch will include your address without heartbeat (you couldn't provide heartbeat because his branch was secret), so when his branch goes public w.h.p. you're not affected by the heartbeats feature.


Regarding the 3 consecutive stakeholders blocks, I think that we should regard it as a single block that is being prepared by 3 different stakeholders, and those 3 stakeholders split the reward equally. Using the same terminology of post #135, the block S02 should actually be an extension of S01, something like S02=S01|sgn01|additional_txns_collected_by_the_2nd_stakeholder, and still have sgn02=sign(h01|h02) and so on. Maybe in the interest of simplicity only the 1st stakeholder should collect the txns, because probably there won't be many new txns to be collected by the 2nd and 3rd stakeholders anyway.

If we cannot blacklist address, then I think that the main issue that we should analyse is the incentive structure for stakeholders. Maybe it makes sense to go with optional fees that are set by the free market, and have a protocol rule that disallows the total fees reward for the stakeholders block to be too high, relative to the average miners fees reward according to the last difficulty retarget window. This way the stakeholders couldn't demand too high fees to further enrich themselves at the expense of non-stakeholders? The honest client should also calculate and set the minimal recommended fee as the default fee, and this fee should be the same whether the txn was included by miners or by stakeholders, I think?

Edit: Apologies that I haven't noticed your new thread (link) and wiki updates. I only looked briefly right now. I see that you switched from 3 to 5 lucky stakeholders, which gives better security but worse performance if it'd be more difficult to find 5 active stakeholders (which puts upward pressure on the reward for stakeholders). I'll try to read everything later, but if you'd like to focus on some particular new aspects that you've raised then please let me know.

[cunicula]

My intuition still says that heartbeats/blacklisting addresses is infeasible. I'll be happy to learn that I'm wrong if you or someone else could convince me otherwise, because the features that you describe would be great to have. Suppose you need one database entry per satoshi. This entry specifies the pubkey that controls this satoshi, and the rest of the data that you mentioned. With 2,100,000,000,000,000 satoshis, if each entry occupied 1 byte, then the size of the database can be about 1910 terabytes. If each entry holds two pubkeys and other information, the total database size is say 1000 times bigger. If it's Litecoin instead of Bitcoin, then it's 4 times bigger on top of that. All the nodes that verify the blockchain need to be able to derive this database in an unambiguous way. With the blockchain we have txn-fees that restrain the total size by discouraging too much fragmentation.

Good point, but I definitely don't think we should give up on blacklisting. It has very nice properties.

Bitcoin tries to decentralize too much. It is not practical to have individual public keys holding pennies. The prevelance of tiny inputs substantially bloats the bitcoin blockchain. Public keys with pennies should be discouraged.

My suggestion is to tax small inputs. Treat them as dead by default. Say we limit lottery eligibility to public keys containing 1 full coin. Then only public keys holding 1 coin or more need to go in the database. A 1 byte entry takes up 20 MB max and the total database takes up 20 Gigabytes max. That seems manageable.

If you have more than 1 coin, you get can get all your coins in the database by consolidating inputs into one public key. If you have less than 1 coin, then you win the lottery about once every 2 years. People with very small holdings should store their money in online wallets. The online wallets can hold money in larger accounts. These online wallets can offer interest to depositors.  

As far as the two linked keys almost doubling blockchain size, this is completely worth it. The theft problem is a really big issue.

Additionally, heartbeats provide a disincentive to mine attack chains. You will not want to accept a chain where you don't have your heartbeat recorded.

Could you elaborate? If it's a double-spending attacker who creates a short competing branch, then there's a negligible probability that his branch will include your address without heartbeat (you couldn't provide heartbeat because his branch was secret), so when his branch goes public w.h.p. you're not affected by the heartbeats feature.

It only works well for long attack chains. However even for a 6 block long attack chain it still could have some functionality. If there are 30 voluntary signatures every 6 blocks, then there may be people rich enough to be included twice. (The largest bitcoin account has over 600k. That is enough to be included twice.)

[iddo]

I don't see how exactly you could store only addresses that hold at least one coin. To pick a uniform-random stakeholder via follow-the-satoshi , we derive one uniform-random satoshi out of all the satoshis that have been minted, and given that the address that controls this satoshi might control at least one coin that's fragmented across many inputs, how would you tell whether the derived satoshi is blacklisted? You could have a cryptocurrency with 21,000,000 coins in total, instead of 2,100,000,000,000,000 coins in total, but that'd be hard to distribute among the entire population and wouldn't be good for micro-payments. If you agree that the total number of coins should be in the ballpark of 2,100,000,000,000,000 then it's unclear how you handle "pennies". The devil is in the details, I'm still unclear on what your proposed data structure is supposed to support exactly, without space/time complexity blowup. There should be a more detailed description of how the nodes calculate the two basic operations that I mentioned:

(1) if optional winning address which was derived via follow-the-satoshi didn't provide the heartbeat then you have to discover all the other satoshis that are controlled by this address and mark them as blacklisted in the database, and (2) whenever someone transfers his coins to a blacklisted address we should blacklist those newly transferred coins too.

I'd also like to analyse the non-blacklisting simplified protocol from economic and technical viewpoints:

If we cannot blacklist address, then I think that the main issue that we should analyse is the incentive structure for stakeholders. Maybe it makes sense to go with optional fees that are set by the free market, and have a protocol rule that disallows the total fees reward for the stakeholders block to be too high, relative to the average miners fees reward according to the last difficulty retarget window. This way the stakeholders couldn't demand too high fees to further enrich themselves at the expense of non-stakeholders? The honest client should also calculate and set the minimal recommended fee as the default fee, and this fee should be the same whether the txn was included by miners or by stakeholders, I think?

Simply capping the reward isn't good, because an attacker could broadcast a txn with high fee to exclude everyone else, and our objective is to include as many txns as possible in each block. We could cap the fee for each txn according to the average fee in the previous retarget window, and also cap the total number of txns. The property that I'm trying to achieve is that the stakeholders wouldn't try to enrich themselves too much by refusing to sign the block until they receive a higher total fee. The miners have to re-solve the block when there are no willing stakeholders available, so this should provide some competition among the stakeholders and hopefully push their fees downwards. I'm trying to figure out which incentives structure would work well, and we should also consider your bribe attack scenarios in this context. So far I think that these simple ideas are questionable and inelegant, maybe there are better ideas for the non-blacklisting simple protocol? Preferably without infinite monetary inflation, but we can consider ideas that use infinite inflation too. Maybe even have colored-coins as the reward for stakeholders? Though the colored-coins could be exchanged for regular coins, like BTC/LTC etc.

[cunicula]

[Okay, finished.]

I think the database is completely workable.

However, some concepts need to be introduced.
There are two databases that are used.
1) Blockchain: Source of all data that bitcoin uses + data on input age which is necessary to calculate demurrage fees on dead coins
2) Database of Blockchain Meta Info: Source of data for 1) lottery 2) demurrage fees reductions 3) recording of signatures


I'm not sure where to begin, so I'm just going to go through an algorithm for maintaining the database, running the lottery, and enforcing fees.

Here are the database fields that are going to be populated:

"Public Key (sorted by alphabet)"

"Linked Stake Public Key"

"Balance"

"Cumulative Balance"

"Coin-Age"

"Forgiven Coin-Age"

Here is the data which is taken directly form the block chain:

"Total Input Value"

"Average Input Age"

"Total Mint"

Part I Sending
1) For each txn in block t, check if the public key that signed the txn is listed in the database.
a) If yes,
      i) Txn fee on send: Txn Fee >= max(Balance,total input value)*(exp(max(Coin-Age, Average Input Age)*annual demurrage rate)-1) - Balance*(exp(Forgiven Coin-Age*annual demurrage fee)-1) [Otherwise the txn is invalid.]
      ii) If the txn is sent from a limited stake signing key, check: Change Returned to Root Public Key >= all coins sent to other addresses * {max(k,k*(t/coin-years on public key)} where k=9 and t=1/12.  [Otherwise the txn is invalid]
      iii) Set Balance_t= Balance_(t-1)-total value of inputs. [This could be less than 0. That is fine]
      iv) Set Coin-age=1 and Forgiven Coin-age=0.
      v) If Balance_t<1 , then delete the public key from the database together with all its associated data.
b) If no, then
     i) Txn fee on send: Txn Fee >= (total input value)*(exp(average input age in years*annual demurrage rate)-1) [Otherwise the txn is invalid.]
     ii) The database remains unchanged.

Part II Receiving
1) For each txn in block t, check if the receiving public key is listed in the database.
2) If yes,
       a) add to the balance on the receiving address as follows: balance_t=balance_(t-1)+received coins
       b) update the coin-age on the receiving address as follows: Coin_age_t = [Coin_age_(t-1)*balance_(t-1)+received coins]/balance(t)
3) If no,
        a) Check if the address has received more than one coin, if so add the receiving public key to the database.
             Step 1: Set the public key balance = the number of received coins. (this may be less than the true value of inputs controlled by the key)
             Step 2: Set the coin-age on the public key balance = 1. (this may be less than the true age of the inputs controlled by the key)
             Step 3: Leave the Linked Stake Public Key field blank.
             Step 4: Set Active=1.

Part III General Changes.
1) If an address has not received coins, its Coin-Age(t)=Coin-Age(t-1)+1

Part IV Assigning Linked Stake Public Keys: Special txns record linkages between public keys and limited stake public keys.
1) Check if the public key is listed in the database. [If not, the txn is invalid.]
2) If yes,
       a) check if the public key is already associated with a linked stake public key. [If yes, the txn is invalid.]
       b) if the public key has not been assigned a linked stake public key, then record the linked stake public key in the database.

Part V. Txn Fee Fund
1) If the block is PoW
         a) Txn Fee Fund(t)=0.9999*(Txn Fee Fund(t-1)+(1/2-Voluntary Sigs in Block/10)*Txn Fees (t))
         b) Generation to PoW miner = 0.0001*(Txn Fee Fund(t-1)+(1/2+Voluntary Sigs in Block/10)*Txn Fees (t))
2) If the block is PoS
         a) Txn Fee Fund(t)=0.995*((Txn Fee Fund(t-1)+(1/2-Voluntary Sigs in Block/10)*Txn Fees (t))
         b) Generation to each PoS signatory and PoS block miner = 0.001*((Txn Fee Fund(t-1)+(1/2+Voluntary Sigs in Block/10)*Txn Fees (t))
[Note there are a total of 5 Signatories including PoS block miner. There is an incentive to include Voluntary Sigs in Blocks]

Part VI. Mandatory and Voluntary Signatures. [For PoS Blocks only]
1) If the key has provided a mandatory signature or voluntarily signed the previous PoS Block.
    a) then forgiven coin-age (t)= coin-age(t-1).  [Note that coin-age is not reset by the signature. Forgiven Coin-Age is just increased.]
2) Voluntary Signatures
    a)Voluntary signatures are just special txns that are included in blocks. 
    b)For any voluntary Signature check if
        i) Has the voluntary signature been requested since time t-6 [If a block includes an unrequested signature it is invalid.]
        ii) Has the voluntary signature been provided in a block since time t-6 [If a block includes a duplicate signature, then it is invalid]
    c) A maximum of 5 voluntary signatures can be included in 1 block. [If not, the block is invalid.]
3) If a key's voluntary signature is requested at time t-6 but this signature is not in any block up to time t
    a) The entry for this key should be deleted from the database.
   
Part VII. Cumulative Balance
  1) After Balance is updated, the lottery probabilities will change. Cumulative Balance needs to be repopulated to account for changes in balance. Call the sum total cumulative for the last database entry "Total Balance"
  
Part VIII. Lottery Draw
  1) Check if PoW submission meets the difficulty target [If not draw is invalid]
  2) Hash PoW submission 10 times
  3) Map each hash to a draw from the uniform distribution on the interval [0, Total Mint]
  4) Check if all of the hashes map to the interval [0, Total Balance] (Note that Total Balance <= Total Mint)
        4a) If yes, identify the public key associated with each draw in the database. The first five draws indicate mandatory signatures. The next five draws indicate voluntary
               signatures.
        4b) If no, the PoW submission is invalid.

Part IX Mining Process
  1) PoW miner broadcasts message0={work submission; Hash(Previous PoS Block), ,Hash (This PoW block) }
  2) Message is transmitted. Receivers verify
              a) work submission meets target. 
              b) Hash (Previous PoS Block) refers to the most recent PoS Block they have heard of.
              c) work submission Lottery Draw maps to 10 addresses in the database.
              d) They have not previously heard this message.  [Note that it is fine if multiple PoW Blocks circulate simultaneously]
              e) They have not heard an updated version of this message that includes one or more signatures.
              f)  If (a)-(e) are true, receivers relay the message.
   3) Key holder provides his mandatory signature and transmits the new message. message1={work submission; Hash(Previous PoS Block),Hash (This PoW block); Sig 1(message 0)  }
   4) Receivers verify
              a) work submission meets target. 
              b) Hash (Previous PoS Block) refers to the most recent PoS Block they have heard of.
              c) work submission Lottery Draw maps to 10 addresses in the database.
              d) They have not previously heard this message.  [Note that it is fine if multiple PoW Blocks circulate simultaneously]
              e) They have not heard an updated version of this message that includes more signatures.
              f)  The mandatory signatures are the correct ones as indicated by a hash of the work submission.
              g) If (a)-(f) are true, receivers relay the message.
     5) Go to 3 and repeat until all 5 signatures have been added {work submission; Hash(Previous PoS Block),Hash (This PoW block); Sig 1(message 0); Sig 2(message 1); Sig 3(message 2); Sig 4(message 3) ; Sig 5(message 4)}
     6) PoW miner receives all 5 signatures and broadcasts block together with signatures.
     7) 5th Signatory hears of broadcast PoW block. He then broadcasts his own block and signs Hash (PoS block, PoW block). The PoS block contains payments for all the mandatory PoS signatories.

Part X) Block Validation.
         i) All txns in block are valid. (e.g. standard blockchain checks + additional checks as described above)
        ii) Each blocks must build on the previous one. (can be done in the standard way whatever that is)
        iii) The PoW submissions maps to to 10 signatures in the database. [The database needs to be constructed as the blockchain is validated.]
        iv) The PoW block contains the correct Txn fee payments to the generation address.
         v) The PoS block contains the correct Txn fee payments to the five mandatory signatories.
        vi) The block is not over the block size limit.

            
Not sure what else I am missing. I am sure there is plenty.