Testing so that opcodes can be re-enabled

[TierNolan]

From here, Gavin says that re-enabling disabled opcode (and adding new ones) requires some kind of systematic testing framework.

Most of the opcodes were disabled with a "misc change" commit.

From here, the issues are listed.  However, no info is provided about what actually happened.

These are the ones that seem script based

- LSHIFT opcode could cause crash
- Some way to fool the script to allow transctions to be spent [ * ]
- Script executed to much processing

The success of disabling opcodes as a protection is shown by the fact that they are the first three issues and then script never caused a problem.

So, it looks like the main threats are client crashing, processor over usage and scripts mis-calculating the output.

Running the opcodes in a mini virtual machine should cover the processor problem and the crashing problem.

The virtual machine would do bounds testing on all arrays.

Each opcode would have to be given an estimate of how long it takes.  Each time an opcode completes, the processor usage is incremented by that amount.

There would a threshold for processor usage per output. 

The stack would have to be tested very carefully.  A maximum stack size could be set.

If is it working, then (many) opcode could be tested exhaustively.  If that is not possible, then they could be tested with a smaller search space and also with random instances.

A left shift opcode could have full test for 4 byte arrays and then random 32 byte arrays, for example.

It could also be tested with random stack settings.  The parts of the stack that are not affected would be checked to make sure they didn't change.

[1715190399]

1715190399

[1715190399]

1715190399

[1715190399]

1715190399

[1715190399]

1715190399

[1715190399]

1715190399

[Mike Hearn]

The most useful thing to reactivate would be tx replacement - re-adding opcodes is a hard forking change at this point and nobody has any use cases for them, whereas tx replacement is not a hard forking change and it'd be useful for some real things.

[mmeijeri]

The disabled opcodes could become more useful if they had more data to work with than the signature script. Not something that should happen any time soon, but thinking about it now can't hurt.

[piotr_n]

yeah, it was stupid to disable these commands. there is no way to turn them back, cause that would make even more trouble
but at the other hand, who would need to use them anyway - bitcoin chain is not a calculator. nobody even uses ifs yet

[TierNolan]

The most useful thing to reactivate would be tx replacement - re-adding opcodes is a hard forking change at this point and nobody has any use cases for them, whereas tx replacement is not a hard forking change and it'd be useful for some real things.

Script has the advantage that it allows people to implement new features without needing central authorization.

Ideally, scripts should be made more general, or specific use case upgrades to the script system need to be supported.

[Sergio_Demian_Lerner]

I have a hundred ideas of marvelous futuristic things that could be done with a rich script system, that can read the transaction inputs and the transaction outputs.

This is my wish list:
 PUSH_INPUT_AMOUNT / PUSH_INPUT_SCRIPT / PUSH_INPUT_COUNT (to control how money is used)
 PUSH_FEES / PUSH_OUTPUT_AMOUNT / PUSH_TOTAL_OUTPUT / PUSH_OUTPUT_COUNT (to control how money is spent)
 PUSH_BLOCK_DATE / PUSH_BLOCK_NUMBER / PUSH_BLOCK_HASH  (to control time, and random values)
 PARSE_SCRIPT_TOKEN (for previn/prevout parsing right in the script)
 PUSH_PREVTX_OUTPUT (for tx compression)

All these opcodes (maybe with the exception of PARSE_SCRIPT_TOKEN) are completely secure and it's impossible to mess things up implementing them.

You could do things like persistent transaction-sequences (inputs that are virally copied to outputs).

And once you have persistence, you can have autonomous transaction behavior, such as paying fees every month, limiting the spent amounts, etc.
These are like contracts that persist over time and over transactions.

I'm sure that if I tell you each one of my ideas you will be delighted to use them and you'll find ten more use cases that I didn't think of.

But there is this chicken-and-egg problem: because opcodes are not enabled (and probably won't be) nobody wants to research about them.

Best regards,
 Sergio.

[mmeijeri]

IIRC early versions of the scripting engine also gave access to the height of the blockchain. Theoretically you could do very interesting things if the script had access to the data in the blockchain, or at least to all ancestor transactions. Not all of these things would be good, taint-based policies come to mind as a bad example.

[Mike Hearn]

Well, I wouldn't say nobody wants to research possible future versions of script. Gavin actually told me he wanted to brainstorm Script 2.0 at some point .... it's just that I already did a lot of research into ways of using our existing capabilities and almost none of it has been implemented. This leads to a kind of "death spiral" where the moment someone notices a problem or potential issue with some functionality, instead of getting fixed (hard) it gets disabled (easy), which can be justified because nobody uses the features. We lost tx replacement entirely that way, we lost opcodes that way, we'll lose more in future if we're not careful.

So before we invent new scripting languages, we need to reverse the decline in the existing one. That means instead of just researching and reporting DoS vulnerabilities or bugs, actually writing real fixes. It means creating compelling applications that use the feature set we have to ensure it can't be just switched off on the grounds that nobody uses it and it poses additional risk.

In other words, what we need is people writing code, lots of it. That's why I focused my own research on how to use the features designed by Satoshi and not on Bitcoin 2.0.

[TierNolan]

We lost tx replacement entirely that way, we lost opcodes that way, we'll lose more in future if we're not careful.

Heh, so the moral of the story is to start creating non-standard transactions, so that whitelisting of transactions becomes harder?

Make sure every opcode is used at least once per 100 blocks :p.

[Sergio_Demian_Lerner]

That means instead of just researching and reporting DoS vulnerabilities or bugs, actually writing real fixes.

I don't understand why you underestimate the task of researching and reporting DoS vulnerabilities or bugs.
It's as useful as any other community activity.
It has been proven useful to protect the network. The only DoS bug I didn't spot (the last one) was exploited in the wild, so I must assume that ones I did foresee could have been exploited too. I even helped you with the BountyCastle vulnerability some time ago.

And don't forget that "There's an unclaimed $1.1bn dollar bounty to hack bitcoin"  (AndreasMAntonopoulos)

Each one must collaborate with what he can do best, and what he has time for.
If you like programming, and Bitcoin needs lots of programmers, then go programming. I really appreciate you work on Bitcoinj, and the microchannel implementation.
I won't tell you to stop programming and start researching vulns.

I invent and I research and I'll do this foreeeeveeeeeeeeeer......

Best regards, Sergio.

[gmaxwell]

The only DoS bug I didn't spot

There have been plenty of DoS bugs you didn't spot.   (And some of the other ones have also been used against the network)  But indeed, your help is greatly appreciated.  As always, it would be even more appreciated if you did even _MORE_, for the obvious reasons,  some of your reports haven't been quite correct and they take time to validate, a PoC or a least a walk through would be nice— but that doesn't reduce the fact that you've been helpful indeed and I'm happy you've been able to contribute what you can.

I do generally think that most attacks go unmade— or at least, we've managed to discuss serious and easily exploited "knock the whole network out" DoS bugs in open forums (because the conversation started in an open forum before we realized the severity) many times without anyone actually exploiting them. I'm not entirely sure why some DoS attacks get made but not most of the ones that could be made.  Part of this probably comes from the fact that its fairly hard to profit from them, though with more altcoins being promoted as an alternative to Bitcoin perhaps thats changing... although at the same time I expect anyone technical enough to make an attack knows that few if any of the altcoins would survive a dirty-business technical war against the Bitcoin community.

[Sergio_Demian_Lerner]

]There have been plenty of DoS bugs you didn't spot.  

Yes I know. I apologize for that comment.

I was just trying to make my point for vuln research

[Mike Hearn]

I don't understand why you underestimate the task of researching and reporting DoS vulnerabilities or bugs. It's as useful as any other community activity.

I'm not saying it's useless, but I think you're wrong, what you're doing is less useful than writing code.

I think we need (again) a reality check here. Bitcoin is nowhere near DoS proof today. It's not hard to find ways to overload nodes or cause problems, especially if you assume access to a botnet. Although you found some clever attacks, I am reluctant to even call these issues "vulnerabilities" because that implies some kind of expectation of strength.

As an example to prove I'm not just bullshitting, I just wrote a program that bloats up any arbitrary bitcoind until it runs out of memory and gets OOM killed. Eyeballing it, seems that I can add about 10mb a second to the heap with this program. It took me about 20 minutes to find this and write a proof of concept. This stuff isn't hard, it's easy because the problems are so numerous.

When someone stumbles on some random new DoS problem and insists it be treated the same as a buffer overflow, they simply place an expectation on other people to react in a mad scramble to come up with quick hacks. That's exactly why the existing contracts features have become so broken

For instance, look at the last point release. I've known for years you could add extra data to the end of a tx message and have it be relayed. Anyone who read that code carefully knew it. And it's obvious that by doing so, you could fill up the memory pool with garbage quite quickly. This was not worth reporting or discussing because we knew for a long time that mempool management requires a rewrite, such that it's got a limited size and low priority transactions that don't fit get dropped. It's just a variant of that wider problem that was already well known and has never been solved because .... nobody wrote the code to do it! Instead now we have a stupid hack that makes the code even more complicated (the right quickfix would have been to store transactions in mapRelay instead of byte buffers, thus removing the feature and simplifying the code).

tl;dr - research isn't the bottleneck for making Bitcoin hard to DoS, writing code is. Someone needs to actually implement a real anti-DoS strategy that will work, write tests to prove it works, and so on. This is all a long hard slog.

[Peter Todd]

For instance, look at the last point release. I've known for years you could add extra data to the end of a tx message and have it be relayed. Anyone who read that code carefully knew it. And it's obvious that by doing so, you could fill up the memory pool with garbage quite quickly. This was not worth reporting or discussing because we knew for a long time that mempool management requires a rewrite, such that it's got a limited size and low priority transactions that don't fit get dropped.

You're the only person on the dev team who seems to have noticed that you could add extra data; it's not all that obvious.

You ever considered you might actually just be a shitty programmer when it comes to security? All those other ways of filling up the memory pool (that we know of) cost thousands of dollars in fees, or don't actually fill it up very fast because we rate-limit free transactions. The nLockTime screwup wasn't anywhere near as bad as it was because even at $5/BTC it would have required the attacker to have about $100k worth of bitcoins to cause even just a 10KB/sec of extra traffic on the network. These days with the price at $100 memory exhaustion is the worry, and costs the attacker about 1mBTC/KB, or $10,000/GB.

Someone who actually understood security would have realized that the extra data attack created an attack thousands of times cheaper than existing ones.

It's just a variant of that wider problem that was already well known and has never been solved because .... nobody wrote the code to do it! Instead now we have a stupid hack that makes the code even more complicated (the right quickfix would have been to store transactions in mapRelay instead of byte buffers, thus removing the feature and simplifying the code).

Anyway, rather than complaining about the stupid fix, why didn't you write a better one? I mean, heck, I wrote that fix while the main network was being actively attacked by it, and had the bad luck to wind up in hospital for a few days right after. Fortunately the fix has the side-effect of inoculating the rest of the network (small tx's propagate faster than large ones) except for directed attacks, so there was time to improve it.

tl;dr - research isn't the bottleneck for making Bitcoin hard to DoS, writing code is. Someone needs to actually implement a real anti-DoS strategy that will work, write tests to prove it works, and so on. This is all a long hard slog.

"fundamentally for SPV clients an attacker only need to outspend whatever limited resource the sum of all SPV client users are willing to spend to connect to the network" <- speaking of making Bitcoin hard to DoS, what limited resource(s) you are willing to see SPV clients spend in exchange for using up node resources?

You know, fundamentally we're still learning what features Bitcoin can support without being vulnerable to attack - that's the real reason we keep on disabling stuff. But I see you spending a lot more time writing about "death spirals" of disabled features then I do you writing about ways to make those features DoS resistant. I also see you wasting people's time arguing for features to be enabled before we figure out ways to make them DoS-resistant, as you did with tx-replacement itself.

[piotr_n]

I think we need (again) a reality check here. Bitcoin is nowhere near DoS proof today. It's not hard to find ways to overload nodes or cause problems, especially if you assume access to a botnet. Although you found some clever attacks, I am reluctant to even call these issues "vulnerabilities" because that implies some kind of expectation of strength.

Well put.

[Mike Hearn]

The root cause of this disagreement is that I don't perceive Bitcoin as robust in the face of a decent DoS attacker, and other people do.

If someone does starts filling up the memory pool with bloated garbage transactions without padding? Then what? You say "oh it's more expensive", yes, but it's a long way from impossible isn't it? Especially given that once some exchange starts offering legal short selling you can much more easily turn such attacks into profit. "Thousands of dollars in fees" is hardly a big deal given the amounts at play in the current market.

Why didn't I write a better patch? Maybe if we'd taken a few more days then I'd have done so, or suggested a different approach, but because of the "zomg vulnerability" approach the one we have now got checked in and released as fast as possible leaving no time for such things.

Besides, like I said, Bitcoin still has lots of ways to DoS it. I wrote one last night just to prove a point, that's how easy it is. There actually was an anti-DoS check on that codepath but it doesn't work. So, ultimately these sorts of patches aren't a big deal. If I thought Bitcoin was really hard to DoS except for that one minor oversight then I'd probably have taken a different approach. Unfortunately that robustness won't be there until a systematic approach is taken to it.

I see you spending a lot more time writing about "death spirals" of disabled features then I do you writing about ways to make those features DoS resistant.

I've already explained multiple times how to do this properly. If you didn't see it that's not because I didn't do it. Everyone knows what I think needs to be done. I don't ever bring it up except when other people are talking about "vulnerabilities" because obviously, I'm not currently rewriting the bitcoind anti-DoS architecture, I have other things on my plate.

[Sergio_Demian_Lerner]

We have a way of establishing the severity of a vuln: the severity field (https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures)

But if you think that "DoS vulnerabilities" are not vulnerabilities, let's rename them to "DoS problems". I don't mind.

Regarding a systematic approach, I agree. This is what I wrote in the wiki much time ago (https://en.bitcoin.it/wiki/Weaknesses#Denial_of_Service_.28DoS.29_attacks):

  "Satoshi client does not directly limit peer bandwidth nor CPU usage."

Limiting peer resources would be a systematic approach.

Regarding programming: how can one help Bitcoin if one has half an hour of free time a day to dedicate to it?
I cannot program decent code in that time. It takes me half an hour to get concentrated on what I have to do, to do it right.

The best would be that people donated more money to the Foundation so the foundation could hire more programmers to do the hard work.

[piotr_n]

But if you think that "DoS vulnerabilities" are not vulnerabilities, let's rename them to "DoS problems". I don't mind.

He only said that calling them "vulnerabilities" implies some kind of expectation of strength, while no strength against DoS attacks was intended when the current protocol was being designed in the first place.. well, if it was, then somebody really screw it up badly, so let's better assume that it wasn't...

Doing it the proper way, the architecture of the network protocol, as well as the architecture of client's core components (e.g. memory pool, peer trust management, signature verification engine), should be based on a DoS prevention design. Instead of being based on DoS proof-of-concepts with prevention patches that follow, which certainly seems to be the case now.

[jdillon]

The root cause of this disagreement is that I don't perceive Bitcoin as robust in the face of a decent DoS attacker, and other people do.

If someone does starts filling up the memory pool with bloated garbage transactions without padding? Then what? You say "oh it's more expensive", yes, but it's a long way from impossible isn't it? Especially given that once some exchange starts offering legal short selling you can much more easily turn such attacks into profit. "Thousands of dollars in fees" is hardly a big deal given the amounts at play in the current market.

Seems to me your advice for someone deciding if it's worth installing security screens on their windows in a high-crime area is "Why bother? All the thieves have to do is rent an excavator."

The security of Bitcoin itself is a matter of cost-vs-reward, the 51% attack, so we should ensure the cheapest way to attack Bitcoin remains via the extremely expensive 51% attack.

Why didn't I write a better patch? Maybe if we'd taken a few more days then I'd have done so, or suggested a different approach, but because of the "zomg vulnerability" approach the one we have now got checked in and released as fast as possible leaving no time for such things.

I see you would have rather Peter done nothing and let an actual attack on mainnet continue.

I'm glad we didn't put you in charge of the defense of the island of Britain back in WWII.

Besides, like I said, Bitcoin still has lots of ways to DoS it. I wrote one last night just to prove a point, that's how easy it is. There actually was an anti-DoS check on that codepath but it doesn't work.

So are you going to report the issue so someone can fix it? Or are you just making up bullshit?

I've already explained multiple times how to do this properly. If you didn't see it that's not because I didn't do it. Everyone knows what I think needs to be done. I don't ever bring it up except when other people are talking about "vulnerabilities" because obviously, I'm not currently rewriting the bitcoind anti-DoS architecture, I have other things on my plate.

I remember from your tx-replacement debacle your "solution" was to rate-limit replacements, thereby making the replacement feature useless until the attacker gave up. Meanwhile you aren't willing to accept taking fees into account to allow legit users to get their replacements prioritized, and in general you even advocate that we do away with fees in general.

You also didn't answer Peter's question about what limited resource you would like to see SPV clients spend so that a DoS-ing attacker can be distinguished from legit users.

[Greydon Isis]

isn't that the purpose for test net 3 bitcoins? why not try it out on them~~~