We present a novel and efficient method for computing point addition and scalar multiplication on elliptic curve, within bitcoin Script. For point addition, we reduce a script size of more than 1MB to ~400 bytes.
Addition
For each i, each point Pi is represented by two coordinates (xi, yi). To compute P3 = P1 + P2, we use the following formula:
If P1 != P2,
Otherwise,
A naive implementation requires calculating modular multiplicative inverse, applying the extended Euclidean algorithm. However, this leads to excessive Script size, since the exact number of loops in the algorithm is not known in advance and a large conservative upper bound has to be used.
Efficient Solution
Instead of directly calculating point addition, we turn the issue on the head by passing the expected point P3 in the unlocking script. We only verify P3 = P1 + P2 in Script. To avoid modular multiplicative inverse in the verification, we transform the formula into the following equivalent form.
Same as P3, λ is also precomputed off chain and passed in the unlocking script, as shown below. This results in extremely compact Script size, only ~400B.
Multiplication
x * P = (x0 + x1 * 2 + x2 * 4 + x3 * 8 + … + x255 * 2²⁵⁵) * P
= x0 * P + x1 * (2P) + x2 * (4P) + x3 * (8P) + … + x255 * (2²⁵⁵P)
x0, x1, x2, …, x255 are the bit representation of scalar x, from least significant bit to most. We precompute 2P, 4P, 8P, …, 2²⁵⁵P off chain and pass them in the unlocking script, which are verified in the locking script as shown below in Line 21–24.
Acknowledgements
This article is based on the work of Craig Wright and Owen Vaughan, with invaluable feedback from Enrique Larraia and Owen Vaughan of nChain.
