From: Gregory Maxwell <greg@xiph•org>
To: "Russell O'Connor" <roconnor@blockstream•io>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Schnorr signatures BIP
Date: Fri, 6 Jul 2018 22:00:28 +0000 [thread overview]
Message-ID: <CAAS2fgTM+8mORcgjGdQxGxMkXjW7NOqByZwD1_VEad80ofVObA@mail.gmail.com> (raw)
In-Reply-To: <CAMZUoKks9of0oWdn8J=601cY2PMf+EV4e=PeWpDAXPcGPNFkRw@mail.gmail.com>
On Fri, Jul 6, 2018 at 9:05 PM, Russell O'Connor via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> 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.]
next prev parent reply other threads:[~2018-07-06 22:00 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-06 18:08 Pieter Wuille
2018-07-06 21:05 ` Russell O'Connor
2018-07-06 22:00 ` Gregory Maxwell [this message]
2018-07-06 22:01 ` Gregory Maxwell
2018-07-08 14:36 ` Russell O'Connor
2018-07-14 15:42 ` Sjors Provoost
2018-07-14 21:20 ` Pieter Wuille
2018-08-04 12:22 ` Russell O'Connor
2018-08-05 14:33 ` Russell O'Connor
2018-08-06 8:39 ` Anthony Towns
2018-08-06 14:00 ` Russell O'Connor
2018-08-06 21:12 ` Tim Ruffing
2018-08-12 16:37 ` Andrew Poelstra
2018-08-29 12:09 ` Erik Aronesty
2018-09-03 0:05 ` Andrew Poelstra
2018-09-05 12:26 ` Erik Aronesty
2018-09-05 13:05 ` Andrew Poelstra
2018-09-05 13:14 ` Erik Aronesty
2018-09-05 15:35 ` Gregory Maxwell
2018-09-11 16:34 ` Erik Aronesty
2018-09-11 17:00 ` Gregory Maxwell
2018-09-11 17:20 ` Erik Aronesty
2018-09-11 17:27 ` Gregory Maxwell
2018-09-11 17:37 ` Erik Aronesty
2018-09-11 17:51 ` Gregory Maxwell
2018-09-11 18:30 ` Erik Aronesty
2018-09-13 18:46 ` Andrew Poelstra
2018-09-13 20:20 ` Erik Aronesty
2018-09-14 14:38 ` Andrew Poelstra
2018-09-20 21:12 ` Russell O'Connor
2018-07-07 2:47 Артём Литвинович
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=CAAS2fgTM+8mORcgjGdQxGxMkXjW7NOqByZwD1_VEad80ofVObA@mail.gmail.com \
--to=greg@xiph$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=roconnor@blockstream$(echo .)io \
/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