Instantly share code, notes, and snippets.

RobinLinus/cat_ecc.md

Last active June 12, 2024 17:58
Show Gist options
• 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.