Threshold-encryption for multisig backups. This is a demo to backup the xpubs of a 3-of-5 multisig

threshold-encrypted-backup.py

#
# This is a scheme to encrypt a backup of a t-of-n Multisig spending script
# such that any combination of t-of-n xpubkeys can recover the missing (n-t) xpubkeys.
#
#
# In this example, we encrypt the 5 xpubkeys of a 3-of-5 Multisig 
# and demonstrate how to recover from any 3 xpubkeys the other 2 missing xpubkeys.
#
# The scheme is a simple variation of Shamir's secret sharing.
# It is nicely compact. The encrypted payload is only the size of 2 xpubkeys.
#


# Encode a string as a big integer
def string_to_int(s: str, encoding='utf-8') -> int:
    byte_representation = s.encode(encoding)
    return int.from_bytes(byte_representation, 'big')

# Decode a string into a big integer
def int_to_string(num: int, encoding='utf-8') -> str:
    num_of_bytes = (num.bit_length() + 7) // 8  # Calculate number of bytes required for the integer
    byte_representation = num.to_bytes(num_of_bytes, 'big')
    return byte_representation.decode(encoding)


# Lagrange interpolation
def lagrange_interpolation(points, field_size, x_interpolate):
    def lagrange_basis(i, x):
        basis = 1
        for j in range(len(points)):
            if j != i:
                basis *= (x - points[j][0]) * pow(points[i][0] - points[j][0], -1, field_size)
                basis %= field_size
        return basis
    
    interpolated_value = 0
    for i in range(len(points)):
        basis = lagrange_basis(i, x_interpolate)
        interpolated_value += (basis * points[i][1]) % field_size
        interpolated_value %= field_size
        
    return interpolated_value

# Some random prime which is large enough to contain xpub keys
# This constant should be chosen once and for all users
FIELD_SIZE = 0x100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000000000000000000000000000000000000000000000000b77


# Example xpubkeys included in this 3-of-5 backup
xpubkeys = [
    "xpub6BosfCnifzxcFwrSzQiqu2DBVTshkCXacvNsWGYJVVhhawA7d4R5WSWGFNbi8Aw6ZRc1brxMyWMzG3DSSSSoekkudhUd9yLb6qx39T9nMdj",
    "xpub6CUGRUonZSQ4TWtTMmzXdrXDtypWKiKrhko4egpiMZbpiaQL2jkwSB1icqYh2cfDfVxdx4df189oLKnC5fSwqPfgyP3hooxujYzAu3fDVmz",
    "xpub6BosfCnifzxcM3XKbZdmQiRs8P7HbYMGZaAAYRShiwPHmTq6S5vE1ZzYtpzAXgZ9WE3aSq7CST7tZJuXhjZAKoE3jo63Eeu2ajtzu9twvP5",
    "xpub661MyMwAqRbcG8Zah6TcX3QpP5yJApaXcyLK8CJcZkuYjczivsHxVL5qm9cw8BYLYehgFeddK5WrxhntpcvqJKTVg96dUVL9P7hZ7Kcvqvd",
    "xpub6BosfCnifzxcN6JHh8D8y7HZMXJU3SJ2AoCLNQLNLY5evZJwaF1CUDGZL5Ge2PKe7eQXeT5gE3RKokMGRsYkPyMPpkfDBfxerBaVxEFsykt"
]

# Convert the xpubkeys to points
points = [(i+1, string_to_int(xpub)) for i, xpub in enumerate(xpubkeys)]


#
# Sample two more points on the polynomial
# Those are the "public points", which act as the encrypted backup
# E.g. you could inscribe them into the blockchain
# 
print(f"++ Encrypt the Backup ++")

x_interpolate = 6 
encrypted_value1 = lagrange_interpolation(points, FIELD_SIZE, x_interpolate)
print(f"The first public value is f({x_interpolate}) = {hex(encrypted_value1)}")

x_interpolate = 7  
encrypted_value2 = lagrange_interpolation(points, FIELD_SIZE, x_interpolate)
print(f"The second public value is f({x_interpolate}) = {hex(encrypted_value2)}")



# 
# Example recovery using any combination of three xpubkeys
#
print("\n\n++ Decrypt the Backup using 3-of-5 xpub keys ++")

# To recover missing keys we have to know any three xpubkeys. In this example, it's xpubkey2, xpubkey3, xpubkey5. 
# We want to recover the two missing keys, here, xpubkey1 and xpubkey4
points = [
    (2, string_to_int("xpub6CUGRUonZSQ4TWtTMmzXdrXDtypWKiKrhko4egpiMZbpiaQL2jkwSB1icqYh2cfDfVxdx4df189oLKnC5fSwqPfgyP3hooxujYzAu3fDVmz")),
    (3, string_to_int("xpub6BosfCnifzxcM3XKbZdmQiRs8P7HbYMGZaAAYRShiwPHmTq6S5vE1ZzYtpzAXgZ9WE3aSq7CST7tZJuXhjZAKoE3jo63Eeu2ajtzu9twvP5")),
    (5, string_to_int("xpub6BosfCnifzxcN6JHh8D8y7HZMXJU3SJ2AoCLNQLNLY5evZJwaF1CUDGZL5Ge2PKe7eQXeT5gE3RKokMGRsYkPyMPpkfDBfxerBaVxEFsykt"))
]

# Append the two public points
points.append((6, encrypted_value1))
points.append((7, encrypted_value2))

# Interpolate the first missing key, xpubkey1 = f(1)
x_interpolate = 1
interpolated_value = lagrange_interpolation(points, FIELD_SIZE, x_interpolate)
print(f"The recovered xpubkey{x_interpolate} is: {int_to_string(interpolated_value)}")

# Interpolate the second missing key, xpubkey4 = f(4)
x_interpolate = 4
interpolated_value = lagrange_interpolation(points, FIELD_SIZE, x_interpolate)
print(f"The recovered xpubkey{x_interpolate} is: {int_to_string(interpolated_value)}")