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

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.

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


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.


I elaborate on my idea below after I describe heartbeats.

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.

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?

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.

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?

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.

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?

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.


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.


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.

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.

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.

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.

I would prefer n=3.



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.

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.

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.

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?

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

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.

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

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.

Hey iddo,

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

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

1) some signatures on should be mandatory

mandatory sigs make secret PoW attacks very, very hard

2) there should be also be optional signatures

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

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

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

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

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

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

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