Topic: Sustainable nanopayment idea: Probabilistic Payments (Read 6466 times)

Right, I meant that each interaction that results in a payment going through actually consists of two transactions. I'll try to figure out a better way to word that.

Nice!

I assume you mean "each actual payment"?

phelix, I'm pretty sure that jevon's idea works as-is. I wrote a sample implementation in Node: https://github.com/hi-entropy/bitcoin-nanopayment

This sounds really good. Would any of the suggested methods actually work?

At least not as intended :)

Sadly most opcodes are crippled, disabled or useless. For example, math opcodes can only work on 4-byte numbers, so 160-bit hashes won't give the result you are expecting.

Repeat it 5000 times to the same merchant in a short period of time and you're probably consuming enough that a nanopayment no longer makes sense.  Just pay 0.5 BTC to the intended recipient the normal way.  This is intended as a way for moneybees to casually and anonymously pay for bits of pollen from lots of payflowers without burdening the block chain with dust spam - not so much for people to buy a jar of honey.

Very cool.  Watching.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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)

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)?

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.


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.


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 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.