You don't need captchas - Proof of Work

Info

The point of this article is not to say captchas are worthless, though they are often overpowered and way too expensive. All of the following code is just pseudocode to explain the principles.

Intro

Okay, what exactly are captchas? Captcha stands for

C ompletely

A utomated

P ublic

T uring Test to tell

C omputers and

H umans

A part

So the point of a captcha is to automatically (meaning without human intervention) differentiate between computers and humans. How do they do it?

How do CAPTCHAs work?

CAPTCHAs use multiple approaches, often combined. One of the most common CAPTCHAs prompts you to select all parts of an image that contain (part) of a given object.

CAPTCHA (AI generated)

I'd categorize CAPTCHAs in three:

• Visible (interactive)
• Visible (checkbox only)
• Invisible

Both visible and invisible captchas often do background checks, like testing browser capabilities, evaluating mouse movement,...

One thing I didn't mention yet: CAPTCHAs already often contain proof of work challenges.

Why you shouldn't use captchas

Captchas are very expensive. For example hCaptcha costing $99 for 100k evals and $0.99/1k after. So if you for example need spam protection but not the higher probability the call is human-made, CAPTCHAs are just not worth it.

What is Proof-of-Work?

As the name suggests, its a proof computational work was done. But how does that protect from spam?PoWs are computationally expensive, and you can adjust the difficulty as needed. For example, requiring 0.1–5 seconds of CPU time per request means a spammer would need massive computing resources to flood your system.

How does it work?

Its actually pretty simple:

1. Server generates a Bytes randomly
2. Saves challenge with id in Cache/redis
3. Tells client how many leading zeros are the target has and the challenge ID
4. Client generates random Bytes
5. Combines Challenge Bytes with the generated
6. Hashes the result
7. Counts leading zeros
8. Sends request including the challenge ID and result if hash has enough leading zeros, else starts at 4. again.
9. Server retrieves challenge using the ID
10. Combines Challenge Bytes with clients result bytes
11. Hashes result
12. Counts leading zeros
13. Denies request if too few, accepts if enough

Why does it work?

Cryptographic hash functions are unpredictable, but deterministic. So you only can try over and over again until you get the expected result. Let’s say we require 22 leading zero bits in the hash. That’s a 1 in 4,194,304 chance per attempt, so on average the client must compute about 2,097,152 hashes to find a valid result. An iPhone 14 does ~1 million hashes per second, so 22 leading zeros would take an average time of two seconds to reach. due to the random nature of it, it can be both way less and way more. For the server the computational work is negligible, since it only has to do one hash operation.

How would that look in code?

Solve on client:

struct POWHandler1 {
    static func solvePoW(_ payload: Data, leadingZeros: Int) -> (nonce: Data, digest: SHA256.Digest) {
        while true {
            // 1) generate a 64-bit nonce
            let randomNonce = UInt64.random(in: .min...UInt64.max)
            // 2) turn it into 8 bytes (little-endian)
            let nonceData = withUnsafeBytes(of: randomNonce.littleEndian) { Data($0) }
            
            // 3) concatenate payload || nonce
            var msg = Data()
            msg.append(payload)
            msg.append(nonceData)
            
            // 4) compute SHA256
            let digest = SHA256.hash(data: msg)
            // 5) count leading zero bits
            if countLeadingZeroBits(in: digest) >= leadingZeros {
                return (nonce: nonceData, digest: digest)
            }
            // else: next iteration
        }
    }
    
    static private func countLeadingZeroBits(in digest: SHA256.Digest) -> Int {
        var count = 0
        for byte in digest {
            let lz = byte.leadingZeroBitCount
            count += lz
            if lz < 8 { break }
        }
        return count
    }
}

Generate on Server

private func generatePoWChallenge(
    difficulty: Int,
    ttl: TimeInterval
) -> (id: UUID, payload: Data) {
    let id = UUID()
    let payload = Data([UInt8].random(count: 16))
    return (id: id, payload: payload)
}
//save in KV storage (Cache, Redis, Memcached)

Verify on Server

func verifyPoWSubmission(
    challengeID: UUID,
    nonce: Data
) async throws {
    guard let storedChallenge = retrieveChallenge(challengeID) else {
        throw APIError(code: 400, message: "Invalid challenge ID")
    }
    
    var msg = Data()
    msg.append(storedChallenge.payload)
    msg.append(nonce)
    let digest = SHA256.hash(data: msg)
    
    let zeros = countLeadingZeroBits(in: digest)
    guard zeros >= storedChallenge.leadingZeros else {
        throw APIError(code: 400, message: "Bad PoW")
    }
}

Notes

You should make PoW challenges valid only for a limited time and for a single use, to prevent attackers from precomputing solutions or replaying old ones. Also you could use ratelimiting in combination with PoW, making PoW increasingly harder. If an IP exceeds its rate limit but the user hasn’t, I increase the PoW difficulty instead of blocking them immediately. Consider providing a way to adjust PoW difficulty dynamically based on device performance, or offer an alternative for users who cannot complete the challenge. To be better protected against ASICs or botnets (if that is a realistic threat to you) consider using scrypt or Argon2 instead of AES256. Though that would lead to more utilization on your end as well.

Conclusion

Proof of work can in some cases be a way cheaper alternative to prevent spam. The computation work happens almost only on the client, so it doesn't eat you precious ressources.

If you enjoyed the read I would appreciate you sharing it.

Until next time, Mia