Topic: Managing substantial changes to Bitcoin - a QA network. (Read 4146 times)

Yes, this is what I want. A way for the entire network to collectively trigger such a changeover without the demand that everyone update their client, and definitely without the network being down, or having to rollback legitimate transactions. And then extensive testing of this process on a test chain in all the scenarios we expect to have to use a given changeover method.

We should strive for this to be the end goal of any plan we make. In some cases it will simply not be possible to accomplish this goal, but we should call out those scenarios and determine what the best we can do is.

Rolling back transactions has approximately a 99.9% chance of killing bitcoin. It being down for any extended period of time is less likely to kill it, but still very likely depending on the length of the outage and the effects. We're running a financial network here. If anything like this happens and people lose money because of it, we are done. And people not being able to accept transactions for any length of time will be considered "losing money".

Yes, that's what I initially thought too. But maybe you should read more about the scriptSig. It seems kind of like all I need to do is craft a scriptPubKey that eventually validates to one of my addresses. It isn't as limited as just changing an address - I can do almost whatever I want as long as it hashes to the same thing. It doesn't have to go to a valid Bitcoin address, it just needs to eventually return true with some input that gets prepended to it in a new tx. That's a lot looser of a restriction. The scriptPubKey can be of arbitrary length - more than enough for 256 bits that can be added to the tx.

If I have control enough that I can make anything have whatever hash I want, I can change outputs to go wherever I want, because even if I can't do anything more interesting than make the scriptSig always return true (next person to write a tx with this as the input gets it) then I can also write a completely new tx later on in the blockchain that consumes that output and actually sends to an address that I own. Since we're already rewriting the blockchain, I win - I can now rewrite arbitrary tx to go wherever I want, and rewrite the blockchain so that those tx are buried deep.

Like I said, it'd be kind of obvious which tx were the invalid ones in this case since they clearly wouldn't use standard scriptSigs, but that isn't necessarily going to be an iron-clad indicator forever.

It would still be a good idea to have an implementation spec in place for a hash algorithm switchover.  Ideally you want to be running a hash system that has no known vulnerabilities, and the ability to seamlessly and very quickly switch from one hash system to another.  It doesn't take a lot of work to completely kill people's trust in a currency, especially one that relies of crypto voodoo to work.  Much like the Fukushima disaster, all you have to do is yell loud enough that X uses Y, and Y is (whatever), therefore X is (whatever) in order for most people to believe it.  The ability to go "oh shit", notify everyone, and collectively vote to switch would be a very powerful way to mitigate that effect.

Code the protocol such that:
If 26 of the last 40 blocks have the 'use new hash' toggled to yes, then every to-spec miner and the official client will ignore all blocks not using the new hash from block 26 onwards.  Clients can read both block types, and transact in both block types, because this was pushed potentially years before it was needed.  And once there is a discovered vulnerability, the miners can decide for themselves as a group if they should transition to the newer, harder hash system.

if you have 256 bits you can do anything you want with. If you can identify even 3-4 bytes in a tx block that you can twiddle without making it invalid, or useless, then I'll be impressed, from my reading of the spec that should not be possible.

It appears that you are comparing the number of possible states in say 1k of data, to the number of states in a hash. For unbounded data, there are clearly many hash collisions in a 1k block, but we are not talking about all possible 1k data blocks, only about those which are also valid tx.

Most of the data in the tx is not twittleable, because it is ether static, or derived from the rest of the data, none of the hashes or headers are twiddleable, but twiddleing anything else requires also twiddling the hashes. The only data you could twiddle is the only data you can't get anything out of randomizing, the recipient address.

Are you sure? I mean, hashes are just really, really complex checksums, right? If there are 256 bits in the hash it seems like you should be able to change 256 bits in any message and get any hash you want, if you knew the right places to twiddle bits, or could add extra bits somewhere.

It is at least theoretically possible to do this, since md5 had something similar...

