path: root/d7/a3635d488fa9e8234149bdc9682dc85810ef75

Return-Path: <johanth@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 681A3C0036
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 May 2023 07:34:23 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 344E541887
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 May 2023 07:34:23 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 344E541887
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20221208 header.b=R5ZH8/Bj
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 smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id XXE2cuSXOXM6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 May 2023 07:34:21 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 971334187A
Received: from mail-yb1-xb30.google.com (mail-yb1-xb30.google.com
 [IPv6:2607:f8b0:4864:20::b30])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 971334187A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 May 2023 07:34:21 +0000 (UTC)
Received: by mail-yb1-xb30.google.com with SMTP id
 3f1490d57ef6-b9e6ec482b3so5738190276.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 30 May 2023 00:34:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20221208; t=1685432060; x=1688024060;
 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=CCpoQvdQ3m1AWx8XVIFEvZLic0R/wRLJfiYatMK7/vU=;
 b=R5ZH8/BjGGOUkbLHaidLRebiHl53E/P48FvFq+Eo4d9bBMRE7V2c/o65504I8CkZ+Q
 PoVlsFbKLqGg+QdyR01htTfklVzgZF2TUd9eHHKygQxdRyTBCW1YETYe+cY1XecD+qQf
 /fwRuV8hanHPw5Kq4HvhJYLedyxXGCdGJliv+8Z9JAzJ07shVSlo8hy54J5yB7ULfs83
 55QTATmE6dF2SImnTbscQytJfMiPTOBHseVtNPKyFdJ1Ay6xe0DUBN0tCFSWjQhP/XxO
 T5YjdDAKHzJSkG47yXS89WUdsNfKsHMbI4SsR36JGtsugw+Tb6JkmJ0vyXHjsEAkdxqM
 1CnQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20221208; t=1685432060; x=1688024060;
 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=CCpoQvdQ3m1AWx8XVIFEvZLic0R/wRLJfiYatMK7/vU=;
 b=dswhEkUt2O3UmCwaHQBy7nEvU0M3T6cTpo8EzIRo1Sce5bxviXe8fx+fE0fsfqDDPH
 9ffO0iiMBGpIjWHkJVDModuzFD99HVHpe3mcNqerYalB68iwiS5ZHrWrYNVUgZDELPEZ
 ex9H2ize24ydtapgs1zkd+C9oEzzV3TFBqcDCA1ONHNnC6L3zU8HOgLwPlEQXz1XsYy+
 TsjQ1MUySP7A2pFTjdS3UURJ/IfAq76h+G2TpDX7uvWEqdIaahlY6ut0aEcdzss7QJtN
 DMimff1+ClNO78iq6+DqMaqFIBma9Z3Ha2QWgyxj81xk5+onfaQAG6rkgqUxpVNrye/x
 4MwA==
X-Gm-Message-State: AC+VfDyNv8pYBbREaQ6d1CBUon8J3iVnBJ/3p5TAs9pLIMSLJmwvv2wq
 z+7FyAcMag05mNIdQcPhIWg7FeZnumJg56nb9aE=
X-Google-Smtp-Source: ACHHUZ5pLnseJ8T+OTmIfiJII5WzqKk9TjNjFLbGNux6wVYsGQNwdg9QodMdOR/L43xSTMikhceHfxR+T2fWAymE0oQ=
X-Received: by 2002:a25:786:0:b0:ba8:5e41:5b17 with SMTP id
 128-20020a250786000000b00ba85e415b17mr2019625ybh.21.1685432060322; Tue, 30
 May 2023 00:34:20 -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>
 <CAD3i26DMGj=KRfi=gqHPdCZ_WyUAvWV50g7TcH4n2e3xSCx8Lg@mail.gmail.com>
 <CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com>
In-Reply-To: <CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com>
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Tue, 30 May 2023 09:34:09 +0200
Message-ID: <CAD3i26DRFXMVp3HQ77V6g9aLktoeXekUNF4kzC6MOURtf3UEVw@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: Tue, 30 May 2023 08:42:28 +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: Tue, 30 May 2023 07:34:23 -0000

I should clarify: the current proposal already achieves the first part
needed for coin pools: removing some data from the merkle tree (I was
indeed referring to the embedded data, not the taptree).

The thing that is missing is removal of a public key from the taproot
internal key, but as mentioned I do agree that this is out of scope
for this proposal.

