[PPC] PPCoin 0.2 Proposal

[killerstorm]

There  is a lottery. Here's a crude approximation:

Suppose attacker owns n identical accounts each having probability p of winning next proof-of-stake block. Attacker wants k-deep reorg.

Chances that k transactions can be used to build a chain of k blocks are p^k. However, there are C(n, k)*k! such different chains, and attacker can try to build them all (don't worry, there is early rejection: if first block does not match, attacker does not need to compute the rest). Moreover, attacker can wait for q blocks to perform his attack, i.e. he is not in a hurry.

Thus to perform this attack successfully we need p^k * C(n, k)*k! > 1/q, thus p > 1/(C(n, k)*k! *q)^(1/k)

For example, q = 1000, n = 5, k = 5: p > 0.096
q = 1000, n = 10, k = 5: p > 0.0319

We can see that having twice more accounts means we need 3x more probability, thus likely attacker needs as many accounts as possible. However, handling many accounts might require a lot of computational resources, at some point it won't be feasible.

Now what's about p, we don't know whether getting to 0.03 is realistic. But we can get a crude estimate. Suppose there are 100 equal shares in work. We can expect that chances that one of shares wins next proof-of-stake block are 1. But shares are not equal in terms of number of confirmations. If bp is chances to win for a smallest share, then we can write:

Code:

1*bp + 2*bp+...+100*bp=1

Thus bp ~= 1/5000. Thus to get to p > 0.03 we need 150 confirmations, to get to  p > 0.1 we need 500 confirmations.

So an attacker with 5% of money can do a 5-deep reorg each week or so. Attacker with 10% of money can do reorg each day.

I should note that this is a very crude estimate, but it demonstrates that problem is real.

This is not same as 51% attack on Bitcoin because: 1) smaller share is required; 2) attacker does not lose anything when he is trying to do a reorg, he can as well do it for shits and giggles. (Or, likely, for small profit.)

[cunicula]

Suppose there are 100 equal shares in work. We can expect that chances that one of shares wins next proof-of-stake block are 1. But shares are not equal in terms of number of confirmations. If bp is chances to win for a smallest share, then we can write:

Code:

1*bp + 2*bp+...+100*bp=1

Thus bp ~= 1/5000. Thus to get to p > 0.03 we need 150 confirmations, to get to  p > 0.1 we need 500 confirmations.

So an attacker with 5% of money can do a 5-deep reorg each week or so. Attacker with 10% of money can do reorg each day.

I should note that this is a very crude estimate, but it demonstrates that problem is real.

This is not same as 51% attack on Bitcoin because: 1) smaller share is required; 2) attacker does not lose anything when he is trying to do a reorg, he can as well do it for shits and giggles. (Or, likely, for small profit.)

I don't understand the part "suppose there are 100 equal shares in work". Is this equivalent to assuming hat the attacker has a work ability equal to 1% of aggregate work?

The reason I ask is that if you write suppose there are n shares in work, you then calculate b=n(n+1)/2p, which would seem to indicate that the answer depends heavily on the choice of n=100.

[killerstorm]

The reason I ask is that if you write suppose there are n shares in work, you then calculate b=n(n+1)/2p, which would seem to indicate that the answer depends heavily on the choice of n=100.

Yep, you are right. I do not fully understand behaviour here, but it looks like higher number of participants make it harder to perform attack. On the other hand, attacker can try splitting his coins into many accounts too.

It would be ironic if large-scale attacks would be infeasible computationally.

