Extended key lineage.depth overflows and produces garbage key

[quapka]

I've tested the following on version3 and also master (the code needs to be slightly different for the version3 to compile.

#include <bitcoin/system.hpp>
#include <string.h>
#include <iostream>

#include <stdio.h>
#include <stdlib.h>

using namespace bc;
using namespace libbitcoin::system;
using namespace bc::system::wallet;


int main() {

    // Example tests from https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#test-vector-1
    data_chunk hd_seed = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f};

    /* data_chunk seed_chunk(to_chunk(hd_seed)); */
    hd_private m(hd_seed, hd_private::mainnet);
    hd_public y = m.to_public();

    for (int i = 0; i < 255; i++) {
        y = y.derive_public(0);
    }
    printf("%d: ", y.lineage().depth);
    std::cout << y << std::endl;

    y = y.derive_public(0);
    printf("%d: ", y.lineage().depth);
    std::cout << y << std::endl;

    return 0;
}

(The example does not show this for hd_private, because I couldn't get the demo to derive 256th key, but the problem is most likely the same for hd_private as well.)

which gives the following output:

255: xpubEND4cWBkwMUcwj3bjw4RNYcpnuvgbEaGSCAujB1XQro3Ptpvs8hDMFsBmk1mhfz9sGc3k4XPpueGAcR66Kb7HMXwfnKKBaV3i7YyMxLuwKh
0: 1111111111111111111111111111111111111111111111111111111111111111111111111111114rcJhr

For the version3 case it seemed clear, why the overflow happens in hd_private.cpp and hd_public.cpp. I haven't investigated further, where does the 1111111111111111111111111111111111111111111111111111111111111111111111111111114rcJhr value come from though.

The master versions hd_private.cpp and hd_public.cpp seem to be aware of this, but from my testing I see the same result for version3 and master.

Maybe I just misunderstood how the key derivation is intended to work, but also from checking the examples, I am failing to see, e.g., some checks, that would be supposed to catch this in the client's code.

[evoskuil]

The serialization is for the null key (an error return as a consequence of the 1 byte depth overflow):

https://github.com/libbitcoin/libbitcoin-system/blob/master/src/wallet/keys/hd_private.cpp#L253-L254

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#serialization-format

4 byte: version bytes (mainnet: 0x0488B21E public, 0x0488ADE4 private; testnet: 0x043587CF public, 0x04358394 private)
1 byte: depth: 0x00 for master nodes, 0x01 for level-1 derived keys, ....
4 bytes: the fingerprint of the parent's key (0x00000000 if master key)
4 bytes: child number. This is ser32(i) for i in xi = xpar/i, with xi the key being serialized. (0x00000000 if master key)
32 bytes: the chain code
33 bytes: the public key or private key data (serP(K) for public keys, 0x00 || ser256(k) for private keys)

We don't support a derivation depth beyond what is serializable.

[quapka]

Sorry, if I wasn't clear. My point is exactly the same as yours. But I see now that I've missed the checking, such as here. I didn't see any such checks in the examples. So, whenever a key is derived it's better to immediately check:

key.derive_{private|public}(*)
if (!key) {
  ... handle lack of key...
}

Would highlighting the need to check for a valid key after derivation make sense to you? And maybe adding a test case?

[evoskuil]

Generally speaking, if a constructed wallet object has a bool override, that's for validity. The EC construction of a key can fail also. It's rare, and most people seem to ignore it, but it's real. So it's not sufficient to just guard depth (in this case).

Example code always tends to be light on error handling, as a software industry practice. And libbitcoin documentation doesn't really exist yet. It's hard to produce test case failures for libsecp25k1 failures, without a means to inject the library - which is often a bit much in C++. But in this case the condition is easily reproduced and really should be incorporated into test. Pull requests always welcome!

[quapka]

Generally speaking, if a constructed wallet object has a bool override, that's for validity.

Thanks, good to know.

The EC construction of a key can fail also. It's rare, and most people seem to ignore it, but it's real. So it's not sufficient to just guard depth (in this case).

While deriving 255+ depth keys is maybe not common, it's guaranteed to produce incorrect keys. Compared to the EC or Hash512 very unlikely failures. But I agree that all shall be accounted for.

Example code always tends to be light on error handling, as a software industry practice.

It is now, but should that be the case?

And libbitcoin documentation doesn't really exist yet.

Sure, understandable. There is always too many things to do at once :)

It's hard to produce test case failures for libsecp25k1 failures, without a means to inject the library - which is often a bit much in C++. But in this case the condition is easily reproduced and really should be incorporated into test. Pull requests always welcome!

I've tried to quickly stitch together some cases, see #1624. Surprisingly, there seems to be one troublesome derivation code path.

[evoskuil]

It is now, but should that be the case?

It's a tradeoff, since error handling tends to make up most code, it's harder to see primary behavior when example are littered with comprehensive error handling. In many cases this is intentional. In libbitcoin the sample code is contributory and hasn't been reviewed by developers.