[ANN] PHP implementation of BIP32/electrum/bitcoin functions & multisig

[fbueller]

Over the past while I've been coding libraries that will help me get Bitwasp ready to implement multisig and bip32. Finally I've achieved just that. The libraries are currently on Github, in a repository I use for testing multisignature transactions. https://github.com/Bit-Wasp/multisig

BIP32
https://github.com/Bit-Wasp/multisig/blob/master/application/libraries/BIP32.php
The main interesting one is the BIP32 library - there hasn't been an implementation of this in PHP before, so I hope this is useful for others. It has functions for master key creation, and the child derivation, along with other helper functions, such as a build_key function to make dealing with the CKD function much easier, build_address which sits on top of this, and to convert from extended private to public keys.

Writing this was pretty fun, the CKD is a recursive function which, when it realizes that a generated key is invalid, will call itself again with (child number+1) to generate a valid key. This has what, 1 : 10^127 chances of occuring? but it's all taken care of anyway, and once the recursive function is done, it returns the extended key, and a human readable string describing the address (in case it DID hit an invalid key)

Out of sheer novelty it supports both bitcoin and dogecoin (magic bytes for dogecoin extended key were taken from bip32.org), although if someone wants to post litecoin's testnet/mainnet public/private key bytes, as well as the pay-to-pubkey-hash address version bytes, please do and I'll add these.

Multisig
This part requires bitcoind, but the repository can be pulled and pointed to a running bitcoind to facilitate multisig transactions. The code is pretty much ready to go with processing escrow transactions (2 of 2 wallets with autosigned spending transactions, or 2of3 signature escrow transactions). If you're setting up a 2of3 site you should really generate the 'trusted 3rd party' keys using electrum or bip32 and sign them elsewhere, as by default it imports the key so it can sign the transaction immediately for testing purposes.

Bitcoin Library
https://github.com/Bit-Wasp/multisig/blob/master/application/libraries/BitcoinLib.php
A while ago I was playing with theymos' library, and have over time recoded most of it. I've added a few functions to handle compression/decompression of public keys, and other bits and pieces which should help handling these.

Electrum
https://github.com/Bit-Wasp/multisig/blob/master/application/libraries/Electrum.php
I've written a library that handles creation of electrum seeds, generating the master public key, and derivation of private keys/public keys. Not much to see here, but maybe it'll help someone.


Update 1:
There's a new example script showing how addresses should be derived when doing multisig when you have 3 extended keys. Later on I'm going to set up the tests so they can be called through the web browser, and also then will have the multi signature address generation.
I have also started adding support for passing a tuple containing (base58_extended_key, definition like "m/0'/1") around, instead of just the extended key. This is so the functions can be used several times while accurately keeping track of the sequence numbers of the key, so if you do build_key, and subsequently to build_key, you aren't just left with the definition that was performed in the CKD.
 Or maybe i'll work on refactoring the Bitcoin API library.

[strip4bit]

I looked for a MPK/BIP32 Version for Lite and Dogecoins and landed here.

Looks really cool, but i don't get your bip32 example.
Your Electrum sample is really cool and works fine. But when i use the seed dcb85458ec2fcaaac54b71fba90bd4a5 from this sample as the BIP32::master_key('dcb85458ec2fcaaac54b71fba90bd4a5') seed i don't get the public addresses like in the Electrum example.

Is it possible to make a "electrum"-Example for Lite and Dogecoins?

The Litecoin key bytes should be:

   // Litecoin
   public static $litecoin_mainnet_public = '019da462';
   public static $litecoin_mainnet_private = '019d9cfe';
   public static $litecoin_mainnet_version = '30';
   public static $litecoin_testnet_public = '0436f6e1';
   public static $litecoin_testnet_private = '0436ef7d';
   public static $litecoin_testnet_version = ''; //dont found it

also add them to BIP32::describe_magic_bytes

[fbueller]

Thanks for the bytes! I can get the litecoin testnet version byte when I get home, so this should be added to github quick enough.

All the functions in the BIP32 library accept either a string (the extended key), or else an array: (extended_key, string_def). They pretty much all return an array like this as well.

The reason you supply an array as input, is so your code can return the entire set of sequence numbers defining your key or address once it's done generating it.
The reason it needs to return an array is because there is a 1:10^127 chance that you might generate an invalid key... the CKD function will handle this and move to the next valid key, but you need to know what your code has returned.

Code:

$master = BIP32::master_key('dcb85458ec2fcaaac54b71fba90bd4a5');
//Once you run BIP32::master_key(), you'll get (extended_key, 'm').

$build_key = BIP32::build_key($master, "0'/1/2"); // note the ', its required for level 1 keys.
// this will give you a tuple like master_key() does: (extended_key, "m/0'/0/0")

$build_address = BIP32::build_address($master, "0'/1/2");
// this will give you a tuple, but with the address instead of the key: (address, "m/0'/0/0")

// you can generate keys sequentially like this, illustrating why passing an array is better with this.
$key1 = BIP32::build_key($master, "0'"); // note the ' - its required for level 1 keys.
$key2 = BIP32::build_key($key1, "1");
$key3 = BIP32::build_key($key2, "2");

Check out the examples here: https://github.com/Bit-Wasp/multisig/tree/master/examples. any level 1 keys (like key1 above) really must be generated as 0' - otherwise you risk compromising the other chains in your wallet. Just remember the level1 derivative key must always have an apostrophe in the sequence number.

BTW, if you pass a second argument to BIP32::master_key, a lowercase string like 'dogecoin', you generate a dogecoin master key.

Litecoin/Dogecoin is supported by the electrum library if you use the BitcoinLib class to help generating the private WIF.

Code:

// Electrum class generating litecoin addresses/private key.
$seed = 'dcb85458ec2fcaaac54b71fba90bd4a5';
$desired_address_number = 0;

// public derivation of the address.
$mpk = Electrum::generate_mpk($seed);
$address = Electrum::address_from_mpk($mpk, $desired_address_number, '30');          // Supply 3rd argument to make it a litecoin address

// private derivation of the litecoin private key:
$private_hex = Electrum::generate_private_key($seed, $desired_address_number);
$private_WIF = BitcoinLib::private_key_to_WIF($private_hex, '30');         // Must supply address byte for this. Generates the wif format.

[strip4bit]

Ah, really cool. Thank you. Sadly i have no time to code now

But i tried it and it works, i also got an error:

on the 13. iteration:

$seed = 'dcb85458ec2fcaaac54b71fba90bd4a5';
// public derivation of the address.
$mpk = Electrum::generate_mpk($seed);
$address = Electrum::address_from_mpk($mpk, 13, '00');
       
// private derivation of the bitcoin private key:
$private_hex = Electrum::generate_private_key($seed, 13);
$private_WIF = BitcoinLib::private_key_to_WIF($private_hex, '00'); //error happens here

==> base58_encode: uneven number of hex characters

On the first look, it seems to be, that your code is much slower then this:
https://github.com/prusnak/addrgen/blob/master/php/addrgen.php
But yours does more. No big deal here.

[fbueller]

Ah, really cool. Thank you. Sadly i have no time to code now

But i tried it and it works, i also got an error:

on the 13. iteration:

$seed = 'dcb85458ec2fcaaac54b71fba90bd4a5';
// public derivation of the address.
$mpk = Electrum::generate_mpk($seed);
$address = Electrum::address_from_mpk($mpk, 13, '00');
       
// private derivation of the bitcoin private key:
$private_hex = Electrum::generate_private_key($seed, 13);
$private_WIF = BitcoinLib::private_key_to_WIF($private_hex, '00'); //error happens here

==> base58_encode: uneven number of hex characters

On the first look, it seems to be, that your code is much slower then this:
https://github.com/prusnak/addrgen/blob/master/php/addrgen.php
But yours does more. No big deal here.

I'll look into this error, there's something I meant to change there anyway.

Pavol Rusnak code only generates using the public address, which is pretty quick. The seed stretching, which is done when generating the mpk and private key (you could stretch and pass that to both functions, then it'd only be done once), involves hashing it 100000 times with SHA256. That's the slow bit, it takes around 0.86s on my laptop.

Just generating addresses is way quicker!

Code:

require_once(dirname(__FILE__).'/../application/libraries/BitcoinLib.php');
require_once(dirname(__FILE__).'/../application/libraries/Electrum.php');

$mpk = '819519e966729f31e1855eb75133d9e7f0c31abaadd8f184870d62771c62c2e759406ace1dee933095d15e4c719617e252f32dc0465393055f867aee9357cd52'; // the mpk for your seed above
echo Electrum::address_from_mpk($mpk, '0', '00')."\n";

[NotATether]

This thread is linked in various codebases on Github as a justification for using the extended version bytes posted in this thread.

I would like to point out that Litecoin is using the same extended version bytes as Bitcoin and is not using Ltub/Ltpv as was defined for Litecoin, it is using xpub/xprv like Bitcoin.

Consequentially, all properties for Litecoin "L" addresses are defined to be those in the "Bitcoin | xpub/xprv" row (the first row) in the SLIP-0132 document: https://github.com/satoshilabs/slips/blob/master/slip-0132.md

According to [1] and [2], Litecoin was supposed to use Ltub/Ltpv, but Litecoin devs never got around to implementing that.
[1] https://www.reddit.com/r/litecoin/comments/7rorqa/electrum_using_bitcoin_xpub_headers/dszq9d5/?context=3
[2] https://github.com/ranaroussi/pywallet/issues/6

Basically, don't use this:

Code:

Litecoin	0x019da462 - Ltub	0x019d9cfe - Ltpv	P2PKH or P2SH	m/44'/2'

Use this:

Code:

Bitcoin 	0x0488b21e - xpub	0x0488ade4 - xprv	P2PKH or P2SH	m/44'/0'

Just wanted to clear that up. Happy coding