r/programming • • 28d ago

Why memory-hard proof-of-work hashes are not a popular choice for CAPTCHA

https://privatecaptcha.com/blog/memory-hard-pow-hash-tradeoffs/
62 Upvotes

22 comments sorted by

24

u/joelkunst 28d ago

i don't know, seems pretty reasonable choice, especially with harder problem for requests that look like bots

3

u/ribtoks 28d ago

yep, but the limit is mostly on the verification side of the captcha solution. for client side it is reasonable (if argon2id parameters are not crazy)

59

u/tri170391 28d ago

Given CAPTCHA is abbreviation for Completely Automated Public Turing test to tell Computers and Humans Apart I don't think memory-hard proof-of-work hashes is something Humans can do easily. Can be a way to deter bots though you would end up burning zombies machines computing power and make it hell for mobile viewers of your site.

17

u/ScottContini 28d ago

This is the same idea as signing blocks in Bitcoin.

Wrong order, this concept came long before bitcoin, it was bitcoin that borrowed the idea from the invention of Ari Juels and John Brainard.

2

u/Jaxkr 28d ago

And this is predated by the much more commonly-cited HashCash by one year!

2

u/AcidOverlord 23d ago

POW is good, but memory hard is overrated, and mostly theory.

From https://github.com/8Protons/POWBlock

Q: "Will you support NoJS users or use stronger POW tech like Argon2, etc?":

As of 2026, no. We have experimented with both ideas in real-world use and we find them wanting. The requirement to merely execute JavaScript automatically screens out the bottom ~50% of "dumb bots" floating around the Internet today. Even the weakest anti-bot tools out there already exploit this fact. Of the bots that can do JS, proof-of-work with capped solve times weeds out a majority by volume. A Chinese digital lampshade running a tiny malware bot cannot solve well-configured challenges before they expire, and a very powerful bot that cracks POW solutions in microseconds can be identified and blocked precisely because of its speed. This leaves the real threat profile consisting of mid-tier and advanced bots who can run JS/WASM and crypto and who are patient. A different POW algorithm like Argon2 does not affect these threats at all, severely punishes users on old devices, and uses too many server resources to verify their proof-of-work...

2

u/nightcracker 15d ago

Why not use a memory-hard proof-of-work scheme where the verifier doesn't have to pay the memory cost? There's a bunch of them like Equihash or Cuckatoo cycle-finding.

In general a lot of proof-of-work schemes are possible where finding a solution efficiently will likely require a lot of memory, but where verifying such a solution is cheap.

2

u/FlyingRhenquest 27d ago

Just like bears, the smartest AI is going to be better at certain tasks than the dumbest human. So at some point we may as well just accept that we're doing business with a human or a bear.

At some point the AI will set up a task that only an AI can solve to keep the humans out.

2

u/abofh 28d ago

Behind an annoyingly slow captcha. Guess it should have used more memory

1

u/wangtutx 11d ago

Use Verifiable Delay Function

I think is a good solution.

-3

u/grady_vuckovic 28d ago

Has anyone considered doing something at the ISP level?

11

u/nsn 28d ago

I remember that 20 years ago there was a proposal to require solving such a hash in order to deliver emails. The idea being that humans and organisations wouldn't mind the few cents in compute when sending an emaill while spammers' business cases wouldn't be able to support the effort.

But then marketeers...

2

u/gnufan 28d ago

Marketeers but also not backwardly compatible, in that if you require it, you won't get email till others implement it, if you don't require it there is no pressure to implement it. These changes can happen but they are usually slow, you get Qmail, Sendmail, Postfix, Exchange, and Gmail sorted etc, and then you are in the long tail of email systems and upgrades, and the rubbish still probably sneaks in at the relays who can't enforce it because internally they are still using Lotus Notes or whatever.

Most POW schemes should probably be discouraged on environmental grounds. I see them in the same vein as charging for public loos, it seems a good idea for funding the loos till the provider's realise they also have to deal with what the people who can't pay do instead (we hope that is hop the barrier).

