As you say in your subsequent comments, things are not so clear. I admit that my initial comment here was somewhat confused, but I still think that the concern is quite real. So for example if the last txn of the block competes with another txn, and 50% of the gold holders see and sign the block with the first txn and the other 50% sign the block with the competing txn: it could be that none of the gold holders is malicious, but we've reached a gridlock, so if 16% honest gold holders switch and also sign the other block, and vice versa, we get two forked branches. In case the gold holders are rational instead of honest, more elaborate scenarios that involve e.g. extortion could arise when the last txn is valuable.


I pity PPS pool operators...
I was wrong, the pool better work on its own branch even if the vast majority of the hashpower works on the competing branch, because it has its usual chances of solving the next block (and thereby solve two consecutive blocks), and if it switched to the competing branch then the likely-to-be-orphaned block that it solved immediately goes to waste.

Looking at your post there:


If I understand correctly, any txn (above threshold of 210 coins) modifies the hash and thereby derives new lucky stakeholders who may sign the block, who would thereby move the blockchain to the next block t+1. If that's the case, how is it different than PoW mining? Any "miner" with large computational power could just tweak some txn (that he sends to himself) until the block gets solved. Each tweak attempt derives new pseudorandom lucky stakeholders, so it's equivalent to PoW hash attempts (actually PoW hash attempts at an extremely low difficulty, because creating ECDSA signature for the txn can be done quickly, so the competing "miners" will cause huge network sync problems).

Two problems.

1) Suppose that there are (say) 50k gold holders. With Bitcoin, you know that your txn will be processed in about 10 minutes. Here, you said nothing about the variance. The user who wishes to do a txn has to wait until 50k other users also wish to do txns, so the amount of time he has to wait could be highly unpredictable. I'm not sure whether it'd all converge to predictable numbers, and how long it would take to re-converge if some fundamentals have changed, etc.

2) The much more severe problem is forked branches. After 49,999 txns were broadcasted, when a 50,000th txn is broadcasted it might compete with another 50,000th txn that reaches other network nodes first, so we've forked into two branches. After the next 50k txns, those two branches could fork into 4 branches, and so on.

BTW, how does the Bitcoin client behave when it solves a block which gets rejected by other nodes because they saw another solved block (slightly) earlier? Does it try to extend its solved block, or throw it away because of the rejections? If it tries to extend, does it mean that a mining pool that solved a would-be orphaned block will waste the next 10 minutes (on average) trying to extend it?

Hello cunicula,


There could be rational/malicious stakeholders who always provide the voluntary signatures to avoid the demurrage fee, but would be less willing to provide the mandatory signatures. To measure the participation level of a particular stakeholder we have to use voluntary signatures, because mandatory signatures that he failed to provide won't be recorded anywhere. Therefore the benefits of blacklisting become less straightforward, even if we do the lottery only among stakeholders who provided a heartbeat (whitelist). In other words, the voluntary signatures indeed force the stakeholder to maintain a full node that's always online, but it doesn't force the stakeholder to participate in generating mandatory blocks. So we overcome the concern of "lazy" stakeholders who aren't online, but not the concern of rational/malicious stakeholders who attempt to enrich themselves by denying service until their demands are met. Assuming that the would-be lazy stakeholders are honest (i.e. accept the recommended fee price as specified by the protocol), the voluntary signatures will push the fees downwards (compared to non-blacklisting protocol). But if the would-be lazy stakeholders are rational/malicious, the voluntary signatures wouldn't help in this regard.

Regarding the simple non-blacklisting protocol. Suppose that every (say) 5th block is the PoW block that derives the winning stakeholders who should create their mandatory block, and at the end of the difficulty retarget window we measure two difficulties: the regular pure-PoW difficulty, and the difficulty of the special 5th PoW blocks (by summing up the time differences between every 5th and 7th blocks in the retarget window, where the 6th block is the stakeholders block). Now we can have a separate difficulty re-adjustment for the special 5th blocks, which means that if too many stakeholders are greedy/malicious and deny service until their demands are met, then at the next retarget window it would be easier for the miners to generate the 5th PoW block, so more potential stakeholders would get a chance to participate (by re-solving the block when there aren't willing stakeholders available), which will hopefully push the stakeholders' fees downward toward the recommended fee that's used by honest clients?

Edit: The alternative is to have only PoW blocks that derive winning stakeholders (your post #134). Then there'd be only one re-adjusted difficulty that takes into account both the PoW hashrate and the stakeholders' participation level. This should also work in this regard, it just maximizes the reliance on stakeholders, so it has other implications. BTW, the protocol should probably split the txn fees between the PoW block that derives the winning stakeholders and the following stakeholders block, because near-instant stakeholders blocks wouldn't have many txns. If it's a protocol with 3 winning stakeholders, then it could specify that only the 3rd stakeholder includes txns in their block.

What about you idea of using mandatory fixed fees, say 0.1% fees? We could re-adjust the mandatory fixed fee at the next retarget window for example according to total txn volume (fewer total number of txns imply that we need higher fixed fee) ? This way it'd be futile for stakeholders (and miners) to demand higher fees, they could only refuse to generate blocks while not enough (high-paying) txns were broadcast. I think that you mentioned this idea in relation to bribe attacks?

Not sure that I understand the scenario exactly. At the end of the day the user who wishes to do some txn has to pay some fee to the entity that handles his txn. When the system is decentralized, he pays the fee to the decentralized node that processed his txn, and when the system is centralized he pays the fee to the central entity. Why do you claim that the fee to the central entity will be lower than the fee to the decentralized node? Wouldn't the central entity be a monopoly who could jack up fee prices, while decentralized nodes compete and therefore the fee prices are pushed downward?


How about blackmail, for example the 1/3 malicious minority could say "pay us X silver coins otherwise we deny service" ? You might even describe this 1/3 minority as rational instead of malicious?

All I'm saying is that a protocol that withstands 1/2 malicious stakeholders is preferable to a protocol that only withstands 1/3 malicious stakeholders, and those were just the initial thoughts, maybe there are even worse vulnerabilities that we're still missing. One other drawback of this protocol vis-a-vis the lottery protocol is that here the malicious majority (actually 1/3) can deny service completely, while with lottery the 1/2 malicious majority could only generate empty blocks half of the time. Edit: actually with 3 consecutive mandatory stakeholders blocks, the performance will become 8 times slower, and 1/8 of the time the malicious 1/2 will create empty blocks.


I don't think that double-spending/denial-of-service attacks with this pure-PoS protocol are analogous to the mixed PoW+PoA protocol. With mixed PoW+PoA the attacker depletes his resources while he's carrying out the attack, because of the PoW element. With pure-PoS it's costless for the malicious/rational stakeholders to carry out attacks.

I don't think that you explained the tradeoff between txn fees and decentralization?

I think that if you wish to buy for example a new car then you can transact directly on the blockchain, and for less valuable fast txns there could be centralized transaction hubs, on top of the cryptocurrency: https://en.bitcoin.it/w/index.php?title=Myths&oldid=27737#Point_of_sale_with_bitcoins_isn.27t_possible_because_of_the_10_minute_wait_for_confirmation


I remain unconvinced. There are at most 100,000 gold coins in total, so a malicious entity can obtain 1/3 of all the gold coins in sync with the rest of the participants, until it gets 33,334 gold coins at the most. I still claim that if 1/3 of the stakeholders are malicious then this system would be destroyed.

If we replace 2/3 by 1/2 then the double-spending risk becomes more pronounced, in particular when we use your common assumption that the majority is rational rather than honest. Even if only (say) 30% of the stakeholders are malicious, there would need to be just 20% rational stakeholders for double-spending to occur.

I'm not so convinced that there's a tradeoff. I agree that more decentralization implies more security. I think that technology-wise we can provide fast enough speed (say new block every 2 minutes or 10 minutes), so if you wait e.g. 10 minutes or 60 minutes you can be confident that your txn cleared, which is much better than what centralized banks offer at the present (for example having to wait days until your money reaches mtgox). For scenarios that require even faster speeds, we can have external (more centralized) payment processing systems on top of the cryptocurrency (discussed e.g. at Talk:Scalability and this old wiki revision). Regarding low fees, I agree that this would increase the value of the cryptocurrency, but can you explain why there's supposed to be a tradeoff between low fees and more decentralization? Also, could you explain why the pure-PoS protocol that you propose here is supposed to imply lower fees than the pure-PoW protocol?
I think that rather than this supposed tradeoff, the advantages of PoS over PoW are (1) better security because the stakeholders are (also) responsible for providing security, and (2) more efficient energy use.


Initial thoughts regarding this particular protocol:

1/3 malicious gold-holders can destroy the cryptocurrency by denying service. If you change the signatures requirement to 1/2 instead of 2/3, then a malicious majority could double-spend. Similar scenario was discussed here. We generally seek to obtain a secure system as long as the majority isn't malicious, while your system is vulnerable if just 1/3 is malicious.

The initial distribution isn't so clear, could you elaborate? Who would control the initial distribution process? Can it be done in a decentralized fashion?

Hello cunicula,


Apologies, I was confused. Obviously what I suggested also blacklists fragmented dead coins because they're ineligible as I mentioned.

Also, what I suggested wouldn't broadcast ineligible PoW blocks, because all PoW blocks will be in fact eligible: if the first pseudorandom satoshi isn't eligible then the protocol says that it isn't used, and we look at the 2nd pseudorandom satoshi, and so on, until reaching 3 eligible satoshis, and those 3 satoshis are the ones that are derived from the PoW block (this procedure is unambiguous because all nodes that follow the protocol will have the same info/database at this block). An alternative approach is that if any of the first 3 pseudorandom satoshis isn't eligible then the PoW block is invalid, but also with this approach the PoW miner wouldn't need to broadcast his failed block to the rest of the network, so I don't understand what was your concern. The PoW difficulty will re-adjust accordingly if we use the 2nd approach, so I think that the 2nd approach is actually more efficient.

Looking at your post #140, you suggest to store the balances of all eligible addresses, pick random number smaller than this cumulative balance, and find the corresponding address. The end result is the same as with using follow-the-satoshi, but your post #140 is much more strict: all nodes must use exactly the same database at every block, and might need to maintain different continuations of the database in case of chain forks, i.e. it's a duplicative effort in addition to maintaining the blockchain. Supposedly you're trading space complexity for time complexity, but my guess is that using follow-the-satoshi is better overall, and it's more elegant.

BTW, there's also a positive aspect to the eligibility requirement of having at least one consolidated coin, because it encourages less blockchain fragmentation.


I agree that heartbeats aren't that difficult to implement, but I don't see why you think that it's less bloated. Each heartbeat signature has to be stored in the blockchain, so storing such a signature is similar to storing a txn. One difference is that the txn could be some txn that the stakeholder wanted to do anyway, implying that the txns approach is less bloated.


I have a request: could you please summarize all the benefits that we'd get from heartbeats/blacklisting, i.e. benefits that we don't know how to get without blacklisting? I realize that you already mentioned it in various posts, but maybe your understanding has progressed a little since then, and anyway it'd be useful to have a clear summary in order to decide whether the complexities of blacklisting are something that's worth doing. Regarding which benefits you should focus on, my main concern is the incentive structure that'd imply high stakeholders' participation. I think that regarding a protocol with mandatory stakeholders' blocks, the main focus should be what I mentioned in post #135:


Though we should also be concerned that the reward for stakeholders isn't excessive (the rich get richer, extreme example in post #129), as well as bribe attacks.

How about this: whenever an address receives at least one coin, we increment a counter that's stored at the database entry of this address, and whenever an address spends an input of at least one coin we decrement the counter. When the counter reaches zero we remove the address from the database. If the address failed to provide a heartbeat then it's kept in the database and marked as inactive. This way the total number of entries in the database is bounded by 21 million. All addresses that control at least one (consolidated) coin will be in the database.

To derive a lucky stakeholder, we cannot just select a random address uniformly from the database, because addresses that hold more coins should have higher probability to be selected. We can use follow-the-satoshi, and if the address that controls the satoshi isn't in the database (because it controls less than one consolidated coin) or is blacklisted then it's ineligible we derive the next pseudorandom satoshi, until reaching 3 eligible satoshis. The drawback is that stakeholders that control less than one (consolidated) coin don't participate in the lottery, so the reasons why heartbeats are useful should be persuading (both because of this drawback, and because of the added complexity). One unfortunate property that's implied by drawback is that fragmented dead coins won't be blacklisted, but there's probably not getting around that, because we cannot allow blacklisting each single satoshi without complexity blowup. Do you think that there is a better ways to derive the lucky stakeholder, instead of follow-the-satoshi?

The database can be virtual, i.e. it isn't important whether all the nodes have exactly the same database (e.g. the addresses don't have to be in the same order) or if they use another data structure to maintain this information. The protocol rule can simply specify that the if derived pseudorandom satoshi is ineligible (because the address didn't provide heartbeat or because the address doesn't control at least one consolidated coin) then it must not be used, so we hash and derive the next pseudorandom satoshi, until getting 3 eligible satoshis. The official client would probably create this database in order to verify the calculations, but everything that's stored in the database can be derived unambiguously from the blockchain. We rely on the assumption that >50% of the nodes are honest. There might be a risk that lazy nodes will prefer to skip the extra calculations and ignore the database, if the stakeholders' participation level is very high?

Maybe the one consolidated coin threshold should be dynamic? Meaning that if stakeholders participation is high then an address would need more than one consolidated coin in order to enter the database? I think that this would add significant complexities, and the benefits aren't so crucial (e.g. 2 million database entries instead of 21 million entries).

I'm not sure whether the extra heartbeats mechanism is superfluous, and instead we could simply say that an address in the database that didn't spend any of its coins in the last (say) 1000 blocks is blacklisted. What'd be the disadvantages of this approach?

What if an address that controlled less than 1 coin received only a few satoshis in this txn, but those few satoshis now caused it to control more than 1 coin? You would have to calculate the balance of each address in each txn of each block?
What if some blacklisted address (that controlled more than 1 coin and didn't provide a heartbeat) transfers a few satoshis so that it now controls less than 1 coin, do you remove this address from the database? If the answer is yes, then this address could then receive a few satoshis in order to get back into the whitelist so that it'd un-blacklist itself? If the answer is no, then blacklisted addresses are kept in the database, implying that the total number of entries in the database can reach 2^256

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:


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

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.

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.



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.

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?


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?

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?

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


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.

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.


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.

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?

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.


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.

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


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.