From: Andrew Poelstra <apoelstra@wpsoftware•net>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Should Graftroot be optional?
Date: Wed, 23 May 2018 17:52:39 +0000 [thread overview]
Message-ID: <20180523175239.GR14992@boulet.lan> (raw)
In-Reply-To: <20180523135013.GN14992@boulet.lan>
[-- Attachment #1: Type: text/plain, Size: 3112 bytes --]
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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 455 bytes --]
next prev parent reply other threads:[~2018-05-23 17:52 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-22 18:17 Pieter Wuille
2018-05-23 6:15 ` ZmnSCPxj
2018-05-23 13:50 ` Andrew Poelstra
2018-05-23 17:52 ` Andrew Poelstra [this message]
2018-05-25 9:46 ` Johnson Lau
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=20180523175239.GR14992@boulet.lan \
--to=apoelstra@wpsoftware$(echo .)net \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox