[Debunked] Stake grinding (bitcoin wiki is wrong)


#1

The following is wrong:
“There are also “stake grinding” attacks which require a trivial amount of currency. In a stake[2] grinding attack, the attacker has a small amount of stake and goes through the history of the blockchain and finds places where their stake wins a block… Because this attack exists… Peercoin[3]… have “master” public keys that control the blockchain.” (https://en.bitcoin.it/w/index.php?title=Altcoin&action=history)

I’ve learned about this attack vector a few days ago. The first thing I did was to search peercointalk, to see if it had been discussed but I found nothing. Therefor I want to make a post now, so that other that hears about it, can learn Peercoin is not susceptible to this attack.

This is not something that I’m just saying, I asked both sigmike and Sunny King, who says that stake grinding (or stake-grinding) won’t work on Peercoin.


#2

Anyone have access to the bitcoin wiki and some kind of political super that makes it possible to update the wiki?


#3

Stake grinding is interesting, one of point that make me curious is buying old key/stakes while they are interconnected. Maybe stakes ~blending is worth exploration as a part of security?
Maybe we should (randomly?) reward past minting keys to discourage selling them, and/or consider coinjoin/mixing as security measure.


#4

[quote=“kac-, post:3, topic:2502”]Stake grinding is interesting, one of point that make me curious is buying old key/stakes while they are interconnected. Maybe stakes ~blending is worth exploration as a part of security?
Maybe we should (randomly?) reward past minting keys to discourage selling them, and/or consider coinjoin/mixing as security measure.[/quote]

I’ve come to realize that there are two different versions of this myth. One is about there being hashes that could be attacked. The other is about grinding through probabilities and thereby building very long chains with only a limited amount of coin age; this myth being busted as well, because it is not the longest chain that wins, but the chain with the most coin age consumed.

Where did I go wrong? If I didn’t go wrong, are you talking about another sort of attack? I’m confused. Could you help me out here (I don’t even know what stake blending is)?


#5

Chain trust is calculated from diff not coin age https://github.com/ppcoin/ppcoin/blob/master/src/main.h#L1275


#6

Chain trust is calculated from diff not coin age https://github.com/ppcoin/ppcoin/blob/master/src/main.h#L1275[/quote]

wait what… in http://peercoin.net/assets/paper/peercoin-paper.pdf it reads:

The protocol for determining which competing block chain wins as main chain has been switched over to use consumed coin age. Here every transaction in a block contributes its consumed coin age to the score of the block. The block chain with highest total consumed coin age is chosen as main chain.

What is wrong here; the white paper or the source code? Or is it something that I’m missing?


#7

mmmhhh… there’s a difference, but…
The total consumed coin age" means: coin age times number of coins

To meet the difficulty you need a valid coinstake kernel.
To have this kernel you need an amount of coin age.
So the total consumed coin age and the difficulty are connected with each other.
The thing is: to meet the difficulty you can comsume much more coin age than it would be required.
Saying “the total consumed coin age” decides which fork clients will choose is not 100% accurate, but in fact it is even safer for the network to decide which fork to choose based on difficulty (as this limits the possibility to attack the block chain with huge amounts of coin age even further).
I don’t know (maybe Sunny can tell), but the whitepaper might be from a time when the protocol has been different from now?


#8

Stake grinding [SG] states that you can pre-compute future, or post-compute history, winning chain using small amount of coins- making Peercoin a PoW coin.
PoW is wrong, more PoS * PoW.
The SG assumptions is that computation is cheap - is false, it’s diff * price ( old keys also have price: demand / supply ).

SG forms:

  • passive - collect set of outputs, don’t use them until you find your lucky streak (by searching some limited future)
  • active- rewrite at least 30 days of blockchain
    ** more he re-write - more he controls

What can be done against:

  • increase diff (mint, minting wars[capped coinstake reward])
  • decrease supply of past keys eligible to attack (coins circulation)
  • increase price of past keys by creating (false)demand

Decreasing # of old keys (coins circulation):

Attacker bought 2 keys, A and B, with 100 and 90 PPCs(in the past) respectively.

The issue is that after A key was spent 1 from 100 PPCs landed(probably through many transactions/exchanges/betting sites/mixers) as input of key B value. Attacker cannot use B key because if he want 90 PPCs w/ B - he need to spend A ( include tx spending A in attacking chain ) and lose control over 100 PPCs.

http://i.imgur.com/t0K7YvR.png

A: P1abc…
B: P3zyx…
Attacker can:
exclude tx X, keep A, lose tx Y and B
include tx X and tx Y, lose A, keep B

Keys with coins that were mixed with coins from other minting stake of attacked chain are useless too.

Coins circulation limits (past)stake eligible to attack.


#9

What would be consequences of calculating BlockTrust as diff * stakedAmount ?
—edit—
Answer: easy attack
[s]
maybe diff * sqrt( stakedAmount )

diff=1
6 blocks w/ 1 PPCs -> trust=6
6 blocks w/ 10 PPCs -> trust=19
6 blocks w/ 100 PPCs -> trust=60
6 blocks w/ 1000 PPCs -> trust=190
6 blocks w/ 10000 PPCs -> trust=600
?

[/s]
or diff * log stakedAmount

BTW, about BUSTED http://www.peercointalk.org/index.php?topic=2976.msg27789#msg27789
State of the blockchain is deterministic thus it can be a subject of pre/post computation, times and heights can be selected, one bit from block hashes is taken to stakeModifier so there is place for some play. The question is how complicated those computations are[memory and CPU requirements] relative to possible reward?
IMO: it may be more resource-intensive than BTC mining.


#10

That’s where some of the work that the Ethereum team was putting into the “Dagger” and “Slasher” hard-memory algorithms were interesting. I think that, eventually, there’s going to be a benefit from continuing to tweak the proof-of-stake algorithm that Peercoin uses to make it harder to pre-compute a block given a specific difficulty.


#11

I find the answer to that question here:

[quote=“kac-, post:8, topic:2502”]Stake grinding [SG] states that you can pre-compute future, or post-compute history, winning chain using small amount of coins- making Peercoin a PoW coin.

SG forms:

  • passive - collect set of outputs, don’t use them until you find your lucky streak (by searching some limited future)
  • active- rewrite at least 30 days of blockchain[/quote]

In my myth busting thread, I would like create something similar to a user story for the attacker. Like what’s the step the attacker needs to take, why and the implications of it; all presented in a way that someone that have not read the white paper, not read the source code and are unfamiliar with key concepts can understand or at least use a platform for further studies. I’ve found some answers spread across many threads, but I fear that my ignorance and stupidity makes it impossible to do this without help from you gurus. This is as close as I can get:

  • The attacker want to create a reorg of the blockchain let’s say 6 blocks deep. The blocks will be broadcasted to the net, only when the attack chain is fully built and the attacker knows that it will win over the main chain.
  • The attacker has prepared for the attack in advance (90 days), creating at least as many unspent outputs as number of blocks the attacker wants to create during the reorg. This is required because the coins used in the stake in a successful mint will loose all coin age and not be possible to use again before 30 coin days.
  • To create a block, a hash is produced that has to meet full-fill certain criteria, such as creating a hash that meet a target difficulty. The recent blocks in the blockchain can not be exploited to change the hash, because when creating a block, the data used in the hashing is obtained from the block where the unspent output was registered (first confirmed), which is out of control for the attacker.
  • The only thing that the attacker can really manipulate when generating the hash, is the clock time because the protocol allows for some degree of clock drift. This implies that when the attacker search for a hash that meets the required target difficulty, the attack can go through the “clock space” available to improve on his chance to find a block.
  • Because the protocol doesn’t allow the hash to be changed (save for manipulating the clock), the attacker need to increase the coin age of his coins to improve on the odds of successfully carrying out the attack.
  • While the reward for a proof-of-stake, increases over time as the coin age grows, the coin age that the coins can use in the stake is capped at 90 days. This means that the attacker can not supercharge a few coins. To get more coin age, the attacker is forced to get more coins.
  • How much coins are needed? To replace the main blockchain, the attacker needs to create an attack chain that has more accumulated chain trust, then the main chain. On the main chain, all minters are competing with each other to win the block and the winning stake is the one that consumes most coin age (and is able to meet the difficulty target). The attackers attack 6 attack blocks, must have more chain trust together, then what the winners stakes contributed to the main chain during the same period.

What happens next, depends on what answer I get here:
http://www.peercointalk.org/index.php?topic=3090

  • Since we don’t know how many people will be minting and what coin age the winning stakes will contribute to the chain trust, we can for the sake of argument assume that XXX with difficulty XXXX with means that the attacker must have XXX coins for each block.
  • In the original Peercoin implementation, the attacker could also increase his own chance of success, by making it difficult for other minters to win, when creating his block, but a stake modifier has been introduced which uses data that is not available at the time attacker is creating the block that makes this much harder.
  • Besides, this there is not much that the attacker can do in terms of exploits of the protocol, to improve on his chance to find a block. The only option left for the attacker is to get his hands on as much coin age as possible and distribute them as 6 unspent outputs.

As you can see I’m both ignorant and stupid. Please, please help me correct all the errors in the story above.


#12

I would make SG that way:

  1. Prepare stake
    a) buy old minting keys
    b) buy old not-minting keys and mint blocks for 16 days (64 6 hour long stakeModifier intervals)
  2. Create 64 tuples (stake-selected-by-modifier, signature1, signature2), signatures that give different first bit of block hash
  3. Brute-force this 64 bit space:
    a) re-create chain w/ new signature
    b) mint on top of it for next stake modifier interval
    c) choose best/satisfying chain trust, remove oldest (block, sig,sig) tuple from 64 set, add new one
    d) repeat from (a)

    e) optimize, pray for more trusted chain, if not- take next ~bit combination and goto 3.a)

Can core-dev verify this flow? May run parallel.

Or go full-random and mix and mint till you win.

Attacker needs 7200+ outputs, to cover whole 64 bit space he needs (2^64 - 1) * 7 200 = 1.32 * 10^23 (10^8 peta) stake-hash / calc-sec, right? With time he’ll narrow his initial search space but to fight-the-random he’ll need to create computation branches from his best chains. IDK, leaving this thread until someone optimize it.


#13

Bump - valid or not?


#14

If you manage to find 6 blocks, it’s not very hard to beat the main chain in having burned more coin-age, therefore having more chain trust. Look at the sample I posted here. Most found stakes have reward < 0.3PPC , meaning the coin-age consumed was less than ~10,000 PPCdays.

The difficult part is finding those 6 blocks. Time drift can only give you two extra hours of minting time. Compared with many months time it usually takes to find a block, this advatage is trivial.


#15

Bump - valid or not?[/quote]

Re-bump. [member=30141]sigmike[/member], [member=79]Sunny King[/member] coud you give us an answer to [member=28723]kac-[/member] post?


#16

Re-re-Bump!

[member=79]Sunny King[/member] [member=30141]sigmike[/member]


#17

re-re-re Bump!

@Sunny King @sigmike