Bitcoin Wiki - User contributions [en]

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

2012-08-28T08:48:38Z

Vbuterin:

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===
This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59-character Base58Check-encoded message that starts with the characters "6s".

To start off, generate K-1 random values, with the ith value (1-indexed) 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 k-pieces that will go into the next step. The reason why the k-pieces 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 higher-valued final key pieces will cause overflow if the full range of [0...2^256) is allowed for all of the intermediate k-pieces.

Note that implementations which use a different formula than min(2^280/k^n,2^256) to find the random k-piece 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 256-bit values are valid Bitcoin private keys - the set of 256-bit 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into <code>n</code> pieces, any <code>k</code> of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> 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: <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...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 user-visible 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 <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 k-of-n 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 K-of-N of a known, non-random 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 <code>v(1)</code>, <code>v(2)</code> and <code>v(3)</code> are):

# <code>4f9360?? v(1)</code>
# <code>4f9362?? v(1) + v(2)*2 + v(3)*4</code>
# <code>4f9363?? v(1) + v(2)*3 + v(3)*9</code>
# <code>4f9364?? v(1) + v(2)*4 + v(3)*16</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===

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 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>
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)
</code>

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

<code>
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

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

2012-08-28T00:30:24Z

Vbuterin:

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===
This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59-character Base58Check-encoded message that starts with the characters "6s".

To start off, generate K-1 random values, with the ith value (1-indexed) 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 k-pieces that will go into the next step. The reason why the k-pieces 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 higher-valued final key pieces will cause overflow if the full range of [0...2^256) is allowed for all of the intermediate k-pieces.

Nearly all 256-bit values are valid Bitcoin private keys - the set of 256-bit 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into <code>n</code> pieces, any <code>k</code> of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> 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: <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...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 user-visible 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 <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 k-of-n 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 K-of-N of a known, non-random 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 <code>v(1)</code>, <code>v(2)</code> and <code>v(3)</code> are):

# <code>4f9360?? v(1)</code>
# <code>4f9362?? v(1) + v(2)*2 + v(3)*4</code>
# <code>4f9363?? v(1) + v(2)*3 + v(3)*9</code>
# <code>4f9364?? v(1) + v(2)*4 + v(3)*16</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===

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 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>
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)
</code>

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

<code>
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

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

2012-08-13T11:34:32Z

Vbuterin: Created page with "There is NO reason why this needs to be limited to 8 keys. I understand that the exponentiation causes overflow if you generate all 8 pieces from [0,2^256), but there is no ne..."

There is NO reason why this needs to be limited to 8 keys. I understand that the exponentiation causes overflow if you generate all 8 pieces from [0,2^256), but there is no need to do that. There is nothing wrong with generating the pieces in reverse order and just limiting the higher ones to progressively decreasing maxima.

[[User:Vbuterin|Vbuterin]] ([[User talk:Vbuterin|talk]]) 11:34, 13 August 2012 (GMT)

User talk:Vbuterin

2012-08-07T23:25:13Z

Vbuterin: /* K_of_N_redundant_offline_private_key_proposal */

==K_of_N_redundant_offline_private_key_proposal==

[[User:Vbuterin/K_of_N_redundant_offline_private_key_proposal]]

I just checked Recent Changes and was excited to see you putting this together! A few things:

# Does this bear any similarity to "Shamir's secret-sharing scheme"? (which I know little about other than having skimmed the Wikipedia article)
# Your proposal points out that the payload will have varying lengths, but the same time, stipulates a prefix of 0x86 for the benefit of the user. Off the top of your head, how much do the lengths vary? The reason I ask is that the prefix on the base58 string as seen by the user only stays constant when the number of bytes in the message is constant. If the variation isn't that much, then adding padding bytes might work. For example, the private key that starts with '5' suddenly starts with a 'K' or 'L' when an extra byte is added. If it isn't clear why, a simple analogy can be made for hexadecimal vs. decimal: all four-digit decimal numbers that start with 5 (i.e. decimal numbers between 5000 and 5999) will have a hex equivalent that starts with 1, but it's not true for non-4-digit numbers: 50000 and 59999 will have a hex equivalent that starts not with 1, but instead, C, D, or E.
# Somewhere in the message, there should be a 1-bit flag that tells whether to create the bitcoin address from the uncompressed vs. compressed public key.
# Somewhere in the message, there ought to be a small handful of bits taken from the resulting bitcoin address, so a user interface accepting parts one by one can reliably detect and complain: "The last part you entered does not belong to the part(s) you entered before".
# Somewhere in the message, there should be a count that tells the UI how many total parts are needed and how many exist. (e.g. the values of K and N)

[[User:Casascius|Casascius]] ([[User talk:Casascius|talk]]) 19:54, 5 August 2012 (GMT)

