Trying to implement BIP 0032, having some trouble.

[riplin]

Hi,

I'm trying to implement the Hierarchical Deterministic wallet as described in: https://en.bitcoin.it/wiki/BIP_0032

The code path that generates a key pair from a private key works. I can generate the key pairs described here: https://en.bitcoin.it/wiki/BIP_0032_TestVectors

It's the generating a public key from a public key that I'm having trouble with.

My code is based heavily on the java implementation here: https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java

Here's my implementation:

Code:

        private static bool GenerateKeyPair(byte[] aPrivateKey, byte[] aPublicKey, byte[] aChainCode, byte aDepth, uint aParent, uint aSequence, string aLabel, out DeterministicKeyPair aKeyPair)
        {
            aKeyPair = null;

            if (((aSequence & 0x80000000) != 0) && aPrivateKey == null)
                return false;

            byte[] extended = null;
            if ((aSequence & 0x80000000) == 0)
            {
                extended = new byte[aPublicKey.Length + 4];
                Buffer.BlockCopy(aPublicKey, 0, extended, 0, aPublicKey.Length);
                extended[aPublicKey.Length + 0] = (byte)((aSequence >> 24) & 0xff);
                extended[aPublicKey.Length + 1] = (byte)((aSequence >> 16) & 0xff);
                extended[aPublicKey.Length + 2] = (byte)((aSequence >> 8) & 0xff);
                extended[aPublicKey.Length + 3] = (byte)((aSequence >> 0) & 0xff);
            }
            else
            {
                extended = new byte[aPrivateKey.Length + 5];
                Buffer.BlockCopy(aPrivateKey, 0, extended, 1, aPrivateKey.Length);
                extended[aPrivateKey.Length + 1] = (byte)((aSequence >> 24) & 0xff);
                extended[aPrivateKey.Length + 2] = (byte)((aSequence >> 16) & 0xff);
                extended[aPrivateKey.Length + 3] = (byte)((aSequence >> 8) & 0xff);
                extended[aPrivateKey.Length + 4] = (byte)((aSequence >> 0) & 0xff);
            }
            
            byte[] privateKey = null;
            byte[] publicKey = null;
            byte[] chainCode = null;
            
            if (!GenerateKeyPairAndChainCode(aChainCode, extended, out privateKey, out publicKey, out chainCode))
                return false;

            if ((aSequence & 0x80000000) != 0) //This differs from the Java version!
            {
                byte[] newPrivateKey = new byte[32];
                int newPrivateKeyLen = 32;
                Utils.EcdsaAddMod(privateKey, privateKey.Length, aPrivateKey, aPrivateKey.Length, newPrivateKey, ref newPrivateKeyLen);
                
                if (Utils.VerifySecretKey(newPrivateKey) != 1)
                    return false;

                byte[] newPublicKey = new byte[33];
                int newPublicKeyLen = 33;

                if (Utils.PublicKeyFromSecretKey(newPublicKey, ref newPublicKeyLen, newPrivateKey, 1) != 1)
                    return false;

                    aKeyPair = new DeterministicKeyPair(newPrivateKey, newPublicKey, chainCode, aDepth, aParent, aSequence, aLabel);
            }
            else
            {
                byte[] newPublicKey = Utils.ECPointMultiplyAdd(privateKey, aPublicKey, true);
                if (newPublicKey == null)
                    return false;

                aKeyPair = new DeterministicKeyPair(newPublicKey, chainCode, aDepth, aParent, aSequence, aLabel);
            }

            return true;
        }

And this is the ECPointMultiplyAdd function:

Code:

        public static byte[] ECPointMultiplyAdd(byte[] aPrivateKey, byte[] aPublicKey, bool aCompressed)
        {
            X9ECParameters ps = Org.BouncyCastle.Asn1.Sec.SecNamedCurves.GetByName("secp256k1");
            ECPoint point = ps.Curve.DecodePoint(aPublicKey);

            ECPoint pubPoint = ps.G.Multiply(new BigInteger(1, aPrivateKey)).Add(point);
            
            pubPoint = ps.Curve.CreatePoint(pubPoint.X.ToBigInteger(), pubPoint.Y.ToBigInteger(), aCompressed);

            if (pubPoint.IsInfinity)
                return null;

            return pubPoint.GetEncoded();
        }

The biggest difference between my code and the Java version is the last if statement in the GenerateKeyPair function. In the Java implementation, it checks if the private key is available regardless if the most significant bit is set or not. Personally, I believe this to be a bug, since it's using the public key version of 'extended' to generate the key, instead of the private key version. I was wrong.

But regardless, I'm not getting the correct result in any public key based derivation.


Any hints / tips would be greatly appreciated.

[Pieter Wuille]

If you start from an extended private key, and private derivation is used (the highest bit of the child id is 1), there are two ways to obtain the derived public key:

• Add the tweak to the parent public key.
• Convert the derived private key to a public key using normal EC multiplication with the generator.

Both are correct, but the latter is (negligably) more efficient.[/list]

[riplin]

The code path that starts from an extended private key works. It's the code path that starts from an extended public key that's giving me trouble.

Edit:

Ok, I'm a little bit further. Still getting the same (wrong) results, but I'm now using the PublicKeyTweakAdd (which feels more symmetrical).

Code now looks like this for the public key path:

Code:

                byte[] newPublicKey = new byte[aPublicKey.Length];
                Buffer.BlockCopy(aPublicKey, 0, newPublicKey, 0, aPublicKey.Length);
                if (Utils.PublicKeyTweakAdd(newPublicKey, newPublicKey.Length, privateKey) != 1)
                    return false;

                aKeyPair = new DeterministicKeyPair(newPublicKey, chainCode, aDepth, aParent, aSequence, aLabel);

Edit 2:

Ok, I think I'm starting to understand it a bit more. Pieter, please correct me if I'm wrong, but there are basically two key spaces?

One is 0...0x7FFFFFFF (let's call this A) and the other is 0x80000000...0xFFFFFFFF (let's call this B).

Key Space A can be generated with just the parent public key (or private key, if present) and key space B can only be generated if the parent private key is present?



Last edit:

So I completely overlooked the internal / external key bit in the BIP. Everything is working fine.