threshold-wallets.ipynb

Kernel: SageMath 10.0

Connect: Threshold Wallets in Cryptocurrency

Module 12 | Real-World Connections

Split a signing key across multiple devices so no single point of compromise exists.

Introduction

A cryptocurrency wallet is controlled by whoever holds the private signing key. If that key lives on a single device, it is a single point of failure: theft, hardware failure, or a compromised employee means total loss.

Threshold wallets solve this using Shamir secret sharing (Notebook 12a): split the signing key into $n$ shares distributed across different devices or custodians, with a threshold of $t$ required to produce a signature.

For example, a 2-of-3 threshold wallet might distribute shares to:

1. A hardware wallet (cold storage)

2. A mobile phone (hot wallet)

3. A cloud backup (recovery)

Any 2 of these can sign a transaction; losing any 1 does not compromise the funds.

The key insight: the full private key is never reconstructed on any single device. Instead, parties compute partial signatures using their shares and combine them via Lagrange interpolation.

Shamir Sharing of the Signing Key

We start by splitting a "signing key" $sk$ into $(t, n)$ Shamir shares. In real threshold ECDSA/Schnorr, the key is a scalar in the elliptic curve group. Here we work over a small prime field to see the mechanics clearly.

# === Shamir sharing of a signing key ===

p = 1009
F = GF(p)
R.<x> = PolynomialRing(F)

def shamir_share(secret, t, n, field):
    """Split secret into n Shamir shares with threshold t."""
    p_val = field.order()
    coeffs = [field(secret)] + [field(randint(1, p_val - 1)) for _ in range(t - 1)]
    f = PolynomialRing(field, 'z')(coeffs)
    shares = [(field(i), f(field(i))) for i in range(1, n + 1)]
    return shares, f

def lagrange_coeffs(xs, field):
    """Compute Lagrange coefficients for evaluation at x=0."""
    n = len(xs)
    lambdas = []
    for i in range(n):
        num = field(1)
        den = field(1)
        for j in range(n):
            if i != j:
                num *= -xs[j]
                den *= (xs[i] - xs[j])
        lambdas.append(num / den)
    return lambdas

def shamir_reconstruct(shares, field):
    """Reconstruct secret from t or more Shamir shares."""
    xs = [s[0] for s in shares]
    ys = [s[1] for s in shares]
    lambdas = lagrange_coeffs(xs, field)
    return sum(l * y for l, y in zip(lambdas, ys))

# Signing key and threshold
sk = F(777)  # the private signing key
t, n = 2, 3  # 2-of-3 threshold

shares, poly = shamir_share(sk, t, n, F)

print(f"=== Threshold Wallet Setup ===")
print(f"Signing key: sk = {sk}")
print(f"Threshold: ({t},{n}) --- any {t} of {n} devices can sign")
print(f"Polynomial: f(x) = {poly}")
print()
print(f"Key shares distributed:")
devices = ["Hardware wallet", "Mobile phone", "Cloud backup"]
for i, ((xi, yi), dev) in enumerate(zip(shares, devices)):
    print(f"  {dev}: share_{i+1} = ({xi}, {yi})")

Threshold Signing (Simplified)

In a real threshold signature scheme (e.g., threshold Schnorr or GG20 for ECDSA), each party computes a partial signature using their key share, and the partial signatures are combined using Lagrange coefficients.

Here we simulate this with a simplified "signature" $\sigma = sk \cdot H(m)$ where $H(m)$ is a hash of the message. Each party $i$ computes:

$$\sigma_i = \lambda_i \cdot y_i \cdot H(m)$$

where $\lambda_i$ is the Lagrange coefficient for party $i$'s evaluation point. The full signature is $\sigma = \sum_i \sigma_i = sk \cdot H(m)$.

The critical property: no party ever sees the full key $sk$.

# === Threshold signing protocol (simplified) ===

def toy_hash(message, field):
    """Simplified hash: map message to a field element."""
    h = 0
    for c in message:
        h = (h * 31 + ord(c)) % field.order()
    return field(h) if h != 0 else field(1)

def threshold_sign(message, participating_shares, field):
    """Produce a threshold signature from t participating shares.
    
    Each party computes a partial signature; the sum is the full signature.
    """
    h = toy_hash(message, field)
    xs = [s[0] for s in participating_shares]
    ys = [s[1] for s in participating_shares]
    lambdas = lagrange_coeffs(xs, field)
    
    partial_sigs = []
    for i in range(len(participating_shares)):
        sigma_i = lambdas[i] * ys[i] * h
        partial_sigs.append(sigma_i)
    
    full_sig = sum(partial_sigs)
    return full_sig, partial_sigs, h

def verify_sig(message, sigma, sk, field):
    """Verify: sigma == sk * H(m)."""
    h = toy_hash(message, field)
    return sigma == sk * h

# Sign with hardware wallet + mobile phone (parties 1 and 2)
message = "Send 1 BTC to Alice"
signing_subset = [shares[0], shares[1]]  # hardware + mobile

sigma, partials, h = threshold_sign(message, signing_subset, F)

print(f"Message: '{message}'")
print(f"H(m) = {h}")
print()
print(f"Partial signatures:")
for i, (share, ps) in enumerate(zip(signing_subset, partials)):
    dev = devices[int(share[0]) - 1]
    print(f"  {dev}: sigma_{int(share[0])} = {ps}")

