Privacy from nosy signatories

[bitcoinhodler]

Goal

If I give a friend or family member one of my multisig keys to store safely for me as an emergency backup, that person should be unable to find my balance or see my transaction activity.

Assumptions

If the key is in the form of a hardware wallet, which stores both the account map and the seed in a secure element, we can assume the nosy signatory will not be able to access it.

But I would also like to support stateless wallets, where the seed phrase is handwritten on paper and the account map is a printed QR code, which the user types in and scans (respectively) only at the time of signing.

It would also be useful to support printed backups, even with a HWW, in case the HWW dies or is damaged or destroyed.

Requirements

• The nosy signatory cannot see the account map in cleartext. Otherwise they could import this as a watch-only wallet and see all my transactions.
• The nosy signatory cannot have access to any one of my BIP39 seed phrases (either passwordless, or with a password known to the signatory). Otherwise they could guess the derivation paths and find matching pubkeys in the P2WSH withdrawal scripts on the blockchain, exposing all of my spending from this wallet.
• If the user (or his legitimate heir) has access to M-of-N keys, they must be able to find all UTXOs and spend the money.

Proposal

• At account creation time, create strong BIP39 passwords for each key. Random gibberish will do; the user will never see these.
• Record all N BIP39 passwords in the account map
• Shard the account map using Shamir's Secret Sharing into M-of-N pieces
• Include one shard as a printed QR code with each key
• Provide a process for restoring the account map from M-of-N shards

The user will keep the unsharded account map, for his own use in the signing process, but will not provide it to other keyholders.

As part of the stateless wallet signing process, the user will provide the account map to the signing device, either via printed QR code or UR. The signing device will then use the BIP39 password corresponding to its key. (It can determine which one belongs to it by trying all N until it finds one that creates an xpub that matches one of the xpubs in the descriptor. Or perhaps all N keys can use the same password.)

Limitations & drawbacks

• Adds complexity, which is the enemy of security
• Adds dependency on Shamir library
• Precludes user from providing their own BIP39 password (though maybe it's as simple as appending the user's password to the one in the account map?)

[Rspigler]

#6

[bitcoinhodler]

@Rspigler I'm following #6 but I figured this proposal was a little more broad and would benefit from a more focused discussion.

Since nobody wants to discuss it, how about I simplify the proposal down to the one essential item:

• Add a standard way to record BIP39 passwords for each xprv in the account map

[ChristopherA]

I’m actually inclined a bit differently — Leverage bytewords to covert a full xpub as used in a Bitcoin wallet descriptor (e.g.[fingerprint/path’/to/xpub…]) to text, and the xprv equivalent, as compactly as possible.

This also means the derived keys can also be converted to Shamir sskr shares as well.

Full xpub -> binary -> UR cobj-> bytewords

/cc @wolfmcnally

[Rspigler]

cobj?

[ChristopherA]

COBJ is a binary representation JSON, which is more compact and easier to sign.

[bitcoinhodler]

Thank you for the response but I'm afraid I don't follow at all. My assumption is that there's a handwritten BIP39 seed phrase on paper, along with an account map in some form, and the goal is to make that as private as possible. Are you proposing a different privacy method with the same assumptions, or a different set of assumptions?

[Rspigler]

My concern with SSS is it is notoriously hard to implement, and there have been a number of historical vulnerabilities.

[ChristopherA]

@Rspigler wrote:

My concern with SSS is it is notoriously hard to implement, and there have been a number of historical vulnerabilities.

Which is why Blockchain Commons worked so hard with others (Unchained Capital, Satoshi Labs, HTC Exodus, Mark Friedenbach, Bryan Bishop, Daan Sprenkels, etc.) over the course of over a year including two in-person events (RWOT9 and 10) on the sskr specification and it's reference code:

• Reference code for the core Shamir (and to ease security review): https://github.com/BlockchainCommons/bc-shamir
• Reference code for the binary structure of the shards: https://github.com/blockchainCommons/bc-sskr
• UR spec: https://github.com/BlockchainCommons/Research/blob/master/papers/bcr-2020-011-sskr.md
• Turning the data into text:
  • Spec: https://github.com/blockchainCommons/bc-bytewords
  • https://github.com/blockchainCommons/bc-bytewords
  • https://github.com/blockchainCommons/bc-bytewords-cli
• Libraries for other platforms:
  • iOS: https://github.com/BlockchainCommons/BCLibsSwift
  • Java https://github.com/BlockchainCommons/bc-libs-java
• Demos to exercise our SSKR libraries:
  • CLI: https://github.com/blockchainCommons/bc-seedtool-cli
  • Hardware: https://github.com/blockchainCommons/bc-lethekit
  • iOS: https://github.com/BlockchainCommons/Fehu

So as you can see, substantial work has been done to address the past concerns about Shamir.

[Rspigler]

Wow, that is a lot of great work, thank you! What development phase would you say the Shamir libraries are in? (It's not noted in the README.md's)

How would one split an Account Map into shares? Account Map -> x -> Bytewords - > Shamir?

[Rspigler]

@bitcoinhodler I like this a lot! (Apologies for initially disregarding it :) )
With this proposal, spending and watching (past and future) of the HD wallet can be the same M of N, unlike traditional multisig where privacy is a serious concern (1 of N).
I like that the passwords could be auto-generated, and don't need to be handled really at all by the users.

With BIP39 concerns, could you use bytewords instead? Not sure how they handle encryption though.

[bitcoinhodler]

Yes, exactly: watching is now M-of-N.

This doesn't apply when seedless hardware wallets are used. But if you store seed phrases on paper, either for use with stateless hardware or as a backup of the HWW, then this will solve the privacy concern.

So you don't want to use BIP39 at all, but instead store the xprv directly (encoded using bytewords)?

BIP39 includes the password as part of its spec. Bytewords has no equivalent, so you'd have to specify some other way of encrypting the xprv using a password. I'm not an expert in that field but it seems like any standard/common (block? stream?) cipher would work. This proposal could be easily adapted for that.

[bitcoinhodler]

@mflaxman 's alternative proposal would neatly solve the problem of encrypting the bytewords xprv: no need for that anymore.

[Rspigler]

Yeah so I'm also thinking of the case where users are just using Core (instead of HWWs). In that case, I believe bytewords could be used to encode the hdseeds, and I really like how Blockchain Commons selected their alphabet.

[mflaxman]

I propose an alternate approach, which has the following benefits over the above protocol:

• It's already compatible with any BIP32-compatible hardware wallet (provided it allows for arbitrary BIP32 paths), so it requires little-to-no changes to hardware wallets / coordinator softwares to work today.
• Some of the blinding can take place on internet connected machines with reasonable security tradeoffs (mostly privacy), but of course it would be better to perform this on a secure Signer (especially if using this scheme to blind multiple seeds).
• Multiple private keys need never live on the same device, nor even exist in the same geography. Your nosy signatory can generate their own xpriv, across the world, and the HOLDer can blind their xpub from afar. The construction is similar to a diffie-hellman exchange.
• A user can participant in nearly infinite multisig schemes with their existing hardware wallet, using just their one BIP32 seed phrase. For example, power user "Uncle Jim" can use his existing hardware wallet to derive 10 child xpubs, with a unique one for each friend/relative. He can have a unique emergency recovery xpub in each of their m-of-n (say 2-of-3, but each might have it's own m-of-n) in a way where this leaks no information about what funds he can cosign for until he is called upon to cosign (and is provided with the secret bip32 path).

Steps:

1. Create a regular m-of-n multisig using any number of Signers the HODLer desires, let's say it's 2-of-3 for this example.
2. For every Signer whose xpub the HODLer would like to blind, she has her coordinator software pick a very large (say 160 bit) number using good randomness, and encodes that as a base 2,147,483,647 number. I chose this because it's 2^31 - 1, the max depth allowed in BIP32. This very large number is now the unhardened BIP32 path for that blinded signer, and it might look something like m/920870093/318569592/821713943/1914815254/1398142787/9
3. The resulting child xpub is calculated by the Coordinator, and included in the account map for receive address generation.
4. If there is a nosy signer (say a banker drills the safe deposit box or an heir wants to peak at their inheritance), then without the bip32 path they see nothing about what that seed phrase is protecting (not balance, transaction history, or even anything about spent funds).
5. If the HODLer wishes to use this seed phrase to spend bitcoin, she simply fetches the Signer or seed phrase backup and combines it with the secret BIP32 path to spend funds.

Note that the example that I give is only for nosy signatories, but it need not be so restrictive. The obvious next step of this scheme is to the then split the account map info (including most importantly the secret BIP32 path) using SSSS. It would be possible to use this protocol on all n Signers and then use Blockchain Common's SSSS library to split the account map up into p-of-q parts (which is different from the m-of-n used in bitcoin multisig scripts). For example, you might have a 4-of-7 bitcoin multisig with 10 secure locations (if you store some of the seeds redundantly in duplicate places). You might need only 2-of-10 of these locations to recover your 4-of-7 account map. This means that someone who got into any 1 of your 10 secure locations and could read a seed phrase in plain text would learn nothing about the contents of your wallet!

To make it more real, here is a working POC in simple python code:
https://gist.github.com/mflaxman/a2e11e0023474f369827c4aec527cd30

This is just research code that is the easiest way to convey the idea, I didn't bother with child accounts here (though it would be trivial) nor any of the SSSS parts (I'm just blinding 1 signatory only in this example so I assume it can be recovered from another more-secure location).

