Last active
August 28, 2023 11:32
-
-
Save RobinLinus/dd0eff8dcf32ab877e38a6b3baf11070 to your computer and use it in GitHub Desktop.
Threshold-encryption for multisig backups. This is a demo to backup the xpubs of a 3-of-5 multisig
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# | |
# 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)}") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment