Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[ZmnSCPxj via bitcoin-dev]

Good morning Dmitry, and Jeremy,


> There is a principle that some find valuable: "During reorgs of depth
> less than 100, it is always possible to eventually replay transactions
> from the old branch into the new branch as long as no double spends are
> attempted" (quoted from Russel O'Connor from the discussion about
> 'revocation utxo' on Elements Slack channel).
>
> As far as I can tell, this principle can be violated with the use of
> RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch
> B and then branch A wins -> children of (tx') can't be replayed"

But an RBF-ed transaction *is* a double-spend, and the principle makes an 
exception specifically for double-spends.
Thus RBF, and other double-spends, are exempt from this principle.

My vague understanding of the "revocation UTXO" feature is that it is 
implemented as a double-spend of a precommitted `OP_CTV`, so that also is 
exempted from the principle.

As Jeremy notes as well, the *actual* principle is that "a script that is valid 
now remains valid in the future" (as this is required by the script cache 
implementation of Bitcoin Core), and this principle does not mention UTXOs, 
only scripts; the existence or non-existence of a required UTXO is separate 
here.
Thus, an "automatic inverse timelock" is not possible to implement with 
**only** script (it implies that a script that is valid now will become invalid 
in the future), but requires some action on the blockchain (notice that HTLCs 
effectively implement an "inverse timelock" on the hash-branch participant, by 
threatening a spend (i.e. blockchain activity) by the counterparty if does not 
comply).

Regards,
ZmnSCPxj



>
> Some may hold an opinion that introducing new rules that violate that
> principle should be done with caution.
>
> The 'revocation utxo' feature enabled by OP_CTV essentially introduces
> a manually triggered 'inverse timelock' - normal timelocks make tx
> invalid until certain point in time, and inverse timelock make tx
> invalid after certain point in time, in this case by spending an
> unrelated UTXO.
>
> In a reorg, one branch can have that UTXO spent before the OP_CTV
> transaction that depends on it is included in the block, and the OP_CTV
> transaction and its children can't be replayed.
>
> This is the same issue as an 'automatic inverse timelock' that could
> be enforced by the structure of the transaction itself, if there was
> appropriate mechanism, with the difference that 'revocation utxo' is
> manually triggered.
>
> The absense of 'automatic inverse timelock' mechanism in Bitcoin hints
> that it was not seen as desireable historically. I was not able to find
> the relevant discussions, though.
>
> I would like to add that the behaviour enabled by inverse timelocks
> could be useable in various schemes with covenants, like the vaults
> with access revocable by spending the 'revocation utxo', or in the
> trustless lending schemes where the covenant scripts can enforce
> different amounts of interest paid to lender based on the point in time
> when the loan is returned - the obsolete script paths (with smaller
> interest paid) can be disabled by inverse timelock.
>
> В Fri, 13 Dec 2019 23:37:19 -0800
> Jeremy jlru...@mit.edu wrote:
>
> > That's a cool use case. I've thought previously about an
> > OP_CHECKINPUT, as a separate extension. Will need to think about if
> > your construction introduces a hash cycle (unless
> > SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely).
> > Also re signatures I think it's definitely possible to pick a
> > (signature, message) pair and generate a pk from it, but in general
> > the Bitcoin message commits to the pk so forging isn't possible.
> > On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov d...@simplexum.com
> > wrote:
> >
> > > Another idea for smart vaults:
> > > The ability to commit to scriptSig of a non-segwit input could be
> > > used for on-chain control of spending authorization (revoking the
> > > spending authorization), where CTV ensures that certain input is
> > > present in the transaction.
> > > scriptSig of that input can contain a signature that commits to
> > > certain prevout. Unless it is possible to forge an identical
> > > signature (and I don't know how strong are guarantees of that),
> > > such an input can only be valid if that prevout was not spent.
> > > Thus spending such prevout makes it impossible to spend the input
> > > with CTV that commits to such scriptSig, in effect revoking an
> > > ability to spend this input via CTV path, and alternate spending
> > > paths should be used (like, another taproot branch)
> > > В Fri, 13 Dec 2019 15:06:59 -0800
> > > Jeremy via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org
> > > пишет:
> > >
> > > > I've prepared a draft of the changes noted above (some small
> > > > additional modifications on the StandardTemplateHash described in
> > > > the BIP), but have not yet updated the main branches for the BIP
> > > > to leave tim

Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)

[David A. Harding via bitcoin-dev]

On Fri, Feb 14, 2020 at 12:07:15PM -0800, Jeremy via bitcoin-dev wrote:
> Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
> I'm missing something in one of the cases? 

That's fair.  However, it's only true if everyone constructs their
merkle tree in the same way, with a single ` OP_CHECKSIG` as
one of the top leaves.   Taproot effectively standardizes the position
of the all-parties-agree condition and so its anonymity set may contain
spends from scripts whose creators buried or excluded the the all-agree
option because they didn't think it was likely to be used.

More importantly, there's no incentive for pure single-sig users to use a
merkle tree, since that would make both the scriptPubKey and the witness
data are larger for them than just continuing to use v0 segwit P2WPKH.
Given that single-sig users represent a majority of transactions at
present (see AJ Towns's previous email in this thread), I think we
really want to make it as convenient as possible for them to participate
in the anonymity set.

(To be fair, taproot scriptPubKeys are also larger than P2WPKH
scriptPubKeys, but its witness data is considerably smaller, giving
receivers an incentive to demand P2TR payments even if spenders don't
like paying the extra 12 vbytes per output.)

Rough sums:

- P2WPKH scriptpubkey (22.00 vbytes): `OP_0 PUSH20 `
- P2WPKH witness data (26.75): `size(72) , size(33) `
- P2TR scriptpubkey (34.00): `OP_1 PUSH32 `
- P2TR witness data (16.25): `size(64) `
- BIP116 MBV P2WSH scriptpubkey (34.00): `OP_0 PUSH32 `
- BIP116 MBV P2WSH witness data (42.00): `size(64) , size(32)
  , size(32) , size(36)  PUSH32
   OP_MBV>`

-Dave

P.S. I think this branch of the thread is just rehashing points that
 were originally covered over two years ago and which haven't really
 changed since then.  E.g.:


https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015629.html


signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot public NUMS optimization (Re: Taproot (and graftroot) complexity)

[Jeremy via bitcoin-dev]

I am working on CTV, which has cases where it's plausible you'd want a
taproot tree with a NUMS point.

The need for NUMS points is a little bit annoying. There are a few reasons
you would want to use them instead of multisig:

1) Cheaper to verify/create.
If I have a protocol with 1000 people in it, if I add a multisig N of N to
verify I need a key for all those people, and the probability of use seems
low.
I then also need to prove to each person in the tree that their key is
present. My memory on MuSig is a bit rusty, but I think they key
aggregation requires sending all the public keys and re-computing. (Maybe
you can compress this to O(log n) using a Merkle tree for the tweak L?)
Further, these keys can't just be the addresses provided for those 1000
people, as if those addresses are themselves N of Ns or scripts it gets
complicated, fast (and potentially broken). Instead we should ask that each
participant give us a list of keys to include in the top-level. We'd also
want each participant to provide
two signatures with that key of some piece of non-txn data (so as to prove
it itself wasn't a NUMS point -- otherwise may as well skip this all and
just use a top-level nums point).
2) Auditable.
If I set up an inheritance scheme, like an annuity or something, and the
IRS wants me to pay taxes on what I've received, adverse inference will
tell them to assume that my parent gave me a secret get all the money path
and this is a tax dodge. With a NUMS point, heirs can prove there was no
top-level N of N.
3) I simply don't want to spend it without a script condition, e.g.,
timelock.


Now, assuming you do want a NUMS, there is basically 4 ways to make one
(that I could think of):

1) Public NUMS -- this is a constant, HashToCurve("I am a NUMS Point").
Anyone scanning the chain can see spends are using this constant. Hopefully
everyone uses the same constant (or everyone uses 2,3,4) so that "what type
of NUMS you are using" isn't a new fingerprint.
2) Moslty Public NUMS -- I take the hash of some public data (like maybe
the txid) on some well defined protocol, and use that. Anyone scanning the
chain and doing an EC operation per-txid can see I'm using a constant --
maybe my HashToCurve takes 10 seconds (perhaps through a VDF to make it
extra annoying for anyone who hasn't been sent the shortcut), but in
practice it's no better than 1.
3) Interactive NUMS -- I swap H(Rx), H(Ry) with the other participant and
then NUMS with H(Rx || Ry). This is essentially equivalent to using a MuSig
key setup where one person's key is a NUMS. Now no one passively scanning
can see that it's NUMS, but I can prove to an auditor later.
4) 1/2 RTT Async-Interactive NUMS -- I take some public salt -- say the
txid T, and hash it with a piece of random data R and then HashToCurve(T ||
R)... I think this is secure? Not clear the txid adds any security. Now I
can prove to you that the hash was based on the txid, but I've blinded it
with R to stop passive observers. But I also need ot send you data out of
band for R (but I already had to do this for Taproot maybe?)

The downsides with 3/4 is that if you lose your setup, you lose your
ability to spend/prove it's private (maybe can generate R from a seed?). So
better hold on to those tightly! Or use a public NUMS.

Only 3,4 provide any "real" privacy benefit and at a small hit to
likelihood of losing funds (more non-deterministic data to store). I guess
the question becomes how likely are we to have support for generating a
bunch of NUMS points?

Comparing with this proposal which removes the NUMS requirement:

1) NUMS/Taproot anonymity set *until* spend, MAST set after spend
2) No complexity around NUMS generation/storage
3) If people don't have ecosystem-wide consistent NUMS practices, leads to
additional privacy leak v.s. bare MAST which would be equivalent to case 1
(Public NUMS)
4) Slightly less chain overhead (32 bytes/8 vbytes).
5) Slightly faster chain validation (EC Point tweak is what like 10,000 -
100,000 times slower than a hash?)


Matt raises a interesting point in the other thread, which is that if we
put the option for a more private NUMS thing, someone will eventually write
software for it. But that seems to be irrespective of if we make no-NUMS an
option for bare MAST spends.

Overall I think this is a reasonable proposal. It effectively only
introduces bare MAST to prevent the case where people are using a few
different Public NUMS leaking metadata by putting incentive to use the same
one -- none. Using a private NUMS is unaffected incentive wise as it's
essentially just paying a bit more to be in the larger anonymity set. I
think it makes some class of users better off, and no one else worse off,
so this change seems Pareto.

Thus I'm in favor of adding a rule like this.

I think reasonable alternative responses to accepting this proposed change
would be to:

1) Add a BIP for a standard Public NUMS Point exported through secp256k1 to
head off people defining their own po

Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)

[Jeremy via bitcoin-dev]

Dave,

I think your point:
















*When schnorr and taproot are done together, all of the following
transaction types can be part of the same set: - single-sig spends
(similar to current use of P2PKH and P2WPKH) - n-of-n spends with musig
or equivalent (similar to current use of   P2SH and P2WSH 2-of-2
multisig without special features as used by   Blockstream Green and LN
mutual closes) - k-of-n (for low values of n) using the most common k
signers   (similar to BitGo-style 2-of-3 where the keys involved are
alice_hot, alice_cold, and bob_hot and almost all transactions are
  expected to be signed by {alice_hot, bob_hot}; that common case   can
be the key-path spend and the alternatives {alice_hot,   alice_cold}
and {alice_cold, bob_hot} can be script-path spends) - contract
protocols that can sometimes result in all parties   agreeing on an
outcome (similar to LN mutual closes, cross-chain   atomic swaps, and
same-chain coinswaps) *

Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
I'm missing something in one of the cases? I guess there's a distinction on
"can" v.s. "are likely"?


Jonas,

That's a really interesting point about K-N systems making the most likely
K-K the taproot key. (For the uninitiated, MuSig can do N-of-N aggregation
non-interactively, but K-of-N requires interaction). I think this works
with small (N choose K), but as (N choose K) increases it seems the
probability of picking the correct one goes down?

I guess the critical question is if cases where there's not some timelock
will be mandatory across all signing paths.


cheers,

jeremy

--
@JeremyRubin 



On Mon, Feb 10, 2020 at 9:16 AM Jonas Nick via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I agree with most of the comments so far, but the group brings up an often
> overlooked point with respect to the privacy benefits of taproot. In the
> extreme
> case, if there would be no policies that have both a key and a script spend
> path, then taproot does not improve anonymity sets compared to the "Taproot
> Public NUMS Optimization" proposal (which saves 8 vbytes in a
> script-spend). (*)
>
> In fact, the cases where scripts would have to be used given usage of
> Bitcoin
> today are be rare because threshold policies, their conjunctions and
> disjunctions can be expressed with a single public key. Even if we
> disregard
> speculation that timelocks, ANYPREVOUT/NOINPUT and other interesting
> scripts
> will be used in the future (which can be added through the leaf or key
> versions
> without affecting key-spend anonymity sets), not all of today's
> applications are
> able to be represented single public keys because there are applications
> that
> can not deal with interactive key setups or interactive signing. For
> applications where this is possible it will be a gradual change because of
> the
> engineering challenges involved. For example, k-of-n threshold policies
> could
> have the most likely k-of-k in the taproot output key and other k-of-k in
> the
> leaves, instead of going for a k-of-n taproot output key immediately.
>
> Given that anonymity sets in Bitcoin are permanent and software tends to be
> deployed longer than anyone would expect at the time of deployment,
> realistically Taproot is superior to the "Public NUMS Optimization" and "An
> Alternative Deployment Path".
>
> (*) One could argue that the little plausible deniability gained by a very
> small
> probability of the change of a script-spend being a key-spend and vice
> versa is
> significantly better than no probability at all.
>
> On 2/9/20 8:47 PM, Bryan Bishop via bitcoin-dev wrote:
> > Apologies for my previous attempt at relaying the message- it looks like
> > the emails got mangled on the archive. I am re-sending them in this
> > combined email with what I hope will be better formatting. Again this is
> > from some nym that had trouble posting to this mailing list; I didn't see
> > any emails in the queue so I couldn't help to publish this sooner.
> >
> > SUBJECT: Taproot (and Graftroot) Complexity
> >
> > This email is the first of a collection of sentiments from a group of
> > developers who in aggregate prefer to remain anonymous. These emails have
> > been sent under a pseudonym so as to keep the focus of discussion on the
> > merits of the technical issues, rather than miring the discussion in
> > personal politics.  Our goal isn't to cause a schism, but rather to help
> > figure out what the path forward is with Taproot. To that end, we:
> >
> > 1) Discuss the merits of Taproot's design versus simpler alternatives
> (see
> > thread subject, "Taproot (and Graftroot) Complexity").
> >
> > 2) Propose an alternative path to deploying the technologies described in
> > BIP-340, BIP-341, and BIP-342 (see thread subject, "An Alternative
> > Deployment Path for Taproot Technologies").
> >
>

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Jeremy via bitcoin-dev]

Hi Dmitry,

I don't think that this is fundamentally introducing new behavior, but
let's take a closer look.

We can talk about the issue you bring up purely in terms of a hypothetical
"OP_CHECKINPUTOUTPOINTVERIFY" and "OP_CHECKINPUTSCRIPTVERIFY" (CIOV, CISV)
with obvious implied by name semantics, as a separate construct from CTV
itself. Such opcodes would be strictly more powerful/flexible than what CTV
is enabling.

