The one fear that almost everyone owning a cryptocurrency has is the security of their wallet. In fact, there are people who lost all their cryptos which were worth millions of dollars just because they lost the backup of their wallet. Some of them are still searching for their pen drive in the trash. Just Imagine how painful is that? Mathematically speaking the person finding their pen drive in the trash has more probability of finding who Satoshi Nakamoto is than the probability of finding the seed of a lost wallet.
Photo by Tom Fisk from Pexels
We are expected to keep the long 58-base string safe. It is not at all safe to save the seed in a file on the computer or to be uploaded to your favorite cloud services. Also, one can't easily memorize this long string.
For example:
5Kb8YzgWQnogXYB9KkLNydF76MzPL6TsZZf9idDAMssSzY36hWX
Though mnemonics are there to help us simplify this long string using words like history, irony, typists, etc. One can agree that it makes it easier to type them in case the words are written on paper or something similar but it doesn't help us in memorizing the whole seed.
So, neither we can memorize it, nor we can store it on a computer or a cloud service.
What could be the possible solution to safely store the seed such that we can sleep in peace?
The answer is Encryption. But How? Which method is trustworthy?
The method of encryption that we must be using is the Shamir Secret Sharing Algorithm. This algorithm is named after the cryptographer Adi Shamir. The S in the famous cryptosystem RSA is named after his surname.
Explanation
In this part, I'll explain how this algorithm works.
First of all, let's consider we have our seed S to which we want to secure. What this algorithm will do is encode the seed into N different parts, let's say S1, S2, S3, ..., Sn. These parts when treated individually will not show any relation with the seed.
Now each of these parts means nothing individually but when any K number of these parts are combined together they will reconstruct our seed S. What if any K-1 parts are combined? The answer is simple, the seed won't get reconstructed. The only possible way to reconstruct the seed will be to have K or more than K parts together.
For example, we want our secret seed S to be divided into 4 parts and if any 2 parts are combined together, the seed will get reconstructed. Obviously, the seed can also be constructed if we have 3 or 4 parts together but we'll need at least any 2 of them to reconstruct.
Now, you'll be thinking, "How does the algorithm work? It must be complicated to grasp."
You'll be amazed to know the fact that all you need to know is the basic algebra to understand this algorithm.
Now, let me ask you a question. Can you draw a line by using only one point (1,1)?
Probably, No. What about if I give you another point (2,2). Now you can definitely do that. You would probably have the line in your mind y = x.
What about if I give you another point (3,3)? The problem is already solved, you don't need another point. So, now no matter how many points I give to you it won't create any difference.
Please consider the previous example in which we created 4 parts in which any 2 parts can reconstruct the seed. Do you notice anything? The parts represent the points on a graph, which considered individually has no meaning but when any two of them are combined they reveal the equation of the line. The seed can then be inferred through the equation of the line.
In a nutshell, we are hiding the secret key inside the equation of the line, and the parts are represented by the points, which don't contain any significant meaning on their own but when any 2 of them are brought together it may reveal the equation of the line. First of all, we'll convert the base-58 string into an integer, and then that integer will sit in the place of the constant c of the equation y = mx + c (equation of the line with slope m and constant c). So, after constructing the equation of a line, we'll plug x with the value 0 and then the value of y will be equal to the secret key as an integer.
The interesting part of using this algorithm is that we are not limited to just the straight line but we can use any polynomial of degree n. To reconstruct the equation we'll require n+1 points, and thus n+1 shares. For example, if you want that any three shares must be required to construct the secret key, then that can be done using a quadratic equation (a polynomial of degree 2).
To hide a secret key, we'll first convert the secret key to a number, this will be stored in the constant c. Then, we'll generate random numbers for the coefficients a1, a2, ..., an. Then, the shares will be generated as the random points that will lie on the curve represented by the polynomial.
Now, to reconstruct the polynomial equation, we'll need n+1 points.
If there are just two points (x1, y1) and (x2, y2) and we want to calculate the equation of line it can be done using this formula.
In case the polynomial is of a higher degree then we use Lagrange's Polynomial Interpolation to reconstruct the equation. This formula looks a little complicated but is very straightforward in the sense that we have to plug the points in the equation. You can also refer to this YouTube video if you are new to this concept.
Quite Simple! Isn't it?
Cryptographers found this method less secure. So, instead of using the polynomial over real numbers, they prefer to use the polynomial over the Finite Field. Finite Field is similar to real numbers where we can perform operations like addition, subtraction, multiplication, division, etc. but instead of infinite series, we have finite series of {1, 2, 3, ..., p-1}, where p is a very big prime number. Now, explaining it is beyond the reach of this article but I can say that it's easier to learn Finite Field than Trignometry. To understand more you'll also have to read about Elliptic Curve Cryptography. Here's an article to get you started with that.
Though I can show you how complicated the graph of polynomial gets when used over a finite field. Let's consider this polynomial for reference.
This is how this polynomial looks over real numbers.
This is how the same polynomial looks over the finite field of a prime number 251.
Anyone can agree that a finite field adds complexity to the algorithm. If you want to see how a particular polynomial looks in a finite field you can play with the tool here.
Implementation
This final part is for the programmers. The implementation is in Python. If you don't have experience with programming feel free to skip this section and jump directly to the Conclusion.
First of all, we'll generate shares. The function given below will require three arguments n, m, secret. The argument n will store the total number of shares to be generated. The second argument m stores the minimum number of shares required to reconstruct the key. The third argument is the secret key in the integer form. The function generating_coeffs uses random numbers to generate the coefficients of the polynomial. There's another function calculate_y which calculates the value of polynomial by plugging the value of x.
def generate_shares(n, m, secret): """ n -> Total Shares m -> Threshold Required secret -> The secret number """ coeffs = generate_coeffs(m,secret) shares = [] for i in range(n): x = random.randrange(1, field_size) y = calculate_y(x, coeffs) shares.append((x, y)) return sharesNow, this function will return the shares which is the list of tuples.
With the help of any m out of these n shares, the secret key can be reconstructed using Lagrange's Polynomial Interpolation discussed earlier. So, here's the function for reconstructing the key using the given m shares. There is a library used called Decimal which prevents the approximation done by Python, thus providing accurate results.
def reconstruct_secret(shares): """ Uses Lagrange's Interpolation to generate the secret key. Secret = P(0) """ sums, prod_arr = 0, [] for j, (xj, yj) in enumerate(shares): prod = Decimal(1) for i, (xi, yi) in enumerate(shares): if i != j: prod *= Decimal(Decimal(xi)/(xi-xj)) prod *= yj sums += Decimal(prod) return int(round(Decimal(sums),0))
If you want to check the full code, I've created a GitHub repository.
Conclusion
This algorithm can be used to create a number of shares that can be stored in the cards similar to the size of a credit card. Those cards can then be stored at safe locations or can be given to family members or friends that you trust. When a significant number of cards are brought together the secret key could be reconstructed. Thus providing you with a very safe backup of your wallet.
If you are very rich and holds a large number of cryptos, you may prefer to store the shares in the vaults of different countries. You can even make your friends and family members as the nominees to the vaults. So, in case of your death, they can use the cryptos you own.
