Topic: Is there any full node implementation 100% compatible with the core client? - page 2. (Read 4539 times)

If you need to make use of some sort of custom node (server backend for example) I would recommend running a copy of bitcoind in wallet only mode. Then have your custom node connect only to the bitcoind under your direct control.   With bitcoind acting like a bitcoin firewall it will prevent entire categories of consensus split isolation attacks.  Just keep in mind it isn't a magic bullet.   If your consensus rules are bad enough your custom node may drop blocks passed by the bitcoind and thus "stall out" but that is preferable to being fed a false history by a malicious node.

Great talk. Too bad, that Bitcoin messages use length encoding, even in scripts.

I think its fair to say its fundamentally hard (in a computer science formal sense) to make two implementations that are consensus identical in an adversarial setting.

Consensus is a new and tougher version of the host security challenges.  You dont even have to make an implementation buffer overflow in a steerable way, nor perform something it shouldnt have; just most divergences become sufficient to adversarially steer to the advantage of whoever finds the divergence first and is inclined to exploit it.

About the former simpler problem, Meredith Patterson gave an interesting research summary presentation on the limits of (computer) language security: https://archive.org/details/The_Science_of_Insecurity_

I encourage people, even those who think they know a decent amount about host security, to have a listen.  Its quite interesting.  You can see that any network protocol with messages interpreted by software forms a computer language, as well as bitcoin incorporating explicit languages like script as part of its operation.

Adam

Right. So maybe we can try to think about how to break bitcoin up into modular parts (eg. secp256k1, vm/script, encoding/decoding, merkle tree, create/verify block header, add block to tree, etc.). Then we can start with verifying the parts, and with verified parts you are much more likely to have a valid whole. Maybe at that point we can all band together and build an asic for it, then all run the asic instead of building software on the myriad OS's (which practically precludes the possibility of formal verification, as you've noted). Then maybe we'll have a safe bitcoin?! It's extreme but I'll entertain it.

You are right. The real foundation of Bitcoin is the shared desire to have it, that will overcome any technical obstacles.

https://github.com/conformal/btcd

I don't know if it works and is done yet, but here you go... hahaha.


In truth though Bitcoin is an agreement between humans and as such it can never die. Hash algorithms and signing algorithms can be switched and bugs can be fixed. Consensus splits can be resolved - ALL of those have already happened before.
(Original payment method was supposed to be IP based, 2010 had a script bug letting everyone spend anything and as noted 2013 had a major fork event)

Gavin's scalability roadmap breaks the Bitcoin protocol, but because people support it and because they believe it is aligned with the concept of "Bitcoin" it will happen eventually.

However the system remains stable because you need 90+% majority for such things to work and only simple changes aligned with the human vision can attain that. It's extremely interesting and beautiful in a way.

You guys should read Asimovs Foundation book series.

I'd like to invite you to point out any place where I argued anything about probability, except to rebut your reliance on that argument. Bitcoin is an experimental system, and in some regards it is pushing the envelope about the kinds of systems we know how to engineer and is doing so under considerable resource restrictions.

We can't just cherry pick what to apply our arguments to.  The entire argument here is entirely based around the probability that Bitcoin Core is less likely to fork than alternatives, because the exact same logic you describe applies to multiple versions of Bitcoin Core on different compilers, OSes, hardware, etc, as much as it does to alternatives.  Of course, in an adversarial environment, you have bad faith actors looking to exploit those probabilities.  You're asserting that there is a much lower probability that they will be able to do so between two versions of Bitcoin Core.  That's fair, but it doesn't make any sense to use probabilities to assert that and then turn around and say they don't matter when applied to a different implementation.

Either probabilities don't matter and the entire argument about whether Bitcoin Core is more or less likely (probability) to fork or not is moot, or they really do matter.  I claim they absolutely do matter because Bitcoin Core isn't immune to forks either and there is clearly some chance involved that forks will occur between any two pieces of Bitcoin software.


The claim isn't that a prefab test suite is entirely sufficient, it's that it lowers the probability of a fork occurring.  When is the probability low enough that it's generally safe to transact?  If you claim there isn't one, then Bitcoin, as a whole, is unsafe to transact on because the entirety of consensus is probability based to begin with.

Probabilities are not an effective model to reason about bugs in an adversarial environment. (Even in conventional reliability engineering-- without invoking an adversary-- you must first separate systematic failure from random failure in order to reason about failure distributions.)

"If you have a website with a billion pixels and due to a bug clicking one gives the reader one of your bitcoins, and you have one visitor an hour and a normal visitor clicks on 100 pixels, how long until you've lost 100 bitcoins?"  .... This doesn't make sense, and thinking about consensus bugs in this manner doesn't make sense. Existing consensus bugs we've seen triggered against implementation were 10^-100 scale events if your model is random monkies pounding on keyboards to produce transactions.

Virtually all the errors we care about are not random failures, and to the extent that there is an element of randomness an attacker can behave adaptively to bring out the otherwise 'rare' behavior that is harmful to your interests.

