Pages:
Author

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

newbie
Activity: 7
Merit: 0
Each payment requires two transactions (hence double the transaction fee)
I assume you mean "each actual payment"?

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.
legendary
Activity: 1708
Merit: 1020
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
Nice!

Each payment requires two transactions (hence double the transaction fee)
I assume you mean "each actual payment"?
newbie
Activity: 7
Merit: 0
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
legendary
Activity: 1708
Merit: 1020
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.


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

donator
Activity: 532
Merit: 501
We have cookies
When Alice sends a share to Bob, she signs a transaction that looks like this:  OP_DUP OP_HASH160 OP_EQUALVERIFY OP_2DUP OP_CHECKSIGVERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_XOR OP_MOD OP_0 OP_EQUAL

NOW, HOW ON EARTH DOES THAT SCRIPT SOUP 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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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.

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.

sr. member
Activity: 308
Merit: 250
Very cool.  Watching.
full member
Activity: 126
Merit: 110
Andrew Miller
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
sr. member
Activity: 323
Merit: 251
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.
full member
Activity: 225
Merit: 101
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.
full member
Activity: 225
Merit: 101
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.
newbie
Activity: 36
Merit: 0
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.

Quote
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.
legendary
Activity: 1526
Merit: 1134
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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.
full member
Activity: 169
Merit: 100
Firstbits : 1Hannes
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  Cry. 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.
legendary
Activity: 1526
Merit: 1134
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.
sr. member
Activity: 462
Merit: 250
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.
vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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)
legendary
Activity: 1050
Merit: 1003
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)?

vip
Activity: 1386
Merit: 1140
The Casascius 1oz 10BTC Silver Round (w/ Gold B)
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.
Pages:
Jump to: