[Challenge] Come up with scripts that could take a long time to evaluate

[Coding Enthusiast]

Scripts are being evaluated/run so that we can verify the validity of the given transaction. Depending on the script itself and the implementation, this evaluation could take a much longer time than normally expected.
As a challenge, try to come up with such scripts that could take longer than normal (could be 10 second, minute or hour!). There are also some rare examples out there on the internet from old days that you can find and post here.

• The script doesn't have to be standard but it has to be valid (eg. no disabled OPs).
• It doesn't have to be in a full transaction. It could be as scriptPub, scriptSig and if available redeemScript or witnesses. Or simply 1 script from start to end.
• It should also include the expected time that it takes to evaluate in addition to the device hardware and platform used.

This topic is self-moderated to prevent it from going off-topic.

[Carlton Banks]

• It should also include the expected time that it takes to evaluate.

I would suggest naming a range of valid hardware platforms, or that platform used to benchmark should be a part of each submission. Otherwise you might waste time discovering that someone was using some underpowered embedded device (or a Nintendo Gameboy) to produce their quirky, but totally honest, result

[Coding Enthusiast]

I would suggest naming a range of valid hardware platforms, or that platform used to benchmark should be a part of each submission. Otherwise you might waste time discovering that someone was using some underpowered embedded device (or a Nintendo Gameboy) to produce their quirky, but totally honest, result

(Added your suggestion to OP)
I'll also try to publish a final benchmark in a comparing way with a regularly used script as the base-line and anything else I can come up with or find here as the rest.

[ETFbitcoin]

I just remember this thread : New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify

According to https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures, it's not fixed yet, but it's possible no one bother update it's status.

[Coding Enthusiast]

I just remember this thread : New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify

The posts by Sergio here and on his blog was what I had in mind when I said there are rare examples out there already. The first problem was that some of those examples were quite redundant such as the OP_0 OP_CheckSig one which fails right away. But at the same time it is the reason why I started this.

