Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[ZmnSCPxj via bitcoin-dev]

Good morning Greg,

I am probably being exceedingly naive, but I would like to compare Taproot to a 
generalization of funding transactions.

For instance, CoinSwapCS:

1.  It uses an HTLC in an off-chain transaction, and a funding transaction TX0 
whose output is a "simple" 2-of-2.
2.  The HTLC tx spends this 2-of-2.
3.  If a branch of the HTLC succeeds, the parties contact each other and create 
a replacement of the (unconfirmed and unbroadcasted but signed) HTLC tx that 
assigns the funds to the correct owners.
4.  If the above step fails, individual parties can in isolation publish the 
HTLC tx and provide its requirements.

Both of #3 and #4 above, appear to me naively as similar to the two "top" cases 
of Taproot, i.e. either C is signed by all parties, or S is revealed and 
fulfilled.

The important bits of this "generalized funding transaction" pattern is:

1. The contract that enforces correct behavior spends an unsigned and 
unbroadcasted funding transaction output (which requires N-of-N).
2. The enforcement contract is signed first by all parties before the funding 
transaction is signed by anybody.  This is possible due to SegWit.
3.  Then, when all parties are sure they have the fully-signed smart contract, 
the initial funding transaction is signed and broadcast and confirmed.
4.  When the condition that the contract requires is achieved, then the parties 
contact each other and try to jointly create a simpler transaction that spends 
the funding transaction directly to whoever gets the money in the correct 
proportion.  This avoids publishing the smart contract onchain, and looks like 
an ordinary N-of-N spend.
5.  If they fail to get all required signatures for any reason, any party can 
publish the enforcement contract transaction and subsequently fulfill its 
conditions in another transaction.

Admittedly, Taproot if added to the consensus would reduce the number of 
transactions by 1 in the "S is revealed" case.
But the "generalized funding transaction" pattern is already possible today, 
and MuSig (to my limited understanding) can be used to make it 
indistinguishable from 1-of-1 (so, possibly, make it P2WPKH?).


(I am probably neglecting something very simple and direct, however...)

Regards,
ZmnSCPxj

 Original Message 
 On January 23, 2018 8:30 AM, Gregory Maxwell via bitcoin-dev 
 wrote:

>Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
> areas: efficiency and privacy. Efficiency because unexecuted forks of
> a script can avoid ever hitting the chain, and privacy because hiding
> unexecuted code leaves scripts indistinguishable to the extent that
> their only differences are in the unexecuted parts.
>
> As Mark Friedenbach and others have pointed out before it is almost
> always the case that interesting scripts have a logical top level
> branch which allows satisfaction of the contract with nothing other
> than a signature by all parties.  Other branches would only be used
> where some participant is failing to cooperate. More strongly stated,
> I believe that any contract with a fixed finite participant set
> upfront can be and should be represented as an OR between an N-of-N
> and whatever more complex contract you might want to represent.
>
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments. Otherwise, if the
> anonymity set of fancy usage is only other fancy usage it may not be
> very large in practice. One suggestion has been that ordinary
> checksig-only scripts should include a dummy branch for the rest of
> the tree (e.g. a random value hash), making it look like there are
> potentially alternative rules when there aren't really.  The negative
> side of this is an additional 32-byte overhead for the overwhelmingly
> common case which doesn't need it.  I think the privacy gains are
> worth doing such a thing, but different people reason differently
> about these trade-offs.
>
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.
>
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
>
> Alice has public A, Bob has pubkey B.
>
> We compute the 2-of-2 aggregate key C = A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
>
> We form our timelock script S =  " OP_CSV OP_DROP B 
> OP_CHECKSIGVERIFY"
>
> Now we tweak C to produce P which is the key we'll publish: P = C + H(C||S)G.
>
> (This is the attack hardened pay-to-contract construction described in [2])
>
> Then we pay to a 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Matt Corallo via bitcoin-dev]

Gah, please no. I see no material reason why cross-input signature aggregation 
shouldn't have the signatures in the first n-1 inputs replaced with something 
like a single-byte push where a signature is required to indicate aggregation, 
and the combined signature in the last input at whatever position the signature 
is required.

On January 27, 2018 5:07:25 PM UTC, Russell O'Connor via bitcoin-dev 
 wrote:
-snip-
>Cross-input signature aggregation probably requires a new field to be
>added
>to the P2P transaction structure to hold the aggregated signature,
>since
>there isn't really a good place to put it in the existing structure
>(there
>are games you can play to make it fit, but I think it is worthwhile). 
>The
>obvious way add block commitments to a new tx field is via the witness
>reserved value mechanism present in BIP 141.  At this point I think
>there
>will be some leeway to adjust the discount on the weight of this new
>aggregated signature tx field so that even a single input taproot using
>the
>aggregated signature system (here an aggregation of 1 signature) ends
>up no
>more expensive than a single input segwit P2WPKH.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Russell O'Connor via bitcoin-dev]

On Tue, Jan 23, 2018 at 1:44 AM, Anthony Towns via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Tue, Jan 23, 2018 at 12:30:06AM +, Gregory Maxwell via bitcoin-dev
> wrote:
> > One point that comes up while talking about merkelized scripts is can
> > we go about making fancier contract use cases as indistinguishable as
> > possible from the most common and boring payments.
>
> > Now we tweak C to produce P which is the key we'll publish: P = C +
> H(C||S)G.
> > (This is the attack hardened pay-to-contract construction described in
> [2])
> > Then we pay to a scriptPubKey of [Taproot supporting version] [EC point
> P].
>
> Is this really intended as paying directly to a pubkey, instead of a
> pubkey hash?
>
> If so, isn't that a step backwards with regard to resistance to quantum
> attacks against ECC?
>
> Paying direct to pubkey doesn't seem quite enough to make pay-to-taproot
> cheaper than p2wpkh: the extra 12 bytes in the scriptPubKey would need
> you to reduce the witness by 48 bytes to maintain the weight, but I think
> you'd only be saving 33 bytes by not having to reveal the pubkey, and
> another 6-7 bytes by having a tighter signature encoding than DER. Still,
> that's pretty close with a difference of only a couple of vbytes per
> input by my count.
>

