Proposal: proquints encoded HD wallet root key with n-of-m support

[martinus]

I've been working on an alternative to BIP39. These are my main motivations:

• I wanted to get rid of the wordlist, and replace it with a more language agnostic representation that's still relatively easy to read.
• Much more compact representation.
• Use a configurable n-of-m representation of the root key instead of passwords

Additionally, the prototype that I have has these features:

• Very compact representation: 16bit overhead for each share
• 4 version bits. This prototype is currently version 0.
• Supports n-of-m shares, up to 4-of-4.
• Very good safety against typos: The probability that a typo of a 2-of-m share is undetected is 1 in 262144.
• Very compact QR code: 128 bit encode into 45 Alphanumeric characters, so version 2 is enough. E.g. see https://chart.googleapis.com/chart?chs=150x150&cht=qr&chl=BASABMIVAPPOTUFJULOHHIFOBRIGIJPAJIHLUTOLHAJAJ
• Accidentally mixing two shares that were constructed from different secret is undetected with a probability of 1 in 65536.
  
• the proquints representation is optional, e.g. base 58 is also possible.

Here is a sample random 128 bit secret encoded in 2-of-3 shares:

batod kibab namus jupag pahot zumas filur fuhuk hojid
bipap bupar bugul nadun lokil kuhoj jilub buzih pijuv
bonik foguf mutal fasoz gaham dugar mubab dakap bofif

Each share consists of 9 proquints (see https://arxiv.org/html/0901.4016) encoding 16 bits each. The first proquint is special: it encodes the version, share ID, number of required shares to reconstruct the secret, and checksum.

• Version: the first 4 bit. Since the first 4 bit are encoded by the first letter, the letter for version 0 is always 'b'.
• Share ID: 2 bits to identify the ID of the share (1, 2, 3, 4).
  
• The next 10 bits encode the number of required shares (2 bit), and 1-byte checksum of the reconstructed secret. These 10 bit are XORed with 10 bits of the checksum of the share when the 10 bits were set to zero. When decoding the message from two shares, the number of required shares and 1-byte checksum of the secret is reconstructed for each share by XORing back with the share's checksum. Both shares must decode the same 10 bits to be valid. Additionally, the first byte of the reconstructed secret's checksum must match for a reconstruction to be successfull. Thus, the actual safety of this checksumming system is 2^10 * 2^8 = 2^18 = 262144 (there is a 1 in 262144 chance that a typo remains undetected).

I have a prototypical implementation in Ruby here: https://github.com/martinus/bitcoin-mnemonic/blob/master/bitcoin-mnemonic.rb.

What do you think? I appreciate any comments!

[Quickseller]

I am not quite sure I am understanding what you are proposing. It is currently possible to combine m xpub keys to create a n of m HD wallet.

When creating a multisig address/wallet, it is important to use very different public keys generated and stored either by different people or in different locations, otherwise you lose out in the added security of multisig.

[martinus]

This is different from multisignature. This a representation to store the root key, which might be part of a multisignature wallet or not. My proposal is similar to this: https://github.com/cetuscetus/btctool/blob/bip/bip-xxxx.mediawiki

[Quickseller]

I have never really understood the advantage of Shamirs Secret Sharing over multisig.

With Shamirs secret sharing, you are generating the private key on a single device (I think), and must ultimately use one device to calculate the private key when you wish to use the private key. With multisig, you have multiple private keys that can be kept entirely separate, including when you wish to spend funds controlled by said private keys.

Multisig is more expensive to use as there is more signature data, however both are generally designed so that  most entities use both 'systems' for a small minority of their transactions.

[martinus]

I have never really understood the advantage of Shamirs Secret Sharing over multisig.

I see that Shamir's secret Sharing only as an alternative to passwords, not as an alternative to multiwallets. So in most cases this feature is not needed at all. Here are two examples:

Scenario #1: Multiwallet 2-of-2, passwordless

With BIP39 you can use two keys, e.g.
    before circle champion auto sleep embody nose february illegal refuse solve build
and a second key:
    enable struggle rather mail sea ski similar achieve ride wave hold black

The equivalent version with my proposal would be to use two 1-of-1 keys, e.g.
    banof gubit zokom zimuv tahuz vohih sahir nanuv vibar
and a second key:
    babor josas zasag dotit sasub jinug fanim lazup zogiv

The advantage of using my proposed proquints encoding here is that it's language agnostic, shorter, and provides better safety against typos

Scenario #2: 2-of-2 Multiwallet, one part password protected.

Again say you want to have a 2-of-2 multiwallet. In BIP39 it looks like this:

Part 1:
    dentist liquid evoke universe clinic convince cute erase fold about swap anger

Part 2:
    pepper cliff fruit wise extend daughter symptom quick once love shadow snap
password for part 2:
    my secret password that I will surely remember

In my proposal Part 1 is equivalent to above, a simple 1-of-1 proquint encoded key:
    bakad pusuz mamis vinod vutat siniz jutur vunun ruluv

For the second part of the multiwallet, since I do not support passwords, the alternative is to use a 2-of-2 shamir's secret:
    batuh nifat sizip jimuz hiror hibus masum ragis guhid
    bijol guhuh rudis hijag jofir virif duruv hudoz kufis

So instead of the 2 parts mnemonic & password, the key consists of 2 parts mnemonic & mnemonic. The main advantage here is that the password is replaced with another share that is required to reconstruct the secret.