okay, now you are betting on the square of two astronomically unlikely hash collisions. First that there even exists a valid hash collision for the signed hash, and then that that the EXACT SAME hash collision applies to the tx as a while. Even if you can generate reverse hashes in 0 time, you can't pull hash collisions out of thin air.

I don't need to generate a new signature. My modified transaction hashes to the same value as the one you signed. I don't need your key. The vulnerability lies in the hash algorithm you use to generate the signature; if I can come up with a transaction that is still "signed" by you, but sends the btc somewhere else, I win.

In this case, though, I would think we'd be able to tell the difference between a legit and a false transaction. The legit tx is the one that doesn't have padding garbage in it. But that isn't necessarily the only way this could happen.

The scriptSig contains a pub-key signature of the transaction, in order to generate a valid tx, you MUST be able to generate a valid pub-key signature for a hash of the transaction, which means you have to break pub-key to do that for a wallet you don't control.

breaking pub-key breaks EVERYTHING about bitcoin, there is no contingency plan. Unless somebody comes up with a pub-key system that works on a different mathematical basis so as not to be broken at the same time, the game is over. Not being a candidate for the Fields Medal, I'm not in a position to contribute to that contingency plan.

What if the break is such that I can simply take an existing tx, change it to go to my address instead, then pad it with carefully selected garbage in spots that bitcoin doesn't care about (in the scriptSig, maybe) and write that tx into a block? If I can make arbitrary data hash to a given value, I don't have to generate new tx - I can redirect old ones.

I would like to see an argument for breaking tx without breaking pub-key. While you could certainly create other possible source data for a tx hash if you broke the hash algo you would still need to accomplish four things:

1) find such a data block that was in tx format
2) generate the pubkey pair that matches the valid tx that matches your hash
3) make sure that the scriptSig was valid for a currently non-empty wallet
4) make sure that your randomly generated tx agrees with the contents of the embedded scriptSig

I see that one might be able to, in theory, to steal some arbitrary amount of bitcoins from some arbitrary wallet for some astronomically small number of hashes. I'm willing to wager that, even with a completely reversible hash function the search space for such a hash is larger than the entire search space for the entire block chain for the next century.

You are making quite a lot of assumptions about what is and is not possible. The scenario you describe is one scenario - the one where only block hashes are compromised and not tx hashes. If we can't prove conclusively that a certain disaster scenario is impossible, we should assume that it is, and write a plan for it. Even if that plan consists of "throw up our hands and watch as billions of dollars of currency goes up in smoke, because we can't possibly recover, because of x y z." for example, as you said, a breakthrough in factoring primes would be a hard break, but only because we don't have another algorithm that doesn't depend on that. But maybe we do, and if so, we should find and agree on the next algo now, so we are prepared in that case.

One benefit of this planning would be the ability to simply code support for all of the contingency algorithms into bitcoin preemptively; this would allow us to test that such a switch would go smoothly.

I'm liking responses so far. Do we need a separate thread for this? My goal is to develop contingency plans via feedback from the community (I don't pretend to understand crypto perfectly, for example, so I don't know if certain attacks really ARE impossible) and then we can test each plan in a different environment. Once we're done we should have a document that clearly describes the actions we will take in each case, so there are no surprises about things like who is making the decisions or what the procedure will be.

We can also test preventative security measures there, like the "scaffold" hash you describe, or perhaps aware miners can always add a different type of hash for the block? If we have a heterogeneous set of hashes used in blocks in addition to the canonical SHA2 we reduce our attack exposure; it will be easy for clients to verify the hashes they understand and ignore the ones they don't, but we'll need to make sure they actually enhance security instead of just being warm fuzzies. For example if all hashes are optional but the sha2, what keeps someone from rewriting the block chain and just not putting extras in, or rehashing their attack contents?

I can't see how that would be necessary.

Even if you cracked the hash, and could win/rewrite every block, your blocks still need to be validatable, so go a few blocks deep and you need to completely rewrite the rest of the chain, with validating transactions, which means using your own BTC to pad the block to create a hash match, which seems like it would become just as computationally intensive as mining, since you can't generate pub-key sigs to spec.

This seems only as troubling as the 51% processing vulnerability, which is not all that scary.

How about we build some memory/watchdog into to client so that it will vote to favor continuity over a highly divergent block chain?

The security of the blockchain will be lowered if the hash is cracked, but the blockchain will not become invalid, or trivially editable, because of the pubkey data being hashed.

If hash-function failure is the concern all we have to do is allow some subset, of crypto-unrelated alternate hashes, and possibly even require one to be used every mod64 blocks, as a scaffold in the case that the current hash gets abandoned. This should be rolled out at least 6mo before it is used - probably tied to a block number rollover, and will need to be done soon before people start building embedded devices that use bitcoin. The trick is picking the hashes, and building the GPU code to crunch them.

Now if the Pub-key part is broken on a fundamental level, then we are SOL, are there even any non-large-prime based pub-key systems?

Only a handful of trusted people need to come to an agreement about the block chain contents unless there is any significant disagreement about it. If there is disagreement, it might take a few days to reach consensus. Speed doesn't seem that critical to me, since it will still take some time for everyone to upgrade once an agreement is reached.


I can't think of any fairer way.


I was thinking just one hash for the entire thing. Maybe the "previous block" field in the version genesis block will be a hash of all the hashes, or the root of a Merkle tree.


I'd like transactions to support specifying the hash type used. That would allow people to choose their own security. Slower algorithms might require higher fees.


Bitcoin will already detect the case where new block/tx versions have the majority of the network. It will say:
RPC is also shut off, so all Bitcoin sites will stop working.

So how long do you expect this discussion to take? Who is permitted to participate? How do we get the word out that there even is a discussion happening? We need this to happen within hours of a break.

So we will roll back the entire network for possibly a week? Reversing legitimate transactions sounds terrible. I would guess that the number of honest people who would re-send payment for something that they got a week ago is half at best. If someone bought something with bitcoins, and then later their money arrived back in their account, I have a hard time believing that they would research why this happened and correct the error.

I don't know how we'd have a heuristic for separating bad from good transactions, though. But that can shake out of more discussion of what threats exist.


This is one of the ways I was thinking we could handle it. So we have a block attached to the end of the v1 blockchain, a "version upgrade genesis block", that essentially re-confirms the previous blockchain in our new secure hash algo and defines the hash parameters of the new chain? A record of the entire chain that came before, saying "block 1's SHA3 hash is X, block 2...".

It depends, right? In some cases we might just know that it is broken but not how to do it ourselves. In others it's a public exploit. It might still require a lot of power to break, just a fraction of what it was, or it could be trivial, or it could just be a tiny crack in the dam. We should probably work out all the possible failure scenarios and classify them, and determine how to defend against each.


The reason I asked that sequence of questions is, it is theoretically possible for us to develop recovery plans now, and implement support for such in the client, so that if the client encounters an upgrade block, it can just reconfigure itself and go on. If we did this, we could switch bitcoin onto new crypto preventatively - if SHA2 continues to degrade and SHA3 eventually proves itself worthy, we can upgrade before the disaster.

If we do this early enough, code can make it into 51%+ of the clients on the network, and when the network decides to switch over, most clients can come with it without an update - or at least disable themselves. But preloading would be preferred.

I don't have a plan in my head right now. I don't even know all the scenarios. But I want to start talking about it now; bitcoin is growing exponentially right now, and the longer we wait, the larger the risk is.

We'll have a discussion here and on IRC. Whoever controls bitcoin.org makes the final decision about what is listed there, and if other people disagree, they will advocate different versions on their sites.


We'll come to some agreement about it at the time. I'd advocate removing all blocks where it is likely that most transactions are illegitimate. Most legitimate transactions can be reversed without doing too much damage, since honest senders will make new transactions.


At least all block contents should be hashed. Maybe later a hash of a "balance sheet" of only unspent transactions could be created for the sake of efficiency. These would be version 1 blocks, and later blocks would be version 2 (likewise for transactions). Perhaps the first version 2 block would refer to this hash instead of the previous block hash.


If SHA-256 or RIPEMD-160 is broken, the key isn't necessary. Miners memorize the contents of unspent transactions, indexed by the new secure hash. People who want to spend a transaction refer to the new secure hash instead of the insecure hash.

If signing becomes totally broken, Bitcoin would probably have to restart. If the attack does not allow recovery of the private keys, maybe the same keypairs could be used with a more secure algorithm.


Yes.


An alert will be issued.


Most likely.


Creating a complete plan and testing would be good.

I assumed this. That's not answering any of my questions, though. Every single one of those steps is just a handwave. Hell, you've basically just quoted the current bitcoin spec at me.

How are we planning to come to that agreement? What happens if the attack isn't published for a little while, and so an arbitrary number of blocks have bad data in them? How do we pick out the bad while losing a minimum of good tx?

How do we hash the agreed-upon content? What format will that take? Will it be a completely new genesis block, or a new block type that is added to the current block chain? How do we re-secure the money contained in the blockchain without the private keys for those addresses?

What happens on the client side when we do this? Do people have to download a new client? If so, when they are using the old client, is there any indication that they need to download a new client? If they don't download the new client, are they still making transactions that won't be ported to the new chain? Could oblivious people continue using the old, broken blockchain for an extended period of time?

This is what I mean. We "know" how we'd do it, but no one's actually bothered to come up with an actual plan, let alone tested the scenario. Developing this plan will take a very long time - there will be holes in a first draft, some people won't agree on things at first, and so on. The time to go through this process is not "Oh shit, SHA2 has been broken with a first-preimage attack for a week now via an undisclosed exploit and we have people rewriting the blockchain and doublespending like crazy, what do we do now?", it's "Okay, this scenario is inevitable given enough time, so let's start designing and testing a solution so that when it DOES happen, the efforts can focus on actual problems instead of basic preparation."

To be clear, we need plans for a variety of scenarios. A 0day hard break in our crypto is not the only case in which we'd want to do something like this. We need to have a plan for preemptive changes too.

We'll come to an agreement as to the content of the blocks, hash them all with a secure hash, and hard-code that into Bitcoin.

I was going to start a new thread about this, but this one seems like a good match for now.

Basically I've been thinking about the argument against bitcoin saying "Crypto algorithms always eventually fail." You and I know that if SHA256 were to be broken tomorrow we could still probably salvage the block chain and switch to some unbroken crypto. The problem lies in that word "probably". We don't actually know how we would accomplish such a change yet.

Imagine the scenario where, tomorrow, someone breaks SHA in such a way that they can rewrite the block chain arbitrarily, or rewrite transactions, or something of that nature. I agree that this is extremely unlikely, but as you increase the length of time we're talking about, the probability approaches 1. We don't even stop generating coins until 2040. Can you say with complete assurance that ALL the crypto elements in our current implementation will remain completely unbroken for the next 30 years?

If you say yes to that question you are insane and also clearly don't work in test. The point is, I've been telling people that it's not a worry because we can just swap out the crypto... But no one has actually thought about how we'd go about doing that, let alone testing those plans. That's a little scary. The time to do that is not when we have to.

So we should assume that this will happen and have some plans in place for how this would be accomplished. How could we recover from a disaster of that nature? What about the less severe case where it is broken somewhat (like md5) but bitcoin is not immediately broken? We still should clearly move to a replacement for the compromised crypto, but the scenario is different - how do we handle the changeover? Can we shift in such a way that no one loses transactions in the changeover?

I think we should develop such a contingency plan for both scenarios (and any others we think of) and then test such plans on test networks.