This scheme was inspired by an earlier idea that was less generalizable to all signers.

[mflaxman]

I'm trying to find a way to avoid having to validate every receive address on >1 device. When my keys are properly geographically distributed, that's a giant PITA.

Ya, that is an annoying part of a bulletproof multisig setup :(

If I have a printed account map that I've previously validated on all N devices, an online wallet with that same account map, and one offline quarantined laptop that I use with that handwritten key, an attacker would have to compromise two of those three things before a phony receive address would validate. I don't think that counts as a single point of failure?

What is the handwritten key?

But yes, if you can keep track of that account map somewhere securely and validate that is hasn't changed on just 1 device that isn't compromised, then that's sufficient. The problem with validating that by hand is that introduces the possibility of mistakes, or that your device is compromised. A hardware wallet is designed to solve these problems already, and since we explicitly trust these devices, having them replay a signature is requires no extra mental steps from the human (you'd just check the device and see that it displays the correct address).

In the physical security case (not your top concern), an evil maid swaps out these physical pieces and then what you validate against isn't real. Think of the most extreme case:

1. You have 4-of-7 spread across the world, with one seed phrase in each continent in the world.
2. You keep a copy of the account map at home that you properly validated at setup time (but didn't cryptographically sign).
3. The evil maid swaps out the account map you keep at home (physical copy and/or on your computer), and you deposit new bitcoin to a 4-of-7 receive address where your attacker controls 4 (or more) of the keys.

As long as you're sure that account map is correct, you don't need to validate on 4 of your devices. It's just that being sure the account map is correct becomes softly defined. Maybe you secretly keep an airgap laptop under your bed for performing this task and your evil maid is unaware of this.... Or maybe the maid is aware of this and updates it and you're duped!

Btw, if you're validating an account map by hand, you probably want to be validating some digest as it could be very long (think 3-of-5). The bitcoin core checksum is only 40 bits, so you'd probably want to validate against some sort of hash-digest. That's not the case when replaying a signature, where the device can just display "yes, I've validating this account map and here are your receive addresses."

I could see a scenario in the future where hardware wallets with physical security (secure elements) offer a watch-only mode and the wallet would never have private key material. This watch-only hardware wallet would just store the account map state. But of course your trust model shifts from your m-of-n multisig validation to "is this device being honest?". You might manually add more checks (another device), but the point is that when you violate the trust boundary things get messy. For example, your real hardware wallets (with private keys) that are spread out in different geographies might be honest, but now your watch-only hardware wallets could lie to you.

I am concerned about physical security, but I don't see how that would change the analysis.

Thanks for a very enlightening discussion. In conclusion, I like your privacy proposal (using long unpredictable BIP32 path) better than mine (using BIP39 passwords).

Thanks, the more I think about it the more I like this BIP32 path proposal. It's just tricky because fo the very different use-cases (third-party blinding 1 signer and first-party blinding all n signers).

I'd like to write something up soon.

[bitcoinhodler]

What is the handwritten key?

One of the N BIP39 seed phrases, stored at the owner's home along with the validated account map.

I'm not sure what you're talking about validating the account map "by hand". The process is:

• Coordinator prints account map QR code
• On each of N airgap laptops, scan in that paper, type in corresponding BIP39 seed, and the software (something like GlacierScript, Yeti, or Proof Wallet) will verify that its xpub appears in the account map
• Save that piece of paper as the "validated account map"

The user never has to look at the descriptor or anything else in the account map.

Wouldn't you agree that the evil maid would have to compromise both my online wallet AND either my airgap laptop or the printed pages? They would also have to compromise the online wallet software so it would continue to display my UTXOs despite the descriptor no longer matching. (Otherwise I would notice the anomaly and no longer trust that wallet.) It's true they could do all of this in a single location, but this would require an extraordinarily determined thief to pull off such an attack, and there's probably much easier ways of stealing my coins.

3. The evil maid swaps out the account map you keep at home (physical copy and/or on your computer), and you deposit new bitcoin to a 4-of-7 receive address where your attacker controls 4 (or more) of the keys.

This "and/or" is where you misunderstand: it must be AND, not OR, because I generate new receive addresses on the online wallet and then validate them using the printed account map on the airgap laptop. If either one of those flows is still intact, the address will not validate, and the attack fails.

Thinking about the HWW use model, if the HWW stored the account map, it would have the same protections. An attacker would have to compromise both the online node and the HWW in order to get fake receive addresses to validate. Do you think that's a feasible attack vector?

[mflaxman]

I think without precise semantics, discussing this accurately is nearly impossible. I need to make a clear writeup that separates third-party blinding of < m seeds and first-party blinding of all n seeds, and uses precise labels for what validating each piece of data means and under what threat model. Otherwise, it gets very circular. Especially since you can likely get away with a ton; multisig isn't the lowest hanging fruit for malware authors and most attacks would be stopped by just confirming an address on one stateful hardware wallet with physical security (i.e. coldcard). However, it can be far more complex if you want real security guarantees; perhaps that one device is malware the whole time!

Inline.

What is the handwritten key?

One of the N BIP39 seed phrases, stored at the owner's home along with the validated account map.

I'm not sure what you're talking about validating the account map "by hand". The process is:

• Coordinator prints account map QR code
• On each of N airgap laptops, scan in that paper, type in corresponding BIP39 seed, and the software (something like GlacierScript, Yeti, or Proof Wallet) will verify that its xpub appears in the account map
• Save that piece of paper as the "validated account map"

At that point if you have seeds and account maps on a device you've just built a full Signer (i.e. a hardware wallet).

At the moment you validated the account map on all N signers, it is properly validated. If you save that somewhere and in the future retrieve it (remember, it's intentionally not saved on the Signers), you now have to wonder if it's still validated or if a third party tampered with it, whereas we treat hardware wallets as tamper-proof and inside the trust-boundary. This is the thing that Signatures from private keys solve, by validating those signatures on trusted displays storing those private keys we can guarantee that there hasn't been tampering.

The user never has to look at the descriptor or anything else in the account map.

Wouldn't you agree that the evil maid would have to compromise both my online wallet AND either my airgap laptop or the printed pages? They would also have to compromise the online wallet software so it would continue to display my UTXOs despite the descriptor no longer matching. (Otherwise I would notice the anomaly and no longer trust that wallet.) It's true they could do all of this in a single location, but this would require an extraordinarily determined thief to pull off such an attack, and there's probably much easier ways of stealing my coins.

The amount of places that you check against is the amount of places that would need to be compromised for loss.

If you hide 10 copies of the account map at home (just the account map, no private keys) and you check an address against all 10 (and nowhere else), this is secure provided that your evil made didn't find and edit all 10 copies (perhaps this evil maid only discovered 9 copies and altered them). Or perhaps you loaded each of those 10 copies into 1 watch-only wallet, and so the evil maid only had to malware the 1 watch-only device. You can repeat this in any combo, perhaps you have 1 paper copy laying around, one digital copy on an airgap computer, 1 digital copy on your phone, etc. If you check all of them, then an attacker would need to compromise all of them.

But keep in mind, if a 2-of-3 wsh sortedmulti might be ~445 characters. You don't need to strictly validate the whole thing, but we don't have a great checksum (the first receive address is a nice hack, although it needs a device and can't just be read manually on paper). For the end-user to validate that a device which holds the private key (Signer) was a participant to a sortedmulti involved loading the account map on to the device and seeing it say "YES". To confirm that the other n-1 seeds haven't been swapped out would require validating on all of them. With signatures, you can replay your previous validation of ALL n devices so you might see that as enough (assuming your device wasn't ever malware, it's telling you that it previously validated this whole account map).

So for most people, 2 separate/unrelated watch-only (no private keys) systems with the account map is possiblygood enough. But if you're Michael Saylor and receiving a 10,000 BTC payment, you might want to confirm on all N signers.

3. The evil maid swaps out the account map you keep at home (physical copy and/or on your computer), and you deposit new bitcoin to a 4-of-7 receive address where your attacker controls 4 (or more) of the keys.

This "and/or" is where you misunderstand: it must be AND, not OR, because I generate new receive addresses on the online wallet and then validate them using the printed account map on the airgap laptop. If either one of those flows is still intact, the address will not validate, and the attack fails.

I think I didn't set this up with precise enough words so we're saying a lot of the same things differently. If you check x systems before validating a receive address, then the only way to swap out a receive address is for your attacker to tamper with x systems. But you have to factor in the weakest link in all of them. For example, without a signature being replayed (a feature that doesn't yet exist), a stateless hardware wallet (like Trezor) can be trivially be fooled by only a compromised coordinator (swap out all but 1 xpub and the Trezor would display the attacker's receive address).

Thinking about the HWW use model, if the HWW stored the account map, it would have the same protections. An attacker would have to compromise both the online node and the HWW in order to get fake receive addresses to validate. Do you think that's a feasible attack vector?

What's tricky is that in practice it depends on if the HWW has a secure element (which are all currently closed source, and if you trust that close source secure element as part of your trust model). If you're OK with that secure element, the HWW could store state and also someone who got physical access to that HWW wouldn't have access to the state without the PIN (and the device limits PIN attempts and self-destructs).

If the HWW is stateless (and/or you don't trust it to store state), then compromising the online node ONLY is enough to display the attacker's receive address on both the online node and the hww. This is why replaying a signature is great, because it renders this attack impossible. But separately, you might still want to check on >1 Signers, because of the risk that the online node and HWW are both compromised.

[bitcoinhodler]

I agree with everything you're saying for the use model of HWWs, where you can assume that the evil maid cannot access the xprv stored inside. But when my seed words are written on paper, an evil maid can swap out the account map AND create a new valid signature using those seed words. Checking the signature no longer tells me that the account map is uncompromised.

You might say, "That's why you have to validate every receive address on multiple devices," and you're right. If I had a 3-of-5 and the attacker replaced the last 3 xpubs with his own, I could successfully validate a phony receive address on the first 2 devices (assuming I had no signatures). With signatures, the attacker would have to compromise both of those locations for that to work.

Anyway, I think you've convinced me that my proposed system is secure enough for me. :P

Want to talk about canaries?

[mflaxman]

I realized IDK who you are (the internet is amazing!), but just form how you're talking about it I'm confident you know the risks you're taking and they sound reasonable for your use-case.

I'll write something up as a proposal for first-party and third-party blinding. They use very similar techniques but have different tradeoffs (including interactivity and what state can/can't be shared). It's even messier if you mix the two (a 3-of-5 perhaps with 4 devices that are first-party blinded and 1 device that is third-party blinded).

[Rspigler]

Why not just use BSMS and then Blockchain Commons' SSS library on the descriptor record?

[bitcoinhodler]

Does BSMS solve this?

The nosy signatory cannot have access to any one of my BIP39 seed phrases (either passwordless, or with a password known to the signatory). Otherwise they could guess the derivation paths and find matching pubkeys in the P2WSH withdrawal scripts on the blockchain, exposing all of my spending from this wallet.

[Rspigler]

Ah, no. That would only be an issue once the cold storage was spent from, however. And I don't believe this would be an issue post-taproot.

[Rspigler]

only be an issue once the cold storage was spent from

Point being, I rarely spend from my cold storage, and I have a separate wallet setup for bitcoin I spend more frequently (mobile for example, and another for just desktop use cases, etc).

[ChristopherA]

@Fonta1n3 had been working with some other wallet vendors on a way to share hash first set of addresses to enable address verification between network airgap & networked wallets.

Both @Fonta1n3 & @wolfmcnally are implementing LifeHash for account maps, which requires a canonical hash, possibly useful here.

There is also a form of degenerate Account Map called Policy Maps where all xpubs are removed. These can be used with crypto-request so that the airgap can know what kind of use the xpub will be used for before issuing, and balk if used in some other policy. Gordian Cosigner supports those as well with LifeHash.