diff options
| author | Russell O'Connor <roconnor@blockstream.com> | 2023-10-17 14:00:26 -0400 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-10-17 18:00:41 +0000 |
| commit | 42cb64b4614ede2b5c4628a390f8100acbc6c770 (patch) | |
| tree | 5425136aac5f17d0e75e46da8298157a7df1bf46 | |
| parent | 0eff08699d5f9328fead51a2055d197892a8d9a6 (diff) | |
| download | pi-bitcoindev-42cb64b4614ede2b5c4628a390f8100acbc6c770.tar.gz pi-bitcoindev-42cb64b4614ede2b5c4628a390f8100acbc6c770.zip | |
Re: [bitcoin-dev] BitVM: Compute Anything on Bitcoin
| -rw-r--r-- | 31/5bd80f0726e4a3e4ea6a1d958c4116790ab54a | 199 |
1 files changed, 199 insertions, 0 deletions
diff --git a/31/5bd80f0726e4a3e4ea6a1d958c4116790ab54a b/31/5bd80f0726e4a3e4ea6a1d958c4116790ab54a new file mode 100644 index 000000000..c1c474fab --- /dev/null +++ b/31/5bd80f0726e4a3e4ea6a1d958c4116790ab54a @@ -0,0 +1,199 @@ +Return-Path: <roconnor@blockstream.com> +Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 6E4E4C0032 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 17 Oct 2023 18:00:41 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp1.osuosl.org (Postfix) with ESMTP id 3D1FF82094 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 17 Oct 2023 18:00:41 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 3D1FF82094 +Authentication-Results: smtp1.osuosl.org; + dkim=pass (2048-bit key) header.d=blockstream-com.20230601.gappssmtp.com + header.i=@blockstream-com.20230601.gappssmtp.com header.a=rsa-sha256 + header.s=20230601 header.b=d6CH1gvG +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -1.899 +X-Spam-Level: +X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, + SPF_PASS=-0.001] autolearn=ham autolearn_force=no +Received: from smtp1.osuosl.org ([127.0.0.1]) + by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id xxHwFD7OcHHB + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 17 Oct 2023 18:00:39 +0000 (UTC) +Received: from mail-oa1-x35.google.com (mail-oa1-x35.google.com + [IPv6:2001:4860:4864:20::35]) + by smtp1.osuosl.org (Postfix) with ESMTPS id C407A8208A + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 17 Oct 2023 18:00:38 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org C407A8208A +Received: by mail-oa1-x35.google.com with SMTP id + 586e51a60fabf-1e9d3cc6e7aso2966849fac.2 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 17 Oct 2023 11:00:38 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=blockstream-com.20230601.gappssmtp.com; s=20230601; t=1697565637; + x=1698170437; darn=lists.linuxfoundation.org; + h=to:subject:message-id:date:from:in-reply-to:references:mime-version + :from:to:cc:subject:date:message-id:reply-to; + bh=KRR3LOZoPVpWV58o8dJgjZiIdgsq3e7Xp97TLYnwCaE=; + b=d6CH1gvGCljo42rSjY65ToloG2osLSfjHZBodw9atyU6R5+nCx8wOBwuVHBCoIGefk + 3jqVQAT8dd7JoN7iI2t9mbBZAtiqstamDRmnk4Y9UgTO4byd8dZCXqW3W62dEFxcQuAN + dBhK2Ik01s+p34+7at5EaeeAWhTl4xCxiQ9mp2fml1kK4OD/PB9K4cSx6KIUAjEsLQL+ + apJaBxs2OrIzKZ+l2NZxoitlaDo82yDaRNHzVQ4G+9c3ZoNBrZGMIDYnbAk7VyqZXChg + jfDgUAaF7UYMDZAomaUeVGWJPCx6WKUXQMpCk6B+B0e8Ua8xpCIsVL6sAt+22jXThyoQ + q91Q== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1697565637; x=1698170437; + h=to:subject:message-id:date:from:in-reply-to:references:mime-version + :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; + bh=KRR3LOZoPVpWV58o8dJgjZiIdgsq3e7Xp97TLYnwCaE=; + b=K/oYrQVuyrWcQleOjSpHk6r1xchrK74gobpfgMFRKSkBwy4v2od2855T5yQ8VQu/i6 + kpDKR5JgVTu2BhAV9enfpYdqtLtR5gOlbSTMRFeOxZvB8/FjOUNoEaCr1NuBGCUy70pk + z+noIbhc9aWhQ1GDH+jaEratH27BSSzwHQajhz/j72t2JOQTKNT5H7q2cPCvRcBY/z0f + ev/bnIGML0J/1954wALrfCkyKpPRZQwtFcFkF8zKlxiCZfvZvCeAU3ButAguwNSWzrRG + 0qASIei05zHcL9mn/X6rIxTMxv/Q4ogAbdDHsu+2B6Qpc6laznQhzaenzHoORX0l23Ql + 1QeA== +X-Gm-Message-State: AOJu0Yw1c0w4dFgYS8Nxy+nIB8EChqLeW4nmMptkTw7CPbfCNrsSW6+b + 0VQ935l4TYrJ9FOyYBrCgC91ZOMlDbzDr1aNpkWvn0ViXXBRPws5 +X-Google-Smtp-Source: AGHT+IELYiaKV16kp9cSh5kY/7XSPmJI+ekUxMRTEGcPeLBRPUSNOI/5ooZi2SekXeoZcMJmDUwf6WeEZULePAF8u6Q= +X-Received: by 2002:a05:6870:1017:b0:1e9:f73e:636c with SMTP id + 23-20020a056870101700b001e9f73e636cmr3036843oai.43.1697565637699; Tue, 17 Oct + 2023 11:00:37 -0700 (PDT) +MIME-Version: 1.0 +References: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org> +In-Reply-To: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org> +From: "Russell O'Connor" <roconnor@blockstream.com> +Date: Tue, 17 Oct 2023 14:00:26 -0400 +Message-ID: <CAMZUoKm56htx9Ux4D8CvgpQ+W_f1qw9HrkWBfkFPo699Esp--Q@mail.gmail.com> +To: Robin Linus <robin@zerosync.org>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="000000000000d17ff30607ed4c1c" +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Tue, 17 Oct 2023 18:00:41 -0000 + +--000000000000d17ff30607ed4c1c +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +While I haven't looked at the BitVM in detail, I would like to mention that +Simplicity's core language (excluding introspection primitives) has the +same expressivity as Boolean circuits. + +A few years ago I did some experiments to compile Simplicity expressions to +a system of polynomial constraints (R1CS). The experiments were +successful. For instance, I was able to compile our Sha256 compression +function specification written in Simplicity to a set of approximately +128,000 constraints. Under this "circuit" interpretation, Simplicity types +represent cables, which are a bundle of wires equal to the 'bit size' of +the given type. The 'case' combinator ends up being the only "active" +component (implementing a demux). The 'injr' and 'injr' combinators output +some fixed Boolean values. The rest of the combinations end up only +connecting, bundling and unbundling wires, and contribute no constraints at +all. + +While my previous experiment was generating constraints, it is clear to me +that a similar interpretation could instead generate logic gates, and I +would expect the same order of magnitude in the number of gates generated +as the number of constraints generated above. Thus Simplicity could be +used as a source of ready made expressions to generate useful circuits for +the BitVM, should someone be interested in pursuing this angle. + +On Mon, Oct 9, 2023 at 10:05=E2=80=AFAM Robin Linus via bitcoin-dev < +bitcoin-dev@lists.linuxfoundation.org> wrote: + +> Abstract. BitVM is a computing paradigm to express Turing-complete Bitcoi= +n +> contracts. This requires no changes to the network=E2=80=99s consensus ru= +les. +> Rather than executing computations on Bitcoin, they are merely verified, +> similarly to optimistic rollups. A prover makes a claim that a given +> function evaluates for some particular inputs to some specific output. If +> that claim is false, then the verifier can perform a succinct fraud proof +> and punish the prover. Using this mechanism, any computable function can = +be +> verified on Bitcoin. Committing to a large program in a Taproot address +> requires significant amounts of off-chain computation and communication, +> however the resulting on-chain footprint is minimal. As long as both +> parties collaborate, they can perform arbitrarily complex, stateful +> off-chain computation, without leaving any trace in the chain. On-chain +> execution is required only in case of a dispute. +> +> https://bitvm.org/bitvm.pdf +> _______________________________________________ +> bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> + +--000000000000d17ff30607ed4c1c +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr"><div>While I haven't looked at the BitVM in detail, I = +would like to mention that Simplicity's core language (excluding intros= +pection primitives) has the same expressivity as Boolean circuits.</div><di= +v><br></div><div>A few years ago I did some experiments to compile Simplici= +ty expressions to a system of polynomial constraints (R1CS).=C2=A0 The expe= +riments were successful. For instance, I was able to compile our Sha256 com= +pression function specification written in Simplicity to a set of approxima= +tely 128,000 constraints.=C2=A0 Under this "circuit" interpretati= +on, Simplicity types represent cables, which are a bundle of wires equal to= + the 'bit size' of the given type. The 'case' combinator en= +ds up being the only "active" component (implementing a demux).= +=C2=A0 The 'injr' and 'injr' combinators output some fixed = +Boolean values. The rest of the combinations end up only connecting, bundli= +ng and unbundling wires, and contribute no constraints at all.</div><div><b= +r></div><div>While my previous experiment was generating constraints, it is= + clear to me that a similar interpretation could instead generate logic gat= +es, and I would expect the same order of magnitude in the number of gates g= +enerated as the number of constraints generated above.=C2=A0 Thus Simplicit= +y could be used as a source of ready made expressions to generate useful ci= +rcuits for the BitVM, should someone be interested in pursuing this angle.<= +br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gma= +il_attr">On Mon, Oct 9, 2023 at 10:05=E2=80=AFAM Robin Linus via bitcoin-de= +v <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@= +lists.linuxfoundation.org</a>> wrote:<br></div><blockquote class=3D"gmai= +l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20= +4,204);padding-left:1ex">Abstract. BitVM is a computing paradigm to express= + Turing-complete Bitcoin contracts. This requires no changes to the network= +=E2=80=99s consensus rules. Rather than executing computations on Bitcoin, = +they are merely verified, similarly to optimistic rollups. A prover makes a= + claim that a given function evaluates for some particular inputs to some s= +pecific output. If that claim is false, then the verifier can perform a suc= +cinct fraud proof and punish the prover. Using this mechanism, any computab= +le function can be verified on Bitcoin. Committing to a large program in a = +Taproot address requires significant amounts of off-chain computation and c= +ommunication, however the resulting on-chain footprint is minimal. As long = +as both parties collaborate, they can perform arbitrarily complex, stateful= + off-chain computation, without leaving any trace in the chain. On-chain ex= +ecution is required only in case of a dispute.<br> +<br> +<a href=3D"https://bitvm.org/bitvm.pdf" rel=3D"noreferrer" target=3D"_blank= +">https://bitvm.org/bitvm.pdf</a><br> +_______________________________________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= +bitcoin-dev@lists.linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= +man/listinfo/bitcoin-dev</a><br> +</blockquote></div> + +--000000000000d17ff30607ed4c1c-- + |