Using these opcodes I can make an output that can *only* be spent with
another output -- e.g.,

  OP_CISV OP_DROP  OP_CHECKSIGVERIFY
  OP_CIOV OP_DROP  OP_CHECKSIGVERIFY

Let's look at CISV first:

1) Assume that  is from the same owner as PK
2) Assume that  is from a different owner than PK

In case 1, the wallet can create or recreate the appropriate output as
needed if it gets spent/stuck

In case 2, the wallet can get "frozen" in a reorg until a signer on 
re-spends.


For CIOV:

1) Assume that  exists in the chain somewhere
2) Assume that  exists in the mempool somewhere
3) Assume that  does not exist (or, is provably non-creatable -- h =
txid(x) | x.IsValid() == false)

In case 2, this is just a fancy op-return.

Case 1 degrades into case 2 in the event of a reorg.

In Case 2, if the output  is spent in another transaction, our script
becomes provably unspendable (unless a second reorg).

Otherwise, it is possible to mine a block with our transaction.


Compare the above to normal transactions:

1) If a reorg occurs, and someone double-spends, your transaction gets
cancelled.
2) You can re-sign your UTXO onto a different transaction

However, if you have deleted your key (e.g. using a pre-signing HSM), or
your transaction was using a multi-sig with an uncooperating party, you
will have an output that may be effectively burned.

These issues are -- as with CTV -- not present in the single input use case.

Thus I argue that CTV -- whose semantics are less powerful/flexible than
CISV/CIOV -- aren't introducing something that's not already present when
doing protocols involving more than one input.

Further, on CTV "monotonic authorization":

Generally we want Bitcoin Scripts to have the property that once a
condition is reached, it is 'permanently' a true case. E.g., showing a hash
preimage to C x, H(x) == C. This can't change with the weather or anything
else. Even things like timelocks -- although not obvious at first glance --
have this property. They express logic that says "given the chain is at
this height, ...". This means that on any chain at such a height the txn is
valid. CISV/CIOV semantics also fall in line with this description. It
says, "given such an input U, ...". If that input is realizable one time,
it is provably realizable across reorgs. However, that doesn't mean someone
couldn't interrupt U from being created. But generally, with Reorg + Double
spend, or Reorg > 100 blocks (potentially destroying CB reward), all bets
are off as to the replay-ability of transactions.

I want to also point out that this "revocation" property -- to the extent
it is something new that can't already be emulated with pre-signeds or RBF
-- is entirely opt-in as far as CTV is concerned. You have to specify that
an output can only be spent with another, most wallets shouldn't do that,
and it can't "infect" other wallets to an extent more than spending from
any recently confirmed output exposes you to more reorg risk.

*In sum, we do not need to worry about this for CTV.*


Lastly, I want to note that revocation is part of what CTV is designed to
do (absent reorgs). It allows us to prune spending conditions by playing a
transaction forward.

E.g., spending conditions {Alice & Bob, Preimage(H(X)) + Eve, CTV({Alice &
Bob}, 1 day)}

Expresses that Eve has 1 day to reveal the preimage to H(X), otherwise
Alice and Bob can take the coin back by removing Eve's HTLC path. What's
cool about this revocation v.s. just {Alice & Bob, Preimage(H(X)) + Eve} is
that Alice and Bob don't need to coordinate a multisig to revoke Eve.



--
@JeremyRubin 



On Fri, Feb 14, 2020 at 3:17 AM Dmitry Petukhov  wrote:

> I decided to take this thread back on-list because I beleive that the
> 'revocation utxo' feature enabled by OP_CTV commiting to scriptSig may
> have wider implications that can slightly change the behavior of Bitcoin
> as a system, and some might not expect such changes or might not find
> them desireable (although there is already a case for such behaviour
> with RBF).
>
> There is a principle that some find valuable: "During reorgs of depth
> less than 100, it is always possible to eventually replay transactions
> from the old branch into the new branch as long as no double spends are
> attempted" (quoted from Russel O'Connor from the discussion about
> 'revocation utxo' on Elements Slack channel).
>
> As far as I can tell, this principle can be violated with the use of
> RBF: "(tx) that was included in branch A and then RBF-ed (tx') i

Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY

[Dmitry Petukhov via bitcoin-dev]

I decided to take this thread back on-list because I beleive that the
'revocation utxo' feature enabled by OP_CTV commiting to scriptSig may
have wider implications that can slightly change the behavior of Bitcoin
as a system, and some might not expect such changes or might not find
them desireable (although there is already a case for such behaviour
with RBF).

There is a principle that some find valuable: "During reorgs of depth
less than 100, it is always possible to eventually replay transactions
from the old branch into the new branch as long as no double spends are
attempted" (quoted from Russel O'Connor from the discussion about
'revocation utxo' on Elements Slack channel).

As far as I can tell, this principle can be violated with the use of
RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch
B and then branch A wins -> children of (tx') can't be replayed"

Some may hold an opinion that introducing new rules that violate that
principle should be done with caution.

The 'revocation utxo' feature enabled by OP_CTV essentially introduces
a manually triggered 'inverse timelock' -  normal timelocks make tx
invalid until certain point in time, and inverse timelock make tx
invalid _after_ certain point in time, in this case by spending an
unrelated UTXO.

In a reorg, one branch can have that UTXO spent before the OP_CTV
transaction that depends on it is included in the block, and the OP_CTV
transaction and its children can't be replayed.

This is the same issue as an 'automatic inverse timelock' that could
be enforced by the structure of the transaction itself, if there was
appropriate mechanism, with the difference that 'revocation utxo' is
manually triggered.

The absense of 'automatic inverse timelock' mechanism in Bitcoin hints
that it was not seen as desireable historically. I was not able to find
the relevant discussions, though.

I would like to add that the behaviour enabled by inverse timelocks
could be useable in various schemes with covenants, like the vaults
with access revocable by spending the 'revocation utxo', or in the
trustless lending schemes where the covenant scripts can enforce
different amounts of interest paid to lender based on the point in time
when the loan is returned - the obsolete script paths (with smaller
interest paid) can be disabled by inverse timelock.

В Fri, 13 Dec 2019 23:37:19 -0800
Jeremy  wrote:

> That's a cool use case. I've thought previously about an
> OP_CHECKINPUT, as a separate extension. Will need to think about if
> your construction introduces a hash cycle (unless
> SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely).
> 
> Also re signatures I think it's definitely possible to pick a
> (signature, message) pair and generate a pk from it, but in general
> the Bitcoin message commits to the pk so forging isn't possible.
> 
> On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov 
> wrote:
> 
> > Another idea for smart vaults:
> >
> > The ability to commit to scriptSig of a non-segwit input could be
> > used for on-chain control of spending authorization (revoking the
> > spending authorization), where CTV ensures that certain input is
> > present in the transaction.
> >
> > scriptSig of that input can contain a signature that commits to
> > certain prevout. Unless it is possible to forge an identical
> > signature (and I don't know how strong are guarantees of that),
> > such an input can only be valid if that prevout was not spent.
> >
> > Thus spending such prevout makes it impossible to spend the input
> > with CTV that commits to such scriptSig, in effect revoking an
> > ability to spend this input via CTV path, and alternate spending
> > paths should be used (like, another taproot branch)
> >
> >
> > В Fri, 13 Dec 2019 15:06:59 -0800
> > Jeremy via bitcoin-dev 
> > пишет: 
> > > I've prepared a draft of the changes noted above (some small
> > > additional modifications on the StandardTemplateHash described in
> > > the BIP), but have not yet updated the main branches for the BIP
> > > to leave time for any further feedback.
> > >
> > > See below:
> > >
> > > BIP:
> > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki
> > > Implementation:
> > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2
> > >
> > > Thank you for your feedback,
> > >
> > > Jeremy
> > > --
> > > @JeremyRubin 
> > >   
> >
> >  

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