Re: [bitcoin-dev] Proposed BIP for MuSig2 Descriptors

[Salvatore Ingala via bitcoin-dev]

Hi Andrew,

Thank you for putting this together; these standards will be of great
help for implementations.

The only concern I have is about the utility of supporting KEY
expressions inside musig to contain ranged derivations with `/*`.

Consider a wallet described as follows:

  musig(key1/<0;1>/*, key2/<0;1>/*, ..., keyN/<0;1>/*)

With such a setup, for each input being spent, each signer is required
to derive the child xpub for each key, and then execute the KeyAgg
algorithm [1] (which includes N scalar multiplications).

Instead, a policy like:

  musig(key1, key2, ..., keyN)/<0;1>/*

is more succinct, and KeyAgg is executed only once for all the inputs.
I think the performance impact is substantial for signing devices.

Therefore, unless there are known use cases, I would suggest keeping
the standard minimal and supporting only the second form, avoiding
both the performance overhead and the additional complexity when
writing descriptor parsers.

If, on the contrary, there are legitimate use cases, a discussion
about them (and the above mentioned tradeoffs) might be worth adding
to the BIP proposal.

Best,
Salvatore


[1] - BIP-327 MuSig2: https://github.com/bitcoin/bips/blob/master/bip-0327
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Concrete MATT opcodes

[Salvatore Ingala via bitcoin-dev]

Hi Antoine,

Thanks for your comments and insights.

On Mon, 14 Aug 2023 at 05:01, Antoine Riard  wrote:

> I think cross-input inspection (not cross-input signature
> aggregation which is different) is opening a pandora box in terms of
> "malicious" off-chain contracts than one could design. E.g miners bribing
> contracts to censor the confirmation of time-sensitive lightning channel
> transactions, where the bribes are paid on the hashrate distribution of
> miners during the previous difficulty period, thanks to the coinbase pubkey.
>

At this time, my goal is to facilitate maximum experimentation; it's safe
to open Pandora's box in a sandbox, as that's the only way to know if it's
empty.
Concerns will of course need to be answered when a soft-fork proposal is
made, and restrictions can be added if necessary.

Cross-input introspection seems very likely to have use cases; for example,
I drafted some notes on how it could be used to implement eltoo-style
replacement for lightning (or arbitrary state channels) when combined with
ANYONECANPAY:
 https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63
.
Although, it would be much easier with CCV+CHECKSIGFROMSTACK, and in that
case cross-input introspection is not needed.

Similarly, some people raised concerns with recursivity of covenant
opcodes; that also could be artificially limited in CCV if desired, but it
would prevent some use cases.

I have some thoughts on why the fear of covenants might generally be
unjustified, which I hope to write in long form at some point.

More than a binary flag like a matrix could be introduced to encode subset
> of introspected inputs /outputs to enable sighash_group-like semantic:
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019243.html
>

The flags alter the semantic behavior of the opcode; perhaps you rather
refer to generalizing the index parameter so that it can refer to a group
of inputs/outputs, instead?
I'm not aware of the use cases at this time, feel free to expand further.


> Or even beyond a matrix, it could be a set of "tags". There could be a
> generalized tag for unstructured data, and another one for bitcoin
> transaction / script data types (e.g scriptpubkey, amount, nsequence,
> merkle branch) that could be fetched from the taproot annex.
>

How would these "tags" interact with CHECKCONTRACTVERIFY? I don't quite
understand the use case.

I think this generic framework is interesting for joinpool / coinpool /
> payment pool, as you can check that any withdrawal output can be committed
> as part of the input scriptpubkey, and spend it on
> blessed-with-one-participant-sig script. There is still a big open question
> if it's efficient in terms of witness space consumed.
>

More generic introspection might not fit well within the semantics of CCV,
but it could (and probably should) be added with separate opcodes.

That said, I still think you would need at least ANYPREVOUT and more
> malleability for the amount transfer validation as laid out above.
>

I personally find OP_CHECKSIGFROMSTACK more natural when thinking about
constructions with CCV; but most likely either would work here.

Looking on the `DeferredCheck` framework commit, one obvious low-level
> concern is the DoS risk for full-nodes participating in transaction-relay,
> and that maybe policy rules should be introduced to keep the worst-CPU
> input in the ranges of current transaction spend allowed to propagate on
> the network today.
>

Of course, care needs to be taken in general when designing new deferred
checks, to avoid any sort of quadratic validation cost.
The DeferredChecks added specifically for CCV has negligible cost, as it's
just O(n_outputs + n_ccv_out) where n_ccv_out is the number of executed
OP_CHECKCONTRACTVERIFY opcodes (transaction-wide) that check the output
amount.

Best,
Salvatore
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Concrete MATT opcodes

[Salvatore Ingala via bitcoin-dev]

Hi Johan,

Thanks a lot for the comments, and the independent implementation!

> - For the opcode parameter ordering, it feels unnatural for the two
> tweaks (data, taptree) to be separated by the internal key. A more
> natural ordering of parameters IMO would be (of course this is all
> subjective):
>  OP_CCV.
>
> If you disagree, I would love some rationale for the ordering you
> chose! (looks like you also changed it again after your last post?).

The main concern for the reordering was to put  at the bottom,
as that's typically passed via the witness stack.

I put the  right next, as I suspect there are use cases for
specifying via the witness what is the input index where a certain
(CCV-encumbered) UTXO is to be found, or which output should funds
be sent to, instead of hard-coding this in the script. This might
help in designing contracts that are more flexible in the way they
are spent, for example by allowing batching their transactions.

Instead, I expect the other parameters to almost always be hardcoded,
or propagated from the current input with the <-1> special values.

I agree that your ordering is more aesthetically pleasing, though.

> I'm wondering what other use cases you had in mind for the deferred
> output amount check? Maybe I have missed something, but if not it
> would perhaps be better to leave out the amount preservation check, or
> go the extra mile and propose a more powerful amount introspection
> machinery.

Yes, the deferred output amount check is not enough for coinpools;
however, it comes at no cost if we have a  parameter anyway,
as OP_2 (value for CCV_IGNORE_OUTPUT_AMOUNT) is a single byte opcode.

The intent of preserving amounts for many-to-one contracts (vaults),
or the one-to-one cases (channels, any 2-party contract, etc.) seems
common enough to deserve 1 bit in the flags, IMHO.
Efforts to define and add explicit introspection to cover your
(exciting!) use cases can proceed independently, but I don't think
they would nullify the advantages of this (optional) feature of CCV.

Best,
Salvatore
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Concrete MATT opcodes

[Salvatore Ingala via bitcoin-dev]

Hi Dave,

I apologize for the confusion and the inconsistent use of plurals.
The reason I called it a "complete proposal" is that the opcode is
now functionally complete, unlike the previous attempt where the
approach for the output amount introspection was not yet specified.

The semantics are informally defined in the previous e-mail, and
implemented in the code [1], which is the only formal specification
at this time. I believe the code is now fairly stable and ready to
experiment with.
My own and (hopefully) others' experimentation will help in writing
a more informed BIP proposal in the next few months.

About the plurals: OP_CHECKCONTRACTVERIFY is indeed now a single
opcode that is useful on its own, but I will also be maintaining a
separate branch [2] that contains both OP_CHECKCONTRACTVERIFY and
OP_CAT, which enables the full generality of the MATT proposal.

Best,
Salvatore

[1] -
https://github.com/bitcoin-inquisition/bitcoin/compare/24.0...Merkleize:bitcoin:checkcontractverify
[2] - https://github.com/Merkleize/bitcoin/tree/matt
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[bitcoin-dev] Concrete MATT opcodes

[Salvatore Ingala via bitcoin-dev]

Hi all,

I have put together a first complete proposal for the core opcodes of
MATT [1][2].
The changes make the opcode functionally complete, and the
implementation is revised and improved.

The code is implemented in the following fork of the
bitcoin-inquisition repo:

https://github.com/Merkleize/bitcoin/tree/checkcontractverify

Therefore, it also includes OP_CHECKTEMPLATEVERIFY, as in a
previous early demo for vaults [3].

Please check out the diff [4] if you are interested in the
implementation details. It includes some basic functional tests for
the main cases of the opcode.

## Changes vs the previous draft

These are the changes compared to the initial incomplete proposal:
- OP_CHECK{IN,OUT}CONTRACTVERIFY are replaced by a single opcode
  OP_CHECKCONTRACTVERIFY (CCV). An additional `flags` parameter allows
  to specify if the opcode operates on an input or an output.
  This also allows inspection of other inputs, that was not possible
  with the original opcodes.
- For outputs, the default behavior is to have the following deferred
  checks mechanism for amounts: all the inputs that have a CCV towards
  the same output, have their input amounts summed, and that act as a
  lower bound for that output's amount.
  A flag can disable this behavior. [*]
- A number of special values of the parameters were defined in order
  to optimize for common cases, and add some implicit introspection.
- The order of parameters is modified (particularly,  is at the
  bottom of the arguments, as so is more natural when writing Scripts).

## Semantics

The new OP_CHECKCONTRACTVERIFY takes 5 parameters from the stack:

  , , , , 

The core logic of the opcode is as follows:

"Check if the -th input/output's scriptPubKey is a P2TR
whose public key is obtained from , (optionally) tweaked with
, (optionally) tap-tweaked with ".

The following are special values of the parameters:

- if  is empty, it is replaced with a fixed NUMS point. [**]
- if  is -1, it is replaced with the current input's taproot
  internal key.
- if  is -1, it is replaced with the current input's index.
- if  is empty, the data tweak is skipped.
- if  is empty, the taptweak is skipped.
- if  is -1, it is replaced with the current input's root
  of the taproot merkle tree.

There are two defined flags:
- CCV_FLAG_CHECK_INPUT = 1: if present,  refers to an input;
  otherwise, it refers to an output.
- CCV_FLAG_IGNORE_OUTPUT_AMOUNT = 2: only defined when _CHECK_INPUT
  is absent, it disables the deferred checks logic for amounts.

Finally, if both the flags CCV_FLAG_CHECK_INPUT and
CCV_FLAG_IGNORE_OUTPUT_AMOUNT are absent:
  - Add the current input's amount to the -th output's bucket.

After the evaluation of all inputs, it is verified that each output's
amount is greater than or equal to the total amount in the bucket
if that output (validation of the deferred checks).

## Comment

It is unclear if all the special values above will be useful in
applications; however, as each special case requires very little added
code, I tried to make the specs as flexible as possible at this time.

With this new opcode, the full generality of MATT (including the fraud
proofs) can be obtained with just two opcodes: OP_CHECKCONTRACTVERIFY
and OP_CAT.
However, additional opcodes (and additional introspection) would
surely benefit some applications.

I look forward to your comments, and to start drafting a BIP proposal.

Best,
Salvatore Ingala


[*] - Credits go to James O'Beirne for this approach, taken from his
  OP_VAULT proposal. I cherry-picked the commit containing the
  Deferred Checks framework.
[**] - The same NUMS point suggested in BIP-0341 was used.


References:

[1] - https://merkle.fun/
[2] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html
[3] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html
[4] -
https://github.com/bitcoin-inquisition/bitcoin/compare/24.0...Merkleize:bitcoin:checkcontractverify
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

On Thu, 4 May 2023 at 10:34, Johan Torås Halseth  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 = 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 = 128 participants requires about 8 hashes, so
around 250 bytes in total of witness size; 2^10 = 1024 should bring that
to the ballpark of 350 bytes.

Best,
Salvatore Ingala
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Vaults in the MATT framework

[Salvatore Ingala via bitcoin-dev]

Hi Michael,

I can't make any claim of expertise on the field (especially on the
other proposals that you mentioned), so this post necessarily includes
my opinions − and possibly my biases.

The core functionality of MATT is quite simple, and could be adapted
to any version of the scripting system: basically, COCV allows to
"embed" some data in the next output, and decide its script; CICV
allows "reading" this data.
The design I proposed on taproot is surely not the only possible way,
but it's the most simple/elegant I could come up with. Moreover, it
doesn't seem very useful to spend time trying to get it to work on
pre-taproot Script, due to the obvious advantages of those ideas when
deployed on taproot (like having taptrees, and all the nice properties
of Schnorr signatures).

CICV/COCV can certainly be considered an additional form of
introspection: you're checking that the script of an input/output
equals a certain value, which is not possible in today's Script.
I think that's generally true for all covenant proposals.

Unlike some other proposals, MATT is not yet fully formalized, so I
generally call "MATT" the combination of CICV+COCV, plus some other
small set of opcodes that is yet to be defined exactly. I would say it
fits in the same family as APO/OP_CTV/OP_VAULT, per your bucketization.

The previous posts about MATT, fraud proofs, etc. are an exploration of
the deeper things that are enabled by the MATT opcodes. The claim is
that a set of changes that is (arguably) quite small and easy to analyze
is enough to express general smart contracts − thanks to fraud proofs.
However, fraud proofs themselves are a quite advanced application of
the new opcodes, and are not needed for most/all of the things that
people are trying to build today with the other covenant proposals.


Since you mention Simplicity: my current understanding is that its
endeavour of replacing Script with a better language is orthogonal to
the discussion about what features (e.g.: introspection, covenants)
should be in the language.

All the covenant proposals listed above are technically a lot smaller
and easier to audit than both the SegWit and the Taproot soft forks,
both in terms of code and conceptual complexity.

Therefore, if we _do_ want the features that they enable, the required
engineering for a soft-fork is relatively straightforward, and there is
not much of a reason to wait for Simplicity. It will be trivial to "port"
any
constructions we might create today with covenants to Simplicity scripts.

If we _do not_ want those features, then the decision would rather be
guided by other considerations, like potential risks to bitcoin caused
by the effect of those features on miners' incentives. These
concerns are not answered by Simplicity, as far as I understand:
you would then want to implement Simplicity _without_ those features.

Best,
Salvatore

On Mon, 1 May 2023 at 16:18, Michael Folkson 
wrote:

> Hi Salvatore
>
> Can you clarify for me which bucket this proposal sits? We have APO, CTV,
> OP_VAULT etc that are proposals to add additional functionality to SegWit
> version 1, Tapleaf version 0 scripts. We have Simplicity that would need a
> new Tapleaf version (e.g. Tapleaf version 1). And then there are CISA like
> proposals that would need a new SegWit version (e.g. SegWit version 2). It
> looks to me like your proposal is in the first bucket (same as APO, CTV
> etc) as it is just introducing new opcode functionality to existing script
> with no deeper introspection needed but previous and current discussion of
> fraud proofs, MATT frameworks etc made me initially think it was going to
> require more than that.
>
> Thanks
> Michael
>
> --
> Michael Folkson
> Email: michaelfolkson at protonmail.com
> GPG: A2CF5D71603C92010659818D2A75D601B23FEE0F
>
> Learn about Bitcoin: https://www.youtube.com/@portofbitcoin
>
> --- Original Message ---
> On Monday, April 24th, 2023 at 20:37, Salvatore Ingala via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Hello list,
>
> TL;DR: the core opcodes of MATT can build vaults with a very similar design
> to OP_VAULT. Code example here:
>
>
> https://github.com/bitcoin-inquisition/bitcoin/compare/24.0...bigspider:bitcoin-inquisition:matt-vault
>
>
> In my previous emails about the MATT proposal for smart contracts in
> bitcoin [1], I mostly focused on proving its generality; that is, it
> allows arbitrary smart contracts thanks to fraud proofs.
>
> While I still find this "completeness" result compelling, I spent more time
> thinking about the framework itself; the construction is not very
> interesting
> if it turns simple things into complicated ones. Luckily, this is not the
> case.
> In particular, in this email we will not merkleize anything (other than
> taptr

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

Hi all,

I apologize for a couple of oversights in my last e-mail.

The first is that m_B can't be committed as-is in the contract's
embedded data, with the current semantics of OP_COCV, which
only allows 32-byte values. A solution could be to store its
hash SHA256(m_B), instead.

(I didn't test the Scripts, so there could be other bugs − hopefully the
general idea is clear, anyway)

On Mon, 1 May 2023 at 15:11, Salvatore Ingala 
wrote:

> If the internal_pubkey is a musig-aggregated key of Alice and Bob,
> the game can be settled entirely offline after the first transaction.
> Simply, Bob communicates his move to Alice, Alice reveals her move to
> Bob, and they can settle the bet. The game would be played without
> any script being executed, therefore all transactions could look like
> any other P2TR, with the only possible fingerprinting being due to the
> input amounts.
>

This is incomplete: Alice can't trust Bob by revealing her move, as
he could then cheat on-chain and play a different move.

The fix should be straightforward, after adding the requirement that the
internal pubkey of [S1] is a musig2 of both players.
After Bob reveals his move (say, Rock), Alice will only agree to continue
the game off-chain if Bob pre-signs transactions for the state [S1] (where
m_B = Paper, and m_B = Scissors) that send all the money to Alice.
This guarantees that a cheating Bob is punished.

Best,
Salvatore Ingala
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

 in practice than
I initially thought.

If the internal_pubkey is a musig-aggregated key of Alice and Bob,
the game can be settled entirely offline after the first transaction.
Simply, Bob communicates his move to Alice, Alice reveals her move to
Bob, and they can settle the bet. The game would be played without
any script being executed, therefore all transactions could look like
any other P2TR, with the only possible fingerprinting being due to the
input amounts.

It should be possible to generalize the protocol so that many rounds
can be played off-chain within the same UTXO, but I didn't try to
figure out the details.

Best,
Salvatore Ingala


[1] - https://en.wikipedia.org/wiki/Rock_paper_scissors
[2] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html

On Fri, 28 Apr 2023 at 10:48, Johan Torås Halseth  wrote:

> Hi, Salvatore.
>
> I find this proposal very interesting. Especially since you seemingly
> can achieve such powerful capabilities by such simple opcodes.
>
> I'm still trying to grok how this would look like on-chain (forget
> about the off-chain part for now), if we were to play out such a
> computation.
>
> Let's say you have a simple game like "one player tic-tac-toe" with
> only two tiles: [ _ | _ ]. The player wins if he can get two in a row
> (pretty easy game tbh).
>
> Could you give a complete example how you would encode one such state
> transition (going from [ X, _ ] -> [ X, X ] for instance) in Bitcoin
> script?
>
> Feel free to choose a different game or program if you prefer :)
>
> Thanks!
> Johan
>
>
>
> On Tue, Dec 13, 2022 at 2:08 PM Billy Tetrud via bitcoin-dev
>  wrote:
> >
> > Re Verkle trees, that's a very interesting construction that would be
> super useful as a tool for something like Utreexo. A potentially
> substantial downside is that it seems the cryptography used to get those
> nice properties of Verkle trees isn't quantum safe. While a lot of things
> in Bitcoin seems to be going down the path of quantum-unsafe (I'm looking
> at you, taproot), there are still a lot of people who think quantum safety
> is important in a lot of contexts.
> >
> > On Thu, Dec 1, 2022 at 5:52 AM Salvatore Ingala via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> >>
> >> Hello Rijndael,
> >>
> >>
> >>
> >> On Wed, 30 Nov 2022 at 23:09, Rijndael 
> wrote:
> >>>
> >>> Hello Salvatore,
> >>>
> >>> I found my answer re-reading your original post:
> >>> > During the arbitration phase (say at the i-th leaf node of M_T), any
> party can win the challenge by providing correct values for tr_i = (st_i,
> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
> values, and Script can verify that indeed the state moves from st_i to
> st_{i + 1} by executing op_i. The challenge is over.
> >>
> >> You are correct, the computation step encoded in a leaf needs to be
> simple enough for Script to verify it.
> >>
> >> For the academic purpose of proving completeness (that is, any
> computation can be successfully "proved" by the availability of the
> corresponding fraud proof), one can imagine reducing the computation all
> the way down to a circuit, where each step (leaf) is as simple as what can
> be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
> >>
> >> In practice, you would want to utilize Script to its fullest, so for
> example you wouldn't compile a SHA256 computation to something else – you'd
> rather use OP_SHA256 directly.
> >>
> >>>
> >>> That raises leads to a different question: Alice initially posts a
> commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees
> with `y` so starts the challenge protocol. Is there a commitment to `f`? In
> other words, the dispute protocol (as I read it) finds the leftmost step in
> Alice and Bob's execution traces that differ, and then rewards the coins to
> the participant who's "after-value" is computed by the step's operation
> applied to the "before value". But if the participants each present valid
> steps but with different operations, who wins? In other words, Alice could
> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
> Those steps don't match, but both are valid. Is there something to ensure
> that before the challenge protocol starts, that the execution trace that
> Alice posts is for the right computation and not a different computation
> that yields a favorable result for her (and for which she can generate a
> valid merkle tree)?
> >>
> >>
> >> The 

[bitcoin-dev] Vaults in the MATT framework

[Salvatore Ingala via bitcoin-dev]

Hello list,

TL;DR: the core opcodes of MATT can build vaults with a very similar design
to OP_VAULT. Code example here:


https://github.com/bitcoin-inquisition/bitcoin/compare/24.0...bigspider:bitcoin-inquisition:matt-vault


In my previous emails about the MATT proposal for smart contracts in
bitcoin [1], I mostly focused on proving its generality; that is, it
allows arbitrary smart contracts thanks to fraud proofs.

While I still find this "completeness" result compelling, I spent more time
thinking about the framework itself; the construction is not very
interesting
if it turns simple things into complicated ones. Luckily, this is not the
case.
In particular, in this email we will not merkleize anything (other than
taptrees).

This post describes some progress into formalizing the semantics of the core
opcodes, and demonstrates how they could be used to create vaults that seem
comparable to the ones built with OP_VAULT [2], despite using general
purpose
opcodes.

An implementation and some minimal tests matching the content of this
e-mail can be found in the link above, using the bitcoin-inquisition as the
base branch.

Note that the linked code is not well tested and is only intended for
exploratory and demonstrative purposes; therefore, bugs are likely at this
stage.


##
#PART 1: MATT's core
##

In this section, I will discuss plausible semantics for the core opcodes
for MATT.

The two core opcodes are defined below as OP_CHECKINPUTCONTRACTVERIFY and
OP_CHECKOUTPUTCONTRACTVERIFY.

(the initial posts named them OP_CHECK{INPUT,OUTPUT}COVENANTVERIFY)

They enhance Script with the following capabilities:
  - decide the taptree of the output
  - embed some (dynamically computed) data in the output
  - access the embedded data in the current UTXO (if any)

The opcodes below are incomplete, as they only control the output's Script
and
not the amounts; more on that below.

Other than that, the semantics should be quite close to the "right" one for
the MATT framework.


### The opcodes

case OP_CHECKINPUTCONTRACTVERIFY:
{
// OP_CHECKINPUTCONTRACTVERIFY is only available in Tapscript
if (sigversion == SigVersion::BASE || sigversion ==
SigVersion::WITNESS_V0) return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
// (x d -- )
if (stack.size() < 2)
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
valtype& x = stacktop(-2);
valtype& d = stacktop(-1);
if (x.size() != 32 || d.size() != 32)
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
const XOnlyPubKey nakedXOnlyKey{Span{x.data(),
x.data() + 32}};
const uint256 data(d);
if (!execdata.m_internal_key.has_value())
return set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);  // TODO
// Verify that tweak(lift_x(x), d) equals the internal pubkey
if (!execdata.m_internal_key.value().CheckDoubleTweak(nakedXOnlyKey,
, nullptr))
return set_error(serror, SCRIPT_ERR_WRONGCONTRACTDATA);
popstack(stack);
popstack(stack);
}
break;
case OP_CHECKOUTPUTCONTRACTVERIFY:
{
// OP_CHECKOUTPUTCONTRACTVERIFY is only available in Tapscript
if (sigversion == SigVersion::BASE || sigversion ==
SigVersion::WITNESS_V0) return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
// (out_i x taptree d -- )
if (stack.size() < 4)
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
int out_i = CScriptNum(stacktop(-4), fRequireMinimal).getint();
valtype& x = stacktop(-3);
valtype& taptree = stacktop(-2);
valtype& d = stacktop(-1);
auto outps = checker.GetTxvOut();
// Return error if the evaluation context is unavailable
if (!outps)
return set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR); // TODO
if (x.size() != 32 || taptree.size() != 32 || (d.size() != 0 &&
d.size() != 32))
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
if (out_i < 0 || out_i >= (int)outps->size())
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
const XOnlyPubKey nakedXOnlyKey{Span{x.data(),
x.data() + 32}};
const uint256 data(d);
const uint256 *data_ptr = (d.size() == 0 ? nullptr : );
const uint256 merkle_tree(taptree);
CScript scriptPubKey = outps->at(out_i).scriptPubKey;
if (scriptPubKey.size() != 1 + 1 + 32 || scriptPubKey[0] != OP_1 ||
scriptPubKey[1] != 32)
return set_error(serror, SCRIPT_ERR_WRONGCONTRACTDATA);
const XOnlyPubKey outputXOnlyKey{Span{scriptPubKey.data() + 2, scriptPubKey.data() + 34}};
// Verify that taptweak(tweak(lift_x(x), d), taptree) equals the
internal pubkey
if (!outputXOnlyKey.CheckDoubleTweak(nakedXOnlyKey, data_ptr,
_tree))
return set_error(serror, SCRIPT_ERR_WRONGCONTRACTDATA);
popstack(stack);
popstack(stack);
popstack(stack);
popstack(stack);
}
break;

### Commentary

CheckDoubleTweak function (implemented in the branch) gets an x-only pubkey,
optionally some data, and 

Re: [bitcoin-dev] Wallet policies for descriptor wallets

[Salvatore Ingala via bitcoin-dev]

Hi Antoine,

Thanks for your very interesting suggestions!

On Mon, 23 Jan 2023 at 20:53, darosior  wrote:

> Actually you can save a few more characters, and gain some clarity, by 
> showing the "semantic policy" instead of the actual Miniscript. If the intent 
> is for the user to verify the semantic of the Bitcoin Script they are 
> importing, you can just drop all the type information.
> For instance, for a Miniscript representing the Miniscript policy "a 3-of-3 
> that becomes a 2-of-3 after 90 days" instead of showing:
>
> thresh(3,pk(Alice),s:pk(Bob),s:pk(Carol),sln:older(12960))
> You could show:
>
> thresh(3,pk(Alice),pk(Bob),pk(Carol),older(12960))
> For this specific example you'd save 8 (confusing) characters to be verified 
> on the signing device.
>
>
I thought about that, and I still consider it a possible future improvement
in UX. However, I wasn't comfortable deploying it in this way for the
following reason: if there is malware in your software wallet at policy
registration time, the malware could find a different miniscript with the
same semantic policy.
The result is now a mismatch between the wallet policy in the user's backup
and the one where funds are actually received. The user might see funds
mysteriously disappear, while the attacker would know the actual miniscript
policy, enabling ransom attacks.

The attack seems very unlikely today, and for many interesting semantic
policies, there are probably not many miniscript policies to sift through
in case of recovery.
However, I suspect it will become more realistic in a taproot world, where
the semantic policy of each tapleaf could have multiple options, resulting
in combinatorial explosion.
For example, if there are 2 options for the miniscript of each leaf, and n
leaves, you would have 2^n possible descriptors with the same semantic
policy.

One solution might be to explicitly enumerate (or at least upper-bound) the
number of possible descriptors that are lifted to the same policy, and use
the simplified UX if this number is not too large.
Having a set of standard recovery tools for those situations might make
this approach more viable in my opinion.

I wonder if signing devices could even go further and display a plain
english verification to the user, like "This policy contains 4
spending paths. Be ready to verify the 4 spending paths. The first
spending path is Alice, Bob and Carol signing together. The second
spending path is Bob and Carol signing together after 90 days. The
third spending path is Alice and Carol signing together after 90 days.
The third spending path is Alice and Bob signing together after 90
days."
> It seems feasible to be doable in a general manner from a Miniscript 
> "semantic policy".
>
> A lower-hanging fruit might be to find ways of registering
xpubs/identities on the device, so that one could replace xpubs with
"Alice" and "Bob".
Once that's done, that might be one of the possible approaches to simplify
the UX flow.
I suspect the design space to be quite large and I have not yet put enough
thought into it.

I guess it clashes with the user willing to check their backup against
the policy registered on the device. You could always have the
user-friendly policy check at first and have an option to show the raw
descriptor for them to be able to cross-check it with their backup.
>
> I'm assuming the user will do the minimum amount of work they are forced
to do, therefore I only consider this safe iff we address the
miniscript-combinatorial-explosion issues above.

PS: the numerous usage of the word "policy" is getting complex lol, is
it a Miniscript concrete policy, a Miniscript semantic policy, a
BIP-wallet-policies policy? :)
>
> ...yeah, we should have a policy against that!

Salvatore Ingala
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

Hello Rijndael,



On Wed, 30 Nov 2022 at 23:09, Rijndael  wrote:

> Hello Salvatore,
>
> I found my answer re-reading your original post:
> > During the arbitration phase (say at the i-th leaf node of M_T), any
> party can win the challenge by providing correct values for tr_i = (st_i,
> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
> values, and Script can verify that indeed the state moves from st_i to
> st_{i + 1} by executing op_i. The challenge is over.
>
You are correct, the computation step encoded in a leaf needs to be simple
enough for Script to verify it.

For the academic purpose of proving completeness (that is, any computation
can be successfully "proved" by the availability of the corresponding fraud
proof), one can imagine reducing the computation all the way down to a
circuit, where each step (leaf) is as simple as what can be checked with
{OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.

In practice, you would want to utilize Script to its fullest, so for
example you wouldn't compile a SHA256 computation to something else – you'd
rather use OP_SHA256 directly.


> That raises leads to a different question: Alice initially posts a
> commitment to an execution trace of `f(x) = y`, `x`, and `y`. Bob Disagrees
> with `y` so starts the challenge protocol. Is there a commitment to `f`? In
> other words, the dispute protocol (as I read it) finds the leftmost step in
> Alice and Bob's execution traces that differ, and then rewards the coins to
> the participant who's "after-value" is computed by the step's operation
> applied to the "before value". But if the participants each present valid
> steps but with different operations, who wins? In other words, Alice could
> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
> Those steps don't match, but both are valid. Is there something to ensure
> that before the challenge protocol starts, that the execution trace that
> Alice posts is for the right computation and not a different computation
> that yields a favorable result for her (and for which she can generate a
> valid merkle tree)?
>

The function f is already hard-coded in the contract itself, by means of
the tree of scripts − that already commits to the possible futures.
Therefore, once you are at state S14, you know that you are verifying the
6th step of the computation; and the operation in the 6th step of the
computation depends solely on f, not its inputs. In fact, you made me
realize that I could drop op_i from the i-th leaf commitment, and just
embed the information in the Script of that corresponding state.

Note that the states S0 to S14 of the 256x game are not _all_ the possible
states, but only the ones that occurred in that execution of the contract
(corresponding to a path from the root to the leaf of the Merkle tree of
the computation trace), and therefore the ones that materialized in a UTXO.
Different choices made by the parties (by providing different data, and
therefore choosing different branches) would lead to a different leaf, and
therefore to different (but in a certain sense "symmetric") states.



Since we are talking about the fact that f is committed to in the contract,
I'll take the chance to extend on this a bit with a fun construction on top.
It is well-known in the academic literature of state channels that you can
create contracts where even the function ("program", or "contract") is not
decided when the channel is created.

Since f is generic, we can choose f itself to be a universal Turing
machine. That is, we can imagine a function f(code, data) that executes a
program ("code") on the "data" given to it as input.
Since we can do fraud proofs on statements "f(code, data) == output", we
could build contracts where the "code" itself is chosen later.

For example, one could build a universal state channel, where parties can
enter any contract among themselves (e.g.: start playing a chess game)
entirely inside the channel. The state of this universal channel would
contain all the states of the individual contracts that are currently open
in the channel, and even starting/closing contracts can happen entirely
off-chain.

I believe these constructions are practical (the code of universal Turing
machines is not really complicated), so it might be worth exploring further
to figure out useful applications of this approach (supercharging
lightning?).

We should probably start by implementing testnet rock-paper-scissors in
MATT, though :)

Best,
Salvatore Ingala
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Wallet policies for descriptor wallets

[Salvatore Ingala via bitcoin-dev]

Hi list,

Following up on this topic, I now opened a pull request with the BIP
proposal:

 https://github.com/bitcoin/bips/pull/1389

I also attempted a proof-of-concept of how an integration of wallet
policies to HWI might look like:

 https://github.com/bitcoin-core/HWI/pull/647

which might help to provide context, and also serves as a demo of the
possible UX flows with hardware signers (as currently implemented in the
Ledger bitcoin app).

There are no substantial changes to the initial version proposed to the
list:
- some additional restrictions to the allowed descriptors were added as
further simplifications;
- added test vectors and observations on backwards compatibility;
- general improvements to the text.

I look forward to your comments and improvements.
Salvatore Ingala

On Thu, 5 May 2022 at 16:32, Salvatore Ingala 
wrote:

> In the implementation work to implement descriptors and miniscript support
> in hardware wallets [a][b], I encountered a number of challenges. Some of
> them are technical in nature (e.g. due to constraints of embedded
> development). Others are related to the attempts of shaping a good user
> experience; with bitcoin reaching more people who are not tech-savvy,
> self-custody is only as secure as what those newcomers can use easily
> enough.
>
> The main tool that I am using to address some of these challenges is a
> layer that sits _on top_ of descriptors/miniscript, while staying very
> close to it. Since there is nothing that is vendor-specific in the vast
> majority of the approach I'm currently using, I tried to distill it here
> for your comments, and will propose a BIP if this is deemed valuable.
>
> I called the language "wallet policies" (suggestions for a better name are
> welcome). I believe an approach based on wallet policies can benefit all
> hardware wallets (stateless or not) that want to securely support complex
> scripts; moreover, wallet policies are close enough to descriptors that
> their integration should be extremely easy for any software wallet that is
> currently using descriptors.
>
> [a]: https://blog.ledger.com/bitcoin-2 - early demo
> [b]: https://blog.ledger.com/miniscript-is-coming - miniscript example
>
>
> Salvatore Ingala
>
>
> ==
>
> This document starts with a discussion on the motivation for wallet
> policies, followed by their formal definition, and some recommendations for
> implementations.
>
> == Rationale ==
>
> Output script descriptors [1] were introduced in bitcoin-core as a way to
> represent collections of output scripts. It is a very general and flexible
> language, designed to catch all the possible use-cases of bitcoin wallets
> (that is, if you know the script and you have the necessary keys, it will
> be possible to sign transactions with bitcoin-core's descriptor-based
> wallets).
>
> Unfortunately, descriptors are not a perfect match for the typical usage
> of hardware wallets. Most hardware wallets have the following limitations
> compared to a general-purpose machine running bitcoin-core:
>
> - they are embedded devices with limited RAM and computational power;
> - they might not be able to import additional private keys (all the keys
> are generated from a single seed via [BIP-32](
> https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki));
> - they might not have permanent storage (*stateless* hardware wallet
> design).
>
> Moreover, other limitations like the limited size of the screen might
> affect what design choices are available in practice. Therefore, minimizing
> the size of the information shown on-screen is important for a good user
> experience.
>
> A more native, compact representation of the wallet receive/change would
> also benefit the UX of software wallets using descriptors to represent
> software wallets using descriptors/miniscript for multisignature or other
> complex locking conditions.
>
> === Security and UX concerns of scripts in hardware wallets ===
>
> For a hardware wallet, allowing the usage of complex scripts presents
> challenges in terms of both security and user experience.
>
>  Security issues 
>
> One of the security properties that hardware wallets strive to guarantee
> is the following: **as long as the user correctly verifies the information
> that is shown on the hardware wallet's screen before approving, no action
> can be performed without the user's consent**.
> This must hold even in scenarios where the attacker has full control of
> the machine that is connected to the hardware wallet, and can execute
> arbitrary requests or tamper with the legitimate user's requests.
>
> Therefore, it is not at all trivial to allow complex scripts, especially
> if they contain keys that belong to third parties.
> The hardware wallet must guarantee that the user knows precisely *what*
> "policy" is being used to spend the funds, and that the "unspent" funds (if
> any) will be protected by the same policy. This 

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

Hi Antoine,
It appears that my explanation of the relationship between the covenant and
the bisection protocol is still unclear; I'll do my best to clarify.

The bisection's Merkle tree never ends up on-chain, in any form. Therefore,
a bigger computation does not end up in a bigger witness size, which is key
to the scalability of the approach. Only in the case of a challenge, it
will result in a (logarithmically) longer chain of transactions to resolve
it. This chain of transactions could be mapped to a root-to-leaf path in
the Merkle tree of the computation trace.

The actual computation trace (and the corresponding Merkle tree) is only
computed by the parties when they execute the computation.
What's in the tapleaves is only the valid transitions at the current state
of the protocol; that is, the valid transitions in the Finite State Machine
(and possibly other valid exit conditions that remove the covenant
encumbrance, if any).

The bisection protocol only makes sense as a step in a larger protocol that
makes use of it.

Perhaps presenting the protocol in a less-than-general case might help to
understand it. So let's play a simpler game using a protocol that includes
a fraud proof.

Alice claims that she knows how to multiply by 256, while Bob doesn't
believe her. So they make a bet: they each commit 1 coin; then Bob choses a
number x; then Alice computes y = 256*x by doubling x eight times
(expensive multiplications were disabled in a tragic DDoS accident), and
publishes the result y. Bob independently computes 256 * x (he has a friend
who is a mathematician, he'll know how to do it). If the result is not y,
Bob will start a challenge; otherwise, Alice wins and takes the money.

(The example is of course artificial, as redoing the computation in Script
is cheaper than executing the fraud proof in this case!)

What follows is an actual execution of the protocol. In the following, each
[Si] is a UTXO corresponding to some possible FSM node, starting with the
S0, the UTXO with 1+1 = 2 coins. Each line with "-" is a possible
transition (script in the taptree), specifying what is the next FSM node
after the "==>" symbol; the encumbrance in the scripts enforce that the
state of the next UTXO is updated correctly (details omitted below), and
any other necessary conditions to ensure the integrity of the protocol.


=


[S0]: Initial UTXO
  - only Bob can spend, he must choose his number x ==> S1

[S1; state: x]:
  - only Alice can spend, she publishes her answer y ==> S2

[S2. state: x, y]:
  - after 1 day: Alice won, she can take the money // Happy case!
Usually that's the end
  - Bob disagrees with the answer, post z as his answer. ==> S3

The challenge starts here! Let's put some actual numbers. x = 2; y = 508; z
= 512.

This is what Alice computed:

  2 => 4 => 8 => 16 => 32 => 64 => 127 => 254 => 508

This is what Bob computed:

  2 => 4 => 8 => 16 => 32 => 64 => 128 => 256 => 512

At this time, we don't know who is right. They both built a tree that looks
like this (ASCII art only working in fixed-width font):

 ___H18___
/ \
   /   \
H14 H58
/ \ / \
   /   \   /   \
  / \ / \
H12 H34 H56 H78
/ \ / \ / \ / \
  H1  H2  H3  H4  H5  H6  H7  H8

Remember that each internal node commits to: the state of the computation
before the leftmost leaf in the subtree, the state after the rightmost
leaf, and the hash of sub-trace for the sub-tree. Each leaf just commits to
that intermediate computation step (and the operation, which here is always
"double the input"). For example, H4 commits to "16 => 32" according to
both Alice's and Bob's computation traces.

(From our privileged point of view, we can foresee that the earliest
disagreement is on the 6th step of the computation: "64 => 127" according
to Alice, "64 => 128" according to Bob).

Let's denote h_{A;18} (resp. h_{B;18}) all the information committed to in
the node H18, according to Alice (resp. Bob). Similarly for all the other
nodes.

[S3. state: x, y, z]: Challenge starts!
  - Alice posts the root of her computation trace h_{A;18} ==> S4

[S4. state: x, y, z, h_{A;18}]
  - Bob posts the root of her computation trace h_{B;18} ==> S5

Since they disagree, it must be the case that h_{A;18} != h_{B;18}.

[S5. state: x, y, z, h_{A;18}, h_{B;18}]
  - Alice opens the commitment h_{A;18}, by revealing H14 and H58
(according to her) ==> S6

Note that in this last transition (going to S6), the covenant enforces that
the child commitments are compatible: the transition is only valid if the
starting state of the computation according to h_{A;14} is compatible with
h_{A;18} (that is, it's equal to x); similarly the end state of the
computation in h_{A;58} must be y, and h_{A;18} can be recomputed from the
data provided (ensuring the integrity of the Merkle tree).
This is true for all the commitment openings 

Re: [bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

Hi ZmnSCPxj, Bram, Peter, David,

Thanks for all your comments; replies below.

On Tue, 8 Nov 2022 at 13:01, ZmnSCPxj  wrote:

> Modulo bugs, operator error, misconfigurations, and other irrationalities
> of humans.
>

I agree that making footguns impossible is a much more difficult problem to
solve!

Rather than get taptree from the stack, just use the same taptree as in the
> revelation of the P2TR.
> This removes the need to include quining and similar techniques: just do
> the quining in the SCRIPT interpreter.
>

That's a possibility; I suspect it would be less efficient for many
contracts (in particular, when the total number of states in the FSM is
relatively large, but each of them has only few valid transitions). We
could always allow both variants.

Another reason I preferred to present it in this way is to show that it is
possible to limit the design to covenants where recursion is not allowed /
limited; I don't personally think recursion is bad at this time − but the
covenants (and the protocol for fraud challenges) do not require it in
order to be useful.

Anyway, I suggested some opcodes only as a sketch. I'm not knowledgeable
enough to suggest the best design, and maybe it will be easier to compare
several variants once we implement something on top.


On Wed, 9 Nov 2022 at 00:34, Bram Cohen  wrote:

> Hash chained covenants in general all have about the same plateau of
> functionality, which seems roughly reasonable to add to Bitcoin as it is
> today but suffer from being limited and hence likely only a stepping stone
> to greater functionality and unless whatever's put in now cleanly extends
> to supporting more in the future it's likely to turn into a legacy
> appendage which has to be supported. So my generic suggestion for this sort
> of thing is that it should be proposed along with a plan for how it could
> be extended to support full-blown covenants in the future.
>

I actually struggle to find constructions that are _not_ possible using
such covenants; do you have any concrete example?
That would be very interesting in order to correctly classify the
expressive power of UTXO+Script+covenants when compared to the
"Turing-complete"+stateful models.

Another probably unhelpful bit of feedback I have is that Bitcoin should
> probably be taking verkle trees seriously because those can have
> substantially lower size/cost/weight than merkle trees. That doesn't just
> apply to this proposal, but to Bitcoin in general, which doesn't seem to
> have any serious verkle tree proposals to date.
>

I am not an expert in Verkle trees, but I think the efficiency gain (if
any) is not that interesting for many of the applications I'm suggesting,
as most Merkle trees would be quite small.
Therefore, I agree with Peter that the additional complexity might not be
worth it at this time; if applications requiring large Merkle trees arise
in practice, Verkle trees could always be added in the future as an
optimization.

Moreover, Verkle trees, or even any risky/fancy cryptography, could be used
in layer-2 solutions enabled by the covenant, without impacting any funds
not locked in the covenant in case of disasters.


On Wed, 9 Nov 2022 at 13:07, Peter Todd  wrote:

> Particularly since even having merkle trees in Bitcoin
> is arguably a mistake: they allow for degenerate, weak, security modes
> like SPV
> that aren't clearly good for Bitcoin as a whole.
>

I disagree, as the title of this thread suggests! :)
Thanks to Merkle trees, we'll be able to keep layer 1 extremely light, so
everyone can run a full node − while all the complexity of fancy
constructions is pushed to the application layer.


On Thu, 10 Nov 2022 at 08:39, David A. Harding  wrote:

> > 1. Alice posts the statement “f(x) = y”.
> > 2. After a challenge period, if no challenge occurs, Alice is free to
> > continue and unlock the funds; the statement is true.
> > 3. At any time before the challenge period expires, Bob can start a
> > challenge: “actually, f(x) = z”.
>
> That looks to me very similar to Gregory Maxwell's script from[1]
>

Zero-Knowledge contingent payments do indeed solve the problem more
elegantly in the specific case where swapping Alice's knowledge for x with
a payment from Bob is the entire smart contract.

The covenant adds the ability to carry over some sort of state. For
example, imagine Alice and Bob want to play a game of chess, and the winner
takes all the money [*]. The "state" in the covenant would be the entire
chessboard, and a valid transition is a valid chess move. The covenant
enforces that the game proceeds according to the rules, by only allowing
correct updates to the "state".
Moreover, the parties participating to a covenant don't necessarily need to
be decided in advance, which is crucial for constructions like coinpool [1].

Note that no this does not require any fraud proof, as the rules of chess
are simple enough that each "transition" is a simple enough function. In
fact, many contracts might not 

[bitcoin-dev] Merkleize All The Things

[Salvatore Ingala via bitcoin-dev]

Hi list,

I have been working on some notes to describe an approach that uses
covenants in order to enable general smart contracts in bitcoin. You can
find them here:

https://merkle.fun

The approach has a number of desirable features:

- small impact to layer 1;
- not application-specific, very general;
- it fits well into P2TR;
- it does not require new cryptographic assumptions, nor any construction
that has not withstood the test of time.

This content was presented at the BTCAzores unconference, where it received
the name of MATT − short for Merkleize All The Things.
In fact, no other cryptographic primitive is required, other than Merkle
trees.

I believe this construction gets close to answering the question of how
small a change on bitcoin's layer 1 would suffice to enable arbitrary smart
contracts.

It is not yet at the stage where a formal proposal can be made, therefore
the proposed specs are only for illustrative purposes.

The same content is reformatted below for the mailing list.

Looking forward to hearing about your comments and improvements.
Salvatore Ingala


==


# General smart contracts in bitcoin via covenants

Covenants are UTXOs that are encumbered with restrictions on the outputs of
the transaction spending the UTXO. More formally, we can define a covenant
any UTXO such that at least one of its spending conditions is valid only if
one or more of the outputs’ scriptPubKey satisfies certain restrictions.

Generally, covenant proposals also add some form of introspection (that is,
the ability for Script to access parts of the inputs/outputs, or the
blockchain history).

In this note, we want to explore the possibilities unleashed by the
addition of a covenant with the following properties:

- introspection limited to a single hash attached to the UTXO (the
“covenant data”), and input/output amounts;
- pre-commitment to every possible future script (but not their data);
- few simple opcodes operating with the covenant data.

We argue that such a simple covenant construction is enough to extend the
power of bitcoin’s layer 1 to become a universal settlement layer for
arbitrary computation.

Moreover, the covenant can elegantly fit within P2TR transactions, without
any substantial increase for the workload of bitcoin nodes.

A preliminary version of these notes was presented and discussed at the
BTCAzores Unconference [1], on 23rd September 2022.


# Preliminaries

We can think of a smart contract as a “program” that updates a certain
state according to predetermined rules (which typically include access
control by authorizing only certain public keys to perform certain
actions), and that can possibly lock/unlock some coins of the underlying
blockchain according to the same rules.

The exact definition will be highly dependent on the properties of the
underlying blockchain.

In bitcoin, the only state upon which all the nodes reach consensus is the
UTXO set; other blockchains might have other data structures as part of the
consensus, like a key-value store that can be updated as a side effect of
transaction execution.

In this section we explore the following concepts in order to set the
framework for a definition of smart contracts that fits the structure of
bitcoin:

- the contract’s state: the “memory” the smart contract operates on;
- state transitions: the rules to update the contract’s state;
- covenants: the technical means that can allow contracts to function in
the context of a bitcoin UTXO.

In the following, an on-chain smart contract is always represented as a
single UTXO that implicitly embeds the contract’s state and possibly
controls some coins that are “locked” in it. More generally, one could
think of smart contracts that are represented in a set of multiple UTXOs;
we leave the exploration of generalizations of the framework to future
research.

## State

Any interesting “state” of a smart contract can ultimately be encoded as a
list, where each element is either a bit, a fixed-size integers, or an
arbitrary byte string.

Whichever the choice, it does not really affect what kinds of computations
are expressible, as long as one is able to perform some basic computations
on those elements.

In the following, we will assume without loss of generality that
computations happen on a state which is a list of fixed length S = [s_1,
s_2, …, s_n], where each s_i is a byte string.

### Merkleized state

By constructing a Merkle tree that has the (hashes of) the elements of S in
the leaves, we can produce a short commitment h_S to the entire list S with
the following properties (that hold for a verifier that only knows h_S):

- a (log n)-sized proof can prove the value of an element s_i;
- a (log n + |x|)-sized proof can prove the new commitment h_S’, where S’
is a new list obtained by replacing the value of a certain leaf with x.

This allows to compactly commit to a RAM, and to prove correctness of RAM
updates.

In other words, a 

Re: [bitcoin-dev] Wallet policies for descriptor wallets

[Salvatore Ingala via bitcoin-dev]

Hi all,

TL;DR: It is easy to convert from wallet policy to descriptors and back;
imho aliases are better left out of descriptors in real world usage; some
more examples given.

I received some very useful feedback on the wallet policy proposal (in this
list and outside); that also led me to realize that my initial post lacked
some clarity and more practical examples.

This post wants to:
- clarify that extracting descriptors from the wallet policy is trivial;
- argue that figuring out the wallet policy (template and list of keys
information) from the descriptor is reasonably easy − automatable for sane
descriptors currently in use, and much more general ones as well;
- give an idea of what the information shown on a hardware wallet screen
would look like (emphasizing compactness);
- explain my point of view on "descriptors with aliases".

This gist demoes conversions from wallet policies to descriptors, and back:
https://gist.github.com/bigspider/10df51401be3aa6120217c03c2836ffa

Note that I would expect/hope software wallets to prefer working directly
with wallet policies − but it might help to have automated tools for the
conversion, for interoperability with tools that do not adopt wallet
policies.

(All the following examples use the `/**` notation as a shortcut for
`/<0,1>/*`; this notation might be dropped without consequences on the rest
of the proposal.)

All the keys in the example I'm proposing are followed by /**. It is
unclear to me if hardware wallets should allow *registration* of wallet
policies with static keys (that is, without any range operator), as that
would incentivize key reuse. The specs still support it as there might be
other use cases.

The policy for miniscript examples not using taproot was generated with the
online compiler: https://bitcoin.sipa.be/miniscript. Many examples are also
borrowed from there.
(To the best of my knowledge, there is no publicly released compiler for
miniscript on taproot, yet)

Note on aliases: it has been pointed out that many miniscript
implementations internally use aliases to refer to the keys. In my opinion,
aliases:
- should be external to the descriptor language, as they bear no
significance for the actual script(s) that the descriptor can produce
- fail to distinguish which part of the KEY expression is part of the
"wallet description", and which part is not

By clearly separating the key information in the vector (typically, an xpub
with key origin information) from the key placeholder expression (which
typically will have the `/**` or `/<0,1>/*` derivation step), wallet
policies semantically represent keys in a way that should be convenient to
both software wallets and hardware signers.

Associating recognizable names to the xpubs (and registering them on the
device) is a good idea for future developments and can greatly improve the
UX, both during wallet setup, or in recognizing outputs for repeated
payments; it should be easy to build this feature on top of wallet policies.

== Examples ==

All the examples show:
- Miniscript policy: semantic spending rules, and optimization hints (can
be compiled to miniscript automatically)
- Miniscript: the actual miniscript descriptor, compiles 1-to-1 to Bitcoin
Script
- Wallet template: the "wallet descriptor template"
- Vector of keys: the list of key information (with key origin information)

Together, the wallet template and the vector of keys are the complet
"wallet policy".

=== Example 1: Either of two keys (equally likely) ===

Miniscript policy: or(pk(key_0),pk(key_1))
Miniscript:
 
wsh(or_b([d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL/<0;1>/*),s:pk([12345678/44'/0'/0']xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB/<0;1>/*)))

Descriptor template:   wsh(or_b(pk(@0/**),s:pk(@1/**)))
Vector of keys: [

"[d34db33f/44'/0'/0']xpub6ERApfZwUNrhLCkDtcHTcxd75RbzS1ed54G1LkBUHQVHQKqhMkhgbmJbZRkrgZw4koxb5JaHWkY4ALHY2grBGRjaDMzQLcgJvLJuZZvRcEL",

"[12345678/44'/0'/0']xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB"
]

In all the following examples, I will replace the xpubs with aliases in the
miniscript for brevity, and omit the corresponding vector of keys in the
wallet policy.

Of course, in comparing the "information density" (especially for UX
purposes), it is important to take the full descriptor into account.
It is always to be assumed that the keys are xpubs, complete with key
origin information if internal (that is, controlled by the software or
hardware signer that the wallet policy is being with).

=== Example 2: Either of two keys, but one is more likely ===

Miniscript policy: or(99@pk(key_likely),pk(key_unlikely))
Miniscript:   wsh(or_d(pk(key_likely),pkh(key_unlikely)))

Descriptor template: wsh(or_d(pk(@0/**),pkh(@1/**)))
Vector of keys: 

=== Example 3: A 

Re: [bitcoin-dev] Wallet policies for descriptor wallets

[Salvatore Ingala via bitcoin-dev]

Hi Antoine and Billy,

Thank you for your comments and for looking into the proposal.

On Mon, 9 May 2022 at 12:36, darosior  wrote:

> 1. The `` optimization for the common usecase of using 2
> descriptors at different derivation indices
>for receive and change. [1]
> 2. The `/**` optimization for the common usecase of `/<0;1>` for point 1).
>
> [...]
>
> I'm not so sure about the second point. Is another deviation from the
> standard worth it just for saving 3
> characters?
>

I agree with the concerns of both you and Billy on the `\**` syntax, and it
is certainly not a crucial part of the proposal, as it is arguably
redundant once `\<0;1>` is available.
I have been using it since before the `\<0;1>` syntax was proposed (afaik),
and I thought I would leave it mostly for the sake of optimizing the UX in
the most common use cases. I think that

sh(sortedmulti(2,@0/**,@1/**,@2/**))

is quite a lot more readable (especially on a small screen) than

sh(sortedmulti(2,@0/<0;1>/*,@1/<0;1>/*,@2/<0;1>/*))

Apart from the additional 5 characters *per placeholder*, there are a lot
more numbers to parse for the user.

Yet, I'm not too attached to the feature as it is probably not very useful
in taptrees. For the future, I expect further improvements will come from
the hardware wallets analyzing the wallet policy and recognizing the
commonly used patterns. No reason to show the full taptree of a complex
3-of-5 multisig setup − you can just say "Taproot 3-of-5 multisig". Show
the full taptree policy should be reserved for the 1% of advanced use-cases
that are not in the catalogue.

Slightly off-topic, but my impression is that descriptors are outgrowing
their original scope (probably the reason for sipa's comments[1] on the
early proposals for multiple derivation paths in one descriptor).
I think there is a case to be made for keeping the language of descriptors
limited to represent either (1) a single output, or (2) a list of outputs
with the `/*` syntax; in this interpretation, the `/` syntax would
entirely be on a separate layer (the `combo` descriptor[2] would also be
extraneous in this interpretation).
I tried to design the policy wallet language in a way that is agnostic to
these details of descriptor specs (since I target a _subset_ of
descriptors, it will work either way).

However, why does it need to be a change to the descriptor language? It
> looks a lot like something that needs
> to be handled at the application level with key aliasing.


Key aliasing is not part of descriptors; therefore, "descriptors with key
aliasing" are still a language on top of descriptors.

Adding key aliases will indeed be a great UX improvement, but in my opinion
it is better built on top of wallet policies, rather than within the
language itself.
Note that by separating the *wallet descriptor template* from the keys
themselves, such a feature is already facilitated. Moreover, wallet
policies separate the KEY expressions of descriptors into two semantically
relevant parts: only the xpub and its origin info goes into the "vector of
key information", while the receive/change part of the derivation is kept
in the placeholder (therefore in the descriptor template). Adding
restrictions is also useful: `xpub/1/2/3/4/<0;1>/5/6/*` might be valid
miniscript, but supporting this kind of thing would be (arguably)
unreasonable and a lot more complicated for hardware wallets; therefore,
placeholders and key informations are a lot more limited in the wallet
policy language than their miniscript counterpart.

While I understand that descriptors are designed with a maximum flexibility
mindset, a minimized feature set is very valuable for hardware wallets, and
I believe it can be done with little to no practical loss of use cases.
Restrictions can be lifted in future versions when the need arises.

I think to better suit the needs of both hardware and software wallets, you
need both the *extensions* and the *restrictions*. That's why I propose to
keep them separated, rather than suggesting changes to descriptors.

Unrelated question, since you mentioned `musig2` descriptors in this
> context. I thought Musig2 wasn't really
> feasible for hardware signing devices, especially stateless ones. Do you
> think/know whether it is actually
> possible for a HW to take part in a Musig2?
>

I certainly have some more homework to do on musig2, and for this proposal
I was only concerned with making sure the wallet policy language won't
break with future upgrades to descriptors.
Yet, as far as I understand , the complications for hardware wallets are
(1) possible lack of good quality randomness, and (2) need to keep state
during a signing session. Ledger signers have a hardware TRNG, and while
the design is generally stateless, there is flash memory that can be used
to store the secret nonce during a signing session (or, more likely, a few
parallel signing sessions). Therefore, I don't think there are technical
blockers for musig2.

Salvatore

[bitcoin-dev] Wallet policies for descriptor wallets

[Salvatore Ingala via bitcoin-dev]

In the implementation work to implement descriptors and miniscript support
in hardware wallets [a][b], I encountered a number of challenges. Some of
them are technical in nature (e.g. due to constraints of embedded
development). Others are related to the attempts of shaping a good user
experience; with bitcoin reaching more people who are not tech-savvy,
self-custody is only as secure as what those newcomers can use easily
enough.

The main tool that I am using to address some of these challenges is a
layer that sits _on top_ of descriptors/miniscript, while staying very
close to it. Since there is nothing that is vendor-specific in the vast
majority of the approach I'm currently using, I tried to distill it here
for your comments, and will propose a BIP if this is deemed valuable.

I called the language "wallet policies" (suggestions for a better name are
welcome). I believe an approach based on wallet policies can benefit all
hardware wallets (stateless or not) that want to securely support complex
scripts; moreover, wallet policies are close enough to descriptors that
their integration should be extremely easy for any software wallet that is
currently using descriptors.

[a]: https://blog.ledger.com/bitcoin-2 - early demo
[b]: https://blog.ledger.com/miniscript-is-coming - miniscript example


Salvatore Ingala


==

This document starts with a discussion on the motivation for wallet
policies, followed by their formal definition, and some recommendations for
implementations.

== Rationale ==

Output script descriptors [1] were introduced in bitcoin-core as a way to
represent collections of output scripts. It is a very general and flexible
language, designed to catch all the possible use-cases of bitcoin wallets
(that is, if you know the script and you have the necessary keys, it will
be possible to sign transactions with bitcoin-core's descriptor-based
wallets).

Unfortunately, descriptors are not a perfect match for the typical usage of
hardware wallets. Most hardware wallets have the following limitations
compared to a general-purpose machine running bitcoin-core:

- they are embedded devices with limited RAM and computational power;
- they might not be able to import additional private keys (all the keys
are generated from a single seed via [BIP-32](
https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki));
- they might not have permanent storage (*stateless* hardware wallet
design).

Moreover, other limitations like the limited size of the screen might
affect what design choices are available in practice. Therefore, minimizing
the size of the information shown on-screen is important for a good user
experience.

A more native, compact representation of the wallet receive/change would
also benefit the UX of software wallets using descriptors to represent
software wallets using descriptors/miniscript for multisignature or other
complex locking conditions.

=== Security and UX concerns of scripts in hardware wallets ===

For a hardware wallet, allowing the usage of complex scripts presents
challenges in terms of both security and user experience.

 Security issues 

One of the security properties that hardware wallets strive to guarantee is
the following: **as long as the user correctly verifies the information
that is shown on the hardware wallet's screen before approving, no action
can be performed without the user's consent**.
This must hold even in scenarios where the attacker has full control of the
machine that is connected to the hardware wallet, and can execute arbitrary
requests or tamper with the legitimate user's requests.

Therefore, it is not at all trivial to allow complex scripts, especially if
they contain keys that belong to third parties.
The hardware wallet must guarantee that the user knows precisely *what*
"policy" is being used to spend the funds, and that the "unspent" funds (if
any) will be protected by the same policy. This makes it impossible for an
attacker to surreptitiously modify the policy, therefore stealing or
burning user's funds.

 UX issues 

With miniscript (and taproot trees) allowing substantially more complex
spending policies to be used, it becomes more challenging to make sure that
the user is able _in practice_ to verify the information on the screen.
Therefore, there are two fundamental design goals to strive for:
- Minimize the amount of information that is shown on screen - so that the
user can actually validate it.
- Minimize the number of times the user has to validate such information.

Designing a secure protocol for the coordination of a descriptor wallet
among distant parties is also a challenging problem that is out of scope in
this document. See BIP-129 [2] for an approach designed for multisignature
wallets.

=== Policy registration as a solution ===

A solution to address the security concerns, and part of the UX concerns,
is to have a *registration* flow for the wallet 

Re: [bitcoin-dev] Taproot Fields for PSBT

[Salvatore Ingala via bitcoin-dev]

Hi Andrew,

Thanks for the clarification, I was indeed reading it under the mistaken
assumption that only one leaf would be added to the PSBT.

En passant, for the less experienced readers, it might be helpful if the
key types that are possibly present multiple times (with different keydata)
were somehow labeled in the tables.

Best,
Salvatore Ingala
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot Fields for PSBT

[Salvatore Ingala via bitcoin-dev]

Hi Andrew,

I just have a small suggestion on this proposal.

On Tue, 22 Jun 2021 at 23:29, Andrew Chow via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> | Taproot Leaf Script
> | PSBT_IN_TAP_LEAF_SCRIPT = 0x15
> | 
> | The control block for this leaf as specified in BIP 341. The control
> block contains the merkle tree path to this leaf.
> | 

Re: [bitcoin-dev] Proposal: Bitcoin Secure Multisig Setup

[Salvatore Ingala via bitcoin-dev]

Hi Hugo,

First of all, thank you for the impressive work on leading the
standardization efforts!

I believe one ought to more clearly distinguish the "Signer" (as in: one of
the parties in the multisig setup), from the "*Signing device*" (which is
likely a hardware wallet). BSMS defines a "Signer" as "a participating
member in the multisig",  therefore a person/entity who is likely using
both a hardware wallet and some BSMS-friendly software wallet (e.g. the
next version of Specter Desktop). It is therefore relevant to discuss which
parts of the BSMS mechanism are implemented in the Signer's software
wallet, and which should be in the Signer's hardware wallet.
>From the discussion, it appears to me that different people might have
different expectations on what the signing device/HWW should do, so I would
like to comment on this point specifically (while I reckon that it mostly
falls within the realm of concerns #4 and #5 of the motivation paragraph,
which are explicitly left out of scope).

I fully agree that a *Signer* must persist the full wallet's description,
and should also create physical backups which include the full descriptor
and the cosigner's information. I would disagree, however, if any standards
were to force *hardware wallets* to persist any substantial amount of state
other than the seed, as I believe that it gives no substantial advantage
over externally stored signed data for many use cases.

The following is the *wallet registration flow* I am currently working on
(in the context of adding support to multisig wallets at Ledger). The goal
is to allow a *Signer* (the person) to persist a multisig setup in its
storage, while achieving a similar level of security you would have if you
were storing it on the hardware wallet itself (note that the following flow
would happen as part of Round 2):

1) The desktop wallet of the requests the HWW to register a new multisig
wallet. The request includes the full multisig wallet description, and some
extra metadata (e.g.: a name to be associated to this multisig wallet).
2) The HWW validates the wallet and verifies it with the user with the
trusted screen (as per BSMS Round 2); on confirmation, it returns a wallet
id (which is a vendor-specific hash of all the wallet description +
metadata) and signature
3) The desktop wallet stores the full wallet description/id/signature.
(Optionally, a backup could be stored elsewhere).

Whenever an operation related to the multisig wallet is required (verifying
a receiving address, or signing a spending transaction), the HWW first
receives and verifies all the data stored at step 3 above (without any user
interaction). Then it proceeds exactly the same way as if it had always
stored the multisig wallet in their own storage. I think this is basically
the same flow Michael Flaxman is suggesting here:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-April/018775.html

(Note that none of this is flow specific to Multisig wallet, as the same
flow would be unchanged for any arbitrary supported script that needs to be
"registered" on a stateless device, and can be generalized for MPC
protocols)

The only caveat I can think of is that the script registration is never
revocable if a signing key derived from the seed is used in step (2), which
might or might not be desirable. One could instead prefer to use a
different signing key that is destroyed if the device is wiped, which would
therefore need to be stored on the device. Note that the only thing that is
lost is the on-device multisig wallet registration, which could easily be
repeated from a backup.


On Sun, 11 Apr 2021 at 19:11, Hugo Nguyen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I reiterate that I strongly disagree that going stateless is the direction
> we want to pursue when it comes to multisig.
>
> In a multisig or any type of MPC smart contract, any Signer in the
> contract must know who the other co-Signers are at all times. You can
> choose to do this verification once at setup and persist this info on the
> Signer, or you'd have to re-do the verification for every single
> transaction. There is no other choice.
>

>
Signing the descriptor record is insufficient, while also introducing a
> great deal of complexity. Here are the problems:
> 1) The signature needs to be stored somewhere. Who stores it if it's not
> the Signer itself? What if it gets lost? (If the Signer stores its own
> signature, then the scheme is no longer stateless. You might as well store
> the full descriptor).
>

In the flow I describe above, the desktop wallet would indeed store the
signed descriptor record and wallet metadata. So yes, the *Signer* as in *the
party in the protocol* stores it, but not the signing device*. *The same
method could be used to store state temporarily between round 1 and 2,
where the only *state* on the hardware wallet would be the TOKEN, while
everything else is stored (encrypted and signed) on the Signer's desktop.

[bitcoin-dev] Hash-based accumulators with quick insertion

[Salvatore Ingala via bitcoin-dev]

Dear all,

I have been working on some constructions for cryptographic accumulators
that optimise for quick insertion.

As a brief background, an accumulator is a data structure that maintains
compact commitments to a potentially very large (and dynamic) set, while
keeping proofs of membership short. Unsurprisingly, they are getting more
popular, and one notable application in Bitcoin is to create light-weight
full nodes that do not need to store the UTXO set (Utreexo accumulator[1]).

In this work, I focus on additive accumulators that supports adding new
elements, but not removing them. My motivation is to support extending
Script with access to an arbitrarily large portion of the blockchain
history and state (e.g., past blocks, txids, or any more complex state
obtained from them - with all due care). The additional storage and
computation cost for nodes is small, and the cost (in additional bytesize)
for any transaction that wishes to access state committed in the
accumulator should be just slightly bigger than typical Merkle proofs.

I have focused on:
- An accumulator with insertion time O(1) and proof size O(log^2 n)
- A construction with insertion time O(log log n) and proof size O(log n
log log n)

All the performance metrics above are in "number of hashes".

You can find:
- draft writeup:
https://github.com/bigspider/accumulator/blob/master/docs/paper-draft.pdf
- sample python code (only for the first construction at this time):
https://github.com/bigspider/accumulator

While this is still an unfinished work, the ideas in the draft are
hopefully clear enough and easy to understand. I wanted to share it at this
stage as it can benefit from comments to improve the constructions, to
cover any related work or to find potential applications in Bitcoin (e.g.
Script, layer2, side chains, etc).

Best,
Salvatore Ingala

[1] - Thaddeus Dryja, Utreexo: A dynamic hash-based accumulator optimized
for the Bitcoin UTXO set - https://eprint.iacr.org/2019/611.pdf
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev