ppcoin stake generation tournament

[H@ml3t]

A perpetual tournament is proposed, in which stake holders try to compete against each other for generating the longest consecutive fork. This will provide an empirical means to investigate the security of the ppcoin network and show strengths and weaknesses of the current scheme.

I've shown before that I can generate large consecutive chains of blocks by just bring the exchange cold wallet online. The first time I did this I got 84 consecutive blocks. The second time over 100. Yesterday I brought another wallet online and left it running. When I closed it overnight it had 400 blocks in 'immature' status. That is probably why POS difficulty is currently 30+. The exchange doesn't have that many coins. There are people out there with more coins than the exchange I'm sure.

Did you do this with 0.3 or pre-0.3? If you did it with 0.3 we propably can assume that the pos problem has not been fixed, or?

[Jutarul]

I've shown before that I can generate large consecutive chains of blocks

Did you do this with 0.3 or pre-0.3? If you did it with 0.3 we propably can assume that the pos problem has not been fixed, or?

see my response. https://bitcointalk.org/index.php?topic=152809.msg1627960#msg1627960

for the POS scheme to work, block generation needs to be competitive. Also at any time the differential of stake dS added to the network must not be greater than the existing stake S. Assuming proportionality between stake and stake generation power. In fact what you want is the added stake generation power d(SGP) to be less than the stake generation power (SGP) being online at any given moment.

Assuming that the POS difficulty is equilibrated, one could assume that the stake generation power of the network is proportional to the current difficulty. It should thus be easy to estimate the stake generation power required to overcome the network at any given time. I have some experience with physics, so I may try to express this in terms of mathematical equations.

What happens when you move stake offline for a while is that your stake matures and gets charged in terms of stake generation power. There is a cap of 90 days to prevent supercharging stake.

[doublec]

Did you do this with 0.3 or pre-0.3? If you did it with 0.3 we propably can assume that the pos problem has not been fixed, or?

0.3 doesn't switch on until after March 20 I think.

[Jutarul]

Q: Can you fork the chain by turning your client off for a long time, then spamming PoS blocks when it comes back online?

I think the easiest implementation to test this is to just start up the coin with 10,000 coins or whatever in a bunch of public addresses on a test net with PoW disabled.  Then, see if anyone can spam the chain quickly enough with PoS blocks to fork it and do things they shouldn't be able to do, like invalidate transactions.

Good question.

I think the default behavior is that the generation of blocks is suppressed if the client detects that it is disconnected from the network. However you can circumvent that by creating your own little network of clients in which you can breed a fork. Then when ready, you switch to the public network, which pushes the fork online.

On the main network this would be prevented by checkpoints, since other miners won't accept your fork if the delta>6. I don't know the security implications of checkpoints and how they react to a mix of DDOS and forked blockchain. I think the use of centralized checkpoints rules out a few attack vectors, where you would confuse the checkpointing mechanism by means of communicating with the node, and the central communication seems to be protected by signatures (the central checkpoints are signed, checkpoints.cpp:369).

Without checkpoints the same properties as with the bitcoin network applies, which means that the longest chain wins.

[H@ml3t]

I've shown before that I can generate large consecutive chains of blocks

Did you do this with 0.3 or pre-0.3? If you did it with 0.3 we propably can assume that the pos problem has not been fixed, or?

see my response. https://bitcointalk.org/index.php?topic=152809.msg1627960#msg1627960

for the POS scheme to work, block generation needs to be competitive. Also at any time the differential of stake dS added to the network must not be greater than the existing stake S. Assuming proportionality between stake and stake generation power. In fact what you want is the added stake generation power d(SGP) to be less than the stake generation power (SGP) being online at any given moment.

Assuming that the POS difficulty is equilibrated, one could assume that the stake generation power of the network is proportional to the current difficulty. It should thus be easy to estimate the stake generation power required to overcome the network at any given time. I have some experience with physics, so I may try to express this in terms of mathematical equations.

What happens when you move stake offline for a while is that your stake matures and gets charged in terms of stake generation power. There is a cap of 90 days to prevent supercharging stake.

I understand that the block generation needs to be competitive, but I think you can call the current network environment competitive. I mean the wallet of the exchange doesn't have a majority of coins for sure but dublec is still able to create long chains on his own.
I think the main problem is charging your stake offline. If that wouldn't be possible, the situation could be compared to POW, where you can keep your mining devices offline to wait for lower difficulty in order to spam the blockchain later, but nobody is doing this as you can't mine coins while your offline/not running mining devices. With the current POS scheme however you are able to keep difficulty low while charging your stake, which can be turned into coins later, so it is economically in two ways:You can keep your stake offline for some time to wait for lower difficulty and "mine" the coins later AND you can try to attack the network when difficulty is low.