I've been thinking about your comment, and I think your concern can be
addressed.  Taproot would almost certainly be deployed in conjunction with
cross-input signature aggregation.  Because aggregation doesn't work with
ECDSA, only those signatures using Taproot and other Schnorr signatures
would be available for aggregation.  Just having the ability to support
cross-input signature aggregation may be motivation enough for ordinary
pub-key users to switch to Taproot.  However, there is more.

Cross-input signature aggregation probably requires a new field to be added
to the P2P transaction structure to hold the aggregated signature, since
there isn't really a good place to put it in the existing structure (there
are games you can play to make it fit, but I think it is worthwhile).  The
obvious way add block commitments to a new tx field is via the witness
reserved value mechanism present in BIP 141.  At this point I think there
will be some leeway to adjust the discount on the weight of this new
aggregated signature tx field so that even a single input taproot using the
aggregated signature system (here an aggregation of 1 signature) ends up no
more expensive than a single input segwit P2WPKH.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 12:30 AM, Gregory Maxwell  wrote:
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.

Keeping in mind that a single public point can stand in for any
monotone function of public keys, a taproot branch is only needed for
accountability (being able to tell from public data which branches
were used) or when conditions other than public keys are required e.g.
CSV + a monotone function of keys.

I believe that with scriptless-scripts most of hash preimages can be
accomplished without an actual hash pre-image condition.

Are there other simple and very useful/general preconditions that
would be useful ANDed with a monotone function of public keys like is
the case for CSV?

I ask because recursive taproot by itself isn't very interesting,
since (other than accountability) there is no gain to not just merging
the alternative, but if there are additional conditions then it can be
useful. E.g.

[pubkey]
  \-[pubkey]&
 \-[fancy script]

So it might make sense to support a taproot construction that can
nest, where interior nested keys have a CSV/CLTV predicate. But are
there other simple predicates that cover a lot of cases?


[Aside: _please_ change the subject lines for further discussion about
quantum computers;]
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael via bitcoin-dev]

Den 25 jan. 2018 00:22 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:


I think you misread my second proposal. The first step is not only to
publish the hash but to publish a *pair* consisting of the hash and the
transaction.

If the attacker changes the transaction on the wire, the user does not
care and will try again.


I guess I assumed you meant it otherwise because I didn't assume you
intended a commitment to the full transaction just without the asymmetric
key material.

You could treat it the same way as in my suggestion, let it expire and
prune it if the key material isn't published in time.

However... A sufficiently powerful attacker can deploy as soon as he sees
your published signature and key, delay its propagation to the miners,
force expiration and then *still* repeat the attack with his own forgery.

Honestly, as long as we need to allow any form of expiry + relying on
publication of the vulnerable algorithms result for verification, I think
the weakness will remain.

No expiration hurts in multiple ways like via DoS, or by locking in
potentially wrong (or straight up malicious) transactions.

---

There's one way out, I believe, which is quantum safe Zero-knowledge
proofs. Currently STARK:s are one variant presumed quantum safe. It would
be used to completely substitute the publication of the public key and
signatures, and this way we don't even need two-step commitments.

It does however likely require a hardfork to apply to old transactions. (I
can imagine an extension block type softfork method, in which case old
UTXO:s get locked on the mainchain to create equivalent valued extension
block funds.)

Without practical ZKP,  and presuming no powerful QC attackers with the
ability to control the network (basically NSA level attackers), I do think
the Fawkes signature scheme is sufficient. Quantum attacks are likely to be
very expensive anyway, for the foreseeable future.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 19:51 +0100, Natanael wrote:
> 
> That's not the type of attack I'm imagining. Both versions of your
> scheme are essentially equivalent in terms of this attack. 
> 
> Intended steps: 
> 1: You publish a hash commitment. 
> 2: The hash ends up in the blockchain. 
> 3: You publish the transaction itself, and it matches the hash
> commitment. 
> 4: Because it matches, miners includes it. It's now in the
> blockchain. 

I think you misread my second proposal. The first step is not only to
publish the hash but to publish a *pair* consisting of the hash and the
transaction.

If the attacker changes the transaction on the wire, the user does not
care and will try again.

By the way: As described here, everybody could do this first step and
flood the blockchain with it. We cannot immediately subtract a fee,
because it's not clear that some transaction will take place at all. So
we need to take the fee from somewhere else or do something else to
prevent spam. But that's entirely different issue...
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael via bitcoin-dev]

Den 24 jan. 2018 16:38 skrev "Tim Ruffing via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:

Okay, I think my proposal was wrong...

This looks better (feel free to break again):
1. Commit (H(classic_pk, tx), tx) to the blockchain, wait until confirmed
2. Reveal classic_pk in the blockchain

Then the tx in the first valid commitment wins. If the attacker
intercepts classic_pk, it won't help him. He cannot create the first
valid commitment, because it is created already. (The reason is that
the decommitment is canonical now; for all commitments, the
decommitment is just classic_pk.)


That's not the type of attack I'm imagining. Both versions of your scheme
are essentially equivalent in terms of this attack.

