Nanopayments
a.k.a. Micropayments
Nanopayments are tiny payments for a trivial service. For example, 0.0001 BTC for each of three Tor nodes to relay one megabyte of traffic with premium priority.
It should be easy to see that a series of payments like this would be "spam" to Bitcoin, and infeasible due to transaction fees, and unwelcome to everyone who must download and store the whole block chain.
The idea, in a nutshell, is for Alice to make a 0.0001 BTC nanopayment to Bob by signing a message not worth 0.0001 BTC, but by signing a message that has 1 in 10000 probability of being worth 1 BTC, and sending it to Bob directly. This message would function much like a share in a mining pool. Out of 10000 nanopayments, on average, 9999 will be worthless and 1 will not.
For it to work fairly, Alice must not have any way to know which share is actually redeemable to the recipient.
Of course, due to variance, Alice will sometimes get her services for free, and sometimes she will vastly overpay. However, if she consumes such services regularly, the amount she pays will tend toward the amount she consumes.
Technical stuff: How can probabilistic transactions be created?
Bob creates a secret transaction that will be used for a "guess my hash" challenge. The value can be the minimum and will be sent back by Alice's transaction. He doesn't broadcast it yet.
Alice will create a multi-input transaction that spends her own coin AND Bob's secret transaction. Here's where the random chance comes in. We're going to randomize the prevout identifying Bob's transaction. Multi-input transactions are not valid unless all their inputs exist, so if Bob's transaction is misidentified, the whole transaction is void.
For the hash identifying the secret transaction, Bob only gives Alice a numeric range that the hash is in. If the hash is H, and we want a 1/N chance of the nanopayment being real, then Bob would take H1=H-rand(N) and tell Alice the hash is between H1 and H1+N.
Alice chooses H2 in the range H1 to H1+N and creates the transaction. Input 1 is her coin, and input 2 uses H2 as the prevout hash that may or may not match Bob's secret transaction. She signs input 1 and gives the transaction to Bob. Note that signing one input locks in the prevouts of all inputs, so Bob can't change H2.
Bob now checks if the H2 she used equals H. If it is, he signs input 2 and broadcasts both his secret transaction and Alice's transaction.
If H2 is not H, then the transaction can never be valid, because there can be no previous transaction that hashes to H2. Since the transaction is invalid, not just unspendable, Bob can't be a jerk and submit it to the network just to waste Alice's coin.
What if Alice tries to double spend her 1 BTC out from under Bob before he gets his successful transaction into the block chain?
If Alice tries to double spend on nanopayments, she'll spend more on transaction fees than she saves.
She would need to selectively double spend the real ones, but she doesn't know if the transaction she gave Bob was real. All she can do is wait and watch if Bob broadcasts it, but by then his transaction will already have a big head start. If Bob is really paranoid, he could connect directly to the pool miners and broadcast only to them first to get most of the mining power sewed up before Alice would even know.
This may not be a big enough problem to matter for most casual, low value uses.
If need be, this could be solved with hub servers that nanopayment recipients would use to announce coins currently in use to other nanopayment recipients.
When Alice sends her nanopayment transaction to Bob, she would need to use her coin's EC-DSA key to sign a reserve message containing the current time, her coin's hash, and the address she's paying to. Bob sends this message to the hub server to reserve her coin for some predetermined period like 1 minute.
A hub server would be pretty simple, just a single lookup table. A merchant sends it a reserve message. The server checks that the signature matches the coin. If a reserve is already in effect for that coin, it returns an error, otherwise OK. It adds the reservation to its lookup table and purges it when it expires. Merchants could connect to several hub servers to keep them honest and for redundancy. It would be fitting to pay the hub servers with nanopayments.
Notes
This article is derived from Sustainable nanopayment idea: Probabilistic Payments by casascius.
The bitcoin-nanopayment project is a relatively unproven implementation of this using Node.js.
Tadge Dryja (of Lightning Network fame) talked about probabilistic payments in April 2016: [1]
Although probabilistic payments were considered for the Lightning Network, the current lnd implementation does not use them. Instead, it just rounds down to the nearest satoshi when a channel is closed.