Difference between revisions of "User:Vbuterin/K of N redundant offline private key proposal"
(overflow detection and workaround is not necessary if the overflow is prevented in the first place, which is easy to do.) 

(8 intermediate revisions by 2 users not shown)  
Line 2:  Line 2:  
===1. Kpiece key splitting===  ===1. Kpiece key splitting===  
+  This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59character Base58Checkencoded message that starts with the characters "6s".  
−  +  To start off, generate K1 random values, with the ith value (1indexed) being taken from the range [0,min(2^280/k^n,2^256)], then XOR them all together along with the specific key to get one more value. This last value followed by all of the random values make up the kpieces that will go into the next step. The reason why the kpieces need to be sampled from progressively smaller ranges is that the base58check format imposes a maximum value of 2^280  1, and the algorithm for generating the highervalued final key pieces will cause overflow if the full range of [0...2^256) is allowed for all of the intermediate kpieces.  
−  +  Note that implementations which use a different formula than min(2^280/k^n,2^256) to find the random kpiece generator's maxima are perfectly compatible with the original provided that the formula actually works to keep the size of the final output of the algorithm below 2^280.  
−  
−  +  Nearly all 256bit values are valid Bitcoin private keys  the set of 256bit values constituting invalid private keys all start with 127 or more consecutive 0 or 1 bits and are extremely unlikely to be encountered by accident with an appropriate source of random numbers.  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
−  
===2. N piece generation===  ===2. N piece generation===  
Line 35:  Line 19:  
* Each message representing a single part will be 59 base58 characters starting with '6s'.  * Each message representing a single part will be 59 base58 characters starting with '6s'.  
* Byte 0: <code>0x4f</code> (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 0: <code>0x4f</code> (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...  +  * Byte 1: 0x93+k where k = 1...16. 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). 
* Bytes 2,3 = Bitmapped:  * Bytes 2,3 = Bitmapped:  
** bit 15...13 (MSB): The fixed value 011. This is necessary for the uservisible prefix to work as intended.  ** bit 15...13 (MSB): The fixed value 011. This is necessary for the uservisible prefix to work as intended.  
** bit 12: compression flag (0=none, 1=compressed)  ** bit 12: compression flag (0=none, 1=compressed)  
−  ** bits 11...  +  ** bits 11...8: the x coordinate assigned to this key part, taken from the range 0...15 excluding 1 
−  ** bits  +  ** bits 7...0: SHA256(private key)[0], for the purpose of matching parts together 
−  * Bytes 4 thru 38: The number <code>v(1) + v(2)*  +  * Bytes 4 thru 38: The number <code>v(1) + v(2)*x + v(3)*x^2 + v(4)*x^3 + ...</code>. This is equivalent to Shamir's secret sharing scheme. 
−  +  ===Ideas for another iteration===  
+  # An ideal target for a kofn scheme is a deterministic wallet, not just a single address. There should be a field in the message to specify what kind of deterministic wallet is being targeted with respect to the list at [[Deterministic wallet]].  
+  # The current scheme correctly rejects parts that belong to the wrong address, but doesn't reject incompatible parts if the same addresses is encoded twice (with new random values for v(1...8) and then the parts mixed together. Some bits should be dedicated to checksumming the chosen values of v(1...8).  
+  # Avoiding the constraint that v(8) start with a zero bit would be nice  
+  # Using something like AES instead of XOR might increase security without sacrificing reversibility (which is necessary when making KofN of a known, nonrandom key)  
===Example===  ===Example===  
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 <code>v(1)</code>, <code>v(2)</code> and <code>v(3)</code> are):  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 <code>v(1)</code>, <code>v(2)</code> and <code>v(3)</code> are):  
−  # <code>  +  # <code>4f9360?? v(1)</code> 
−  # <code>  +  # <code>4f9362?? v(1) + v(2)*2 + v(3)*4</code> 
−  # <code>  +  # <code>4f9363?? v(1) + v(2)*3 + v(3)*9</code> 
−  # <code>  +  # <code>4f9364?? v(1) + v(2)*4 + v(3)*16</code> 
−  # <code>  +  # <code>4f9365?? v(1) + v(2)*5 + v(3)*25</code> 
−  +  And you're done. Any three of these pieces will be able to be used to reconstitute the original private key, and can be distributed as you like. 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===  ===Key Reconstitution===  
Line 60:  Line 48:  
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 <code>v(1)</code> to <code>v(k)</code>. Once you have these values, XOR all of them to get your final result.  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 <code>v(1)</code> to <code>v(k)</code>. Once you have these values, XOR all of them to get your final result.  
−  For example imagine that you have pieces  +  For example imagine that you have pieces 2, 3 and 5 from above, letting <code>pc(i)</code> be the value from piece <code>i</code> not including the three byte prefix. You thus have: 
<code>  <code>  
−  v(1) + v(2)*2  +  v(1) + v(2)*2 + v(3)*4 = pc(2) 
−  v(1) + v(2)*  +  v(1) + v(2)*3 + v(3)*9 = pc(3) 
−  v(1) + v(2)*  +  v(1) + v(2)*5 + v(3)*25 = pc(5) 
</code>  </code>  
Line 71:  Line 59:  
<code>  <code>  
−  v(1) + v(2)*  +  v(1) + v(2)*3 + v(3)*9 = pc(3) 
−   v(1)  v(2)*2  v(3)*  +   v(1)  v(2)*2  v(3)*4 = pc(2) 
.  .  
−  v(2)  +  v(2) + v(3)*5 = pc(3)  pc(2) 
−  v(1) + v(2)*  +  v(1) + v(2)*5 + v(3)*25 = pc(5) 
−   v(1)  v(2)*2  v(3)*  +   v(1)  v(2)*2  v(3)*9 = pc(2) 
.  .  
−  v(2)*  +  v(2)*3 + v(3)*16 = pc(5)  pc(2) 
−  +  v(2)*3 + v(3)*16 = pc(5)  pc(2)  
−  v(2)  +   v(2)  v(3)*5 = pc(3) + pc(2) 
    
