Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: RealityRipple on March 30, 2018, 03:59:18 PM


Title: BIP32 Child Derivation Function - Can't Find My Mistake
Post by: RealityRipple on March 30, 2018, 03:59:18 PM
I'm working on a Public-key-only BIP32 script to track purchases on my website rather than having users sign messages to verify themselves as the purchaser, and I spent yesterday getting the code together for it. The primary extended public key (m) code is now fully functional, but deriving children is running into issues. I've been testing with TestVector 02 (xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8id oc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB), and have successfully generated this data with the key:
Quote from: m
Version: 488b21e
 Depth: 00000000
 Parent Fingerprint: 00000000
 Child Index: 00000000
 Chain Code: 60499f801b896d83179a4374aeb7822aaeaceaa0db1f85ee3e904c4defbd9689
 Key: 03cbcaa9c98c877a26977d00825c956a238e8dddfbd322cce4f74b0b5bd6ace4a7
 Key Hash: bd16bee53961a47d6ad888e29545434a89bdfe95
 Key Str: 1JEoxevbLLG8cVqeoGKQiAwoWbNYSUyYjg

When I begin derivation of m/0, however, I get this far and then things end up wrong:
Quote from: m/0
Version: 488b21e
 Depth: 00000001
 Parent Fingerprint: bd16bee5
 Child Index: 00000000
 Chain Code: f0909affaa7ee7abe5dd4e100598d4dc53cd709d5a5c2cac40e7412f232f7c9c
####OH NOES BELOW####
 Key: 02d83bc1ba1544900181dc0a68f70c7f35de329935252d6a8a69609f18613e57e2
 Key Hash: 05bde101bb72a69c8cfe19e0700f66542b706d49
 Key Str: 1XMqymHzMur3pkEXr29pr8ghZbJkNWPw4
Of course, m/0 should be 19EuDJdgfRkwCmRzbzVBHZWQG9QNWhftbZ, not 1XMqymHzMur3pkEXr29pr8ghZbJkNWPw4. In comparing with https://en.bitcoin.it/wiki/BIP_0032_TestVectors (https://en.bitcoin.it/wiki/BIP_0032_TestVectors), I can verify that the Chain Code matches, so up to the SHA512 hash must be working correctly, however, the X/Y coordinates are completely wrong, resulting in the wrong key. The actual values for the left-side-of-I and the X/Y coordinates I'm ending up with are:
Quote from: m/0
iL: 60e3739cc2c3950b7c4d7f32cc503e13b996d0f7a45623d0a914e1efa7f811e0
 X: d83bc1ba1544900181dc0a68f70c7f35de329935252d6a8a69609f18613e57e2
 Y: 24f0d3bc9e646d0951df799e7e0691ac6a8ab228a62e2e76ff93c57886b4abfc
Since the chances of my iL being wrong are virtually impossible because the Chain Code is right, my best guess is my point math must be off. The code I'm using is:
Code:
$k = Point::add(Point::mul($il, $secp256k1_G), $this->ECpub);
where $il is a big-integer version of iL above, $secp256k1_G is the G Point, and $this->ECpub is the parent key's Point (decompression of Key's Bytes of course).

Here's the function in its entirety:
Code:
  public function derive_child($i)
  {
   if (USE_EXT == 'GMP')
   {
    $secp256k1   = new CurveFp('0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F', '0', '7');
    $secp256k1_G = new Point($secp256k1,
      '0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798',
      '0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8',
      '0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141');
   }
   else
   {
    $secp256k1   = new CurveFp('115792089237316195423570985008687907853269984665640564039457584007908834671663', '0', '7');
    $secp256k1_G = new Point($secp256k1,
      '55066263022277343669578718895168534326250603453777594175500187360389116729240',
      '32670510020758816978083085130507043184471273380659243275938904335757337482424',
      '115792089237316195423570985008687907852837564279074904382605163141518161494337');
   }
   $data = self::pubKeyEnc($this->ECpub) . pack('N', $i);
   $hash = hash_hmac('sha512', $data, $this->chain_code, true);
   $il   = BigInt::bin2big(substr($hash, 0, 32));
   $ir   = substr($hash, 32, 32);
   $k    = Point::add(Point::mul($il, $secp256k1_G), $this->ECpub);
   $ret  = new BIP32(null, $coin);
   $ret->coin               = $this->coin;
   $ret->chain_code         = $ir;
   $ret->ECpub              = $k;
   $ret->child_index        = $i;
   $ret->parent_fingerprint = substr($this->ECpubKeyHash, 0, 4);
   $ret->version            = $this->version;
   $ret->depth              = $this->depth + 1;
   $pubBinStr               = self::pubKeyEnc($ret->ECpub);
   $ret->ECpubKeyHash       = self::encKeyHash($pubBinStr);
   return $ret;
  }

Points, CurveFPs, and all that good elliptical shit are handled via a stripped down version of Matyas Danter's phpecc, so I'm pretty sure the actual mathematics I'm calling are good there, but the outcome for $k is always ending up as d83bc1ba1544900181dc0a68f70c7f35de329935252d6a8a69609f18613e57e2 rather than fc9e5af0ac8d9b3cecfe2a888e2117ba3d089d8585886c9c826b6b22a98d12ea, and I can't figure out for the life of me why.

For reference, the point I'm getting when multiplying iL and g is x=b661389998a7d5f191064dd13de77d6ecdc180660cd035c39e4242e4b2421b04, y=e4b7d21882264392ba68ab5a91fa6a7eb7794273e6887cbbcc367f0fc1a711be. I have no idea if this is correct or not, but I know that once I add the parent's public curve, it ends up being completely wrong. So, please, if anyone could have a working implementation spit out the points for iL * g, the parent key, and k, I'd like to know where I'm going wrong.

My own results, in decimal, are as follows:
Quote
m's ECpub: 92177583198369651078012650237376329809196622616143640907636115035502672667815, -56007618903221299795442838537477169399092506140195394231153621809959624157777
il * G: 82492713246181758252564353521594198071070516838199040858840666892200560433924, 103452112517317065707525904845368455724160088879315742877692289659877619863998
k: 97805156324642238343967192827814613794937570537923054831382185035481516759010, 16708767198174203366132415676330364127973636681074638317164427780658514144252

The negative y on the parent's ECpub sorta makes me anxious, but the key output is right for "m", so it must be correct, yes?

Title: Re: BIP32 Child Derivation Function - Can't Find My Mistake
Post by: achow101 on March 30, 2018, 09:51:02 PM
Before you do the adding, can you print out what you get for
Code:
Point::mul($il, $secp256k1_G)
and
Code:
$this->ECpub

Make sure that those are what you expect them to be.

The only thing that can be wrong here is that either you are adding the wrong things or Point::add is broken.

Title: Re: BIP32 Child Derivation Function - Can't Find My Mistake
Post by: RealityRipple on March 30, 2018, 09:52:32 PM
Quote from: achow101 on March 30, 2018, 09:51:02 PM
Before you do the adding, can you print out what you get for
Code:
Point::mul($il, $secp256k1_G)
and
Code:
$this->ECpub

Make sure that those are what you expect them to be.

The only thing that can be wrong here is that either you are adding the wrong things or Point::add is broken.
I already did. They're in the final quote under the names il * G  and m's ECpub respectively.

Also, Point::add and Point::mul are used in my recoverPubKey function for verifying signed messages, which I'm already sure works correctly for multiple coin types. However, I can't completely rule out the possibility of an issue, which is why I'd like verification on the numbers and the results, as you say.

Title: Re: BIP32 Child Derivation Function - Can't Find My Mistake
Post by: achow101 on March 30, 2018, 11:25:59 PM
Quote from: RealityRipple on March 30, 2018, 09:52:32 PM
]I already did. They're in the final quote under the names il * G  and m's ECpub respectively.
Can you print them in hex? The negative makes things slightly harder to check things.

The X component of m's Pub is correct and iL * G is also correct.

Title: Re: BIP32 Child Derivation Function - Can't Find My Mistake
Post by: RealityRipple on March 30, 2018, 11:50:04 PM
Quote from: achow101 on March 30, 2018, 11:25:59 PM
Quote from: RealityRipple on March 30, 2018, 09:52:32 PM
]I already did. They're in the final quote under the names il * G  and m's ECpub respectively.
Can you print them in hex? The negative makes things slightly harder to check things.

The X component of m's Pub is correct and iL * G is also correct.

Yeah, so I have no idea what the standard is for converting negatives to hex is here. but it's whatever -7bd3305d363c26f82c1e41c667e4b3561c06c60a2104d2b548e6dd059056aa51 would be represented as, in any case.

Ah, yes, it was my decompression of Y. I had my suspicions. You helped me narrow it down quite a bit, actually. Thank you for your assistance.


Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines