tradecraftio / tradecraft

Tradecraft integration/staging tree https://tradecraft.io/download
Other
13 stars 9 forks source link

Change ROLL semantics into "deep swap" for witness scripts #57

Open maaku opened 4 years ago

maaku commented 4 years ago

To support the relaxation of script limits for witness scripts, some opcode semantics need to be altered. One of these is ROLL, which has runtime costs equal to the size of the stack. If the stack has 30,000 entries, then 30000 ROLL requires moving 30000*sizeof<vector<unsigned char> > bytes around, because it deletes an item deep in the stack.

This is unacceptable and ROLL needs to go. However many of the use cases for ROLL could be accomplished, sometimes even more cheaply, with an opcode that swaps the top most stack element with the element n deep in the stack. This is constant-time behavior: no moving of intermediate bytes is required. For witness scripts, ROLL should be replaced with this "deep swap" semantics.

maaku commented 4 years ago

60 removes OP_ROLL from witness scripts, giving it instead "return true" semantics. This solves the immediate performance issue of OP_ROLL in witness scripts, and allows us to take our time in getting the semantics right as part of a later script upgrade.

I therefore removed this issue from the "Deploy segregated witness" project, but am keeping it open to track the issue of adding new "DEEPSWAP" semantics for this opcode in witness scripts.