Things to consider:
Using a brand new block chain could be an element of these plans, or we could devise a way to continue with the current chain as a base.
Can we accept old-chain transactions into our new chain on the fly, converting their formats to what we want in our new one? In a non-catastrophic scenario, if we don't do this, how do we prevent people who don't get the memo from being scammed (old bitcoin network still exists after changeover, person spends old btc via transactions that will not be ported to new chain)
How do we recover if an attacker was known to have the ability to rewrite the block chain arbitrarily? How can we recover the maximum amount of legitimate data?

I don't have any code yet, just ideas spinning in my head. I want a solid answer to the question "what happens if the crypto is broken" that's better than the counter-question "what happens if the government collapses", because one of those things really is a little more likely than the other. I don't want to answer "Well we can just change the crypto, but no one's really worked out how we'd do that." I want to be able to say "we've tested a complete changeover in that exact worst case scenario, and the majority of the network already understands how to implement that plan."

In Internet Time one day is an eternity. An hour is long enough for someone to do significant damage. We can't be having this discussion on day 0 or it really will destroy us. We need to be able to have the network running on unbroken crypto within an hour of knowing that it's busted, and we need to be sure that doing so will go smoothly.

It's a reasonable idea but a lot of work that requires co-ordination from lots of miners.

I think a better approach is just to develop a real test suite. It's not really great for financial software to have no test suite at all and anything that boils down to having people carefully manually every release (whether it's on a QA network or not) isn't going to inspire much confidence.

The nice thing about a test suite is that it can be run after every change is made. So, you can find problems as soon as they are introduced instead of having to do a potentially very complex distributed binary search.

Will Bitcoin succeed forever without substantial changes?

If the answer is is "Yes" then everything is fine and the rest of this post is unimportant.

Bitcoin is still at a relatively early stage of development. Some desired and designed features are still to be implemented and it has not been tested by either determined attacks or a "mainstream-adoption" level of transactions per second. It's plausible to imagine therefore that the software and/or protocol will have to be changed in response to situations which will occur. Implementing these changes is a big problem for the engineers however.

Whenever the software is changed, there's a small but significant chance that the new version will be worse than the old. Obviously, the intention is that the new version is superior to the old version but it's a well known reality in the software engineering world that a software update can result in disaster. As applications mature, the ratio of the incremental value of the update to the value of the current software tends to zero and the economic loss of a disaster tends to increase. Even with careful testing the probability of a shipping a new version that is broken cannot be reduced to zero and the equation implied by these facts tends to mean that updates become more infrequent, substantial and nerve-wracking.

With the recent fall in the value of USD and other national currencies against the Bitcoin , one's Bitcoin holdings become a non-trivial fraction of one's liquid assets and anything that jeopardizes these holdings is a serious concern. This must weigh heavily on the minds of the developers. The current Bitcoin client is particularly problematic in that it's a piece of software that can only be properly tested when in a network with other clients with heterogeneous versions. Fortunately at the moment, the network only has one species of client.

What Bitcoin needs is a realistic test network. The current test network is an excellent start but the activity on it is too capricious and unrepresentative of the main network. The current test network is more of a R&D network as shown by the fact that non-standard transactions are currently permitted.

I propose that a new QA network be instigated which Bitcoin users can choose to support. QA supporting users would have two bitcoin clients installed; one running the current client and one running the current QA candidate. New transactions that the user instigates on the main network would be mapped to corresponding new transactions on the QA network. Miners would be encouraged to devote a tiny but globally fixed fraction of their current real mining power so that the QA network has the same distribution of mining power as the main network. The QA network could be operated for a number of months with one release candidate and confidence in a good candidate would grow as it could be shown to cope with the current mainstream transaction load. Bitcoin software engineers could choose to inject extra other transactions into the QA network to check how it copes with either attacks or a higher level of legitimate transactions. There would have to be a mechanism to exclude griefers from the QA network who could interfere with the testing by either inserting unwanted transactions or mining with too high a fraction of their real mining power.

Normally I propose ideas with the technical details better fleshed out but in this case, it's quite a big task. I therefore submit the idea for consideration on its general principles.

ByteCoin