Another point which is interesting to consider are the lost coins. In Bitcoins those coins don't matter but with POS lost coins can weaken the security as those coins cant generate stake anymore, thus making 51% POS attacks cheaper.

[Jutarul]

I understand that the block generation needs to be competitive, but I think you can call the current network environment competitive. I mean the wallet of the exchange doesn't have a majority of coins for sure but dublec is still able to create long chains on his own.
I think the main problem is charging your stake offline. If that wouldn't be possible, the situation could be compared to POW, where you can keep your mining devices offline to wait for lower difficulty in order to spam the blockchain later, but nobody is doing this as you can't mine coins while your offline/not running mining devices.

Glad you brought the topic up. In fact POW has a similar problem as POS, but hardly nobody knows or cares. What you have in bitcoin is technology bound hashing, where the costs for the hardware is high and the cost for the energy is (comparatively) low. This is amplified by the fact that the efficiency of the mining devices is rapidly increasing. However, once we hit a technological barrier (it may be sooner than you think) and technology becomes ubiquitous we enter an era of energy bound hashing. And that changes the nature of the game, where it may suddenly be advantageous to not perform 24/7 hashing.

The POS scheme implemented in ppcoin gives us a glimpse of where the bitcoin POW system is going eventually - not today, not tomorrow, but many years from now. Thus by studying the relationship between block generation power and stake you may solve a future crisis of bitcoin, which is a real crisis in ppcoin right now. I think this fact is under appreciated.

With the current POS scheme however you are able to keep difficulty low while charging your stake, which can be turned into coins later, so it is economically in two ways:You can keep your stake offline for some time to wait for lower difficulty and "mine" the coins later AND you can try to attack the network when difficulty is low.

Another point which is interesting to consider are the lost coins. In Bitcoins those coins don't matter but with POS lost coins can weaken the security as those coins cant generate stake anymore, thus making 51% POS attacks cheaper.

The economy of a 51% is a bit of a different topic. There are some who argue that the collateral damage of performing an attack as a POS miner is larger then the potential gain. It needs analyzing, but what has to come first in my opinion is a technical means to establish a better relationship between block generation power and stake.

[H@ml3t]

Did you do this with 0.3 or pre-0.3? If you did it with 0.3 we propably can assume that the pos problem has not been fixed, or?

0.3 doesn't switch on until after March 20 I think.

Would you mind bringing the cold wallet online once again, now after the protocoll switch, to see how many blocks in a row you can create on your own after the fix?

[Jutarul]

*bump*

If you have any more constructive ideas on this issue, please post them - I am going to work on the details soon.

[Vuxil]

I just wanted to say thank you to everyone taking the time to investigate this issue and work towards a solution. I contacted Sunny King about contributing to the project, and I'm going through some documentation and code for Bitcoin and PPCoin right now. Hopefully I'll be on your guys' level pretty soon here =)

[tacotime]

I think few good questions were brought up here;

Still trying to wrap my head around this;

You have 10,000 people attempting to mine stake blocks.  A has 30,000 coin years, and B has 10,000 coin years, and the rest of the network have less than 10,000 coin years.

B mints a stake block and the rest of the network mints stake blocks on top of B.

Can A fork the chain by declaring a chain in which he mints a stake block in place of B's block?  I would guess you made that forbidden by timestamp, but if A decides he doesn't like a transaction in block B, what's to stop A from announcing a new block and in effect destroying that transaction before the next person adds a block?  Is there anything in place to stop malicious stake mining like that, or is that the "51%" stake attack?

51% stake attack doesn't seem to require 51% of the coins either, since 51% would be based upon the assumption that everyone in the network is holding coins to mine stake blocks.  However, if most coins are being used for actual transactions, the required amount of stake to fork the network is actually only a fraction of 51%.

A problem also may arise when you have 10,000 people all making hundreds of possibly valid chains at the same.  If all these 10,000 people are announcing valid stake blocks at the same time, how do you avoid network congestion because the users are all required to figure out what the most valid chain is (chain with the most coinstakeage)?  Won't you generate hundreds or thousands of orphan chains?

I'm curious to see how the PPC network would work if we generated a massive number of clients with large coin age all competing for stake blocks at the same time.

Additionally important is the theoretical mathematical problem of exactly how much stake investment (cumulative coin age) it will take to fork the network given a percentage of users actually using the coin within a 30 day period.

I'm wondering if the eventual massive stake competition will actually lead to PPC being energy inefficient in terms of network bandwidth, which would defeat the purpose of the chain's claimed energy efficiency.

[killerstorm]

