Threshold Signatures

1Regular signature: (r, s)
2Threshold signature: (r, s)
3→ Indistinguishable!

 1from hashlib import sha256
 2import secrets
 3
 4class DistributedKeyGeneration:
 5    def __init__(self, threshold, num_parties, prime, generator):
 6        self.threshold = threshold
 7        self.num_parties = num_parties
 8        self.prime = prime
 9        self.G = generator
10    
11    def generate_key_shares(self):
12        """
13        Simulate DKG for threshold ECDSA
14        In practice, this would involve secure multi-party computation
15        """
16        # Each party generates a secret and shares it using Shamir
17        party_secrets = []
18        all_shares = [[] for _ in range(self.num_parties)]
19        
20        for party_id in range(self.num_parties):
21            # Generate secret for this party
22            secret = secrets.randbelow(self.prime)
23            party_secrets.append(secret)
24            
25            # Generate shares of this secret
26            shares = self._shamir_share(secret, self.threshold, self.num_parties)
27            
28            # Distribute shares
29            for i, share in enumerate(shares):
30                all_shares[i].append(share)
31        
32        # Each party combines received shares to get their key share
33        key_shares = []
34        for party_shares in all_shares:
35            key_share = sum(share[1] for share in party_shares) % self.prime
36            key_shares.append(key_share)
37        
38        # Compute public key (sum of all secrets · G)
39        total_secret = sum(party_secrets) % self.prime
40        public_key = self._scalar_mult(self.G, total_secret)
41        
42        return key_shares, public_key
43    
44    def _shamir_share(self, secret, threshold, num_shares):
45        """Generate Shamir shares"""
46        # Generate random polynomial coefficients
47        coeffs = [secret] + [secrets.randbelow(self.prime) 
48                             for _ in range(threshold - 1)]
49        
50        # Evaluate polynomial at different points
51        shares = []
52        for x in range(1, num_shares + 1):
53            y = sum(coef * pow(x, i, self.prime) 
54                   for i, coef in enumerate(coeffs)) % self.prime
55            shares.append((x, y))
56        
57        return shares
58    
59    def _scalar_mult(self, point, scalar):
60        """Scalar multiplication on elliptic curve (simplified)"""
61        # In practice, use proper EC library
62        return (point[0] * scalar, point[1] * scalar)

 1class ThresholdECDSA:
 2    def __init__(self, curve_order, generator):
 3        self.n = curve_order
 4        self.G = generator
 5    
 6    def sign_partial(self, message, key_share, nonce_share, R, r):
 7        """
 8        Generate partial signature
 9        
10        Args:
11            message: Message to sign
12            key_share: This party's share of private key
13            nonce_share: This party's share of nonce k
14            R: Combined nonce point
15            r: x-coordinate of R
16        """
17        # Hash message
18        h = int.from_bytes(sha256(message).digest(), 'big') % self.n
19        
20        # Compute k^(-1) for this share
21        k_inv = self._mod_inverse(nonce_share, self.n)
22        
23        # Partial signature: s_i = k_i^(-1) * (H(m) + r * x_i)
24        s_partial = (k_inv * (h + r * key_share)) % self.n
25        
26        return s_partial
27    
28    def combine_signatures(self, partial_sigs):
29        """Combine partial signatures into final signature"""
30        s = sum(partial_sigs) % self.n
31        return s
32    
33    def verify(self, message, signature, public_key):
34        """Verify threshold signature (same as regular ECDSA)"""
35        r, s = signature
36        h = int.from_bytes(sha256(message).digest(), 'big') % self.n
37        
38        # Compute u1 = H(m) * s^(-1), u2 = r * s^(-1)
39        s_inv = self._mod_inverse(s, self.n)
40        u1 = (h * s_inv) % self.n
41        u2 = (r * s_inv) % self.n
42        
43        # Compute point: u1*G + u2*P
44        point = self._add_points(
45            self._scalar_mult(self.G, u1),
46            self._scalar_mult(public_key, u2)
47        )
48        
49        # Verify: x-coordinate of point equals r
50        return point[0] % self.n == r
51    
52    def _mod_inverse(self, a, m):
53        """Modular multiplicative inverse"""
54        def extended_gcd(a, b):
55            if a == 0:
56                return b, 0, 1
57            gcd, x1, y1 = extended_gcd(b % a, a)
58            return gcd, y1 - (b // a) * x1, x1
59        
60        _, x, _ = extended_gcd(a % m, m)
61        return (x % m + m) % m
62    
63    def _scalar_mult(self, point, scalar):
64        """Scalar multiplication (use proper EC library in production)"""
65        pass
66    
67    def _add_points(self, p1, p2):
68        """Point addition (use proper EC library in production)"""
69        pass

 1class ThresholdSchnorr:
 2    def __init__(self, curve_order, generator):
 3        self.n = curve_order
 4        self.G = generator
 5    
 6    def sign_partial(self, message, key_share, nonce_share, R_agg):
 7        """
 8        Generate partial Schnorr signature
 9        
10        Schnorr is linear: s = k + H(R,P,m)·x
11        Threshold: s_i = k_i + H(R,P,m)·x_i
12        """
13        # Compute challenge
14        challenge = self._compute_challenge(R_agg, message)
15        
16        # Partial signature: s_i = k_i + c * x_i
17        s_partial = (nonce_share + challenge * key_share) % self.n
18        
19        return s_partial
20    
21    def combine_signatures(self, R_agg, partial_sigs):
22        """Combine partial signatures"""
23        s = sum(partial_sigs) % self.n
24        return (R_agg, s)
25    
26    def verify(self, message, signature, public_key):
27        """Verify Schnorr signature"""
28        R, s = signature
29        c = self._compute_challenge(R, message)
30        
31        # Verify: s·G = R + c·P
32        left = self._scalar_mult(self.G, s)
33        right = self._add_points(R, self._scalar_mult(public_key, c))
34        
35        return left == right
36    
37    def _compute_challenge(self, R, message):
38        """Compute Fiat-Shamir challenge"""
39        data = R.to_bytes() + message
40        return int.from_bytes(sha256(data).digest(), 'big') % self.n

 1class ThresholdBLS:
 2    def __init__(self, pairing_group):
 3        self.group = pairing_group
 4    
 5    def sign_partial(self, message, key_share):
 6        """
 7        Generate partial BLS signature
 8        
 9        BLS signature: σ = H(m)^x
10        Partial: σ_i = H(m)^(x_i)
11        """
12        # Hash message to curve point
13        H_m = self._hash_to_curve(message)
14        
15        # Partial signature: σ_i = H(m)^(x_i)
16        sigma_partial = H_m ** key_share
17        
18        return sigma_partial
19    
20    def combine_signatures(self, partial_sigs, lagrange_coeffs):
21        """
22        Combine partial signatures using Lagrange interpolation
23        
24        σ = ∏ σ_i^(λ_i)
25        where λ_i are Lagrange coefficients
26        """
27        sigma = self.group.identity()
28        
29        for sigma_i, lambda_i in zip(partial_sigs, lagrange_coeffs):
30            sigma = sigma * (sigma_i ** lambda_i)
31        
32        return sigma
33    
34    def verify(self, message, signature, public_key):
35        """
36        Verify BLS signature using pairing
37        
38        Check: e(σ, g) = e(H(m), P)
39        """
40        H_m = self._hash_to_curve(message)
41        g = self.group.generator()
42        
43        # Pairing check
44        left = self.group.pair(signature, g)
45        right = self.group.pair(H_m, public_key)
46        
47        return left == right
48    
49    def _hash_to_curve(self, message):
50        """Hash message to curve point (use proper hash-to-curve)"""
51        pass

 1# ✅ GOOD: Deterministic nonce (RFC 6979)
 2def generate_nonce_deterministic(private_key, message):
 3    """Generate deterministic nonce (simplified RFC 6979)"""
 4    h = sha256(private_key + message).digest()
 5    k = int.from_bytes(h, 'big')
 6    return k
 7
 8# ❌ BAD: Random nonce (can be manipulated in MPC)
 9def generate_nonce_random():
10    return secrets.randbelow(curve_order)

 1✅ DO:
 2- Use authenticated channels
 3- Encrypt all communications
 4- Verify party identities
 5- Log all protocol messages
 6
 7❌ DON'T:
 8- Send shares in plaintext
 9- Skip authentication
10- Ignore protocol deviations

1Problem: Single private key is single point of failure
2
3Solution: (2, 3) threshold signature
4- 3 key shares distributed
5- Any 2 can sign transactions
6- Private key never exists!
7- On-chain: looks like regular transaction

1Company code signing key:
2- (3, 5) threshold among executives
3- No single person can sign
4- Quorum required for releases
5- Key never assembled

1Oracle network:
2- (t, n) threshold signature
3- t nodes must agree on data
4- Single signature on-chain
5- Gas efficient

1Rollup validators:
2- (2/3, n) threshold
3- 2/3 must sign state updates
4- Single signature to L1
5- Efficient verification

1Problem: Need t parties online simultaneously
2
3Solutions:
4- Preprocessing: Generate nonces offline
5- Async protocols: Parties contribute when available
6- Backup shares: Rotate participants

 1class ThresholdSigningSession:
 2    def __init__(self, session_id, threshold, participants):
 3        self.session_id = session_id
 4        self.threshold = threshold
 5        self.participants = participants
 6        self.round = 0
 7        self.commitments = {}
 8        self.shares = {}
 9        self.partial_sigs = {}
10    
11    def advance_round(self):
12        """Move to next round after validation"""
13        if len(self.get_current_round_data()) >= self.threshold:
14            self.round += 1
15            return True
16        return False
17    
18    def get_current_round_data(self):
19        """Get data for current round"""
20        if self.round == 1:
21            return self.commitments
22        elif self.round == 2:
23            return self.shares
24        elif self.round == 3:
25            return self.partial_sigs

1✅ Use trusted DKG ceremony or secure MPC
2✅ Verify all shares before accepting
3✅ Test signing with small amounts first
4✅ Document threshold and participants
5✅ Establish communication protocols
6✅ Plan for participant rotation

1✅ Authenticate all participants
2✅ Encrypt all communications
3✅ Validate each round before proceeding
4✅ Log all protocol messages
5✅ Monitor for malicious behavior
6✅ Have abort procedures

1✅ Plan for participant unavailability
2✅ Have backup communication channels
3✅ Document recovery procedures
4✅ Test recovery regularly

1- tss-lib (Binance): Go implementation
2- multi-party-ecdsa (ZenGo): Rust implementation
3- threshold-crypto: Rust BLS implementation

 1import (
 2    "github.com/binance-chain/tss-lib/ecdsa/keygen"
 3    "github.com/binance-chain/tss-lib/ecdsa/signing"
 4)
 5
 6// Key generation
 7parties := []*tss.PartyID{...}
 8params := tss.NewParameters(curve, ctx, partyID, parties, threshold, len(parties))
 9outCh := make(chan tss.Message, len(parties))
10endCh := make(chan keygen.LocalPartySaveData, 1)
11
12party := keygen.NewLocalParty(params, outCh, endCh)
13go func() {
14    if err := party.Start(); err != nil {
15        // Handle error
16    }
17}()
18
19// Signing
20msg := []byte("message to sign")
21signingParams := tss.NewParameters(curve, ctx, partyID, parties, threshold, len(parties))
22signingParty := signing.NewLocalParty(msg, signingParams, key, outCh, endCh)