What would you do if you wanted to buy a $0.50 pack of gum, but you only had a one-dollar bill and a penny and no one could make change?

If you read the title of this blog post, this simple idea might occur to you:

1. Have the gum vendor call “heads” or “tails”.
2. Flip the penny, and if the vendor called the flip correctly, pay them $1.
3. Take the gum either way, and enjoy.

This isn’t exactly the same as paying $0.50, but it tends to be the same in the long run if you engage in a lot of probabilistic payments.

Generalized probabilistic payments

Say you wanted to buy a single stick of gum for $0.05, but you still only had a one-dollar bill. In this case, you could ask the gum vendor to choose a number between 0 and 19. Then you could look at the serial number of the dollar bill together and pay $1 if the serial number modulo 20 matched his prediction.

Even more generally, probabilistic payments between untrusted parties work with any system that enforces payment with the desired likelihood.

Probabilistic micropayments

Probabilistic payments are a solution to the problem of micropayments. Micropayments lack a precise definition, but they’re generally meant to be payments that are too small to process in the usual ways. For example, you can’t buy something for $0.01 with a credit card because that amount wouldn’t even cover the credit card fees.¹

Probabilistic payments solve this problem. Instead of paying $0.01, just pay $10 with probability 1/1000. Whatever fees exist are only assessed on the rare occasion when the payment actually happens, so they’re amortized.

This applies to the blockchain too, where fees tend to be per transaction. So-called “layer 2” solutions can sometimes help, but they tend not to address the needs of one-off micropayments.²

Using an Ethereum smart contract

Earlier I wrote that probabilistic payments require a system that enforces payment at the right likelihood. What you don’t want is a system where the buyer can just run off when they realize they’ll have to pay.

If you read my earlier post on Ethereum smart contracts, you know that they’re perfect for this use case. A micropayment can be enforced by the smart contract, which means two parties who don’t trust each other can still transact.

Probabilistic payment protocol details

In the description below, S means seller and B means buyer:

0. B escrows funds with a smart contract, some of which go to a “penalty fund”.
1. S produces a random number r, sends hash(r) to B.
2. B produces a random number r2.
3. B sends S a signed payment: { S, hash(r), r2, amount, probability, expiration }.
4. The smart contract pays S if r^r2 % probability == 0.
5. The smart contract prevents replays by treating r as a per-recipient nonce.
6. The smart contract slashes the penalty fund if a “winning” payment exceeds the sender’s balance.

Step 0 is a setup step. Anyone wishing to use the described smart contract has to escrow funds there initially. In particular, a penalty fund has to be established, and those funds have to be locked in the smart contract until some timeout has elapsed. I’ll discuss the penalty fund in more detail in the next section.

This protocol also features a commitment scheme. In the first step, the seller generates a secret random number and commits to it by sharing its hash. The seller later reveals this secret to a smart contract. Because the hash is already known, the seller has to be honest and stick with their original number.³

What I’m calling a “signed payment” is sometimes called a lottery ticket because it “wins” with a certain probability and can then be collected.

Double spending attack

If a seller is meant to accept a probabilistic payment, they have to know that it’s just as good as a real payment. In other words, they need a guarantee that they’ll actually get paid if their “lottery ticket” wins.

This is a problem because there’s no way to know how many lottery tickets are out there. I could escrow just $1 with the smart contract and then buy 100 packs of gum from 100 different vendors using probabilistic payments. Every gum vendor could plainly see I had enough to cover the purchase I’m making with them, but when they try to collect, they could find they’re too late.⁴

The solution typically used is the penalty fund I mentioned in the preceding section. The penalty fund is money that gets destroyed if there are ever insufficient funds to pay a winning lottery ticket. If this penalty is sufficiently large—more on that in a moment—I have the right incentive to make sure I always have enough in the smart contract to cover the payments I’m making.⁵

How big is big enough?

Unfortunately, it’s not clear how big a penalty fund has to be, and it could be that no size is sufficient! If there’s no limit to how much I can buy at the same time, there’s no limit to how much I might owe, and thus there’s no size penalty fund that would prevent me from profiting.

Fortunately, there are practical limits on how much spending someone can do before they’re caught. Decentralized Anonymous Micropayments by Chiesa et al. provides a framework for deciding how big of a penalty fund is necessary to provide the right economic incentives.

There are likely additional practical solutions for the blockchain case, such as insurance and reputation systems (perhaps combined). Outside of the blockchain, there is legal recourse if someone bounces a check. Presumably this would also work for probabilistic payments.

Real-world usage

I had the opportunity to audit the Orchid Network Protocol last November. Orchid provides a peer-to-peer VPN service and uses probabilistic micropayments to pay for bandwidth.

---

1. Credit card fees are typically a fixed per-transaction fee plus a percentage, e.g. $0.30 + 2.9% from Stripe. ↩︎

2. Payment channels support an arbitrary number of off-chain transactions but require two on-chain transactions (one for setup and one for settlement) per pair of participants. So if you’re going to buy gum from the same vendor every day, a payment channel would help, but if this is a one-time purchase, the cost of the payment channel exceeds the normal fees for a single transaction. Bitcoin’s Lightning Network or Ethereum’s Raiden Network are more useful, but they can’t avoid the fact that every transaction (even off-chain) has fixed costs. ↩︎

3. This is true because cryptographic hash functions are second-preimage resistant. ↩︎

4. In practice, I’d probably also write myself a lottery ticket that I knew would win, and I’d try to be the first to collect. ↩︎

5. It’s important that the penalty fund is destroyed rather than distributed among those owed. Otherwise I can just write myself a lot of winning lottery tickets and take the penalty fund for myself (or at least an arbitrarily large portion of it). ↩︎