Skip to content

Instantly share code, notes, and snippets.

@RobinLinus
Last active September 3, 2024 22:05
Show Gist options
  • Save RobinLinus/8890ded496c9c12796dc6a65c196a147 to your computer and use it in GitHub Desktop.
Save RobinLinus/8890ded496c9c12796dc6a65c196a147 to your computer and use it in GitHub Desktop.
OP_CAT Enables Scalar Multiplication for EC Points

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment