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