Re: [bitcoin-dev] BitVM: Compute Anything on Bitcoin

[ZmnSCPxj <ZmnSCPxj@protonmail.com>]

Good morning Robin et al,

It strikes me that it may be possible to Scriptless Script BitVM, replacing hashes and preimages with points and scalars.

For example, equivocation of bit commitments could be done by having the prover put a slashable fund behind a pubkey `P` (which is a point).
This slashable fund could be a 2-of-2 between prover and verifier `P && V`.

Then the prover provides a bit-0 point commitment `B`, which is a point.
If the prover wants to assert that this specific bit is 0, it has to provide `b` such that `B = b * G`.
If the prover wants to instead assert that this bit is 1, it has to provide `b + p` such that `B = b * G` and `P = p * G`.
If `b` (and therefore `B`) is chosen uniformly at random, if it makes exactly one of these assertions (that the bit is 0, or that the bit is 1) then it does not reveal `p`.
But if it equivocates and asserts both, it reveals `b` and `b + p` and the verifier can get the scalar `p`, which is also the private key behind `P` and thus can get the fund `P && V`.

To create a logic gate commitment, we have the prover and validator provide public keys for each input-possibility and each output-possibility, then use MuSig to combine them.
For example, suppose we have a NAND gate with inputs I, J and output K.
We have:

* `P[I=0]` and `V[I=0]`, which are the public keys to use if input I is 0.
* `P[I=1]` and `V[I=1]`, which are the public keys to use if input I is 1.
* ...similar for input `J` and output `K`.

In the actual SCRIPT, we take `MuSig(P[I=0], V[I=0])` etc.
For a SCRIPT to check what the value of `I` is, we would have something like:

```
OP_DUP <MuSig(P[I=1], V[I=1])> OP_CHECKSIG
OP_IF
  OP_DROP
  <1>
OP_ELSE
  <MuSig(P[I=0], V[I=0])> OP_CHECKSIGVERIFY
  <0>
OP_ENDIF
```

We would duplicate the above (with appropriate `OP_TOALTSTACK` and `OP_FROMALTSTACK`) for input `J` and output `K`, similar to Fig.2 in the paper.

The verifier then provides adaptor signatures, so that for `MuSig(P[I=1], V[I=1])` the prover can only complete the signature by revealing the `b + p` for `I`.
Similar for `MuSig(P[I=0], V[I=0])`, the verifier provides adaptor signatures so that the prover can only complete the signature by revealing the `b` for `I`.
And so on.
Thus, the prover can only execute the SCRIPT by revealing the correct commitments for `I`, `J`, and `K`, and any equivocation would reveal `p` and let the verifier slash the fund of `P`.

Providing the adaptor signatures replaces the "unlock" of the challenge-response phase, instead of requiring a preimage from the verifier.

The internal public key that hides the Taproot tree containing the above logic gate commitments could be `MuSig(P, V)` so that the verifier can stop and just take the funds by a single signature once it has learned `p` due to the prover equivocating.

Not really sure if this is super helpful or not.
Hashes are definitely less CPU to compute.

For example, would it be possible to have the Tapleaves be *just* the wires between NAND gates instead of NAND gates themselves?
So to prove a NAND gate operation with inputs `I` and `J` and output `K`, the prover would provide bit commitments `B` for `B[I]`, `B[J]`, and `B[K]`, and each tapleaf would be just the bit commitment SCRIPT for `I`, `J`, and `K`.
The prover would have to provide `I` and `J`, and commit to those, and then verifier would compute `K = ~(I & J)` and provide *only* the adaptor signature for `MuSig(P[K=<result>], V[K=<result>])`, but not the other side.

In that case, it may be possible to just collapse it down to `MuSig(P, V)` and have the verifier provide individual adaptor signatures.
For example, the verifier can first challenge the prover to commit to the value of `I` by providing two adaptor signatures for `MuSig(P, V)`, one for the scalar behind `B[I]` and the other for the scalar behind `B[I] + P`.
The prover completes one or the other, then the verifier moves on to `B[J]` and `B[J] + P`.
The prover completes one or the other, then the verifier now knows `I` and `J` and can compute the supposed output `K`, and provides only the adaptor signature for `MuSig(P, V)` for the scalar behind `B[K]` or `B[K] + P`, depending on whether `K` is 0 or 1.

That way, you only really actually need Schnorr signatures without having to use Tapleaves at all.
This would make BitVM completely invisible on the blockchain, even in a unilateral case where one of the prover or verifier stop responding.

Regards,
ZmnSCPxj