ANN: Announcing code availability of the bitsofproof supernode

[Sergio_Demian_Lerner]

The point of being vague is that us finding bugs on random code reviews isn't reliable or scalable. With your new codebase you're not solving a problem any of the current core developers have, so there isn't much incentive for us to go finding bugs for you. But if people were to use or mine upon a new implementation with bugs, that would definitely cause problems.

So what's important to demonstrate is that your code can be used without presenting a danger to the network, and that means really solid processes and testing to ensure the behavior matches exactly. If we can find one or two issues, there could well be more, so a rigorous testing and protocol compliance regime is the only way to build confidence.

I disagree with Mike and GMaxwell.

Remember when Bitcoin was v0.2 ?

The only thing that made it possible to reach 0.8 is by people sending as much information regarding bugs as possible.

Developers can never test everything, because resources are always scarce in every software development I've ever seen in the world.

With lots of bug reports, the developers can think of the best strategy for testing, concentrate in the common patterns, focus on certain modules, etc.

The quality of software will always rely on the development procedures implemented. But Grau is not part of an big organization with statistical information regarding 100 previous projects, nor he has the funding for one.

The best way to design the best software engineering procedures and the right testing plans for a software project with limited resources is to have the deepest knowledge about its current bugs.

[Jan]

I applaud Grau for doing all this work. I don't get the logic of withholding known bugs. If you don't want to help this is fine, but claiming that you found a bug, you just don't want to tell about it, is silly at best. We had a similar situation a year back or so where an alt-coin developer claimed to have found a bug in the satoshi-code, he just didn't want to tell Gavin (sorry can't find the reference).

Grau, maybe you should see if you can find a bug in BitcoinJ so you have something to trade with  
(Jan tries to dodge the flames)

[2112]

I don't get the logic of withholding known bugs.

This type of "logic" is normally called extortion. GMaxwell is a known extortionist, except that he calls it "tipping the incentives". Here is the link his post from the beginning of this year where he was openly asking for payment:

https://bitcointalk.org/index.php?topic=56675.msg677910#msg677910

When I joined this forum I was completely wrong calling the Bitcoin core development team "Bitcoin bunker". Now that I understand the situation better I know that there's no single bunker. There are numerous one-or-two-person cubbyholes that may occasionally form the aliances to shoot at the occupant of another cubbyhole. The situation conforms better to the distributed paradigm inherent in the design of Bitcoin.

[2112]

I'm pretty sure there is a bug, yes. If I'm wrong then I will of course apologise and go back to update my previous post.

The point of being vague is that us finding bugs on random code reviews isn't reliable or scalable. With your new codebase you're not solving a problem any of the current core developers have, so there isn't much incentive for us to go finding bugs for you. But if people were to use or mine upon a new implementation with bugs, that would definitely cause problems.

So what's important to demonstrate is that your code can be used without presenting a danger to the network, and that means really solid processes and testing to ensure the behavior matches exactly. If we can find one or two issues, there could well be more, so a rigorous testing and protocol compliance regime is the only way to build confidence.

I'm preserving this against further editing. If anyone has any remaining doubts about Mike's motivation please compare this post with his earlier post in the "multi-sig or scalability" thread:

https://bitcointalk.org/index.php?topic=94453.msg1046848#msg1046848

[gmaxwell]

I applaud Grau for doing all this work. I don't get the logic of withholding known bugs. If you don't want to help this is fine, but claiming that you found a bug, you just don't want to tell about it, is silly at best.

First, lets be completely clear about this before you start slandering me:  I _offered_ but also said I think it would be best to find it via testing, because we have no other way of knowing if the testing is sufficient. It is utterly essential that the complete rules of the system be faithfully executed. It is very hard to get this right. It's no insult to anyone if it's not quite right at first, but it is very essential that its well tested so that the test turn up every short coming.

Just as a reminder of what I said:

Unless you object, I'm contemplating keeping this missing rule to myself for now so that it can function as a test of the testing. E.g. if the test don't find it, they're incomplete.  Obviously I don't want to withhold information which could undermine the network, but absent better testing the software shouldn't be in production use anyways... and there are scarcely few good ways of testing the tests.   Does this sound reasonable to you?

A problem is that even with good testing it is hard to have confidence that the testing is good, and so the software remains untrustworthy even if its perfect. In fact, the more perfect the software is the more doubtful the tests become— They always pass!

Because of this, the fact that someone knows about an issue is a significant opportunity: If the tests find it then there is some actual evidence that the tests are sufficient. Not complete evidence, but some.  And right now the software is new and pre-production, so there is no harm created by some rules issues persisting for a bit, no risk to the Bitcoin network of someone exploiting the differences, etc. So finding something like this is an opportunity to build confidence in the software quality which would be destroyed by me just throwing out specifics about what is broken.

(And, of course, the tests are far from sufficient in the reference client— otherwise I'd just be saying "run the reference client's tests against your software". But the reference client's behavior is normative, so the bar is higher for alternatives: They have to emulate the rules related 'bugs' in the reference client: All (rules) bugs are features. This is one reason why Satoshi didn't support alternative clients).

I am ready to take the challenge.
How would you rate the current coverage of rules after your review (100% being complete)?
May I have a pointer if the omission you found is in script, message format, protocol, block-chaining (reorg), caching or any other more specific area?

I think it looked mostly complete, that is why I asked though— I wasn't sure if you believed it to be complete already or if you were still working on it. The issue I'm aware of is a part of script validation— though I'd encourage you to not over optimize on what I'm aware of, simply because there may be other useful things you find while testing.

[Mike Hearn]

I was pretty specific about the bug actually. It's a thread safety issue that can cause a split in the consensus, ie, it's in block chain verification. That narrows it down to a pretty specific region of code. It should be easy to spot.

Re: withholding specific bugs. I want to be convinced that this class of errors can be found by Grau in some systematic way. It's scary because finding thread safety bugs can be quite hard, though this one I suspect can be detected by FindBugs, which should make it easy.

If Grau doesn't find it after a few days or so and wants it reported, I'll do that.

I want to ram the point home that Greg is already making. Bitcoin is not like normal software. Fully verifying re-implementations are dangerous. If people use them and their behavior varies from Satoshis code at all, in even the tiniest detail, it can be used to split the consensus and in the worst case steal money from people. Satoshi was dead set against them for that reason and I'm pretty much with him on that.

Even refactorings of the Satoshi codebase scare me given that they have in the past temporarily introduced consensus-splitting bugs. Given that simply re-organizing the existing code is difficult and dangerous, you can imagine how I might feel about a full reimplementation!

Grau, maybe you should see if you can find a bug in BitcoinJ so you have something to trade with

There are undoubtably bugs in it, especially as the full verification support is new. That's why it comes with a prominent health warning on its home page and that's why I won't be recommending people rely on its fully-verifying mode any time soon. That's despite the fact that Matt has done a ton of work on testing, his tools are so good they actually found bugs in the Satoshi client after the ultraprune refactoring, so I have some confidence that those tests are thorough. They could easily be re-used here.

Obviously in SPV mode the damage it can cause is far more limited, so that's less of a concern.

One of my biggest worries about merging Matts work on full verification into bitcoinj was that somebody would use it for mining. If I heard anyone even think about that, I'd ask them to reconsider in the strongest possible way. I'm not super comfortable with even having it merged into the codebase, but since the code was written already, it seemed better to integrate it and be able to keep control over the documentation and how it's presented.

If you said "there is a bug in the SPV code of class X in region Y" then I would go and take a close look at that, and bulk up the testing around it to try and flush out the issue. And if I really couldn't find it no matter what I'd ask for help. But that would, I think correctly, shake peoples confidence in the code. If you found a bug in the full verification code, you would merely prove my point.

[grau]

If Grau doesn't find it after a few days or so and wants it reported, I'll do that.

I will think about the puzzle presented and will want it reported if I claim the test set is complete, or any earlier at your choice.

I think that Bitcoin is not the Satoshi code, that merely proved the concept, we all bought into.
 
You might be furious about this statement, but if that code would be suitable to all, then why on earth did you create BitcoinJ or jgarzik picocoin and pynode, to name a few with likely more credit in your eyes?

There are/will be other implementations that are closed source and you will have less handle on them than on mine. Given the increasing demand on capacity and speed miner are the first asking for and creating their own alternatives. Do you think few years down the road big merchants will connect their accounting systems to an executable that is a digital dogma?

You may warn people using alternative implementations, do your best to shake confidence in my abilities, but do not think that keeps you at the warm place you are used to for too long. That place will be either empty since this project dies or there will be lots of players who are not asking for your wisdom, while I still do.

[jgarzik]

I think that Bitcoin is not the Satoshi code, that merely proved the concept, we all bought into.

Not true.  We are stuck with the bugs found in early Satoshi code.  We must faithfully reproduce these bugs, to avoid splitting the network.  Examples include but are not limited to:

• Genesis block is not spendable
• CHECKMULTISIG requires an OP_0 to work around a bug
• Some transactions' hashes duplicate earlier transaction hashes, effectively making those earlier transactions unspendable.  Your code must similarly do the same.

You might be furious about this statement, but if that code would be suitable to all, then why on earth did you create BitcoinJ or jgarzik picocoin and pynode, to name a few with likely more credit in your eyes?

picocoin and pynode both carry "under construction, alpha quality, do not trust with money" warnings because they are incomplete and risk splitting the network because they do not follow the reference client 100% yet.

[grau]

Obviously I don't want to withhold information which could undermine the network, but absent better testing the software shouldn't be in production use anyways... and there are scarcely few good ways of testing the tests.   Does this sound reasonable to you?

Yes until the approach is constructive, that is to support creation of the product and not to bring the proof that it can't be done.

I am ready to take the challenge.
How would you rate the current coverage of rules after your review (100% being complete)?
May I have a pointer if the omission you found is in script, message format, protocol, block-chaining (reorg), caching or any other more specific area?

I think it looked mostly complete, that is why I asked though— I wasn't sure if you believed it to be complete already or if you were still working on it. The issue I'm aware of is a part of script validation— though I'd encourage you to not over optimize on what I'm aware of, simply because there may be other useful things you find while testing.

Thanks, the brief evaluation made me feel better. I will walk away with this puzzle too for now.

[Mike Hearn]

You might be furious about this statement, but if that code would be suitable to all, then why on earth did you create BitcoinJ or jgarzik picocoin and pynode, to name a few with likely more credit in your eyes?

I'm not furious about it I've often wondered that myself!

I created bitcoinj because I wanted to use Bitcoin on my Android smart phone. This led to two problems:

1) Integrating with an Android GUI requires you to use Java. Of course, you can try to use JNI. It is complex and the binding code is a lot of work. Especially when you take into account the need for many complex callbacks. Still, it could have been done and I considered that for a while.

2) Satoshis code did not support SPV mode (it still doesn't). I had a partial patch from him but it was unfinished and clearly not going to work on something as constrained as a phone, partly because his code assumes it can load all block headers into RAM and that assumption is pretty prevalent through the code. You can't do that on Android, there isn't enough space. So it was clear that Satoshis code would need major work to do what I wanted.

There was a third concern I had, which is that back then the Satoshi client didn't really have any unit tests and the changes needed were pretty deep. My understanding of the code was much worse than today and I was afraid of breaking things. So a fresh implementation meant there was no risk of me being the cause of anyone losing money.

At the time, I thought it would be about as much work to do a new SPV implementation than adapt Satoshis code, because you don't have to validate all the rules, just manage the block chain. And as I thought it was about the same amount of work, I figured I could make an API for writing Bitcoin apps whilst I was at it.

In the end, I found I was mistaken - it was a lot more work than I expected

So, knowing what I know now, would I have done things differently? Well, maybe. I'm not sure. On one hand, I massively underestimated the amount of work required. On the other hand, I've also seen several times how easy it is to break Satoshis code in subtle ways. So my enthusiasm for writing a new codebase would have been less, but my fear of changing the existing one would have been more. Perhaps ignorance is bliss

Given the increasing demand on capacity and speed miner are the first asking for and creating their own alternatives.

Pieter has been able to get the satoshi client verifying the chain at thousands of transactions per second, which is excellent and I doubt we'll need any more performance than that for the forseeable future (PayPal processes a grand total of 40 transactions per second).

So I'm not sure I agree with you that this executable will be "digital dogma" - I think it'll still be in wide use as it'll have a long track record and good performance.

By the way, how do I switch your code to sync the production chain? I cloned it from git and ran the demo, but I can't see any command line switch or obvious XML config tweak to make it use the main network. I'm sure I'm missing something obvious.

[grau]

I think that Bitcoin is not the Satoshi code, that merely proved the concept, we all bought into.

Not true.  We are stuck with the bugs found in early Satoshi code.  We must faithfully reproduce these bugs, to avoid splitting the network.  Examples include but are not limited to:

• Genesis block is not spendable
• CHECKMULTISIG requires an OP_0 to work around a bug
• Some transactions' hashes duplicate earlier transaction hashes, effectively making those earlier transactions unspendable.  Your code must similarly do the same.

I reproduced the bugs you listed as they are widely known "features" of the protocol. Point me to any further collection of "features" and I follow them. I read and tried to reason the Satoshi code and some of yours, while might have missed to identify features that need to be replicated. That code base evolves too, therefore boundaries have to be clear where the definition ends since other implementations will not follow that for ever.

picocoin and pynode both carry "under construction, alpha quality, do not trust with money" warnings because they are incomplete and risk splitting the network because they do not follow the reference client 100% yet.

If that makes a difference I make sure I say the same

[grau]

So, knowing what I know now, would I have done things differently? Well, maybe. I'm not sure. On one hand, I massively underestimated the amount of work required. On the other hand, I've also seen several times how easy it is to break Satoshis code in subtle ways. So my enthusiasm for writing a new codebase would have been less, but my fear of changing the existing one would have been more. Perhaps ignorance is bliss

I do feel what you say. My journey started with the hunger for details and similar ignorance of the size of the problem. My belief however remained that alternative implementations strengthen not weaken the system as they are the real test cases of each other.

Pieter has been able to get the satoshi client verifying the chain at thousands of transactions per second, which is excellent and I doubt we'll need any more performance than that for the forseeable future (PayPal processes a grand total of 40 transactions per second).

So I'm not sure I agree with you that this executable will be "digital dogma" - I think it'll still be in wide use as it'll have a long track record and good performance.

Yes, it does work well and it would be rather surprising if all of the core teams effort would not have stellar results in areas they focus. The point is that they won't solve problems that are not sexy or global enough. 

By the way, how do I switch your code to sync the production chain? I cloned it from git and ran the demo, but I can't see any command line switch or obvious XML config tweak to make it use the main network. I'm sure I'm missing something obvious.

There are sets of configurations e.g. server, lserver, audit, demo

java -jar target/supernode-0.6-SNAPSHOT.jar server

starts the relational model, but you have to configure the datasource you use (it is defaulted to derby) Make sure you add derby a lot of buffers since default configuration of the distribution is a joke.

java -jar target/supernode-0.6-SNAPSHOT.jar lserver

starts LevelDB configuration. I also use -Xmx4g and -server flags to java but that should depend on your conf.

Please report bugs you will surely find in issues at github.

[Jan]

If you said "there is a bug in the SPV code of class X in region Y" then I would go and take a close look at that, and bulk up the testing around it to try and flush out the issue. And if I really couldn't find it no matter what I'd ask for help. But that would, I think correctly, shake peoples confidence in the code. If you found a bug in the full verification code, you would merely prove my point.

X=Wallet Y=reorganize()

Details and fix sugestion  posted here: http://code.google.com/p/bitcoinj/issues/detail?id=257

Sorry couldn't help it 

[grau]

I should have also said:
configurations are under: src/main/resources/context and src/main/resources/etc file names correspond to the ones I listed in the previous mail. Configurations are packaged into the jar, so you have to do
mvn package
after modifying, to use them.

[Mike Hearn]

Whilst I was playing around to see if the bug I saw was real (it is), I noticed a few others too, all chain splitting unfortunately.

Let us know when you want to know what they are. Otherwise as you improve test coverage I'll sync to git master every so often and see if they got fixed.

[Sergio_Demian_Lerner]

We must faithfully reproduce these bugs, to avoid splitting the network.  Examples include but are not limited to:

• Genesis block is not spendable
• CHECKMULTISIG requires an OP_0 to work around a bug
• Some transactions' hashes duplicate earlier transaction hashes, effectively making those earlier transactions unspendable.  Your code must similarly do the same.

Could you create a list of issues that you know and upload it to the https://en.bitcoin.it wiki ?
Or if you post the list here, I can edit the wiki.

It's very important that this information is made public.

[grau]

It's very important that this information is made public.

Yes. The current practice of requiring undefined but unlimited compliance is a break on innovation.
Those posess the details would serve the community by documenting them.

[Mike Hearn]

I'm sorry guys, but I feel like we're not getting through to you.

There is no canonical list of quirks. We don't know them all and discover more all the time, so trying to build a wiki page with them in would be misleading. That's why we're saying Bitcoin is not like normal software and re-implementing it is dangerous - the list of things you might get wrong is both long and unknown.

It's not a "practice" to require unlimited compliance. It's inherent in the nature of how Bitcoin works. Any deviation from the standard behaviour at all can lead to chaos if the deviant implementation gets enough users. This includes behaviour that is implicit in libraries like OpenSSL or the database code.

The best way to find out what quirks or bugs have to be re-implemented is really, really thorough testing practices. So far, nobody has been able to achieve this successfully - even the best tested re-implementations have on inspection been found to contain consensus-splitting bugs. The more often this happens the more I come to think re-implementing Bitcoin successfully isn't possible and we will never have a reference specification that is usable.

[grau]

The practice I referred to and do not comprehend is: not attempting to capture the compliance requirements. This is as if unknown and untold implementation details would serve security. This is not a mainstream thinking in cryptography.

I do understand your concern but think it is short sighted to assume this will go mainstream without defining its nature.

A practical suggestion: test cases you created for the Satoshi client check for features you ensure to pass at each release. I think it would be beneficial to state what exactly they check for in a wiki.

[Mike Hearn]

Yes, like I said, Bitcoin is not like normal software. Of course in a normal software environment the protocol would be defined by some specification documents, test suites would be produced to check compliance, etc.

But then in normal software environments the cost of failure is really low. OK, you wrote a web browser that doesn't correctly implement the JavaScript specs. Some web pages fail to display properly. No big deal, just fix the bugs and try again. Users temporarily switch to another browser, life carries on.

With Bitcoin it's, OK, you wrote a program that follows the specs, but the spec was incomplete in some minor detail. It got some users. Now you have created a security vulnerability that can be used to undermine everyones assumptions about double-spending hardness and potentially defraud people out of millions of dollars. The severity of failure is so much higher. And worse it can affect people who didn't ever even use your software. Maybe only avionics software comes close to this.

Chain-splitting bugs are really an entirely new class of security vulnerability that existing software doesn't have to think about.

So with Bitcoin, and especially bitsofproof supernode, we're in uncharted waters. There have been several re-implementations, but none of the authors ever supported mining before. That is one of the things you said you'd work on next, hence the attention this thread is getting. For the first time ever the prospect of a non-Satoshi implementation being used by real miners or real merchants is coming up.

The question we have to answer is - is it possible to achieve the level of accuracy needed to do a safe re-implementation? We used to think the answer was yes, just document the protocol, write some decent unit tests and you're done, like any other program. My opinion is changing on this quite fast, because we keep finding bugs that could be used by an attacker to split the chain but which weren't found via testing or automated analysis.

So far, I think Matts work on testing for the bitcoinj full mode is the most thorough yet - he wrote a tool that compares block acceptance step by step against two different nodes and runs through it a set of carefully crafted test blocks. It's impressive and was a ton of work. Last night I ran FindBugs on the code and discovered at least two different chain-splitting bugs that weren't found by the tests, one of which is also present in bitsofproof. It took me five minutes!