Intended steps:
1: You publish a hash commitment.
2: The hash ends up in the blockchain.
3: You publish the transaction itself, and it matches the hash commitment.
4: Because it matches, miners includes it. It's now in the blockchain.

Attack:
1: You publish a hash commitment.
2: The hash ends up the blockchain.
3: You publish the transaction itself, it matches the hash commitment.
4: The attacker mess with the network somehow to prevent your transaction
from reaching the miners.
5: The attacker cracks your keypair, and makes his own commitment hash for
his own theft transaction.
6: Once that commitment is in the blockchain, he publishes his own theft
transaction.
7: The attacker's theft transaction gets into the blockchain.
8 (optionally): The miners finally see your original transaction with the
older commitment, but now the theft transaction can't be undone. There's
nothing to do about it, nor a way to know if it's intentional or not.
Anybody not verifying commitments only sees a doublespend attempt.

---

More speculation, not really a serious proposal:

I can imagine one way to reduce the probability of success for the attack
by publishing encrypted transactions as the commitment, to then publish the
key - the effect of this is that the key is easier to propagate quickly
across the network than a full transaction, making it harder to succeed
with a network based attack. This naive version by itself is however a
major DoS vector against the network.

You could, in some kind of fork, redefine how blocks are processed such
that you can prune all encrypted transactions that have not had the key
published within X blocks. The validation rules would work such that to
publish the key for an encrypted transaction in a new block, that
transaction must both be recent enough, be valid by itself, and also not
conflict with any other existing plaintext / decrypted transactions in the
blockchain.

Blocks wouldn't necessarily even need to include the encrypted transactions
during propagation. This works because encrypted transactions have zero
effect until the key is published. In this case you'd effectively be
required to publish your encrypted transaction twice to ensure the raw data
isn't lost, once to get into a block and again together with the key to get
it settled.

Since miners will likely keep at least the most recent encrypted
transactions cached to speed up validation, this is faster to settle than
to publish the committed transaction as mentioned in the beginning. This
increases your chances to get your key into the blockchain to settle your
transaction before the attacker completes his attack, versus pushing a full
transaction that miners haven't seen before.

This version would still allow DoS against miners caching all encrypted
transactions. However, if efficient Zero-knowledge proofs became practical
then you can use one to prove your encrypted transaction valid, even
against the UTXO set and in terms of not colliding with existing
commitments - in this case the DoS attack properties are nearly identical
to standard transactions.
If you want to change a committed transaction, you'd need to let the
commitment expire.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 13:51 +0100, Natanael via bitcoin-dev wrote:
> Sidenote: There's a risk here with interception, insertion of a new
> commitment and getting the new transaction into the blockchain first.
> However, I would suggest a mining policy here were two known
> conflicting transactions with commitments are resolved such that the
> one with the oldest commitment wins. How to address detection of
> conflicting transactions with commitments older than confirmed
> transactions isn't obvious. Some of these may be fully intentional by
> the original owner, such as a regretted transaction.

Okay, I think my proposal was wrong...

This looks better (feel free to break again):
1. Commit (H(classic_pk, tx), tx) to the blockchain, wait until confirmed
2. Reveal classic_pk in the blockchain

Then the tx in the first valid commitment wins. If the attacker
intercepts classic_pk, it won't help him. He cannot create the first
valid commitment, because it is created already. (The reason is that
the decommitment is canonical now; for all commitments, the
decommitment is just classic_pk.)

By the way, maybe I'm stating the obvious but Taproot (or similar) is
indeed very nice for outputs generated in the future: You can have a
path for a classical signature scheme and a path for a quantum-secure
scheme.

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

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Natanael via bitcoin-dev]

Den 23 jan. 2018 23:45 skrev "Gregory Maxwell via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org>:

On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns  wrote:
> Hmm, at least people can choose not to reuse addresses currently --
> if everyone were using taproot and that didn't involve hashing the key,

Can you show me a model of quantum computation that is conjectured to
be able to solve the discrete log problem but which would take longer
than fractions of a second to do so? Quantum computation has to occur
within the coherence lifetime of the system.


Quantum computers works like randomized black boxes, you run them in many
cycles with a certain probability of getting the right answer.

The trick to them is that they bias the probabilities of their qubits to
read out the correct answer *more often than at random*, for many classes
of problems. You (likely) won't get the correct answer immediately.

https://en.wikipedia.org/wiki/Quantum_computing

Quoting Wikipedia:

> An algorithm is composed of a fixed sequence of quantum logic gates and a
problem is encoded by setting the initial values of the qubits, similar to
how a classical computer works. The calculation usually ends with a
measurement, collapsing the system of qubits into one of the 2 n
{\displaystyle 2^{n}} 2^{n} pure states, where each qubit is zero or one,
decomposing into a classical state. The outcome can therefore be at most n
{\displaystyle n} n classical bits of information (or, if the algorithm did
not end with a measurement, the result is an unobserved quantum state).
Quantum algorithms are often probabilistic, in that they provide the
correct solution only with a certain known probability.

A non programmed QC is essentially an RNG driven by quantum effects. You
just get random bits.

A programmed one will need to run the and program over and over until you
can derive the correct answer from one of its outputs. How fast this goes
depends on the problem and the algorithm.

Most people here have heard of Grover's algorithm, it would crack a
symmetric 256 bit key in approximately 2^128 QC cycles - completely
impractical. Shor's algorithm is the dangerous one for ECC since it cracks
current keys at "practical" speeds.

https://eprint.iacr.org/2017/598 - resource estimates, in terms of size of
the QC. Does not address implementation speed.

I can't seem to find specific details, but I remember having seen estimates
of around 2^40 cycles in practical implementations for 256 bit ECC (this
assumes use error correction schemes, QC machines with small some
imperfections, and more). Unfortunately I can't find a source for this
estimate. I've seen lower estimates too, but they seem entirely
theoretical.

Read-out time for QC:s is indeed insignificant, in terms of measuring the
state of the qubits after a complete cycle.

Programming time, time to prepared for readout, reset, reprogramming, etc,
that will all take a little longer. In particular with more qubits
involved, since they all need to be in superposition and be coherent at
some point. Also, you still have to parse all the different outputs (on a
classical computer) to find your answer among them.
Very very optimistic cycle speeds are in the GHz range, and then that's
still on the order of ~15 minutes for 2^40 cycles. Since we don't even have
a proper general purpose QC yet, nor one with usable amounts of qubits, we
don't even know if we can make them run at a cycle per second, or per
minute...

However if somebody *does* build a fast QC that's nearly ideal, then
Bitcoin's typical use of ECC would be in immediate danger. The most
optimistic QC plausible would indeed be able to crack keys in under a
minute. But my own wild guess is that for the next few decades none will be
faster than a runtime measured in weeks for cracking keys.

---

Sidenote, I'm strongly in favor of implementing early support for the
Fawkes scheme mentioned previously.

We could even patch it on top of classical transactions - you can only
break ECC with a known public key, so just commit to the signed transaction
into the blockchain before publishing it. Then afterwards you publish the
transaction itself, with a reference to the commitment. That transaction
can then be assumed legit simply because there was no room to crack the key
before the commitment, and the transaction matches the commitment.

Never reuse keys, and you're safe against QC:s.

Sidenote: There's a risk here with interception, insertion of a new
commitment and getting the new transaction into the blockchain first.
However, I would suggest a mining policy here were two known conflicting
transactions with commitments are resolved such that the one with the
oldest commitment wins. How to address detection of conflicting
transactions with commitments older than confirmed transactions isn't
obvious. Some of these may be fully intentional by the original owner, such
as a regretted transaction.

Another sidenote: HD wallets with 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Tim Ruffing via bitcoin-dev]

On Wed, 2018-01-24 at 01:52 +, Andrew Poelstra via bitcoin-dev
wrote:
> 
> > They are. But I don't believe that is relevant; the attacker would
> > simply steal the coins on spend.
> 
> 
> Then the system would need to be hardforked to allow spending through
> a
> quantum-resistant ZKP of knowledge of the hashed public key. I expect
> that in a post-quantum world there will be demand for such a fork,
> especially if we came into such a world through surprise evidence of
> a discrete log break.
> 

There are simpler ways using consensus / waiting instead of zero-
knowledge, e.g., 

1. Include H(classic_pk, tx) to blockchain, wait until confirmed.
2. Reveal classic_pk, tx

This is taken from my tweet [1] but now I realize that these are
basically Guy Fawkes "signatures" [2]. Joseph Bonneau and Andrew Miller
 [3] had the idea to use this for cryptocurrency without asymmetric
cryptography.

Best,
Tim

[1] https://twitter.com/real_or_random/status/948226830166786048
[2] https://www.cl.cam.ac.uk/~rja14/Papers/fawkes.pdf
[3] http://www.jbonneau.com/doc/BM14-SPW-fawkescoin.pdf

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

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Andrew Poelstra via bitcoin-dev]

On Tue, Jan 23, 2018 at 10:45:06PM +, Gregory Maxwell via bitcoin-dev wrote:
> On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns  wrote:
> > Hmm, at least people can choose not to reuse addresses currently --
> > if everyone were using taproot and that didn't involve hashing the key,
> 
> Can you show me a model of quantum computation that is conjectured to
> be able to solve the discrete log problem but which would take longer
> than fractions of a second to do so? Quantum computation has to occur
> within the coherence lifetime of the system.
> 
> > way for individuals to hedge against quantum attacks in case they're ever 
> > feasible, at least that I can see (well, without moving their funds out of 
> > bitcoin anyway)?
> 
> By using scriptpubkeys with actual security against quantum computers
> instead of snake-oil.
> 
> > (It seems like using the point at infinity wouldn't work because
> 
> Indeed, that doesn't work.
> 
> > that when quantum attacks start approaching feasibility. If funds are
> > being held in reused addresses over the long term, that would be more
> 
> They are. But I don't believe that is relevant; the attacker would
> simply steal the coins on spend.


Then the system would need to be hardforked to allow spending through a
quantum-resistant ZKP of knowledge of the hashed public key. I expect
that in a post-quantum world there will be demand for such a fork,
especially if we came into such a world through surprise evidence of
a discrete log break.

-- 
Andrew Poelstra
Mathematics Department, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

"A goose alone, I suppose, can know the loneliness of geese
 who can never find their peace,
 whether north or south or west or east"
   --Joanna Newsom



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: Privacy preserving switchable scripting

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 10:22 PM, Anthony Towns  wrote:
> Hmm, at least people can choose not to reuse addresses currently --
> if everyone were using taproot and that didn't involve hashing the key,

Can you show me a model of quantum computation that is conjectured to
be able to solve the discrete log problem but which would take longer
than fractions of a second to do so? Quantum computation has to occur
within the coherence lifetime of the system.

> way for individuals to hedge against quantum attacks in case they're ever 
> feasible, at least that I can see (well, without moving their funds out of 
> bitcoin anyway)?

By using scriptpubkeys with actual security against quantum computers
instead of snake-oil.

> (It seems like using the point at infinity wouldn't work because

Indeed, that doesn't work.

> that when quantum attacks start approaching feasibility. If funds are
> being held in reused addresses over the long term, that would be more

They are. But I don't believe that is relevant; the attacker would
simply steal the coins on spend.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Anthony Towns via bitcoin-dev]

On Tue, Jan 23, 2018 at 01:15:38PM +, Gregory Maxwell wrote:
> On Tue, Jan 23, 2018 at 6:44 AM, Anthony Towns  wrote:
> > Is this really intended as paying directly to a pubkey, instead of a
> > pubkey hash?
> > If so, isn't that a step backwards with regard to resistance to quantum
> > attacks against ECC?
> Considering the considerable level of address reuse -- I recall prior
> stats that a majority of circulating funds are on addresses that had
> previously been used, on top of the general race limitations-- I am
> now dubious to the idea that hashing provides any kind of meaningful
> quantum resistance and somewhat regret introducing that meme to the
> space in the first place. If we considered quantum resistance a
> meaningful concern we should address that specifically.  --- so I
> don't think that should be a factor that drives a decision here.

Hmm, at least people can choose not to reuse addresses currently --
if everyone were using taproot and that didn't involve hashing the key,
there would be no way for individuals to hedge against quantum attacks
in case they're ever feasible, at least that I can see (well, without
moving their funds out of bitcoin anyway)?

Even "X + H(X|script)g" with X being a random point would end up
attackable, since that would almost always end up corresponding with a
valid public key that a successful attack could then find a private key
for.

(It seems like using the point at infinity wouldn't work because 
P = 0+H(0||S)g = H(0||S)g, so as soon as you tried to spend it via S,
someone watching the mempool would know H(0||S), which is the secret key
for P, and be able to spend it via the pubkey path -- no quantum crypto
needed. Or am I missing something?)

Also, if the people currently reusing addresses tend to cycle the funds
through fairly quickly anyway, they might be able to simply stop doing
that when quantum attacks start approaching feasibility. If funds are
being held in reused addresses over the long term, that would be more
of a problem though...

> When collision resistance is needed (as I think it clearly is for
> taproot) you don't get a space savings in the txout from hashing, so
> there is an argument to use the public key directly at least... but
> it's worth considering.  Direct SPK use is also adventitious for being
> able to efficiently ZKP over the UTXO set, e.g. for private solvency
> proofs, but it isn't absolutely mandatory for that (one can hash
> inside the proof, but it's slower).

Yeah, that was one of the assumptions for
http://www.jbonneau.com/doc/DBBCB15-CCS-provisions.pdf iirc. 

(Also, pretty sure you mean "advantageous", but at least I learnt a new
word today)

Cheers,
aj

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

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 9:23 PM, Matt Corallo via bitcoin-dev
 wrote:
> The issue with that approach without support for the privacy-encouraging
> wrapper proposed by Greg here is that it encourages adoption halfway and
> destroys a lot of the value of the apparent-script monoculture for privacy
> preservation. Greg's proposal here doesn't change the format of any specific
> MAST implementation, but instead adds the privacy wrapper that I always felt
> was missing in existing proposals, without any real additional overhead in
> many use-cases!
>
> Indeed, permissionless innovation is important, but the huge advantage of
> providing the privacy wrapper by default here is absolutely massive to the
> ecosystem and should not be handwaved away for vague possibly-advantages.

Even if to someone who didn't care about anyone's privacy at all,
non-taproot is simply inefficient.  In the (I argue) overwhelmingly
common case of everyone-agrees simple hash based branching requires a
30% overhead to communicate the commitment to the untaken branch (and
worse in the case of extensive aggregation).  I don't think an
argument can be sustained in favor of that kind of communications
overhead.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Matt Corallo via bitcoin-dev]

The issue with that approach without support for the privacy-encouraging 
wrapper proposed by Greg here is that it encourages adoption halfway and 
destroys a lot of the value of the apparent-script monoculture for privacy 
preservation. Greg's proposal here doesn't change the format of any specific 
MAST implementation, but instead adds the privacy wrapper that I always felt 
was missing in existing proposals, without any real additional overhead in many 
use-cases!

Indeed, permissionless innovation is important, but the huge advantage of 
providing the privacy wrapper by default here is absolutely massive to the 
ecosystem and should not be handwaved away for vague possibly-advantages.

Matt

