Add Bitpie mnemonics import

[matevz]

Before ADR 0008 was settled, some ROSE wallets already existed (Bitpie probably being the most widely used) with slightly different path derivation.

From the private slack conversation with bitpie team:

Bitpie ROSE derivation path:
1. Use the ECDSA curve to derive the master private key of ROSE, derive path m/44'/474‘/0’
2. The ROSE master private key continues to be derived using Ed25519, derive path m/0/0

I propose the following:

• [ ] implement alternative (bitpie) derivation path
• [ ] check if the alternatively computed wallet address (and private key) from mnemonics matches the one from bitpie wallet
• [ ] GUI: in the Import wallet from mnemonics screen, add a checkbox Legacy mnemonic derivation path (Bitpie users). If checked, use this alternative derivation path

[pro-wh]

I've heard that existing Ledger accounts also uses a different derivation formula. Could we also similarly add that?

[lukaw3d]

~Bitpie test mnemonic: cement earn silver hidden butter grid fee sting will soda sort stomach should generate private key: uVbOfoQg20q7zLb2u3cRBNIco/B5o+75Lys2a/LTb8YL5xONsuvJa2dqrklrgdJQbUenl/CChKzntPda35D3+w== address: oasis1 qz4k 7tlr p4fe 2hp5 yp8h mdkv htk9 km54 6s6j th2s~

Edit: bitpie wallet on Luka's phone sometimes generated private keys that didn't work :shrug: maybe this is incorrect

[Yawning]

While I am sketching out an implementation of this derivation method, I am extremely against this for a number of reasons.

• They opted to actually use BIP32-Ed25519, which is evil and should be destroyed. More to the point, it requires being able to use 64-byte representations of Ed25519 private keys, which is more of a historical curiosity than something that should be used for anything.
• Their derivation implementation is over-complicated, and requires pulling in code for secp256k1 arithmetic.

If it were up to me "transfer to a different address if you want to migrate off bitpie, WONTFIX" should be the solution.

[Yawning]

I am totally confused. The private key you gives, is 32-bytes followed by the public key (which corresponds to the address you provided). However I have no idea what the first 32-bytes represents as I fail to get a matching public key when I try interpreting it as a RFC 8032-style seed or raw scalar.

So this will either getting more details from them, or ripping apart their APK.

[Yawning]

Anyway, what doesn't appear to work is:

1. seed <- BIP-32(Mnemonic)
2. master_key <- BIP32-secp256k1(seed, "m/44'/474'/0'")
3. private_key <- BIP32-ed25519(master_key, "m/0/0") // Where the secp256k1 scalar in the standard big endian representation is used as the new seed.

But at the point where the example provided by @lukaw3d doesn't appear to deserialize via any of the standard methods to something consistent, there are other issues preventing implementing this (Which I still will assert is a terrible idea).

[Yawning]

Well, with a working example that @matevz gave me, the private key is indeed a RFC 8032 seed, with the public key appended to it (so NaCl-style representation).

The derivation process they claim to be using is incapable of producing private keys of this form. The output of BIP32-Ed25519 is (scalar, nonce), while the private key they export is input that is fed into SHA-512 to derive (scalar, nonce).

I suspect that there is a massive miscommunication somewhere, or there is something extremely exotic in the APK, that would cause the academic cryptography community to go into a frenzy of panic.

[matevz]

My Bitpie mnemonics and private key which works fine with oasis wallets:

Bitpie mnemonic: cross enable vendor service pulse account ceiling omit trial myself front misery private key: Ti5c02lEEmMyL7KpXLos0UN3Zi9iMxfHQFSNN5Noe8CvoATShjZB9ppupyXLerynDWBpxHbsPtEZxtxscvpOeQ== address: oasis1qp8d9kuduq0zutuatjsgltpugxvl38cuaq3gzkmn

[lujunZhang]

Well, with a working example that @matevz gave me, the private key is indeed a RFC 8032 seed, with the public key appended to it (so NaCl-style representation).

The derivation process they claim to be using is incapable of producing private keys of this form. The output of BIP32-Ed25519 is (scalar, nonce), while the private key they export is input that is fed into SHA-512 to derive (scalar, nonce).

I suspect that there is a massive miscommunication somewhere, or there is something extremely exotic in the APK, that would cause the academic cryptography community to go into a frenzy of panic.

I have roughly written an example of the derivation here for your reference. You need to pay attention to the nonHardenedChild method.

Bitpie mnemonic: cross enable vendor service pulse account ceiling omit trial myself front misery

Master key: fe333947e1dce3fcfa377dce4099f2972eadc25b1b6a4d5f60878969cd657bc0

Private key (m/0): 0ef310a16dcc1b68ac50b2b9c4890d076ab4128945db2d51e9f049ffb8667bc093262aee1b625f793b7631f7879195e93b9bb89e2dd09cd5d639e00cb738462a

Private key (m/0/0): 4e2e5cd369441263322fb2a95cba2cd14377662f623317c740548d3793687bc0afa004d2863641f69a6ea725cb7abca70d6069c476ec3ed119c6dc6c72fa4e79

m/0 = newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).expBytes() m/0/0 = newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).onHardenedChild(BigEndian.int32(0)).expBytes()

//int PrivateKeySize = 64;

OasisPrivateKey newKeyFromSeed(byte[] seed) {
    byte[] prv = new byte[PrivateKeySize];
    System.arraycopy(seed, 0, prv, 0, 32);
    return new OasisPrivateKey(prv);
}

EdPrivateKey nonHardenedChild(byte[] selector) {
    byte[] xpub = XPub().toBytes();
    byte[] pub = new byte[32];
    System.arraycopy(xpub,32,pub,0,32);

    byte[] input = new byte[32 + 1 + selector.length];
    System.arraycopy("N".getBytes(),0,input,0,1);
    System.arraycopy(xpub,0,input,1,32);
    System.arraycopy(selector,0,input,33,selector.length);

    byte[] h = HDUtils.hmacSha512(HDUtils.createHmacSha512Digest(pub), input);

    pruneIntermediateScalar(h);

    int sum = 0;
    for (int i = 0; i < 32; i++) {
        sum = (toBytes()[i] & 0xff) + (h[i] & 0xff) + (sum >> 8);
        h[i] = (byte)(sum & 0xff);
    }

    if(sum >> 8 != 0) {
        throw new IllegalArgumentException("sum does not fit in 256-bit int");
    }
    return new EdPrivateKey(h);
}

EdPublicKey XPub() {
    byte[] scalar = new byte[32];
    System.arraycopy(toBytes(),0,scalar,0,32);
    GroupElement point = ED_25519_CURVE_SPEC.getB().scalarMultiply(scalar);
    byte[] buf = point.toByteArray();
    byte[] xpub = new byte[64];
    System.arraycopy(buf,0,xpub,0,32);
    System.arraycopy(toBytes(),32,xpub,32,32);
    return new EdPublicKey(xpub);
}

void pruneIntermediateScalar(byte[] f) {
    f[0] &= 248;
    f[29] &= 1;
    f[30] = 0;
    f[31] = 0;
}

byte[] expBytes() {
    byte[] exp = new byte[PrivateKeySize];
    System.arraycopy(toBytes(), 0, exp, 0, 32);
    System.arraycopy(XPub().toBytes(), 0, exp, 32, 32);
    return new String(Base64.encode(exp), Charset.forName("UTF-8"));
}

[Yawning]

@lujunZhang

Thanks, this helps. This looks like a incompatible variant of the algorithm in Khovratovich/Law's "BIP32-Ed25519 Hierarchical Determinsitc Keys over a Non-linear Keyspace".

Differences, using the paper as the baseline:

• The paper specifies i as a unsigned 32-bit integer ("indexed from 0 to 2^32-1"), the example uses signed integers. This has no impact in practice.
• The paper specifies that i in the context of HMAC input is serialized in little-endian byte order, the example uses big-endian. This makes no functional difference for i == 0, but a world of difference for everything else.
• The paper uses Z = HMAC-SHA512(C_P, 0x02 | A_P | i), the example uses Z = HMAC-SHA512(C_P, 'N' | A_P | i).
• Step 2 is totally different. The paper uses 224-bits of the digest ("Z_L is the left 28-byte part of Z") and multiplies by the cofactor, the example uses 225-bits of the digest and clears the cofactor.
• The paper checks to see if the resulting scalar is divisible by the base order, the example checks to see if the addition will overflow a uint256 instead.
• Step 3 is missing. The paper does C_i = HMAC_SHA512(C_P, 0x03 | A_P | i)[32:], the example uses what the paper calls Z_R (ie: the right 32-bytes of Z).

Open questions:

• The master key is a 256-bit value. nonHardenedChild requires 512-bits of input. How does this go from the master key to m/0? I can derive A_P with a scalar-basepoint multiply, but xpub[32:] (the chain code in BIP-32 terms) is missing.
• The example that @matevz gave to me that is reportedly the result of exporting a key generated by the bitpie wallet appear of the form RFC 8032 seed || public key, as interpreting the leading 32-bytes as a RFC 8032 seed, and deriving the public key gives a byte-for-byte identical result to the trailing 32-bytes. How does the export function convert from the output of the example to what @matevz gave me? This should be impossible.

