Sustainable nanopayment idea: Probabilistic Payments

[casascius]

I came up with an idea for how Bitcoin (or an alt chain) could be used to facilitate tiny anonymous nanopayments, while keeping reins on block chain bloat.  I wondered what others thought of it.

By nanopayment, I mean paying something super tiny for a trivial service - example - to pay 0.0001 BTC to each of three Tor nodes to relay one megabyte of traffic with premium priority.  Or as antispam e-mail stamps.

The problem on its face:  Making nanopayments is at odds with bloating Bitcoin's block chain.  It should be pretty 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 wants to hold the whole block chain (that means everyone).

I mention an alt chain as a suitable task for this for two reasons.  One, my idea that solves the "nanopayment bloat" issue would require enabling of disabled arithmetic opcodes on Bitcoin, new messages to the protocol, and probably a chain fork - something totally unlikely to be accepted on Bitcoin as stated by the core developers.  But if my idea has merit, maybe this will give legitimacy to an existing alt chain doing this and finding a niche.  Maybe Litecoin can be the official chain of probabilistic payments or something.

So what's the idea?

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 (from Alice's view) 1 in 10000 probability of being worth 1 BTC to Bob, and by sending it directly to him.  This message would function much like a share in a mining pool.  Out of 10000 such 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.  So, here's what I propose.

• Alice starts with a txout she owns, worth 1 BTC.  Maybe Bob will get it, maybe Bob won't, but the more she consumes Bob's services, the odds go up that Bob will get the whole thing.
• Bob generates a brand new Bitcoin address and sends it to Alice.  It is important that Alice not yet know the public key to this Bitcoin address to prevent her from defrauding Bob, so Bob must never have spent from this address before.
• Alice generates and signs a transaction for Bob that spends her 1 BTC to him.  However, this transaction for Bob is encumbered by Alice in three ways via the txout script.
  
  • One is that it must be signed by Alice, which of course it is.  (This keeps strangers out.)
  • Two is that its redemption also requires knowledge of the address's public key, which for the time being, only Bob has.
  • Three is that some pseudorandom condition - unpredictable to Alice but statistically likely to occur with 1/10000 probability - must be satisfied for the payment.  Alice must not be able to predict the good shares or else she could withhold them.  The unpredictability for Alice hinges on Alice not knowing the public key to Bob's payment.
• As Alice continues to request and consume services from Bob (e.g. megabytes of premium Tor bandwidth), she continually signs and sends these nanopayment transactions to Bob.  Each time she signs, she must choose a different random value K in the signature (or alternately, signs it with an incrementing nonce that is OP_DROPped), which basically rolls the dice and makes a new share.  Bob evaluates them for spendability, and if he detects that he received a share that satisfies all three requirements, he broadcasts it to the blockchain revealing his public key, and collects his full bitcoin.

Of course, due to variance, Alice will sometimes get her services for free, and sometimes she will vastly overpay for them.  However, if Alice consumes such services regularly, the amount she pays will tend toward the amount she consumes.

Now, here is how those steps would work on Bitcoin (ignoring the fact that it uses disabled opcodes and nonstandard transactions - which is why this idea could get jumped on by an alt chain looking for distinction.)

• Assume Alice has a normal txout worth exactly 1 BTC.
• Alice knows <bobs-address> having been given it by Bob.
• When Alice sends a share to Bob, she signs a transaction that looks like this:  OP_DUP OP_HASH160 <bobs-address> OP_EQUALVERIFY OP_2DUP OP_CHECKSIGVERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_XOR <constant:10000> OP_MOD OP_0 OP_EQUAL
• Bob would evaluate the share for spendability, and publish it to the block chain if he determined he could spend it, in other words, the random component flagged a win.  (He could still publish it to the block chain without the random win, but he would be sending his coin to its grave in the process)
• Bob would spend it to himself by issuing not just Sig and Pubkey, but N, Sig, and Pubkey
• Alice can continue to send micropayments to Bob using the same transaction, just signing it repeatedly and resending it to Bob, for each unit/megabyte/whatever she consumes from Bob.  (Remember, Alice's signature has a random component k known only to Alice, so the signature will be different each time she signs the same message.  This difference is how Bob can treat it as a brand new share.)

NOW, HOW ON EARTH DOES THAT SCRIPT SOUP WORK?

The difficult-to-follow part of the script is the part that sets up a 10000:1 condition that Alice can't predict, but that Bob can confirm his odds on.  The script does the following:

• Checks Alice's signature.  (The first several operations, except the OP_2DUP, should look familiar)
• The extra OP_2DUP takes an extra copy of both the Sig and Pubkey before they are consumed by OP_CHECKSIGVERIFY, because we want both of these to check if our share is any good
• OP_CHECKSIGVERIFY checks the signature, failing the transaction if it's bad.  It consumes one copy of Sig and Pubkey, leaving the other copy of both of them on the stack.
• Now, we have OP_HASH160 OP_SWAP OP_HASH160 OP_XOR.  This takes a hash of both Sig and Pubkey, and XORs them into a single number that, importantly, Alice could not predict. EDIT: see note at bottom.  This part might not work and might need to be replaced by something else, like a random number or incrementing nonce included by Alice, to be hashed with Bob's public key in order to fulfill the same goal: produce a pseudorandom number Alice can't predict, based on a commitment Bob can't change.
• The 10000 OP_MOD divides the combined hash and keeps the remainder.  (10000, in this case, is the "odds" factor that determines the likelihood the share will be good.)
• If the modulus turns out to be zero, Bob is a winner and gets the whole 1 BTC.

Pretty simple and straightforward.

Now, to make sure Bob keeps his 1 BTC bounty safe, one challenge remains: he needs to get it into the block chain before Alice figures out that he successfully won it.  That's because Alice could double-spend it out from under him.  Alice could also be using that same 1 BTC to buy services from somebody else, who won't know she is pledging shares of that same coin in more than one place, where somebody would be shortchanged if both services won the same bitcoin at around the same time.

So, to make that work, there would need to be a way for Alice to put that 1 BTC on hold for Bob's benefit, albeit only temporarily.  This way, Alice can't swipe the coin out from under Bob, but on the other hand, Bob doesn't get to keep control of the coin if he doesn't receive a winning share after a certain amount of time.

The only feasible way I could think of doing that, is by broadcasting a new memory-only peer-to-peer message that pledges a certain txout to a certain destination bitcoin address for a certain period of time.  This message doesn't go in the block chain - it just puts nodes on notice to only accept spends destined for Bob until the lock time expires.  Something I think would be extremely unlikely to fly with the Bitcoin developers, but something that an alt chain looking for a niche might not have such a problem with.

I'm requesting comments, so fire away.

EDIT: I think I have realized one problem with my proposal, at least with respect to its implementation.  I believe I am incorrectly assuming that the script will be hashing the sig and pubkey sent by Alice, but really, this script will be run when Bob spends the funds, and thus, what will be hashed is Bob's pubkey and signature, which he could just repeatedly generate.  So, if you notice this, then perhaps before pointing this out, consider that there might be another way to come up with the random condition (ultimately it's in the form of a signed random number sent by Alice, if not the signature itself... combined with the hash of something known only to Bob).

[cunicula]

Interesting idea.

Can you explain a bit how this economizes on record keeping?

In particular, what are the bandwidth and data requirements of contracts specifying a payment probability relative to actual payments?


Can contracts specifying a payment probability be recorded temporarily and then permanently deleted (which would differentiate them from actual payment records)?

[casascius]

Interesting idea.

Can you explain a bit how this economizes on record keeping?

It saves on recordkeeping because real coins only change hands when a winning share is conveyed.  If someone consumes services and pays with shares and none of them win, no coin transaction takes place.  So in effect, if shares with 1/10000 odds are being used as payments, on average only one coin transfer takes place for every 10,000 shares spent on the market.

When someone makes a nanopayment, they are not paying with a nanocoin - they are paying a nano chance of scoring a big coin.  records are kept only of the winning shares, just like (in Bitcoin) only winning hashes go into blocks.

In particular, what are the bandwidth and data requirements of contracts specifying a payment probability relative to actual payments?

The bandwidth is only consumed privately between the service provider and its client.  None of the nanopayment traffic hits the P2P network except to record winning shares, and to temporarily pledge coins to single potential payees to prevent double-commitments.

If I'm a client Alice, and you're a Tor node Bob, and I want your services, an exchange might go like this (completely automated, of course).

• Alice: I want to consume your service.  I understand your rates are 0.0001 BTC per megabyte.  I will be paying with shares that have a 1/10000 chance of being worth 1 BTC, so each share is worth 0.0001 BTC.
• Bob: Thank you very much.  My Bitcoin address is <address>
• Alice: Thank you.  Now, here is a signed message reserving this bitcoin for you until <time / block>.  I broadcasted it to the P2P network.
• Bob: OK, the message arrived to me.  You can use my services until either <time/block>, or until I win your bitcoin, as long as you send me a new share for each 1MB you consume.
• Alice: Thanks.  Here is a share to pay for my first megabyte of transfer.  <share transaction>
• Bob evaluates the share to see if he won the bitcoin.
  
  • If he did not win the Bitcoin, he thanks Alice and gives her 1MB of transfer.
  • If he won the bitcoin, he says to Alice:  Sorry Alice, I just won your coin.  You have 1MB of transfer credit, but you're going to have to pledge a new one to go any further.
• When Alice does 1MB worth of transfer and wants to continue, she sends another share to Bob, assuming her pledge time isn't close to expiration.  When she is done consuming Bob's services, she just disappears.

Side note, if Bob were to see a new pledge on the P2P network to someone else, or somehow saw a spend on the pledged coin (e.g. mined into a block by a miner who didn't know about the pledge), he would stop accepting shares on that coin and require a new one to continue.  The intended behavior of a pledge is, specifically, to ask relays to accept spends to the pledged address as a higher priority (replacing any spends of that same coin to another address), and to ask miners to refrain from including any transaction in a block that would violate the pledge while it is in force.

These rules are somewhat loose, because they depend somewhat on nodes honoring the pledges, a prime reason why an alt chain dedicated to this would be preferable and why Bitcoin itself could likely never support this.  When it's nanopayments, someone managing to steal a small amount of nano-services once in a while (e.g. by running a rogue miner that dishonors pledges) isn't really a big deal, particularly as the nano service provider will soon detect the conflicting "scam block" and demand a different coin to continue (the same way as if the coin had been won).  Of course, pledges would have nothing to do with normal (non-nano) payments of coins on the alt chain - a misbehaving miner couldn't doublespend regular transactions any more than one can on Bitcoin today.

Can contracts specifying a payment probability be recorded temporarily and then permanently deleted (which would differentiate them from actual payment records)?

Sure, this would be a private matter between client and server.  The only contract that needs to be broadcast to the P2P network would be one that pledges the bitcoin to Bob while Alice is consuming his services (so only Bob can redeem it), but the P2P network isn't concerned with the actual probability that Bob might win it.  It only cares if either Bob won it, or if he did not win it before Alice's pledge expired.  This pledge record would never be saved to disk and would be deleted when it expired (a typical pledge lifetime might be 30 minutes).

[dooglus]

Now, we have OP_HASH160 OP_HASH160 OP_XOR.  This takes a hash of both Sig and Pubkey, and XORs them into a single number [...]

I don't think that's how OP_HASH160 works.  If you have 2 things on the stack and then OP_HASH160 twice, you'll hash the 2nd thing twice, not both things once each.

[casascius]

Now, we have OP_HASH160 OP_HASH160 OP_XOR.  This takes a hash of both Sig and Pubkey, and XORs them into a single number [...]

I don't think that's how OP_HASH160 works.  If you have 2 things on the stack and then OP_HASH160 twice, you'll hash the 2nd thing twice, not both things once each.

Oh yeah, you're right.  OP_SWAP in between would probably fix that though, so I am guessing you're pointing out a mistake in my example more so than, say, a reason the whole thing wouldn't work...right?  Edited the OP to include OP_SWAP

[cunicula]

Okay, I'm still not clear on some things.

1) Suppose that Alice and Bob expect to do 1 BTC volume of business (say a transfer of 10 GB). In this case why not just pay 1 whole BTC for 10 GB and forget about paying 0.0001 BTC per MB?

2) Suppose that Alice and Bob expect to do only 0.0001 BTC of business. There is a micropayment problem. The volume of business is too small to be supported by a regular txn.

