Generation of addresses with unique 2-char postfixes (from a seed). 1225 limit?

[reardenlife]

I wrote a little tool on JS which generate addresses with unique postfixes.
It derives addresses from bip39 mnemonic and uses increments of bip44 derivation path.
What surprised me is that the total number of these addresses is somehow limited to 1225 (I ran increments into 1M, but the unique addresses dwindle out at about 20k), instead of expected 3364 (58^2).
Can anyone expain why this is the case?

Code:

const bitcoin = require('bitcoinjs-lib');
const bip32 = require('bip32');
const bip39 = require('bip39');
const EventEmitter = require('events');
var eventEmitter = new EventEmitter()

function db() {
        var knex = require('knex')({
                client: 'mysql',
                connection: {
                        host : '127.0.0.1',
                        user : 'root',
                        password : 'pw',
                        database : 'btckeygen'
                }
        });
        return knex;
}

function getAddress (node, network) {
  return bitcoin.payments.p2pkh({ pubkey: node.publicKey, network }).address
}

var knex = db();
const dpath = "m/44'/0'/0'";

eventEmitter.on('eIteration', function(i){
        if ( i % 1000 == 0 )
                console.log(i);
        if ( i < 1000000 )
                syncLoop(i + 1);
        else
                process.exit(0);
});

const mnemonic = 'gesture large void donate enroll demise about fade arrest romance knock breeze melody card another';
const seed = bip39.mnemonicToSeed(mnemonic)
const root = bip32.fromSeed(seed)
const string = root.toBase58()
console.log('BIP32 Root: ' + string);
const bip44xprv = root.derivePath(dpath)
const bip44xpub = bip44xprv.neutered().toBase58();
console.log('Account xprv: ' + bip44xprv.toBase58());
console.log('Account xpub: ' + bip44xpub);
const bip32xprv = root.derivePath(dpath + "/0")
const bip32xpub = bip32xprv.neutered().toBase58();
console.log('BIP32 xprv: ' + bip32xprv.toBase58());
console.log('BIP32 xpub: ' + bip32xpub);

function syncLoop(i) {
        const dpathi = dpath + "/0/" + i ;
        const child = root.derivePath(dpathi)
        const addr = getAddress(child, bitcoin.networks.mainnet);
        //console.log('Child' + i + ' Address: ' + addr);
        const prv = child.privateKey.toString('hex');
        const pub = child.publicKey.toString('hex');

        var search = addr.substr(-2);
        knex
  .select('address')
        .from('keystore')
  .where(knex.raw('RIGHT(??, 2) = ?', ['address', `${search}`]))
        .then(function (result) {
                if ( !result || result.length == 0 ) {
                        //console.log(result);
                        //console.log(this.path);
                        knex.insert({derivation_path: this.path, address: this.address, pub: this.pub, prv: this.prv})
                        .returning('id')
                        .into('keystore')
                        .then(function (id) {
                                console.log(id);
                        })
                        .catch(function(e) {
                                console.error(e);
                        });
                }
                eventEmitter.emit('eIteration', this.i)
         }.bind({path:dpathi, address:addr, pub:pub, prv:prv, i:i})
        )
        .catch(function(e) {
                console.error(e);
        });
}

syncLoop(0);

[1714036294]

1714036294

[1714036294]

1714036294

[1714036294]

1714036294

[1714036294]

1714036294

[reardenlife]

Holy cow.

So I modified the program a little bit by adding the second table which keeps the seed.  I generated 1225 addresses with one mnemonic, and then commented it out and put the second one.  I was expecting to get some more addresses due to the new seed.  To my surprise, I've got 0 new (2 last char unique).  Here:

Code:

const bitcoin = require('bitcoinjs-lib');
const bip32 = require('bip32');
const bip39 = require('bip39');
const EventEmitter = require('events');
var eventEmitter = new EventEmitter()

function db() {
        var knex = require('knex')({
                client: 'mysql',
                connection: {
                        host : '127.0.0.1',
                        user : 'root',
                        password : 'pw',
                        database : 'btckeygen'
                }
        });
        return knex;
}

function getAddress (node, network) {
  return bitcoin.payments.p2pkh({ pubkey: node.publicKey, network }).address
}

var knex = db();
const dpath = "m/44'/0'/0'";

eventEmitter.on('eIteration', function(i, _bip32root, fk_seed){
        if ( i % 1000 == 0 )
                console.log(i);
        if ( i < 1000000 )
                syncLoop(i + 1, _bip32root, fk_seed);
        else
                process.exit(0);
});

//const mnemonic = 'cube violin apple bounce sign wine spare hood receive trade unique silk frequent embody unveil';
const mnemonic = 'detect force general regular nation profit kidney spray evil rice juice raccoon crop assume maze';
const seed = bip39.mnemonicToSeed(mnemonic);
const _bip32root = bip32.fromSeed(seed);
const bip32root = _bip32root.toBase58();
console.log('BIP32 Root: ' + bip32root);
const _bip44xprv = _bip32root.derivePath(dpath);
const bip44xprv = _bip44xprv.toBase58();
const bip44xpub = _bip44xprv.neutered().toBase58();
console.log('Account xprv: ' + bip44xprv);
console.log('Account xpub: ' + bip44xpub);
const _bip32xprv = _bip32root.derivePath(dpath + "/0");
const bip32xprv = _bip32xprv.toBase58();
const bip32xpub = _bip32xprv.neutered().toBase58();
console.log('BIP32 xprv: ' + bip32xprv);
console.log('BIP32 xpub: ' + bip32xpub);

// Get fk_seed
//

knex
.select('id')
.from('seed')
.where('bip32root', '=', bip32root)
.then(function (result) {
        if ( !result || result.length == 0 ) {
                        console.log(result);
                        knex.insert({mnemonic: this.mnemonic, bip32root: this.bip32root, bip44xprv: this.bip44xprv, bip44xpub: this.bip44xpub, bip32xprv: this.bip32xprv, bip32xpub: this.bip32xpub})
                        .returning('id')
                        .into('seed')
                        .then(function (id) {
                                syncLoop(0, this._bip32root, id);
                        }.bind({_bip32root: this._bip32root}))
                        .catch(function(e) {
                                console.error(e);
                        });
        }
        else {
                syncLoop(0, this._bip32root, result[0].id);
        }
        }.bind({mnemonic: mnemonic, bip32root: bip32root, _bip32root: _bip32root, bip44xprv: bip44xprv, bip44xpub: bip44xpub, bip32xprv: bip32xprv, bip32xpub: bip32xpub})
)
.catch(function(e) {
        console.error(e);
});


function syncLoop(i, _bip32root, fk_seed) {
        const dpathi = dpath + "/0/" + i ;
        const child = _bip32root.derivePath(dpathi)
        const addr = getAddress(child, bitcoin.networks.mainnet);
        //console.log('Child' + i + ' Address: ' + addr);
        const prv = child.privateKey.toString('hex');
        const pub = child.publicKey.toString('hex');

        var search = addr.substr(-2);
        knex
  .select('address')
        .from('keystore')
  .where(knex.raw('RIGHT(??, 2) = ?', ['address', `${search}`]))
        .then(function (result) {
                if ( !result || result.length == 0 ) {
                        //console.log(result);
                        //console.log(this.path);
                        knex.insert({fk_seed:fk_seed, derivation_path: this.path, address: this.address, pub: this.pub, prv: this.prv})
                        .returning('id')
                        .into('keystore')
                        .then(function (id) {
                                console.log(id);
                        })
                        .catch(function(e) {
                                console.error(e);
                        });
                }
                eventEmitter.emit('eIteration', this.i, this._bip32root, this.fk_seed)
         }.bind({path:dpathi, address:addr, pub:pub, prv:prv, i:i, _bip32root:_bip32root, fk_seed:fk_seed})
        )
        .catch(function(e) {
                console.error(e);
        });
}

DB:

Code:

-- phpMyAdmin SQL Dump
-- version 4.8.3
-- https://www.phpmyadmin.net/
--
-- Host: localhost
-- Generation Time: Mar 30, 2019 at 08:18 PM
-- Server version: 10.1.35-MariaDB
-- PHP Version: 7.2.12

SET SQL_MODE = "NO_AUTO_VALUE_ON_ZERO";
SET AUTOCOMMIT = 0;
START TRANSACTION;
SET time_zone = "+00:00";

--
-- Database: `btckeygen`
--

-- --------------------------------------------------------

--
-- Table structure for table `keystore`
--

CREATE TABLE `keystore` (
  `id` int(11) NOT NULL,
  `fk_seed` int(11) NOT NULL,
  `derivation_path` varchar(20) NOT NULL,
  `address` varchar(50) NOT NULL,
  `pub` varchar(200) NOT NULL,
  `prv` varchar(200) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- --------------------------------------------------------

--
-- Table structure for table `seed`
--

CREATE TABLE `seed` (
  `id` int(11) NOT NULL,
  `mnemonic` varchar(200) NOT NULL,
  `bip32root` varchar(200) NOT NULL,
  `bip32xpub` varchar(200) NOT NULL,
  `bip32xprv` varchar(200) NOT NULL,
  `bip44xpub` varchar(200) NOT NULL,
  `bip44xprv` varchar(200) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

--
-- Indexes for dumped tables
--

--
-- Indexes for table `keystore`
--
ALTER TABLE `keystore`
  ADD PRIMARY KEY (`id`);

--
-- Indexes for table `seed`
--
ALTER TABLE `seed`
  ADD PRIMARY KEY (`id`),
  ADD UNIQUE KEY `bip32root` (`bip32root`);

--
-- AUTO_INCREMENT for dumped tables
--

--
-- AUTO_INCREMENT for table `keystore`
--
ALTER TABLE `keystore`
  MODIFY `id` int(11) NOT NULL AUTO_INCREMENT;

--
-- AUTO_INCREMENT for table `seed`
--
ALTER TABLE `seed`
  MODIFY `id` int(11) NOT NULL AUTO_INCREMENT;
COMMIT;

So .. why the hell there is only 1225 unique seed-independent 2 char postfixes in BTC addresses?

[reardenlife]

Woops.
I forgot that string comparison in mysql is case-sensitive by default.  

After 24k tries I successfully generated 3364 addresses.

[reardenlife]

Alright.  But now it appears that I hit some kind of limit.  Check it out.

I increased the number of unique characters to three - the second character from the left of the address and two from the right so the total number of addresses is 195112.  I generated them all for p2pkh addresses with prefix 1.
Now I switched to p2wpkh-p2sh addresses and for some reason there seems to be only 25 unique prefixes:

Code:

MariaDB [btckeygen2]> select distinct prefix from keystore order by prefix;
+--------+
| prefix |
+--------+
| 31     |
| 32     |
| 33     |
| 34     |
| 35     |
| 36     |
| 37     |
| 38     |
| 39     |
| 3A     |
| 3B     |
| 3C     |
| 3D     |
| 3E     |
| 3F     |
| 3G     |
| 3H     |
| 3J     |
| 3K     |
| 3L     |
| 3M     |
| 3N     |
| 3P     |
| 3Q     |
| 3R     |
+--------+
25 rows in set (0.15 sec)

Any idea why it stops at "R"?

Here is the code:

Code:

const bitcoin = require('bitcoinjs-lib');
const bip32 = require('bip32');
const bip39 = require('bip39');
const EventEmitter = require('events');
var eventEmitter = new EventEmitter()

function db() {
        var knex = require('knex')({
                client: 'mysql',
                connection: {
                        host : '127.0.0.1',
                        user : 'root',
                        password : 'pw',
                        database : 'btckeygen2'
                }
        });
        return knex;
}

function getScriptAddress (node, network) {
        return bitcoin.payments.p2sh({
      redeem: bitcoin.payments.p2wpkh({ pubkey: node.publicKey, network }),
      network
    }).address
}

var knex = db();
const dpath = "m/49'/0'/0'";
const atype = 'p2wpkh-p2sh';
var g_ts = new Date().getTime();
var g_op = 0;

eventEmitter.on('eIteration', function(i, _bip32root, fk_seed){
        if ( i % 10000 == 0 ) {
                var ts = new Date().getTime();
                var diff = ts - g_ts;
                var opsec = g_op / (diff / 1000);
                g_ts = ts;
                g_op = 0;
                console.log(Math.round(opsec * 100) / 100 + ' keys/sec' + '; i = ' + i);
        }
        if ( i < 100000000 )
                syncLoop(i + 1, _bip32root, fk_seed);
        else
                process.exit(0);
});

const mnemonic = 'xxx';
const seed = bip39.mnemonicToSeed(mnemonic);
const _bip32root = bip32.fromSeed(seed);
const bip32root = _bip32root.toBase58();
console.log('BIP32 Root: ' + bip32root);
const _bip44xprv = _bip32root.derivePath(dpath);
const bip44xprv = _bip44xprv.toBase58();
const bip44xpub = _bip44xprv.neutered().toBase58();
console.log('Account xprv: ' + bip44xprv);
console.log('Account xpub: ' + bip44xpub);
const _bip32xprv = _bip32root.derivePath(dpath + "/0");
const bip32xprv = _bip32xprv.toBase58();
const bip32xpub = _bip32xprv.neutered().toBase58();
console.log('BIP32 xprv: ' + bip32xprv);
console.log('BIP32 xpub: ' + bip32xpub);

// Get fk_seed
//

knex
.select('id')
.from('seed')
.where('bip32root', '=', bip32root).andWhere('type', '=', atype)
.then(function (result) {
        if ( result.length == 0 ) {
                        //console.log(result);
                        knex.insert({mnemonic: this.mnemonic, bip32root: this.bip32root, bip44xprv: this.bip44xprv, bip44xpub: this.bip44xpub, bip32xprv: this.bip32xprv, bip32xpub: this.bip32xpub, type: atype})
                        .returning('id')
    A
                        .into('seed')
                        .then(function (id) {
                                syncLoop(0, this._bip32root, id);
                        }.bind({_bip32root: this._bip32root}))
                        .catch(function(e) {
                                console.error(e);
                        });
        }
        else {
                syncLoop(0, this._bip32root, result[0].id);
        }
        }.bind({mnemonic: mnemonic, bip32root: bip32root, _bip32root: _bip32root, bip44xprv: bip44xprv, bip44xpub: bip44xpub, bip32xprv: bip32xprv, bip32xpub: bip32xpub, atype: atype})
)
.catch(function(e) {
        console.error(e);
});


function syncLoop(i, _bip32root, fk_seed) {
        const dpathi = dpath + "/0/" + i ;
        const child = _bip32root.derivePath(dpathi)
        const addr = getScriptAddress(child, bitcoin.networks.mainnet);
        //console.log('Child' + i + ' Address: ' + addr);
        const prv = child.privateKey.toString('hex');
        const pub = child.publicKey.toString('hex');

        var prefix = addr.substr(0, 2);
        var postfix = addr.substr(-2);
        //console.log(prefix + '...' + postfix);
        knex
  .select('address')
        .from('keystore')
  .where(knex.raw('?? = ? AND ?? = ? AND ?? = ?', ['fk_seed', `${fk_seed}`, 'prefix', `${prefix}`, 'postfix', `${postfix}`]))
        .limit(1)
        .then(function (result) {
                if ( result.length == 0 ) {
                        //console.log(result);
                        //console.log(this.path);
                        knex.insert({fk_seed: this.fk_seed, derivation_path: this.path, address: this.address, pub: this.pub, prv: this.prv, prefix: this.prefix, postfix: this.postfix})
                        .returning('id')
                        .into('keystore')
                        .then(function (id) {
                                //console.log(id);
                                g_op++;
                        })
                        .catch(function(e) {
                                console.error(e);
                        });
                }
                eventEmitter.emit('eIteration', this.i, this._bip32root, this.fk_seed)
         }.bind({path:dpathi, address:addr, pub:pub, prv:prv, i:i, _bip32root:_bip32root, fk_seed:fk_seed, prefix:prefix, postfix:postfix})
        )
        .catch(function(e) {
                console.error(e);
        });
}

[reardenlife]

Oh. So it is due to base256-to-base58 conversion.
Since the leading byte is always a constant (0x00 for p2pkh and 0x05 for p2sh), when it converts to base58, it affects not only leading symbol of output, but it partially affects the second symbol also (~2 bits of it).  So it explains the limited number of prefixes (25, not 58).

But why this is not the case for.p2pkh addresses then?  Their structure in base256 is the same - one leading byte.

[reardenlife]

Aha!!

https://en.bitcoin.it/wiki/Base58Check_encoding

The leading character '1', which has a value of zero in base58, is reserved for representing an entire leading zero byte,

That was unexpected. 

[reardenlife]

Oh. So it is due to base256-to-base58 conversion.
Since the leading byte is always a constant (0x00 for p2pkh and 0x05 for p2sh), when it converts to base58, it affects not only leading symbol of output, but it partially affects the second symbol also (~2 bits of it).  So it explains the limited number of prefixes (25, not 58).

Nah.  It is still quite unclear how that conversion works.
1 character in base58 suppose to take about 5.8579 bits (log2(58)).  So that first byte suppose to affect the value of the second base58 character by 2.1420 bits.  But if so, there is only 3.7159 bits left for variable combinations which doesn't add up to 25 of them (log2(25)=4.6438).

Am I missing something?

[reardenlife]

The question is completely resolved.  

https://github.com/bitcoinjs/bitcoinjs-lib/issues/1374#issuecomment-479697090
junderw:

You're overthinking.

We don't convert bits directly since 58 is not a multiple of 2.

Instead, we convert it to a decimal number and encode that number into base58 by divide then mod method.

The question you are asking is akin to: "why does my base64 encoded data change two characters when I'm only changing the last 6 bits of my data?"

The answer is the same:

because positionally, the bitlengths of each character doesn't line up, causing overflow into the adjacent character sometimes.

[reardenlife]

Just wondering, if i want to try your code, do i need to install node.js and configure MySQL (create table, etc.) ?

Yes, you do.

If you will decide so, here is a structure of db and package.json:

Code:

-- phpMyAdmin SQL Dump
-- version 4.8.3
-- https://www.phpmyadmin.net/
--
-- Host: localhost
-- Generation Time: Apr 04, 2019 at 05:33 PM
-- Server version: 10.1.35-MariaDB
-- PHP Version: 7.2.12

SET SQL_MODE = "NO_AUTO_VALUE_ON_ZERO";
SET AUTOCOMMIT = 0;
START TRANSACTION;
SET time_zone = "+00:00";

--
-- Database: `btckeygen`
--

-- --------------------------------------------------------

--
-- Table structure for table `keystore`
--

CREATE TABLE `keystore` (
  `id` int(11) NOT NULL,
  `fk_seed` int(11) NOT NULL,
  `derivation_path` varchar(50) NOT NULL,
  `prefix` char(2) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `address` varchar(50) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `postfix` char(2) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `pub` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `prv` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- --------------------------------------------------------

--
-- Table structure for table `seed`
--

CREATE TABLE `seed` (
  `id` int(11) NOT NULL,
  `mnemonic` varchar(200) NOT NULL COMMENT 'bip39',
  `type` enum('p2pkh','p2wpkh-p2sh','','') NOT NULL DEFAULT 'p2pkh',
  `bip32root` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `bip32xpub` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `bip32xprv` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `bip44xpub` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL,
  `bip44xprv` varchar(200) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

--
-- Indexes for dumped tables
--

--
-- Indexes for table `keystore`
--
ALTER TABLE `keystore`
  ADD PRIMARY KEY (`id`),
  ADD KEY `address` (`address`),
  ADD KEY `fk_seed` (`fk_seed`),
  ADD KEY `prefix` (`prefix`) USING BTREE,
  ADD KEY `postfix` (`postfix`) USING BTREE;

--
-- Indexes for table `seed`
--
ALTER TABLE `seed`
  ADD PRIMARY KEY (`id`),
  ADD UNIQUE KEY `uniqkey` (`type`,`bip32root`) USING BTREE;

--
-- AUTO_INCREMENT for dumped tables
--

--
-- AUTO_INCREMENT for table `keystore`
--
ALTER TABLE `keystore`
  MODIFY `id` int(11) NOT NULL AUTO_INCREMENT;

--
-- AUTO_INCREMENT for table `seed`
--
ALTER TABLE `seed`
  MODIFY `id` int(11) NOT NULL AUTO_INCREMENT;
COMMIT;

Code:

{
  "name": "genbtcaddresses",
  "version": "0.0.1",
  "description": "A program to generate a bunch of BTC addresses from one seed",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "author": "",
  "license": "ISC",
  "dependencies": {
    "bip32": "^2.0.0",
    "bip39": "^2.5.0",
    "bitcoinjs-lib": "^4.0.3",
    "bs58": "^4.0.1",
    "events": "^3.0.0",
    "knex": "^0.16.3",
    "mysql": "^2.16.0",
    "wif": "^2.0.6"
  },
  "postinstall": "find ./node_modules/**/node_modules -type d -name 'bitcore-lib' -exec rm -r {} + && echo 'Deleted duplicate bitcore-libs'"
}