(Also it's worth noting that with your system top hash-rate equivalent is achieved when all money is in hands of one miner, as he will spend all his hasing power on account which highest coin-confirmations, while many independent miners would also waste their hashes on accounts with low coin-confirmations.)

[Sunny King]

There  is a lottery. Here's a crude approximation:

Suppose attacker owns n identical accounts each having probability p of winning next proof-of-stake block. Attacker wants k-deep reorg.

Chances that k transactions can be used to build a chain of k blocks are p^k. However, there are C(n, k)*k! such different chains, and attacker can try to build them all (don't worry, there is early rejection: if first block does not match, attacker does not need to compute the rest). Moreover, attacker can wait for q blocks to perform his attack, i.e. he is not in a hurry.

Thus to perform this attack successfully we need p^k * C(n, k)*k! > 1/q, thus p > 1/(C(n, k)*k! *q)^(1/k)

If you take your n (accounts) to infinity, you see it's just (p*n)^k > 1/q. Here p*n = p1 = probability of attacker finding next block first. So I hope you can see now that splitting coins does not give attacker any real advantage.

Pitting p1^k against 1/q does not make sense to me, you could argue the same against Bitcoin. I suggest re-reading Satoshi's analysis on Bitcoin's main chain protocol.

As to cunicula's post #40, I think he already realizes it does not apply. No you don't get to mint a block just because you have more coin age than what's in the last block.

[killerstorm]

If you take your n (accounts) to infinity, you see it's just (p*n)^k > 1/q. Here p*n = p1 = probability of attacker finding next block first.

Awesome! So attacker just needs to collect some portion of total coin-age to bring p1^k into a realistic range. Say, p1=1/4 is enough to do a 6-deep reorg once a month.

Pitting p1^k against 1/q does not make sense to me, you could argue the same against Bitcoin. I suggest re-reading Satoshi's analysis on Bitcoin's main chain protocol.

You were told many times, that's the fundamental difference between PoS and PoW.

If somebody gets 1/4 of hashing power and runs it for a month, he loses LOTS of money in electricity/equipment costs and in number of coins he haven't got.

If somebody accumulates 1/4 of coin-age to perform double-spend, he loses almost nothing. A single CPU can be used to find matching chains, and all he loses monetarily is interest-on-interest, which is negligible, i.e. 1/10000 per year(?).

So if there is an alternative PPCoin client which tries to do double-spends instead of normal PoS mining, there is no reason why a rational individual won't use it.

Moreover, it's possible to make a separate p2pool which aims to make double-spends using peer's shares and provides some extra reward for it.

One can simply run this p2pool in addition to a normal client. It consumes very little resources and might give some extra reward, so why not?

Running extra p2pool does not make any sense with Bitcoin: you'll likely be losing money.

Got it?

[markm]

Probably not, because getting it doesn't pay. Remember the old saw about getting things the getting of wihich undermines one's paycheque?

Maybe realsolid started out this way too, the extremism only arises as more and more realities keep getting in the way of the riches being gotten quick?

-MarkM-

[Sunny King]

You were told many times, that's the fundamental difference between PoS and PoW.

If somebody gets 1/4 of hashing power and runs it for a month, he loses LOTS of money in electricity/equipment costs and in number of coins he haven't got.

If somebody accumulates 1/4 of coin-age to perform double-spend, he loses almost nothing. A single CPU can be used to find matching chains, and all he loses monetarily is interest-on-interest, which is negligible, i.e. 1/10000 per year(?).

I am sorry I don't agree that the main thing protecting the network is the cost of the attack. I think the crucial thing is the exponentially diminishing success rate in the attack as users wait for more confirmations. Even if attacker doesn't pay any cost in the attack, users still may adjust and wait for more confirmations and that would make the attack pointless.

And you forgot another thing, such wealthy attacker has strong incentive to protect the reputation of the network. It appears to me that you are a proof-of-stake critic in general, you don't really agree with much of the opinions expressed in the bitcoin wiki page on proof-of-stake.

[Sunny King]

Ok I think I have got the message so there is no need to keep trying too hard. Let's just be polite and agree to disagree. I feel the critics are disingenuous as their main goal seems to be discrediting the design, rather than to help, as obviously v0.2 protocol is way stronger in the protection against double-spending than v0.1, yet none of them even care to mention this little fact.

v0.2 will be released by this weekend on schedule.

I guess we'll just have to see who is right in the market. You will have plenty of chance to prove it to the market you are right. I will gradually open up the checkpoint policy so you can attempt the attack you believe so much in. Fair enough?

Peace

[killerstorm]

You're again missing the point: this is how crypto research works. People try to find vulnerabilities. I'm sure that a person like Schneier would praise a person who would point at out a flaw in his design.

I'm not arguing with you, I'm just making this information public for people to see. If you don't take it into account it's your own problem.

While we are here, no, I'm not against PoS in general. In fact I'm a fan of Etlase2's Decrits design. (Punishment solves problem I mentioned.) Also I think Meni's design can work (i.e. strengthen Bitcoin's security), but it's rather complex.

I don't think that Cunicula's design is secure enough (although it's more like PoS+PoW so it does not suffer from same problems you have), but I believe it can be tweaked to make it secure. (Although this security will be a tradeoff.)

I can confirm that PPCoin 0.2 design is more secure than PPCoin 0.1: first version of PPCoin was just a brainfart (i.e. obviously insecure), this one actually warranted in-depth analysis. So you're making progress, kind of

I don't know whether your design can be strengthened, but keep trying

As for your economic argument, I believe it can be like prisoner's dilemma, where everybody knows that doing double-spends sucks, but everybody will still do it. At least, if they are rational in game-theoretic sense. Otherwise people might be bribed with Bitcoins to undermine PPCoin's security, and if they believe that it's serious, it would make sense for them to participate in attacks. Self-fulfilling prophecy.

Love

[Sunny King]

Fair enough. You sound like genuine now. I will definitely try to improve upon it if your concern proves to be valid.

Peace & Love

[foggyb]

v0.2 will be released by this weekend on schedule.

Excellent. Progress is good.

[Icoin]

Quote from: Sunny King on August 28, 2012, 06:49:52 PM

v0.2 will be released by this weekend on schedule.


Excellent. Progress is good.

Is v0.2 merged mining capable ??

[Jutarul]

Quote from: Sunny King on August 28, 2012, 06:49:52 PM

v0.2 will be released by this weekend on schedule.


Excellent. Progress is good.

Is v0.2 merged mining capable ??

Unlikely. The developer makes a point of ppcoin being a competitor, thus not relying on infrastructure for bitcoin.

[Sunny King]

Is v0.2 merged mining capable ??

Unlikely. The developer makes a point of ppcoin being a competitor, thus not relying on infrastructure for bitcoin.

Merge-mining will not be supported. The main benefit of merge-mining is to help a new crypto-currency to withstand 51% attack by leveraging the power of Bitcoin. This function is currently provided via our central checkpoint and will be provided by proof-of-stake protection in the future. So I don't see much benefit in supporting merge-mining.

As to competition to Bitcoin I think it is still far too early to consider that. Our goal is to first validate the correctness of the design in the market, and possibly bring some fresh air of innovation into the community. Personally I have very high regard of Satoshi and the current Bitcoin development team. Even if we do manage to become successful and compete with Bitcoin I still consider we are part of a bigger team in the grand scheme of things and doors are open to all kinds of possible cooperations.

[Jutarul]

Is v0.2 merged mining capable ??

Unlikely. The developer makes a point of ppcoin being a competitor, thus not relying on infrastructure for bitcoin.

Merge-mining will not be supported. The main benefit of merge-mining is to help a new crypto-currency to withstand 51% attack by leveraging the power of Bitcoin. This function is currently provided via our central checkpoint and will be provided by proof-of-stake protection in the future. So I don't see much benefit in supporting merge-mining.

As to competition to Bitcoin I think it is still far too early to consider that. Our goal is to first validate the correctness of the design in the market, and possibly bring some fresh air of innovation into the community. Personally I have very high regard of Satoshi and the current Bitcoin development team. Even if we do manage to become successful and compete with Bitcoin I still consider we are part of a bigger team in the grand scheme of things and doors are open to all kinds of possible cooperations.

Yes. With competition I didn't want to imply opposition. Competition is good, because it keeps the developers on their toes. If ppcoin and bitcoin are both viable, they surely will coexist.

[Sunny King]

Yes. With competition I didn't want to imply opposition. Competition is good, because it keeps the developers on their toes. If ppcoin and bitcoin are both viable, they surely will coexist.

Thanks. We also hope that our work on ppcoin could in the future provide healthy competition in the field of crypto-currency and help further advance this new peer-to-peer technology