Bitcoin Forum

Download link: https://github.com/vbuterin/btckeysplit

Donation address: 1P3QJKmn5hUpRw6Xs4ENVoqiDTy9B4k974 (https://blockchain.info/address/1P3QJKmn5hUpRw6Xs4ENVoqiDTy9B4k974)

This topic came up about two weeks ago (https://bitcointalk.org/index.php?topic=97485.0) on these forums, and I had drafted a standard (which others improved upon) for an algorithm of how to split a private key into an arbitrary n pieces, such that any k (1 <= k <= n) of them could be used to reconstitute the original key. The idea is to make it safer too use offline wallets by maximizing both security against theft and protection against accidental loss by distributing these pieces out to different places all of which are unrelated to each other - if you have a 3-of-5 setup you might keep one at home, another on your computer, a third in a safety deposit box at your bank, a fourth with a friend and a fifth buried in a treasure chest on the beach.

The algorithm is an implementation of Shamir's secret sharing scheme (https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing), using modular arithmetic over modulo N (a prime number imperceptibly smaller than 2^256 that is already a core part of the Bitcoin protocol). To understand how it works, in the basic case of k = 2 the algorithm creates a line using the original data as the y-intercept and a randomly chosen value as the slope (eg. is you're encrypting 167, the line might be y = 13x + 167). It then hands out the pieces as points along the line - piece 1 would be (1, 180), piece 2 would be (2,193), etc. Since two points make a line, anyone with access to any two points can recreate the original line and then get back 167 as the secret. For higher k, like 3, 4 or even 12, polynomials are used instead of lines - the coefficients of a quadratic polynomial, for example, can be determined from any three points along the curve.

The maximum number of pieces that it supports so far is 15, although I am considering increasing that to 255 in the future.

Github for the software is available here: https://github.com/vbuterin/btckeysplit (https://github.com/vbuterin/btckeysplit). It now includes a command line interface which gives you all of these options - run it by calling python main.py. So please download the software and try it out - generate a key, split a key, split a key with one piece from a seed, reconstitute using various combinations of the pieces that get outputted. I would be glad to accept any suggestions for improvement.

Looking into it...

My understanding was that Shamir's Secret Sharing Scheme involves doing the math with finite field arithmetic.  I'd probably feel better about the scheme if that property were maintained, and plus that might also solve the problem of the numbers being too big.

Looked up Shamir's scheme again - looks like you're right. The strict definition does require finite fields. I'm no fan of following strict definitions for their own sake, but here using finite fields would actually make sense since that way any keypiece could itself be split into keypieces, allowing a nested hierarchy system.

What do you think about picking a prime between 2^256 and 2^257, preferably one that can easily be defined (ie. you can memorize an algorithm to generate it), and just doing modular arithmetic over the integers below that? It would still support all the features needed for the system I made so far to work (addition, subtraction, multiplication, division), and you are right, it would get rid of the space problem. It would make more room for pieces too - I don't see a reason why we can't lower the upper limit from 2^280 to 2^272 and increase our limit from 15 all the way to 256.

I would have to think a bit about how to implement the brainwallet piece though - my preliminary reasoning on the matter tells me that the algorithm would involve generating the brainwallet piece and then deriving the key from that, so you cannot generate both the key and the brainwallet piece from a seed (which makes sense, keys that you store k-split don't need to have a single backdoor).

Edit: as a modulus, I found two candidates:

1. 2^256 + 1. It's not prime, but its lowest factor is about 1.2 quadrillion, so the algorithm will fail perhaps at most once every 40 trillion attempts.
2. The Woodall prime (https://oeis.org/A002234) 249 * 2^249 - 1. Slightly more complex in form, but with a size between 2^256 and 2^257 it may be just what we need.

What about the ECDSA secp256k1 value N?  It's slightly smaller than 2^256, but close enough to be even better than 1 in 40 trillion.

That's actually a really good idea - no need to add any new constants that way. Also, aren't privkeys required to be below N anyway?

Hmmmmm .......

Changed the algorithm as per Casascius's suggestions. See latest commit. No brainwallet implementation yet though - I'll bring that back at some point in the future.

i dont understand, but i want to donate :)

Why not post an adress?

If a private key is greater than N, it's equivalent to that same key minus N and will generate the same corresponding public key and bitcoin address. Most tools allow them for input and never generate them on output.

Here's a donation address.

1P3QJKmn5hUpRw6Xs4ENVoqiDTy9B4k974


Alright then, my code does the modular operation at every step so it should have that exact same effect - so, basically, it does work for above-N keys.