From: Matt Whitlock <bip@mattwhitlock•name>
To: Nikita Schmidt <nikita@megiontechnologies•com>
Cc: bitcoin-development <bitcoin-development@lists•sourceforge.net>
Subject: Re: [Bitcoin-development] Presenting a BIP for Shamir's Secret Sharing of Bitcoin private keys
Date: Fri, 04 Apr 2014 12:03:37 -0400 [thread overview]
Message-ID: <1529077.7WHAYP4Dpn@crushinator> (raw)
In-Reply-To: <CAC7yFxQXn=c7CEC326yMx4bF7Cv7Gc62shS7xU0XvSp5sQSGZw@mail.gmail.com>
On Friday, 4 April 2014, at 5:51 pm, Nikita Schmidt wrote:
> On 4 April 2014 01:42, Matt Whitlock <bip@mattwhitlock•name> wrote:
> > The fingerprint field, Hash16(K), is presently specified as a 16-bit field. Rationale: There is no need to consume 4 bytes just to allow shares to be grouped together. And if someone has more than 100 different secrets, they probably have a good system for managing their shares and won't need the hash anyway.
>
> Right, of course. Sorry, I didn't notice there was an update. Two
> bytes are plenty.
>
> I'm worried however about the dependency on SHA-512, which may be
> stretching it for a tiny embedded application. The other uses of
> HashL can be avoided. We are balancing here between consistency with
> the rest of this proposal, where everything is done via HashL, and
> consistency with the general practice of generating fingerprints with
> SHA-256, like in Base58Check.
I'd be fine with changing the key fingerprint algorithm to something else. Do you like CRC16?
> >> Speaking of encoding, is it not wasteful to allocate three different
> >> application/version bytes just for the sake of always starting with
> >> 'SS'? It would be OK if it were accepted as a BIP, but merely as a
> >> de-facto standard it should aim at minimising future chances of
> >> collision.
> >
> > I agree on principle, however I think the more user-acceptable behavior is for all base58-encoded Shamir shares to begin with a common prefix, such as "SS". Users are accustomed to relying on the prefix of the base58 encoding to understand what the object is: "1" for mainnet pubkey hash, "3" for mainnet script hash, "5" for uncompressed private key, "P" for passphrase-protected private key, etc.
>
> Yes, "5" for uncompressed private key and "K" or "L" for compressed
> private key. One A/VB and three prefixes in base58. Am I the only
> one to see this as a counter-example?
>
> However, thinking about this, I can find logic in wanting to stabilise
> text prefixes at a cost of six A/V bytes (as per the latest spec).
> There are only 58 first characters versus 256 AVBs, so we should
> rather be saving the former.
The type of a base58-encoded object is determined not only by the application/version byte but by the payload length as well. For example, a base58-encoded object with an application/version byte of 0x80 but a payload length of 16 bytes would not be mistakable for a Bitcoin private key, even though AVB 0x80 does denote a Bitcoin private key when the payload length is 32 or 33 bytes. So it's not as simple as saying that this proposal costs 6 AVBs. It really costs one AVB for 18-byte payloads, one AVB for 21-byte payloads, one AVB for 34-byte payloads, one AVB fo 37-byte payloads, one AVB for 66-byte payloads, and one AVB for 69-byte payloads.
> >> What about using the same P256 prime as for the elliptic curve? Just
> >> for consistency's sake.
> >
> > The initial draft of this BIP used the cyclic order (n) of the generator point on the secp256k1 elliptic curve as the modulus. The change to the present scheme was actually done for consistency's sake, so all sizes of secret can use a consistently defined modulus.
>
> Fair enough. Although I would have chosen the field order (p) simply
> because that's how all arithmetic already works in bitcoin. One field
> for everybody. It's also very close to 2^256, although still smaller
> than your maximum prime. Now of course with different bit lengths we
> have to pick one consistency over others.
As Gregory Maxwell pointed out, you can't use p when you're dealing with private keys, as that is the order of the finite field over which the elliptic curve is defined, but private keys are not points on that curve; a private key is a scalar number of times to multiply the generator point. That means you have to use the order of the generator point as the modulus when working with private keys.
> >> Also, I'm somewhat inclined towards using the actual x instead of j in
> >> the encoding. I find it more direct and straightforward to encode the
> >> pair (x, y). And x=0 can denote a special case for future extensions.
> >> There is no technical reason behind this, it's just for (subjective)
> >> clarity and consistency.
> >
> > There is a technical reason for encoding j rather than x[j]: it allows for the first 256 shares to be encoded, rather than only the first 255 shares.
>
> Wow, big deal. It's hard to imagine anyone needing exactly 256
> shares, but who knows. And with j = x (starting from 1) we'd get
> user-friendly share numbering and simpler formulas in the spec and
> possibly in the implementation, with no off-by-one stuff. And M
> instead of M-2...
It's common for implementation limits to be powers of two. I don't foresee any off-by-one errors, as the spec is clear on the value of each byte in the encoding.
next prev parent reply other threads:[~2014-04-04 16:03 UTC|newest]
Thread overview: 90+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-04-03 12:41 Nikita Schmidt
2014-04-03 21:42 ` Matt Whitlock
2014-04-04 13:51 ` Nikita Schmidt
2014-04-04 14:14 ` Gregory Maxwell
2014-04-04 16:05 ` Matt Whitlock
2014-04-04 16:25 ` Gregory Maxwell
2014-04-04 16:36 ` Matt Whitlock
2014-04-04 17:08 ` Gregory Maxwell
2014-04-04 17:16 ` Matt Whitlock
2014-04-04 17:51 ` Gregory Maxwell
2014-04-04 18:53 ` Matt Whitlock
2014-04-04 16:03 ` Matt Whitlock [this message]
2014-04-08 0:33 ` Nikita Schmidt
2014-04-08 0:38 ` Gregory Maxwell
2014-04-08 1:46 ` Matt Whitlock
2014-04-08 2:07 ` Gregory Maxwell
2014-04-08 11:52 ` Matt Whitlock
2014-04-10 22:31 ` Nikita Schmidt
2014-04-22 8:06 ` Jan Møller
2014-04-22 8:11 ` Matt Whitlock
2014-04-22 8:27 ` Jan Møller
2014-04-22 8:29 ` Matt Whitlock
2014-04-22 8:39 ` Jan Møller
2014-04-22 8:43 ` Matt Whitlock
2014-04-22 8:51 ` Jan Møller
2014-04-22 9:13 ` Matt Whitlock
2014-04-22 11:50 ` Justin A
2014-04-22 8:35 ` Matt Whitlock
2014-04-22 8:39 ` Tamas Blummer
2014-04-22 8:40 ` Matt Whitlock
2014-04-22 8:43 ` Tamas Blummer
2014-04-22 8:47 ` Matt Whitlock
2014-04-22 8:50 ` Tamas Blummer
2014-04-22 15:32 ` Mark Friedenbach
2014-04-22 15:49 ` Tamas Blummer
2014-04-22 17:03 ` Mark Friedenbach
2014-04-22 17:07 ` Jan Møller
2014-04-22 18:29 ` Tamas Blummer
2014-04-22 18:46 ` Gregory Maxwell
2014-04-23 5:33 ` Tamas Blummer
2014-04-23 6:16 ` Gregory Maxwell
2014-05-05 19:36 ` Nikita Schmidt
2014-05-12 12:09 ` Jan Møller
2014-08-14 19:23 ` Nikita Schmidt
2014-04-22 13:37 ` Nikita Schmidt
2014-04-22 8:15 ` Gregory Maxwell
2014-04-22 8:49 ` Jan Møller
[not found] <CACsn0ckScTWG4YxNCscxvtdsmcUkxtR2Gi-rdBs2HCkirPz5rA@mail.gmail.com>
2014-03-29 15:44 ` Matt Whitlock
2014-03-29 16:59 ` Alan Reiner
2014-03-29 17:19 ` Matt Whitlock
2014-03-29 17:52 ` Alan Reiner
2014-03-29 18:00 ` Matt Whitlock
2014-03-29 18:08 ` Alan Reiner
2014-03-29 18:10 ` Matt Whitlock
[not found] ` <CAAt2M18j7bGDsKouVw+e4j+FMiJ4vK6-sx+nrkwHyiKLqiH7Jg@mail.gmail.com>
2014-03-29 19:34 ` Natanael
2014-04-04 2:38 ` Jeff Garzik
2014-03-29 18:16 ` Tamas Blummer
2014-03-29 18:41 ` Alan Reiner
2014-03-29 17:28 ` Roy Badami
2014-03-29 17:42 ` Matt Whitlock
2014-03-29 17:51 ` Roy Badami
2014-03-29 17:28 ` devrandom
[not found] ` <1396113933.8809.91.camel@mimiz>
2014-03-29 17:38 ` Matt Whitlock
2014-03-29 17:46 ` Gregory Maxwell
2014-03-29 19:49 ` Tamas Blummer
2014-03-29 17:48 ` devrandom
2014-03-29 17:51 ` Matt Whitlock
2014-03-29 17:56 ` devrandom
-- strict thread matches above, loose matches on Subject: below --
2014-03-29 8:05 Matt Whitlock
2014-03-29 8:34 ` Tamas Blummer
2014-03-29 8:44 ` Tamas Blummer
2014-03-29 8:51 ` Matt Whitlock
2014-03-29 8:54 ` Matt Whitlock
2014-03-29 16:54 ` Matt Whitlock
2014-03-29 17:37 ` Tamas Blummer
2014-03-29 9:08 ` Chris Beams
2014-03-29 9:31 ` Matt Whitlock
2014-03-29 11:16 ` Matt Whitlock
2014-03-29 11:54 ` Chris Beams
2014-03-29 13:27 ` Jeff Garzik
2014-03-29 13:36 ` Mike Hearn
2014-03-29 13:38 ` Tamas Blummer
2014-03-29 14:10 ` Matt Whitlock
2014-03-29 14:19 ` Jeff Garzik
2014-03-29 14:55 ` Matt Whitlock
2014-03-29 15:04 ` Mike Hearn
2014-03-29 14:28 ` Watson Ladd
2014-03-29 14:36 ` Gregory Maxwell
2014-03-29 15:01 ` Matt Whitlock
2014-03-29 9:21 ` Chris Beams
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=1529077.7WHAYP4Dpn@crushinator \
--to=bip@mattwhitlock$(echo .)name \
--cc=bitcoin-development@lists$(echo .)sourceforge.net \
--cc=nikita@megiontechnologies$(echo .)com \
/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