Bitcoin Secret Sharing

Aug 27, 2024

Introduction

You have just created your Bitcoin wallet and written down the 12 or 24 words of your seed phrase on a piece of paper. At this point, you fear losing it or that it might get damaged, so you think about making a copy. However, this leaves you having to hide two papers in secure locations, increasing the probability that someone might find them and obtain the seed phrase, consequently gaining access to your funds.

So, you try to “split” the seed phrase, distributing the words across multiple sheets so that no single one contains the full list. This solution, however, is riskier than it seems: in some cases, an attacker who obtains even just a portion of the words could still reconstruct the entire seed phrase.

There is, however, a more secure method called Shamir Secret Sharing. Based on mathematics, it allows you to divide the seed phrase into multiple parts without compromising its security.

Anatomy of a Wallet

To truly understand which practices can put the security of your bitcoin at risk, it is useful to start with how a Bitcoin wallet works.

A wallet is, essentially, a collection of public and private key pairs. The private key must remain secret and is used to sign transactions. The public key, on the other hand, is mathematically derived from the private one and allows for the public verification of the digital signature’s validity.

To make management, backup, and portability easier, the BIP32 and BIP44 (Bitcoin Improvement Proposal) standards define a method to deterministically derive all the private keys of a wallet starting from a string of entropy of 128 or 256 bits.

To facilitate the transcription of this entropy, the BIP39 standard represents it through a list of English words.

In practice, writing down the 12 or 24 words of the seed phrase on paper allows the wallet to deterministically regenerate all the private keys.

The 256-bit entropy consists of a sequence of 256 randomly generated binary values (0 or 1), which correspond to a massive binary number: for an attacker without a priori information, trying to derive a wallet’s entropy would be equivalent to guessing a number between $0$ and $2^{256} \approx 1.1579 \cdot 10^{77}$ (a number larger than the atoms in the observable universe!).

For an attacker, possessing even a part of the entropy would provide an exponential advantage, compromising the security of the funds.

How the Method Works

Secret Sharing allows for the division of a secret (in this case, the wallet’s entropy) into several parts without reducing its security.

Two parameters are defined: the total number of parts $n$ and the threshold $m$ . The original secret can be reconstructed only by having at least $m$ parts out of $n$ .

If you possess fewer than $m$ parts, however, you obtain no useful information about the secret.

For example, it is possible to divide the entropy into 3 parts and require 2 for reconstruction: any pair of parts among the 3 is sufficient. Similarly, one can use 3-of-5 schemes, 4-of-6, and so on. In this way, the possibility of recovery is maintained even if one part is lost or becomes inaccessible, without offering an advantage to an attacker who does not reach the threshold.

Mathematical Description

From a mathematical perspective, the method is based on the principle that to uniquely identify a polynomial function of degree $g$ , $g+1=m$ points are required.

For example, to uniquely identify a line, at least two points are necessary, as infinite lines pass through a single point.
Similarly, to uniquely determine a second-degree curve (parabola), three points are required.

Possessing fewer points than required to uniquely determine the function is completely useless, as there would be infinite functions passing through those points.

The polynomial function can be represented in this form:

\Pi_g(x) = y_0 \psi_0(x) + y_1 \psi_1(x) +

... + y_n\psi_g(x)

where the original information is represented by the point $a_0$ (the intersection of the function with the $y$ -axis).

The functions $\psi_i$ are the characteristic polynomials, whose coefficients can be reconstructed using the Lagrange interpolation method:

\Pi_g(x) = \sum_{k=0}^g{y_k \psi_k(x)} =

= \sum_{i=0}^g{y_k \prod_{j=0,j\neq i}^g{\frac{x-x_j}{x_i-x_j}}}

Implementation

To simplify the process of splitting and reconstructing entropy via mnemonics, I have implemented a simple program in Rust, which can be found in the public repository https://github.com/damianobacchin/bitcoin-secret-sharing

Note: The code is created purely for educational purposes. Do not use it to store real funds, as incorrect use could lead to the loss of funds.