Bitcoin Forum

Abstract
=====

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.

Discussion
=======
The network security model of ppcoin is based on the premise that no particular stake holder can generate POS blocks faster than the network, i.e. the remaining stake holders combined. While this feature is implied by the proportionality between stake generation power and the amount of stake used at any given time, the proportionality is not proven yet. In fact, as the pre-0.3.0 version showed, it is not guaranteed for cases when stake generation power can be augmented by the use of computational power.

Due to incentive and time limitations, a thorough investigation of the POS scheme takes time. To advance this issue, I'd like to propose an empirical way of investigating the effectiveness of individual strategies to augment (temporarily) the stake generation power (POS blocks/time).

Since such a tournament would require lifting the checkpointing mechanism, which currently protects ppcoin from this vulnerability, it would likely have to be carried out on the testnet. However, even better, a special purpose tournament-net could be declared which could be equipped with features important for carrying out such a stress test.

I invite for a discussion of how such a tournament should look like. Comments are highly appreciated.

just seen this and skim read... am well interested and have a small sum of PPC that I stake generate with.. but not of late as wallet locked... but am willing to help test and experiment with, and will post more thoughts here once I have walked the dog :)

Sounds like a good plan.

I believe a special test net would need to be set up (remove check pointing and assign a new rpc / IP p2p port).

Possibly change the address version just to avoid confusion.

I will put the chain on cryptocoinexplorer.com

I'll bring my bladder full of water and a case of bottled water for this PP contest.  :D

Why do you need special testnet there is testnet running.

ppcoind -daemon -testnet

You can mine some coins on testnet with cpu easily. Or you can ask me for them.

My main concern is the removal of check point system. My thought is that it would affect others using the test net for other things, or that a mix of clients using/not using check points might affect the tournament itself.

However, if I am mistaken , it would certainly be easier to use the current test net.  :)

My main concern is the removal of check point system. My thought is that it would affect others using the test net for other things, or that a mix of clients using/not using check points might affect the tournament itself.

However, if I am mistaken , it would certainly be easier to use the current test net.  :)
[/quote]

Testnet doesn't have auto checkpoint.

Although I think it's hard to run on testnet as not many people would be interested.

You can run the contest on mainnet with checkpoint just try to claim consecutive proof-of-stake blocks. Even with checkpoint it won't prevent you from going way above 6 of them if you can generate them fast enough.

And here I thought that this last release did not need check pointing.

Did I miss something?

Checkpointing -> broken code

I would prefer if the blockchain behaves as realistic as possible without checkpoints - and it would make things easier to analyze if the forks are able to incorporate themselves into the main chain for delta>6, because of the lack an absolute clock.

To lead a more specific discussion, for the tournament net I propose to
1) deactivate POW
2) a genesis block is created, where each output contains 10k stake (this may need some fine-tuning) directed towards a ppcoin address of one participant
3) have a quick turn over of the stake, with a 1 day recovery (instead of the 30 days) and 3 days of maturing.
4) allow for a "warm up" period, e.g. 1 week or a number of generated blocks, in which each participant can setup their stake according to their own strategy.
5) After the warm up has ended, declare open season :)
6) finish the tournament at a later time, e.g. after 2 weeks or a number of generated blocks.
7) each participant should evaluate the block chain and determine the longest consecutive POS series they were able to generate from their own stake, which got incorporated into the main chain.
8 ) bonus points for successful double spent attacks?
9) declare the results and the winners, at least the winner has to disclose their strategy
10) rinse and repeat

further points:

- In the spirit of game theory I propose that each participant creates a strategy which can be expressed as an algorithm. It can be either a fundamental strategy, e.g. reject all other POS blocks at any given time, or a mix of fundamental strategies.
- a participant can have more the one contender, however each contender must work according to their own rules - and for the simplicity of it, contenders from the same participant should not collaborate. This can be enforced by forbidding mixing coins from different contenders (which would be a reason for disqualification).

outcomes:
- for the tournament we will likely create analytical tools which allow us to analyze and monitor blockchain forks in realtime
- we will learn which stake generation strategies perform best for maximizing the stake generation power
- we promote the POS concept and attract coders and smart people
- have fun

I don't think we will need monetary incentives right now. Later we may declare prizes for ppcoins on the main chain, which are generated from a fee collected for registering a contender.

I LOL'd

No seriously, if a bladder full of water helps squeezing out more stake blocks in a unit of time, I'd want to know :D

Meanwhile, difficulty of PPCoin is rising again  :o

can this not be mathematically modelled?

Well you can actually setup your own little blockchain and let each strategy play out. The purpose of a public tournament is to involve more brain power and to discuss the effect of stake generation strategies in the open.

It's of no use if one intelligent member figures out the perfect strategy to augment stake generation power, and the public only learns about it during successful double spend attacks.

Thanks for the invite Jut. I have a decent amount of coins on the main chain with the latest client and I'm somewhat technically literate, but I haven't given much thought yet to how one could attack this chain. I'd like to help out but I don't have anything to contribute right now, if you have any suggestions then let me know and I'll keep an eye on this thread.

Right now what you can do is to think about how a tournament net should be designed and what you'd like to be included in a stress test. I am going to push this idea, but I'd like to see people interested beforehand, which includes some brainstorming on the detailed design.

This defeats the purpose of what the thread is about. Now we will see if this coin will survive!

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.

Can you point me to a description of the new algo? I don't want to dig through all the source code just to see what's improved.

Unfortunately Sunny decided to skip the release of the design documents and nobody took the time to analyze it yet. There's a release thread: https://bitcointalk.org/index.php?topic=144964.0

Yes. But this is mainly an outcome of the mining to be non-competitive. For any consensus mechanism to work it has to be a competitive environment, no exceptions, including POW.

Yes. It's hard to learn anything if the exact numbers are not known. That's where a tournament would help.

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.

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.

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

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.

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.

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.


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.

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?

*bump*

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

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

I think few good questions were brought up here;

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.

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.


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.


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.

BTW I found a strange thing in PPCoin code.

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


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:

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:

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.