POW Captcha: a lightweight, self-hosted proof-of-work captcha
git.sequentialread.com
git.sequentialread.com
It's perfectly possible to make a memory hard PoW that's instantly verifiable, by using something other than hashcash. Examples include Cuckoo Cycle [1], and Equihash [2]. These can easily be made to use hundreds of MB in solving, while verification is memory less.
1. LSAT[1] support for micropayments (recently mentioned on HN[2])
2. RandomX[3], mining XMR for the site owner
Both provide something useful, replacing advertising and/or subscriptions for the site owner, rather than solely wasting energy. Let's eliminate captchas and advertising together.
[1]: https://lsat.tech/ [2]: https://news.ycombinator.com/item?id=28459713 [3]: https://xmrig.com/docs/miner
Any mining-based payment will inherently be worse and less efficient than a money-based payment, especially for mobile.
Excellent for preventing spam: https://twitter.com/lntxbot
I mean, if that's an intentional exception for personal scripts, that's awesome, but it doesn't really seem to serve the expectations of a CAPTCHA then.
Also, while I like the idea, I fear this could stop working in the long term.
With cryptocurrencies, PoW works because the "good guys" (miners) and the "bad guys" (double spenders) have equal access to computing power: If the difficulty increases, both can simply add more mining hardware and stay in the game. If the "bad guys" threaten to get an advantage, the system can always increase the difficulty without risking to lock out the "good guys".
With CAPTCHA, the situation is different: Here, the "bad guys" (spammers) still have as much computing power available as they can buy and stuff in their data center. However, the "good guys" (regular users) have hard constraint: They have to use whatever hardware the browser runs on (which might just be a smartphone) and they can't spend more than a few minutes to solve the puzzle - otherwise, the user will probably grow impatient and give up.
This means, you can't easily increase the difficulty of the puzzle without locking out regular users. If the captcha grows popular, there can easily be a situation where you'd make the captcha unsolvable for all regular users ling before it would become unsolvable for spammers.
No Bitcoin PoW works because of economics and game theory; it is rational if group of people invested a lot of resources into mining and building consensus that they will stick to that consensus in order to preserve their wealth.
Read what Satoshi said in the Incentive section of the Bitcoin Whitepaper: "If a greedy attacker is able to assemble more CPU power than all the honest nodes, he would have to choose between using it to defraud people by stealing back his payments, or using it to generate new coins. He ought to find it more profitable to play by the rules, such rules that favour him with more new coins than everyone else combined, than to undermine the system and the validity of his own wealth."
I mean, even in the regular, non-crypto economy there are lots of products that are sold at a loss for strategic reasons.
But you're right, that explanation wasn't quite correct. My point was that cryptocurrencies rely on the assumption that all legitimate users taken together have more computing power than a typical malicious user. That assumption is supported by game theory and made use of with dynamic difficulty adjustment.
However for a PoW captcha, the assumption does not hold: The captcha has to be solvable by WASM on a smartphone, otherwise it would lock out legitimate users. And that is a pretty low bar for an attacker to meet, computation-wise.
But yeah, this seems like a way to archive something similar with potentially less complexity. (If you're willing to tolerate the wastefulness, which is still not cool in the age of climate change).
A challenge could be correctly invalidating a nonce. You don't want an attacker to reuse a previously solved puzzle for multiple requests - on the other hand, it's difficult to set up a good "time to live" for a nonce as you can't know in advance how much time a user would need to solve this nonce.
So I guess some global state to track recently "spent" nonces would be necessary.
Isn't this already the case with other captchas where you can pay people to solve them for you? You could easily build a programmatic solution for that. If you're willing to "invest the work", nothing can really stop people automatically.
But I think the problem is that a PoW captcha can be cracked significantly more easily than a regular captcha:
For a regular captcha, a spammer would have to deal with brittle image analysis software or find people willing to do extremely boring, borderline illegal work for pennies.
For a PoW captcha, they have to load the page in Selenium and... that's it. All that's left is a slight bump in the power bill.
Barriers to entry. Different services will require different levels of security. This might be enough for a simple poll app.
If you're a script kiddy who knows how Selenium works, you can crack this.
What this does for resource-poor attackers is implement some wasteful form of rate-limiting. But then, why not just use actual rate-limiting?
It works, the thing is that "working" in that case is to increase the cost of doing this. Solving 1000 captchas costs $2 https://anti-captcha.com/.
The difference here is that people that have no money can automate selenium on their own computer and defeat a PoW captcha. But for people that have to pay for either servers or a captcha solving service, there is no difference.
With a PoW captcha, it doesn't matter how smart you make your algorithm, it's still going to be slow. With existing systems I'd argue it's probably a lot slower for people than for machines, especially since it's people guessing what a machine thinks people would classify an image as.
This is an easy solution for rate limiting low trust/high risk connections and better software isn't going to magically make it any faster. This has always been what captchas aim to accomplish.
Hell, charge me one penny per refresh and a dime per tweet and login attempt. Then let the bots run freely if they're willing to pay that rate.
Seems like this might exclude users lower-end electronics that might be low-income.
You can have it turn itself off during a normal "1 request per minute" day on a small blog and then crank up to "A new CPU needs 2 seconds" during a DDOS.
Use token bucket or leaky bucket or whatever so a few normal users clicking around for 10 minutes won't trigger it, but after a while the server runs out of patience if they keep making requests faster.
Turns out when you zoom a picture in far enough, large bus windows, train windows, and building windows all look very similar.
There are obviously UX challenges to making it easy to acquire the crypto, but I could imagine this starting as an optional alternative to captchas.
Yea micropayments were Satoshi's vision. For example you could pay like 1/100 of a cent to unlock and bypass captcha puzzle.
Suboptimal and an inefficient use of resources, yes, but possibly the only way to combat bots without privacy intrusive services. I'm open to hearing alternative ideas, though!
Bots will trend towards resembling real users exactly.
All you can really do is make it expensive for a bot to spam requests. Everything else will be identical to humans one day, and in the meantime it's annoying to block legit Tor users or legit scraper bots.
Then you just need to make sure your algorithm is also space-hard and resists parallelization so GPUs and ASICs can't get it.
Basically it's a password hash, like Argon2. I think libsodium already has an official WebAsm build, so there you go.
Web browsers also have "crypto.subtle" but it's not allowed on file:// (making testing on local difficult) and I don't know if it has password hashing.
Generating 1MM units of PoW will always be more efficient than 1MM people generating each 1 unit of PoW.
Optimization always works better at scale. Therefore an attacker always has the upper hand.
PoW is absolutely useless as a CAPTCHA and doesn't even do what C.A.P.T.C.H.A. says.
Check out this guy on YouTube, he can pretty much open any lock in thirty seconds without causing any physical damage, will change your whole perspective on security.
https://youtube.com/c/lockpickinglawyer
It’s better to plan for people getting in then depend on preventing it.
If someone wants to make 10,000 accounts, I'd rather it cost them 5 cents per captcha solve, $500, than for it to be free.
Some attackers can make it pay off, but many can't, so they don't try. That makes my life easier, as I'm the one being paged during an attack.
I assume attacker doesn't need the accounts immediately. I also assume that a real user will wait at most 10 seconds when creating an account on their old underpowered phone.
So the attacker could either wait 27 hours (10*10000 seconds) to do the attack, which for most attacks wont matter much. Or they could use some high powered aws instance that's 100x as powerful as the phone and wait a few mins (aws pricing aint that bad if you just need 5 min of compute time).
Yes it increases "costs" but not by very much and not in a way that scales
It is true that it can still be annoying for extra CPU work though (and may waste energy), and if they both disabled scripts/workers and also won't or can't do otherwise despite that it will still be denied access.
An attacker can easily an cheaply generate way more PoW than a legitimate user by optimizing their system.
This is just an "unskippable" delay timer not a CAPTCHA!
It does not. Its broken the day someone who can code wants to beak it.
>The user is not as affected by the cost...
Its exactly the opposite it affects the user not an attacker who can generate millions of PoW units on toaster for a few bucks. Or even use another systems idle time. No human needed == its super cheap. Unlike real CAPTCHAs where you need to pay real people to solve them.
Beating the average smartphones in-browser hash power does absolutely nothing. You are not competing against them you compete against large scale mining farms with special hardware.
However that's not possible with Scrypt, especially with the relatively large memory cost and block size parameters that this software uses. Even GPUs choke on scrypt at these levels. See: https://www.mobsec.ruhr-uni-bochum.de/media/mobsec/arbeiten/...
Even in the absolute worst case where no optimization is possible at all the attacker can still run a device 24/7 so if a normal user has to wait 20 second on a smartphone an attacker can spam at least 4320 messages per day with the same device. And it scale at least perfectly linear. 2 such devices would double the spam capacity.Aand if the block sizes are increased to slow the attacker down it is exactly as much as it slows down the real user. But the real user actually cares and gets annoyed the attacker does not, he keep the same spam/legit message ratio.
Because of improved interfaces to exploit the poor, a spammer can already pay to have humans solve captchas using an API, just as well as they could pay for computing time to solve hashes.
As such, if you were to tune the difficulty of a computing proof of work to be more expensive to compute than to pay the lowest bidding human farm to solve a captcha, it should be better at decreasing spam.
If you would raise the PoW to cost more than that the average user would simply be unable to solve the PoW it in a meaningful time on their hardware.
So if I have 100 cores available, I can run 100 sessions in parallel.
For a determined or resourceful attacker, this alone won't be good enough defense, but I can see it being a layer of defense in depth.
Type of spent resource is rather irrelevant, isn't it?
Any waiting period for calculation that won't annoy users is not long enough for an attacker to not still be able to spam, given that they will be solving them 2-100x faster with an optimized native implementation vs in a browser.
It also doesn't work as a turing test, because by their nature computers are good at batch solving proofs of work.
I once started an anonymous email service with browser-based PoW for antispam. It didn't work.
You'd need users to do like, several hours of in-browser PoW to make it viable as an anti-abuse measure. Anything less means a bot farm is posting spam dozens of times per hour.
Frictionless micropayments are still a pipe dream today, as any useful technology available to do so has basically been outlawed in the USA without a multimillion dollar license, and a KYC department, et c. It's a real shame because we have all of the technology for cash-based anti-abuse bonds and the like. It's just illegal to deploy it unless you go full MSB.
Not only is it a total privacy invasion, all the burden is borne by the service providers for implementing the government’s universal financial surveillance.
Spammers aren't sitting there at an interactive session, waiting to create an account while staring at a spinner.
Native code is not "2-100x faster" than WebAssembly. That's what I wanted to address.
How much slower is it?
The animated demo shows this perfectly. The bar which is showing the progress in the proof of work could just be a simple timer, and it would look exactly the same.
The back end generates the page, and makes a note of the current time. Then it doesn't accept the submission until N seconds have passed since that time. The animated bar on the front end is just for show; the browser isn't what is enforcing it.
Proof of elapsed time requires nothing from the other party. If I want proof that you spent at least 30 seconds waiting from the moment I gave you some starting signal, the only evidence I need to trust are the readings of my own stopwatch.
And so, that's why we need proof of work; thank you for bringing my derailed narrative back on the proper technical track.
Makes a note where exactly? In a data store? That means that I'm allowing an untrusted entity to trigger an action that requires me to store and later query my data store. That's a bad idea. The whole reason to have a captcha at all is to stop bots from overloading your system. The data store is a major bottle neck in most systems.
Proof of work is stateless. It's fast to verify. If you sign the challenge input before giving it to the user, you can also statelessly verify it's a legit challenge. No data store needed until after verification is complete.
Edit: also what ahsima said! The point of a captcha is to make it more expensive to use a bot net against you. Timers don't do that.
This stateless principle is implemented in TCP SYN cookies for warding off SYN flood attacks, for instance.
Thank you, also.
Good thinking!
But I'm curious if it might need more work in the 'accessible' area. Like, for example, is the progress bar percentage-done exposed in an accessible way? I don't see anything obvious here: https://git.sequentialread.com/forest/pow-captcha/src/branch... , seems like it just changes width via css styling, but I could be missing it. I'm not sure it presents an easily understandable reason why the submit button is disabled, that you need to wait, etc, either.
So I don't really have a great way to make it accessible to blind users at the moment, but it's only a couple code changes away, while most other "Captcha" solutions might require a redesign before they could be considered accessible.
That's a problem; captchas need a fallback mechanism for situations when JS is disabled.
(I think that could be arranged; e.g. in the no JS case, the web application just spits out some token, which the user must copy and paste into some program that does the work, and then passes the answer back into the web application.
This project is also cool: https://git.sequentialread.com/forest/greenhouse
A reverse proxy that lets you split the "public-visible focal point" part of a web server from the "Holds a lot of private data and runs code" part. So the latter can run in someone's living room.
It will redirect you to a unique link tied to your IP/User Agent string so if you want to see it again you will have to click the original link again.
This seems like a very significant limitation. Is there a way around this?
My first though is that if instead of one problem 100x as hard you solved 100 easier problems. That at least would give you a somewhat accurate loading bar, but I'm not sure if that would actually reduce your variance.
There are tons of things in nature that are like this, for example how long it takes a spinning quarter to topple over on the table and land heads or tails. Its theoretically possible it could balance perfectly and never fall, but how many times have you seen that IRL???
It is completely fine to use it to build an application for a client. Such an application cannot become a product without becoming open source, however.
GPL is a great license, but for libraries (or „building blocks“) it greatly limits their usage. Not everybody wants to license their application as GPL. Just like not everybody likes bananas. Some prefer peaches or oranges.
But for a library project, GPL is quite an unusual choice. I don't know any commonly used library, that has such a restrictive license. Most of them use LGPL, Apache, MIT, BSD or something similar. Otherwise your library is commonly doomed to be a stillbirth.
Ghostscript is one example, a lot of users ran into legal trouble using it.