Rootstock chief engineer reveals that Bitcoin scripts have "new quadratic delays" and increasing block size poses security risks

Rootstock lead engineer Sergio Demian Lerner revealed in a blog post that he discovered new quadratic delays in Bitcoin Script while conducting research on the SegWit protocol.

Lerner detailed that he started working on SegWit expansion last week and studying the code, specifically the “EvalScript() function”. In the process, Lerner discovered two quadratic complexity loops in the Bitcoin Core protocol. However, Lerner said that everyone does not need to worry about this test result, and he believes that “there are worse problems in Bitcoin block verification.” However, he went on to detail a potential attack scenario from malicious miners.

Lerner explained:

“A malicious miner could create a SegWit block that takes about 10 seconds to validate. The example transaction shown in the blog took less than 10 seconds.”

“I don’t consider my findings to be vulnerabilities. However, if the block size is to be increased in the future, these issues need to be addressed before that happens. The stack value of the script example given here is not empty, but the Bitcoin protocol does not require it. Bitcoin only needs the top value to be true to accept the script.”

Bitcoin scripts need to be optimized to prevent "surprises" during future expansion

Lerner further described an issue he called “Unmet Heckler: OP_IF Abuse,” and another issue he called “Rock-and-Roll” in the OP_ROLL opcode. He also detailed a lot of work being done to optimize block processing, though he said “some old code still needs to be optimized to prevent any ‘surprises’ in the future as we scale.”

“There is a new quadratic delay in Bitcoin Script. — Sergio Demian Lerner (@SDLerner) April 17, 2017”

Additionally, Bitcoin security expert Kristov Atlas complemented Lerner and his findings. He said:

“Another great write-up of a DoS attack vector. Thanks to Lerner for the research and publication.”

Parallel Validation

Lerner's blog post also prompted another thought, with one commenter asking:

"What do you think of BUIP033?"

BUIP033 is a concept proposed by Bitcoin developer Peter Tschipper in October 2016. BUIP033 proposes creating a separate thread for block verification. Essentially, this idea is the opposite of the current method of verifying each block through the main processing thread.

Lerner responded:

“I think separate threads are essential for Bitcoin to scale. It reduces the impact of all the block size issues.”

Lerner joins scaling debate

The Rootstock chief engineer has already added his voice to the current scaling debate. He recently wrote a block size proposal involving SegWit and a 2MB block size increase. Last month, the "SegWit 2mb + soft fork/hard fork combination" scaling plan received mixed reactions and comments from Bitcoin developers. Lerner is also the inventor of ASICBOOST technology, which was hotly debated in the Bitcoin community some time ago.