From: "Johan Torås Halseth" <johanth@gmail•com>
To: Salvatore Ingala <salvatore.ingala@gmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Tue, 30 May 2023 09:34:09 +0200 [thread overview]
Message-ID: <CAD3i26DRFXMVp3HQ77V6g9aLktoeXekUNF4kzC6MOURtf3UEVw@mail.gmail.com> (raw)
In-Reply-To: <CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com>
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 − but I am only moderately confident as
> this is beyond the level of sophistication I've been exploring so far.
On Sun, May 28, 2023 at 12:24 PM 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 == 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 − but I am only moderately confident as
> 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
prev parent reply other threads:[~2023-05-30 7:34 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-08 9:17 Salvatore Ingala
2022-11-08 12:01 ` ZmnSCPxj
2022-11-10 9:42 ` Salvatore Ingala
2022-11-08 23:34 ` Bram Cohen
2022-11-09 12:07 ` Peter Todd
2022-11-10 7:39 ` David A. Harding
2022-11-11 21:49 ` Antoine Riard
2022-11-12 15:04 ` Salvatore Ingala
2022-11-30 19:42 ` Rijndael
2022-11-30 22:09 ` Rijndael
2022-12-01 8:47 ` Salvatore Ingala
2022-12-13 6:59 ` Billy Tetrud
2023-04-28 8:48 ` Johan Torås Halseth
2023-05-01 13:11 ` Salvatore Ingala
2023-05-01 21:15 ` Salvatore Ingala
2023-05-04 8:34 ` Johan Torås Halseth
2023-05-05 21:18 ` Salvatore Ingala
2023-05-26 11:45 ` Johan Torås Halseth
2023-05-28 10:24 ` Salvatore Ingala
2023-05-30 7:34 ` Johan Torås Halseth [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAD3i26DRFXMVp3HQ77V6g9aLktoeXekUNF4kzC6MOURtf3UEVw@mail.gmail.com \
--to=johanth@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=salvatore.ingala@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox