[HOWTO] Hierarchical deterministic wallet

[Delek]

Hi there BTCguys  

In a network based game that I'm developing there's possible to buy certain things with a points like system, it works but I will migrate the whole monetary system to Bitcoin for lot of advantages that you already know and not even worth commenting.

In a first sketch of the idea I simply come up with this:
1) Every new user gets his new random private+public key.
2) Every new item gets his new random private+public key.
3) If the system detects that item X's address gets a pay from user X's address, the item belongs to user X.

This is PURE bitcoin and it works, but:
New items are added all the time, so the whole process of creating a new item's address must run on the server making this vulnerable to a server hack.
I come up with the idea of having a UNIQUE OFFLINE COLD STORAGE wallet for the ENTIRE game, but then, and this is the main question: how do I recognize which item did the user buy? Could I use the less significative digits of VALUE output for storing the ID? There's a way to store arbitrary data on a output script?

EDIT: Found it!, using HD Wallets But how to code it in Java?

[1713941297]

1713941297

[fbueller]

Maybe colored coins are something you might be interested in. You can mix colored coins at an address if you follow whatever rules there are - so a user with a single private key could hold multiple assets.

Colored coins are not much more than tracking child transactions of one where the 'color' was imparted. So a user collecting colored coins is analogous to collecting items.

[Delek]

I will use Bitcoin, thanks for the info anyway. 

[DannyHamilton]

I will use Bitcoin, thanks for the info anyway. 

Colored coins ARE Bitcoins.

It's simply a way of identifying a particular bitcoin output.

[Delek]

I was thinking in standard bitcoin scheme, but this colored coins are included in some java library? How can I achieve a similar id thing with bitcoinj?

[lemipawa]

You could use a watching wallet on the live server, and keep the coins in cold storage. Basically the watching wallet only has the public keys, so even if that server is hacked, the Bitcoin is still safe. With the watching wallet, you can just monitor the addresses and see what transactions are being made.

[Delek]

Thanks for the watch only tip, lemipawa, but as I said before, items are generated all the time on the fly: creating an address, even a "watch only", is a server task and this should be avoided.
The scenario is only 1 Address for the game and Lot of addresses for the players, for example:

1GAMExuq835482hv9823yq8q21aaz
1PLAYER1xuq835482hv9823yq8q21aaz
1PLAYER2xuq835482hv9823yq8q21aaz
1PLAYER3xuq835482hv9823yq8q21aaz
1PLAYER4xuq835482hv9823yq8q21aaz
1PLAYER5xuq835482hv9823yq8q21aaz
1PLAYER6xuq835482hv9823yq8q21aaz

Transaction
1PLAYER1xuq835482hv9823yq8q21aaz buys item [ID] for 0.001btc -> 1GAMExuq835482hv9823yq8q21aaz

The question is, where can I store the [ID] in a way that will be transparent for bitcoin network but useful to me?  

[Delek]

Ok so I finally found something that should work.

Using a deterministic generation of public keys from a fixed private key by using a Master Public Key I can spawn lot of new addresses without compromising the master private key.
This theory was implemented inside Electrum wallet (hierarchical deterministic wallet).
Now I only need to generate new public adresses from a master public key in Java. Is it possible with BitcoinJ to generate hierarchical deterministic wallets? Where's the theory/info about Master Public Keys? Thanks guys.

[coinpr0n]

Ok so I finally found something that should work.

Using a deterministic generation of public keys from a fixed private key by using a Master Public Key I can spawn lot of new addresses without compromising the master private key.
This theory was implemented inside Electrum wallet (hierarchical deterministic wallet).
Now I only need to generate new public adresses from a master public key in Java. Is it possible with BitcoinJ to generate hierarchical deterministic wallets? Where's the theory/info about Master Public Keys? Thanks guys.

Yes, it's possible... BitcoinJ uses Hierarchical Deterministic wallets (see: https://bitcoinj.github.io/working-with-the-wallet#seeds-and-mnemonic-codes).

I may have some code laying around but I'd need to find it. It's definitely possible.

[Delek]

Thanks coinpr0n, I coded this sofar:

Code:

public static void main(String[] args) throws Exception {
		byte[] randomBytes=new byte[32];
		new SecureRandom().nextBytes(randomBytes);
		
		DeterministicKey key1 = HDKeyDerivation.createMasterPrivateKey(randomBytes).derive(1);
		String serialized_xpub = key1.serializePubB58();
		String serialized_xpriv = key1.serializePrivB58();
		
		System.out.println("Deterministic tree:");
		System.out.println("---- xpub: "+serialized_xpub);
		for(int x=0; x<3; x++){
			for(int z=0; z<3;z++){
				String address=getAddressFromXCoord(serialized_xpub, x, z, false);
				String priv=getAddressFromXCoord(serialized_xpriv, x, z, true);
				System.out.println("------- derived public address from points "+x+","+z+": "+address+"/"+priv);
			}
		}
		System.out.println("---- xpriv: "+serialized_xpriv);
}

Code:

static String getAddressFromCoords(String serialized_x, int x, int z, boolean priv){
		NetworkParameters params = MainNetParams.get();
		DeterministicKey root_xpub = DeterministicKey.deserializeB58(null,serialized_x);
		int x_positive=x>0?x:x*-1, z_positive=z>0?z:z*-1;
		
		DeterministicKey key = HDKeyDerivation.deriveChildKey(root_xpub, new ChildNumber(x_positive, false));
		key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));

		if(x<0)
			key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(x_positive, false));
		
		if(z<0)
			key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));
		
		if(priv)return key.getPrivateKeyEncoded(params).toString();
		else return key.toAddress(params).toString();
}

And it outputs for example:

Code:

Deterministic tree:
---- xpub: xpub68yoVWPimjBPNSD9Lp4SzfPbhCVkZpYTxsSJkt1zqt2skkbd9NpR4Q6DFPbtgmnLnkZsbjKnqKuLNTRb3skiBToc6gDAHxyFake78sRwDeG
------- derived public address from points 0,0 public: 12P4who4aXh3g4CX82Np7qkWcQRMtPU142 / private: L3KBFty38whmgDrTPP2r93dK3gtQ6YNokQgYy17QiWp84eK6E6nc
------- derived public address from points 0,1 public: 1LKMC8SHBtcj7bMkwU1rYorGfCYHeocrPC / private: L5cVafedoXX6cWaeL9oCZRUhhPxHo2JTeZ9ovLaQm2vssuH7FQrH
------- derived public address from points 0,2 public: 1Pbn6GW5LNtZVD8Le1ReGSz2QgvDE7e3bc / private: KxUe45V9eC3T6oKG4cUfrnThvqW8hwWqHaWYtqjM1sMQMnxVcVA4
------- derived public address from points 1,0 public: 1H4stLytbwDbmbMAm8FJjs2FEAsHAs7gBu / private: KzkMyHgPLqHNTNidCpwZ8bESKjNvYGYDCdsS59MU4gi65iuaPtUx
------- derived public address from points 1,1 public: 1LbuqXtbYAhJgZhvCmB78doft4BW3FKms4 / private: Kx2YbnfM6To2DwpXkZfjwLVvmphbeK46DJFCvdmFWpoktzDjAvqw
------- derived public address from points 1,2 public: 1AhADvSzuZLvWcHUZH4uQGx1XvkDExUWbT / private: L3eWaZWynXRuXpRzzQgaCC8EpBzXBh76hSnX1LJArGvtP3USaM9C
------- derived public address from points 2,0 public: 16deviewo45m65RqD2FxXTbnmtzUbNTBq / private: KwbxyS65itURqC5aLmkphtZhV3caq2G4QpRbHRTxpcrFbdW3covr
------- derived public address from points 2,1 public: 1FpG3QmDM5FAfyUvLSP5mBsuaPHJcKPwQ / private: KxApcJ2jmvVkf3FBPH5VspFMYTgBdeXHTyo9NxNbyrFon9eZKogo
------- derived public address from points 2,2 public: 1JhTUw5W6HcTAhAqfJik7x9ECznm76m8KY / private: L5826yjT7s6eU9Sk9PEX9ASpB8BFo2fLzAgnjWUXFQWJgdQ8Fiey
---- xpriv: xprv9uzT5zrpwMd69x8gEnXSdXSs9AfGAMpcbeWhxVcPHYVtsxGUbqWAWbmjQ9JvAeLLFVFJXtoJWy8WrMS1Ffg2cvacdXoVuLjmGsjiidJK7Uo

Now, I have some the questions:

1) It is fine just to simply start the MasterPrivateKey from 32 bytes of a SecureRandom?
2) After the creation of the MasterPrivateKey I call to .derive(1). What's the reason behind not using .derive(0)?
3) After getting the xpub, check how I managed to code a "plane" of addresses (the function getAddressFromCoords). It it fine to make another child of child if the coordinate is negative?
4) While the list of public keys derived from the master public key grows the chances of discover the private key also grows?, I mean, I can generate infinite public addresses with the xpub without EVER compromise the private key?
6) If I need to obtain the private key of some of those public address generated, how can this be done? Using the xpriv with a function like HDKeyDerivation.deriveChildPrivateKey(root_xpub, new ChildNumber(x_positive, false), xpriv)??(Forget it, I already figured this one by my own)

[Delek]

Nobody? 

[DannyHamilton]

1) It is fine just to simply start the MasterPrivateKey from 32 bytes of a SecureRandom?

As long as you are certain that your SecureRandom isn't compromised or broken, certainly.  Why wouldn't it be?

4) While the list of public keys derived from the master public key grows the chances of discover the private key also grows?,

No, not in any realistic way.

I mean, I can generate infinite public addresses

I doubt you have the time or enough energy to generate infinite public addresses.  The number of addresses that you do have time and energy for is not significant when compared to the total key space.

with the xpub without EVER compromise the private key?

As long as the Master Key was generated randomly, you aren't going to have enough time to realistically encounter a collision.

[Delek]

Thanks for your time, Danny.  


I have this two outstanding questions:

2) After the creation of the MasterPrivateKey I call to .derive(1). What's the reason behind not using .derive(0)?

To complete the information: If I remove .derive(1) and add the xpub here: http://webhdwallet.github.io/
It shows the next legend:
"Non-standard key depth: should be 1, and it is 0, are you sure you want to use that?"

There's a security reason behind don't use a depth != 1? Maybe it is only a "standard"?

3) After getting the xpub, check how I managed to code a "plane" of addresses (the function getAddressFromCoords). It it fine to make another child of child if the coordinate is negative?

For the game that I'm making, I need a plane of fresh new addresses for every x,z values; negative coordinates are acceptable too.

And because I can't have a negative ChildNumber, I end up with this trick to re-do a child with the positive value again if the number is negative.

static String getAddressFromCoords(String serialized_x, int x, int z, boolean priv){
      NetworkParameters params = MainNetParams.get();
      DeterministicKey root_xpub = DeterministicKey.deserializeB58(null,serialized_x);
      int x_positive=x>0?x:x*-1, z_positive=z>0?z:z*-1;
      
      DeterministicKey key = HDKeyDerivation.deriveChildKey(root_xpub, new ChildNumber(x_positive, false));
      key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));

      if(x<0)
         key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(x_positive, false));
      
      if(z<0)
         key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));
      
      if(priv)return key.getPrivateKeyEncoded(params).toString();
      else return key.toAddress(params).toString();
}

I end up with a tree like this:

                                             /-------------
                                            /-Z
                                 /-------/-------
                                /-X     /
                    /--------/-------/----
                   /Z
         /------/-----------
xpub  /X
------/


EDIT:
So I found a bug in my function getAddressFromCoords():
------- derived public address from points -1,1 public: 1LUCtto3T8e4jdUHmZK7ThU6X6pGQ4czKE / private: KxugeoYxhzBnbAbxdL7unXv1LskqbAccwHhEjh1KMykrT19RcTEj
------- derived public address from points 1,-1 public: 1LUCtto3T8e4jdUHmZK7ThU6X6pGQ4czKE / private: KxugeoYxhzBnbAbxdL7unXv1LskqbAccwHhEjh1KMykrT19RcTEj

-1,1 and 1,-1 returns the SAME address. Fuck.

[Delek]

Ok this is the final one I think:

static String getAddressFromXCoord(String xpub, int x, int z, boolean priv){
      NetworkParameters params = MainNetParams.get();
      DeterministicKey root_xpub = DeterministicKey.deserializeB58(null,xpub);
      int x_positive=x>0?x:x*-1, z_positive=z>0?z:z*-1;

      DeterministicKey key = HDKeyDerivation.deriveChildKey(root_xpub, new ChildNumber(x_positive, false));
      key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));

      if(x<0)key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(x_positive, false));

      if(z<0){
         key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));
         key = HDKeyDerivation.deriveChildKey(key, new ChildNumber(z_positive, false));
      }

      return key.toAddress(params).toString();
}

I need to know if this technic (for every x and z) is SECURE, SAFE and re-usable with the same xpub on a server.