A cautionary note: I just forked webbtc.com/bitcoin-ruby via two different ways

[Peter Todd]

webbtc.com runs on bitcoin-ruby, a re-implementation of Bitcoin, and as we keep saying over and over again, re-implementations are dangerous because they invariably have bugs and don't duplicate bitcoin-qt behavior exactly.

I forked webbtc.com on testnet yesterday, still not quite sure how I pulled that off, but I was playing with non-standard transactions.

I also forked webbtc.com on mainnet today with transaction 315ac7d4c26d69668129cc352851d9389b4a6868f1509c6c8b66bead11e2619f It has two inputs, both using SIGHHASH_SINGLE, and only one output. SignatureHash() in script.cpp has the following code:


if (nOut >= txTmp.vout.size())
{
    printf("ERROR: SignatureHash() : nOut=%d out of range\n", nOut);
    return 1;
}


The thing is, that's not actually an error. SignatureHash() returns the hash of the signature, and CheckSig() doesn't check the return code, so it acts as though the hash the signature signed was 0000000000000000000000000000000000000000000000000000000000000001 You can create a signature for that, and it works just fine and the transaction is considered valid.

bitcoin-ruby and libbitcoin, and probably a few more, all treat this case as an actual error and fail, so they get forked from the main network and are vulnerable to an attacker creating fake confirmations.

I was auditing litecoin this weekend, and in the process found a half-dozen obscure edge cases in Bitcoin's scripting code that I didn't know about it, and I'm already an expert on how Bitcoin works. Frankly the science of software engineering just isn't at the point where we know how to re-implement bitcoin and get it right. This is a problem at least as hard as writing safety-critical flight avionics software; in my opinion it's probably harder.

DO NOT TRUST RE-IMPLEMENTATIONS OF BITCOIN WITH YOUR MONEY
DO NOT WRITE FULL-NODE RE-IMPLEMENTATIONS OF BITCOIN
YOU ARE NOT SMART ENOUGH TO MAKE THEM SECURE, NOBODY IS

[gmaxwell]

writing safety-critical flight avionics software

I think software for avionics has a lot to teach us. In particular, modified condition/decision coverage is important.

In this case a coverage analysis of these implementations run against their tests (maybe just the main blockchain) would show the nOut >= txTmp.vout.size() branch never taken.

What avionics software doesn't teach us as much about is handling adaptively hostile input (though if your code is correct for all inputs that hostile is just a subset— but hard to be confident that you're correct for all with cryptographic constructs in the loop), nor does it so much about implementation agreement in consensus systems. I suppose avionics would tell us we need to be testing the whole network as a single system because of the inescapable tight coupling, but sadly thats not realistic.

They could have had a test for it failing in that case... and seen that it rejected the block. The coverage would be good, it would be a sensible self-consistent behavior... but not consistent with the reference implementation.

Right now because the rules logic in the reference software doesn't have any test available which achieves anything close to modified condition/decision coverage (which, in also fairly hard to measure because the code is written in C++ and does a lot of dynamic allocation and boost-dance) it means that even if you test an alternative well you can't compare it to Bitcoind unless the same tests also test the reference implementation equally well.

But there are still tests which do test _a lot_ of it, and it seems they weren't used here:

It's worth noting here that Bluematt found this behavior about a year ago. The blocktester should be testing it.  I guess this indicates these alternative implementations have not been tested with the blocktester.  I suppose that in and of itself is a bit more concerning then even the specific failure.  On the other hand, the fact that they haven't been means we actually get an indication of their level of review which we wouldn't have gotten if the blocktester had already been run an exposed all the known-troublesome spots.

[Remember remember the 5th of November]

I'm already an expert on how Bitcoin works.

I don't want to be a douche, but those words shouldn't be used too lightly. As an example, I personally wouldn't call Linus Torvalds an expert of his own kernel, because we see constantly people fixing bugs(that might have been made by the same users) that Linus himself merges the pull requests.

[gmaxwell]

I don't want to be a douche, but those words shouldn't be used too lightly. As an example, I personally wouldn't call Linus Torvalds an expert of his own kernel, because we see constantly people fixing bugs(that might have been made by the same users) that Linus himself merges the pull requests.

You're misunderstanding his statement here.  Peter's message is all about the limitations on what an expert can reasonably achieve in this domain at this time. If he instead defined an expert as someone without those limitations he could have alternatively said "there does not exist a Bitcoin expert" and been conveying the same message.

[Peter Todd]

I don't want to be a douche, but those words shouldn't be used too lightly. As an example, I personally wouldn't call Linus Torvalds an expert of his own kernel, because we see constantly people fixing bugs(that might have been made by the same users) that Linus himself merges the pull requests.

You're misunderstanding his statement here.  Peter's message is all about the limitations on what an expert can reasonably achieve in this domain at this time. If he instead defined an expert as someone without those limitations he could have alternatively said "there does not exist a Bitcoin expert" and been conveying the same message.

Yup.

There's probably a dozen people in the world who understand Bitcoin as well as I do. If there exist Bitcoin experts at all, those dozen people are your experts. Yet even that group still keeps on finding stuff about Bitcoin that they just didn't know before.

Looking at how the code is written I'll bet you if you asked Satoshi himself what he thought would happen, he would say the transaction would be rejected. Sure, it's a bug really, yet because Bitcoin relies on 100% consensus, or all hell breaks loose, we can't "fix" that behavior now.

[2112]

writing safety-critical flight avionics software

I think software for avionics has a lot to teach us. In particular, modified condition/decision coverage is important.

In this case a coverage analysis of these implementations run against their tests (maybe just the main blockchain) would show the nOut >= txTmp.vout.size() branch never taken.

What avionics software doesn't teach us as much about is handling adaptively hostile input (though if your code is correct for all inputs that hostile is just a subset— but hard to be confident that you're correct for all with cryptographic constructs in the loop), nor does it so much about implementation agreement in consensus systems. I suppose avionics would tell us we need to be testing the whole network as a single system because of the inescapable tight coupling, but sadly thats not realistic.

They could have had a test for it failing in that case... and seen that it rejected the block. The coverage would be good, it would be a sensible self-consistent behavior... but not consistent with the reference implementation.

Right now because the rules logic in the reference software doesn't have any test available which achieves anything close to modified condition/decision coverage (which, in also fairly hard to measure because the code is written in C++ and does a lot of dynamic allocation and boost) it means that even if you test an alternative well you can't compare it to Bitcoind unless you test.

But there are still tests which do test _a lot_ of it, and it seems they weren't used here:

It's worth noting here that Bluematt found this behavior about a year ago. The blocktester should be testing it.  I guess this indicates these alternative implementations have not been tested with the blocktester.  I suppose that in and of itself is a bit more concerning then even the specific failure.  On the other hand, the fact that they haven't been means we actually get an indication of their level of review which we wouldn't have gotten if the blocktester had already been run an exposed all the known-troublesome spots.

retep and gmaxwell wrote a very good summary of the most common misunderstanding about Bitcoin and its development process.

Bitcoin software isn't safety-critical, it is correctness-critical.

In this regard it is less like avionics and more like medical.

So let me use the medical analogies:

1) what bitcoin is not: it isn't a pacemaker software where a gedanken function would return {send-a-jolt,no-jolt}

2) what bitcoin is like: it is a medical test software where a gedanken function
would return {true,false,change-the-batteries}

3) you may think that you know how to "safely" map "change-the-batteries" to either "true" or "false", then consider those two functions:

3a) bool isHIVpositive(...) throw(change_batteries);

3b) bool isPregnant(...) throw(change_batteries);

Now lets switch out of the medical field and get back to Bitcoin. Imagine what would happen in May of this year if Bitcoin software had

bool ProcessBlock(...) throw(...,database_resource_exhaustion,...);

instead of the current design

bool ProcessBlock(...);

with almost every "catch()" clause plugged to "return false;".

Anyway, Bitcoin is neither avionics nor medical. Bitcoin is finacial application. In accounting when the books don't close the procedure isn't:

A) kill all accountants that said "false" and promote the one that said "true"

The SOP is:

B) keep re-auditing the books until the majority of the accountants agrees.

In the Bitcoin millieu somehow (A) became the SOP. There will be a lot of killed accountants until the (B) is adopted.

[Peter Todd]

Anyway, Bitcoin is neither avionics nor medical. Bitcoin is finacial application. In accounting when the books don't close the procedure isn't:

A) kill all accountants that said "false" and promote the one that said "true"

The SOP is:

B) keep re-auditing the books until the majority of the accountants agrees.

In the Bitcoin millieu somehow (A) became the SOP. There will be a lot of killed accountants until the (B) is adopted.

Given that the disagreements we are talking about are things like "Does Alice have a valid check signed by Bob entitling her to take $1000 of Bob's money?" any type of majority voting protocol is unacceptable - you're proposing a system that would allow a majority of miners to decide that they are going to steal your money with no recourse.

[Mike Hearn]

I'd like to have a developer FAQ on the website at some point, and a warning about reimplementing the protocol should be a part of it.

I have more confidence in Matt's work than any other reimplementation, but there's no way I'd trust large sums of money to bitcoinj full verification mode (at least not yet). We have certainly found chain splitting errors in it even quite recently, and we're not even really looking.

AFAIK coinbase runs on Bitcoin-Ruby. I believe they have had issues with being accidentally forked off before .... I am hoping at some point they investigate using bitcoinj SPV with JRuby and connect it to a local bitcoind. It should give them the APIs they need without the same level of split risk.

[2112]

Given that the disagreements we are talking about are things like "Does Alice have a valid check signed by Bob entitling her to take $1000 of Bob's money?" any type of majority voting protocol is unacceptable - you're proposing a system that would allow a majority of miners to decide that they are going to steal your money with no recourse.

I wouldn't expect any other answer from you.

It is difficult to get a man to understand something, when his salary depends upon his not understanding it!

Anyway, for those who really do think that Bitcoin is avioncs, I have a good quote:

* Quality must be built into the software, at a known level, rather than adding the quality after development.
* You cannot test quality into software

For those actually interested in learning about avionics software development process I have two good links:

http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20100028293_2010030759.pdf

http://www.nap.edu/openbook.php?record_id=2222&page=39

Obviously that example is unrealistic for Bitcoin purely for budgetary reasons, but please pay attention to using two competing teams from IBM in Houston,TX and from Rockwell in Downey,CA. You then should be able to understand what is going on here.

Edit: Actually retep had provided below a better, one paragraph, summary of why he isn't about safety but about control.

Yeah, nothing wrong with re-implementations if you hide them behind a trusted bitcoind node (IE one you run yourself) and/or use them for small sums of money. Just remember you'll occasionally suffer downtime when your implementation mistakenly thinks a block or transaction is invalid, but your trusted bitcoind node will protect you from false confirmations.

That kind of "safety" is typically called "job-safety".

[Peter Todd]

I'd like to have a developer FAQ on the website at some point, and a warning about reimplementing the protocol should be a part of it.

Good idea.

I have more confidence in Matt's work than any other reimplementation, but there's no way I'd trust large sums of money to bitcoinj full verification mode (at least not yet). We have certainly found chain splitting errors in it even quite recently, and we're not even really looking.

Yeah, nothing wrong with re-implementations if you hide them behind a trusted bitcoind node (IE one you run yourself) and/or use them for small sums of money. Just remember you'll occasionally suffer downtime when your implementation mistakenly thinks a block or transaction is invalid, but your trusted bitcoind node will protect you from false confirmations.

In addition I should point out the existence of bitcoinj and python-bitcoinlib and other libraries written by competent developers who understand the consensus problem is a good thing - Matt has done a tonne of good work on testing that greatly helped by the process of creating bitcoinj. The problem is people who don't understand the consensus problem and think they'll succeed in replacing the reference client, and there are a lot of developers in that boat, often developers who are otherwise talented and productive people.

AFAIK coinbase runs on Bitcoin-Ruby. I believe they have had issues with being accidentally forked off before .... I am hoping at some point they investigate using bitcoinj SPV with JRuby and connect it to a local bitcoind. It should give them the APIs they need without the same level of split risk.

Good idea.

SPV mode is good for this application because SPV nodes don't verify anything but the transactions you are interested in.

If bitcoinj sees a transaction that it thinks is invalid, can you use it in a way that lets other transactions from the same block be processed normally? IE the customer receiving a payment with a weird transaction would simply have to wait until someone fixes the problem, but other customers would be unaffected.

[gmaxwell]

Yeah, nothing wrong with re-implementations if you hide them behind a trusted bitcoind node (IE one you run yourself)

Careful, you just gave an example here where it matters.  The advice is "If you run them behind a bitcoin node and you don't care about the DOS attack of someone triggering you getting stuck" and even thats not enough depending on the "reimplementation" scope: A reimplementation which has errors in IsMine() could still get you ripped off even behind a bitcoin node, a reimplementation with a buffer overflow in script parsing could still get you ripped off etc.

[Peter Todd]

Anyway, for those who really do think that Bitcoin is avioncs, I have a good quote:

* Quality must be built into the software, at a known level, rather than adding the quality after development.
* You cannot test quality into software

Indeed - this is why I think the problem Bitcoin faces is harder than writing avionics software: we have no choice but to start with a buggy and poorly designed piece of software, the original Bitcoin client written by Satoshi, and maintain and improve it. The avionics analogy would be to take a multi-engine WWII-era bomber, fly and maintain it continuously 24/7 via in-flight refueling, and gradually upgrade it to be as good as a brand new Boeing 777 without ever landing once. Needless to say, starting from scratch would be much easier, but we don't have that option.

You say to know a lot about writing quality software, why don't you write a from-scratch alt-coin implementation done correctly with solid software engineering? I'm sure if you succeed it'll get adopted; in fact it's quite possible to one day collectively decide to replace Satoshi's implementation with yours in a hard-fork, just copy the UTXO set over and get miners to switch on the appointed flag day. Even if it doesn't get a lot of use it'll still be a worthwhile and groundbreaking exercise: no-one has ever written a from-scratch implementation of a crypto-coin; every alt-coin has simply copied the Satoshi codebase. The closest thing is P2Pool, but it's not as hard because if consensus fails in P2Pool all that happens is variance goes up if one side of the fork doesn't have much hashing power; no money is actually lost.

[Peter Todd]

Yeah, nothing wrong with re-implementations if you hide them behind a trusted bitcoind node (IE one you run yourself)

Careful, you just gave an example here where it matters.  The advice is "If you run them behind a bitcoin node and you don't care about the DOS attack of someone triggering you getting stuck" and even thats not enough depending on the "reimplementation" scope: A reimplementation which has errors in IsMine() could still get you ripped off even behind a bitcoin node, a reimplementation with a buffer overflow in script parsing could still get you ripped off etc.

Right, but the point is those problems aren't unique to Bitcoin-style consensus - what is unique to Bitcoin is the possibility that you'll get a transaction that isn't valid not because there is anything wrong with that transaction, but rather because the block it's in (or a previous block) has something that caused it to be rejected by the majority hashing power.

Those are all important risks, but they're all problems that happen in non-Bitcoin contexts too.

[TierNolan]

I'd like to have a developer FAQ on the website at some point, and a warning about reimplementing the protocol should be a part of it.

I have more confidence in Matt's work than any other reimplementation, but there's no way I'd trust large sums of money to bitcoinj full verification mode (at least not yet). We have certainly found chain splitting errors in it even quite recently, and we're not even really looking.

I think the key is to have code that checks for forks and warns the user/goes into safe mode.

A drop of hashing power on the main chain could be detected, but currently, you cannot detect significant hashing power on a fork.

I would argue that block headers should be forwarded as standard practice, as long as they extend a fork branch that forked within 120 blocks of current.  (In fact, I think even headers that fail to meet POW, but are close should be distributed, but that is another topic).

Full blocks that have never been part of the main chain could be held back to prevent spamming.

The 8.x fork could have been detected if that was the policy.  This assumes all clients agree on the SHA256 method and how to link headers to previous.

[2112]

Indeed - this is why I think the problem Bitcoin faces is harder than writing avionics software: we have no choice but to start with a buggy and poorly designed piece of software, the original Bitcoin client written by Satoshi, and maintain and improve it. The avionics analogy would be to take a multi-engine WWII-era bomber, fly and maintain it continuously 24/7 via in-flight refueling, and gradually upgrade it to be as good as a brand new Boeing 777 without ever landing once. Needless to say, starting from scratch would be much easier, but we don't have that option.

Not true. The core development team made a conscious and explicit decision to avoid considering other options.

However it was excellent analogy: who and why claims that only one plane needs to be flown with a single crew? Bitcoin is most clearly a fleet of planes.

You say to know a lot about writing quality software, why don't you write a from-scratch alt-coin implementation done correctly with solid software engineering?

I already wrote about "why?": I'm both legally and ethically obliged to enjoin myself from the participating "ex-parte" in development of either Bitcoin-compatible or Bitcoin-competitive products due to my involvement in the litigation related to the "non-open-source" or "for-pay-source" product with a name similar to "bitcoind Enterprise Edition". I'm also unwilling (for the same reasons) to open-source the code that was left into my care until it truely becomes an orphaned product and an exhibit in a closed litigation case.

The wheels of justice turn slowly, but grind exceedingly fine. Therefore I'm not "permanently enjoined".

