1

I am trying to write a script that can verify a SNARK, but from what I understand OP_MUL is still disabled in TapScript.

Is anyone working on a BIP to provide OP_MUL or OP_MUL64?

It seems incomprehensible to an outsider why these opcodes were disabled and never fixed after the OP_LSHIFT exploit, (it is trivial to write an OP_MUL opcode without introducing a vulnerability, one could even formally verify the implementation), leaving us with ridiculously inefficient solutions like BitVM or trying to do bigint multiplication by via bit vector multiplication in the stack--- but maybe I am missing something.

Some notes on why this is possible:

  1. You do not need loops/branches for zero knowledge proofs, we have succinct proof systems (such as groth16) that only require 3 pairings to be computed to verify a proof.
  2. With regards to efficiency: Fast recursive zero knowledge proofs now a reality, we can aggregate millions of proofs into one succinct proof without compromising security. If we have one inefficient transaction that verifies a aggregation proof of 10,000 proofs, for example, the cost/compute time per person is tiny.
  3. Curve Ops, ModExp, can it be done? Yes, not only can it be done, it has been done. here are all the bn256 ops we need for groth16 implemented using only op codes supported in the original implementation of bitcoin:
  • OP_ROLL
  • OP_8
  • OP_PICK
  • OP_MOD (Disabled on Bitcoin)
  • OP_ROT
  • OP_OVER
  • OP_2
  • OP_MUL (Disabled on Bitcoin)
  • OP_9
  • OP_7
  • OP_3
  • OP_4
  • OP_11
  • OP_NIP
  • OP_6
  • OP_SUB
  • OP_0
  • OP_EQUAL
  • OP_DROP
  • OP_DUP
  • OP_SWAP
  • OP_BOOLAND
  • OP_ADD
  • OP_2DUP
  • OP_IF
  • OP_2DROP
  • OP_ENDIF
  • OP_NOT
  • OP_13
  • OP_15
  • OP_16
  • OP_14
  • OP_12
  • OP_10
  • OP_TOALTSTACK
  • OP_FROMALTSTACK

1 Answer 1

2

I am trying to write a script that can verify a SNARK, but from what I understand OP_MUL is still is disabled in TapScript.

It appears completely infeasible to me to implement a SNARK verifier in Bitcoin Script, even if an OP_MUL were to exist. Without loops, elliptic curve operations, or even modular exponentiation, you'd be forced to completely unroll the computations to individual multiplications. I can't imagine that can realistically be done in Bitcoin Script without making the transaction exceed size limits. Even if it were somehow just doable, it'd be so ludicrously inefficient that I can't imagine you'd want to use that for anything but experimentation.

If your goal is practical SNARK verification in Bitcoin script, perhaps you should work on a proposal to actually add SNARK verification opcodes instead?

Is anyone working on a BIP to provide OP_MUL or OP_MUL64?

Not as far as I know. Of course, you are free to do so yourself.

It seems utterly understandable to an outsider why these opcodes were disabled and never fixed after the LSHFIT exploit (it is trivial to write a MUL op without introducing a vulnerability, could even formally verify the implementation), leaving us with ridiculously inefficient solutions like BitVM or trying to do bigint multiplication by via bit vector multiplication in the stack--- but maybe I am missing something.

I assume you mean it seems utterly incomprehensible? While I agree that there doesn't seem any real reason why safe versions of such opcodes couldn't exist, I suspect the answer is simply that such opcodes in isolation would not practically enable any new use cases, so there is little reason to go through the tremendous effort of building up community agreement for a consensus change like that.

Bitcoin Script today is practically useful for expressing spending conditions that are boolean functions over signature checking, hash preimage revelation, and timelock checks. Adding multiplication doesn't really change much about that.

2
  • Thanks for the response! I know may sound impractical at first, with OP_MUL and OP_MUL we actually can perform all of the bn256 operations required for computing the pairings of a groth16 proof (I revised my post above with a gist link)! Also, with regards to practicality you might imagine 1000 people aggregating their zero knowledge proofs via recursive verification and paying for a single bitcoin transaction (i.e it is not so impractical if the cost is split by a large number of interested parties) Nov 24, 2023 at 13:39
  • Actually don't need OP_MOD just OP_MUL: For A % B = C 1. Compute W=floor(A/B) and C off chain 2. Provide W and C in the Tx and check that A == W*B+C in place of OP_MUL and if the equality is true push C to the stack ;) Nov 24, 2023 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.