# @1 I came up with the idea myself, so it wasn't inspired by Shamir's scheme.
# @2 The longest piece should be 256 + n*log2(k) bits long, so 257 for the degenerate (1,1) case, 264 for (5,3) and 292 for (12,8). Thus, for high values of i, as it seems that you have already realized, the randomly chosen values do need to get progressively smaller if you want to impose a maximum size limit on the pieces. Making each piece random(0,min(2^256,2^288/k^(3*k))) rather than random (0,2^256) might be a good idea.
# @3,4 Sure, sounds good
# @5 Neither N nor K is strictly necessary, but I can see how it would be nice to have for usability purposes.

[[User:Vbuterin|Vbuterin]] ([[User talk:Vbuterin|talk]]) 23:25, 7 August 2012 (GMT)

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

2012-08-07T13:43:44Z

Vbuterin: /* 1. K-piece key splitting */

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===
This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59-character Base58Check-encoded message that starts with the characters "6s".

If generating a new random key, simply generate K random 256-bit values. If N and K are both 8, then the 8th randomly-generated value needs to have its most significant bit set to zero to prevent an overflow condition described later.

If splitting a specific key, then simply generate K-1 random 256-bit values, taking care that the value to be used in position #8 has its most significant bit set to zero, then XOR them all together along with the specific key. The result of the XOR operation should be used in a position other than the one with a constraint on the highest bit.

Nearly all 256-bit values are valid Bitcoin private keys - the set of 256-bit 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into <code>n</code> pieces, any <code>k</code> of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> 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: <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...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...13 (MSB): The fixed value 011. This is necessary for the user-visible prefix to work as intended.
** 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 the purpose matching parts together and verification they produce the correct address
* Bytes 4 thru 38: The number <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

There are 280 bits allocated to the number (35 bytes). This will fit all of the 256-bit numbers generated in the scheme, multiplied by their respective factors. However, there is one exception: if a user generates an 8-of-8 code, then the factors used to create the eighth code will overflow and require 281 bits whenever v(8) exceeds a certain threshold. In order to prevent this, the value for v(8) needs to be chosen with its eight most significant bits set to zero.

===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):

# <code>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 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>
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)
</code>

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

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-07T13:43:06Z

Vbuterin:

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===
This proposal provides a scheme where a key can be broken into up to 8 parts, and each part is serialized as a 59-character Base58Check-encoded message that starts with the characters "6s".

If generating a new random key, simply generate K random 256-bit values. If N and K are both 8, then the 8th randomly-generated value needs to have its most significant bit set to zero to prevent an overflow condition described later.

If splitting a specific key, then simply generate K-1 random 256-bit values, taking care that the value to be used in position #8 has its most significant bit set to zero, then XOR them all together along with the specific key. The result of the XOR operation should be used in a position other than the one with a constraint on the highest bit.

Nearly all 256-bit values are valid Bitcoin private keys - the set of 256-bit 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.

Pseudocode implementation (doesn't apply anymore)

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into <code>n</code> pieces, any <code>k</code> of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> 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: <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...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...13 (MSB): The fixed value 011. This is necessary for the user-visible prefix to work as intended.
** 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 the purpose matching parts together and verification they produce the correct address
* Bytes 4 thru 38: The number <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

There are 280 bits allocated to the number (35 bytes). This will fit all of the 256-bit numbers generated in the scheme, multiplied by their respective factors. However, there is one exception: if a user generates an 8-of-8 code, then the factors used to create the eighth code will overflow and require 281 bits whenever v(8) exceeds a certain threshold. In order to prevent this, the value for v(8) needs to be chosen with its eight most significant bits set to zero.

===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):

# <code>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 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>
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)
</code>

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

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:22:58Z

Vbuterin: /* 2. N piece generation */

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, <code>P</code>, and find <code>k</code> values (which we'll call<code> v(1)</code> to <code>v(k)</code>) which meet the following conditions:

# <code>hex(SHA256(i))</code> starts with <code>'00'</code> for all <code>i 1</code> to <code>k</code> - this is the checksum
# <code>XOR</code>(<code>v(i)</code> for all <code>i 1</code> to <code>k</code>) = the original private key

Pseudocode implementation:

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into <code>n</code> pieces, any <code>k</code> of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> will have the following format:

* Byte 0 = <code>0x86</code> (unique "format" identifier to make keyparts in base 58 recognizable to the untrained eye)
* Byte 1 =<code> i</code>
* Byte 2 = byte length of everything coming after it (leave this blank at first, and calculate it at the end).
* Bytes 3-whatever = <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

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>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 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>
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)
</code>

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

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:20:43Z

