Topic: Sustainable nanopayment idea: Probabilistic Payments - page 2. (Read 6467 times)

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.

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

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.

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.



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
• Alice: Thank you.  Now, here is a signed message reserving this bitcoin for you until .  I broadcasted it to the P2P network.
• Bob: OK, the message arrived to me.  You can use my services until either , 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.  
• 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.


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

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

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 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 OP_EQUALVERIFY OP_2DUP OP_CHECKSIGVERIFY OP_HASH160 OP_SWAP OP_HASH160 OP_XOR 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).