diff options
| author | Johan Torås Halseth <johanth@gmail.com> | 2023-05-26 13:45:17 +0200 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-05-26 11:45:32 +0000 |
| commit | b11c3a1774b2ea212a9846076d9c5892c12fbd7b (patch) | |
| tree | c3a4b779267c3776a48e3f94dc3fc915801a4893 | |
| parent | d251f821a82d7b1be0c97813c5bfc2f60d5906c6 (diff) | |
| download | pi-bitcoindev-b11c3a1774b2ea212a9846076d9c5892c12fbd7b.tar.gz pi-bitcoindev-b11c3a1774b2ea212a9846076d9c5892c12fbd7b.zip | |
Re: [bitcoin-dev] Merkleize All The Things
| -rw-r--r-- | 63/bc1926504a8078218c57fc908d0a4b46227131 | 240 |
1 files changed, 240 insertions, 0 deletions
diff --git a/63/bc1926504a8078218c57fc908d0a4b46227131 b/63/bc1926504a8078218c57fc908d0a4b46227131 new file mode 100644 index 000000000..977ff2906 --- /dev/null +++ b/63/bc1926504a8078218c57fc908d0a4b46227131 @@ -0,0 +1,240 @@ +Return-Path: <johanth@gmail.com> +Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 868BCC002A + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 26 May 2023 11:45:32 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp3.osuosl.org (Postfix) with ESMTP id 6236A61459 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 26 May 2023 11:45:32 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6236A61459 +Authentication-Results: smtp3.osuosl.org; + dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com + header.a=rsa-sha256 header.s=20221208 header.b=qmiUkEnM +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.099 +X-Spam-Level: +X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, + RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] + autolearn=ham autolearn_force=no +Received: from smtp3.osuosl.org ([127.0.0.1]) + by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id YK32HX5V_C23 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 26 May 2023 11:45:31 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.8.0 +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 2849F613E7 +Received: from mail-yw1-x112a.google.com (mail-yw1-x112a.google.com + [IPv6:2607:f8b0:4864:20::112a]) + by smtp3.osuosl.org (Postfix) with ESMTPS id 2849F613E7 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 26 May 2023 11:45:31 +0000 (UTC) +Received: by mail-yw1-x112a.google.com with SMTP id + 00721157ae682-55db055b412so24283337b3.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 26 May 2023 04:45:31 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20221208; t=1685101530; x=1687693530; + h=content-transfer-encoding:cc:to:subject:message-id:date:from + :in-reply-to:references:mime-version:from:to:cc:subject:date + :message-id:reply-to; + bh=ngGs1QFyTFvtO22pjs+e8Btbt9oiep1i7TPIttouGXk=; + b=qmiUkEnM/KjA2oqYlTbWm934vaOyWKFCdQxYaurfjyghyMQdzAuBhVCaAdWqjfLMON + ojInWdMP/5qJHeur9btpvjnnVt0wyn6mdNXmji+5WeCtXoejzj4++K/ZrvIZ53DWp7d3 + ewcGbSadfemzeYv0sLLZaD3gvA05UgceEpZXp/fmU4+r1TmkhQHnZlYlj7My4argMeAS + jeDS0X9h7Le7uJNxQg9GxYmiX9oLm8oApisBxVI0GM2we4NAeJqoShIvaiJRkCVE5Q8N + ybg31/1Ikc+pmkEDTZzd3YW0/ClrdDT95bdNhc7DZT9OLs8iECuu1+HV2ZL9c5yEC4X7 + rwRA== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20221208; t=1685101530; x=1687693530; + h=content-transfer-encoding:cc: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=ngGs1QFyTFvtO22pjs+e8Btbt9oiep1i7TPIttouGXk=; + b=RQEvJ7r6DAQEC7FnbbqdrPBfYqa4W/FbL/F592tuGLCf9G66I9K+SYxr5Cxm1zOuyi + X0gEn/08gl1D/ee2uvHBj1hD3C5owgnHQCSUhG8brQx96c2R9NJkz5fkROZy8d/DV0km + 85cLownEt+Urfwc+Kj4N0yH1G8EvhEGYHBQarCvLJLxpxkzGIHZjNeOQV3SxUiKmugjo + rBWaqUZG18ONME/7eI97NYLl+KKtkOsn59qKJlm3McnB6AN4awnmYEXIdTK5r7AZsnQ+ + 9yHTCahlQNrJHoGsMMQ+ceLCYYLWUe9aoEGf6iksr49xGEwAZ13mhFZya1b/lyza2F9B + egcg== +X-Gm-Message-State: AC+VfDwGet4uTZax2hqW6YUc1ZkGpg9N1WVSsbHNMO0LOhR+EYgsg3Ef + k0vtJ1zAZJl30kElf73T4P3DN3D6tmslZ+6Jxb+T2fh6Y5vyqTNs +X-Google-Smtp-Source: ACHHUZ5uJwksKuYrkP5eDxY1FRvcD1TJQkeOQFCjFnpNoizWy1mcgTbZvCrD/Vdtc8LBrZnX6B8kJ3++U0fBva6YrD4= +X-Received: by 2002:a81:4e92:0:b0:561:b246:77df with SMTP id + c140-20020a814e92000000b00561b24677dfmr1347909ywb.16.1685101529761; Fri, 26 + May 2023 04:45:29 -0700 (PDT) +MIME-Version: 1.0 +References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com> + <CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com> + <CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com> + <0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com> + <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com> + <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com> + <CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com> + <CAD3i26AXZKDCH3odhCjpMwzOTGQKSFqH9S+5N9UXNTb7CJHONA@mail.gmail.com> + <CAMhCMoFgto3Bu5+yEoqn1Jf8fNd+EQK-t_H3TKR2=3RXe8FdcQ@mail.gmail.com> + <CAMhCMoGdZsDO2eZYMf+G36gc5=-SB0HxHXbRSPx5OaCOjo5_Dw@mail.gmail.com> + <CAD3i26BoasDQGg1VOxaHJzoXXKnYKuBdXOq+wVZ=QhKbycobPA@mail.gmail.com> + <CAMhCMoH-MSfTeG6vnWPdG9bAxWXRatWQY8wUmOqM5mAyH=5n9Q@mail.gmail.com> +In-Reply-To: <CAMhCMoH-MSfTeG6vnWPdG9bAxWXRatWQY8wUmOqM5mAyH=5n9Q@mail.gmail.com> +From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com> +Date: Fri, 26 May 2023 13:45:17 +0200 +Message-ID: <CAD3i26DMGj=KRfi=gqHPdCZ_WyUAvWV50g7TcH4n2e3xSCx8Lg@mail.gmail.com> +To: Salvatore Ingala <salvatore.ingala@gmail.com> +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable +X-Mailman-Approved-At: Fri, 26 May 2023 15:27:10 +0000 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Subject: Re: [bitcoin-dev] Merkleize All The Things +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: Fri, 26 May 2023 11:45:32 -0000 + +Hi, Salvatore. + +As a further exploration of this idea, I implemented a +proof-of-concept of OP_CICV and OP_COCV in btcd[1] that together with +OP_CAT enables a set of interesting use cases. + +One such use case is, as mentioned earlier, CoinPools[2]. The opcodes +let you easily check the "dynamically committed data" of an input you +are spending, and enforce a new commitment on the output. The idea is +to have the set of participants in the pool, and their balances, be +the UTXOs committed data, and use this to validate the legitimacy of +a transaction, determining whether it permits a peer to exit with a +portion of the pooled funds. + +Doing what you suggested above, having the input and output commit to +a merkle tree of participants and balances, we are able to quite +elegantly verify the coin pool exit clause. Here is a working example +of how that could look like: [3]. Obviously this lacks a lot before it +is a working CoinPool implementation, but it demonstrates how +OP_C[I/O]V introduces "memory" to Bitcoin script. + +Having done this exercise, I have a few suggestions on how one could +further extend the proposal: + +1. In the current proposal for OP_CHECKOUTPUTCONTRACTVERIFY, the +opcodes check whether the output key Q is key X tweaked with data D +and taproot T: Q =3D=3D tweak(tweak(X,D), T). + +OP_CHECKINPUTCONTRACTVERIFY on the other hand, works on the input +internal key, and does not care about the taptree on the input: P =3D=3D +tweak(X,D), where Q =3D tweak(P, T). In most cases this is probably good +enough, since you are already executing the current script and that +way know the spender has provided the correct taproot. + +However, in the coin pool script mentioned above, I found that I +wanted to re-use the same taproot for the output (recursively). I +believe this would be a quite common use case. To solve this I +committed the taproot as part of the data itself: D' =3D hash(T+D), +which was then verified by OP_CICV. If you are aware of more efficient +alternatives, I am eager to hear them. + +A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical: +Have OP_CICV take an optional taproot and do the same check as is done +for the output: Q =3D=3D tweak(tweak(X,D), T). + +2.To make fully functioning CoinPools, one would need functionality +similar to OP_MERKLESUB[4]: remove some data from the merkle tree, and +remove a key from the aggregated internal key.This suggestion may +surpass the intended scope of this proposal, and would likely +necessitate the availability of multiple EC operations to accommodate +various key schemes. If we had opcodes for adding and removing keys +from the internal key this would be even more powerful. + +I look forward to hearing your thoughts on these suggestions and +further exploring the possibilities of the proposal! + +Cheers, +Johan + +[1] https://github.com/halseth/btcd/pull/1/commits/90a4065bdcd8029fe3325514= +a250490cba66fddd +[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/01796= +4.html +[3] https://github.com/halseth/tapsim/tree/matt-demo/examples/matt/coinpool +[4] https://github.com/ariard/bips/blob/coinpool-bips/bip-merklesub.mediawi= +ki + + +On Fri, May 5, 2023 at 11:18=E2=80=AFPM Salvatore Ingala +<salvatore.ingala@gmail.com> wrote: +> +> On Thu, 4 May 2023 at 10:34, Johan Tor=C3=A5s Halseth <johanth@gmail.com>= + wrote: +> > +> > It sounds like we can generalize the description of the construct to: +> > Access to (the hash of) embedded data of inputs and outputs, and the +> > enforcement of output keys and (static) taptrees. In other words, as +> > long as you can dynamically compute the output embedded data in +> > Script, you can enforce more or less anything (since you can make the +> > output script enforce presenting a witness "satisfying" the embedded +> > data). +> > +> > Does that sound about right? +> +> Yes. Fraud proofs allow us to extend beyond what Script can do (with the +> necessary tradeoffs), but there is plenty that can be done without them. +> +> +> > For instance, I believe you could simulate coin pools pretty easily: +> > Commit to the set of pubkeys and amounts owned by the participants in +> > the pool, and an output taptree where each participant has their own +> > spending path. Now, to exit the pool unilaterally, the participant +> > must present a proof that their pubkey+amount is committed to in the +> > input and an output where it is no longer committed. +> +> I don't think one would want to have a tapleaf for each participant: +> that would make you pay log n hashes just to reveal the tapleaf, and +> then you still need to pay log n hashes to access the embedded data. +> +> Instead, the "unilateral withdrawal Script" can be the same for all the +> participants. The witness would be the Merkle proof, plus perhaps some +> additional information to identify the leaf in the tree (depending on +> how the Merkle tree is implemented). In a complete Merkle tree for +> N =3D 2^n participants, the witness could contain the n hashes that allow +> to prove the value of the leaf, plus n bits to identify the path to the +> leaf (0/1 for 'left/right" child), since Script doesn't have enough +> opcodes to extract the bits from the leaf index. +> +> The data in the leaf can contain a commitment to all the information +> relevant for that participant (e.g.: their balance and pubkey, in a +> CoinPool construction). +> +> Then, the same witness can easily be reused to compute the new Merkle +> root after the data in the leaf is modified (for example, setting the +> amount to 0 for one participant). +> +> +> > A question that arises is how one would efficiently (in Script) prove +> > the inclusion/exclusion of the data in the commitment. One could +> > naively hash all the data twice during script execution (once for the +> > input, once for the output), but that is costly. It would be natural +> > to show merkle tree inclusion/exclusion in script, but perhaps there +> > are more efficient ways to prove it? +> +> A Merkle tree as described above commits to an entire vector that you +> can index positionally. That's quite versatile, and easier to handle +> than more complex constructions like accumulators with exclusion proofs. +> +> A Merkle proof for 2^7 =3D 128 participants requires about 8 hashes, so +> around 250 bytes in total of witness size; 2^10 =3D 1024 should bring tha= +t +> to the ballpark of 350 bytes. +> +> Best, +> Salvatore Ingala + |