Vbuterin: /* Key Reconstitution */

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, <code>P</code>, and find <code>k</code> values (which we'll call<code> v(1)</code> to <code>v(k)</code>) which meet the following conditions:

# <code>hex(SHA256(i))</code> starts with <code>'00'</code> for all <code>i 1</code> to <code>k</code> - this is the checksum
# <code>XOR</code>(<code>v(i)</code> for all <code>i 1</code> to <code>k</code>) = the original private key

Pseudocode implementation:

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into n pieces, any k of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> will have the following format:

* Byte 0 = <code>0x86</code> (unique "format" identifier to make keyparts in base 58 recognizable to the untrained eye)
* Byte 1 =<code> i</code>
* Byte 2 = byte length of everything coming after it (leave this blank at first, and calculate it at the end).
* Bytes 3-whatever = <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

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>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 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>
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)
</code>

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

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:17:41Z

Vbuterin: /* Key Reconstitution */

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, <code>P</code>, and find <code>k</code> values (which we'll call<code> v(1)</code> to <code>v(k)</code>) which meet the following conditions:

# <code>hex(SHA256(i))</code> starts with <code>'00'</code> for all <code>i 1</code> to <code>k</code> - this is the checksum
# <code>XOR</code>(<code>v(i)</code> for all <code>i 1</code> to <code>k</code>) = the original private key

Pseudocode implementation:

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into n pieces, any k of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> will have the following format:

* Byte 0 = <code>0x86</code> (unique "format" identifier to make keyparts in base 58 recognizable to the untrained eye)
* Byte 1 =<code> i</code>
* Byte 2 = byte length of everything coming after it (leave this blank at first, and calculate it at the end).
* Bytes 3-whatever = <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

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>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 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>
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)
</code>

Elimination goes as follows:

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:17:24Z

Vbuterin: /* Key Reconstitution */

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, <code>P</code>, and find <code>k</code> values (which we'll call<code> v(1)</code> to <code>v(k)</code>) which meet the following conditions:

# <code>hex(SHA256(i))</code> starts with <code>'00'</code> for all <code>i 1</code> to <code>k</code> - this is the checksum
# <code>XOR</code>(<code>v(i)</code> for all <code>i 1</code> to <code>k</code>) = the original private key

Pseudocode implementation:

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into n pieces, any k of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> will have the following format:

* Byte 0 = <code>0x86</code> (unique "format" identifier to make keyparts in base 58 recognizable to the untrained eye)
* Byte 1 =<code> i</code>
* Byte 2 = byte length of everything coming after it (leave this blank at first, and calculate it at the end).
* Bytes 3-whatever = <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

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>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 from above, letting <code>pc(i)</code> be the value from piece i not including the three byte prefix. You thus have:

<code>
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)
</code>

Elimination goes as follows:

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:14:27Z

Vbuterin: /* Key Reconstitution */

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, <code>P</code>, and find <code>k</code> values (which we'll call<code> v(1)</code> to <code>v(k)</code>) which meet the following conditions:

# <code>hex(SHA256(i))</code> starts with <code>'00'</code> for all <code>i 1</code> to <code>k</code> - this is the checksum
# <code>XOR</code>(<code>v(i)</code> for all <code>i 1</code> to <code>k</code>) = the original private key

Pseudocode implementation:

<syntaxhighlight lang="python">
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]
</syntaxhighlight>

So far, what we have are <code>k</code> 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 <code>k</code> pieces, once again referred to as <code>v(1)</code> to <code>v(k)</code>, into n pieces, any k of which can be used to find the original values <code>v(1)</code> to <code>v(k)</code>.

Piece <code>i</code> will have the following format:

* Byte 0 = <code>0x86</code> (unique "format" identifier to make keyparts in base 58 recognizable to the untrained eye)
* Byte 1 =<code> i</code>
* Byte 2 = byte length of everything coming after it (leave this blank at first, and calculate it at the end).
* Bytes 3-whatever = <code>v(1) + v(2)*2^i + v(3)*3^i + v(4)*4^i + ...</code>

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>0x86 1 33 v(1) + v(2)*2 + v(3)*3</code>
# <code>0x86 2 33 v(1) + v(2)*4 + v(3)*9</code>
# <code>0x86 3 33 v(1) + v(2)*8 + v(3)*27</code>
# <code>0x86 4 33 v(1) + v(2)*16 + v(3)*81</code>
# <code>0x86 5 34 v(1) + v(2)*32 + v(3)*243</code>

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 <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 1, 3 and 4 from above. You thus have:

<code>
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)
</code>

Elimination goes as follows:

<code>
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)
|
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
</code>

The general pattern is to take <code>k</code> equations, combine all adjacent pairs to get <code>k-1</code> equations without any coefficient for <code>v(1)</code> and repeat the process until you're down to a single equation of the form <code>v(k)*a = b</code>. 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 <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.

The scheme can easily be adapted to make the private key the EC product of <code>v(1)</code>, <code>v(2)</code>, 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.

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

2012-08-05T12:10:02Z

Vbuterin: /* 2. N piece generation */

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

2012-08-05T12:06:09Z

Vbuterin: /* 1. K-piece key splitting */

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

2012-08-05T12:03:08Z

Vbuterin: /* 2. N piece generation */

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

2012-08-05T11:49:56Z

Vbuterin: Created page with "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 lo..."