Pages:
Author

Topic: [PPC] PPCoin 0.2 Proposal (Read 6580 times)

legendary
Activity: 1205
Merit: 1010
August 31, 2012, 04:32:25 PM
#56
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  Smiley
donator
Activity: 994
Merit: 1000
August 31, 2012, 02:15:31 PM
#55

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.
legendary
Activity: 1205
Merit: 1010
August 31, 2012, 11:56:01 AM
#54

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.
donator
Activity: 994
Merit: 1000
August 31, 2012, 11:20:12 AM
#53
Quote
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.
hero member
Activity: 585
Merit: 501
August 31, 2012, 10:56:42 AM
#52
Quote
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 ??
legendary
Activity: 1708
Merit: 1006
August 29, 2012, 10:48:47 AM
#51

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


Excellent. Progress is good.
legendary
Activity: 1205
Merit: 1010
August 28, 2012, 03:29:29 PM
#50
Fair enough. You sound like genuine now. I will definitely try to improve upon it if your concern proves to be valid.

Peace & Love
legendary
Activity: 1022
Merit: 1033
August 28, 2012, 02:24:13 PM
#49
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 Smiley

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

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
legendary
Activity: 1205
Merit: 1010
August 28, 2012, 01:49:52 PM
#48
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
legendary
Activity: 1205
Merit: 1010
August 28, 2012, 01:20:13 PM
#47
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.
legendary
Activity: 2940
Merit: 1090
August 28, 2012, 12:29:18 PM
#46
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-
legendary
Activity: 1022
Merit: 1033
August 28, 2012, 12:12:14 PM
#45
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.

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

legendary
Activity: 1205
Merit: 1010
August 28, 2012, 10:14:07 AM
#44
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.
legendary
Activity: 1022
Merit: 1033
August 28, 2012, 07:27:14 AM
#43
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. Smiley

(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.)
legendary
Activity: 1050
Merit: 1003
August 28, 2012, 07:03:14 AM
#42

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.
legendary
Activity: 1022
Merit: 1033
August 28, 2012, 03:50:48 AM
#41
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.)
legendary
Activity: 1050
Merit: 1003
August 27, 2012, 11:37:24 PM
#40
There is quite a few factor playing here. It depends on how much coin age is actively participating in block generation (i.e. running the stake minter with a hot wallet). If an attacker manages to beat this total coin age then he indeed can force large reorganization. I would say it is still quite a difficult job for a 5% stake owner. Hash power is irrelevant here, as the v0.2 main chain protocol pretty much gives proof-of-work block a zero score. How long it would take him to do it depends on the average age of the coins protecting the network. If it's 6 months, then the 5% attacker probably needs at least a couple years to pull it off.

I don't know if this is correct or not because i don't know the details of your system (i.e. you say you are using pure proof-of-stake based on accumulated coin age, but I think you are using mixed proof-of-work/proof-of-stake). Let's assume it is pure proof-of-stake setting where coin age determines stake and hashing power is irrelevant. I'm going to assume you are doing this deterministically rather than via a lottery. [Some form of lottery might greatly improve things].

Let's make some assumptions to deal with the factors you mention. I'm going to assume that a unit of coin age is accumulated with every single block. I'm also going to assume 100% participation. I'm going to assume that coin-age is the only thing that influences mining success (say that stake mining has random elements but they are so small as to be negligible [as we will see this causes problems]). I'm going to ignore the existence of proof of work blocks and assume one stake block every 10 minutes. I'm going to normalize the total coin stock to 1.

Say there are n miners active, identical, legit miners each with a fraction c/n of all coins. They all actively participate. Due to symmetry, each miner mines 1 out of every n stake blocks and this occurs when he accumulates n stake confirmations. The amount of coin age which completes the winning block is  n*(c/n)=c.

[The miners are essentially waiting in a line of length n for there turn to mine a block. Each miner has a different position in line and they go back to the end after they reach the front. ]

There is also an attacker who holds all the remaining coins. His holdings are 1-(c/n)n=1-c. He does not mine, but waits to perform 6 block reorgs. To do this, he divides his coins across six accounts and each account holds (1-c)/6 coins. He waits w blocks between attacks. The interval is long enough to successfully attack if w(1-c)/6>c. Let's ignore discontinuities and approximate this with the equality condition: w=6c/(1-c).