I believe you can get many of the benefits by falling back to "old
style multisig" in case someone exits the pool, by having a tap leaf
defining a multisig check amongst the remaining pubkeys.

Cheers,
Johan

> It seems likely that efficient use of the taproot internal pubkey with
> "dynamic key aggregation" is not possible with the current semantics
> (unless one ventures into the fraud proof machinery, which seems
> overkill!).
>
> However, in constructions with MATT opcodes, I would never expect the
> need for data to be stored in the taptree. In particular, for the case
> of CoinPools, the pubkeys of the members could also be stored in the
> embedded data, having a single "unilateral withdrawal" tapleaf.
> Removing a key would then amount to replacing it with a fixed NUMS key
> and computing the new root (re-using the same Merkle proof).
> Note that this is not a lot costlier than using a tapleaf per user:
> instead of paying the cost for the Merkle proof in the control block,
> you pay for it explicitly in the Script witness.
>
> Therefore, I would expect there to be reasonable CoinPools designs
> without additional opcodes =E2=88=92 but I am only moderately confident a=
s
> this is beyond the level of sophistication I've been exploring so far.


On Sun, May 28, 2023 at 12:24=E2=80=AFPM Salvatore Ingala
<salvatore.ingala@gmail.com> wrote:
>
> Hi Johan,
>
> Exciting to finally see some merkleization, which was only confined
> within the meme, up to this point!
>
> > 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).
>
> I think that's an excellent suggestion, which I was already exploring
> for a different purpose: bringing externally signed data onto the
> stack. My goal there was to allow eltoo-style replacement.
>
> Until recently, I thought that a clean/efficient version of eltoo
> would require OP_CHECKSIGFROMSTACK or ANYPREVOUT. However, extending
> OP_CHECKINPUTCONTRACTVERIFY to enable introspection of other inputs
> allows a reasonable workaround: producing a separate UTXO signed with
> ANYONECANPAY, with the required data embedded as usual. Spending that
> UTXO together with the channel's UTXO allows one to get that data
> on the stack (with its signature already checked by consensus rules).
> I drafted this idea in a gist [1].
>
> Remark: it still seems easier (and probably slightly more efficient)
> to build eltoo replacement with CSFS or APO in addition to MATT
> opcodes.
>
> A possible semantics for OP_CHECKINPUTCONTRACTVERIFY could then be
> exactly symmetrical to that of OP_CHECKOUTPUTCONTRACTVERIFY, with
> the exception that the special input index -1 would represent the
> current input.
>
> Pushing this further, another option that could be be worth exploring
> is to have a single OP_CHECK_IN_OUT_CONTRACT_VERIFY opcode, with the
> same semantics as OP_CHECKOUTPUTCONTRACTVERIFY from [2], but with an
> additional `flags` argument, which is a bitmap where:
> - the lowest-significant bit determines if the index refers to inputs
>   or outputs (where input index -1 refers to the current input)
> - the second bit specifies if amounts should be preserved with
>   deferred checks as described in [2] (only applicable to outputs)
> - other bits are OP_SUCCESS and reserved for future behaviors.
>
> This would make the opcodes 1-2 bytes larger, but might allow greater
> flexibility, and keep some room for future extensions.
>
> > 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.
>
> It seems likely that efficient use of the taproot internal pubkey with
> "dynamic key aggregation" is not possible with the current semantics
> (unless one ventures into the fraud proof machinery, which seems
> overkill!).
>
> However, in constructions with MATT opcodes, I would never expect the
> need for data to be stored in the taptree. In particular, for the case
> of CoinPools, the pubkeys of the members could also be stored in the
> embedded data, having a single "unilateral withdrawal" tapleaf.
> Removing a key would then amount to replacing it with a fixed NUMS key
> and computing the new root (re-using the same Merkle proof).
> Note that this is not a lot costlier than using a tapleaf per user:
> instead of paying the cost for the Merkle proof in the control block,
> you pay for it explicitly in the Script witness.
>
> Therefore, I would expect there to be reasonable CoinPools designs
> without additional opcodes =E2=88=92 but I am only moderately confident a=
s
> this is beyond the level of sophistication I've been exploring so far.
>
> Best,
> Salvatore
>
> [1] - https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63
> [2] - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/=
021588.html