Date: Sun, 15 Oct 2023 15:15:49 +0000
To: Robin Linus <robin@zerosync.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <0J6o-j9oKRfD8-D3VURz4e1Ke8-DD3YhHQu4QvElrwd84meA1yvTs9KdQaTatpAfgXAPLfGn78MxitDT1AF76UE4yy53Ym6rOyy0B-4ey5k=@protonmail.com>
In-Reply-To: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
References: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] BitVM: Compute Anything on Bitcoin
Precedence: list

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 pr=
over 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 provid=
e `b` such that `B =3D b * G`.
If the prover wants to instead assert that this bit is 1, it has to provide=
 `b + p` such that `B =3D b * G` and `P =3D p * G`.
If `b` (and therefore `B`) is chosen uniformly at random, if it makes exact=
ly one of these assertions (that the bit is 0, or that the bit is 1) then i=
t 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` a=
nd 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 u=
se MuSig to combine them.
For example, suppose we have a NAND gate with inputs I, J and output K.
We have:

* `P[I=3D0]` and `V[I=3D0]`, which are the public keys to use if input I is=
 0.
* `P[I=3D1]` and `V[I=3D1]`, 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=3D0], V[I=3D0])` etc.
For a SCRIPT to check what the value of `I` is, we would have something lik=
e:

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

We would duplicate the above (with appropriate `OP_TOALTSTACK` and `OP_FROM=
ALTSTACK`) 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=3D1],=
 V[I=3D1])` the prover can only complete the signature by revealing the `b =
+ p` for `I`.
Similar for `MuSig(P[I=3D0], V[I=3D0])`, the verifier provides adaptor sign=
atures 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 commi=
tments 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-res=
ponse phase, instead of requiring a preimage from the verifier.

The internal public key that hides the Taproot tree containing the above lo=
gic gate commitments could be `MuSig(P, V)` so that the verifier can stop a=
nd 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`, t=
he 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 =3D ~(I & J)` and provide *only* the adaptor sig=
nature for `MuSig(P[K=3D<result>], V[K=3D<result>])`, but not the other sid=
e.

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 v=
alue 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`, dep=
ending on whether `K` is 0 or 1.

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

Regards,
ZmnSCPxj