Privacy is one of the greatest value propositions of bitcoin, and security is one of the greatest challenges. Signing services, which hold one or more keys in a multisig wallet, greatly help to improve the security of bitcoin by adding 2-factor auth and spending policies, but have traditionally come at the cost of privacy, because the signing service knows what addresses belong to the user, and therefore knows how many bitcoins the user has. Fortunately, it is possible to use similar elliptic curve mathematics as BIP32 and stealth addresses in order to have all the advantages of signing services while still maintaining privacy. We call this a stealth signing service.
Assume the signing service will hold one key in a 2-of-3 wallet configuration. The user holds one key online and the final key in cold storage. The user needs to be able to generate addresses for outputs that can be spent with 2-of-3 keys, while at the same time the signing service should not be able to derive what these addresses are, so that the signing service cannot know how many bitcoins are being held by the user. We can accomplish this goal by generating a random public key that the service can derive the private key to, but which it cannot derive without being told what the random value is.
The user has private key a and public key A. The user's public key can be derived from the private key, A = aG. The signing service has key B = bG. Finally, the user has a cold storage key C = cG.
The user can generate a new random keypair R = rG. The user can now generate a new hot public key, (R + A) = (r + a)G. The user can also generate a new cold public key, (R + C), to which they can generate the private key if necessary by bringing the cold key online, (R + C) = (r + c)G. The user can also generate a public key owned by the signing service, (R + B). If the user gives the secret r to the signing service, then the signing service can generate the corresponding public key and private key (R + B) = (r + b)G. So long as the value r is very large and random, it is computationally infeasible for the signing service to generate either the public key or private key without being told the value r by the user.
The user can now generate an address from the public keys. A p2sh multisig address, H, is a function of m-of-n and the public keys. In this case, m = 2 and n = 3, and the public keys are (R + A), (R + B), and (R + C). The user can spend funds to this address without the signing service knowing that it exists or that they have one of the keys.
When the user goes to spend the funds, they sign a transaction with the private key a, and then send the secret r to the service. At that time, the service now knows how many bitcoins are in the address.
In order to salvage privacy, the user simply needs to create many addresses, H_1, H_2, ... H_100, each of which are a function of a different secret r_1, r_2, ... r_100. Every time a user goes to spend funds from address H_n, the service will know how many bitcoins are in that address, but the service will not know how many bitcoins are in the other address. Only if the user spends all of their bitcoins by sending every r_1, r_2, ... r_100 to the service will the service know the total number of bitcoins held by the user. If the user never spends any bitcoins, the service does not even know it has a customer.
If the user stops trusting the signing service, the user can always sign transactions by retrieving the cold key. Furthermore, the user can simply not reveal the secrets r_1, r_2, ... r_100 to the signing service, and therefore the funds can be spent without the service ever knowing that it had a key to the corresponding addresses, so the privacy of the user is completely maintained. The service only knows the user owns bitcoins when the service is used to spend those bitcoins.
The user can prevent the service from knowing that a set of addresses H_1, H_2, ... H_100 all belong to the same user. When the user wants to use the service to spend bitcoins, the user generates their own public key (R + A), but does not share A with the service, and only shares R and the result of the computation (R + A). Since subtraction is mathematically infeasible in elliptic curves, the service cannot compute the user's master public key A = ((R + A) - R), and therefore cannot connect two different public keys (R1 + A) and (R2 + A) as having been derived from the same master public key. If the service is used 1000 times for spending, the service cannot tell if this was one user signing 1000 transactions or if it was 1000 users signing one transaction.
If the user wishes to use the spending limit features of a signing service, which sums the total spent bitcoins across multiple transactions, the user will need to reveal which addresses it will be spending from. The user can do this by sharing those addresses with the service. Only those addresses shared with the service before spending can be covered in a spending limit. Other features such as 2-factor auth can still be used while revealing only those addresses that are spent from.
There is a minor problem with the above scheme, which is that a new random number is to be generated for every address. This random number must be backed up, because if it is lost, the funds cannot be spent. This complicates backups because the backup must occur not once, but every time a new random number is generated. This is the same problem that is solved by BIP32, so we can copy the solution. Rather than generate many random numbers r_1, r_2, ... r_100, the user generates a master random number r, which is analogous to the chain code used in BIP32. Rather than generate random numbers r_1, r_2, ... r_100, the user generates deterministic values r_n = HMAC(r, n). These values are unpredictable by the signing service. The user can thus back up the master random value, and all other random values can be derived by simply knowing how many address had been generated. Even this value is not necessary to remember, as it is possible for the user (but not the service) to scan out n addresses to see which addresses have been used.
In practice, it is common for users to use blockchain APIs in order to query the blockchain. In the case of signing services, the blockchain API is usually the same as the signing service, which defeats the purpose of this scheme if the user is requesting exactly which unspent transaction outputs are owned by the user. This problem can be solved with bloom filters in the same manner as BIP 37. The user simply passes a bloom filter that is much larger than their set of unspents, thus hiding which unspents are truly theirs from the blockchain API. Further, the user could mix-and-match blockchain APIs so that the information held by one blockchain API is always limited. And of course, the user can always just download the blockchain and query it directly, which would maintain complete privacy over which addresses are owned by that user, while still leveraging the signing service for signing.
This scheme can be extended to arbitrary numbers of signing services and arbitrary m-of-n multisig. For instance, in a 5-of-8 multisig, the user might hold one key online, and one key offline, as usual. The user then uses the public keys of 6 different signing services to generate addresses, 4 of which would be necessary to sign transactions. In order for this to work in practice, wallets and signing services would need to use a common transaction proposal format and communication protocol, which would need to be invented.
This scheme can be extended not just to arbitrary numbers of signing services, but to arbitrary numbers of distinct users sharing a common m-of-n multisig wallet. The difference here would be that each of the users have their own distinct master random number, r. For instance, in a 2-of-3 multisig wallet with 3 distinct users, the users have their own master random numbers, r_1, r_2 and r_3 respectively. Those are used to derive the random number chains for each user, i.e. for user i, r_i_n = HMAC(r_i, n). The random number r_i_n would need to be shared with the other users in order for them to see the balance of an address or to spend from the address. Such a scheme would be useful for a group of peers who could collectively act as signing services for each other while maintaining mutual privacy.
This scheme can be combined with stealth addresses so that the user can share a public stealth address which senders can use to derive a new address with ECDH without revealing publicly that it is connected to the public stealth address. Suppose the receiver has a 2-of-3 wallet with a single signing service (B = bG) where the receiver holds one key online (A = aG) and one key offline (C = cG).
The receiver computes a random number r for use in the stealth address (or uses a previously derived value), and generates the corresponding public key R = rG, and the public keys for the stealth address (R + A), (R + B), (R + C). The receiver generates one extra keypair, S = sG, the scan key, for use in ECDH.
The sender generates a new random value, r', computes the public key R' = r'G, and arrives at a shared secret with the receiver, sR' = r'S. The sender computes another key by hashing this shared secret, d = hash(r'S), and D = dG. The sender can now derive new public keys to send to, (D + (R + A)), (D + (R + B)), (D + (R + C)). The sender computes the p2sh multisig address H(2, 3, (D + (R + A)), (D + (R + B)), (D + (R + C))) and sends bitcoins to that address, while including the public key R' somewhere in the transaction, either in an OP_RETURN or in an input.
The receiver scans every new transaction in the blockchain, and finds candidate public keys P which may have been used in a stealth transaction (i.e., P might be R'). The receiver attempts to compute a shared secret sP. They then hash this value, hash(sP) = d', and find a candidate shared keypair D' = d'G. They then compute the public keys (D' + (R + A)), (D' + (R + B)), (D' + (R + C)), and the address H(2, 3, (D' + (R + A)), (D' + (R + B)), (D' + (R + C))). If this address is found in an output, then D' = D, and the private keys are given by (d' + r + a), (d' + r + b), and (d' + r + c). If the user wishes to spend this output, they first sign a transaction with their hot key (d' + r + a), an then share the secrets d' and r with the signing service so that it can compute (d' + r + b), to apply the second and final signature. Or the user can bring the cold key c online to compute (d' + r + c) to apply the second signature. Although the user must share the random value r with the signing service, the user never shares the scan key s with the signing service, so the signing service cannot know how many transactions that user has received at this stealth address unless the user uses the signing service to spend them.
The stealth signing scheme makes it possible for a user to choose how much information to reveal to the signing service in order to achieve their desired level of privacy and security. Most significantly, a user can hide their true bitcoin balance from the signing service by using many addresses. The signing service can still provide 2-factor auth while only knowing how many bitcoins the user has spent, but not how many they are currently holding. The service can also proving spending limits, but only if the user is willing to share the balance of bitcoins subject to the limit. In essence, the user can choose to reveal more or less information to the signing service depending on what they feel is appropriate for the services they are being provided.