Emulating curve point scalar multiplication with OP_CAT

Protocol Design
2

Copypasta:

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.

I don’t think that works though? If I want to falsely claim that r*G = X, then I create a valid signature using s*G = x + H(X,G,m)*1, then I make up a random value z that differs from m, calculate c = Hash(X,G,z), and r = s-c and tell you that r*G = X. Without some way of verifying that the z I give you matches the tx msg hash used by the CHECKSIG operation, I don’t think your procedure gives you any way to tell you that I’m lying? On the other hand, it doesn’t give me a way of choosing the value of z, so perhaps that’s good enough in some situations?

If you had CSFS you could force m=z directly; if you had both CTV and APO and they had a common tx msg hash function between them, you could use that to indirectly force m=z (m DUP CTV DROP checks m is correct and leaves m on the stack).

(If you’re introducing a new secp256k1-specific 256 bit opcode op_secp256k1_scalar_sub anyway, I don’t see why you wouldn’t just introduce an secp256k1_mul opcode directly, though)