How to Implement ECDSA Signature Verification in Script and Why DATASIGVERIFY is a Million-Fold Subsidy
ECDSA Signature Verification
It is possible to implement ECDSA signature verification using a very long script that involves first implementing a big number library and secondly implementing loops by unrolling them up to a maximum number of iterations N based on a best guess of how many iterations N are required to perform the loop in all or most cases.
This is the ECDSA signature verification algorithm algorithm (subsequently referred to as "ECDSA"):
Anyone who has programmed in Script might have an idea how to do some of these things, but may have no idea how to do others. Step 1, check that Q_A is not equal to the identity element, is easy, because we have OP_EQUAL. Some steps, like HASH(m), also can be done almost trivially in Script because hash methods are primitive operations.
I won't cover every case, but I will explain on overview of how to do the most important operations. The hard part is big numbers and the operations we need to perform on them. The curve used by Bitcoin, secp256k1, uses 256 bit big numbers (32 bytes). We need to be able to add, multiply, invert, and modulus on big numbers. Any big number library has these methods built-in. We need these methods in Bitcoin.
The way to do this is to base your big number library on CScriptNum. Bitcoin Scripts has numbers built-in based on the basic type CScriptNum. However, these numbers are four bytes long (which overflow to longer), not 32 bytes. We need to be able to combine multiple CScriptNums to one to be able to add them. This is straightforward using the standard addition algorithm. We carry the result and add it to the next.
An important concept to bare in mind when trying write scripts is that we have access to two stacks. With two stacks, we can map Script to a 2PDA. It is known that a 2PDA is equivalent to Script with two stacks and an outer loop and that this is Turing complete, and therefore possible to compute anything we want. Except that we do not have an outer loop. However, we do have the ability to unroll a loop, which is an adequate substitute.
The way this works is as follows. Instead of looping N times, we estimate the maximum number of iterations N and create a long series of N conditionals that check whether are still in the loop. If we are still in the loop, we execute the contents of the conditional, otherwise we do nothing. If N is large and in some special case we only execute a single loop, then almost the entire script is wasted space. But in some cases we may use every conditional. In fact, in some cases, we may run out of conditionals before we are done - in those cases, we should have picked a bigger value of N.
Although nearly everyone things Bitcoin is not Turing complete based on the fact that there is no outer loop, the fact that Bitcoin allows for unrolling a loop is actually adequate to compute any number which can be computed by any computer, which can be seen as follows. If any real computer computes a number, we can discover how many conditionals (N) we need to put in the series by simply running it on a real computer first. In some cases we will be able to pick N large enough to cover every input. In other cases we may need to pick a number high enough to cover most but not all cases. In some cases N will be so large that the fees on the transaction are too high to be economical to broadcast (assuming we remove Script size, transaction size, and block size limits). We do know that no matter what, if it can run on a normal computer, we can run it on Script by picking N sufficiently large. (Because we know the program terminated on the real computer if we actually got the result. This is always the case for ECDSA, which does not loop endlessly, and always terminates).
Once the concept of unrolling a loop is understood, one can imagine how to implement all of the big number functions by unrolling loops, because each one of them is actually a loop around more basic operations. Even the division algorithm can be implemented by using recursion (by unrolling a loop) and using the more basic operations of addition and subtraction, since we do not currently have OP_DIV (but hopefully will soon).
The most important big number operation is point multiplication, because this is a slow operation. Point multiplication is hard because you are multiplying two extremely large numbers. It's worth noting that by "multiplying" in the case of an elliptic curve we mean performing a series of "additions" on the group. Neither "multiplication" nor "addition" are actually the same as the common definition. "Addition" is actually the basic group operation. In order to perform this operation, one must refer to the definition. "Multiplication" is defined as a series of additions.
It is hard to to point multiplication because you are adding numbers an extremely large number of times. However, there is an algorithm to do this more quickly that breaks down the additions into a smaller number of additions and multiplications.
In a nutshell, there is nothing here that can't be done by unrolling every loop into N conditionals where N is picked to be sufficiently large to cover all inputs and inside the conditionals we use the basic operations already available in Script.
One can now do a thought experiment on how to fully implement ECDSA in Script.
- Implement all basic big number operations. This will involve loops inside of loops, all of which must be unrolled to their maximum possible size.
- Implement elliptic curve point multiplication and all other elliptic curve operations. Again, this will involve loops inside of loops, all of which must be unrolled to their maximum possible size.
This will result in a spectacularly large script. Instead of simply having a loop like the programming languages we are used to, which might be a hundred bytes or so, we need to unroll every loop inside of every loop, and each iteration of the loop will need to be in the script. We need to do this assuming the worst case, otherwise our algorithm will fail for some inputs. If we have N iterations, then the size would be N times one hundred.
This is why I estimated that doing something like DATASIGVERIFY would be possible without a special op code except that it would use a "million" operations, or would be about a megabyte in size. The value of "one million" is a guess. But to anyone who has followed my reasoning so far, you can surely agree the size of the script would be far larger than any we have seen on the blockchain so far.
But: it is possible with long scripts.
The problem with DATASIGVERIFY (DSV) is that it is a complex operation. Unlike operations like OP_MUL which can be done in a single cycle on a CPU, DSV uses ECDSA, which even when using an advanced and fast implementation like libsecp256k1 involves many CPU cycles. CHECKSIG (on which DSV is based) is by far the most expensive operation available in Script (again, for anyone familiar, we know it is much slower than hash functions).
Let us suppose DSV takes X total operations including every loop unrolled to its maximum size. I said in my video that X was a million, but that was a guess. You can subsitute whatever value you think is most likely. Normally, scripts in Bitcoin must pay 1 satoshi per byte. If one can do DSV right now (assuming we removed Script size limits), one would have to pay X satoshis in order to execute this script. However, with DSV, we are making this expensive operation cost only 1 byte, or 1 satoshi. Therefore one can compute the value of the subsidy as X/1 = X satoshis. If X is one million, then the subsidy is 1 million satoshis, of 0.01 BCH, or about $4.50 USD at current prices.
Almost all of Script's basic operations are simple operations that can be performed with one or a few CPU cycles. The exception is CHECKSIG. Therefore, CHECKSIG is subsidized. However, this is not a problem for CHECKSIG. It makes perfect sense that the primary money function of Bitcoin is subsidized, because in order to actually spend their mining reward, the miners need to use this operation.
DSV is different. It is unrelated to and useless to the primary money function of Bitcoin. It is a subsidy to whoever uses this operation. Instead of paying $4.50 per usage, they pay only 1 satoshi. The problem with subsidies is best understood by referencing "Economics in One Lesson" by Henry Hazlitt. Think not only of the group who benefits from this operation near-term. Think about the consequences, both good and bad, for the group who uses the operation both near-term and long-term, and also how this impacts every other group near-term and long-term. In other words, if miners are doing a whole lot of DSV for almost free, what else are they not doing that they can no longer afford?
It is not a good idea to subsidize this operation without understanding the economic implications and to know that this of all operations is actually worth subsidizing and is the best one to subsidize. Each operation that is subsidized means one or more other operations or use-cases are not - miners only have so many CPU cycles to validate transactions. That the software is relatively easy to write is a poor reason that does not factor in any of the economic implications.
Bitcoin has the ability to compute the cost of running a script by simply looking at the size. This is why Bitcoin does not have gas like Ethereum. The end-game for subsidizing a bunch of op codes would be that we surely get some wrong, and therefore need to change the fee rate for some of these operations. This would lead to a proxy of gas for Bitcoin - we would need to compute the actual fee based on which particular operations were used rather than simply the size. Instead of being able to look at the size to determine the fee, one would actually have to parse every script and look for expensive op codes to determine the fee. To do this efficiently, one would need to do this at run-time just like Ethereum.
Bitcoin has an elegant solution to computing the cost of script validation, and DSV fundamentally alters that elegant solution.
Thank you to Clemens Ley and Craig Wright for discovering the hidden Turing completeness of Bitcoin and for motivating me to understand and apply it to this situation.
10 of 10 reviewers say it's worth paying for
0 of 10 reviewers say it's not worth paying for