Bitcoin Forum
November 13, 2019, 07:27:49 PM *
News: Help collect the most notable posts made over the last 10 years.
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: [Challenge] Come up with scripts that could take a long time to evaluate  (Read 278 times)
This is a self-moderated topic. If you do not want to be moderated by the person who started this topic, create a new topic. (3 posts by 3 users deleted.)
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 09, 2019, 10:39:30 AM
Last edit: October 09, 2019, 11:51:35 AM by Coding Enthusiast
Merited by ETFbitcoin (1), hugeblack (1)
 #1

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.

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

The Bitcoin Forum is turning 10 years old! Join the community in sharing and exploring the notable posts made over the years.
Carlton Banks
Legendary
*
Offline Offline

Activity: 2548
Merit: 2041



View Profile
October 09, 2019, 11:15:12 AM
Merited by ETFbitcoin (1), Coding Enthusiast (1)
 #2

  • 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

Vires in numeris
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 09, 2019, 11:54:44 AM
 #3

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.

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

ETFbitcoin
Legendary
*
Offline Offline

Activity: 1820
Merit: 2079

Use SegWit and enjoy lower fees.


View Profile WWW
October 09, 2019, 06:28:01 PM
Merited by Coding Enthusiast (1)
 #4

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
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 10, 2019, 05:35:27 AM
Merited by Welsh (4), joniboini (2), ETFbitcoin (1), hugeblack (1)
 #5


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!

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 10, 2019, 06:06:21 AM
 #6

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

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

aliashraf
Hero Member
*****
Offline Offline

Activity: 952
Merit: 706

always remember, remember the cause


View Profile WWW
October 10, 2019, 10:41:09 AM
 #7

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
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 10, 2019, 12:33:32 PM
 #8

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".

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

odolvlobo
Legendary
*
Offline Offline

Activity: 2674
Merit: 1435



View Profile
October 10, 2019, 06:03:24 PM
 #9

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.

Buy stuff on Amazon at a discount with bitcoins or convert Amazon points to bitcoins: Purse.io
Join an anti-signature campaign: Click ignore on the members of signature campaigns.
aliashraf
Hero Member
*****
Offline Offline

Activity: 952
Merit: 706

always remember, remember the cause


View Profile WWW
October 11, 2019, 03:46:41 AM
 #10

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
Hero Member
*****
Offline Offline

Activity: 1330
Merit: 922


Bitcoin realist


View Profile
October 12, 2019, 11:24:53 AM
 #11

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
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 12, 2019, 03:49:00 PM
 #12

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!

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 547
Merit: 531


View Profile WWW
October 16, 2019, 04:54:20 PM
Merited by Coding Enthusiast (5), joniboini (2), ETFbitcoin (1), aliashraf (1), hugeblack (1)
 #13

Check this

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

Carlton Banks
Legendary
*
Offline Offline

Activity: 2548
Merit: 2041



View Profile
October 17, 2019, 01:05:44 AM
 #14


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

not yet merged however.

Vires in numeris
Coding Enthusiast
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
October 17, 2019, 06:08:39 AM
 #15


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

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

aliashraf
Hero Member
*****
Offline Offline

Activity: 952
Merit: 706

always remember, remember the cause


View Profile WWW
October 18, 2019, 05:54:17 AM
 #16

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
Hero Member
*****
Offline Offline

Activity: 701
Merit: 1157


Novice C♯ Coder


View Profile WWW
November 03, 2019, 04:33:22 AM
Merited by Welsh (6), hugeblack (2), ETFbitcoin (1)
 #17

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.

Projects List+Suggestion box
Donation link using BIP21
Bech32 Donation link!
BitcoinTransactionTool (0.9.2):  Ann - Source Code
Watch Only Bitcoin Wallet (supporting SegWit) (3.1.0):  Ann - Source Code
SharpPusher (broadcast transactions) (0.10.0): Ann - Source Code

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!