From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 9989DDB1 for ; Fri, 25 May 2018 09:46:40 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender-of-o51.zoho.com (sender-of-o51.zoho.com [135.84.80.216]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8B9496D3 for ; Fri, 25 May 2018 09:46:39 +0000 (UTC) Received: from [10.8.0.101] (n218103136198.netvigator.com [218.103.136.198]) by mx.zohomail.com with SMTPS id 152724159305895.52026801619877; Fri, 25 May 2018 02:46:33 -0700 (PDT) From: Johnson Lau Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\)) Date: Fri, 25 May 2018 17:46:29 +0800 References: <20180523135013.GN14992@boulet.lan> <20180523175239.GR14992@boulet.lan> To: Andrew Poelstra , bitcoin-dev In-Reply-To: <20180523175239.GR14992@boulet.lan> Message-Id: X-Mailer: Apple Mail (2.3445.5.20) X-ZohoMailClient: External X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Should Graftroot be optional? X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 25 May 2018 09:46:40 -0000 While you have rescind your concern, I=E2=80=99d like to point out that = it=E2=80=99s 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 = wrote: >=20 > On Wed, May 23, 2018 at 01:50:13PM +0000, Andrew Poelstra via = bitcoin-dev wrote: >>=20 >> 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. >>=20 >> 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? >>=20 >> (I also had the same concern about signature aggregation. It seems = like it's >> pretty hard to preserve the "one signature =3D at most one input" = invariant of >> Bitcoin, but I think it's important that it is preserved, at least = for >> outputs that need it.) >>=20 >> 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. >>=20 >> [1] https://github.com/apoelstra/scriptless-scripts/pull/1=20 >>=20 >=20 > On further thought, I rescind this concern (ditto for SIGHASH_NOINPUT) = (but > not for aggregate sigs, they still interact badly with blind = signatures). >=20 > 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). >=20 > Here is a simple scheme that does this: >=20 > 1. Signer provides a nonce R =3D kG >=20 > 2. Challenger computes bip32 tweak h, chooses blinders alpha and = beta, > and computes: > R' =3D R + alpha*G + beta*P > e =3D H(P + hG || R' || tx) > e' =3D e + beta > and sends e' to the signer. >=20 > 3. Signer replies with s =3D k + xe' (=3D k + beta*x + (x + h)e - he) >=20 > 4. Challenger unblinds this as s' =3D s + alpha + he >=20 > (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.) >=20 > 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. >=20 >=20 > Andrew >=20 >=20 > [1] = http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3D8ECEF929559865F= D68D1D873555D18FE?doi=3D10.1.1.68.9836&rep=3Drep1&type=3Dpdf >=20 >=20 > --=20 > Andrew Poelstra > Mathematics Department, Blockstream > Email: apoelstra at wpsoftware.net > Web: https://www.wpsoftware.net/andrew >=20 > "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 >=20 > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev