We've been over this again and again, the fact that he can try doesn't mean he will ever succeed but despite me providing the maths you just don't seem to grasp this concept.
It's exactly the same as the infinite monkey theorem http://en.wikipedia.org/wiki/Infinite_monkey_theorem.

The most precise you've been in the thread was saying:


Ok so this is the most "precise" attack vector you've cared to give me.
I guess your confusion lies in the fact that "occasionally" doesn't mean anything. Will you succeed once every month? Once every year? Once every billion years?

I'll keep it simple and if you really are interested in the subject and aren't just trolling against PoS, I'll be glad to further our discussion.

So let's say the attacker owns 20% of the mining coins (I'm giving you a pretty substantial amount!) and he tries to fork every two hundred minutes in the past.
For the attacker to have a maximum advantage let's also suppose that the attacker didn't mine on the main chain which means he's competing against 100-20=80% of the mining coins.

Over 200 minutes, in average, the main chain will have created 200*0.8=160 while the attacker will create in average 200*0.2=80
I understand where you're coming from, since there's no cost, the attacker can try many times so you might think that at "some point" he will create more blocks than the rest of the network.
This probability is the probability that a Poisson process of Pois(80) has more occurrences than Pois(160) (http://imgur.com/cYZ1SHE) which is ~10^-46

So now let's go back to what "occasionally" actually means.
You can repeat that every 200 minutes (I'll explain why underneath), so the expected time (in years) before you succeed such an attack is 365*24*60/(200*10^-46)~10^48 years.
How large this number is is hard to fathom, as a comparison, the universe is 13.8 billions years old (~10^9).

So if you try your attack "constantly" you'll never succeed.


I know you think you can try more than once, so let me explain why this is not possible.

Trying more than once means that you need to modify the kernel. The only thing you have control over, as an attacker in such a situation, are the parameters linked to the UTXO.
You can modify them, and to do so, you must at the beginning of the fork send your coins back to yourself. These coins will then not be able to create any block for 1.6 days. All the numbers I'm giving are clock time, not real time, so I completely agree you can "spoof" the clock compared to real time, I've been making this supposition all throughout the attack.
So after 200 minutes, your branch will have created exactly zero blocks, the blocks you would have created would be rejected by the nodes because the UTXOs weren't old enough to mine.


If you have any arguments that aren't based on intuition, I'd be glad to answer them.

What is that even supposed to mean?!?
What you're basically saying is that you actually haven't thought of any actual attack vector but "in your opinion" NeuCoin is not secure.

In this case, your opinion definitely isn't worth much.

hi kushti, sorry for the delay, I just posted an answer



Jonald, it's very dishonest of you to imply you proved any point in our discussion.

If you want to have a constructive debate, please provide a detailed description of the attack you think is possible: how many coins you own, what attack are you attempting (e.g. how many blocks you want to reverse), what are the different step of the attack etc. I'll be glad to give you a detailed, clean, step by step answer (with the maths) to prove to you that it's impossible and why.

Otherwise it's just you saying "I'm sure it doesn't work" and I can't possibly provide a counter argument to that.

It depends on what you call "a few blocks".
As you are aware of when owning less than 50% of the mining power (be it hash power or staked coins), your probability to successfully conduct the attack decreases exponentially when the number of blocks you want to replace increases.
So I guess we agree that to reverse any transaction of significant value, the attacker would need 50% of the mining power.

In this case I guess it boils down to: Could an attacker realistically "rent" 50% of the mining power?

While it might be possible in PoW if you suppose a very fluid hash rental market (it might be worth noting that this is not what Bitcoin is heading towards), in the case of renting the coins themselves, it sounds highly unrealistic. There will never be an escrow system with 1/ no limit to what you can borrow 2/ enough liquidity.

There's no technical flaw in your argumentation, I just don't believe this is realistic scenario 50% of the mining coins represents a significant portion of the coins. However, it's a very good point against coins with very low mining participation (and PoW!)



What do you mean look through? If you mean guess when your stakes will mine, the stake modifier prevents this.
Blocks do not need to have sequential timestamps. Anyone can broadcast a valid block at any time, however, nodes do not accept blocks created with a proof which time stamp is too far in the future.

I don't think it does, and I can't say I've ever seen this kind of argument against PoS before. The fact that the cost of a 51% attack scales with the market cap is a well known fact.
There is no reason for the "PoS analysis to give the same number". I'm not making any frictionless hypothesis in the case of PoW. If anything, I'm not taking into account the economies of scale that someone willing to buy the equivalent of 51% of the network's hashrate would enjoy.
The economics of PoW and PoS security are fundamentally different.
While borrowing the coins might seem like a better option than buying them, the security precisely lies in the fact that one cannot simply borrow 25% of the total currency. In our example, how would you go about borrowing $25B worth of coins? Let's suppose you could, I guess that in return, you would need a ~$25B collateral. Once you've attacked the coin and made the price plummet (unlike PoW, the attack can be traced back to you), I very much doubt you collateral wouldn't be seized. Therefore, the attack would still cost you $25B.
Also, in the example I gave, I haven't made the hypothesis than 100% of the coins were mining but only 50%.



By time weighting do you mean the use of coin age in the mining equation? If so, the goal was to diminish the variance of the mining process to encourage small stake miners to mine. It has proven ineffective to attract more miners and it greatly hurts the security of the coin.

Concerning the 1 second rule, it is enforced by the fact that the only parameter that varies with time in the kernel (PoS's equivalent of Bitcoin's block header) is the time stamp which has a 1 second granularity.

Hi Funkenstein,

Thanks for the feedback

The duplicate stake detection mechanism's purpose is to prevent miners from mining on multiple chain when a natural network fork occurs. Without this system miners could mine on both (or more) forks in order to avoid having their block orphaned and this would hurt the consensus.
It's not a security measure against people creating a fork in order to rewrite the transaction history.

 

The chosen inflation level is not the only parameter that matters.
If you consider a PoS and a PoW coin that are economically identical (market cap, inflation, transaction volume etc..) the cost of an attack will be orders of magnitude higher in the case of the PoS coin.
Let's imagine as you say that the PoW coin uses a 6% inflation rate to pay for security and both coins have a $100B market cap.

• In the case of the PoW coin, the cost of a 51% attack will be 51%*$100B*6%~$3B
• In the case of the PoS coin, let's suppose that with a 6% inflation rate, 50% of the coins mine, then the cost of a 51% attack will be: 51%*$100B*50%~B25$

And this doesn't even take into account the fact that in our example the actual inflation rate for the PoW coin is 6% whereas for the PoS coin it's 6%*50%=3%.
Therefore, the PoS coin is paying twice less for a security level ~8 times better.



I'm not sure I get what you mean by that? Your probability to win depends on the size of your stake.
Let's imagine you and I both own 100 neucoins.
If we mine separately, we both try once per second (therefore, together we try twice per second) to find a solution to:
hash(kernel)<target*100

If we put our coins together, we will once per second try to find a solution to:
hash(kernel)<target*200

So it's exactly the same as trying once per second to find a number between 1 and 1000 or trying twice per second to find a number between 1 and 2000. The odds of succeeding are the same.

Since this doesn't appear to be clear, we'll be updating the white paper with a more detailed explanation of why the attack you describe is impossible.
I think you're mistaking what the minimum stake age does. The fact that the attacker cannot mine when sending his coins to himself has nothing to do with the fact that the chain he's building will eventually be accepted or not.
I agree that this discussion isn't going anywhere so I hope you'll take time to give some feedback on the update version.

Exactly and that's the point I'm trying to make!
Every time an attacker sends coins to himself, his coins must wait minimum stake age to be able to mine. This will cause a lag that will make it impossible for an attacker to catch up no matter how many times he tries!
Therefore, to succeed an attacker needs the equivalent of ~50% of the mining coins.



From what I gathered from the thread, this attacker doesn't even try many times, he simply accumulates >50% of the block generation power.
He attacks a coin which has ~10% of coins mining and that uses coin age.
He was able to conduct a temporary 51% attack with 0.07% of the coins.
10%/0.07%~71
So what he did was just accumulate coin age for ~71 days. This is the reason NeuCoin doesn't use coin age.

In order to improve the whitepaper, I was wondering if you've read the technical part. I feel like maybe some points should be made clearer since I'm having a hard time making my point

Of course the attacker can try as many times as he wants I never said the contrary, what I'm saying is that he will never succeed


I guess we're having a hard time understanding each other!

Let's do it differently, if you want give me some hypothesis: total UTXOs the attacker owns, what kind of attack he want to conduct (i.e. how far behind the attacker starts his fork) etc. and I will prove you mathematically that he will never succeed if he doesn't own a very large portion of the mining coin.
The fact that he can try many times doesn't help him.
Otherwise, maybe you could describe how the attacker tries many times and what he does to get different outcomes cause that's the part that's unclear to me in your explanation.

I can't wrap my head around why this idea is so widespread. Maybe a detailed post should be written about it.
What do you mean by "it makes the richest richer"?
People earn coins according to the capital they've invested in the currency (be it in mining hardware or coins). How would you distribute a coin differently?
If anything, PoW is less democratic because people with access to capital enjoy high economies of scale, which by the way is the main reason why small Bitcoin miners are have been going out of business.

Because if he tries again with the same kernel, he will produce exactly the same branch.
I'm not sure if this is clear or not. The hash being deterministic, the only way to try again (i.e. to try to obtain a different outcome) is to change the kernel.

I deeply doubt that given the very limited understanding of PoS that Bitcoin developers have.
The very fact that when asked about PoS in his reddit AMA, Gavin simply provided a link to Andrew Poelstra's paper (Distributed consensus from PoS is impossible) which provides no solid proof whatsoever makes it very hard to believe that they are totally unbiased.

The issue with discussion about grinding is that as long as you don't go into specifics it's difficult to really make progress!!!
I didn't say it was "difficult" to compute but that grinding was made extremely inefficient.
An order of magnitude, is that an attacker with 1 ASIC miner (1TH/S) would need ~33% of the mining coins to perform a 51% attack while an attacker with the entire hash rate of the bitcoin network (~300PH/S) would need ~30%. That's what ennificient means.
The advantage you can get through grinding is highly non-linear.

More generally, it's difficult to answer objections about grinding if the argument specify through which parameter you are trying to grind.



What is difficult (actually probabilistically impossible without large portion of the coins) is to build a chain that is longer than the main chain at any point.
Let me explain, using a relatively simple example:
Unlike in PoW, building a chain in PoS doesn't take time. You could create a fork and know practically immediately what the trust of your fork will be X days from now.
Let's imagine you've got 10% of the coins. What is the probability that you'll be longer than the main chain after it has built 10 blocks? The answer is ~10^-6

From that, you'd be tempted to conclude that you can try again ("grind") many times and that at some point you'll win, because after all 10^6 attempts is nothing even for a laptop.
However, and that's where specifying what you grind through is important, the only way to "try" more than once is to change the kernel of your 10% of coins mining. The best way to do that is to change the parameters of the kernel inherited form the UTXO by sending all the coins to the fork. That's when the minimum stake age kicks in. It will prevent these stakes from mining for 1.6 days (in NeuCoin's case) so the attacker's fork will basically be "losing" 1.6 days worth of blocks he could've mined had his stakes been allowed to.

This period during which he cannot mine is devastating for his performance. It's similar to starting 1.6 days behind in PoW. With 10% the probability to succeed is null.

Maybe another thing I should point out is that nodes do not accept blocks created with a proof that has a timestamp too far in the future (otherwise forking would obviously be trivial).








Maybe I'm missing something, but it sounds like a self-defeating argument:

"We'll prevent this from turning into proof of work by making it really
hard to compute." 

Ok I think the reason why we had a hard time understanding each other is because you're talking about an entirely different implementation of PoS than that derived from Peercoin.
I guess it's closer to NXT's protocol although I'm not particularly familiar with it.

Explaining in details how NeuCoin's (and Peercoin's) implementation works would be too long to do here but you can take a look at the white paper (sections 3.1 to 3.2 starting page 13) if you want more details.

However, it's not possible to grind through stakes the way you described. Basically, the kernel (which is the equivalent of the stake modifier in Peercoin) is designed in way that prevents you from grinding in a efficient manner. This is explained in details in sections 3.3.3 of the white paper.



I thought Vitalik's suggestion of using security deposits were linked to the problem of users mining on multiple branches in case of a network fork, not of attackers trying to rewrite history. I should go take another look at his post

If you find some time to read the technical part of the white paper I'd love to get your feedback on the attacks and whether you think there are more efficient attack vectors.

A common misconception is that you can "keep trying". What do you mean by keep trying?
You can try creating forks at every block of the main chain but the probability to create more blocks than the rest of the network combined over a significant period of time (significant doesn't have to be more than say 10 minutes) is negligible you don't own a very large portion of the mining coins.
If you mean "keep trying" as in trying many times to create a fork at a given height, you simply cannot do that because the outcome will always be the same (since the computation is deterministic and the input is seeded on the mainchain). To get a different outcome and thus be able to "keep trying" the attacker needs to move his coins to the fork and that's when the minimum stake age kicks in.
This is what necessarily creates a lag.



What do you mean it can continue ad infinitum? What you're describing is basically the percentage of coins mining dropping to zero! This is not realistic assumption!
The blocks that should mine and don't are already taken into account in the computation because the attacker compares his stake to the total mining coins and not the total coins.

hi,

I guess it depends on mainly two parameters:

• The long term nominal interest rate.
• How developed the ecosystem of "mining wallets" (service providers that act as traditional wallets + insure a fixed interest rate to coin holders) will be.

During the infancy of the coin, since distribution is done through PoS reward (instead of PoW for Peercoin, Blackcoin etc...), the interest rate will be very high. Therefore, we expect the percentage of mining coins to be very high >80-90% (it's of course difficult to provide an exact number).
After the first years, as the coin becomes highly distributed - meaning most coin holders own <1/100,000th of the coin for instance - the role of the "mining wallet" will become increasingly important. The percentage of coins mining would probably drop to 50%, but this is of course only an educated guess.

Moreover, there are plenty of mechanism that could be easily implemented to increase the long-term mining participation without increasing the chosen maximum inflation.
For example, the mining interest rate could be a function of mining participation. Let's say a long-term inflation rate of 3% is deemed optimal and let's only 30% of the coin holders think it's worth mining for 3% a year, by implementing such a scheme, the miners' interest would be come 3%*10/3=10% . Therefore, the percentage of coins mining would increase and the inflation rate would be fixed at 3%.


PS: sorry I haven't answered your other questions yet. I'm a bit swamped but will definitely get to them when I get a moment

The reason this is incorrect is that there is no possibility for a "computer to calculate an alternate chain that started 200 minutes ago" and have it become longer than the main one.
What one has to keep in mind is that everything is deterministic.
For an attacker to build this fork he must own private keys that give him control over some stakes at the beginning of the attack.
Let's say the attacker has control over 10% of the mining coins. Two possibilities:

• These coins have been used to mine on the main chain. In this case, the stakes will create blocks exactly at the same timestamps then they did when mining on the main chain because since everything is deterministic, the proofs are the same.
  Starting our clock at the start of the fork, let's consider the average case (20 blocks mined by the coins the attacker control), the stakes have generated blocks at time 3,7,13,[...],189,198. Then the attacker's fork will consist of 20 blocks created with the exact same proofs.
  The important part is that since the fork will always be a subset of the main branch he will never be able to create a fork with more trust than the main chain. A second important remark is that the attacker cannot try his luck many time.
  
• The coins used to stake were not mining previously and in this case he would need in average 50% of all mining coins to be able to create a longer fork. This corresponds of course to a 51% attack.
  You might ask, if he gets his hand on 10% might he win? The probability that an attacker a fork with 10% of the coins will outperform the 90% remaining over a 200 minutes period is ~10^-100 (using formula on p.35 on the white paper). Therefore, this kind of event will never happen no matter how often attackers try.
  
• A third possibility would be to send coins you own the fork and mine with them. In theory, you could do that a great number of time and you might expect to succeed at some point. That's why the minimum stake age (i.e. the minimum time during which coins have to wait before they can mine) is important. For these coins to be allowed to mine they must wait a significant amount of time and this creates a lag. And this has a consequence on "real time" since the nodes receiving the forks will check if the proofs used to generate the blocks are valid.
  

The important part is that, you will not "not always be able to achieve this", you will actually never be able to achieve this without owning ~50% of the mining coins.


The reason behind this is that since you cannot "hope" to win be trying to fork a large number of time, the best thing you can hope for is to "grind" through stake modifiers, and to do that you must have control over the current stake modifier and this takes time.

Finally, what do you mean by "additional attack vectors"?

Hi jonald,

I'd love to go into details about the grinding attack.
Could you clarify a few points for me before we dig in so that I don't paraphrase the paper.
1/What do you mean by "creating a false chain"? Creating a competing chain? I'm not sure what "false" means here.
2/What do you mean by "time intervals can all be spoofed". Of course, the attacker doesn't have to "redo the work" if he can reuse some previously create proofs but in this case his fork (at the beginning) will be a subset of the mainchain.

More generally, could you please provide a detailed description of how you would conduct such an attack (even a high level explanation would be great)
thanks !

Debate going on right now on on reddit:
Jeff Garzik arguing against PoS

http://www.reddit.com/r/Bitcoin/comments/30t3k4/proofofstake_is_more_decentralized_efficient_and/