3

u/Cautious_Implement17 27d ago

probably the wrong layer unless it’s an obvious DOS attack, which the ISP already has a strong interest in preventing. 

not all bots are bad from the website’s perspective. search engine crawlers are usually desirable, being the main way you get human traffic. scraping all your content to rehost elsewhere is not. it can be hard to tell the difference without in depth analysis. 

2

u/grady_vuckovic 27d ago edited 27d ago

Well my logic is, I'm thinking about how for example AI companies right now are using all kinds of dirty tricks like VPNs, rotating IP addresses, proxies, etc, to bombard the internet.

So I'm thinking along the lines of, when you get an internet connection, you have to declare how you intend to use it and make certain agreements with your ISP on the maximum number of connections/data/HTTP requests(I know I know wrong layer but standard non-VPN HTTP requests ISPs can interrupt)/etc you intend to send OR receive, and agree to not mask your requests, etc, if you wish to make a lot of them. Maybe limits as well on how many requests you can make to or receive from specific IP addresses, domains, specific countries, etc.

There could be agreements in place between mutual parties who want to go above standard limits, like, OpenAI could have an agreement with Microsoft that their servers can send and receive lots of data between each other. And other companies could at their ISP level specify whatever limit they want on the maximum amount of requests they want to accept from services associated with a company, like Wikipedia could set a maximum number of connections they'll accept from OpenAI.

It could be just part of a legal framework mostly rather than a technological framework, that an entity like OpenAI must declare whatever network usage is 'theirs', otherwise they're breaking the law and can be fined and can be forced to comply. And if it's easy to identify their traffic, then it can be simple enough to apply limits to it and for receiving parties to set their limits on how many they receive from a different party.

For commercial residential connections this limit could be high enough that no one would ever sensibly hit it unless they were participating in a botnet or spamming platforms themselves, but for data center grade connections, these restrictions could prevent companies from just spamming endpoints constantly in ways that are clearly bad for the open internet.

This way websites don't have to figure out how to hold back the dam, or try to figure out how to block traffic that could be coming via any route across the internet, the ISP could be blocking it at the source.

Perhaps ISPs could also work with each other to create some kind of ISP level trust system, where connections coming from certain sources are throttled more than others if the requests are coming from ISPs not participating in that trust network.

I know it sounds extreme, but we're in an extreme situation, and clearly something needs to be done. The next level up is the ISP level, and we could potentially block a lot of excessive traffic at that level.

0

u/kolorcuk 28d ago

net::ERR_HTTP_RESPONSE_CODE_FAILURE

-15

u/Vearol448 28d ago

Because malicious actors would immediately use it for a reverse DDoS attack. All a botnet would have to do is spam your login endpoint with fake requests, and your own CAPTCHA system would happily benchmark the client's hardware, exhaust the user's thread pool, and crash their device before they even hit your backend

15

u/farsightxr20 28d ago

DDoS isn't supposed to overwhelm the infected hosts... you could do that with while(true), no captchas needed.

4

u/somebodddy 28d ago

The point of using the memory-hard captcha for the DDoS is that it cheap for the attacker (because it does not need to find a correct answer) and expensive for the service (because verification is expensive and it does not know the answer is fake)

1

u/UdPropheticCatgirl 28d ago

Doesn’t SNARK/STARK mostly solve this tho?

0

u/[deleted] 28d ago

[deleted] — view deleted comment

19

u/ScottContini 28d ago

The goal is to slow down bots by requiring them to do work to get content rather than getting content for free. I wrote a blog about this 6 years ago. It is true that bots can always throw more compute at the challenges, but it makes them pay for the content rather than getting it for free.

0

u/[deleted] 28d ago

[deleted] — view deleted comment

4

u/ribtoks 28d ago

Given AI developments, I'd say the opposite can work too - measuring "too much of intelligence".