v  v  
−  +  v(2)*3 + v(3)*16 = pc(5)  pc(2)  
−  v(2)*  +   v(2)*3  v(3)*15 = pc(3)*3 + pc(2)*3 
.  .  
−  +  v(3) = pc(5)  pc(3)*3 + pc(2)*2  
−  
−  v(2) = v(3)*  +  v(2) = v(3)*16/3 + pc(5)  pc(2) 
−  v(1) = pc(  +  v(1) = pc(3)  v(2)*3  v(3)*9 
</code>  </code>  
Line 98:  Line 85:  
You actually don't have to know what <code>n</code> is because you can simply assume that <code>n</code> 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 <code>n+1</code>st, <code>n+2</code>nd, etc pieces are all equal to zero.  You actually don't have to know what <code>n</code> is because you can simply assume that <code>n</code> 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 <code>n+1</code>st, <code>n+2</code>nd, etc pieces are all equal to zero.  
−  
− 
Latest revision as of 08:48, 28 August 2012
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:
Contents
1. Kpiece key splitting
This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59character Base58Checkencoded message that starts with the characters "6s".
To start off, generate K1 random values, with the ith value (1indexed) being taken from the range [0,min(2^280/k^n,2^256)], then XOR them all together along with the specific key to get one more value. This last value followed by all of the random values make up the kpieces that will go into the next step. The reason why the kpieces need to be sampled from progressively smaller ranges is that the base58check format imposes a maximum value of 2^280  1, and the algorithm for generating the highervalued final key pieces will cause overflow if the full range of [0...2^256) is allowed for all of the intermediate kpieces.
Note that implementations which use a different formula than min(2^280/k^n,2^256) to find the random kpiece generator's maxima are perfectly compatible with the original provided that the formula actually works to keep the size of the final output of the algorithm below 2^280.
Nearly all 256bit values are valid Bitcoin private keys  the set of 256bit values constituting invalid private keys all start with 127 or more consecutive 0 or 1 bits and are extremely unlikely to be encountered by accident with an appropriate source of random numbers.
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 39byte 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...16. 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).
 Bytes 2,3 = Bitmapped:
 bit 15...13 (MSB): The fixed value 011. This is necessary for the uservisible prefix to work as intended.
 bit 12: compression flag (0=none, 1=compressed)
 bits 11...8: the x coordinate assigned to this key part, taken from the range 0...15 excluding 1
 bits 7...0: SHA256(private key)[0], for the purpose of matching parts together
 Bytes 4 thru 38: The number
v(1) + v(2)*x + v(3)*x^2 + v(4)*x^3 + ...
. This is equivalent to Shamir's secret sharing scheme.
Ideas for another iteration
 An ideal target for a kofn scheme is a deterministic wallet, not just a single address. There should be a field in the message to specify what kind of deterministic wallet is being targeted with respect to the list at Deterministic wallet.
 The current scheme correctly rejects parts that belong to the wrong address, but doesn't reject incompatible parts if the same addresses is encoded twice (with new random values for v(1...8) and then the parts mixed together. Some bits should be dedicated to checksumming the chosen values of v(1...8).
 Avoiding the constraint that v(8) start with a zero bit would be nice
 Using something like AES instead of XOR might increase security without sacrificing reversibility (which is necessary when making KofN of a known, nonrandom key)
Example
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):

4f9360?? v(1)

4f9362?? v(1) + v(2)*2 + v(3)*4

4f9363?? v(1) + v(2)*3 + v(3)*9

4f9364?? v(1) + v(2)*4 + v(3)*16

4f9365?? v(1) + v(2)*5 + v(3)*25
And you're done. Any three of these pieces will be able to be used to reconstitute the original private key, and can be distributed as you like. 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 2, 3 and 5 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)*4 = pc(2)
v(1) + v(2)*3 + v(3)*9 = pc(3)
v(1) + v(2)*5 + v(3)*25 = pc(5)
The simplest method to solve linear systems is elimination, which would work as follows:
v(1) + v(2)*3 + v(3)*9 = pc(3)
 v(1)  v(2)*2  v(3)*4 = pc(2)
.
v(2) + v(3)*5 = pc(3)  pc(2)
v(1) + v(2)*5 + v(3)*25 = pc(5)
 v(1)  v(2)*2  v(3)*9 = pc(2)
.
v(2)*3 + v(3)*16 = pc(5)  pc(2)
v(2)*3 + v(3)*16 = pc(5)  pc(2)
 v(2)  v(3)*5 = pc(3) + pc(2)

v
v(2)*3 + v(3)*16 = pc(5)  pc(2)
 v(2)*3  v(3)*15 = pc(3)*3 + pc(2)*3
.
v(3) = pc(5)  pc(3)*3 + pc(2)*2
v(2) = v(3)*16/3 + pc(5)  pc(2)
v(1) = pc(3)  v(2)*3  v(3)*9
The general pattern is to take k
equations, combine all adjacent pairs to get k1
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+1
st, n+2
nd, etc pieces are all equal to zero.