Topic: [2017-04-19]Rootstock Engineer Discovers Quadratic Delays in Bitcoin Scripts (Read 263 times)

On April 16 the chief engineer of Rootstock, Sergio Demian Lerner, revealed in a blog post that he had found new quadratic delays in Bitcoin scripts while researching the Segregated Witness (Segwit) protocol.

Rootstock Chief Engineer Reviews Segregated Witness

Rootstock Engineer Discovers Quadratic Delays in Bitcoin ScriptsLerner details he began researching Segwit scaling last week and started studying the code “specifically, the EvalScript() function.” During this time, Lerner found two quadratic complexity loops in the Bitcoin Core protocol. The results of the tests shouldn’t make anyone worry, Lerner says, as he believes there are “worse problems in Bitcoin block verification.” However, he goes on to detail one possible attack scenario from a malicious miner within the network.       

“A malicious miner can create a Segwit block that requires approximately 10 seconds to be verified,” explains Rootstock’s chief engineer. “Since the examples presented in this post consume less than 10 seconds.”

I don’t consider my findings as vulnerabilities. However, if the block size is to be increased in the future, these problems should be solved prior to increasing the block size. The scripts presented here as examples do not leave the value stack empty, but the Bitcoin protocol does not require it. Bitcoin only requires the top value to be true to accept the script.
‘Optimizations Needed to Prevent Future Surprises in the Scaling Path’

Lerner goes on further describing an issue that he calls “the unsatisfied questioner: OP_IF abuse” problem, and an issue called “Rock-and-Roll” which is located in the OP_ROLL opcode. He also details that a lot has been done as far as optimizing block processing but says “there are a few pieces of old code that still require some minor optimizations to prevent future surprises in the scaling path.”

New quadratic delays in Bitcoin scripts –> https://t.co/mC2oBxyDlX

— Sergio Demian Lerner (@SDLerner) April 17, 2017
As the research from Lerner gained attention across forums and social media, most people were pleased with the engineer’s discoveries. One Reddit user exclaims, “It’s important that these exploits are found, disclosed, and hopefully patched.”

In addition, Bitcoin security expert Kristov Atlas complemented Lerner and his findings via Twitter, stating:         

Another great write-up on DoS vector. Thanks for researching and posting.
Parallel Validation

Another idea brought to light on Lerner’s blog post comes from a commenter asking, “Do you have already an opinion on BUIP033: Parallel Validation?” BUIP033 is a concept conceived by Bitcoin developer Peter Tschipper in October of 2016, which proposes to create a separate thread for block validation. Essentially this would be in contrast to the current method of validating each block through the main processing thread.

“I think it is essential to scalability,” Lerner replies to the comment. “It reduces the impact of all block-size related issues.”

Lerner’s Involvement with the Scaling Debate

The Rootstock engineer has voiced his opinion quite a bit throughout the great Bitcoin scaling debate. The developer has also written a block size proposal recently which involves Segwit and a 2mb block size increase. The “Segwit 2mb – combined soft/hard fork” scaling plan got mixed responses and reviews from Bitcoin developers last month. Lerner is also one of the inventors of the controversial mining patent ASIC Boost which has escalated the scaling discussion to new levels.
https://news.bitcoin.com/rootstock-engineer-quadratic-delays-bitcoin-scripts/