for the POS scheme to work, block generation needs to be competitive. Also at any time the differential of stake dS added to the network must not be greater than the existing stake S. Assuming proportionality between stake and stake generation power. In fact what you want is the added stake generation power d(SGP) to be less than the stake generation power (SGP) being online at any given moment.

I'm not sure what do you mean by "differential of stake", but I really do not see why do you assume that parity is enough to keep network safe.

Do not forget that attacker can try again and again, boosting his chances to generate a consecutive chain of blocks.

Assuming that the POS difficulty is equilibrated, one could assume that the stake generation power of the network is proportional to the current difficulty. It should thus be easy to estimate the stake generation power required to overcome the network at any given time. I have some experience with physics, so I may try to express this in terms of mathematical equations.

It would be much easier to make a simulation, it's pretty much trivial.

BTW the major problem I see is that if difficulty is high enough incentive to mine diminishes: basically, you might need to keep your computer online for a whole year to get a chance to earn 1%. Unless you have a lot of stake, it makes no sense. And even then, aren't there better things to do with your money?

I think in the end it makes PPCoin security relatively shitty: only a fraction of coins will be used as a stake, and attacker will get a boost from repeated attempts.

What happens when you move stake offline for a while is that your stake matures and gets charged in terms of stake generation power. There is a cap of 90 days to prevent supercharging stake.

Oh, I've missed this... It makes things easier to analyze.

Basically, we can consider only a case where there is a plenty of active stake, so almost all of it already got to 90 days limit. Attacker's coins will be at 90 days limit too.

Thus probability that attacker mines next PoS block is approximately p = attacker's_stake/total_active_stake.

Probability to mine next k blocks is approximately p^k. Now we can calculate expected wait until first success as a mean of geometric distribution, it is 1/p^k.

So if you have 25% of active stake mean time to double-spend is 1/(0.25^6) = 4096, around one month... Not bad.

Obviously, you need less than 25% of coins. It is hard to say how much less, but likely a lot less. Since once PPCoin stake mining gets competitive, it is a fool's errand.

[killerstorm]

BTW I found a strange thing in PPCoin code.

https://github.com/ppcoin/ppcoin/blob/master/src/kernel.cpp#L283

Code:

    // v0.3 protocol kernel hash weight starts from 0 at the 30-day min age
    // this change increases active coins participating the hash and helps
    // to secure the network when proof-of-stake difficulty is low
    int64 nTimeWeight = min((int64)nTimeTx - txPrev.nTime, (int64)STAKE_MAX_AGE) - (IsProtocolV03(nTimeTx)? nStakeMinAge : 0);
    CBigNum bnCoinDayWeight = CBigNum(nValueIn) * nTimeWeight / COIN / (24 * 60 * 60);

Comment doesn't match the code. The difference between v0.2 and v0.3 is that in v0.3 time weight is limited by 60 days, while in 0.2 it was limited by 90.

However, in both cases initial time weight is 30.

Perhaps Sunny meant:

Code:

int64 nTimeWeight = min((int64)nTimeTx - txPrev.nTime  - (IsProtocolV03(nTimeTx)? nStakeMinAge : 0, (int64)STAKE_MAX_AGE));

[Jutarul]

for the POS scheme to work, block generation needs to be competitive. Also at any time the differential of stake dS added to the network must not be greater than the existing stake S. Assuming proportionality between stake and stake generation power. In fact what you want is the added stake generation power d(SGP) to be less than the stake generation power (SGP) being online at any given moment.

I'm not sure what do you mean by "differential of stake", but I really do not see why do you assume that parity is enough to keep network safe.

It means that the ratio between stake and money supply is important. If 1% of all coins are used as stake and 99% are used as money, you only need to own 0.5% of the total money supply to dominate stake mining. In fact, things are worse: The mean time for stake maturity will likely be less than the maximum of 90 days. Let's assume it to be 60 days, you can upgrade the specific stake you have by 50%, reducing your requirement for active stake even further.

However, here comes the worst feature: Creating forks doesn't involve any cost. You can try to create a fork in an instant for each point in the blockchain, based on the stake you have available. If you get lucky and have 7 in a row, you go ahead and perform a double spending attack. The "instant" feature comes from the fact that you do not require actual computational work to be involved in generating a stake block. You just need to be lucky - and by that you only have to wait for the right moment when 7 of your stake outputs chain nicely together.

In fact that's what you referred to as well by:

So if you have 25% of active stake mean time to double-spend is 1/(0.25^6) = 4096, around one month... Not bad.

If you want to prevent this sort of attack, you have to find a means to prevent someone from being able to generate quick forks from their stake without talking to the network. And I don't see how that is possible.

Oh ... and of course this all assumes that you haven't found a way to augment your stake generation power temporarily.