[Bitcoin-development] Proposal to replace BIP0039

[Bitcoin-development] Proposal to replace BIP0039

[thomasV1]

I would like to propose a new BIP, that replaces BIP0039.

My initial problem was that BIP0039 is not backward compatible with Electrum. When trying to solve that, I realized that the seed encoding used in Electrum does not help, because it does not contain a version number information. However, BIP0039 suffers the same shortcoming: it does nothing to help a future replacement, it wants to be final. My first recommendation is to allocate a few bits of the mnemonic, in order to encode a "version number" along with the checksum bits.

The second problem is the wallet structure. There are multiple ways to use a BIP32 tree, and each client will certainly handle this differently. For Electrum, it is important to be able to recover an entire wallet from its mnemonic, using no extra information. Thus, the client needs to know which branches of the BIP32 tree are populated by default. This means that the "version number" I mentioned will not only be about the seed encoding, but it should also give some information about the wallet structure, at least in the case of Electrum.

The third problem is the dictionary. I do not like the dictionary proposed in BIP0039, because it contains too many short words, which are bad for memorization (I explained here how I designed the dictionary used by Electrum: https://bitcointalk.org/index.php?topic=153990.msg2167909#msg2167909). I had some discussions with slush about this, but I do not think it will ever be possible to find a consensus on that topic. 

BIP0039 also suggests to use localized dictionaries, with non-colliding word lists, but it is not clear how that will be achieved; it seems to be difficult, because languages often have words in common. It looks like a first-come-first-served aproach will be used. 

For these reasons, I believe that we need a dictionary-independent solution. This will allow developers to use the dictionary they like, and localization will be easy.

I would like to suggest the following solution:

1. Define a target of k bits: this target contains the metadata ("version number"), plus some extra bits for the checksum. For example, with k=16, we can allocate 8 bits for the version number, and 8 bits for checksum.

2. Pick a random number of length n+k bits, where n is the desired entropy of the seed, and k is the number of bits needed for the metadata (checksum, version number)

3. Translate this random number to a mnemonic string, using a dictionary.

4. Compute a hash of the mnemonic string (utf8 encoded).

5. Repeat steps 2, 3 and 4 until the k first bits of the hash are equal to the target defined in 1.

6. Use the final hash as input for bip32 (as the master seed)

This means that we "mine" for the seed, until the desired metadata is obtained in the hash. This "mining" also adds a bit of difficulty to the process of finding a seed (on average, it will require 2^k iterations). The entropy of the final hash is n, the number of unconstrained bits.

This solution makes it possible for developers to define new dictionaries, localized or adapted to a particular need. 
The resulting mnemonics will always be usable with other clients, even if they do not know the dictionary. 

I am willing to write a new BIP where this proposal is specified in detail.

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 3639 bytes --]

On Thu, Oct 24, 2013 at 7:29 PM, <thomasV1@gmx.de> wrote:

>
> My initial problem was that BIP0039 is not backward compatible with
> Electrum. When trying to solve that, I realized that the seed encoding used
> in Electrum does not help, because it does not contain a version number
> information. However, BIP0039 suffers the same shortcoming: it does nothing
> to help a future replacement, it wants to be final. My first recommendation
> is to allocate a few bits of the mnemonic, in order to encode a "version
> number" along with the checksum bits.
>
>
Two years ago I proposed exactly this and you refused to add extra
information to mnemonic, because "it isn't necessary" and "it makes it
longer to mnemonization". What changed since then?


> The second problem is the wallet structure. There are multiple ways to use
> a BIP32 tree, and each client will certainly handle this differently. For
> Electrum, it is important to be able to recover an entire wallet from its
> mnemonic, using no extra information. Thus, the client needs to know which
> branches of the BIP32 tree are populated by default. This means that the
> "version number" I mentioned will not only be about the seed encoding, but
> it should also give some information about the wallet structure, at least
> in the case of Electrum.
>
>
Hm, what exactly do you need to store about wallet structure? I lived in
opinion that everything is able to recover using CKD function to generate
new addresses and blockchain lookups for their balances.


> The third problem is the dictionary. I do not like the dictionary proposed
> in BIP0039, because it contains too many short words, which are bad for
> memorization (I explained here how I designed the dictionary used by
> Electrum:
> https://bitcointalk.org/index.php?topic=153990.msg2167909#msg2167909). I
> had some discussions with slush about this, but I do not think it will ever
> be possible to find a consensus on that topic.
>
>
Yes, that's true. It isn't possible to make everybody 100% happy. At least
I wanted to be constructive and asked you to replace the most problematic
words. No pull request from you so far.


> BIP0039 also suggests to use localized dictionaries, with non-colliding
> word lists, but it is not clear how that will be achieved; it seems to be
> difficult, because languages often have words in common. It looks like a
> first-come-first-served aproach will be used.
>
>
Yes, it was original idea. So far I don't think this is a problem. Of
course some words may have some meaning across languages, but it should be
easy to avoid them. There are tens of thousands words in every language and
we need to pick "only" 2048 words to wordlist.


> For these reasons, I believe that we need a dictionary-independent
> solution. This will allow developers to use the dictionary they like, and
> localization will be easy.
>
I would like to suggest the following solution:
>
>
If I understand this well, it is basically one-way algorithm "mnemonic ->
seed", right? Seed cannot be printed out as mnemonic, because there's
hashing involved, but the bi-directionality has been the original
requirement for such algorithm (at least in Electrum and bip39).

Then, how is this different to picking 12 random words from dictionary and
hashing them together? I don't see any benefit in that "mining" part of the
proposal (except that it is lowering the entropy for given length of
mnemonic).


> This solution makes it possible for developers to define new dictionaries,
> localized or adapted to a particular need.
>

Are your worries about overlapping words across languages a real issue?

slush

[-- Attachment #2: Type: text/html, Size: 5183 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

slush wrote :
> Two years ago I proposed exactly this and you refused to add extra 
> information to mnemonic, because "it isn't necessary" and "it makes it 
> longer to mnemonization". What changed since then?

I was wrong, and I fully acknowledge it.

My concern was that adding extra information would make the mnemonic 
longer than 12 words.
In addition, you proposed to allocate these extra bits for a checksum, 
not for metadata.
However, a checksum does not really add any information, because 
Electrum checks the existence of a wallet directly from the blockchain.
So, my feeling at that time was that adding extra bits would increase 
the risks (a longer seed is harder to memorize, increases the 
probability of mistakes, etc), and did not bring any real benefit.

However, you showed since then how to solve this by using a slightly 
longer dictionary, and I do like your solution, I find it absolutely 
brilliant.
In addition, I realize now that metadata (ie a "version number") is 
crucially needed, for the reasons mentioned in my previous post.

> Hm, what exactly do you need to store about wallet structure? I lived 
> in opinion that everything is able to recover using CKD function to 
> generate new addresses and blockchain lookups for their balances.

BIP32 gives a lot of freedom to wallet developers: it does not specify 
which branches of the HD tree shall be used for which purpose.

However, if you want to recover a wallet from its mnemonic (a 
requirement for Electrum), then you need to know which branches to explore.
In Electrum 1.9 I had to make some choices about branch allocation. 
However, the decisions that I made are certainly not final, so it is 
important to be able to change them in the future. Thus, this metadata 
needs to be added to the mnemonic.


>  Yes, that's true. It isn't possible to make everybody 100% happy. At 
> least I wanted to be constructive and asked you to replace the most 
> problematic words. No pull request from you so far.

The solution I propose is very different from BIP39, and it does not 
require to predefine a dictionary.
My proposal is actually somewhat similar to Pieter Wuille's proposal, 
which I discovered after his recent post.
( https://bitcointalk.org/index.php?topic=102349.0 )

>  Yes, it was original idea. So far I don't think this is a problem. Of 
> course some words may have some meaning across languages, but it 
> should be easy to avoid them. There are tens of thousands words in 
> every language and we need to pick "only" 2048 words to wordlist.
> ...
> Are your worries about overlapping words across languages a real issue?

No, there are not so many words that are frequent enough.
Overlapping will be an issue, especially if we go for a 4096 words 
dictionary.


> If I understand this well, it is basically one-way algorithm "mnemonic 
> -> seed", right? Seed cannot be printed out as mnemonic, because 
> there's hashing involved, but the bi-directionality has been the 
> original requirement for such algorithm (at least in Electrum and bip39).

You are right, this encoding is not symmetric.
Bi-directionality has never been a requirement for Electrum. May I ask 
why you need bi-directionality in Trezor?
(the only reason I can think of is if you want to export a bip32 branch 
into another wallet, but this would create a very long mnemonic string)

> Then, how is this different to picking 12 random words from dictionary 
> and hashing them together? I don't see any benefit in that "mining" 
> part of the proposal (except that it is lowering the entropy for given 
> length of mnemonic).

it makes it possible to hash a utf8 string, and to retrieve the metadata 
from the hash.
Thus we don't need to spend ages arguing about the best choice of a 
dictionary, and to set it in stone.

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 2477 bytes --]

On Thu, Oct 24, 2013 at 7:29 PM, <thomasV1@gmx.de> wrote:
>
> My initial problem was that BIP0039 is not backward compatible with
> Electrum. When trying to solve that, I realized that the seed encoding used
> in Electrum does not help, because it does not contain a version number
> information. However, BIP0039 suffers the same shortcoming: it does nothing
> to help a future replacement, it wants to be final. My first recommendation
> is to allocate a few bits of the mnemonic, in order to encode a "version
> number" along with the checksum bits.
>
>
On topic of "it wants to be final" and "it is incompatible with Electrum":
None of this is true. Firstly, it *is* possible to implement both algorithm
into the client at the same time, so user will be able to recover wallet
using Electrum or bip39 mnemonic and - what is worse - you already *know*
about this solution. Still you're spreading FUD about it on IRC, on emails
behind my back and here on mailing list.

The solution for Electrum client - as we discussed two weeks ago on IRC -
is that:

a) User type down the mnemonic (created with Electrum or BIP39)
b1) Only if *all* words are presented in both dictionaries and it has valid
BIP39 checksum (which is quite rare situation itself!), the mnemonic can be
consider to be both Electrum or BIP39.
b2) In most of cases we end up here, because the most common situation is
that with given words, only Electrum *or* BIP39 seed can be recovered.
----
c) Consider the mnemonic as Electrum. Create first few addresses and do a
lookup. If there are transactions in address history, this is Electrum
mnemonic.
d) If there were no used address in c), build seed using BIP39 and do the
same lookup. If there's history, this is BIP39 mnemonic.
e) If there are no history on both algorithm, then pick prefered one for
given client (it should not hurt which one, because first use of given
mnemonic will "freeze" given algorithm for next time of mnemonic recovery).

Well, because only Electrum uses some mnemonic algorithm to this date, such
decision tree need to be implemented only in Electrum. You cannot tell that
"it is too complicated" or "ambiguous", because you're using the same
algorithm of deciding between Electrum deterministic / BIP32.

I must admit that I'm quite annoyed of such discussion, because we already
discussed all this privately, you didn't tell me any reason why this should
not work and still I see that this is coming back as a boomerang.

slush

[-- Attachment #2: Type: text/html, Size: 3174 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

here is a simple implementation, with some ideas on how to format the 
metadata:
https://en.bitcoin.it/wiki/Talk:BIP_0039

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 1321 bytes --]

Hi Thomas,

can you more elaborate on that "version" bits? What is exact meaning of it?
I still think this is more an implementation problem. What stops Electrum
to do the same algorithm for searching branches as it is now for used
addresses?

These "version bits" need to be covered by the specification as well,
because if any client will use them differently (or won't use them at all),
it will break cross-compatibility between clients, which was another goal
of bip39.

Marek




On Sat, Oct 26, 2013 at 5:24 PM, Thomas Voegtlin <thomasv1@gmx.de> wrote:

> here is a simple implementation, with some ideas on how to format the
> metadata:
> https://en.bitcoin.it/wiki/Talk:BIP_0039
>
>
>
> ------------------------------------------------------------------------------
> October Webinars: Code for Performance
> Free Intel webinars can help you accelerate application performance.
> Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most
> from
> the latest Intel processors and coprocessors. See abstracts and register >
> http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

[-- Attachment #2: Type: text/html, Size: 2203 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Pieter Wuille]

Let's first try to agree on what we are solving.

It seems that Thomas wants - in addition to the cryptographic data -
to encode the tree structure, or at least version information about
what features are used in it, inside the seed.

I'm not sure whether we're ready to standardize on something like that
yet, not having established best practices regarding different wallet
structures. I do think we first need to see what possibilities and
developments are possible related to it.

In addition, information about the wallet structure is strictly less
secret than the key data - it is even less confidential than address
book data, transaction annotations, labels and comments and
bookkeeping information. It could be backed up anywhere and everywhere
without any repercussions, as far as I can see. I understand that in
the case of Electrum, there is a strong reason to want this
encapsulated together with the seed, but it's not really a requirement
for most wallets.
(if really needed, any key derivation scheme that starts from random
strings can be augmented with metadata by enforcing property-bits on a
hash of the string (so not of the output), as this data doesn't need
protection from brute-forcing).

Regarding other requirements, I wonder why we want the transformation
to be bidirectional? If it is just about generating master seeds, one
direction should be enough, and allows far nicer properties w.r.t.
security. If we do settle on a standard for 'brainwallets', I would
strongly prefer if it had at least some strengthening built-in, to
decrease the impact of worst-case situations.
If the reason is backward-compatibility, I think that any client that
supports seeds already can just keep supporting whatever they
supported before. Only if it matches both encoding schemes (as
mentioned before) there is a potential collision (and in that case,
the user could just be asked).

-- 
Pieter


On Sat, Oct 26, 2013 at 10:47 PM, slush <slush@centrum.cz> wrote:
> Hi Thomas,
>
> can you more elaborate on that "version" bits? What is exact meaning of it?
> I still think this is more an implementation problem. What stops Electrum to
> do the same algorithm for searching branches as it is now for used
> addresses?
>
> These "version bits" need to be covered by the specification as well,
> because if any client will use them differently (or won't use them at all),
> it will break cross-compatibility between clients, which was another goal of
> bip39.
>
> Marek
>
>
>
>
> On Sat, Oct 26, 2013 at 5:24 PM, Thomas Voegtlin <thomasv1@gmx.de> wrote:
>>
>> here is a simple implementation, with some ideas on how to format the
>> metadata:
>> https://en.bitcoin.it/wiki/Talk:BIP_0039
>>
>>
>>
>> ------------------------------------------------------------------------------
>> October Webinars: Code for Performance
>> Free Intel webinars can help you accelerate application performance.
>> Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most
>> from
>> the latest Intel processors and coprocessors. See abstracts and register >
>>
>> http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>
>
> ------------------------------------------------------------------------------
> October Webinars: Code for Performance
> Free Intel webinars can help you accelerate application performance.
> Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most
> from
> the latest Intel processors and coprocessors. See abstracts and register >
> http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

Indeed, I want to include a version number in the seed phrase because 
there are
multiple ways to define the tree structure used with BIP32. It is 
certainly too early
to make final decisions on that, or to achieve a common standard.
Also, I can imagine that bip32 itself might be superseeded in the future.

I understand that encapsulating a version number in the seed phrase might
not be as important for other wallets as it is for Electrum. So it is 
probably not
necessary to propose another BIP for that. I will simply implement it 
for Electrum,
and I will try to do it in such a way that other wallets can use the 
same format.

The other question we might be solving is strenghtening (your proposal). 
I consider
that this is not a strong requirement for Electrum, because it does not 
let the user
choose their seed phrase. However, if a few bits of the seed phrase are 
allocated
for metadata, then I guess strenghtening can be part of it. That's 
another good
reason to have a version number encapsulated in the seed.

I too wonder why the transformation needs to be bidirectional in bip39.




Le 26/10/2013 23:30, Pieter Wuille a écrit :
> Let's first try to agree on what we are solving.
>
> It seems that Thomas wants - in addition to the cryptographic data -
> to encode the tree structure, or at least version information about
> what features are used in it, inside the seed.
>
> I'm not sure whether we're ready to standardize on something like that
> yet, not having established best practices regarding different wallet
> structures. I do think we first need to see what possibilities and
> developments are possible related to it.
>
> In addition, information about the wallet structure is strictly less
> secret than the key data - it is even less confidential than address
> book data, transaction annotations, labels and comments and
> bookkeeping information. It could be backed up anywhere and everywhere
> without any repercussions, as far as I can see. I understand that in
> the case of Electrum, there is a strong reason to want this
> encapsulated together with the seed, but it's not really a requirement
> for most wallets.
> (if really needed, any key derivation scheme that starts from random
> strings can be augmented with metadata by enforcing property-bits on a
> hash of the string (so not of the output), as this data doesn't need
> protection from brute-forcing).
>
> Regarding other requirements, I wonder why we want the transformation
> to be bidirectional? If it is just about generating master seeds, one
> direction should be enough, and allows far nicer properties w.r.t.
> security. If we do settle on a standard for 'brainwallets', I would
> strongly prefer if it had at least some strengthening built-in, to
> decrease the impact of worst-case situations.
> If the reason is backward-compatibility, I think that any client that
> supports seeds already can just keep supporting whatever they
> supported before. Only if it matches both encoding schemes (as
> mentioned before) there is a potential collision (and in that case,
> the user could just be asked).
>

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 3987 bytes --]

Strange, I didn't receive the response from sipa in separate message, so
I'll respond to him at first place.

Le 26/10/2013 23:30, Pieter Wuille a écrit :
> I'm not sure whether we're ready to standardize on something like that
> yet, not having established best practices regarding different wallet
> structures. I do think we first need to see what possibilities and
> developments are possible related to it.

Although many strange practices how to use whole bip32 space are possible,
I think that we may (should?) agree on some "good enough" way how to
discover already used addresses in bip32 space. I read Electrum sources
about bip32 and I see that Electrum still uses quite flat structure (fixed
amount of branches, indexes from 0 to n), which is of course very sane way.

So if I migrate seed to another (non-Electrum) software, I only need to
discover close neighbourhood of the path "0", similarly like Electrum is
doing with "gap limit" in plain old Electrum algorithm, except in two
dimensions (paths 0, 1, 2, 3, 4, 5, 0/0, 0/1, 0/2, 0/3, 0/4, 0/5, 1/0, 1/1,
...5/5 for gap limit "5"). I don't say such operation is cheap, but this
discovery needs to be done only during the import.

For the reason that I think this is the only sane algorithm of general use
of bip32 space, I still don't see why we do need some extra metadata. I
would understand this if Electrum will use for some strange reason
addresses in higher address space like 2^32-1 or so, but this is not going
to happen at least in Electrum.

> I understand that in
> the case of Electrum, there is a strong reason to want this
> encapsulated together with the seed, but it's not really a requirement
> for most wallets.

Well, I can imagine that the bip32 compatible software will do full scan of
address space using some gap factor (actually I think "5" is too low by
default) or it can ask for wallet metadata like which software used such
tree before, to speedup scanning process.

I see that Thomas wants to make this automatic and hidden to user and
generally I agree that hiding the compexity to user is a good practice, but
actually this particular situation sounds to me as an exact oposite of
original statement "no metadata in mnemonic".

> Regarding other requirements, I wonder why we want the transformation
> to be bidirectional? If it is just about generating master seeds, one
> direction should be enough, and allows far nicer properties w.r.t.
> security. If we do settle on a standard for 'brainwallets',

ECDSA has one very nice option - (almost) any random data can be used as a
private key. There are very nice schemas possible by using this feature and
requiring private key to be specially crafted just because the user wanted
to use mnemonic schema is very strong limitation to me.

To be specific, we (in cooperation with / inspired by Timo Hanke) developed
method how to prove that the seed generated by Trezor has been created
using combination of computer-provided entropy and device-provided entropy,
without leaking full private information to other computer, just because we
want Trezor to be blackbox-testable and fully deterministic (seed
generation is currently the only operation which uses any source of RNG).

To limit the complexity of such algorithm it is better to produce plain
seed (128, 192 or 256 bits, depends on settings) and then transform the
result of such "deterministic seed" to mnemonic, so for us the
bi-directionality is quite strong requirement. *Maybe* it would be possible
to combine such algorithm and one-way mnemonic together, but it would
complicate the design and I'm sure you understand that we want to keep
things as clear and simple as possible, especially while handling with seed
generation.

> I would strongly prefer if it had at least some strengthening built-in, to
> decrease the impact of worst-case situations.

Agree (hardening is default in bip39).


Marek

[-- Attachment #2: Type: text/html, Size: 5013 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 958 bytes --]

On Thu, Oct 31, 2013 at 11:41:27AM +0100, slush wrote:
> To be specific, we (in cooperation with / inspired by Timo Hanke) developed
> method how to prove that the seed generated by Trezor has been created
> using combination of computer-provided entropy and device-provided entropy,
> without leaking full private information to other computer, just because we
> want Trezor to be blackbox-testable and fully deterministic (seed
> generation is currently the only operation which uses any source of RNG).

I just wanted to say the fact that you're making key generation
auditable, and using deterministic signatures, is a clear sign that you
guys know what you're doing. Hearing this makes me a lot more confident
that the Trezor will prove to be a secure way to store my Bitcoins and
my pre-order will prove to be money well spent.

Kudos!

-- 
'peter'[:-1]@petertodd.org
000000000000000784d399e7c1d1e8f2fc953c6939b115699a1ee05029a59bc9

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

> To be specific, we (in cooperation with / inspired by Timo Hanke) 
> developed method how to prove that the seed generated by Trezor has 
> been created using combination of computer-provided entropy and 
> device-provided entropy, without leaking full private information to 
> other computer, just because we want Trezor to be blackbox-testable 
> and fully deterministic (seed generation is currently the only 
> operation which uses any source of RNG).
>

Thanks for the explanation. Here is how I understand how it works, 
please correct me if I'm wrong:

The user's computer picks a random number a, the Trezor picks a random 
number b.
Trezor adds a and b in the secp256k1 group, and this creates a master 
private key k.
Trezor sends the corresponding master public key K to the computer.
Thus, the computer can check that K was derived from a, without knowing b.
This also allows the computer to check that any bitcoin address derived 
from K is derived from a, without leaking b. (and reciprocally)

However, it seems to me that this property will work only with bip32 
public derivations; if a private derivation is used, don't you need to 
know k?

Re: [Bitcoin-development] Proposal to replace BIP0039

[Timo Hanke]

On Sat, Nov 02, 2013 at 10:44:58AM +0100, Thomas Voegtlin wrote:
> 
> >To be specific, we (in cooperation with / inspired by Timo Hanke)
> >developed method how to prove that the seed generated by Trezor
> >has been created using combination of computer-provided entropy
> >and device-provided entropy, without leaking full private
> >information to other computer, just because we want Trezor to be
> >blackbox-testable and fully deterministic (seed generation is
> >currently the only operation which uses any source of RNG).
> >
> 
> Thanks for the explanation. Here is how I understand how it works,
> please correct me if I'm wrong:
> 
> The user's computer picks a random number a, the Trezor picks a
> random number b.
> Trezor adds a and b in the secp256k1 group, and this creates a
> master private key k.
> Trezor sends the corresponding master public key K to the computer.
> Thus, the computer can check that K was derived from a, without knowing b.

No. You mean the computer would use B for this check? 
(k,K) could be rigged by Trezor, who computes b as k-a.

Timo

> This also allows the computer to check that any bitcoin address
> derived from K is derived from a, without leaking b. (and
> reciprocally)
> 
> However, it seems to me that this property will work only with bip32
> public derivations; if a private derivation is used, don't you need
> to know k?
> 
> 
> 

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

Le 03/11/2013 07:41, Timo Hanke a écrit :
> No. You mean the computer would use B for this check? (k,K) could be 
> rigged by Trezor, who computes b as k-a. Timo

I was just asking a question, in order to understand how this device 
works, and what are its requirements.
if you think you can help, please explain.

Re: [Bitcoin-development] Proposal to replace BIP0039

[Timo Hanke]

I think the communication would have to go the other way around. Trezor
has to commit to a value First. Like this:

Trezor picks random s and sends S=s*G to computer, keeping s secret.
Computer picks random t and sends t to Trezor.  Trezor makes r := s+t
its internal master private key with corresponding master public key 
R := (s+t)*G. Since R = S+t*G, the computer can verify the master
public key. As you say, the computer can then store R and can later
verify for each derived pubkey that it was indeed derived from R, hence
from his own entropy t.

However, Trezor could not use straight bip32 out of the box. The
chaincode would have to be something like SHA(R). And the seed (that
gets translated to mnemonic) would be r itself, making it 256 bit
instead of only 128 bit.

If the longer seed is bearable then this is a good way to do it.

One question remains: if you only write down the mnemonic how can you be
sure that it is correct and corresponds to the secret in Trezor? You
cannot verify that on paper. You would have to restore it on some
device, eg another empty Trezor, and see if it brings up the same master
pubkey. Right? 

Timo

On Sun, Nov 03, 2013 at 08:03:54AM +0100, Thomas Voegtlin wrote:
> 
> Le 03/11/2013 07:41, Timo Hanke a écrit :
> >No. You mean the computer would use B for this check? (k,K) could
> >be rigged by Trezor, who computes b as k-a. Timo
> 
> I was just asking a question, in order to understand how this device
> works, and what are its requirements.
> if you think you can help, please explain.
> 
> 

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

Le 03/11/2013 08:40, Timo Hanke a écrit :
> I think the communication would have to go the other way around. Trezor
> has to commit to a value First. Like this:
>
> Trezor picks random s and sends S=s*G to computer, keeping s secret.
> Computer picks random t and sends t to Trezor.  Trezor makes r := s+t
> its internal master private key with corresponding master public key
> R := (s+t)*G. Since R = S+t*G, the computer can verify the master
> public key. As you say, the computer can then store R and can later
> verify for each derived pubkey that it was indeed derived from R, hence
> from his own entropy t.

I'm not sure how this differs from what I wrote...

However, if this is how it works, then my question remains:
The computer has no proof to know that pubkeys derived through bip32's 
private derivations are derived from its own entropy...
This verification would only work for public (aka type2) derivations.

.. but maybe Trezor works in a different way? I think an explanation 
from slush would be needed.


> However, Trezor could not use straight bip32 out of the box. The
> chaincode would have to be something like SHA(R). And the seed (that
> gets translated to mnemonic) would be r itself, making it 256 bit
> instead of only 128 bit.
>
> If the longer seed is bearable then this is a good way to do it.
>
> One question remains: if you only write down the mnemonic how can you be
> sure that it is correct and corresponds to the secret in Trezor? You
> cannot verify that on paper. You would have to restore it on some
> device, eg another empty Trezor, and see if it brings up the same master
> pubkey. Right?
>
I guess you have to trust Trezor that it derives R from r

Re: [Bitcoin-development] Proposal to replace BIP0039

[Timo Hanke]

On Sun, Nov 03, 2013 at 09:39:42AM +0100, Thomas Voegtlin wrote:
> 
> Le 03/11/2013 08:40, Timo Hanke a écrit :
> >I think the communication would have to go the other way around. Trezor
> >has to commit to a value First. Like this:
> >
> >Trezor picks random s and sends S=s*G to computer, keeping s secret.
> >Computer picks random t and sends t to Trezor.  Trezor makes r := s+t
> >its internal master private key with corresponding master public key
> >R := (s+t)*G. Since R = S+t*G, the computer can verify the master
> >public key. As you say, the computer can then store R and can later
> >verify for each derived pubkey that it was indeed derived from R, hence
> >from his own entropy t.
> 
> I'm not sure how this differs from what I wrote...

Sorry, yes, of course it's the same..
Your very first proposal was fine, provided that Trezor commits to its
random value first.

> However, if this is how it works, then my question remains:
> The computer has no proof to know that pubkeys derived through
> bip32's private derivations are derived from its own entropy...
> This verification would only work for public (aka type2) derivations.
> 
> .. but maybe Trezor works in a different way? I think an explanation
> from slush would be needed.

Does Trezor even use private derivation?

Regardless of whether the derivation is private or public, and
regardless of what kind of proof you use to show that the master public
key was derived from user supplied entropy, my question also remains:
How do you verify your backup? The backup is a seed or private key. It's
too long to do any meaningful computation by hand. So you would need a
second offline device, eg a second Trezor in "restore mode", just to
verify your backup.

Timo

> >However, Trezor could not use straight bip32 out of the box. The
> >chaincode would have to be something like SHA(R). And the seed (that
> >gets translated to mnemonic) would be r itself, making it 256 bit
> >instead of only 128 bit.
> >
> >If the longer seed is bearable then this is a good way to do it.
> >
> >One question remains: if you only write down the mnemonic how can you be
> >sure that it is correct and corresponds to the secret in Trezor? You
> >cannot verify that on paper. You would have to restore it on some
> >device, eg another empty Trezor, and see if it brings up the same master
> >pubkey. Right?
> >
> I guess you have to trust Trezor that it derives R from r
> 
> 
> 
> 

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Proposal to replace BIP0039

[Pavol Rusnak]

On 04/11/13 16:10, Timo Hanke wrote:
> Does Trezor even use private derivation?

No. It can't. Private keys never leave the device so client would not
know how to generate addresses.

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] Proposal to replace BIP0039

[Pavol Rusnak]

On 03/11/13 08:40, Timo Hanke wrote:
> Trezor picks random s and sends S=s*G to computer, keeping s secret.

That's a really neat trick!

> One question remains: if you only write down the mnemonic how can you be
> sure that it is correct and corresponds to the secret in Trezor?

Right. That's a problem. I'm not sure if this whole cryptomagic is
benefitial at all.

I'd suggest to go the easy way for now, i.e. prove that external entropy
was used while generating the master seed. If the user does not trust
our firmware, he can use his own built one.

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] Proposal to replace BIP0039

[Timo Hanke]

On Sun, Nov 17, 2013 at 12:49:04AM +0100, Pavol Rusnak wrote:
> On 03/11/13 08:40, Timo Hanke wrote:
> > Trezor picks random s and sends S=s*G to computer, keeping s secret.
> 
> That's a really neat trick!
> 
> > One question remains: if you only write down the mnemonic how can you be
> > sure that it is correct and corresponds to the secret in Trezor?
> 
> Right. That's a problem. I'm not sure if this whole cryptomagic is
> benefitial at all.
> 
> I'd suggest to go the easy way for now, i.e. prove that external entropy
> was used while generating the master seed. If the user does not trust
> our firmware, he can use his own built one.

No, this question of mine was regardless of any cryptomagic or neat
tricks like Thomas' suggestion. It has nothing do with auditing the
entropy. It was just a backup question.

I recently had an experience where I thought coins were lost because the
secrets I had didn't match the public keys that I thought they'd match.
From now on I will always recover my wallet first, from the backed up
secrets, before sending any coins to the pubkeys in the wallet. I will
never again generate a wallet, backup the secrets, and hope the secrets
indeed match the pubkeys.. without testing that. My question was how
Trezor allows me to verify my backup.

All this makes me think if having one device generating and displaying
the secret, and making a backing from the display, is the right way to
go. Since you would need a second device to verify your backup is sane,
you could have two devices to start with. One is your hardware wallet
and it only imports secrets (restores backups). The other is an entropy
generator and it only generates secrets.

Best regards,
Timo

p.s. The question about auditing entropy would only apply to the generator,
not the wallet. Is it yet documented how Trezor proves that external
entropy was used? 

-- 
Timo Hanke
PGP 1EFF 69BC 6FB7 8744 14DB  631D 1BB5 D6E3 AB96 7DA8

Re: [Bitcoin-development] Proposal to replace BIP0039

[Pavol Rusnak]

On 17/11/13 01:42, Timo Hanke wrote:
> p.s. The question about auditing entropy would only apply to the generator,
> not the wallet. Is it yet documented how Trezor proves that external
> entropy was used? 

We'll probably use the most straightforward way:
a) trezor prints entropy A on a display (probably in hex format, this
step is triggered by sending a special flag in initialize message)
b) trezor receives entropy B from external source
c) trezor creates sha256(A + B) and uses that as a seed
d) trezor prints used seed on a display (probably in BIP39 format)
e) user can check on a trusted computer that everything was ok

(note that steps b-d are the same regardless of whether the special flag
was set)

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 4535 bytes --]

On Thu, Oct 31, 2013 at 10:13 AM, Thomas Voegtlin <thomasv1@gmx.de> wrote:

> Indeed, I want to include a version number in the seed phrase because
> there are
> multiple ways to define the tree structure used with BIP32. It is
> certainly too early
> to make final decisions on that, or to achieve a common standard.
>

Well, as we're the first pioneers of bip32, let's start using it in some
sane way and I'm sure the others will join. Just because they don't want to
incompatible software.

Actually I quite like that you're not wasting bip32 space by using some
dynamic allocatons in higher address space, so I'm happy to follow your
rules and I think we can agree on generic discover algorithm which maybe
won't be optimal, but will find all used addresses and won't need any
additional information directly in mnemonic.

As I wrote in previous post, in worst case I can imagine dropdown list on
import dialog, which will ask user which software has been handling the
seed before, to speedup the scan. But for now I don't see this necessary at
all.

Also, I can imagine that bip32 itself might be superseeded in the future.
>
>
Although I can imagine that as well, I hope that it won't be the case. We
need to unite and integrate instead of making incompatible applications.

One disadvantage of bip32 is that in fact it is too much flexible, so we
even falled into the necessity of defining version of discovery algorithm.
Lets set up best practices how to use it and other will follow instead of
creating zillion cross-incompatible algorithms which won't understand each
to other.


> The other question we might be solving is strenghtening (your proposal).
> I consider
> that this is not a strong requirement for Electrum, because it does not
> let the user
> choose their seed phrase. However, if a few bits of the seed phrase are
>

Hardening and password protection are two unrelated requirements. Again,
there are some scenarios in which use can leak part of the mnemonic to
attacker, so hardening prevent to bruteforce the rest information by
attacker, even if the mnemonic isn't passphrase protected.

I'm especially refering to our algorithm of mnemonic import to Trezor
during disaster recovery (when Trezor is destroyed and user wants to import
the seed to another one), so that leak isn't just a theoretical concept,
but real-word scenario.


> allocated

for metadata, then I guess strenghtening can be part of it. That's
> another good
> reason to have a version number encapsulated in the seed.
>

Actually creating optional features of such algorithm only make things
complicated (and less cross-compatible). Every software still needs to
implement such hardening even if it is optional feature, to be compatible
with other clients. Then I don't see any reason why to have it optional.

Don't forget that the proposal uses only 4 bits of version, which isn't too
much combination for all these optional features ;-).

I too wonder why the transformation needs to be bidirectional in bip39.
>
>
Well, I wrote longer answer in previous  email. tl;dr; there's quite easy
way how to make the algorithm bi-directional, so I don't see a necessity to
drop potentially useful feature for no good reason.

I was thinking about your proposal and I realized that both our solutions
solves a bit different problem. Lets summarize features (and forget to
wordlist fights for moment):

bip39:
+ bi-directional
+ passphrase protected
+ shorter mnemonic or shorter wordlist
- predefined wordlist

ThomasV proposal:
+ any software can has its own preferred worlist
? passphrase protected
- one-direction only
- longer mnemonic or longer wordlist

Back to wordlist fights
a) actually I think that the wordlist choice is far less important than it
may look at first glance. Thomas thinks that bip39 wordlist is disaster, me
and many other thinks it is ok, but mainly that it is very subjective.

b) I see the beauty of "custom wordlists" in Thomas proposal, still if it
means the algorithm is uni-direction only, it is very strong disadvantage
to our usecase.

c) I advocated our wordlist mainly because we put a lot of effort into it
and after many weeks of tuning it is already done; not because I think that
one method of picking the words is superior to other. I mean - if Thomas
can offer any other plain-english wordlist which he'll be happy with, I'll
vote for dropping our own wordlist and to use Thomas's version for the deal
that he'll accept our need for bi-directionality and he agrees on the rest
of bip39 ;-).

Marek

[-- Attachment #2: Type: text/html, Size: 6432 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[slush]

[-- Attachment #1: Type: text/plain, Size: 689 bytes --]

Oh, I forgot to one practical aspect; the way how the mnemonic is "mined"
in Thomas proposal prevents usage in embedded devices, because difficulty
of generating proper mnemonic is simply too high for embedded
microcontrollers. Maybe this can be solved somehow by modifying the
proposal, but right now it is a showstopper for us.

Marek

On Thu, Oct 31, 2013 at 12:11 PM, slush <slush@centrum.cz> wrote:

>
> bip39:
> + bi-directional
> + passphrase protected
> + shorter mnemonic or shorter wordlist
> - predefined wordlist
>
> ThomasV proposal:
> + any software can has its own preferred worlist
> ? passphrase protected
> - one-direction only
> - longer mnemonic or longer wordlist
>
>

[-- Attachment #2: Type: text/html, Size: 1285 bytes --]

Re: [Bitcoin-development] Proposal to replace BIP0039

[Thomas Voegtlin]

Le 31/10/2013 12:18, slush a écrit :
> Oh, I forgot to one practical aspect; the way how the mnemonic is 
> "mined" in Thomas proposal prevents usage in embedded devices, because 
> difficulty of generating proper mnemonic is simply too high for 
> embedded microcontrollers. Maybe this can be solved somehow by 
> modifying the proposal, but right now it is a showstopper for us.
>
>

even if metadata is only 8 bits ? (that's about 256 hashes)

Re: [Bitcoin-development] Proposal to replace BIP0039

[Luke-Jr]

On Thursday, October 24, 2013 5:29:18 PM thomasV1@gmx.de wrote:
> I would like to propose a new BIP, that replaces BIP0039.

BIP 39 is still a draft. Just suggest revisions to the author(s)...