public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* Re: [Bitcoin-development] BIP39 word list
@ 2013-11-01 20:14 Brooks Boyd
  2013-11-01 23:41 ` Allen Piscitello
  2013-11-02  0:04 ` slush
  0 siblings, 2 replies; 9+ messages in thread
From: Brooks Boyd @ 2013-11-01 20:14 UTC (permalink / raw)
  To: bitcoin-development

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

I was inspired to join the mailing list to comment on some of these
discussions about BIP39, which I think will have great use in the Bitcoin
community and outside it as a way to transcribe binary data.

The one thought I had as the discussions about similar characters are
resulting in culling words from the list, is that it only helps to validate
input, not help the user if it is incorrect.

For example, if both "cat" and "eat" were in the word list, and someone
wrote down "eat", but later mis-translated it and put "cat" back into
translator, the result would be a checksum error; "cat" is a different
number, so the checksum would fail.

As it currently stands, "cat" would not be a valid word ("eat" is the real
word, and no other number is "cat"), so the translator can throw a
different error which is more helpful (i.e. "'cat' isn't a valid word
choice), but still doesn't get the user to the proper translation.

What about if the wordlist included those "words that are so similar to
each other that we only kept one of them" and had them all refer to the
same number? I propose the wordlist have the possibility of multiple words
on a single line, with the first word on the line being the "primary" or
"real" word to be used, with the other similar words be included so that a
translation program if it wanted to assist the user could fix their input
for them (verbosely or not), along the lines of "'cat' isn't a valid word
choice; assuming you meant 'eat', which is valid". You might still hit a
checksum error if that similar word is still the wrong word, but as it
stands now, I know you culled a bunch of words from the wordlist as "too
similar", but if I want to try and help the user fix a bad input, I need to
write a translation program with a full english dictionary alongside the
BIP39 dictionary.

I'd be willing to create a pull request for such an update, but before I
delve into that, does this sound like a good idea? I could see it devolving
into a slippery slope if every number in the 2048 set had a dozen word
variations (misspellings, similar words, slang terms for the real word,
etc.) which could get confusing of how similar is similar enough to be
added as an alternate, and the standard would need to be clear that when
translating binary to words, you only use the "main" word for that row, not
any of the variations.

MidnightLightning


> I've just pushed updated wordlist which is filtered to similar characters
taken from this matrix.
> BIP39 now consider following character pairs as similar:
>         similar = (
>             ('a', 'c'), ('a', 'e'), ('a', 'o'),
>             ('b', 'd'), ('b', 'h'), ('b', 'p'), ('b', 'q'), ('b', 'r'),
>             ('c', 'e'), ('c', 'g'), ('c', 'n'), ('c', 'o'), ('c', 'q'),
('c', 'u'),
>             ('d', 'g'), ('d', 'h'), ('d', 'o'), ('d', 'p'), ('d', 'q'),
>             ('e', 'f'), ('e', 'o'),
>             ('f', 'i'), ('f', 'j'), ('f', 'l'), ('f', 'p'), ('f', 't'),
>             ('g', 'j'), ('g', 'o'), ('g', 'p'), ('g', 'q'), ('g', 'y'),
>             ('h', 'k'), ('h', 'l'), ('h', 'm'), ('h', 'n'), ('h', 'r'),
>             ('i', 'j'), ('i', 'l'), ('i', 't'), ('i', 'y'),
>             ('j', 'l'), ('j', 'p'), ('j', 'q'), ('j', 'y'),
>             ('k', 'x'),
>             ('l', 't'),
>             ('m', 'n'), ('m', 'w'),
>             ('n', 'u'), ('n', 'z'),
>             ('o', 'p'), ('o', 'q'), ('o', 'u'), ('o', 'v'),
>             ('p', 'q'), ('p', 'r'),
>             ('q', 'y'),
>             ('s', 'z'),
>             ('u', 'v'), ('u', 'w'), ('u', 'y'),
>             ('v', 'w'), ('v', 'y')
>         )
> Feel free to review and comment current wordlist, but I think we're
slowly moving forward final list.
> slush

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

^ permalink raw reply	[flat|nested] 9+ messages in thread
* [Bitcoin-development] BIP39 word list
@ 2013-10-18 23:52 jan
  2013-10-18 23:58 ` Gregory Maxwell
  2013-10-23  0:56 ` slush
  0 siblings, 2 replies; 9+ messages in thread
From: jan @ 2013-10-18 23:52 UTC (permalink / raw)
  To: bitcoin-development


The words 'public', 'private' and 'secret' could be confusing when
encoding public and private keys. eg. a private key that begins with
the word 'public'.

I think avoiding words that could look similar when written down would
be a good idea aswell. I searched for words that only differ by the
letters c & e, g & y, u & v and found the following:

car ear
cat eat
gear year
value valve

Other combinations could potentially be problematic depending on the
handwriting style: ft, ao, ij, vy, possibly even lt and il?

I've included the search utility I used below.


#include <stdbool.h>
#include <string.h>
#include <stdio.h>

char *similar_char_pairs[] = { "ce", "gy", "uv", NULL };

bool is_similar_char(char c1, char c2)
{
  char **pairs = similar_char_pairs;
  do {
    char *p = *pairs;
    if ((c1 == p[0] && c2 == p[1]) ||
        (c1 == p[1] && c2 == p[0]))
      return true;
  } while (*++pairs);

  return false;
}

bool print_words_if_similar(char *word1, char *word2)
{
  /* reject words of different lengths */
  if (strlen(word1) != strlen(word2))
    return false;

  size_t i, similarcount = 0;
  
  for (i = 0; i < strlen(word1); i++) {
    /* skip identical letters */
    if (word1[i] == word2[i])
      continue;

    /* reject words that don't match */
    if (is_similar_char(word1[i], word2[i]) == false)
      return false;

    similarcount++;
  }

  /* reject words with more than 1 different letter */
  //if (similarcount > 1)
  //  return false;

  printf("%s %s\n", word1, word2);

  return true;
}

int main(void)
{
  /* english.txt is assumed to exist in the working directory
     download from:
     https://github.com/trezor/python-mnemonic/blob/master/mnemonic/wordlist/english.txt */
  FILE* f = fopen("english.txt", "r");
  if (!f) {
    fprintf(stderr, "failed to open english.txt\n");
    return 1;
  }

  /* read in word list, assumes one word per line */
  #define MAXWORD 16
  char wordlist[2048][MAXWORD];
  int word = 0;
  while (fgets(wordlist[word], MAXWORD, f)) {
    /* strip trailing whitespace, assumes no leading whitespace */
    char *ch = strpbrk(wordlist[word], " \n\t");
    if (ch)
      *ch = '\0';
    word++;
  }

  if (word != 2048) {
    fprintf(stderr, "word list incorrect length\n");
    return 1;
  }

  /* check each word for similarity against every other word */
  int i, j, count = 0;
  for (i = 0; i < 2048; i++) {
    for (j = i+1; j < 2048; j++) {
      if (print_words_if_similar(wordlist[i], wordlist[j]))
        count++;
    }
  }

  printf("%d matches\n", count);
  
  return 0;
}



^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2013-11-02  4:31 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-11-01 20:14 [Bitcoin-development] BIP39 word list Brooks Boyd
2013-11-01 23:41 ` Allen Piscitello
2013-11-02  0:04 ` slush
2013-11-02  4:31   ` Brooks Boyd
  -- strict thread matches above, loose matches on Subject: below --
2013-10-18 23:52 jan
2013-10-18 23:58 ` Gregory Maxwell
2013-10-19 10:11   ` Pavol Rusnak
2013-10-24 13:26   ` slush
2013-10-23  0:56 ` slush

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox