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 4BBE0DBA for ; Fri, 6 Jul 2018 22:00:30 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f177.google.com (mail-ua0-f177.google.com [209.85.217.177]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D6ADC70B for ; Fri, 6 Jul 2018 22:00:29 +0000 (UTC) Received: by mail-ua0-f177.google.com with SMTP id 59-v6so8420830uas.5 for ; Fri, 06 Jul 2018 15:00:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=QM7d3KHty4PnauQxtF5h8Dk5JafDJ+AdN5AWAReTMa0=; b=dvI8GTMmXHi+H54+E1qC3WwSB5XDrOFj1rUAPUIc0xwaGDB96xkdo7WIKCXx2rCwyo hIGtXudxBi9YrR9LapGVpFx2FXjhRJAdGLu9AXGdXiePDxxPmtKzY6LyoHwUbjp1DVdJ fjWAqyWFU2oZHfpNY3riEn4PFuaekb9ewwkoiN+HPO2+AtE7//0ybw97m0bnd+9T+qau IXSFYwhZJ1Xw/2Hhe4koxZVdXg4PSG3SUI6MvNbIJD42gUz7VgURhjYWCZZM3xccgxYK 7qsHiqqeKrAf1vVyJoPi7faD8gN+BZQ5hgraXylqI66kCDrzXeAezRjfhuPV7PoH/9CX 7alQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=QM7d3KHty4PnauQxtF5h8Dk5JafDJ+AdN5AWAReTMa0=; b=as9h9Y/QeI9toj1ME24zTj82Zn2nqim3aGMA7mAdG5xGaSuxFVpw3Qz50agb33/1ca v2SKyvIXkt4W88R3SIpQzGdmXzSfoS/rnCAaTdwCbe0oslipsqPMyRCV+hO8qL1rbNIX QE6+5BvCwg5QQ8OBqD57b8/33CcmS2dvek/zmW6n8qvoPZU8aqzx5YMs2OE3NWnKqzMh NjO5WTWzo2w6zDBRy9V8OckWjiU5BkM9apT+PoT0M76XNwcykqvK6KIz5nuREMhH7p9f QFCHEjs0u0jnzHyypAdHbSyx2/XycPZ9efIAhvw8vWth3Vz8VlhjvJVsW+s643i0+A5b zYSg== X-Gm-Message-State: APt69E1esT2M0dVANzA1h+0cUKUZHjUbqnLP7D7OwAfgkjEQhe446EDo prGkklP9LH+d1g4V6NPSlBbLV1YF3HQTp7FVP0M= X-Google-Smtp-Source: AAOMgpc5XfkIeYwicdojDQhyzBs2uhPq+dO90lo97CUGcNoOs+lCHI5YY6Xxl/yw/exF/RACzwcSf4vq44Wmt95c504= X-Received: by 2002:a9f:3b06:: with SMTP id i6-v6mr7251007uah.75.1530914428868; Fri, 06 Jul 2018 15:00:28 -0700 (PDT) MIME-Version: 1.0 Sender: gmaxwell@gmail.com Received: by 2002:a67:51c9:0:0:0:0:0 with HTTP; Fri, 6 Jul 2018 15:00:28 -0700 (PDT) In-Reply-To: References: From: Gregory Maxwell Date: Fri, 6 Jul 2018 22:00:28 +0000 X-Google-Sender-Auth: whwe5gBOKEOYLXCNNo0zfSLym0w Message-ID: To: "Russell O'Connor" , Bitcoin Protocol Discussion Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, 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] Schnorr signatures BIP 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, 06 Jul 2018 22:00:30 -0000 On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev wrote: > If the inputs to hash were reordered as hash(bytes(dG) || bytes(x(R)) || m) > then there is an opportunity for SHA256 expander to be partially prefilled > for a fixed public key. This could provide a little benefit, especially > when multiple signatures for a single public key need to be generated and/or > verified. If all things are otherwise equal, perhaps this alternate order > is better. There is a minor design preference to have message before nonce when H() is a MD-style hash function. Say the attacker knows some weakness in H and can find pairs of messages m and m' so that the compression function results in the same midstate. He could then ask you to sign m but get a signature that also works for m'. If the signer controlled R value comes first, then this doesn't work. The pubkey being where it is in the current design just follows from the idea that it is just logically prepended on the message. I don't think the pubkey is sufficiently attacker controlled that the above argument would apply, so H(P || R.x || m) would be okay. BUT, the sha256 compression function reads 64 bytes at a time. PRM would not let you precompute a whole compression function run, but instead would just let you hardwire part of the expander in a pubkey dependant way-- an optimization I'm pretty confident virtually no one would use. (Hardwiring to a constant, yes. Hardwiring to a reused dynamic value that comes in from the network, no) If instead the hash function were defined as using 31 zeros then P||R||m (or P || 31 zeros bytes || R || m, I'm not sure what would be better), an entire midstate could be cached for different pubkeys. m is often 32 bytes, sadly- - but the final compression run in that case would only be the constant update with the length.... and almost-all-zeros + constant length, is an easy optimization. (Bitcoin core even has it for computing sha256(sha256())). [I'm not really sure if I was clear, so I'll try TLDRing it: I think optimizing sha256 where part of the input is constant is realistic, optimizing midstate reuse is realistic, optimizing where part is reused is less realistic. If we insert padding, and put P first, we can make it possible to midstate cache P, and the 'extra' compression function run ends up with all constant input, so it could be made faster.]