public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Salvatore Ingala <salvatore.ingala@gmail•com>
To: "Johan Torås Halseth" <johanth@gmail•com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
Date: Sun, 28 May 2023 12:24:14 +0200	[thread overview]
Message-ID: <CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com> (raw)
In-Reply-To: <CAD3i26DMGj=KRfi=gqHPdCZ_WyUAvWV50g7TcH4n2e3xSCx8Lg@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 3551 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 3962 bytes --]

  reply	other threads:[~2023-05-28 10:24 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 [this message]
2023-05-30  7:34                           ` Johan Torås Halseth

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=CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com \
    --to=salvatore.ingala@gmail$(echo .)com \
    --cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
    --cc=johanth@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