Ad-hoc Bluetooth networks and micropayment based internet access

[Mike Hearn]

At the Bitcoin conference in Prague mobile payments failed to work well because of flaky wifi. Very likely at least one or two people there had both an Android phone and a working local data connection, the problem is there was no easy way for them to offer that service to fellow Bitcoin users. Needing to pay for things in foreign countries where you don't want to use data roaming is very common, and locked down wifi is also very common. WiFi is typically locked down using a variety of proprietary payment and ID verification systems which makes automatic usage impossible.

Android has for a long time now supported insecure Bluetooth connections, that is, connections that avoid the need to enter PIN numbers and which are thus susceptible to MITM attacks, but are "instant on". It would be a neat project to use this facility to offer network connectivity to nearby Bitcoin users for:

• Submitting Bitcoin transactions from devices without working wifi or data connectivity
• General internet access

The problem is incentives. For (1) the incentive may simply be to get paid in the first place, so it'd be possible to offer relaying of Bitcoin transactions for free. For (2) the incentive needs to be monetary, as data transfer is increasingly quota-d.

It would be a quite easy and fun project to build a Java library for such a system, such that anyone who installs Bitcoin Wallet on Android or other such apps like BitcoinSpinner can offer their data connectivity to other Bitcoin users automatically and in the background. The first goal would be to relay only syntactically valid Bitcoin transactions to the P2P network (to avoid people abusing you as a general tunnel), for free. It would be helpful for merchants who wish to offer locked down WiFi but still accept Bitcoin using an Android device, and at conferences/restaurants/etc where many Bitcoin users come together and wish to help each other out without running up a huge data bill.

Full-blown local internet connectivity is a much harder but also more exciting problem. The protocol would probably involve the following steps:

• Scan for devices offering network connectivity, ask them for (bid,public key) pairs.
• Select the cheapest bid, eg, 0.01 BTC for 5mb of data transfer. Create a transaction spending some coins to the providers public key. Take the key you used to sign the first input, this will be your signing key.
• Hand the signed transaction to the providing device. They send it to a node picked at random from the network and listen for the broadcast back again (a direct message to ask for tx validation would be better). No need to wait for confirmations as it's just a micropayment.
• Once the payment gets relayed, they begin accepting packets signed with the key used for the first tx input and encrypted with the providers public key that you spent to. This is required because the Bluetooth connection is insecure and can be MITMd, so you need to add your own encryption on top for privacy, and you need signing to avoid other people using up your credit.

There is at least one big unresolved challenge here, namely, you have to trust the provider to actually provide connectivity. There are a few risks: the provider may walk away before your timeslice is used up, they may provide (knowingly or unknowingly) poor connectivity, they may be deliberately dishonest in order to try and harvest the micropayments. Some of these issues can be resolved by starting with a very small payment for a short taste of their connectivity, and then scaling up the payments once you know it works well.

One other design that occurs to me is to use Merkle trees as a form of payment guarantee. It could work like this:

• Create a Merkle tree which contains N leaf nodes which are random numbers, where N is fairly large, say 10,000. The random data for each node is 4 bytes.
• Concatenate the N random numbers together and then hash the result, giving H1. Use this as an unlock code for a tx output for a small micropayment, eg, the script would be OP_SHA256 <H2> OP_EQUALVERIFY where H2 = sha256(sha256(H1))  [bitcoin uses double hashing for everything]. Now anyone who knows H1 can claim the output. Tell the provider where to find this transaction (might mean generating it fresh and giving it to the payment provider). The TX must take at least the first input using a key rather than itself spending using a hash. If the TX was provided fresh then the provider broadcasts it to lock it in. From now on everything is signed/encrypted with your payment key.
• Give the root hash of the merkle tree to the connectivity provider.
• They now select a seed that can be used to select a random permutation over the leaf nodes in the tree, ie a permutation of 0 to 100,000
• For each packet you send, you include the random number selected by the next permutation element and the Merkle branch needed to get back to the root.
• The connectivity provider verifies the random number is in the correct range, hashes it, verifies the Merkle branch (this is all very fast so can be feasibly done on a per packet basis), and moves its cursor along the permutation. If the random number is out of range you drop the connection and refuse to accept the given txout as payment in future.

As the random numbers are used up, the payment provider gets closer to claiming his micropayment. If the payer buys only a small number of packets more than they actually use, the provider can potentially brute force the remaining numbers quite cheaply and claim the payment anyway, as their range is known to be small (guaranteed by the fact that the payer cannot choose in which order to reveal them). If the payer doesn't get the traffic relaying they expect, they just don't provide the random numbers. Whilst the payment could eventually be brute forced regardless, the sizes of the various variables would be set to ensure the cost of the brute forcing would be higher than the value claimed.

All this would operate within fairly small time windows, because Bitcoin is pretty good at micropayments already anyway, but it's not good enough to do a payment for each packet transferred.

[1714150849]

1714150849

[1714150849]

1714150849

[EhVedadoOAnonimato]

I'm happy to see this problem attracts your interest. I was talking about the same thing here.

Creating a protocol that would allow independent routers to be payed for their service would be fantastic. It solves many issues at once.

I'm not sure I understood your Merkle Tree solution. It looks like an "all-or-nothing" in the end, except for this brute force thing - is it intended to be breakable by brute force?

I'm ignorant on bitcoin scripts as I said on the other message, but I know you're an expert. If you didn't come up with a script that would allow proportional payment, based on the number of tokens received, should I imply there's no easy way to do it?

[Mike Hearn]

I'm not sure I understood your Merkle Tree solution. It looks like an "all-or-nothing" in the end, except for this brute force thing - is it intended to be breakable by brute force? I'm ignorant on bitcoin scripts as I said on the other message, but I know you're an expert. If you didn't come up with a script that would allow proportional payment, based on the number of tokens received, should I imply there's no easy way to do it?

Bitcoin indeed only allows for all or nothing in the end. Scripts have a binary outcome. The goal of the merkle tree idea is to allow you to brute force the solution, so if somebody gives ("pays") you, say, 80% of the tree you can then pay a bit more in electricity costs to claim it anyway. But brute forcing the whole thing would cost more than the output value.

A real solution is more complicated than I outlined because you could take back your own output with the last few packets of your current data usage window, making it unclaimable by the the provider. So then you need to also lock the output to the providers key, but you don't have any guarantee you get what you paid for .... the coins are burned if you don't, meaning you probably want the usual nLockTime based dance to avoid this.

The idea is half baked ... more of a thought experiment than anything else. There's another protocol that is fully contract based. It's too slow to do a payment for every packet unless you have some kind of ECDSA accelerator/offload hardware, but it's good enough to do a payment every second.

(edited the following)

The protocol is like the deposit case - you prepare an output of reasonably large value that requires your key and the providers key to claim it (T1), and then another that sends one output to the provider and the other back to you as change. The sequence number on the input is initialized to zero. The lock time is a few minutes in the future. Each time you want to buy another second of air time, you and the provider sign a new T2 that allocates a bit more value to the provider with a higher sequence number. To end the session the provider broadcasts the last seen transaction, claiming the coins.

The more I think about it, the more attractive the latter solution looks. It's not as fine grained but it's easier to convince yourself it's correct.

[EhVedadoOAnonimato]

The protocol is like the deposit case - you prepare an output of reasonably large value that requires your key and the providers key to claim it (T1), and then another that sends one output to the provider and the other back to you as change. The sequence number on the input is initialized to zero. The lock time is a few minutes in the future. Each time you want to buy another second of air time, you and the provider sign a new T2 that allocates a bit more value to the provider with a higher sequence number. To end the session the provider broadcasts the last seen transaction, claiming the coins.

It was something like this I was hoping to be possible, but with ever smaller granularity - like a payment per data packet - so that absolutely no trust is required, and we don't need many small transactions.

Resending the initial transaction seems too much overhead to be done per data packet. Isn't it possible to make smaller increments? Like, in your first transaction, the scripts validates two signatures, one for the transaction without the amount, another of just the amount. So, at each new packet, you just send a new signed amount. Or even that would be too much to be sent at each packet? I hope not. At least Tor does 3 rounds of encryption per packet, so maybe just one tiny signature wouldn't be that much, would it?

[Mike Hearn]

Resending the initial transaction seems too much overhead to be done per data packet. Isn't it possible to make smaller increments? Like, in your first transaction, the scripts validates two signatures, one for the transaction without the amount, another of just the amount. So, at each new packet, you just send a new signed amount. Or even that would be too much to be sent at each packet? I hope not. At least Tor does 3 rounds of encryption per packet, so maybe just one tiny signature wouldn't be that much, would it?

ECDSA signature verification is more expensive than creation, and both are quite expensive, but you're right, it might not be a big deal. You can't sign only the amount and it wouldn't matter if you could because the cost of a signature is ~constant in the amount of data being signed (hashing is fast).

The best way to find out would be to implement or find a program that does ECDSA signing/verification of network traffic on a per-packet level. If you can show it working just fine on modern mobiles, no problem. You could include a new signature with every packet sent. The provider would know based on the setup parameters what transaction you had signed and could recreate it to verify the signature is valid.

Alternatively just simulate it. Measure the packet rates you'd need for interesting data usage (watching a video?) and then whip up a quick Java app that does ECDSA verification at those speeds, see what kind of cost it has. Modern mobiles have dual cores.

I don't think it's interesting to get micropayments to a finer granularity than a network packet, at least I can't think of a use case for that right now.

For the common case you really want to bill by time though, because you'll be receiving more data than you upload. Even if you sign every packet that doesn't do anything for the inbound side. So maybe re-negotiating the transaction every few seconds is still the right way to go.

The more I think about this the more a really fine grained solution seems needlessly clever. Paying in 10 second chunks keeps overheads low and the costs of being ripped off trivial.

[EhVedadoOAnonimato]

ECDSA signature verification is more expensive than creation, and both are quite expensive, but you're right, it might not be a big deal. You can't sign only the amount and it wouldn't matter if you could because the cost of a signature is ~constant in the amount of data being signed (hashing is fast).

I was thinking more on the amount of extra data to send together with every package than on the amount of CPU power. But maybe I was worrying with the wrong thing here.

The more I think about this the more a really fine grained solution seems needlessly clever. Paying in 10 second chunks keeps overheads low and the costs of being ripped off trivial.

You're probably right. Just start with small payments and even if your are ripped-off, that's an insignificant amount. And you can then broadcast on your reachable range that node X is not behaving nicely.

What about the blockchain costs? Don't you think these small payments would be too small for the block chain, in the sense that transactions fees would make a huge part of it? A 10s chunk for example should be extremely cheap so that this system is useful. People wouldn't like to pay much more than what they already pay for 3G access. Actually, the rate of adoption of such system would be quite higher if it could be cheaper than the existent networks.

Maybe a more centralized protocol would be a good idea there? Something like Open Transactions. Suppose both sender and router trust a set of e-wallet providers which implement a common
protocol for transacting inside their system. They could exchange these tokens, which could be really microscopic in amount, and then only perform a true blockchain transaction when they want to withdraw from the e-wallet. I'm not sure if it's a good idea since these token providers would probably have their own fees, but maybe they're are cheaper since there's no proof-of-work there.
The nice thing about Open Transactions is that it is generic... other things besides bitcoins could be used as means of payment.

[Mike Hearn]

What about the blockchain costs? Don't you think these small payments would be too small for the block chain, in the sense that transactions fees would make a huge part of it?

It'd just be factored into the price charged by the provider. Bitcoin transactions aren't free but they're still really cheap. Compared to the cost of data roaming a local Bitcoin-accepting access point will always win by orders of magnitude.

Bear in mind that you aren't actually broadcasting tiny transactions. You exchange transactions each time you buy another 10 second chunk. There are only ever two transactions actually included in the chain. If you use 100mb via somebody elses data connection, it costs the same blockchain-wise as if you use 1kb of transfer.

[MoonShadow]

You guys are really overthinking this use case.  In the use case of mobile bitcoin at a confrence or any other close locality, all that is needed to support local bitcoin payments for those without direct Internet access is a single piratebox within line of sight of both parties, running a bitcoind with a fairly current blockchain, that both users can connect to.  It's always in the interest of the receiver to get the transaction to the network, so that's not really an issue.  It'll happen.  But the piratebox would permit any number of connected devices to share transactions among themselves regardless of whether they were bluetooth capable or ad-hoc aware devices or not.  Payments to the piratebox owner isn't necessary either, because it's likely going to be owned by one or more of the vendors there who desire to trade in bitcoin.  If the business is good enough, it's also in the interest of the router owner/vendor to connect the piratebox to the Internet to keep the bitcoind updated directly, or possiblely to offer Internet access via the piratebox for a bitcoin payment.

[MoonShadow]

Say, as an example, you wanted to set up a piratebox like wifi access point that you could take with you anywhere, and sell short term shared Internet access for a bitcoin fee.  This is how I would do it.

I'd add a full bitcoind to the piratebox, with it's own dedicated drive space as well as a small squid space.  I'd set it up like a capture point, to direct new connections to my capture page with instructions and a bitcoin payment address.  This could be static and local, but if it was neither then I could have more than one such pirate box that users could move from one to another.  I would charge for the day/event not by volume, but also redirect bitcoin ports so that they lead back to the local bitcoind, and only allow that bitcoind outside access.  This prevents a new user from trying to bootstrap over my connection, he can get all the blocks he needs from the bitcoind.  I'd then block ports such as bittorrent, etc.  I'd take it with me to the game/convention/Burning Man/whatever so that the non-local crowd can pay me to share my unlimited 4G/WiMax plan, but limit the number of connected users to some rational shared Internet amount, say 32 connections.  If a connection is idle for more than 5 minutes, boot it to let another connect.  Make these conditions known, and then charge a rational fee for access for the entire event, say 1 BTC for the day/concert or 2 BTC for the entire convention, whatever.  Not much.

That's how I'd handle resaling internet.  But just a disconnected piratebox with a high connection limit and a running bitcoind would be fine to just allow people to transact without also sharing Internet.  This setup fits into a lunchbox and can run off a battery for hours.  Still kick connections if they are idle too long, to limit the number of connections and when people need to transact, they just connect again.  A convention hall could sport a number of these disconnected devices without the need for them to even be connected to each other, so long as the owner was willing and able to update their blockchain at least once each day.  A specialized app for this purpose could be developed to allow the owner to update a piratebox without it's own Internet connection via his smartphone's data plan.  Just download the most recent static image of the blockchain, upload to the piratebox, reboot and restart bitcoind.

This isn't the same use case as my Jabber + Dash7 + Bitcoin idea, however.

[Mike Hearn]

It's always in the interest of the receiver to get the transaction to the network, so that's not really an issue.  It'll happen.

Yes, one question is "how will it happen" and that's what we're discussing here. I think allowing anyone to relay Bitcoin transactions for free is something of a no-brainer, and a Bluetooth protocol for this should be easy to create and standardize on. But something based on ad-hoc wifi might also be a good plan. It's worth discussing.

You guys are really overthinking this use case.  In the use case of mobile bitcoin at a confrence or any other close locality, all that is needed to support local bitcoin payments for those without direct Internet access is a single piratebox

We might well be overthinking it, though discarded ideas here could potentially be reused elsewhere. But your solution won't solve the second problem I had in mind. We don't want a system that requires setup. I don't even know what a piratebox is, let alone where to get one or how to set one up. And if I did know, I probably wouldn't care enough to actually do it.

The goal should be seamlessness + zero trust. If I install an app on my Android phone that has a local (ie, cheap) data SIM, I want to be able to earn money with that without thinking about it, as I walk around, by reselling my data quota to other users. If somebody then wants to deliberately seed places Bitcoin users are likely to hang out with devices running the consumer fire-and-forget software, great, but it shouldn't be necessary.

And ideally users should not need to interact with capture pages or whatever. Just have it be completely automatic. You can set a budget in your app when you first install it, then just forget about it.

The details of how you offer internet access for Bitcoin without each side needing to trust each other (required for seamlessness) is what is being discussed. That's the true power of Bitcoin. Your plan fails as soon as somebody looking for a quick buck plugs in their own Piratebox that simply steals peoples payments and then serves an error page.

[MoonShadow]

We might well be overthinking it, though discarded ideas here could potentially be reused elsewhere. But your solution won't solve the second problem I had in mind. We don't want a system that requires setup. I don't even know what a piratebox is, let alone where to get one or how to set one up. And if I did know, I probably wouldn't care enough to actually do it.

The goal should be seamlessness + zero trust. If I install an app on my Android phone that has a local (ie, cheap) data SIM, I want to be able to earn money with that without thinking about it, as I walk around, by reselling my data quota to other users. If somebody then wants to deliberately seed places Bitcoin users are likely to hang out with devices running the consumer fire-and-forget software, great, but it shouldn't be necessary.

And ideally users should not need to interact with capture pages or whatever. Just have it be completely automatic. You can set a budget in your app when you first install it, then just forget about it.

The details of how you offer internet access for Bitcoin without each side needing to trust each other (required for seamlessness) is what is being discussed. That's the true power of Bitcoin. Your plan fails as soon as somebody looking for a quick buck plugs in their own Piratebox that simply steals peoples payments and then serves an error page.

You seem to have two conflicting goals here.  You want a seamless & automatic system, but also want to do it without considering supporting infrastructure.  I don't think that's possible, but if it is, something like Serval is what you wish to emulate...

http://www.servalproject.org/

Unfortunately, serval requires root access for at least some of the serval phones, which then function in exactly the same manner that a piratebox + Internet access point would.

This is a piratebox...

http://wiki.daviddarts.com/PirateBox

The two techs could be combined as well.  A single piratebox is cheaper than a single smartphone capable of running as a serval 'batphone'.  I've tried it on my Samsung Intercept, and it doesn't have the moxy to run as a batphone, but my android is on the slow end of smartphones these days.

[MoonShadow]

It's always in the interest of the receiver to get the transaction to the network, so that's not really an issue.  It'll happen.

Yes, one question is "how will it happen" and that's what we're discussing here. I think allowing anyone to relay Bitcoin transactions for free is something of a no-brainer, and a Bluetooth protocol for this should be easy to create and standardize on. But something based on ad-hoc wifi might also be a good plan. It's worth discussing.

IMHO trying to mesh with Bluetooth is doomed to failure.  It's practical range is too short, and it's session connect time too long.  Users sitting next to each other in a conference seminar would be able to mesh, but not users sitting on opposite ends of a single row of seats.  Users would have to deliberately stay in range to transact, which is fine for one-to-one transacting, but it doesn't allow for opprotunistic propagation of transactions.  Something along the lines of Forban might work, but it would be clunky. (http://www.foo.be/forban/) Setting your smartphone to autoconnect to a piratebox set up in the vendor's room for the purpose at the beginning of the convention would be about as automatic as I imagine that you can get.

EDIT:

If you're headed to a bitcoin convention, I can't imagine why the convention itself wouldn't sponsor the piratebox + bitcoind, connect the piratebox to a wired lan, port forward the local bitcoind and maybe all bitcoin traffic, and block everything else.  Then set up signs in the space chosen for this to inform attendees that this is the place to take your smartphone to bootstrap if you don't have Internet access.

[Mike Hearn]

Think broader than conventions. Let's say I phone up a couple of Bitcoin using friends who are visiting the country. We meet up at a coffee shop chosen 5 minutes before. We walk in and sit down. Their phones automatically start checking their mail, etc, using my connection, and we never even noticed because it's all automatically negotiated. If I leave but somebody else we never met before and who never met us happens to also be running the same software, it automatically switches to use his connection. It's possible because the protocol is trust free.

Is that coffee shop going to run something called a "pirate box"? Probably not. They most likely want you to use their own expensive wifi AP.

[Andreas Schildbach]

I don't see the absolute need of a working Wifi or the presence of a "pirate box".

If there is trust between the parties, all you need to do is transfer the tx via NFC, Bluetooth or even QR-Code (or your Radio project, for that matter) and you are set.

The tx can be broadcast to the network hours later, when one of the parties get a proper connection again.

I'd suggest focussing the feature on that single, very simple usecase. But do it right, i.e. establishing some standards that different clients can use.

Renting Internet to nearby people is something completely different and depends on a lot more factors.

[MoonShadow]

Think broader than conventions. Let's say I phone up a couple of Bitcoin using friends who are visiting the country. We meet up at a coffee shop chosen 5 minutes before. We walk in and sit down. Their phones automatically start checking their mail, etc, using my connection, and we never even noticed because it's all automatically negotiated. If I leave but somebody else we never met before and who never met us happens to also be running the same software, it automatically switches to use his connection. It's possible because the protocol is trust free.

Is that coffee shop going to run something called a "pirate box"? Probably not. They most likely want you to use their own expensive wifi AP.

Okay, but that is a different use case then you presented.  And this one is satisfied easily by a modified Serval app.  The problem is that most people don't let their wifi radio say on, because it eats power, and bluetooth is too short ranged to even do this across a relatively small restraunt.  Blutooth is practially limited to a range of about 10 feet with a direct line of sight, less if one or both phones are in a pocket next to the human body, which kills the band that Bluetooth uses (along with wifi) because of the water in the human body.  This would work incrediblely well with a running Dash7 radio in phones, but we would have to wait until those became common.  I don't even know if they ever will, Zigbee sure didn't.  Furthermore, it takes up to 2 seconds just to negotiate a new Bluetooth session, and that's before the clients can negotiate a bitcoin for forwarding access transaction.  It takes even longer for bluetooth to determine that a connected device has left range, so when you walk out of the room, it would take at least 10 seconds for your friends' phones to reconnect to anything else.  And then you have the same problem with this as you do with a fake piratebox setup, anyone can write an app that pretends to accept those automatic payments and then serves a 401 page. Or even an app that keeps disconnecting and reconnecting under another spoofed name, draining your budgeted wallet.

[MoonShadow]

Renting Internet to nearby people is something completely different and depends on a lot more factors.

Indeed, seems like we are trying to do too many things at once here.  The anonymous renting of bandwidth is a completely different problem than mobile meatspace bitcoin transactions.  The latter is actually easy with bluetooth or QR codes.  I presented the piratebox point only as an example of widely useful supporting infrastructure, which would allow customers to update their wallets.  But updating the wallets are not a requirement for a simple transaction.  Would be in the interests of the bitcoin accepting vendors, however, since a lightweight phone client can have more than enough actual BTC to make more than one transaction; but depending upon how those BTC are stored on the lightweight client, a user might not be able to spend all of his phone wallet without updating in order to get the block that has his change from previous transactions.

[caveden]

Renting Internet to nearby people is something completely different and depends on a lot more factors.

And I think this is the point of this thread, and for this very reason I must subscribe here.

This is very interesting and has great potential, I'd like to participate, or at least follow closely whatever you come up with.

[caveden]

The problem is that most people don't let their wifi radio say on, because it eats power, and bluetooth is too short ranged to even do this across a relatively small restraunt.  Blutooth is practially limited to a range of about 10 feet with a direct line of sight

Maybe phones would only be the consumers of such services. The providers could be people better equipped, in their homes, allowing unknown people to use their home connection, for a cheaper price than what they would normally pay for 3G...

[MoonShadow]

The problem is that most people don't let their wifi radio say on, because it eats power, and bluetooth is too short ranged to even do this across a relatively small restraunt.  Blutooth is practially limited to a range of about 10 feet with a direct line of sight

Maybe phones would only be the consumers of such services. The providers could be people better equipped, in their homes, allowing unknown people to use their home connection, for a cheaper price than what they would normally pay for 3G...

It would be a fine way for that very same coffe shop to provide customer internet, but most of around here do that already for free.  Even McDonald's around here offer free wifi, even though it's throttled.  I leave my home wifi open by default, on purpose.  If anyone is outside downloading p0rn, I've reduced transmitter power so that they would literallly have to stand on my lawn to do it; but my neighbors could use my signal if they needed to, just as I have used theirs in the past when my router was down.

Offline mobile to mobile bitcoin transactions have a real use case, particularly in the event of a widespread service outage, say caused by a power outage.  Any bitcoin vendor that had an access point set up something along the lines of a piratebox with a local bitcoind could still transact without power in a similar manner that they can transact cash only without power.  The corner store might not have power to run the milk reefer, but a battery backed access point that had Internet up to the point of the power failure can still use bitcoin to sell milk and butter at half-off.  I think that if bitcoin ever starts to grow, we will see such piratebox-like devices show up at the local Farmers' Market and the craft show.  The vendors that wish to sell products via bitcoin will make sure it happens.

[Serith]

All this would operate within fairly small time windows, because Bitcoin is pretty good at micropayments already anyway, but it's not good enough to do a payment for each packet transferred.

hashcoin had an idea about how to make extreme micro payments economically fisible, Instant TX for established business relationships

To get an idea of how powerful this is, with this kind of scheme you could include a payment on every packet going over the internet, or all kinds of extreme micro-payments.