[Stratum] Overlay network protocol over Bitcoin

[ripper234]

Good point. About DDoS - you can DDoS any service even without paying for it. You can just flood it with a lot of requests. So paying as a protection against *real* DDoS isn't a solution. Of course you can make service paid to avoid people misusing processing power. I'm already thinking about it, not sure if I found any viable solution.

Well, it's not the only solution, but it does indeed guarantee only minimal processing will be done on DDOS requests.

Brainstorming: I'm thinking about "credit service" and standard exception "Fee required", which will indicate that service operator want some fee for performing such call. It's up to every server operator which calls will be free or paid. When client receive "fee required" exception, he needs to authenticate to "credit service" with prepaid credit. When previous failed call will be retried, server will credit the fee from such prepaid account. Not sure if this is a good way, but it's the best solution which I found so far. Comments welcome.

It's a good direction. I think the main thing is that you want to ingrain API keys in the service at the deepest level, to make it easy to manage connections and fees. While some servers might support a "guest key" e.g. for testing, every call must have a valid key, that should be pre-registered (for free or not).

These are just some things to think about ... you don't need all the answers in advance. I actually started developing a small Bitcoin webapp today, and got stuck when I realized I'd have to maintain the entire blockchain (or even just the headers). If a prototype of this project comes out early enough (~ 1 month), I'll wait for it instead of writing and debugging blockchain-maintaining code.

You're exactly the person for who I'm doing this project :-). I see that maintaining full client is big overkill for some kind of projects which want to integrate with Bitcoin. And I'm almost sure there will be working server in less than one month. You're using PHP on your site, right? Please send me a PM with some details, I need to design PHP binding and I want to discuss it with somebody who's actively working in PHP...

Nice. Actually ... no, I loath PHP.

Working on Java/Play Framework. The project is open source, I'll publish it when it's ready.
Basically I just need a couple of API calls, so if you provide a JSON http API, I'll be happy to implement java bindings.

[slush]

- firstbits - I'm not really interested in that feature - if it's a security risk, postpone/cancel it.

Yes, depending on firstbits resolution made by another party can be risky. However, fake firstbits in really smart way needs significant computation power, because server operator needs to find his own address which corresponds to given firstbits prefix. It's almost impossible in real time so unless you're selling house using firstbits address, there's no *real* way how to misuse that. However server can also make a mistake, for example by calculating firstbits on wrong blockchain branch...

- withholding TX - mitigated by talking to N independent servers (not random servers to prevent someone from starting 100 instances, but known servers hosted by various known organizations and persons).

yes, possible

- Double spend - Mitigated by talking to N servers. If you send a TX to N independent servers, with at least N/2+1 honest nodes, then any attempt at a double spend will be easily detected.

Yes, possible. Also asking txradar service (on different server) can do the job easily.

- Start with a single server. Next step would be a hard code list of trusted servers, with requests going out to N of them, and at least K have to agree. Future work - please don't let this delaying getting the first server operational ... 1 is so much better than 0.

It's a matter of days when I'll start beta server. I still need to finish some stuff to make it really usable.

- SSL should be mandatory, probably from day 1. I don't see how the protocol itself need to change, just the transport.

TCP socket with SSL is already implemented. It's another transport (on another port), so it's absolutely to user which port/transport he choose.

[slush]

Working on Java/Play Framework. The project is open source, I'll publish it when it's ready.
Basically I just need a couple of API calls, so if you provide a JSON http API, I'll be happy to implement java bindings.

Even better. I'm able to write PHP binding, but not a Java one. Having a protocol implementation and at least "HTTP polling" transport (probably the easiest transport to implement) in Java would be amazing.

[ripper234]

Working on Java/Play Framework. The project is open source, I'll publish it when it's ready.
Basically I just need a couple of API calls, so if you provide a JSON http API, I'll be happy to implement java bindings.

Even better. I'm able to write PHP binding, but not a Java one. Having a protocol implementation and at least "HTTP polling" transport (probably the easiest transport to implement) in Java would be amazing.

Did you know about BCCAPI? It seems to be the third such project I've heard about, trying to solve the same problem (1st being Overlay, 2nd bitcoinjs Exit Nodes).

This one does a java client.

The leaders of these three projects should get together and talk ... see if they can make a unified standard now, before it's too late.

[kjj]

- firstbits - I'm not really interested in that feature - if it's a security risk, postpone/cancel it.

Yes, depending on firstbits resolution made by another party can be risky. However, fake firstbits in really smart way needs significant computation power, because server operator needs to find his own address which corresponds to given firstbits prefix. It's almost impossible in real time so unless you're selling house using firstbits address, there's no *real* way how to misuse that. However server can also make a mistake, for example by calculating firstbits on wrong blockchain branch...

Exactly.  Firstbits can only be safe if the person doing the lookup has the full block chain, AND if the address in question is buried deeply enough in the chain that a reorg can't touch it.  If either of these are false, you are vulnerable.

I'm not sure how widely known that second part is, but since the point of firstbits is to have addresses known in advance, the odds of getting a fresh (aka vulnerable) one are already small.

Don't forget that an attacker doesn't need to wait for a spender to come along before he starts looking for his own bogus addresses that look like firstbits matches.  Since the point of firstbits is for the address to be well known in advance, he can start compiling his database now, and then wait until he sees a transaction to one he's already found before he attacks.

Personally, I think that the inevitable proliferation of chainless light clients is going to kill firstbits, for exactly these reasons.  There is just no way to make it safe without checking on your own fully chained node.

By the way, when I was researching this sort of thing, I came to a couple of surprising conclusions.  First, unidirectional RPC will work totally fine, it is never necessary for the server to initiate, and no state is ever needed.  Second, there are only a few RPC calls missing from the standard client that would be necessary to fully support light clients.  And third, as long as the light client is creating the transaction internally and using the server as a dumb relay, a malicious server can't do any real damage, it can only cause some light mischief.  (That third one is only valid from the spender's point of view, of course.  An owned server is still a big problem for the owner of the server, just not for other people that use it.)

[slush]

Did you know about BCCAPI? It seems to be the third such project I've heard about, trying to solve the same problem (1st being Overlay, 2nd bitcoinjs Exit Nodes).

Yes, I know about BCCAPI and bitcoinjs. BCCAPI is (right now) solving only part of the problem (just a subset which I call "wallet/blockchain services"), it's using custom binary protocol (in the oposite of json-rpc) and only polling transport (in the oposite of various transports). Also server implementation is closed source (I have code on gitorious already).

BitcoinJS has similar purpose. I talked with Stephan Thomas about bitcoinjs in Prague and the result is that he wants to do everything himself.

[ripper234]

Did you know about BCCAPI? It seems to be the third such project I've heard about, trying to solve the same problem (1st being Overlay, 2nd bitcoinjs Exit Nodes).

Yes, I know about BCCAPI and bitcoinjs. BCCAPI is (right now) solving only part of the problem (just a subset which I call "wallet/blockchain services"), it's using custom binary protocol (in the oposite of json-rpc) and only polling transport (in the oposite of various transports). Also server implementation is closed source (I have code on gitorious already).

BitcoinJS has similar purpose. I talked with Stephan Thomas about bitcoinjs in Prague and the result is that he wants to do everything himself.

I see.
I hate "open source" projects that are self centered and don't think big enough.
So much potential for good things, so many misses.

Edit: I don't know too much about bitcoinjs, this is just a random rant that might or might not be relevant.

I'm very much excited about Overlay, and it looks like you're really out to build something good here.
If needed, you can contact me for any questions at ron.gross@gmail.com

[genjix]

I support slush and ThomasV.

[slush]

Brainstorming about signing messages

In the concept of service oriented architecture, some service calls can be proxied to backend or sent over non trusted channel. I like Firstbits as an example of proxied call, but of course there can be a lot of another examples as well as firstbits lookup can be implemented directly inside overlay server and proxy call isn't necessary at all.

For now, during the call of firstbits.resolve, the flow of call is following:

client -> (some transport) -> overlay server -> HTTP (firstbits.com don't support https yet!) -> firstbits.com

Client need to trust every part of this chain. For now, you must use some transport which prevent MITM, trust overlay server operator, hope that there isn't MITM attack in HTTP request to firstbits.com (I hope firstbits fix that and provide https soon).

Well, what if firstbits.com can sign it's response to confirm that resolution has been done directly by the service, which is trusted by client? Then firstbits resolution can be done over pidgin transport and nobody care, because the response is signed with service's key...

JSON-RPC don't offer any standard way how to sign messages, transports usually don't offer signatures either, so I want to fix it in some way. I'm not a crypto expert, but I have some idea how it should be done. Feel free to correct me and propose anything safer/easier:

Signature should be assembled from following information:
a) initial request
b) timestamp of processing
c) response

Signature should not be done from whole json message itself, only from payload, because json serialization can be somehow ambiguous, for example parameter 'id' can be changed during the transport.

I has been thinking about using GPG mechanism, which is widely used platform even for distributing trust, but it looks prettyheavy for such purpose. Not sure if it's possible to check GPG signatures in $3 AVR processor. However Bitcoin world already use signatures pretty nicely and clients already needs ecdsa libraries on their side for signing transactions, so using ecdsa sounds reasonable and pretty easy to me. Simple example for signing/verifying data using SECP256k1 curve in python can be found here: http://pastebin.com/LnPijjfm

However I see real issue in needed CPU time for signing. On my laptop, one signature takes around 200ms. It's low-end one, but it will take some time even on high-end servers. Any idea how to solve it?

Final signed response should looks similar like:
{"id": "1234", "signature": "MEUCIHM3m9IX6oudiBOXLx5bavACtB6uJNFDr8Ir6qVX54nhAiEA9SBgR1tOxEJnVJBqhKt+QfE0ry0h8yP2M7KinmQ/yPs=", timestamp: "1325202560", "result": ["blahblah"], "error": null}

However the question is which pattern/algorithm use to assemble data for signing (request payload, timestamp, response payload). Is there any reasonable solution for that?

[eldentyrell]

Nobody said that all nodes are created equal.

Indeed, the problem is that nobody has said anything at all about equality (aka trust).

[eldentyrell]

So yes - if you don't have full copy of blockchain, you need to trust somebody else, at least on some level.

Thanks slush.  I urge you to be very specific about who this "somebody else" is and exactly what "level".

Without this information, it is not possible for independent third parties to do a security analysis of your protocol.  I would not recommend that people use a protocol that has not (and can not) be analyzed by independent third parties.  History has shown that without this sort of independent analysis, gruesome and nasty security flaws inevitably crop up.

[kjj]

Brainstorming about signing messages
Final signed response should looks similar like:
{"id": "1234", "signature": "MEUCIHM3m9IX6oudiBOXLx5bavACtB6uJNFDr8Ir6qVX54nhAiEA9SBgR1tOxEJnVJBqhKt+QfE0ry0h8yP2M7KinmQ/yPs=", timestamp: "1325202560", "result": ["blahblah"], "error": null}

However the question is which pattern/algorithm use to assemble data for signing (request payload, timestamp, response payload). Is there any reasonable solution for that?

Add a "signature_algorithm" key to the response.  Also, allow the request to specify a list of acceptable algorithms, like {"id": "1234", "signatures_accepted": "ecdsa: SECP256r1, SECP521r1; pkcs 1", "firstbits": "1payBTC"}  If the server can't provide a signature that the client is willing to accept, throw an error response.  Sadly, this is a damned if you do, damned if you don't situation.  If you lock in to a single system, you are stuck with that system and the hassle of replacing it later.  If you make it extensible, you have the hassle of actually supporting multiple systems.  (See IPSEC)

As for actually calculating it, there are two ways to go.  In a binary protocol/format or when the length of the signature is known in advance, it is common to construct the response using zeros to fill in the signature field, then calculate the signature based on that, then overwrite the zeros with the actual signature.  In a text stream like this, I would build the response without the signature key and value, then construct a new response that includes them.  Or just insert them, modern languages have no problem chopping and splicing strings, and C programmers already have lots of practice doing it the hard way.

[slush]

Thanks slush.  I urge you to be very specific about who this "somebody else" is and exactly what "level".

Somebody else = operator of overlay server. It's as simple as this. When we talk about blockchain services, the necessary trust to other party (=operator) is higher than in using full blockchain by self, but a lot lower than depending on "web wallet", because you're still the owner of your funds.

In the case of other (non-blockchain) services like fetching usd/btc quotes from overlay server, it's the same like now; you still need to trust bitcoin exchange and service like bitcoincharts, which is aggregating quotes for you.

Without this information, it is not possible for independent third parties to do a security analysis of your protocol.

What exactly are you missing and in which form you need such information?

[slush]

However I see real issue in needed CPU time for signing. On my laptop, one signature takes around 200ms. It's low-end one, but it will take some time even on high-end servers. Any idea how to solve it?

I found that only python's ecdsa module is so slow. Author of ecdsa package did some comparsion to C++ and it was 20-30x faster. So the obvious solution is "implement python's ecdsa signatures now, optimize it with C++ speedup later". Signed messages have sense only for proxied calls or when using non-secure transport, so <5 ms per signature per message is doable in such situations.

[ripper234]

slush, how would the transaction mechanism work?

What would I need to calculate client side in order to authorize a transaction?
Is there a Java implementation of that somewhere (bitcoinj?)?

[slush]

Add a "signature_algorithm" key to the response.  Also, allow the request to specify a list of acceptable algorithms, like {"id": "1234", "signatures_accepted": "ecdsa: SECP256r1, SECP521r1; pkcs 1", "firstbits": "1payBTC"}

good idea

As for actually calculating it, there are two ways to go.  In a binary protocol/format or when the length of the signature is known in advance, it is common to construct the response using zeros to fill in the signature field, then calculate the signature based on that, then overwrite the zeros with the actual signature.  In a text stream like this, I would build the response without the signature key and value, then construct a new response that includes them.  Or just insert them, modern languages have no problem chopping and splicing strings, and C programmers already have lots of practice doing it the hard way.