How often can the attacker spring into action as a function of his wealth share, 1-c? See below

1-c        w
0.0005 11994
0.005   1194
0.05     114

So approximately the attacker who owns 0.05% of coins can strike once every 11194 blocks or about 4-5 times a year.
An attacker who owns 0.5% of coins can strike 40-50 times a year.
An attacker who owns 5% of coins can strike 400-500 times a year.

Thus, the concern that PPCoin is in the potentially worrisome daily double-spend category.

Note also that since mixed proof-of-work/proof-of-stake is not involved, there are no meaningful mining output losses for the attacker. He is just as efficient a miner as everyone else. Benefits from theft are in addition to his full legitimate mining income. (This is undesirable. Being sneaky like this should be costly. Introduce mixed proof-of-work/proof-of-stake and there are costs in terms of lost mining output.)
legendary
Activity: 1205
Merit: 1010
August 27, 2012, 11:43:56 AM
#39
You cannot stockpile hashing power. You can stockpile coin age.

Killerstorm's point is that stockpiling coin age allows you to double-spend periodically. (of course you can checkpoint every block to prevent this, but...). Whether periodic double-spending is practically relevant or not depends on how frequently it can occur. Obviously once a decade is not a problem. Once a year should be fine too. Once a day would be cause for concern (and might potentially motivate a revision of your design). I'm fine with once every week, but I suspect Killerstorm has more stringent standards. I have no idea what other people think.

The frequency depends on your protocol design and the attacker's resources. Say a wicked stakeholder owns 5% of all coins and 5% of all computing power. I'd say this is a reasonable benchmark attacker (quite well-endowed, but not ridiculously so). He doesn't ever mine except to execute 6-block long reorgs. Can you give us an estimate of how frequently the he can execute these 6-block reorgs? The arithmetic behind the estimate will be really helpful here becuase it will clarify features of your design.

If you haven't worked this out before you can check out the recent posts by killerstorm and I where we try to 'hash out' this property in the context of my scheme. I'm not sure exactly how your scheme operates, but perhaps the math is similar.

There is quite a few factor playing here. It depends on how much coin age is actively participating in block generation (i.e. running the stake minter with a hot wallet). If an attacker manages to beat this total coin age then he indeed can force large reorganization. I would say it is still quite a difficult job for a 5% stake owner. Hash power is irrelevant here, as the v0.2 main chain protocol pretty much gives proof-of-work block a zero score. How long it would take him to do it depends on the average age of the coins protecting the network. If it's 6 months, then the 5% attacker probably needs at least a couple years to pull it off.

It's more difficult to do a formal math analysis as in Satoshi's case. So I am in no hurry to offer such an analysis.

I actually think the bitcoin wiki page about proof-of-stake is quite well-written and I generally agree with the opinions expressed there. I am not as paranoid about this supposed large double-spending attack as I classify it on the same level of a 51% attack on proof-of-work. In terms of defense against some powerful institutions, I think it might turn out to be stronger than Bitcoin as it buys time for the stake owners to bail out and they can even use the profit to do some other good cause.
legendary
Activity: 1022
Merit: 1033
August 27, 2012, 11:37:11 AM
#38
As I understand, here's a formula (with a bit of description): https://github.com/ppcoin/ppcoin/blob/master/src/main.cpp  CTransaction::CheckProofOfStake

This is somewhat different from Cunicula's proposal (particularly, one cannot iterate nonce to find matching hash), but it can be attacked in a similar way: attack should split his coins into many transactions, wait until they are mature enough and try to find a chain of matching blocks.

Numeric analysis is somewhat tricky (i.e. it takes more than 5 minutes), but a general idea is that if people do generate proof-of-stake blocks often, attacker having many aged coins will have an enormous advantage. I'll give you a hint: he can try to build many different chains out of his transactions, like billions of different combinations.

But I have no incentive to do a full analysis before a release.
legendary
Activity: 1050
Merit: 1003
August 27, 2012, 11:21:16 AM
#37

Cunicula also thought it's true, but I've demonstrated that one can easily manipulate things into his favor. Additionally, it turns out that total coin-confirmations is a totally meaningless metric: what matters is average coin-confirmations, and you can beat the average by waiting a bit.


The first part is true. However, "A bit" is misleading. Depending on the design specification, "a bit" could refer to two weeks, two years, or two thousand years.
Pages:
Jump to: