Bitcoinjs-lib: HDNode with consistent and quick serialization

[karelbilek]

Hello,

is there a way to serialize/deserialize HDNode to a JavaScript object in a way, that's efficient?

We are now saving HDNodes in MyTrezor using toBase58 and HDNode.fromBase58; however, we found this to be quite slow, especially if the user has more such HDNodes (one per account).

I am now experimenting with function like this, but it feels too "hacky" and any internal implementation change might break something. However, the speed is immediately obvious. (We _do_ know that the HDNode is neutered.)

function serializeBitcoinJsHDPubNode(node) {
    return {
        depth: node.depth,
        index: node.index,
        parentFingerprint: node.parentFingerprint,
        chainCode: node.chainCode,
        Q: node.keyPair.Q.getEncoded(false),
    };
}

function deserializeBitcoinJsHDPubNode(node) {
    const depth = node.depth;
    const index = node.index;
    const parentFingerprint = node.parentFingerprint;
    const chainCode = new Buffer(node.chainCode);
    const Q = ecurve.Point.decodeFrom(bcurve, new Buffer(node.Q));
    const res = new HDNode(new ECPair(null, Q), chainCode);
    res.depth = depth;
    res.index = index;
    res.parentFingerprint = parentFingerprint;
    return res;
}

[karelbilek]

I might have said, the speed is probably more important for the _de_serialization...

[dcousens]

While the performance of these functions (HDNode.*Base58) leaves so much to be desired, and is easily resolved by https://github.com/bitcoinjs/bitcoinjs-lib/issues/610 (aka, moving to a faster ECDSA library), there are other tricks you can do.

Lazy evaluation is by far the simplest path through this.

However, if that isn't possible, you could just save the X/Y bigi coordinates of the ECPoint rather than re-calculating (ecurve.Point.decodeFrom) them each time.
This is the only real operation that takes any time.

On second thoughts, just use the non-compressed versions of the public key and then switch the compressed flag on import.
That would almost be as performant as just a new Buffer operation IIRC.

edit:
Q: node.keyPair.Q.getEncoded(false),
Oh, you are already doing this... where is the performance issue then?

edit2:
You were already doing the above, therefore, short of lazy evaluation (at the application level), I'd say #610 is the best alternative here.

[dcousens]

I am now experimenting with function like this, but it feels too "hacky" and any internal implementation change might break something.

Understandable, and I apologise we haven't moved on #610 sooner to make this not worth your time, that said, you can assume these are part of the public API and will adhere to SEMVER.

is there a way to serialize/deserialize HDNode to a JavaScript object in a way, that's efficient?

To answer your actual question, I'd say you have hit the nail on the head as to the best path forward.

however, we found this to be quite slow, especially if the user has more such HDNodes (one per account).

Are you feeling this problem in the web browser?
I do 100's of these operations in the space of a second in a mobile browser, let alone the web browser and never feel this as a performance issue.

[karelbilek]

I do 100's of these operations in the space of a second in a mobile browser, let alone the web browser and never feel this as a performance issue.

Interesting. I will make a test script page just for this and will share it here.

[dcousens]

@runn1ng I'm using https://github.com/bitcoinjs/bip32-wallet for my wallets, which lazily uses this.account.getChildren(addresses, [external, internal]) to retrieve the BIP32 nodes when needed.
The only time I ever successively run a en-mass derivation is when doing the initial discovery (or during a catch up after several weeks of being offline w/ payments).

See https://github.com/bitcoinjs/bip32-wallet/blob/master/index.js#L24-L44

[karelbilek]

Here you go. Super simple and easy script that just do 100 of BIP32 deserializations

  var HDNode = bitcoin.HDNode;
  var begin = Date.now();
  for (var i = 0; i < 100; i++) {
      var newNode = HDNode.fromBase58("xpub6BiVtCpG9fQPxnPmHXG8PhtzQdWC2Su4qWu6XW9tpWFYhxydCLJGrWBJZ5H6qTAHdPQ7pQhtpjiYZVZARo14qHiay2fvrX996oEP42u8wZy");
  }
  var end = Date.now();
  var timeSpent = (end - begin) + " ms";
  document.querySelector("#info").innerHTML = timeSpent;

it is here

https://github.com/runn1ng/bitcoinjs-serialization-performance

and deployed here using github pages

http://www.karelbilek.com/bitcoinjs-serialization-performance/

It takes 7 seconds on my Linux Chrome, 15 seconds on my Android Chrome, 4.7 seconds on my Linux Firefox (huh, it used to be slower than Chrome, now it seems to be actually quicker... I wonder what happened). I use the newest version of bitcoin.js (it is browserified in bitcoin.js).

[karelbilek]

Interestingly enough, if I deserialize it from xprv, it is basically instant!

https://github.com/runn1ng/bitcoinjs-serialization-performance/blob/gh-pages/index-xprv.html

http://www.karelbilek.com/bitcoinjs-serialization-performance/index-xprv.html

So it is issue _only_ when deserializing neutered nodes.

[karelbilek]

Most time is spent on this line
https://github.com/bitcoinjs/bitcoinjs-lib/blob/master/src/hdnode.js#L114

    // Verify that the X coordinate in the public point corresponds to a point on the curve.
    // If not, the extended public key is invalid.
    curve.validate(Q)

So, for me, the easiest "fix" would be to add option to skip validation here.

[karelbilek]

screenshot from profiler (sorry if it ends up too giant)

[karelbilek]

I have added a PR and indeed, with the skipValidation set to true, the deserialization is instant

Version of the script with patch #620 and skipValidation to true :

https://github.com/runn1ng/bitcoinjs-serialization-performance/blob/gh-pages/index-patched.html

http://www.karelbilek.com/bitcoinjs-serialization-performance/index-patched.html

[dcousens]

Good find. Indeed that function has always been a pain in the ass.
My Chrome performed the test in 2559 ms... in any case, still quite long.

I'm not sure if just skipping it is the right answer... but I'll certainly look into the options.

[karelbilek]

Thanks. It is definitely better for my use case than saving it in the low level representation (since that might change in the future, for example with the new bignum library).

[dcousens]

@runn1ng my concern is this hack will go away with 3.0.0 because we'll be using bn.js.
Maybe it'd be better off doing that conversion now instead of this 1 edge case optimization?

[karelbilek]

Is bn.js that much faster?

[dcousens]

@runn1ng we're talking about 10-20x IIRC.

[karelbilek]

Oh. In that case, my skipVerification hack might not be needed long-term. So yeah I understand your hesitation

I am however already using it short-term in my patched version in a new mytrezor version (not yet online, but soon).

[dcousens]

Related #623 and #620. (Closing in favour of)