public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Johnson Lau <jl2012@xbt.hk>
To: Andrew Poelstra <apoelstra@wpsoftware.net>,
	bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Should Graftroot be optional?
Date: Fri, 25 May 2018 17:46:29 +0800	[thread overview]
Message-ID: <AE21F8B7-2763-40CA-8A61-F862A80E18BB@xbt.hk> (raw)
In-Reply-To: <20180523175239.GR14992@boulet.lan>

While you have rescind your concern, I’d like to point out that it’s strictly a problem of SIGHASH_NOINPUT, not graftroot (or script delegation in general).

For example, we could modify graftroot. Instead of signing the (script), we require it to sign (outpoint | script). That means a graftroot signature would never be valid for more than one UTXO.

> On 24 May 2018, at 1:52 AM, Andrew Poelstra via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> On Wed, May 23, 2018 at 01:50:13PM +0000, Andrew Poelstra via bitcoin-dev wrote:
>> 
>> Graftroot also break blind signature schemes. Consider a protocol such as [1]
>> where some party has a bunch of UTXOs all controlled (in part) by the same
>> key X. This party produces blind signatures on receipt of new funds, and can
>> only verify the number of signatures he produces, not anything about what he
>> is signing.
>> 
>> BTW, the same concern holds for SIGHASH_NOINPUT, which I'd also like to be
>> disable-able. Maybe we should extend one of ZmnSCPxj's suggestions to include
>> a free "flags" byte or two in the witness?
>> 
>> (I also had the same concern about signature aggregation. It seems like it's
>> pretty hard to preserve the "one signature = at most one input" invariant of
>> Bitcoin, but I think it's important that it is preserved, at least for
>> outputs that need it.)
>> 
>> Or maybe, since it appears it will require a space hit to support optional
>> graftroot anyway, we should simply not include it in a proposal for Taproot,
>> since there would be no opportunity cost (in blockchain efficiency) to doing
>> it later.
>> 
>> [1] https://github.com/apoelstra/scriptless-scripts/pull/1 
>> 
> 
> On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) (but
> not for aggregate sigs, they still interact badly with blind signatures).
> 
> As long as graftroot (and NOINPUT) sigs commit to the public key, it is
> possible for a server to have unique keys for every output, even while
> retaining the same private key, and thereby ensure that "one sig can spend
> only one output" holds. To do this, suppose the server has a BIP32 xpubkey
> (xG, cc). A blind signer using the private key x can be made to sign not
> only for xG, but also for any publicly-derived child keys of (xG, cc).
> 
> Here is a simple scheme that does this:
> 
>  1. Signer provides a nonce R = kG
> 
>  2. Challenger computes bip32 tweak h, chooses blinders alpha and beta,
>     and computes:
>         R' = R + alpha*G + beta*P
>         e  = H(P + hG || R' || tx)
>         e' = e + beta
>     and sends e' to the signer.
> 
>  3. Signer replies with s = k + xe' (= k + beta*x + (x + h)e - he)
> 
>  4. Challenger unblinds this as s' = s + alpha + he
> 
> (This blind signature scheme is vulnerable to Wagner's attack, though see
> Schnorr 2004 [1] for mitigations that are perfectly compatible with this
> modified BIP32ish scheme.)
> 
> I'm unsure whether key-prefixing is _actually_ necessary for this, but it
> makes the security argument much clearer since the messagehash contains
> some data which can be made unique per-utxo and is committed in the chain.
> 
> 
> Andrew
> 
> 
> [1] http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=8ECEF929559865FD68D1D873555D18FE?doi=10.1.1.68.9836&rep=rep1&type=pdf
> 
> 
> -- 
> 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
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev




  reply	other threads:[~2018-05-25  9:46 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-22 18:17 [bitcoin-dev] Should Graftroot be optional? Pieter Wuille
2018-05-23  6:15 ` ZmnSCPxj
2018-05-23 13:50 ` Andrew Poelstra
2018-05-23 17:52   ` Andrew Poelstra
2018-05-25  9:46     ` Johnson Lau [this message]
2018-05-23 22:06 ` Natanael
2018-05-23 23:45   ` Gregory Maxwell
2018-05-24  9:32     ` Natanael
2018-05-24  1:58 ` Pieter Wuille
2018-05-24  2:08   ` Gregory Maxwell
2018-05-24  9:44     ` Natanael
2018-05-24 12:39       ` Andrew Poelstra
2018-05-25 10:14     ` Johnson Lau
2018-06-01  0:25       ` Pieter Wuille
2018-06-06 12:48         ` Tim Ruffing
2018-06-06 17:04           ` Pieter Wuille
2018-06-06 21:25             ` Tim Ruffing
2018-06-20 12:12               ` ZmnSCPxj
2018-06-20 14:30                 ` Gregory Maxwell
2018-06-21  7:09                   ` ZmnSCPxj
2018-06-27  7:29         ` Anthony Towns

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=AE21F8B7-2763-40CA-8A61-F862A80E18BB@xbt.hk \
    --to=jl2012@xbt.hk \
    --cc=apoelstra@wpsoftware.net \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox