<blockquote>
<p>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.</p>
</blockquote>
<p>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 <em>want</em> to use that for anything but experimentation.</p>
<p>If your goal is practical SNARK verification in Bitcoin script, perhaps you should work on a proposal to actually add SNARK verification opcodes instead?</p>
<blockquote>
<p>Is anyone working on a BIP to provide OP_MUL or OP_MUL64?</p>
</blockquote>
<p>Not as far as I know. Of course, you are free to do so yourself.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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 <em>in isolation</em> 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.</p>
<p>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.</p>

CC BY-SA 4.0
2023-11-24T13:39:35.317Z
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)
Carter Feldman
CC BY-SA 4.0
2023-11-24T14:24:44.760Z
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
;)
Carter Feldman
CC BY-SA 4.0
2023-10-25T17:39:00.113Z
2023-10-25T17:39:00.113Z
Pieter Wuille
<p>I am trying to write a script that can verify a SNARK, but from what I understand <code>OP_MUL</code> is still disabled in TapScript.</p>
<p>Is anyone working on a BIP to provide <code>OP_MUL</code> or <code>OP_MUL64</code>?</p>
<p>It seems incomprehensible to an outsider why these opcodes were disabled and never fixed after the <code>OP_LSHIFT</code> exploit, (it is trivial to write an <code>OP_MUL</code> opcode without introducing a vulnerability, one could even formally verify the implementation), leaving us with ridiculously inefficient solutions like BitVM or trying to do <code>bigint</code> multiplication by via bit vector multiplication in the stack--- but maybe I am missing something.</p>
<p>Some notes on why this is possible:</p>
<ol>
<li>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.</li>
<li>With regards to efficiency: Fast <strong>recursive</strong> 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.</li>
<li>Curve Ops, ModExp, can it be done?
Yes, not only can it be done, it has been done. <a href="https://gist.github.com/cf/98e0ea0602bc7d304d5c8b9f90325179" rel="nofollow noreferrer">here are all the bn256 ops we need for groth16</a> implemented using only op codes supported in the original implementation of bitcoin:</li>
</ol>
<ul>
<li>OP_ROLL</li>
<li>OP_8</li>
<li>OP_PICK</li>
<li><strong>OP_MOD (Disabled on Bitcoin)</strong></li>
<li>OP_ROT</li>
<li>OP_OVER</li>
<li>OP_2</li>
<li><strong>OP_MUL (Disabled on Bitcoin)</strong></li>
<li>OP_9</li>
<li>OP_7</li>
<li>OP_3</li>
<li>OP_4</li>
<li>OP_11</li>
<li>OP_NIP</li>
<li>OP_6</li>
<li>OP_SUB</li>
<li>OP_0</li>
<li>OP_EQUAL</li>
<li>OP_DROP</li>
<li>OP_DUP</li>
<li>OP_SWAP</li>
<li>OP_BOOLAND</li>
<li>OP_ADD</li>
<li>OP_2DUP</li>
<li>OP_IF</li>
<li>OP_2DROP</li>
<li>OP_ENDIF</li>
<li>OP_NOT</li>
<li>OP_13</li>
<li>OP_15</li>
<li>OP_16</li>
<li>OP_14</li>
<li>OP_12</li>
<li>OP_10</li>
<li>OP_TOALTSTACK</li>
<li>OP_FROMALTSTACK</li>
</ul>

<script><development><taproot><math><zero-knowledge>
Verifying a zkSNARK on Bitcoin/Hope for a future with OP_MUL
Carter Feldman
# Verifying a zkSNARK on Bitcoin/Hope for a future with OP_MUL

(Asked by: username_0 on 2023-10-25)

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](https://gist.github.com/cf/98e0ea0602bc7d304d5c8b9f90325179) 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

**Tags:** script, development, taproot, math, zero-knowledge


---

## 1 answers

### Answer by username_1 on 2023-10-25. Score: 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.

> **Comments:**
> **username_0**: 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)  
> **username_0**: 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 ;)  

---