print(f"\nCombined signature: sigma = {sigma}")
print(f"Direct signature:   sk * H(m) = {sk * h}")
print(f"Valid? {verify_sig(message, sigma, sk, F)}")
print(f"\nThe full key sk = {sk} was NEVER reconstructed on any device!")

# === Any t-subset can sign ===

print(f"Signing with every possible 2-of-3 subset:")
print()
for combo in Combinations(range(n), t):
    subset = [shares[i] for i in combo]
    devs = [devices[i] for i in combo]
    sigma_test, _, _ = threshold_sign(message, subset, F)
    valid = verify_sig(message, sigma_test, sk, F)
    print(f"  {devs[0]} + {devs[1]}:")
    print(f"    sigma = {sigma_test}, valid? {valid}")

print(f"\nAll {t}-subsets produce the same valid signature.")
print(f"This is the threshold property in action.")

Security: One Compromised Device Is Not Enough

If an attacker steals one device (one share), they cannot sign because they hold fewer than $t$ shares. From a single share, the key $sk = f(0)$ could be any value in $\mathbb{F}_p$ --- the share reveals nothing.

# === Security: one share reveals nothing ===

# Attacker steals the mobile phone (share 2)
stolen_share = shares[1]
print(f"Attacker steals mobile phone: share = {stolen_share}")
print()

# With 1 share and threshold t=2, the key could be anything
# For any guess of sk, there exists a degree-1 polynomial through
# (0, sk_guess) and (stolen_x, stolen_y)
x_stolen, y_stolen = stolen_share
print(f"For every possible key sk, there is a consistent polynomial:")
for sk_guess in [0, 42, 777, 500, 999]:
    sk_g = F(sk_guess)
    # Degree-1 polynomial through (0, sk_g) and (x_stolen, y_stolen)
    slope = (y_stolen - sk_g) / x_stolen
    f_guess = sk_g + slope * x  # as polynomial in x
    check = f_guess(x_stolen) == y_stolen
    print(f"  sk = {sk_guess}: f(x) = {f_guess}  (passes through stolen share? {check})")

print(f"\nAll key values are equally likely. The attacker learns nothing.")
print(f"They would need to steal {t} devices to reconstruct the key.")

Real-World Threshold Wallet Deployments

Company	Protocol	Threshold	Use Case
Fireblocks	MPC-CMP (GG20 variant)	Configurable $(t, n)$	Institutional custody
ZenGo	2-party threshold Schnorr	$(2, 2)$	Consumer wallet
BitGo	Multi-sig + threshold	$(2, 3)$	Exchange custody
Coinbase	Threshold ECDSA	$(t, n)$	Institutional clients

The shift from traditional multi-sig (which requires on-chain support) to threshold signatures (which look like regular signatures on-chain) is one of the biggest practical applications of MPC.

Concept Map: Module 12 $\to$ Threshold Wallets

Module 12 Concept	Threshold Wallet Application
Shamir secret sharing	Splitting the signing key into $(t, n)$ shares
Lagrange interpolation	Combining partial signatures into a full signature
$(t, n)$ threshold property	$m$-of-$n$ signing policy (e.g., 2-of-3)
Information-theoretic security	One stolen share reveals nothing about the key
Feldman VSS	Verifying share consistency during key generation
Beaver triples / SPDZ	Multiplications needed in threshold ECDSA

Every building block from this module has a direct role in real threshold wallet implementations.

# === Exercise: 3-of-5 threshold wallet ===

# An institutional setup with 5 custodians, any 3 can sign
sk_inst = F(314)
t_inst, n_inst = 3, 5
custodians = ["CEO", "CFO", "CTO", "Legal", "Backup HSM"]

shares_inst, poly_inst = shamir_share(sk_inst, t_inst, n_inst, F)

print(f"=== 3-of-5 Institutional Threshold Wallet ===")
print(f"Signing key: sk = {sk_inst}")
print()
for (xi, yi), name in zip(shares_inst, custodians):
    print(f"  {name}: share = ({xi}, {yi})")

# Sign with CEO + CTO + Backup HSM
msg_inst = "Approve 10M USD withdrawal"
signing_team = [shares_inst[0], shares_inst[2], shares_inst[4]]
sigma_inst, _, _ = threshold_sign(msg_inst, signing_team, F)
valid_inst = verify_sig(msg_inst, sigma_inst, sk_inst, F)

print(f"\nSigning team: CEO + CTO + Backup HSM")
print(f"Message: '{msg_inst}'")
print(f"Signature valid? {valid_inst}")

# Verify all 3-subsets work
all_valid = True
count = 0
for combo in combinations(range(n_inst), t_inst):
    subset = [shares_inst[i] for i in combo]
    s, _, _ = threshold_sign(msg_inst, subset, F)
    if not verify_sig(msg_inst, s, sk_inst, F):
        all_valid = False
    count += 1

print(f"All {count} possible 3-of-5 subsets produce valid signatures? {all_valid}")

Summary

Concept	Key idea
Key splitting	The signing key is divided into $(t, n)$ Shamir shares across multiple devices
Partial signatures	Each device independently computes a signature fragment using its share
Lagrange combination	Partial signatures are combined into the full signature via interpolation
No key reconstruction	The full key never exists on any single device at any point
Theft resistance	Losing up to $t - 1$ devices reveals nothing about the key (information-theoretic security)
Availability	Losing up to $n - t$ devices still leaves enough shares to sign

This is one of the most successful real-world deployments of MPC, protecting billions of dollars in cryptocurrency across institutional and consumer wallets.

---

Back to Module 12: Multi-Party Computation