References:

• https://github.com/LedgerHQ/orakolo/blob/master/papers/Ed25519_BIP%20Final.pdf

[lujunZhang]

@Yawning your analysis is very comprehensive. There are differences in the implementation of the algorithm. For this implementation, we refer to Bytom. This is the first public chain supported by our wallet to use ed25519. Regarding your question I re-edited my example above.

• sorry i missed the method newKeyFromSeed.
• The last 32-bytes are the public key expBytes, after base64 is the exported private key.

[Yawning]

@lujunZhang Ok, that makes more sense, and I can deserialize your interemdiaries and get the expected results, which clarifies the export question.

I still do seem to have trouble reproducing the child derivation process. Perhaps you can shed some insight into this.

I can convert the mnemonic into a seed, and do the secp256k1 style BIP-39 to get the master key in your example (fe333947e1dce3fcfa377dce4099f2972eadc25b1b6a4d5f60878969cd657bc0).

What I can't do is go from the master key to m/0, because there is a step missing.

In simple terms, nonHardenedChild() requires 96-bytes of input.

• The scalar (toBytes()[0:32])
• The public key (XPub().toBytes()[0:32])
• The chain code (XPub().toBytes()[32:64])

I am fairly confident that you are using the master key as the scalar (due to the trailing bits of the private keys being 7bc0 remaining unaltered from the master key through all the derivations).

What I am having trouble with is figuring out what the chain code is, though It is possible that I have a subtle bug in my derivation routine somewhere. Further clarity would be appreciated. The output of toBytes() for each step, including prior to calling the first call to nonHardenedChild() would also be extremely helpful.

[lujunZhang]

newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).onHardenedChild(BigEndian.int32(0)).

This is the detailed test data, you can try again.

m/0/0:

m = fe333947e1dce3fcfa377dce4099f2972eadc25b1b6a4d5f60878969cd657bc0

newKeyFromSeed(m).toBytes() = fe333947e1dce3fcfa377dce4099f2972eadc25b1b6a4d5f60878969cd657bc00000000000000000000000000000000000000000000000000000000000000000

newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).toBytes() = 0ef310a16dcc1b68ac50b2b9c4890d076ab4128945db2d51e9f049ffb8667bc05d294b5eba1b20afa30f4420992fef8ba741abaab5f02458884accd31afc0b62

newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).expBytes() = 0ef310a16dcc1b68ac50b2b9c4890d076ab4128945db2d51e9f049ffb8667bc093262aee1b625f793b7631f7879195e93b9bb89e2dd09cd5d639e00cb738462a

newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).onHardenedChild(BigEndian.int32(0)).toBytes() = 4e2e5cd369441263322fb2a95cba2cd14377662f623317c740548d3793687bc05fb00636aaca0fd18aff232c6dee96a38c80170258fc0f5c3ecc7d16c8555f85

newKeyFromSeed(m).nonHardenedChild(BigEndian.int32(0)).onHardenedChild(BigEndian.int32(0)).expBytes() = 4e2e5cd369441263322fb2a95cba2cd14377662f623317c740548d3793687bc0afa004d2863641f69a6ea725cb7abca70d6069c476ec3ed119c6dc6c72fa4e79

expBytes().base64() = Ti5c02lEEmMyL7KpXLos0UN3Zi9iMxfHQFSNN5Noe8CvoATShjZB9ppupyXLerynDWBpxHbsPtEZxtxscvpOeQ==

[Yawning]

Thanks. I pushed my work in progress implementation to a branch so I can revisit this later, though I have a suspicion that it has to do with the following:

The master secret when interpreted as a little-endian 256-bit scalar is greater than the basepoint order (edd3f55c1a631258d69cf7a2def9de1400000000000000000000000000000010 little-endian).

As the Java code looks like it uses str4d's ed25519-java, the scalarMultiply routine has the precondition a[31] <= 127. I'm not sure what happens when this precondition is violated in a ref10 derived Ed25519 implementation, and I currently do not have time to do the analysis.

The reference Go code side-steps this by including a routine pruneRootScalar that does some bit-twidding. Note that it calls what essentially is a Go port of ref10, so even without the bit-twidding, this may produce inter-operable results, but this requires detailed analysis.

The ed25519 library that Oasis uses has "reject", "mask off the high-bit", and "reduce mod N" as options for behavior when de-serializing non-canonical scalars, neither of which are compatible behavior with the Java implementation (which is "YOLO, use it anyway").

[matevz]

BitPie mnemonic support was implemented in the Oasis unmnemonic tool instead.