Yes, I was thinking about this, too. Unfortunately it's getting slightly complicated, because there are also some other fields which can be changed without corrupting the signature, like message "id". It's because ID must be unique in particular session, but this signed response can be created as a response to some proxy call to backend (in the firstbits example, signature is created directly by firstbits service, but signature must be valid also as a response from overlay server to client.

Another issue is that fields in json-rpc don't have strict order, so two identical and valid json-rpc may have different signature (well, 2112 must be laughing now :-) ). This is problematic for validating messages, because you need to extract fields which are not part of signed message, but not affect message payload.

This leads me to conclusion that trying to sign/verify message itself can be very fragile. I also don't want to go against json-rpc specification and force such things like order of fields. Currently I don't know how to decide this issue, is there any best practice to doing this? How other text-based protocols solve such problem?

[EhVedadoOAnonimato]

Sorry if I'm being repetitive, I haven't read all 4 pages of discussion.

But one thing that I don't understand is why are people so in a rush to implement client-server solutions, when a p2p lightweight solution is perfectly possible, and we already have BitcoinJ to demonstrate. BitcoinJ is lightweight to the point you can use it on a mobile phone. And it could scale very well even when blocks are huge if people develop a new protocol message of the kind "what are the outputs of block X?".

Anyway, I don't like the client-server solution due to the fact that the server may know everything you do with your money. You risk losing your privacy when going client-server. Okay, you may hide your IP behind Tor or something, but most people don't even know how to do that. And that might not be enough depending on how the client-server protocol works. If the "what's my balance?" message sends the entire list of address the client has, than Tor won't help, the server already knows your entire wallet. All a malicious server needs now is to link one of these address to the actual owner. And that's not that difficult, just see how many people have public tip jars for example.

There's a strong privacy issue in client-server solutions. IMHO you clever developers should give priority to lightweight p2p solutions, or at least be always very clear on the privacy risks of a client-server solution, so that nobody can say he didn't know about it.

[ripper234]

Sorry if I'm being repetitive, I haven't read all 4 pages of discussion.

But one thing that I don't understand is why are people so in a rush to implement client-server solutions, when a p2p lightweight solution is perfectly possible, and we already have BitcoinJ to demonstrate. BitcoinJ is lightweight to the point you can use it on a mobile phone. And it could scale very well even when blocks are huge if people develop a new protocol message of the kind "what are the outputs of block X?".

Anyway, I don't like the client-server solution due to the fact that the server may know everything you do with your money. You risk losing your privacy when going client-server. Okay, you may hide your IP behind Tor or something, but most people don't even know how to do that. And that might not be enough depending on how the client-server protocol works. If the "what's my balance?" message sends the entire list of address the client has, than Tor won't help, the server already knows your entire wallet. All a malicious server needs now is to link one of these address to the actual owner. And that's not that difficult, just see how many people have public tip jars for example.

There's a strong privacy issue in client-server solutions. IMHO you clever developers should give priority to lightweight p2p solutions, or at least be always very clear on the privacy risks of a client-server solution, so that nobody can say he didn't know about it.

Nobody really cares about privacy anymore. We want convenience first. And a client that keeps zero information is more convenient (easier to program, less space requirement) than a client that maintains a full or even partial blockchain.

Bitcoin is novel in that it enables privacy, lack of central control etc ... but that doesn't mean that every real world application of it requires these properties. I would be happy if my bank started dealing with Bitcoin, because this would increase competition between banks and reduce costs, not (just) because of privacy. When I need privacy in Bitcoin, I'll buy some BTC using cash from someone and use a full P2P client behind TOR. For the other 364.9 days of the year, I'll use a thin "semi-centralized" client.

[EhVedadoOAnonimato]

Nobody really cares about privacy anymore. We want convenience first. And a client that keeps zero information is more convenient (easier to program, less space requirement) than a client that maintains a full or even partial blockchain.

First, a lightweight p2p client is very convenient.
And second, I find bitcoin privacy of major importance, because it makes bitcoin possibly the best way for people to evade taxes while still transacting online. If you believe most people are "government suckers" who want to give their money away then, well, fine, it's your opinion. Maybe for some countries that might even be true. But anyway, all I'm asking is for people to consider the lightweight p2p option, which is trust-free and scale very well, while keeping your privacy, if you happen to care.

At least be open on the privacy risks in using client-server solutions. People downloading the software should know.

[kjj]

Add a "signature_algorithm" key to the response.  Also, allow the request to specify a list of acceptable algorithms, like {"id": "1234", "signatures_accepted": "ecdsa: SECP256r1, SECP521r1; pkcs 1", "firstbits": "1payBTC"}

good idea

As for actually calculating it, there are two ways to go.  In a binary protocol/format or when the length of the signature is known in advance, it is common to construct the response using zeros to fill in the signature field, then calculate the signature based on that, then overwrite the zeros with the actual signature.  In a text stream like this, I would build the response without the signature key and value, then construct a new response that includes them.  Or just insert them, modern languages have no problem chopping and splicing strings, and C programmers already have lots of practice doing it the hard way.

Yes, I was thinking about this, too. Unfortunately it's getting slightly complicated, because there are also some other fields which can be changed without corrupting the signature, like message "id". It's because ID must be unique in particular session, but this signed response can be created as a response to some proxy call to backend (in the firstbits example, signature is created directly by firstbits service, but signature must be valid also as a response from overlay server to client.

Another issue is that fields in json-rpc don't have strict order, so two identical and valid json-rpc may have different signature (well, 2112 must be laughing now :-) ). This is problematic for validating messages, because you need to extract fields which are not part of signed message, but not affect message payload.

This leads me to conclusion that trying to sign/verify message itself can be very fragile. I also don't want to go against json-rpc specification and force such things like order of fields. Currently I don't know how to decide this issue, is there any best practice to doing this? How other text-based protocols solve such problem?

For the usual case, you don't care that multiple messages might be equally valid.  The signature is for "this message", not for "any message bearing the same content as this message".

If you are worried that a proxy might replace the message with a message that is different but equivalent, then you need to have a canonical form, and you should only emit the canonical form.  When the client receives a message, it must convert it into canonical form before checking the signature.

As for the ID, don't leave it out of the signature unless you enjoy replay attacks.  Just force the client to make it globally unique.  There are already well established techniques for doing this.