User:Vbuterin/K of N redundant offline private key proposal

There is an important tradeoff between security and recoverability when storing an offline wallet. The simplest setup, storing the entire private key in a single place in a lockbox, provides medium security but is vulnerable to accidental loss or destruction through accidents such as fire. Storing a simple backup of the key mitigates this risk, but at the same time decreases security, and the opposite strategy, splitting the key into multiple pieces, all of which must somehow be combined to retrieve the original key, increases security but makes the accidental loss problem even worse. The optimal solution is a setup which combines the two strategies, allowing the key to easily be split up into n pieces, any k of which can be used to recover the original key. The simplest such setup is storing k parts of the key and then an XOR of all k parts, but that approach is limiting as it only allows for n = k+1. What this document proposes is a setup which allows any n and k to be used. The steps are the following:

1. K-piece key splitting

Take your private key, P, and find k values (which we'll call v(1) to v(k)) which meet the following conditions:

1. hex(SHA256(i)) starts with '00' for all i 1 to k - this is the checksum
2. XOR(v(i) for all i 1 to k) = the original private key

Pseudocode implementation:

def generate(P,k):
  v = array(k)
  for i in range(0,k-2):
    while hex(sha256(v[i]))[0:2] != '00':
      v[i] = random(1,2^256)
  remainder = P
  for i in range(0,k-2):
    remainder = remainder XOR v[i]
  while hex(sha256(v[k-2]))[0:2] != '00' or hex(sha256(v[k-1]))[0:2] != '00':
    v[k-2] = random(1,2^256)
    v[k-1] = remainder XOR v[k-2]

So far, what we have are k pieces that can be trivially recombined (through XOR) into the original private key, and all of which have a basic checksum to provide some protection against mistakes.

2. N piece generation

The next step will transform these k pieces, once again referred to as v(1) to v(k), into n pieces, any k of which can be used to find the original values v(1) to v(k).

Piece i will have the following format:

• This message contains a 39-byte payload.
• Each message representing a single part will be 59 base58 characters starting with '6s'.
• Byte 0: 0x4f (unique "format" identifier to make keyparts in base 58 start with '6s' to be recognizable visually, when used properly in combination with byte 1)
• Byte 1: 0x93+k where k = 1...8. This will result in the third character being a digit 1 thru 8 so the user can see the value of k. (e.g. 6s1, 6s2, 6s3, 6s4, 6s5, 6s6, 6s7, 6s8 prefixes). Highest allowable value: 0x9c
• Bytes 2,3 = Bitmapped:
  • bit 15 (MSB): Does the number overflow its 35-byte (280 bit) buffer? 0 if no, 1 if yes. (Overflows only happen when k==n==8)
  • bit 14...13 (MSB): Two overflow bits provided if the 280-bit buffer is overflowed. If not needed, these bits MUST be set to 11 to keep the visual prefix intact.
  • bit 12: compression flag (0=none, 1=compressed)
  • bits 11...9: which key part this is, minus 1
  • bits 8...0: SHA256(resulting bitcoin address)[0...1] & 0x01FF, for matching parts together and verification they produce the correct address
• Bytes 4 thru 38: The number v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...

With 8 possible codes, it is presumed that the highest possible value in bytes 4...38 will be 8^8 (whose result is a 25-bit number 0x1000000) * any 256 bit number, which will always result in a number no larger than 281 bits. 280 bits will fit in 35 bytes (provided for). If the MSB out of 281 bits is high (which can happen if k==8 and n==8), then the constant 011 in the header must become 010.

For example, if you want your private key to require three out of five pieces to reconstitute, the final pieces will be (byte lengths will depend on exactly what v(1), v(2) and v(3) are):

1. 0x86 1 33 v(1) + v(2)*2 + v(3)*3
2. 0x86 2 33 v(1) + v(2)*4 + v(3)*9
3. 0x86 3 33 v(1) + v(2)*8 + v(3)*27
4. 0x86 4 33 v(1) + v(2)*16 + v(3)*81
5. 0x86 5 34 v(1) + v(2)*32 + v(3)*243

When you're done, the pieces can be kept as hex or base58 - either format works fine, and stored wherever you want. You might, for example, store one in a safe at home, another at a safety deposit box at the local bank, a third on your computer, a fourth with a friend and memorize the fifth.

Key Reconstitution

To reconstitute the private key, simply solve the linear system from any three pieces, inferring from the second byte of the pieces what all the coefficients are, to get the original values v(1) to v(k). Once you have these values, XOR all of them to get your final result.

For example imagine that you have pieces 1, 3 and 4 from above, letting pc(i) be the value from piece i not including the three byte prefix. You thus have:

 v(1) + v(2)*2  + v(3)*3  = pc(1)
 v(1) + v(2)*8  + v(3)*27 = pc(2)
 v(1) + v(2)*16 + v(3)*81 = pc(3)

The simplest method to solve linear systems is elimination, which would work as follows:

   v(1) + v(2)*8  + v(3)*27 =  pc(2)
 - v(1) - v(2)*2  - v(3)*3  = -pc(1)
 .----------------------------------
          v(2)*6  + v(3)*24 =  pc(2) - pc(1)

   v(1) + v(2)*16  + v(3)*81 =  pc(3)
 - v(1) - v(2)*2   - v(3)*3  = -pc(1)
 .----------------------------------
          v(2)*14  + v(3)*78 =  pc(3) - pc(1)

 v(2)*14  + v(3)*78  = pc(3) - pc(1)
 v(2)*6   - v(3)*24  = pc(2) - pc(1)    <----how did you get this?  shouldn't it be + v(3)*24 not -v(3)*24? Casascius (talk) 06:12, 6 August 2012 (GMT)
                     |  
                     v
 v(2)*84  + v(3)*468 = pc(3)*6  - pc(1)*6
 v(2)*84  - v(3)*336 = pc(2)*14 - pc(1)*14
 .----------------------------------------
            v(3)*132 = pc(3)*6  - pc(2)*14   + pc(1)*8
            v(3)     = (pc(3)*6  - pc(2)*14   + pc(1)*8) / 132
                     
 v(2) = -v(3)*78/14 + pc(3) - pc(1)
 v(1) = pc(2) - v(2)*8 - v(3)*27

The general pattern is to take k equations, combine all adjacent pairs to get k-1 equations without any coefficient for v(1) and repeat the process until you're down to a single equation of the form v(k)*a = b. From there, just work your way back up the chain of intermediate equations to get all the other values.

You actually don't have to know what n is because you can simply assume that n is the number of pieces that you have, and if you have too many pieces solving the linear system will simply lead you to discover that the n+1st, n+2nd, etc pieces are all equal to zero.

The scheme can easily be adapted to make the private key the EC product of v(1), v(2), etc rather than an XOR, and even the linear systems can be changed to an multiplicative/exponential equivalent if desired, so it's pretty adaptable.