Trustless Work for Bitcoin: How ZK Contingent Payments Let Strangers (and AI Agents) Trade With Zero Middlemen

Imagine you could hire a total stranger on the internet — or a total AI agent — to solve a problem for you, pay in Bitcoin, and keep your money unless they can mathematically prove the work is correct before you pay. No Upwork holding your funds for two weeks. No escrow agent taking 3%. No dispute center. No “sorry, your account was suspended” with $4,000 inside.

That’s not a pitch for a startup. It’s a protocol that has existed since 2011, was demonstrated live in 2016, and just got a working open-source implementation you can run on your own machine. It’s called a zero-knowledge contingent payment (ZKCP), and a project called PCP (Proof-Contingent Payment) is the most complete attempt yet to turn it into something both humans and AI agents can actually trade over.

This article explains how it works, what the real numbers look like, why it suddenly matters a lot more in the age of autonomous AI agents, and where the sharp edges are.

The problem: paying for work you can’t verify yet

Every freelance transaction on the internet has the same chicken-and-egg problem:

• The buyer won’t pay before seeing the result.
• The seller won’t deliver before getting paid.

Platforms “solve” this by holding money in escrow — and charging both sides for the privilege, freezing accounts at will, and deciding disputes with the transparency of a black box. The platform is a third party that can see everything, stop anything, and take a cut of everything.

For human freelancers, that’s an annoying tax. For AI agents, it’s a wall: an autonomous program can’t open an Upwork account, can’t pass KYC, and can’t argue with a support desk. If we want software to buy and sell work on our behalf — a solver, a data pipeline, a proof-of-compute service — we need settlement that doesn’t depend on any institution at all.

ZKCP: the trick that removes the middleman

The idea is older than you’d expect. Greg Maxwell described the zero-knowledge contingent payment in 2011 on the Bitcoin wiki, and in February 2016 a sudoku solution was sold this way in a live transaction on the Bitcoin mainnet — the first-ever trustless trade between strangers with no escrow.

The mechanics, in five steps:

1. The seller computes the result R (say, a solved sudoku). They pick a random key k, encrypt the result: C = Enc_k(R), and publish a hash H = SHA256(k).
2. The seller produces a zero-knowledge proof — a cryptographic certificate proving: the encrypted blob C decrypts (with key k, whose hash is H) to a valid solution R. Crucially, the proof reveals nothing about k or R. The buyer can verify the proof and still knows nothing about the answer.
3. The buyer checks the proof before paying anything. If the proof is valid, they know: “the thing I’m buying is correct, and I’m the only one who can decrypt it once I pay.”
4. The buyer pays a Lightning invoice whose payment hash is H. To collect, the seller must reveal the preimage — which is k itself.
5. Claiming payment automatically hands the key to the buyer, who decrypts C and gets the result.

The beauty is the atomicity: no payment without the key; no key without payment. It’s not that nobody could cheat — it’s that cheating is mathematically worthless. The escrow isn’t trusted; it’s unnecessary.

From sudoku demo to a real protocol: PCP

The gap between a 2016 demo and a usable system is where most projects die. A recent open-source project — pcp by Julian Sugiarto — is a serious attempt to close it, and it’s worth studying even if you never run it, because it shows what “production-izing” ZKCP actually involves.

What it is: a written protocol spec (PCP/0) plus a Rust implementation, with a Lightning (LND) payment rail and a RISC Zero zkVM proof backend. The core guarantee: payment settles if and only if a verifier-accepted proof shows the work was done correctly. Atomic, between strangers, no escrow agent, no platform, no court.

Three things this implementation adds beyond the textbook ZKCP:

1. A written protocol, not just code. PCP/0 defines offers, statements, receipts, and refusal messages — so implementations can interoperate. It uses transparent proof systems (no trusted setup), deliberately: in 2017, researchers (Campanelli et al.) showed that a buyer could poison the trusted setup of the original ZKCP construction and walk away with the goods for free. Transparent setups have nothing to poison.

2. Mandates: letting AI agents trade without going rogue. This is the most interesting part for the agent economy. A mandate is a signed authorization from a human principal to their software agent, and it carries hard limits: which job classes the agent may trade, a cumulative cap, a per-deal maximum, an expiry time, and the exact Lightning node that must receive payouts. The agent can do business — but it cannot spend beyond the cap, cannot redirect money to its own node, and every receipt flows back to the human. It’s an allowance system enforced by signatures, not by trusting the agent. As the spec puts it honestly: a mandate proves a key authorized another key — it doesn’t prove the principal is human, and it doesn’t pretend to.

3. Honest performance numbers. This is rare and worth praising. The repo publishes actual measured costs, from CI runs with real LND nodes on regtest: proving a 9x9 sudoku with the reproducible RISC Zero guest takes 62–102 seconds on a 4-vCPU runner, verification is ~0.02 seconds, the receipt is about 224 KB, and a full sale between two real LND nodes has settled end-to-end in CI — seller proves, buyer verifies, payment settles, buyer decrypts, all SETTLED. There’s even a correction section admitting an earlier cost estimate was wrong by 2.3x, with the numbers to show it.

The self-caught bug: why “reviewed by AI” appears in the README

The most instructive part of the project is what the author calls “the embarrassing part.” The first zero-knowledge SHA-256 gadget used in the proof circuit turned out to be forgeable — a seller could have proven a false payment hash and been paid for nothing. It was caught by a separate AI reviewer session that did not write the code, before any money moved. Then came the humbling discovery: upstream had removed that same gadget three weeks earlier, for exactly this reason, and the author hadn’t read why.

The full failure report is public — how it was found, working exploits, the replacement gadget, and what remains unverified. Two break-it challenges are open (soundness and privacy of a published test bundle), with public credit for anyone who succeeds.

For a blog that covers AI systems: this is a good case study of AI-assisted code review catching a real cryptographic vulnerability that the original author missed — and of publishing failures instead of hiding them.

What it costs to run (the real numbers)

Using the published benchmarks:

Translation: proof generation is minutes of cheap CPU time, verification is instant. For anything where the work itself costs more than a few minutes of compute — data, solutions, model outputs, completed computational jobs — the proof overhead is negligible. That’s the economic window where trustless payment beats escrow.

Where this is going (and what to be skeptical about)

The obvious use case everyone is circling: agent-to-agent commerce. Your research agent pays some stranger’s solver agent for a computed result, proof-verified, settled over Lightning, capped by your mandate — all in seconds, no platform, no KYC, no chargeback fraud. The pieces demonstrated in this repo — mandates with spending caps, receipts to the principal, transparent proofs, Lightning settlement — are exactly the pieces that economy needs.

Be skeptical in the right places, though. The project itself says plainly: don’t use real money with it yet. It’s unaudited by any outside party, tested only on regtest, the privacy of the proof system is stated as “works in practice, not proven as a theorem,” and the whole design is explicitly not quantum-resistant. That honesty is a feature — most crypto projects ship without any of these warnings.

The deeper takeaway: the escrow platform is not a law of nature. It’s a workaround for the absence of cryptographic verification. As zero-knowledge proofs get cheaper — this repo is already measuring 60-second proofs of arbitrary computations on commodity CPUs — the workaround becomes optional. And the first big customer for that isn’t a person; it’s the swarm of AI agents we’re all about to be running.

Interested in the details? The whitepaper, spec, failure report, and benchmarks are all in the public repo. The project accepts Lightning (BOLT12), on-chain BTC, ETH, SOL, and BNB donations for its break-it bounties.