I'm however not in any way gagged from openly commenting in public, especially if those comments are instrumental in keeping the privately-developed prior-art in the public domain, like the BIP 2112 comment in my signature.

Edit: speaking of planes, I'm going to gratuitously paste here my attempt at technical satire:

Bitcoin Airlines 2012 Annual Report:

1) The founder and CEO had split and we are still unable to locate him. Interim CEO is in charge until then.

2) The original paper plane has been covered in many layers of varnish and we have declared it fit for the regular service.

3) We've sold many passenger tickets for our Airline and the regular scheduled flights have started.

4) Unfortunately the cruise speed of our planes is barely above stall speed. The engines are weak and we cannot upgrade to the professional state-of-the-art engines that other airlines use. None of our mechanics know how to maintain them and we don't have money to hire some help.

5) Moreover the oxygen supply on our planes isn't working right and the passengers are passing out while onboard. Frequently the conscious passengers rob the passed-out passengers. Sometimes even the plane crew takes into temptation and plunders the unconscious passengers.

6) Fortunately the in-flight entertainment systems on our planes are the best. No-one else is even getting close to what we have to offer: neither on the land nor on the sea nor in the air.

7) Unfortunately almost all the fuel and engine thrust goes into powering the in-flight entertainment systems.

 

[jl2012]

I am not a software engineer. I can't even read C++ code. But IMHO OP_CHECKSIG is just too complicated while not flexible. For each sighash type there is different procedure. With more procedure, there is higher risk of bug.

That's why I propose the CHECKSIG 2.0 ( https://bitcointalk.org/index.php?topic=258931.msg2768432#msg2768432 ). The logic of CHECKSIG 2.0 is simple: "I will release my fund from inputs a, b, c to outputs d, e, f, given that inputs h, i, j are also involved". Preparing subset, hashing, and signature check are separated into 3 OP codes, and it does not depends on OP_CODESEPARATOR. I think it is simpler and more flexible than the current CHECKSIG, easier to standardize, and less likely to have bug.

I have rewritten the proposal and defined the detailed behaviors of the new OP codes. I am looking forward to your comments

[Peter Todd]

I am not a software engineer. I can't even read C++ code. But IMHO OP_CHECKSIG is just too complicated while not flexible. For each sighash type there is different procedure. With more procedure, there is higher risk of bug.

That's why I propose the CHECKSIG 2.0 ( https://bitcointalk.org/index.php?topic=258931.msg2768432#msg2768432 ). The logic of CHECKSIG 2.0 is simple: "I will release my fund from inputs a, b, c to outputs d, e, f, given that inputs h, i, j are also involved". Preparing subset, hashing, and signature check are separated into 3 OP codes, and it does not depends on OP_CODESEPARATOR. I think it is simpler and more flexible than the current CHECKSIG, easier to standardize, and less likely to have bug.

I have rewritten the proposal and defined the detailed behaviors of the new OP codes. I am looking forward to your comments

Try writing up a quick implementation, even of a cut-down version missing most of the features you want. You need to get a sense for how much complexity you are adding to get a better idea of what the trade-offs are.

Any new opcodes are extremely risky and we're going to need to think very carefully about what we're getting ourselves into. IMO it would be a good idea to implement a really simple one first, like OP_BLOCKHEIGHT, as a soft-fork using OP_NOP2 just to understand if our process for even doing that is sufficient. Heck, ignore OP_CHECKSIG for now, do that first as an exercise and write up a detailed plan - just like Gavin wrote for the P2SH BIP - to better understand what you are getting yourself into.

Remember what I said about upgrading flying airplanes...

[wtogami]

https://github.com/lian/bitcoin-ruby/commit/4b8598b84367f9c53e4e6a7a5459a124c1165c7e
I didn't test it myself, but seems to be referring to this thread.

[Peter Todd]

...and webbtc/coinbase is forked yet again on 0000000000000001e4241fd0b3469a713f41c5682605451c05d3033288fb2244

Probably tx df95ff9ac165abe7adb0091b5f1020c25203fd0c16c95b4c7fa6a4475428ef1f, although there's a bunch of other possibilities in there.

[Peter Todd]

Here's a good test if you think you have a hope of re-implementing Bitcoin exactly: a59012de71dafa1510fd57d339ff488d50da4808c9fd4c001d6de8874d8aa26d

Tell me how that transaction got mined in detail.