On January 23, 2018 2:39:37 PM UTC, Mark Friedenbach  
wrote:
>I had the opposite response in private, which I will share here. As
>recently as Jan 9th feedback on BIP 117 was shared on this list by
>Pieter Wuille and others suggesting we adopt native MAST template
>instead of the user programmable combination of BIPs 116 and 117. Part
>of my response then was, I quote:
>
>I havent the hubris to suggest that we know exactly what a templated
>MAST *should* look like. It's not used in production anywhere. Even if
>we did have the foresight, the tail-call semantics allow for other
>constructions besides MAST and for the sake of the future we should
>allow such permission-less innovation. The proper sequence of events
>should be to enable features in a generic way, and then to create
>specialized templates to save space for common constructions. Not the
>other way around. [1]
>
>I take this advance as further evidence in favor of this view. As
>recently as 24 hours ago if you had asked what a native-MAST template
>would have looked like, the answer would have been something like
>Johnson Lau’s BIP 114, with some quibbling over details. Taproot is a
>clearly superior approach. But is it optimal? I don’t think we can
>claim that now. Optimality of these constructs isn’t something easily
>proven, with the nearest substitute being unchanging consensus over
>extended periods of time.
>
>Every time we add an output type specialization, we introduce a new
>codepath in the core of the script consensus that must be maintained
>forever. Take P2SH: from this point forward there is no reason to use
>it in new applications, ever. But it must be forever supported. In an
>alternate universe we could have deployed a native MAST proposal, like
>BIP 114, only to have Taproot-like schemes discovered after activation.
>That would have been a sucky outcome. It is still the case that we
>could go for Taproot right now, and then in six months or a year’s time
>we find an important tweak or a different approach entirely that is
>even better, but the activation process had already started. That would
>be a sucky outcome we haven’t avoided yet.
>
>This is not an argument against template specialization for common code
>paths, especially those which increase fungibility of coins. I do think
>we should have a native MAST template eventually, using Taproot or
>something better. However if I may be allowed I will make an educated
>guess about the origin of Taproot: I think it’s no coincidence that
>Greg had this insight and/or wrote it up simultaneous with a push by
>myself and others for getting MAST features into bitcoin via BIPs 98,
>116, and 117, or 114. Cryptographers tend to only think up solutions to
>problems that are on their minds. And the problems on most people’s
>minds are primarily those that are deployable today, or otherwise
>near-term applicable.
>
>BIPS 116 and 117 each provide a reusable component that together
>happens to enable a generic form of MAST. Even without the workarounds
>required to avoid CLEANSTACK violations, the resulting MAST template is
>larger than what is possible with specialization. However let’s not
>forget that (1) they also enable other applications like honeypots, key
>trees, and script delegation; and relevant to this conversation (2)
>they get the MAST feature available for use in production by the wider
>community. I don’t think I’d personally be willing to bet that we found
>the optimal MAST structure in Greg’s Taproot until we have people doing
>interesting production work like multisig wallets, lightning protocol,
>and the next set of consensus features start putting it into production
>and exploring edge cases. We may find ways Taproot can be tweaked to
>enable other applications (like encoding a hash preimage as well) or
>simplify obscure corner cases.
>
>I feel quite strongly that the correct approach is to add support for
>generic features to accomplish the underlying goal in a user
>programmable way, and THEN after activation and some usage consider
>ways in which common use cases can be made more efficient through
>output specialization. To take a more obvious example, lightning
>protocol is still an active area or research and I think it is
>abundantly clear that we 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Greg Sanders via bitcoin-dev]

Interesting parallels to current Elements sidechain peg-in functionality.
User tweaks the watchmen(BTC holder) pubkey using P2CH, committing to a
script that is used on the *sidechain side* as spending authorization for
that bitcoin output rather than mainnet.

I think composing the two can be done as:

P = C' + H(C'||S')G + H(C||S)G

where C is redefined as `C' + H(C'||S')G`, which for Bitcoin consensus
purposes is just a single pubkey.



On Mon, Jan 22, 2018 at 7:30 PM, Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
> areas: efficiency and privacy. Efficiency because unexecuted forks of
> a script can avoid ever hitting the chain, and privacy because hiding
> unexecuted code leaves scripts indistinguishable to the extent that
> their only differences are in the unexecuted parts.
>
> As Mark Friedenbach and others have pointed out before it is almost
> always the case that interesting scripts have a logical top level
> branch which allows satisfaction of the contract with nothing other
> than a signature by all parties.  Other branches would only be used
> where some participant is failing to cooperate. More strongly stated,
> I believe that _any_ contract with a fixed finite participant set
> upfront can be and should be represented as an OR between an N-of-N
> and whatever more complex contract you might want to represent.
>
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments. Otherwise, if the
> anonymity set of fancy usage is only other fancy usage it may not be
> very large in practice. One suggestion has been that ordinary
> checksig-only scripts should include a dummy branch for the rest of
> the tree (e.g. a random value hash), making it look like there are
> potentially alternative rules when there aren't really.  The negative
> side of this is an additional 32-byte overhead for the overwhelmingly
> common case which doesn't need it.  I think the privacy gains are
> worth doing such a thing, but different people reason differently
> about these trade-offs.
>
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.
>
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
>
> Alice has public A, Bob has pubkey B.
>
> We compute the 2-of-2 aggregate key C = A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
>
> We form our timelock script S =  " OP_CSV OP_DROP B
> OP_CHECKSIGVERIFY"
>
> Now we tweak C to produce P which is the key we'll publish: P = C +
> H(C||S)G.
>
> (This is the attack hardened pay-to-contract construction described in [2])
>
> Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].
>
> Now Alice and Bob-- assuming they are both online and agree about the
> resolution of their contract-- can jointly form a 2 of 2 signature for
> P, and spend as if it were a payment to a single party (one of them
> just needs to add H(C||S) to their private key).
>
> Alternatively, the Taproot consensus rules would allow this script to
> be satisfied by someone who provides the network with C (the original
> combined pubkey), S, and does whatever S requires-- e.g. passes the
> CSV check and provides Bob's signature. With this information the
> network can verify that C + H(C||S) == P.
>
> So in the all-sign case there is zero overhead; and no one can tell
> that the contract alternative exists. In the alternative redemption
> branch the only overhead is revealing the original combined pubkey
> and, of course, the existence of the contract is made public.
>
> This composes just fine with whatever other merkelized script system
> we might care to use, as the S can be whatever kind of data we want,
> including the root of some tree.
>
> My example shows 2-of-2 but it works the same for any number of
> participants (and with setup interaction any threshold of
> participants, so long as you don't mind an inability to tell which
> members signed off).
>
> The verification computational complexity of signature path is
> obviously the same as any other plain signature (since its
> indistinguishable). Verification of the branch redemption requires a
> hash and a multiplication with a constant point which is strictly more
> efficient than a signature verification and could be efficiently fused
> into batch signature validation.
>
> The nearest competitor to this idea that I can come up with would
> supporting a simple delegation where the output can be spent by the
> named 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Mark Friedenbach via bitcoin-dev]

I had the opposite response in private, which I will share here. As recently as 
Jan 9th feedback on BIP 117 was shared on this list by Pieter Wuille and others 
suggesting we adopt native MAST template instead of the user programmable 
combination of BIPs 116 and 117. Part of my response then was, I quote:

I havent the hubris to suggest that we know exactly what a templated MAST 
*should* look like. It's not used in production anywhere. Even if we did have 
the foresight, the tail-call semantics allow for other constructions besides 
MAST and for the sake of the future we should allow such permission-less 
innovation. The proper sequence of events should be to enable features in a 
generic way, and then to create specialized templates to save space for common 
constructions. Not the other way around. [1]

I take this advance as further evidence in favor of this view. As recently as 
24 hours ago if you had asked what a native-MAST template would have looked 
like, the answer would have been something like Johnson Lau’s BIP 114, with 
some quibbling over details. Taproot is a clearly superior approach. But is it 
optimal? I don’t think we can claim that now. Optimality of these constructs 
isn’t something easily proven, with the nearest substitute being unchanging 
consensus over extended periods of time.

Every time we add an output type specialization, we introduce a new codepath in 
the core of the script consensus that must be maintained forever. Take P2SH: 
from this point forward there is no reason to use it in new applications, ever. 
But it must be forever supported. In an alternate universe we could have 
deployed a native MAST proposal, like BIP 114, only to have Taproot-like 
schemes discovered after activation. That would have been a sucky outcome. It 
is still the case that we could go for Taproot right now, and then in six 
months or a year’s time we find an important tweak or a different approach 
entirely that is even better, but the activation process had already started. 
That would be a sucky outcome we haven’t avoided yet.

This is not an argument against template specialization for common code paths, 
especially those which increase fungibility of coins. I do think we should have 
a native MAST template eventually, using Taproot or something better. However 
if I may be allowed I will make an educated guess about the origin of Taproot: 
I think it’s no coincidence that Greg had this insight and/or wrote it up 
simultaneous with a push by myself and others for getting MAST features into 
bitcoin via BIPs 98, 116, and 117, or 114. Cryptographers tend to only think up 
solutions to problems that are on their minds. And the problems on most 
people’s minds are primarily those that are deployable today, or otherwise 
near-term applicable.

BIPS 116 and 117 each provide a reusable component that together happens to 
enable a generic form of MAST. Even without the workarounds required to avoid 
CLEANSTACK violations, the resulting MAST template is larger than what is 
possible with specialization. However let’s not forget that (1) they also 
enable other applications like honeypots, key trees, and script delegation; and 
relevant to this conversation (2) they get the MAST feature available for use 
in production by the wider community. I don’t think I’d personally be willing 
to bet that we found the optimal MAST structure in Greg’s Taproot until we have 
people doing interesting production work like multisig wallets, lightning 
protocol, and the next set of consensus features start putting it into 
production and exploring edge cases. We may find ways Taproot can be tweaked to 
enable other applications (like encoding a hash preimage as well) or simplify 
obscure corner cases.

I feel quite strongly that the correct approach is to add support for generic 
features to accomplish the underlying goal in a user programmable way, and THEN 
after activation and some usage consider ways in which common use cases can be 
made more efficient through output specialization. To take a more obvious 
example, lightning protocol is still an active area or research and I think it 
is abundantly clear that we don’t know yet what the globally optimal layer-2 
caching protocol will be, even if we have educated guesses as to its broad 
structure. A proposal right now to standardize a more compact lightning script 
type would be rightly rejected. It is less obvious but just as true that the 
same should hold for MAST.

I have argued these points before in favor of permission less innovation first, 
then application specialization later, in [1] and at the end of the rather long 
email [2]. I hope you can take the time to read those if you still feel we 
should take a specialized template approach instead of the user programmable 
BIPSs 116 and 117.

[1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015537.html
 

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 6:44 AM, Anthony Towns  wrote:
> Is this really intended as paying directly to a pubkey, instead of a
> pubkey hash?
>
> If so, isn't that a step backwards with regard to resistance to quantum
> attacks against ECC?

You're reading too much into a description of the idea. It's not a BIP
or a spec; I tried to provide enough details to make the general idea
concrete. I didn't dive into details or optimizations (for example,
you can use this with a "no EC redemption path" by special casing
empty C as the point at infinity, and you'd have an output that was
indistinguishable until spend... yadda yadda).

Considering the considerable level of address reuse -- I recall prior
stats that a majority of circulating funds are on addresses that had
previously been used, on top of the general race limitations-- I am
now dubious to the idea that hashing provides any kind of meaningful
quantum resistance and somewhat regret introducing that meme to the
space in the first place. If we considered quantum resistance a
meaningful concern we should address that specifically.  --- so I
don't think that should be a factor that drives a decision here.

When collision resistance is needed (as I think it clearly is for
taproot) you don't get a space savings in the txout from hashing, so
there is an argument to use the public key directly at least... but
it's worth considering.  Direct SPK use is also adventitious for being
able to efficiently ZKP over the UTXO set, e.g. for private solvency
proofs, but it isn't absolutely mandatory for that (one can hash
inside the proof, but it's slower).
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Anthony Towns via bitcoin-dev]

On Tue, Jan 23, 2018 at 12:30:06AM +, Gregory Maxwell via bitcoin-dev wrote:
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments.

> Now we tweak C to produce P which is the key we'll publish: P = C + H(C||S)G.
> (This is the attack hardened pay-to-contract construction described in [2])
> Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].

Is this really intended as paying directly to a pubkey, instead of a
pubkey hash?

If so, isn't that a step backwards with regard to resistance to quantum
attacks against ECC?

Paying direct to pubkey doesn't seem quite enough to make pay-to-taproot
cheaper than p2wpkh: the extra 12 bytes in the scriptPubKey would need
you to reduce the witness by 48 bytes to maintain the weight, but I think
you'd only be saving 33 bytes by not having to reveal the pubkey, and
another 6-7 bytes by having a tighter signature encoding than DER. Still,
that's pretty close with a difference of only a couple of vbytes per
input by my count.

If it were "pay-to-taproot-hash", then presuming taproot hashes were 256
bit, then p2wpkh would be a full 12 vbytes cheaper due to the shorter
hash. That might make it hard to maximise the anonymity set. I suppose
a small penalty/discount could be added to align the economic incentives
though.

I wonder how this interacts with segwit versioning. I think you'd want
to have taproot be versioned overall so that you could cope with moving
to a new signing method (different curve, or something non-ECC based)
eventually, and segwit versioning will handle that already; but maybe
it would also be a good idea to also have "S" include a version, that
could be bumped to add new features to script, but left hidden within
the hash so that the fact you're using new (or old) features is only
revealed when it has to be.

Those nits aside, this seems great.

Cheers,
aj

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

Re: [bitcoin-dev] Taproot: Privacy preserving switchable scripting

[Chris Belcher via bitcoin-dev]

This sounds like a useful idea for improving the privacy of coinswap.
Traditionally coinswap mixing had an anonymity set related to the number
of multisig transactions being used on the blockchain. With the new tech
of Schnorr, MAST and now this Taproot, with sufficient adoption
coinswap's anonymity set could be much higher, potentially including
almost every other on-chain transaction.

[1] https://bitcointalk.org/index.php?topic=321228.0
[2] https://github.com/AdamISZ/CoinSwapCS

On 23/01/18 00:30, Gregory Maxwell via bitcoin-dev wrote:
> Interest in merkelized scriptPubKeys (e.g. MAST) is driven by two main
> areas: efficiency and privacy. Efficiency because unexecuted forks of
> a script can avoid ever hitting the chain, and privacy because hiding
> unexecuted code leaves scripts indistinguishable to the extent that
> their only differences are in the unexecuted parts.
> 
> As Mark Friedenbach and others have pointed out before it is almost
> always the case that interesting scripts have a logical top level
> branch which allows satisfaction of the contract with nothing other
> than a signature by all parties.  Other branches would only be used
> where some participant is failing to cooperate. More strongly stated,
> I believe that _any_ contract with a fixed finite participant set
> upfront can be and should be represented as an OR between an N-of-N
> and whatever more complex contract you might want to represent.
> 
> One point that comes up while talking about merkelized scripts is can
> we go about making fancier contract use cases as indistinguishable as
> possible from the most common and boring payments. Otherwise, if the
> anonymity set of fancy usage is only other fancy usage it may not be
> very large in practice. One suggestion has been that ordinary
> checksig-only scripts should include a dummy branch for the rest of
> the tree (e.g. a random value hash), making it look like there are
> potentially alternative rules when there aren't really.  The negative
> side of this is an additional 32-byte overhead for the overwhelmingly
> common case which doesn't need it.  I think the privacy gains are
> worth doing such a thing, but different people reason differently
> about these trade-offs.
> 
> It turns out, however, that there is no need to make a trade-off.  The
> special case of a top level "threshold-signature OR
> arbitrary-conditions" can be made indistinguishable from a normal
> one-party signature, with no overhead at all, with a special
> delegating CHECKSIG which I call Taproot.
> 
> Let's say we want to create a coin that can be redeemed by either
> Alice && Bob   or by CSV-timelock && Bob.
> 
> Alice has public A, Bob has pubkey B.
> 
> We compute the 2-of-2 aggregate key C = A + B.  (Simplified; to
> protect against rogue key attacks you may want to use the MuSig key
> aggregation function [1])
> 
> We form our timelock script S =  " OP_CSV OP_DROP B 
> OP_CHECKSIGVERIFY"
> 
> Now we tweak C to produce P which is the key we'll publish: P = C + H(C||S)G.
> 
> (This is the attack hardened pay-to-contract construction described in [2])
> 
> Then we pay to a scriptPubKey of [Taproot supporting version] [EC point P].
> 
> Now Alice and Bob-- assuming they are both online and agree about the
> resolution of their contract-- can jointly form a 2 of 2 signature for
> P, and spend as if it were a payment to a single party (one of them
> just needs to add H(C||S) to their private key).
> 
> Alternatively, the Taproot consensus rules would allow this script to
> be satisfied by someone who provides the network with C (the original
> combined pubkey), S, and does whatever S requires-- e.g. passes the
> CSV check and provides Bob's signature. With this information the
> network can verify that C + H(C||S) == P.
> 
> So in the all-sign case there is zero overhead; and no one can tell
> that the contract alternative exists. In the alternative redemption
> branch the only overhead is revealing the original combined pubkey
> and, of course, the existence of the contract is made public.
> 
> This composes just fine with whatever other merkelized script system
> we might care to use, as the S can be whatever kind of data we want,
> including the root of some tree.
> 
> My example shows 2-of-2 but it works the same for any number of
> participants (and with setup interaction any threshold of
> participants, so long as you don't mind an inability to tell which
> members signed off).
> 
> The verification computational complexity of signature path is
> obviously the same as any other plain signature (since its
> indistinguishable). Verification of the branch redemption requires a
> hash and a multiplication with a constant point which is strictly more
> efficient than a signature verification and could be efficiently fused
> into batch signature validation.
> 
> The nearest competitor to this idea that I can come up with would
> supporting a simple delegation where the output can be spent by the
>