Philosophically there should be, but in terms of benefit to the world the value is quite possibly negative. A non-executable or not widely used specification is a dead letter. The behavior of the participants defines the system.  You can point blame all day this way that when some reading of the specification disagrees with some other reading; but its little comfort when all the funds are gone.  As a pedagogical artifact a good specification may be highly useful; but it can also cause harm by feeding deep misunderstandings like having software which you believe-does (instead of actually-does) what you believe the specification says (rather than what everyone else actually-does, regardless of what they believe the specification says) is an acceptable situation to be in. "But I followed the spec!" "Too bad, all your coins have been double spent away because you ended up on a different chain from the other participants."  Compared to other efforts to improve system integrity I think specification work beyond what exists now has fairly low returns.  (Doubly so because existing alternative implementers have frequently made mistakes in parts of the system that are clearly specified and have tests in the normal tests suites.).   In Bitcoin the behavior of the system is all there is. You have no other recourse, no higher authority.   Being surprised or unhappy with at the Bitcoin network for disagreeing with a ream of paper is, in some ways, like being mad at the universe for not being completely defined by Einsteins' description of general relativity.  Like the universe, the Bitcoin network doesn't give a darn about political gamesmanship. It does what it does, not what you think it should do. To the extent that people want to work on specification work, especially if it was specification work that clearly enough defined to permit formal reasoning, it's work I would support-- in spite of my reservations about potential net-negative value from it.

I was going to make a post similar in content to davec's, but he already made my points.

One of the reasons why I didn't get involved with bitcoin at the beginning was because it was a complex distributed system that had a code base but no real specification.  It was genius and luck that bitcoin took off and still works.  There should be a formal specification, but the problem will be keeping it in sync with the code base.  This will be politically impossible so long as there is only a single code base.  So for the long term good of bitcoin it is imperative that there be different code bases.

There will be forks. There are airline crashes.  People still fly.  In the aerospace safety world, the phrase is, "All progress comes as the result of crashes."

I personally think the question is wrong here.  Not even Bitcoin Core is technically 100% compatible with the same version of itself, so asking that question is starting with a false premise.  As previously mentioned, there is a lot of work to be done in the formal verification space, but even then, due to hardware differences, compiler optimization differences, OS differences, and a myriad of other factors, I personally think it's unlikely there will ever be absolute 100% certainty.  The question then becomes, does there really have to be?

To me, what it really comes down to is probabilities.  The popular assumption is that Bitcoin Core has an extremely low probability that it will fork against itself.  So, let's go with that premise and say that the probability of Bitcoin Core forking against itself is something like 1 in a 100 trillion (1e14).

When an alternative implementation passes all consensus tests and covers all known corner cases, then it too has a relatively low probability of forking.  If that is not true, then the consensus tests need to be improved.  For the sake of argument, let's assume that such an alternative is 3 orders of magnitude, or 1000x, more likely to fork.  Well, then the forking probability relative to the Bitcoin Core forking probability previously stated would then be 1 in 100 billion (1e11).

Moreover, if/when a fork does happen, it identifies a case that the consensus tests missed and can be used to improve the consensus tests which in turn further reduces the probability for all nodes involved (including Bitcoin Core) that validate against the consensus tests.

It is estimated that in any given year the odds that you will die from an impact of an asteroid or comet are between 1 in 3,000 and 1 in 250,000.  However, that probability is still low enough that I bet you don't live in a steel box and refuse to go outside just in case.

They're sort of scattered in various places, for example: http://sourceforge.net/p/bitcoin/mailman/message/29699385/

One question with formal verification is what are you formally verifying?  If the question is the most important question in consensus "is this function equivalent to that function for all inputs" there is one very easy to have a strong guarantee that the answer is true: make them be exactly the same function.  Formally proving two functions written in different languages compute the same thing is much harder, and likely not practically possible if the languages are very different or the algorithms used internally substantially different.

To formally verify other properties we first need to extract the part that needs to be verified into it's smallest self contained realization. You can look at whats been done with SEL4 to see whats currently possible (and how much work it takes for a rather small program) at the state of the art.

In Bitcoin core we're working on the isolation which is an important first step on both with the "use the exact same code for the consensus critical parts" approach as well as the "formally show some code achieves certain properties". I suspect that on the latter we won't make much progress in the near term outside of some parts in the underling cryptographic code unless some researchers pick it up as an area of study, but we should hopefully be well positioned to take advantage of formal analysis tools as that space matures.

Is there somewhere I can read about the kinds of corner cases that were discovered and how they were dealt with?

Also, what would it take to produce a formally verifiable implementation of bitcoin? Is such a thing even possible? Can we expect a PhD thesis to deliver the matter in the next decade?

@grau & @justus, no offense but your debate is quite off-topic. If you must discuss the pros/cons of alternate implementations on altcoins, could you create your own thread?

I ran Matt's test harness on bitcoin core 0.9.3 and an assertion was raised. Then I tried on my code and realized that the test harness relies on a specific message order or it deadlocks. After that I started debugging the test harness and got a headache. Maybe it is time to surrender.

The consenus of Bitcoin user created a new type of asset that is not limited to the features supported by the original code.

If people decide to move their asset to an other chain, they do it because they think it offers them something higher value.

They might be right or wrong.
- Assuming they are right, then side chains adds value to the ecosystem.
- Assuming they are wrong, then supply of Bitcoin shrinks and those sticked with it enjoy appretiation.

Of course.

You don't call your competitors "teammates", however.

Software that tries to compete with Bitcoin is not an alternate implementation of Bitcoin - it is a competitor to Bitcoin.

It is called competition. It is what makes things strong.

Trying to make value flow out of the Bitcoin blockchain is the same as trying to kill Bitcoin.

I wouldn't call software whose purpose in life was to extract value from the blockchain an "alternate implementation" - I'd call it an attack.

To be fair, it is easier to keep an implementation consensus compatible with its prior versions, than to achive consensus compatibility with an unrelated code base.

I think that the best option for alternate implementations is to define a side chain that is attractive for reasons other than their token, so value migrates to them.