From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2F53AC0032 for ; Sun, 15 Oct 2023 15:15:59 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 0209E40600 for ; Sun, 15 Oct 2023 15:15:59 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 0209E40600 Authentication-Results: smtp2.osuosl.org; dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com header.a=rsa-sha256 header.s=protonmail3 header.b=XLpP1DyE X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: 0.3 X-Spam-Level: X-Spam-Status: No, score=0.3 tagged_above=-999 required=5 tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H5=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EvbbNHi_oG56 for ; Sun, 15 Oct 2023 15:15:54 +0000 (UTC) X-Greylist: delayed 5981 seconds by postgrey-1.37 at util1.osuosl.org; Sun, 15 Oct 2023 15:15:54 UTC DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 9B115404ED Received: from mail-40138.protonmail.ch (mail-40138.protonmail.ch [185.70.40.138]) by smtp2.osuosl.org (Postfix) with ESMTPS id 9B115404ED for ; Sun, 15 Oct 2023 15:15:54 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1697382952; x=1697642152; bh=VHBiOH1+lOjF4TiMV9HD82rvv3LSxsQY3wBAJF0dLTM=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=XLpP1DyEk6URZ/y6eOMChlnJuh+IJtzkQRmz7cSpTjBFQhaiJ3BaSNf5G2yUhLr0n pwgymgLp4d7ODQ4cJ5ax4trP8QxRrF1jaQGhRomPW6n1syQ36k+h0kstedmnYPDrwh 0xsyGG3mna4VvDqIyHwLoc30qVOoC8b4W+p44QF8v4V4pT/FGW27Wvo0CBhm5/f2hb UEd7rZ+oZ+eDiAjlq+ppCeRMT8cLBGuybXg4rFan/4JfTyAjDAe4X10zOAWj5XXeHr 0R1EDnP3PwN6GvzA7rhtpzPPt0VLAOBqNi+lqJD395T6j6UbSrSpNcUgQuoIQwk0ea 4xl2vhnF1YJOw== Date: Sun, 15 Oct 2023 15:15:49 +0000 To: Robin Linus From: ZmnSCPxj Message-ID: <0J6o-j9oKRfD8-D3VURz4e1Ke8-DD3YhHQu4QvElrwd84meA1yvTs9KdQaTatpAfgXAPLfGn78MxitDT1AF76UE4yy53Ym6rOyy0B-4ey5k=@protonmail.com> In-Reply-To: References: 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 X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 15 Oct 2023 15:15:59 -0000 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 OP_CHECKSIG OP_IF OP_DROP <1> OP_ELSE 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], V[K=3D])`, 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