In case 2, Alice and Bob sign a  pledge contract which says that 1 BTC will be transferred with a 1 in 10000 probability. There is a p2p txn broadcast throughout the network which confirms that Alice has the BTC and ensures that she cannot spend the BTC in the near future. A p2p txn like this has to be broadcast everytime two people do 0.0001 BTC of business. Won't these broadcasts involve a lot of bandwidth and storage, perhaps more than the business is worth?

In Case 1, the broadcast will not be as onerous because Alice and Bob are doing a larger volume of business. However, in Case 1, it is not clear to me why micropayments are necessary in the first place. Are you worried about Bob taking the money and running if he is paid in a lump sum? Paying him in a steady trickle as services are provided is certainly one way to solve this problem. And I agree that this is a problem. However, this is not exactly the mircopayment problem which you set out to solve.

[casascius]

Okay, I'm still not clear on some things.

1) Suppose that Alice and Bob expect to do 1 BTC volume of business (say a transfer of 10 GB). In this case why not just pay 1 whole BTC for 10 GB and forget about paying 0.0001 BTC per MB?

Yes, they could pay 1 BTC for 10GB and be done.  They can do that today.  But that scenario isn't consistent with, as my example, paying premium Tor nodes.

When you use Tor, you engage three Tor nodes your client selects at random.  They are totally anonymous.  They don't know you, you sort of know them (their IP) but that's about it.  It's very casual.  Your selection of Tor nodes changes every several minutes like a new dance partner after each song.

If you paid Tor nodes for their usage, they in turn would have more of an incentive to run them and give you access to higher bandwidth.  This would lead to better performance and greater diversity and hence anonymity, as compared to now where nodes are run by volunteers and the only disincentive against wasting bandwidth is how slow everything runs.

When you use Tor, you don't make a 10GB agreement with one node, otherwise you've defeated the anonymity purpose of Tor.  Tor connections are more like brief flings with strangers, not relationships.  You want to buzz your way to a flower, hang out for a minute, and buzz on to the next.  This idea is how to pay for the pollen at a for-pay flower.

2) Suppose that Alice and Bob expect to do only 0.0001 BTC of business. There is a micropayment problem. The volume of business is too small to be supported by a regular txn.

Not exactly.  For his services, Bob receives a 1 in 10000 chance of receiving a whole bitcoin.  That's worth something, not much, most likely nothing.  But if Bob's service is a relay node, he is receiving these "chances" constantly, then the more of them he gets, the more reliably he can count on 1/10000 of them being worth a bitcoin.  The more he sells, the more he can simply look at each one as being worth 0.0001 BTC.  This is exactly how mining pools work.  If the difficulty is 1300000, they pay you for shares, which are completely worthless to the pool operator 1299999/1300000 of the time, knowing that the true value of the one share that pays him fifty btc 1/1300000 of the time is statistically going to happen often enough that it averages out the same as if each share were actually worth 50btc/1300000.  The pool requires you to submit the share anyway just as proof that you're actually mining and nothing more.