Here is a long rant explaining what I had in mind starting this topic:
As you may have noticed, over the pat 2 years I've been implementing bitcoin from scratch without looking at source codes. Sometimes I come up with some ideas which I explore a little. Right now I'm trying to close the chapter on my Blockchain namespace and as I was implementing scripts and came across that post I came up with the idea of some sort of Just In-Time optimization. It is inspired by what .net JIT compiler does.
Basically it first compiles any code written in any of the .net languages (C#, F#, VB,..) into an Intermediate Language, then JIT compiler converts it into machine code. You can click on the links to see it for an example code, what happens is that the compiler also optimizes the code so the first line (int temp...) doesn't even exist in the final code because it is not used and also the second line is turned into 1 command (ror) instead of being 4 (2 shifts, 1 OR and 1 subtract).

So importing that idea into scripts would be something like this which I'm currently experimenting with. You have the script (raw bytes):

Code:

47304402201a5f741e3ffdb9f33a1828e72829d9c100df79e754dac1f0d5d4251d77c300df022012a87bbed7547657de6ef328cadf1b99e3121429df590fa61cac535c98d38e3c0121034746a7851078bcc646b301be2d0d537dff68ecbf23f432f4338e44add5f4cf5d
76a914a3646f520269f61bba6f56c975eaa593827a3a7188ac

convert it to a list of OPs (IOperation[]) (loosely coupled object oriented approach)

Code:

PushDataOp()
PushDataOp()
DUPOp()
Hash160Op()
PushDataOp()
EqualVerifyOp()
CheckSigOp()

then run it. This is the pseudo-code of what is actually being run:

Code:

stack.push <- first pushOp
stack.push <- second pushOp
stack.peek <- DUP
stack.push
stack.pop <- HASH160
hash.compute
stack.push
stack.push <- third pushOp
stack.pop <- EqualVerify
stack.pop
compare
stack.push
stack.pop
check.true
stack.pop <- CheckSig
stack.pop
checksig

each "stack" operation also consists of multiple checks to expand allocated memory for example, to move index/position and a lot of copies which don't show up in above pseudo-code.
As you can see, this very simple script is doing a ton of pointless operations with the stack. This is a micro optimization which will make a little difference but the idea stands:
You turn this pattern into a single IOperation such as P2PKHOp(), then it would become an object containing these IOperations but instead of calling their Run() it uses the workaround:

Code:

hash.compute(OperationList[1].Data)
compare(OperationList[4].Data)
checksig(OperationList[0].Data, OperationList[1].Data)

As it can be seen, usage of a stack was completely eliminated.

Bitcoin contains a lot of stack manipulation OPs which could be optimized:
OP_DUP + OP_DROP => nothing
OP_SWAP + OP_NIP => OP_DROP
OP_CheckSig + OP_Drop => only remove and verify 2 preceding pushes and skip signature verification!

[Coding Enthusiast]

-snip-

Please keep discussion on topic, if you want to discuss about attack vectors on non-standard scripts open a new topic.

[aliashraf]

op,
From your latest comment, I understand that you are looking for an optimization strategy to execute scripts in a more elegant way what I don't understand is why do you bring this problem up with such a challenge? Is it just for justifying your effort as being important? If so, I'm telling you it is very important, because running scripts in bitcoin will eventually become a bottleneck once the scaling problem is solved.

[Coding Enthusiast]

op,
From your latest comment, I understand that you are looking for an optimization strategy to execute scripts in a more elegant way what I don't understand is why do you bring this problem up with such a challenge? Is it just for justifying your effort as being important? If so, I'm telling you it is very important, because running scripts in bitcoin will eventually become a bottleneck once the scaling problem is solved.

I proposed it as a challenge mainly because I consider it to be a challenge to come up with such scripts that could take considerable amount of time to evaluate. Same with optimizing them, the example above with optimization only takes about 1.5 micro second less (but allocates 1 KB less memory), which is another challenge.
I'm also not trying to justify anything to anyone!

running scripts in bitcoin will eventually become a bottleneck once the scaling problem is solved.

It doesn't look like it to be honest. Most operations are quite fast, the most time consuming ones are the *SIG operations which are taking most amount of time due to ECDSA being the "bottleneck".

[odolvlobo]

My thoughts:

I believe that the slowest operations are the signature checking operations. So, the most time consuming transaction would simply do OP_CHECKSIG repeatedly (with a couple of stack operations in between).

Since there are no loops, each instruction is executed at most once. So, the execution time is roughly proportional to the size of the transaction, which means that if you want to be a nuisance, you are going to have to pay for it. Furthermore, ss cryptography becomes more prevalent, we are going to start seeing cryptographic operations in hardware, which should speed up the signature checking operations greatly.

[aliashraf]

running scripts in bitcoin will eventually become a bottleneck once the scaling problem is solved.

It doesn't look like it to be honest. Most operations are quite fast, the most time consuming ones are the *SIG operations which are taking most amount of time due to ECDSA being the "bottleneck".

ECDSA is not the bottleneck it is just part of a CPU task, script validation, improving any part of this process equally improves the whole task, unlike what we have with bottlenecks.

In some circumstances, bitcoin is CPU bound and it is always about validating transactions and it is why script processing shows up as a bottleneck in such circumstances. For example, average full nodes in the bootstrap phase are bound to their CPU performance rather than network or HDD and it is because transactions included in blocks are not already validated and installed in mempool.

I think in a truly scaled situation, it is very likely that missing transactions from mempool will become a more common practice and we will have CPU as a bottleneck in ordinary block validation because of script processing and it is always good to have a more optimized engine for this.

[hatshepsut93]

So, you are essentially asking to find a DOS vulnerability in Bitcoin? I'm sure a lot of people have tried that, some competitors, legacy financial organizations or even just trolls wouldn't hesitate to use it to attack Bitcoin. The fact that such attacks didn't occur should mean that there's no such scripts, or they are extremely hard to find.

On a side note, I think this attack wouldn't be too scary, as rational miners wouldn't include such transactions in blocks, because it would hurt both them and the network, so at best this vulnerability would only last until miners upgrade their software to ignore malicious transactions.

[Coding Enthusiast]

So, you are essentially asking to find a DOS vulnerability in Bitcoin? I'm sure a lot of people have tried that, some competitors, legacy financial organizations or even just trolls wouldn't hesitate to use it to attack Bitcoin.

Since almost all miners reject non-standard scripts, in order to perform this "attack" one has to be a miner. A malicious miner doesn't need this topic to perform something like that!

[Sergio_Demian_Lerner]

Check this

https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/

[Carlton Banks]

Check this

https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/

I think sipa and jl2012 implemented a (your) solution to this: https://github.com/bitcoin/bitcoin/pull/16902

not yet merged however.

[Coding Enthusiast]

Check this
https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/

Thanks.
By the way it is best that when you post a link to code on GitHub you also include the commit hash in that it in order to keep the link valid forever. For instance https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L659 (from your blog post) right now is pointing to an empty line since it is on master and due to changes in that file over time.
You could do that by simply pressing Y (on your keyboard) to get the permanent link instead: https://github.com/bitcoin/bitcoin/blob/46d6930f8c7ba7cbcd7d86dd5d0117642fcbc819/src/script/interpreter.cpp#L659

[aliashraf]

Check this

https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/

Thank you for the hint, I remember this post of you and the impression. As you have correctly mentioned there: it is to be considered a more serious problem when you look from a perspective that scaling is in the horizon. it is what I reminded to op, above-thread, too.

[Coding Enthusiast]

Could anyone help me figure out how I could use bitcoin core to benchmark validation of the following examples? I'm not that familiar with core, the only idea I can come up with right now is to use getblocktemplate to submit the entire block and compare the results.

The following are some initial results of some benchmarks, at this point it is more about exploration of some ideas I have and optimizing certain parts but overall there is not much optimization in place. There might be some mistakes in some places that I have missed.
specs:

Code:

BenchmarkDotNet=v0.11.5, OS=Windows 7 SP1 (6.1.7601.0)
Intel Core i3-6100 CPU 3.70GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
Frequency=3609482 Hz, Resolution=277.0481 ns, Timer=TSC
.NET Core SDK=2.1.801
  [Host] : .NET Core 2.1.12 (CoreCLR 4.6.27817.01, CoreFX 4.6.27818.01), 64bit RyuJIT

Job=InProcess  Toolchain=InProcessEmitToolchain 

Case 1. verifying P2PKH scripts
This is from my long comment above. Initially inside optimizer I was doing some boxing/unboxing that slowed things down a lot. Fixing that gives a much better result. The CheckSigOp is mocked to simplify things and avoid needing a tx and skip ECC.

|    Method |     Mean |     Error |     StdDev | Ratio | RatioSD |   Gen 0 | Gen 1 | Gen 2 | Allocated |
|---------- |---------:|----------:|-----------:|------:|--------:|--------:|------:|------:|----------:|
| SimpleRun | 439.5 us | 9.2282 us | 10.6272 us |  1.00 |    0.00 | 91.7969 |     - |     - | 141.23 KB |
| Optimized | 373.3 us | 0.2264 us |  0.2118 us |  0.85 |    0.02 | 75.1953 |     - |     - | 115.79 KB |

Case 2. Many pushes

Code:

OP_0 (201 times)
OP_CHECKSIG (200 times)
OP_1
push [ 0 ]
OP_IF
OP_0 (9601 times)
OP_ENDIF

Since there is no signature to check here, CheckSigOp is the real object that handles reading signature and failing right away as invalid data is found. The optimization here is due to many pushes that are supposed to push 201 items to the stack. The optimizer is supposed to recognize that and skip all the pushes until it reaches another type of IOperation then based on how many items that op pops it calls on the data inside the array.

|    Method |     Mean |    Error |   StdDev |   Median | Ratio |
|---------- |---------:|---------:|---------:|---------:|------:|
| SimpleRun | 786.1 us | 10.88 us | 60.57 us | 782.4 us |  1.00 | 
| Optimized | 743.4 us | 10.38 us | 58.15 us | 723.1 us |  0.95 | 

Case 3. Many OP_IF`s

Code:

0
OP_IF { 100 times }

0 { 9798 times }

OP_ENDIF { 100 times }
1

From what I understand from core, it runs the scripts as it interprets them. Here I read (interpret or convert to objects) then run, hence the second bench below called "ReadAndRun" where it does both reading and running afterwards in one place. Assuming a block of 1,000,000 bytes contained 100 transactions each containing these scripts (script size is 10,000 bytes) it wold take ~0.5 second to verify.

|     Method |       Mean |    Error |   StdDev |    Gen 0 |    Gen 1 |   Gen 2 |  Allocated |
|----------- |-----------:|---------:|---------:|---------:|---------:|--------:|-----------:|
|  SimpleRun |   677.3 us | 13.42 us | 15.98 us | 124.0234 |  61.5234 | 41.0156 |  686.45 KB |
| ReadAndRun | 1,343.7 us | 18.92 us | 16.77 us | 248.0469 | 123.0469 | 82.0313 | 1372.67 KB |

Case 4. Many OP_ROLL`s

Code:

1  {999 times}
998 OP_ROLL { 200 times }

Same as above "ReadAndRun" bench is added.

|     Method |     Mean |     Error |    StdDev | Ratio |    Gen 0 |  Gen 1 | Gen 2 | Allocated |
|----------- |---------:|----------:|----------:|------:|---------:|-------:|------:|----------:|
|  SimpleRun | 122.0 us | 1.5537 us | 1.4534 us |  1.00 | 333.1299 | 0.1221 |     - |  511.5 KB |
| ReadAndRun | 145.6 us | 0.5623 us | 0.4985 us |  1.19 | 385.4980 |      - |     - | 594.83 KB |

Future plans:
I intend to continue working on this more and compare things with some actual time values I gain using bitcoin core. But for now I'll move on to optimization of my Asymmetric Cryptography and start the comparison there.