BIP32 Index Randomisation

Hello everyone,

We are working on bitcore-wallet-server (BWS), a HD multisig wallet 'facilitator'. We have a couple of questions regarding BIP32 path usage, and we would love to have feedback from you before moving forward.

Currently the BWS instances hold the set of extended public keys of the wallet's peers to be able to derive addresses.

Since this is a problem from the privacy point of view, we thought using pseudo-random BIP32 paths, with a seed only known be the peers, so the server will be able to verify that addresses submitted by peers belong to the wallet, but will not be able to derive future wallet addresses.

The workflow would be something like:

``` Peer > getCurrentIndex

< Server [index]

Peer:
  pathSeed = PRNG(seed, index);

Peer > createAddress(index, pathSeed);

Server:
  derives the address and add it to the wallet.

< Server new address

Peer: Verifies the address and inform it the user. ```

This way, accessing server data won't reveal future wallet addresses. The
seed (only known by the peers) could
be derived from hashes of their xprivs, so wallet funds can still be
recover with:
  1) The complete set of xprivs
  2) The quorum of xprivs + the complete set of xpubs + the address seed.

Thanks a lot in advance for any comment on this schema.

matías

This seems overly complicated to me, unless I'm missing something.

Instead, I think you should just give the server the master pubkey P only without the chaincode.

Then when you transact you generate the address in whatever manner you like and tell the server the scalar value iL which the user computes as

iL = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i))[first 32
byes],  (per BIP 32).

and the server computes P + iL*G and checks agreement with the address.

It would be inaccurate to call this private, as the server still learns this particular relation. (and really users should _not_ be using the same chaincode with different parties... as it exacerbates the private key leak risk), but its certainly more private than giving people the chain code.

The approach I suggest is also not gratuitously incompatible with hardened derivation, which is what parties should be doing when they don't actually need a third party to generate future addresses for them without their cooperation (as appears to be the case here).

On Fri, Mar 13, 2015 at 3:48 AM, Matias Alejo Garcia <matias@bitpay•com> wrote:

>
> Hello everyone,
>
> We are working on bitcore-wallet-server (BWS), a HD multisig wallet
> 'facilitator'. We have a couple of questions regarding BIP32 path usage, and
> we would love to have feedback from you before moving forward.
>
> Currently the BWS instances hold the set of extended public keys of the
> wallet's peers to be able to derive  addresses.
>
> Since this is a problem from the privacy point of view, we thought using
> pseudo-random  BIP32 paths, with a seed only known be the peers, so the
> server will be able to verify that addresses  submitted by peers belong to
> the wallet, but will not be able to derive future wallet addresses.
>
> The workflow would be something like:
>
> ```
> Peer >   getCurrentIndex
>
> < Server [index]
>
> Peer:
>   pathSeed = PRNG(seed, index);
>
> Peer > createAddress(index, pathSeed);
>
> Server:
>   derives the address and add it to the wallet.
>
> < Server  new address
>
> Peer: Verifies the address and inform it the user.
> ```
>
> This way, accessing server data won't reveal future wallet addresses. The
> seed (only known by the peers) could
> be derived from hashes of their xprivs, so wallet funds can still be recover
> with:
>   1) The complete set of xprivs
>   2) The quorum of xprivs + the complete set of xpubs + the address seed.
>
> Thanks a lot in advance for any comment on this schema.
>
> matías
>
> --
> BitPay.com
>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming The Go Parallel Website,
> sponsored
> by Intel and developed in partnership with Slashdot Media, is your hub for
> all
> things parallel software development, from weekly thought leadership blogs
> to
> news, videos, case studies, tutorials and more. Take a look and join the
> conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

Hey Matias,

We are working on bitcore-wallet-server (BWS), a HD multisig wallet

> 'facilitator'.
> Currently the BWS instances hold the set of extended public keys of the
> wallet's peers to be able to derive  addresses.
>

Could you describe what exactly BWS does? It sounds like the server doesn't have to actually derive the keys itself for any particular purpose beyond knowing the addresses are a part of the wallet. Could the server work if it didn't even know that, and was just a bucket of arbitrary addresses with the clients themselves deriving the addresses?

> Could you describe what exactly BWS does?

Sure. BWS tasks are:

* Coordinate Transaction proposals in multisignature wallets: provide an 'always connected' node to distribute pending transaction proposals and receive the signatures from peers. * Coordinate and store BIP32 derivation indexes. (If the BWS disappear, peer can still access the funds by scanning the blockchain, but having the index in a common accessable point in useful). * Access the blockchain and provide functions like: `getBalance` and `getTxHistory` to peers. * Allow agents to notify incoming funds / or transaction proposals to peers.

BWS is designed to be extremely easy to setup and run. BitPay will provide a public BWS instance, but companies and individuals can run their own for privacy and security reasons.

> It sounds like the server doesn't have to actually derive the keys itself for any particular purpose
> beyond knowing the addresses are a part of the wallet. Could the server work if it didn't even
> know that, and was just a bucket of arbitrary addresses with the clients themselves deriving the
> addresses?

We have evaluated BWS not having the extended public keys (and it is still an open possibility) but the main drawback we found is that BWS will have no way to verify addresses sent by the peers (*).

A peer could send a fake address to BWS and then functions like 'getBalance' or 'txHistory' will be broken. Of course, the peers could verify the addresses on getTxHistory or getBalance (by Address) but we also want to allow thin-clients and agents with lower level of trust (than the server) that can notify the wallet balance and incoming transaction to peers using, for example, mobile push notifications.

(*): Gregory Maxwell proposed an schema for doing this with the "not extended" pubkeys, that we need to evaluate. That could be the best solution.

It sounds like the main issue is this is a web wallet server of some kind. If the clients were SPV then they'd be checking their own balances and downloading their own tx history, which would mean the coordination tasks could be done by storing encrypted blobs on the server rather than the server itself having insight into what's going on (see: Subspace).

So whilst you might be able to use some scheme to avoid the server knowing the xpubkey, if the server still knows all addresses and all transactions because the clients are web wallets ..... is there any point? It seems like maybe going from server knows everything to server knows 95% of everything: maybe not worth the engineering cost.

> It sounds like the main issue is this is a web wallet server of some kind.
> If the clients were SPV then they'd be checking their own balances and
> downloading their own tx history, which would mean the coordination tasks
> could be done by storing encrypted blobs on the server rather than the
> server itself having insight into what's going on (see: Subspace).

You are killing us Mike! :) We really don't like to think that BWS is a webwallet. Note that private keys are not stored (not even encrypted) at the server. Addresses can be generated offline, funds received and transferred by the peers without accessing BWS.

Currently Copay uses the encrypted blob idea (checks balances and tx history thought Insight), but after working with Copay for ~6 months we think having some visibility of the wallet by the multisig facilitator will make the user experience much better (e.g: mobile notifications).

Thanks for the Subspace reference, we will definitely check it.

> So whilst you might be able to use some scheme to avoid the server knowing
> the xpubkey, if the server still knows all addresses and all transactions
> because the clients are web wallets ..... is there any point? It seems like
> maybe going from server knows everything to server knows 95% of everything:
> maybe not worth the engineering cost.

Interesting point. IMO, if we can prevent the server from having the xpubs keys it would be valuable: It will give us more flexibility for future features, and if the server is compromised future addresses will not be known by the attacker, but of course we need to evaluate the cost.

matías

>
> ------------------------------------------------------------------------------
> Dive into the World of Parallel Programming The Go Parallel Website,
> sponsored
> by Intel and developed in partnership with Slashdot Media, is your hub for
> all
> things parallel software development, from weekly thought leadership blogs
> to
> news, videos, case studies, tutorials and more. Take a look and join the
> conversation now. http://goparallel.sourceforge.net/
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

>
> You are killing us Mike! :) We really don't like to think that BWS is
> a webwallet. Note
> that private keys are not stored (not even encrypted) at the server.

Sure, sorry, by web wallet I meant a blockchain.info/CoPay type setup where the client has the private keys and signs txns, but otherwise relies on the server for learning about the wallet contents. I tend to call wallets where the server has the private key BitBanks but I don't know if anyone else uses this terminology. It might just be a personal quirk of my own ;)

> we think having some visibility of the wallet by the multisig
> facilitator will make the user experience much better (e.g: mobile
> notifications).
>

Fair enough. Yes, push notifications to mobiles in a decentralised way is rather a hard problem.

I think what Gregory suggested is then the best approach for you to do what you want. Whether it's worth the additional complexity is something I don't have any feedback on, only you can judge that.