Precomputed PoW attack

[harsh-deshpande]

The white paper talks about the precomputed PoW attack, but it doesn't offer a concrete way to tackle it. While such an attack can only harm the system temporarily, its effects can still be damaging for people wanting to use RaiBlocks for payments. The cost of such an attack will also come down drastically once we see ASICs for Blake2b coming out in the market.

We can increase the difficulty of PoW when that happens to prevent such attacks but that would severely hurt normal users' ability to perform PoW on their personal computers and mobile devices. So we want to be able to prevent a malicious attacker from precomputing the PoW while keeping the difficulty unchanged.

A valid block must have a nonce such that the nonce concatenated with the previous block's hash maps to a value below a certain threshold under hashing. Proof of work involves trying several different nonces before we find one that meets our requirement. We can roughly think of a number being below a certain threshold as having a certain number of zeros as its prefix. The number of zeros we require sets the difficulty of PoW. Suppose instead we require a random string of bits of a fixed length to be the prefix (instead of simply zeros) and the network agrees upon a different random prefix string every few minutes. However we keep the length fixed. Thus we make the PoW requirement dynamic, at the same time not making it any more difficult for honest users.

Since the attacker cannot know what prefix string to expect next, there is no way they could precompute the PoW any longer than the latency of a given prefix. The spam is still a nuisance but it cannot cripple the network. The attacker will have no choice but to give up on this attack because it is costing them money to perform the PoW while not hurting the network at all.

As for how to get the entire network to agree upon a prefix string without any form of centralisation, we could use other decentralised blockchains as seed to deterministically calculate the next prefix string. For example, the prefix string could be the first few bits of the hash of the latest bitcoin block. Alternatively we could have our own PoW blockchain that generates blocks with no transactions or rewards, but containing just nonces and hashes. The sole purpose being, to act as a seed for prefix calculation.

[BlackBeltBob]

If a block could be expanded to contain a timestamp, this problem would be easily solved by checking the average time between two blocks and increasing the PoW difficulty for a next block if the blocks preceeding it were broadcast close together. It could be a slight exponential increase that would rapidly make flooding improbably expensive.

[bradennapier]

Yeah I think this is the most logical. Providing a simple exponential backoff for consecutive transactions should be fairly straight forward and help to greatly increase the cost of such an attack.

[harsh-deshpande]

I agree, this might just work! Although, I'm not sure how it could work with exchanges or merchants who you want to be able to handle large volumes.

Also what's to stop an attacker from creating millions of accounts with small balances and then flood the network with transactions created by different accounts.

[PlasmaPower]

Blocks containing timestamps is a big challenge, because nodes can go offline. It's very hard to build consensus for timestamps.

[harsh-deshpande]

What if, instead of timestamps being a part of the blocks, they are stored locally (by the node) as a way to prioritise what transactions get processed first. The more PoW you do, the higher the priority you get. If the previous/source block was sent in the near past, you have a higher PoW requirement. Also, if the transaction amount is small, you are low on priority. A combination of these criteria could help the nodes compute a score for each transaction and process the transaction in the order dictated by the scores.

Of course this is all just a heuristic. The actual details would be far more involved. It might just turn out that the calculation of this score is more costly than simply processing the transaction. But in spite of the cost, this would prevent the junk transactions from being forwarded to the other nodes.

[bradennapier]

Another way, albeit far more involved, is to build a "Network of Trust" by having the ability to "rate" the partner after each transaction that occurs. In this sense, a user which has more "trust" of users across the network would be able to send more transactions without the PoW hit. In that sense, I would think exchanges would end up being able to send a lot of transactions quickly whereas an attacker with thousands of random accounts would have far less rating and would have to deal with the PoW issue.

[mbosecke]

OP was thinking of a way for the network to achieve consensus on a random value and I posted this idea which is to leverage the existing voting mechanism to do so: https://www.reddit.com/r/RaiBlocks/comments/7qpc5v/a_new_type_of_block_to_defend_against_precomputed/

[harsh-deshpande]

Thanks mbosecke. I also liked what PlasmaPower suggested on Discord. To paraphrase their idea:

Every x minutes, the reps broadcast a randomly generated nonce. You wait for 1 minute to hear all the responses. Sort those nonces by the respective rep's voting weight and take the first n nonces, concatenate them, hash them to generate the prefix. Of course not all nodes will have heard all the votes, but that's fine. The consensus for the right prefix will built by observing what transactions get approved by 50%+ of the reps by voting power. All the nodes will adjust their prefixes.

[Dekoze]

Main downside I see is anything regarding a dynamic pow target will also prevent regular users from taking advantage of cached pow. From a UX perspective a just-in-time pow calculation is less than ideal.

[harsh-deshpande]

What I'm suggesting is, at any given time, there will be k (=2?) prefixes that are considered valid - the most recent one and the k-1 previous ones. That way even if a user's device has already performed PoW for the previous prefix, it won't be rejected by the network as long as it was one of the previous k-1 prefixes.

[Dekoze]

I see, so then the trade off occurs in the value of k where you want to ensure the transaction frequency of an average account will still have a valid cached pow but not be so forgiving to allow a malicious user to accumulate significant precomputed pow's.

@bradennapier I think the representative stake is a decent analog for trust. Reducing the required pow for a representative proportionally could be a form of explicit incentivization that the XRB network is currently lacking. Without fees or new value creation within the network, current node incentives are relatively abstract and providing a mechanism to reduce the pow cost for power users could prevent a tragedy of the commons situation in the long term.

[harsh-deshpande]

I really like that idea. That would encourage merchants and exchanges to run full nodes. Not only that, it would also decentralise the network even more as nodes compete against each other to gain users' voting weight.

[bradennapier]

Exactly. It is akin to what built trust in commerce on the internet in the first place (ebays user rating system), but in a more decentralized fashion.

[cryptocode]

This sounds a bit like Byteball's main chain (a chain with total ordering in the DAG determined by trusted witnesses.)

[bradennapier]

Not too familiar with Byteball, but in my mind building this in a way that could then be expandable to general e-commerce could be huge. It would end up being a kind of "user rating system" for payments across the web rather than payments across a single website.

Obviously a huge amount of questions to answer though and a good amount of internal infrastructure that would need to be carefully built to support it. Although I see it solving a few problems that are being faced if built correctly.

I do know there were a few other things Colin said he liked as a solution when I originally discussed this idea with him, so not sure where that ended up for now.

[Derek123456]

With regards to the k value. Wouldn't that decrease the PoW required for an attack that is not pre-computed? If k = 2, then there are now 2 possible PoW prefixes that can be found. This halves the amount of work needed to find one of them. If k = 4 then there would be 4 possible PoW prefixes so you reduce the amount of work required by 4.

The alternative is to add the calculated nonce to each and every transaction so it's included before the PoW calculation occurs. That keeps the difficulty the same, but has the drawback of adding clutter to the transactions.

[harsh-deshpande]

Assuming k = 2, there will be 2 prefixes valid at any given time, the nth prefix and the (n-1)th prefix. All we need to keep track of is just 1 extra bit of information that tells you whether they computed the work for the even prefix or the odd one. This could be part of the work field itself. We could simply designate the first bit of the work field to indicate which prefix they computed the work for. One extra bit isn't that much clutter.

[rkeene]

I'm going to close this ticket as a duplicate of #506, even though that may not be the final implementation.

The discussion has been invaluable but we are unable to merge tickets with GitHub and we want to manage the issue of addressing spam with fewer tickets.

[bradennapier]

Oh @rkeene always the friendly descriptive gentleman. :)

I’m in Vegas where u at :-P