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

[Undescribed Horrific Abuse, One Victim & Survivor of Many]

On 10/15/23, ZmnSCPxj via bitcoin-dev
<bitcoin-...@lists.linuxfoundation.org> wrote:
> 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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-...@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>