Bitcoin Forum
October 22, 2019, 02:36:49 AM *
News: 10th anniversary art contest
 
   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 219 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: 694
Merit: 1113


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
 #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

1571711809
Hero Member
*
Offline Offline

Posts: 1571711809

View Profile Personal Message (Offline)

Ignore
1571711809
Reply with quote  #2

1571711809
Report to moderator
1571711809
Hero Member
*
Offline Offline

Posts: 1571711809

View Profile Personal Message (Offline)

Ignore
1571711809
Reply with quote  #2

1571711809
Report to moderator
1571711809
Hero Member
*
Offline Offline

Posts: 1571711809

View Profile Personal Message (Offline)

Ignore
1571711809
Reply with quote  #2

1571711809
Report to moderator
"With e-currency based on cryptographic proof, without the need to trust a third party middleman, money can be secure and transactions effortless." -- Satoshi
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1571711809
Hero Member
*
Offline Offline

Posts: 1571711809

View Profile Personal Message (Offline)

Ignore
1571711809
Reply with quote  #2

1571711809
Report to moderator
Carlton Banks
Legendary
*
Offline Offline

Activity: 2520
Merit: 1991



View Profile
October 09, 2019, 11:15:12 AM
Merited by 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: 694
Merit: 1113


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: 1792
Merit: 2055

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: 694
Merit: 1113


Novice C♯ Coder


View Profile WWW
October 10, 2019, 05:35:27 AM
Merited by Welsh (4), joniboini (2)
 #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: 694
Merit: 1113


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: 924
Merit: 664


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: 694
Merit: 1113


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: 2646
Merit: 1425



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: 924
Merit: 664


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: 1302
Merit: 895


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: 694
Merit: 1113


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: 530


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

Check this

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

Carlton Banks
Legendary
*
Offline Offline

Activity: 2520
Merit: 1991



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: 694
Merit: 1113


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: 924
Merit: 664


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.

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!