path: root/63/bc1926504a8078218c57fc908d0a4b46227131

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