Bitcoin Forum

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

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.

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.

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.

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

I wouldn't expect any other answer from you.


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


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.
That kind of "safety" is typically called "job-safety".

Good idea.


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.


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.

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.

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.

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.

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.

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.

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:

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

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

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

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

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.

The HASH160 of 0xac91 is 0x827fe37ec405346ad4e995323cea83559537b89e so it is valid?

EDIT: The HASH160 of 0xac is 0x17be79cf51aa88feebb0a25e9d6a153ead585e59

So actually there is no CHECKSIG done here

You need to learn how P2SH works: BIP16 (https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki)

Yes, I was wrong.

For the second input, the serialized script is simply OP_CHECKSIG. So one can use ANY public key with a correct signature to redeem it, right? (normally, the public key is part of the serialized script)

For the first one, the serialized script is OP_CHECKSIG OP_NOT. So one can use any public key with a WRONG signature to redeem it.

I didn't check the validity of the signature but obviously they use the same signature and public key...... So there must be something wrong in my interpretation....

Compare the scriptSigs against the one in this transaction: 315ac7d4c26d69668129cc352851d9389b4a6868f1509c6c8b66bead11e2619f

I can't read C++, but it seems it works like this:

• For the first input, it is an invalid SIGHHASH_SINGLE signature, so the overall script is valid (with OP_NOT)

• For the second input, for the same reason as 315ac7d4c26d69668129cc352851d9389b4a6868f1509c6c8b66bead11e2619f, it is valid

Also, here's another fun puzzle: 61d47409a240a4b67ce75ec4dffa30e1863485f8fe64a6334410347692f9e60e

How is the byte string 000080 not true, yet any other non-zero bytestring does evaluate as true?

Ok, but then if the signature is valid on the second input, how can the exact same signature be valid for a totally different transaction spending normal inputs? (the second one I provided, 315ac7d4c26d69668129cc352851d9389b4a6868f1509c6c8b66bead11e2619f)

Didn't you explain it in the OP? If one uses SIGHASH_SINGLE without a corresponding output, a signature for 0000000000000000000000000000000000000000000000000000000000000001 is valid

BTW, there is a typo on the wiki:
https://en.bitcoin.it/wiki/OP_CHECKSIG#Procedure_for_Hashtype_SIGHASH_SINGLE

Yup, exactly - come to think of it the example would have been better done by spending three outputs, with two valid-yet-the-same-signature ones.


Thanks, fixed.

https://en.bitcoin.it/wiki/Script

so 000080 = 0?

Yup! Good job!

Is this behavior intentional (with legitimate use) or unintentional (aka. bug)?

Definitely a bug. If SignatureHash() had returned 0 in that case rather than 1 you could use it to steal everyone's coins apparently due to how ECC signatures work.

Somewhere I read Gavin said that there was a bug that allow everyone to spend everyone's coins (now fixed). Do you know which one he was referring to?

Hint: The OP_RETURN opcode used to return true, not false.

Why is that a problem?

I find your conversation with Gavin here: http://sourceforge.net/mailarchive/forum.php?thread_name=CANEZrP3qgo-VC5YHTSLOH5rGdv5PP4e2V6qECQVfvMgJXFbx-g@mail.gmail.com&forum_name=bitcoin-development

It seems to me that a script was always declared as true when it hit an OP_RETURN, and the rest of the script was ignored. So the fix was to make OP_RETURN returning false, and to execute the scriptSig and scriptPubKey separately. So even if the scriptSig is true, it still needs to run the scriptPubKey.

So what will happen in this case now? : scriptSig = OP_FALSE, scriptPubKey = OP_NOT. As the scriptSig is false, will it stop there as false, or the scriptPubKey will make the overall outcome as true?

Roughly correct, except that the scriptSig doesn't return a value, it returns a stack. Same with the scriptPubKey really, it's  just in that case we take the top value of that stack to determine if the script succeeded or not.


Right, since it returns a stack, not a value, the scriptPubKey is executed and the overall outcome is true.

Speaking of, OP_RETURN doesn't really return false, rather, it makes the script fail. It probably would have been better called OP_FAIL.