Anti-spamming hash-based proof-of-work?

Question

I'm planning to implement a public mailbox for receiving feedback, and I'd like to use hash-based proof-of-work to frustrate spammers.

First, we want to use 320-bit capacity Gimli permutation as the underlaying primitive for the sponge-based hash function, because

1. I don't want to make it hard for server to re-evaluate KDF each time there's a message,

2. it's not available on commodity hardware, which means someone will have to pay for silicon to have it accelerated,

3. less parameters to tune (capacity/rate and preimage length).

Second, for each message, there will be a time-based challenge (server will allow a small window for error) prepended to each message to be hashed and sent to deter pre-computation attacks.

However, there's a few things I'm not confident about. Namely:

1. Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?

2. Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?

Answer 1

I agree with e-sushi that PoW does work, however, the primitives used by HashCash are too friendly for adversaries. As the OP pointed out we need contextually bound challenge and response that cannot be reused or precomputed.

We cannot prevent the work from being delegated; but we can make the PoW much more expensive than an ASIC friendly hash function. The argon2 KDF family is well suited for this, specifically argon2d which was designed for PoW; whereas argon2i was designed for secret passwords.

The memory and cpu parameters may be tuned individually such that no real users are too inconvenienced and the server is not overwhelmed when under load.

Instead of requiring the PoW be computed 100% of the time, you might only require it while the server is under load. This may not apply to your use case.

1. Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?

Advantages:

• Increase adversary costs

Disadvantages:

• Inconvenience users (less than a captcha)

• More code running on the user's client, inconveniencing users who opt to disable JavaScript

• Drain the power of user's mobile devices

• Adds additional computational costs, increasing power consumption for minimal benefit

2. Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?

• Remote delegation to unsuspecting users (like recently cryptominers on government sites)

• Deniable of service. The adversary may produce fake solutions without trying. The server still performs the computational costs.

Alternatives:

• Enable the user to send money as a micropayment. This scale will require a high performance ledger, or better many ledgers. On the other hand, an adversary may have enough money to burn, possibly stolen.

Answer 2

I have to contradict the other answer by DannyNiu which wrongly states POW (proof of work) does not work here.

It does.

As a matter a fact, you are about to reinvent the wheel. See HashCash which was invented to do exactly that.

Quoting the related Wikipedia article :

Hashcash is a proof-of-work system used to limit email spam and denial-of-service attacks, and more recently has become known for its use in bitcoin (and other cryptocurrencies) as part of the mining algorithm. The original idea was first proposed by Cynthia Dwork and Moni Naor and Eli Ponyatovski in their 1992 paper "Pricing via Processing or Combatting Junk Mail". Later a similar proposal called Hashcash was proposed in 1997 by Adam Back.

For further reading, check

• Pricing via Processing or Combatting Junk Mail
• HashCash

---

As I noted in my comment

Everything can be automated, even captchas. Looking at how frequently captchas services like Google's ReCaptcha get reverse engineered and their captchas hacked, you might as well simply use POW with a tweakable parameter or two.

Answer 3

POW don't work here because:

POW only allows trivial verification of non-trivial computation being done, most of the schemes as of 2018 cannot verify that the computation is being done by an honest party oneself.

Computation of hash functions are easily outsourcable (interested readers may see this), and there are bitcoin mining trojans abusing both the bitcoin blockchain system and ordinary unwilling computers.

What really should be done to deter spammers, is to use (a moderate amount of) tracking cookies, check "Referer" header, use POW and CAPTCHA, and finally Baysian network, combined together as layered security measure.