In case 2, Alice and Bob sign a  pledge contract which says that 1 BTC will be transferred with a 1 in 10000 probability. There is a p2p txn broadcast throughout the network which confirms that Alice has the BTC and ensures that she cannot spend the BTC in the near future. A p2p txn like this has to be broadcast everytime two people do 0.0001 BTC of business. Won't these broadcasts involve a lot of bandwidth and storage, perhaps more than the business is worth?

No, they only have to do it once per engagement.  Alice pledges 1 BTC to Bob and uses his services for a few minutes.  Over the course of those few minutes, Alice may only end up spending 0.0053 with Bob, perhaps she did 53 MB of transfer.  Alice pledged 1 BTC as Bob's prize in case any of those 53 shares were winners.  There was only one pledge for the whole encounter, one P2P message, not 53.  A second pledge would be necessary if a) Bob won the bitcoin which forced Alice to pledge another, or b) the pledge expired and Alice wanted to continue doing business.

In Case 1, the broadcast will not be as onerous because Alice and Bob are doing a larger volume of business. However, in Case 1, it is not clear to me why micropayments are necessary in the first place. Are you worried about Bob taking the money and running if he is paid in a lump sum? Paying him in a steady trickle as services are provided is certainly one way to solve this problem. And I agree that this is a problem. However, this is not exactly the mircopayment problem which you set out to solve.

In the premium Tor node example, Alice and Bob don't and can't know each other, so if Bob were trusted with 1 BTC he didn't earn, he could run with it with impunity.  So, yes, in this case, Bob can't be trusted to not do so.

[cunicula]

I think your idea is great and I'm not trying to devalue it. However, using the phrase micropayment problem to describe what you are addressing may be misleading. Here is the distinction I'm making:

1) You have proposed a way to pay in very small increments for services as they are provided. A requirement here is that the two parties involved expect to exchange a significant total volume of services over a longer time period. You are addressing a trust problem. One party doesn't have to worry about the other party taking the money/service and running. If they do take the money/service and run, then at most they will get a tiny amount. It will likely be more advantageous to behave honestly. I understand how this is applicable to the tor context you mention.

2) You have not proposed a way to conduct exceptionally small one-off exchanges. If there is a "swarm" of people providing other "swarm members" with one-off services worth 0.0001 BTC, it is not clear whether your method could these support "micro" exchanges.

Do you disagree with (2)?

[casascius]

I think your idea is great and I'm not trying to devalue it. However, using the phrase micropayment problem to describe what you are addressing may be misleading. Here is the distinction I'm making:

2) You have not proposed a way to conduct exceptionally small one-off exchanges. If there is a "swarm" of people providing other "swarm members" with one-off services worth 0.0001 BTC, it is not clear whether your method could these support "micro" exchanges.

Do you disagree with (2)?

You are correct, I have not.  They could do these micro exchanges without pledges, but could also scam a significant percentage of the time in the absence of them.  Actually, I think it has nothing to do with the size or cost of the service, and everything to do with the ratio of the number of p2p pledges the network resources could support versus how quickly they were consumed.  If your "swarm" example needs to pledge ten times as often as my Tor example, all will remain the same, the same network will just support one tenth the participants before the system needs another tier designed into it.  (a problem that will plague Bitcoin with enough growth as well)

[fivebells]

If I wanted to address this problem in a protocol changing way, I would probably go for the heart of the matter, and devise a scheme which periodically embeds easily verifiable summaries of the current list of spendable coins.  Then the blockchain could get as big as it wanted.  A node catching up on the state of the ledger would only need to download the blocks generated since the last summary.

[Mike Hearn]

I'm not totally clear on how this is better than the simpler proposal already on the contracts page:

https://en.bitcoin.it/wiki/Contracts#Example_7:_Rapidly_adjusted_.28micro.29payments_to_a_pre-determined_party

Given that you need to go through a setup stage with the pre-determined party, and Alice needs to sign for each new share anyway, you could just re-sign the transactions with adjusted value fields when it's time to do so and lose the probabilistic nature.

[hannesnaude]

I'm not totally clear on how this is better than the simpler proposal already on the contracts page:

Was thinking the same thing. The only  advantage that I  can think of is that in cases where the expected final transaction value is less than the prize that can be won, and therefore the mean number of winning "shares" is  less than 1, the blockchain impact (and therefore the tx cost) will be less. But the variance will also be more, and pools have taught us where the population stands on the variance-efficiency tradeoff  . So this will be niche at best.

Still a fascinating concept though. Would like to have access to something like the hash of block number X in the script language as a source of randomness. Feels like there would be all kinds of interesting applications beyond the obvious gambling stuff.

[casascius]

I'm not totally clear on how this is better than the simpler proposal already on the contracts page:

It's very possible it's no better.  I was not familiar with the other proposal and also have not been completely clear on how nLockTime works.

[Mike Hearn]

Heh, I also came up with some (less elegant) probabilistic solution before I knew about the simpler approach. And I had the benefit of Satoshi explaining it to me directly, doh. He phrased it in a different way so I didn't see the applicability to rapidly adjusted micropayments until later.

[jevon]

I think there's a simpler way that only needs standard transactions and works with the network as-is. I wrote it up in a wiki article:
https://en.bitcoin.it/wiki/Nanopayments

In a nutshell... Bob makes a secret transaction. He tells Alice the hash is in a certain range and Alice tries to guess its hash. Her transaction depends on Bob's, so if she guesses wrong, her transaction is invalid for spending a nonexistent transaction.

Now, to make sure Bob keeps his 1 BTC bounty safe, one challenge remains: he needs to get it into the block chain before Alice figures out that he successfully won it. That's because Alice could double-spend it out from under him.

Alice doesn't know it's successful until Bob broadcasts it, so Bob can use the element of surprise to grab the pool miners before she knows he's broadcasting.

Alice could also be using that same 1 BTC to buy services from somebody else, who won't know she is pledging shares of that same coin in more than one place, where somebody would be shortchanged if both services won the same bitcoin at around the same time.

Nanopayment receivers only need to communicate with other nanopayment receivers at the time to call dibs on coins for a minute or so. This could be accomplished with some simple hub servers. No need to involve the Bitcoin network. More details in the wiki article.

For some applications it may not matter because it would be too much trouble for users to exploit this loophole.

[blueadept]

jevon, I love this. It's workable now and has advantages over the rapidly adjusted micropayment schemes in situations where you're paying many parties small numbers of micropayments each rather than a few parties many micropayments each. I've been thinking about the idea of a peer to peer network where computing resources are for rent and such a scheme could easily help for common but low cost services such as price discovery. I'm going to write it up in the next few days even if I don't have time to implement it now.

[blueadept]

Just realized the setup would have to be performed for each nanopayment. Your 1 in 10000 chance becomes a 1 in 9999 chance after one choice is eliminated. Repeat that 5000 times and you're paying twice what you should be. Not necessarily a big deal if the setup is embedded into the communication about the service bought with the payment to avoid extra round trips.

[2_Thumbs_Up]

I proposed another way to achieve something similar to this. It requires a third party, but probably not a lot of trust and works with the current block chain. The idea is that one of the bigger pools could let people buy mining hashes that they can use for payments.

If payer wants to pay payee, then payee gives him an adress, payer has an account at the pool that he can reload, and instructs the pool to redirect some of its hashing power towards that adress. The pool can compensate the miners with money from the account. Payer then gives the hashes directly to the payee who can verify that they represent real proof of work the same way hashes are verified by pools.

Regarding TOR nodes and the like, this has the added benefit that you can't link the user to a bitcoin adress since all the payments will be newly created coins.

[socrates1024]

Here are a few papers on this topic that might be helpful:

[Rivest, 1997] Electronic Lottery Tickets as Micropayments http://people.csail.mit.edu/rivest/Lottery.pdf
[Rivest and Shamir, 1996] PayWord and MicroMint: Two simple micropayment schemes http://people.csail.mit.edu/rivest/RivestShamir-mpay.pdf
[Rivest, 2002] Micropayments Revisited http://people.csail.mit.edu/rivest/pubs/MR02a.pdf
[Hashem et al, 2005] New probabilistic scheme with Variable Sized Micropayments http://www.setit.rnu.tn/last_edition/setit2005/electronique/293.pdf

[RaggedMonk]

Very cool.  Watching.