OP_CAT Enables Scalar Multiplication for EC Points

cat_ecc.md

OP_CAT Enables Scalar Multiplication for EC Points

CAT can reduce curve point scalar multiplication to a subtraction in the scalar field.

Subtraction of field elements can probably be emulated in less than 250 (?) opcodes. For now, let's assume we had an (emulated) opcode, op_scalar_sub, for subtracting two elements of the scalar field of secp256k1.

Given secp's generator G, we want to compute for some scalar r the point R = rG

That is possible by hacking it into a Schnorr signature (R,s) for the key P = xG = 1G = G

The Script performs the following steps:

1. Verify the signature (R,s) for the committed key P = G. That's possible with op_checksig.
2. Get the sighash M onto the stack using the Schnorr+CAT trick (requires a second signature)
3. Compute c = Hash(R | P | M) using op_cat, op_sha256
4. Compute r' = s - c using op_scalar_sub
   • this works because s = r + c * x, and x = 1
5. Verify r == r'

This proves that R is r * G, which is as good as computing the scalar multiplication ourselves. However, unfortunately, this works only for scalar multiplications with the generator point G. Still, that's useful.