Right now the big idea for scaling Bitcoin is the Lightning network, which lets people do most of their transactions off-chain and only occasionally settle the balances on the actual blockchain. Like the vault I described earlier, it turns out to be way easier on Ethereum.
The basic idea is called a payment channel. Let's say Alice wants to make a lot of payments to Bob, without paying gas fees for every transaction. She sets up a contract and deposits some ether. For each payment, she sends Bob a signed message, saying "I agree to give $X to Bob." At any time, Bob can post one of Alice's message to the contract, which will check the signature and send Bob the money.
The trick is, Bob can only do this once. After he does it, the contract remembers it's done, and refunds the remaining money to Alice. So Alice can send Bob a series of messages, each with a higher payment. If she's already sent Bob a message that pays 10 ether, she can pay him another ether by sending a message that pays 11 ether.
We can also add an expiration date, after which Alice can retrieve any money she deposited that's not already paid out. Until then, her funds are locked. Before the deadline, Bob is perfectly safe keeping everything offline. He just has to check the balance and deadline, and be sure to post the message with the highest value before the deadline expires.
There's sample code at a project on github. This version uses Whisper, which is Ethereum's built-in messaging system. That's basically working but not enabled by default, so it's not quite fully usable. But any communications channel can work. In fact, this sample was made by EtherAPIs, which plans to use similar code to let people send micropayments over HTTP for API calls.
The actual smart contract code is here. I've excerpted the part with the magic, and simplified it slightly:
function verify(uint channel, address recipient, uint value,
uint8 v, bytes32 r, bytes32 s) constant returns(bool) {
PaymentChannel ch = channels[channel];
return ch.valid &&
ch.validUntil > block.timestamp &&
ch.owner == ecrecover(sha3(channel, recipient, value),
v, r, s);
}
function claim(uint channel, address recipient, uint value,
uint8 v, bytes32 r, bytes32 s) {
if (!verify(channel, recipient, value, v, r, s)) return;
if (msg.sender != recipient) return;
PaymentChannel ch = channels[channel];
channels[channel].valid = false;
uint chval = channels[channel].value;
uint val = value;
if (val > chval) val = chval;
channels[channel].value -= val;
if (!recipient.call.value(val)()) throw;;
}
This contract can handle lots of payment channels, each with an owner.
Alice sends Bob a message with the following values:
- the id of the channel she's using (since this contract can handle lots of channels)
- the recipient, i.e. Bob's address
- the value of her payment
- her signature, consisting of the three numbers v, r, s (a standard elliptic curve signature)
The verify function starts by taking a hash of the channel id, recipient, and value. The sha3 function can take any number of parameters, and it'll just mash them together and hash it all:
sha3(channel, recipient, value)
To verify the signature we use the ecrecover function, which takes a hash and the signature (v, r, s), and returns the address that produced that signature. We just check that to make sure the signature was made by the channel owner:
ch.owner == ecrecover(sha3(channel, recipient, value), v, r, s);
Make sure the channel is still active and the deadline hasn't passed, and we're done verifying. The claim function first calls verify, and if that returns true, sends the money to Bob and sets channel.valid to false so Bob can't make withdraw any more funds.
If Alice overdraws her funds, it's up to Bob to stop accepting her payments. In case he screws up, we check for that; if funds are overdrawn we reduce the payment to what's available in the channel.
A unidirectional channel like this works a lot like the blind auction. Only Bob is allowed to call claim(), and his incentive is to claim the most money he can, which is exactly what we want to happen.
Duplex channels
Suppose Alice and Bob want to make frequent small payments to each other. They could use two channels, but that means closing out each channel when it runs out of funds, even if their net balances haven't changed much. It'd be better if we had duplex channels, where payments flow both directions.
One method is for one party to submit the current state (i.e. balances for both parties), and allow time for the other party to submit a more recent state. This works for any sort of state channel, but it gets a little complicated. We have to include a nonce that increments with each message; what if Alice and Bob send messages to each other at the same time?
For simple value transfers there's an easier way. Instead of including a net balance, have messages just add to the total funds sent so far by the message sender. The contract figures net balances when the channel closes. This keeps us from having to worry about message ordering. We can trust both parties to send their most recent receipt, since that will be the one that pays them the most.
To calculate the net payment to Alice, we take Alice's balance, add Alice's total receivable, and subtract Bob's total receivable. It's ok if the receivables exceed the balances, it just means the money's gone back and forth a lot. As before, we adjust receivables downward if someone overdraws.
To make this work we remove the immediate ether transfer from the claim function, and let each party withdraw after both claims are submitted. If one party doesn't submit a claim before the deadline, we assume they received no money. An attacker could attempt to spam the network to prevent the other party from submitting its receipt; to mitigate this we'll need to make sure the channel stays open for some minimum time period after the first claim.
A network of channels
But Lightning is more than two-party payment channels. It'd be pretty hard on cash flow if you had to deposit a bunch of money in a payment channel for everyone you might want to pay a few times. Lightning is supposed to let you route payments through intermediaries. With a network of payment channels, you can route your payment anywhere you want it to go, as long as you can find a path through the network to your payee.
The Lightning paper (pdf) is hard to understand in detail if you don't know Bitcoin opcodes, which I don't. But recently I found a wonderful little article that described the basic concept, which is really quite simple and elegant, and realized it's easy to implement on Ethereum.
Let's say Alice wants to pay 10 ether to Carol. She doesn't have a channel to Carol but she does have a channel to Bob, who has a channel to Carol. So the payment needs to flow from Alice to Bob to Carol.
Carol makes a random number, which we'll call Secret, and hashes it to make HashedSecret. She gives HashedSecret to Alice.
Alice sends a message to Bob, which is just like the two-party payment channel message, but adds the HashedSecret. To claim the money, Bob has to submit this message to the contract along with the matching Secret. He has to get that secret from Carol.
So he sends a similar message to Carol, with the same payment value minus his service fee. Service fees don't have to be implemented in the contract; each node just sends a slightly smaller payment to the next node.
Carol of course already has the Secret, so she can immediately claim her funds from Bob. If she does, then Bob will see the Secret on the blockchain, and be able to claim his funds from Alice.
But instead of doing that, she can just send the Secret to Bob. Now Bob can retrieve his money from Alice, even if Carol never touches the blockchain again.
So at this point:
- Carol is able to claim funds from Bob by submitting his signed statement and the matching secret.
- Bob has the secret too, so he's able to claim his money from Alice
- Bob sends the secret to Alice so she has verification that Carol got the payment
As we make new payments, we do the same as two-party channels, just updating the total. This means the recipient only has to keep the most recent secret.
To make all this work, all we have to do is slightly modify our verify and claim functions:
function verify(uint channel, address recipient, uint value,
bytes32 secret, uint8 v, bytes32 r, bytes32 s)
constant returns(bool) {
PaymentChannel ch = channels[channel];
if !(ch.valid && ch.validUntil > block.timestamp) return false;
bytes32 hashedSecret = sha3(secret)
return ch.owner == ecrecover(sha3(channel, recipient,
hashedSecret, value), v, r, s);
}
function claim(uint channel, address recipient, uint value,
bytes32 secret, uint8 v, bytes32 r, bytes32 s) {
if( !verify(channel, recipient, value, secret, v, r, s) ) return;
Now the signature is over the sha3 of the channel, recipient, hashedSecret, and value. And we're passing in the secret, and verifying that it hashes to what's in the signature.
Early Shutdown
Imagine that Alice want to pay Dave, and routes the payment through Bob and then Carol. So this is payment ABCD. Let's say this is the first payment in the BC channel, so Bob's total accumulated payment balance to Carol is just the ABCD amount. But Dave never reveals the secret.
Now Eddie wants to pay Fred, also through Bob and Carol, making payment EBCF.
To process EBCF, Bob has to add Eddie's payment amount on top of Carol's, so the total accumulated payment on BC is ABCD + EBCF. But Carol can redeem that balance with just the secret from Fred.
Bob can use Fred's secret to claim the money from Eddie. But without Dave's secret, he can't claim the money from Alice, so he eats a loss in the amount of the ABCD payment.
So Bob has to avoid putting new payments on the BC channel while there's an unrevealed secret. (It's tempting to think he could issue EBCF with a total that assumes ABCD didn't exist, but what if the secret's revealed later?)
This means we should let nodes shut down their channels early, so they can restart if they stall. Over time, people will settle on reliable partners.
This also means that channels are completely synchronous, which isn't ideal for a scalability solution. Fast webservers don't process one request at a time; they can accept lots of requests and send each response whenever it's ready. But a Lightning channel has to go through a complete request-response before it can accept another request. I think this is also the case with Bitcoin's Lightning. Still, compared to putting every transaction on chain, we can do pretty well.
Maybe these synchronous channels help avoid centralization. Since each channel has limited throughput, users are better off routing through low-traffic channels.
Routing
Speaking of routing, it's really easy because we can do it all locally on the client. All the channels are set up on chain, so the client can just read them all into memory and use whatever routing algorithm it likes. Then it can send the complete route in the off-chain message. This also lets the sender figure out the total transaction fees that will be charged by all the intermediaries.
To make this easy, we can just use events to log each new channel. The javascript API can query up to three indexed properties, so we index on the two endpoint addresses and the expiration. We'll also log the off-chain contact info for each address; it could be http, email, whatever. The javascript queries the channels, asks the endpoints how much funds they have available, and constructs a route.
The Contract
As far as I know, what I've described pretty much does what Lightning does, and we can implement it with a contract that's two pages long. We'll need client code to handle the routing and messaging, but the on-chain infrastructure is really simple and works without any changes to Ethereum. Here's some totally untested code for the whole contract.
contract Lightning {
modifier noeth() { if (msg.value > 0) throw; _ }
function() noeth {}
uint finalizationDelay = 10000;
event LogUser(address indexed user, string contactinfo);
event LogChannel(address indexed user, address indexed bob,
uint indexed expireblock, uint channelnum);
event LogClaim(uint indexed channel, bytes32 secret);
struct Endpoint {
uint96 balance;
uint96 receivable;
bool paid;
bool closed;
}
struct Channel {
uint expireblock;
address alice;
address bob;
mapping (address => Endpoint) endpoints;
}
mapping (uint => Channel) channels;
uint maxchannel;
function registerUser(string contactinfo) noeth {
LogUser(msg.sender, contactinfo);
}
function makeChannel(address alice, address bob, uint expireblock) noeth {
maxchannel += 1;
channels[maxchannel].alice = alice;
channels[maxchannel].bob = bob;
channels[maxchannel].expireblock = expireblock;
LogChannel(alice, bob, expireblock, maxchannel);
}
function deposit(uint channel) {
Channel ch = channels[channel];
if (ch.alice != msg.sender && ch.bob != msg.sender) throw;
ch.endpoints[msg.sender].balance += uint96(msg.value);
}
function channelExpired(uint channel) private returns (bool) {
return channels[channel].expireblock < block.number;
}
function channelClosed(uint channel) private returns (bool) {
Channel ch = channels[channel];
return channelExpired(channel) ||
(ch.endpoints[ch.alice].closed &&
ch.endpoints[ch.bob].closed);
}
//Sig must be valid,
//signer must be one endpoint and recipient the other
function verify(uint channel, address recipient, uint value,
bytes32 secret, uint8 v, bytes32 r, bytes32 s)
private returns(bool) {
bytes32 hashedSecret = sha3(secret);
address signer = ecrecover(sha3(channel, recipient,
hashedSecret, value),
v, r, s);
Channel ch = channels[channel];
return (signer == ch.alice && recipient == ch.bob) ||
(signer == ch.bob && recipient == ch.alice);
}
function claim(uint channel, address recipient, uint96 value,
bytes32 secret, uint8 v, bytes32 r, bytes32 s) noeth {
Channel ch = channels[channel];
Endpoint ep = ch.endpoints[recipient];
if ( !verify(channel, recipient, value, secret, v, r, s)
|| channelClosed(channel)
|| ep.receivable + ep.balance < ep.balance ) return;
ep.closed = true;
ep.receivable = value;
//if this is first claim,
//make sure other party has sufficient time to submit claim
if (!channelClosed(channel) &&
ch.expireblock < block.number + finalizationDelay) {
ch.expireblock = block.number + finalizationDelay;
}
LogClaim(channel, secret);
}
function withdraw(uint channel) noeth {
Channel ch = channels[channel];
if ( (msg.sender != ch.alice && msg.sender != ch.bob)
|| ch.endpoints[msg.sender].paid
|| !channelClosed(channel) ) return;
Endpoint alice = ch.endpoints[ch.alice];
Endpoint bob = ch.endpoints[ch.bob];
uint alicereceivable = alice.receivable;
uint bobreceivable = bob.receivable;
//if anyone overdrew, just take what they have
if (alicereceivable > bob.balance + bob.receivable) {
alicereceivable = bob.balance + bob.receivable;
}
if (bobreceivable > alice.balance + alice.receivable) {
bobreceivable = alice.balance + alice.receivable;
}
uint alicenet = alice.balance - bobreceivable + alicereceivable;
uint bobnet = bob.balance - alicereceivable + bobreceivable;
//make double sure a bug can't drain from other channels...
if (alicenet + bobnet > alice.balance + bob.balance) return;
uint net;
if (msg.sender == ch.alice) {
net = alicenet;
} else {
net = bobnet;
}
ch.endpoints[msg.sender].paid = true;
if (!msg.sender.call.value(net)()) throw;
}
}
Tokens
The code above does everything with ether. But it wouldn't be hard to extend it to use other tokens. Set the token address when creating a channel, change the deposit and withdraw functions, and you're done.
Further reading
The Raiden Network is a well-known implementation of a lightning-style network on Ethereum. Its Solidity code is significantly more complicated; compared to Sparky, it uses ERC20 tokens instead of ether, has a different settlement mechanism, and uses some assembly for performance optimization. The project includes all the off-chain infrastructure too.
Here's an article about payment channel networks on Ethereum and Bitcoin, with some interesting ideas.
Vitalik recently described state channels at a financial conference.