Title: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 09, 2019, 10:39:30 AM 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.
This topic is self-moderated to prevent it from going off-topic. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Carlton Banks on October 09, 2019, 11:15:12 AM
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 Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 09, 2019, 11:54:44 AM 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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: ABCbits on October 09, 2019, 06:28:01 PM I just remember this thread : New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify (https://bitcointalk.org/index.php?topic=140078.msg1491085#msg1491085)
According to https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures (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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 10, 2019, 05:35:27 AM I just remember this thread : New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify (https://bitcointalk.org/index.php?topic=140078.msg1491085#msg1491085) The posts by Sergio here and on his blog (https://bitslog.com/2017/01/08/a-bitcoin-transaction-that-takes-5-hours-to-verify/) 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 (https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBLANmgExAGoAfAAQGYACcgJloEYB2AWACgBvD632mgK7YAdhmoAlCBgCGGGOOwBzABYYAFENHUEaaiLHCAlN3Z8zerXIC2AB2oBeaozo1i1YQG4e53uWbU1BGoAPmD3Q2pSAKCAHhiAygY4cMMvUz4AX29eDgygA===), then JIT compiler converts it into machine code (https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAZgAJiAmSgRgHYBYAKAG8XzPKKBXASwB2GcgCUIGbBhgi+AcwAWGABT8h5BGnKDhAgJTtmXI1rVT8AB3IBecrSoUA1OQEBuDsc7F65JQnIA+f2ddckIfPwAeCJ9SGjhg3TdDLgBfd04WFKA=). 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 Code: PushDataOp() Code: stack.push <- first pushOp 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) 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! Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 10, 2019, 06:06:21 AM -snip- Please keep discussion on topic, if you want to discuss about attack vectors on non-standard scripts open a new topic.Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: aliashraf on October 10, 2019, 10:41:09 AM 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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 10, 2019, 12:33:32 PM 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! Quote 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". Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: odolvlobo on October 10, 2019, 06:03:24 PM 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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: aliashraf on October 11, 2019, 03:46:41 AM 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". 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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: hatshepsut93 on October 12, 2019, 11:24:53 AM 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. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 12, 2019, 03:49:00 PM 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! Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Sergio_Demian_Lerner on October 16, 2019, 04:54:20 PM Check this
https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/ Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Carlton Banks on October 17, 2019, 01:05:44 AM 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 (https://github.com/bitcoin/bitcoin/pull/16902) not yet merged however. Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on October 17, 2019, 06:08:39 AM 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 (https://help.github.com/en/articles/getting-permanent-links-to-files) instead: https://github.com/bitcoin/bitcoin/blob/46d6930f8c7ba7cbcd7d86dd5d0117642fcbc819/src/script/interpreter.cpp#L659 Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: aliashraf on October 18, 2019, 05:54:17 AM Check this 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. https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/ Title: Re: [Challenge] Come up with scripts that could take a long time to evaluate Post by: Coding Enthusiast on November 03, 2019, 04:33:22 AM 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) 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 | Case 2. Many pushes Code: OP_0 (201 times) | Method | Mean | Error | StdDev | Median | Ratio | Case 3. Many OP_IF`s Code: 0 | Method | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated | Case 4. Many OP_ROLL`s Code: 1 {999 times} | Method | Mean | Error | StdDev | Ratio | Gen 0 | Gen 1 | Gen 2 | Allocated | 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. |