Threshold Signatures, MPC, and Distributed Key Generation (DKG) TODO

Algorithms · Day 86 / 100 · F. Cryptography & ZK (Day 82-96)

Concept

A (t,n) threshold signature splits a private key into n shares such that any t or more must combine to produce a valid signature — the complete key never exists in one place at any point in time. The underlying idea is Shamir's secret sharing: distributing points on a degree-(t-1) polynomial lets any t points reconstruct the constant term (the secret), while t-1 points reveal nothing at all. DKG is a protocol where participants jointly generate a shared public key and their individual shares purely through interaction, with no trusted dealer, using verifiable secret sharing to filter out cheating participants. BLS signatures thresholdize naturally because keys and signatures simply add together, whereas ECDSA's multiplicative structure demands a far more complex MPC protocol. General MPC is the broader category — computing a joint function's result while each party's input stays hidden — and threshold signing is a special case of it.

The security of a bridge, custody, or oracle signer set ultimately comes down to how the key is split, and a large share of real incidents start from a single leaked key.

Code & Formula

# 임계 서명·MPC·DKG — Shamir 비밀 분산으로 (t, n) 임계 스킴의 핵심(다항식 보간)을 구현한다.
# t개 지분이 모이면 비밀(상수항)을 복원하고, t-1개로는 아무 정보도 얻지 못함을 보인다. (교육용)

import secrets

PRIME = 2**127 - 1  # 큰 소수 체 (토이 규모)

def make_shares(secret_value, t, n):
    """t-1차 다항식을 무작위 계수로 만들고, n개 지분 (x, f(x))을 반환한다."""
    coeffs = [secret_value] + [secrets.randbelow(PRIME) for _ in range(t - 1)]
    def f(x):
        return sum(c * pow(x, i, PRIME) for i, c in enumerate(coeffs)) % PRIME
    return [(x, f(x)) for x in range(1, n + 1)]

def lagrange_interpolate_at_zero(shares):
    """t개 지분 (x_i, y_i) 으로부터 f(0) = 비밀을 라그랑주 보간으로 복원한다."""
    secret = 0
    for i, (xi, yi) in enumerate(shares):
        num, den = 1, 1
        for j, (xj, _) in enumerate(shares):
            if i == j:
                continue
            num = (num * -xj) % PRIME
            den = (den * (xi - xj)) % PRIME
        secret = (secret + yi * num * pow(den, -1, PRIME)) % PRIME
    return secret

SECRET_KEY = 424242424242424242
t, n = 3, 5  # (t,n) 임계: 5명 중 3명이 모여야 서명(복원) 가능

shares = make_shares(SECRET_KEY, t, n)
print(f"generated {n} shares for a ({t},{n}) threshold scheme")
print("shares:", shares)

recovered_with_t = lagrange_interpolate_at_zero(shares[:t])
print(f"recovered with exactly t={t} shares:", recovered_with_t)
print("matches original secret:", recovered_with_t == SECRET_KEY)

# t-1개(부족한 지분)로 복원을 시도하면 완전히 다른(무의미한) 값이 나온다
recovered_with_t_minus_1 = lagrange_interpolate_at_zero(shares[:t - 1] + [(999, 12345)])
print(f"attempting recovery with only t-1 shares gives garbage:", recovered_with_t_minus_1)
print("=> below threshold, the polynomial is underdetermined: any value is equally consistent")

docs/code/algorithms/algorithms-86.py

Exercise

Implement Shamir's secret sharing over a small prime finite field, and confirm experimentally that t shares reconstruct the secret while t-1 shares leave every possible value equally plausible.

Practical Connection

If Verex puts oracle submission or settlement authority behind a threshold signature or multisig instead of a single EOA, one compromised key no longer translates directly into a manipulated market outcome.

Where it lands in Jayverse

• Bridge: put the lock-and-mint relayer's minting authority behind a (t,n) threshold signature instead of one EOA. One compromised relayer key currently means unbacked minting; threshold signing removes that single point.
• Wallet: use BLS's additive threshold structure for session-key/mandate revocation authority once Wallet handles real value. BLS thresholdizes naturally; retrofitting the same onto ECDSA is a much harder MPC protocol, so the signature scheme choice matters before the design is set.
• Devnet: prototype Shamir/DKG on devnet first, using the exercise's small-prime-field implementation, before deciding which of Verex, Bridge or Wallet gets threshold signing first.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

임계 서명·MPC·분산 키 생성(DKG) TODO

Algorithms · Day 86 / 100 · F. 암호학·ZK (Day 82–96)

개념

(t,n) 임계 서명은 비밀키를 n개 지분으로 나눠 t개 이상이 모여야 유효한 서명을 만들 수 있게 하는 방식으로, 어떤 시점에도 완전한 키가 한 곳에 존재하지 않는다. 원리는 Shamir 비밀 분산으로, t-1차 다항식 위의 점들을 배포하면 t개 점으로만 상수항(비밀)을 복원할 수 있고 t-1개로는 아무 정보도 얻지 못한다. DKG는 신뢰할 딜러 없이 참가자들이 상호작용만으로 공동 공개키와 각자의 지분을 만들어내는 프로토콜이며, 검증 가능한 비밀 분산을 써서 부정 참가자를 걸러낸다. BLS 서명은 키와 서명이 그대로 더해지는 성질 덕분에 임계화가 자연스럽지만, ECDSA는 곱셈 구조 때문에 훨씬 복잡한 MPC 프로토콜이 필요하다. 일반적인 MPC는 각자의 입력을 감춘 채 공동 함수의 결과만 계산하는 더 넓은 범주이고 임계 서명은 그 특수 사례로 볼 수 있다.

브리지·커스터디·오라클 서명자 집합의 보안은 결국 키를 어떻게 나눠 갖느냐에 달려 있고, 실제 사고 상당수가 단일 키 유출에서 시작된다.

코드 · 수식

# 임계 서명·MPC·DKG — Shamir 비밀 분산으로 (t, n) 임계 스킴의 핵심(다항식 보간)을 구현한다.
# t개 지분이 모이면 비밀(상수항)을 복원하고, t-1개로는 아무 정보도 얻지 못함을 보인다. (교육용)

import secrets

PRIME = 2**127 - 1  # 큰 소수 체 (토이 규모)

def make_shares(secret_value, t, n):
    """t-1차 다항식을 무작위 계수로 만들고, n개 지분 (x, f(x))을 반환한다."""
    coeffs = [secret_value] + [secrets.randbelow(PRIME) for _ in range(t - 1)]
    def f(x):
        return sum(c * pow(x, i, PRIME) for i, c in enumerate(coeffs)) % PRIME
    return [(x, f(x)) for x in range(1, n + 1)]

def lagrange_interpolate_at_zero(shares):
    """t개 지분 (x_i, y_i) 으로부터 f(0) = 비밀을 라그랑주 보간으로 복원한다."""
    secret = 0
    for i, (xi, yi) in enumerate(shares):
        num, den = 1, 1
        for j, (xj, _) in enumerate(shares):
            if i == j:
                continue
            num = (num * -xj) % PRIME
            den = (den * (xi - xj)) % PRIME
        secret = (secret + yi * num * pow(den, -1, PRIME)) % PRIME
    return secret

SECRET_KEY = 424242424242424242
t, n = 3, 5  # (t,n) 임계: 5명 중 3명이 모여야 서명(복원) 가능

shares = make_shares(SECRET_KEY, t, n)
print(f"generated {n} shares for a ({t},{n}) threshold scheme")
print("shares:", shares)

recovered_with_t = lagrange_interpolate_at_zero(shares[:t])
print(f"recovered with exactly t={t} shares:", recovered_with_t)
print("matches original secret:", recovered_with_t == SECRET_KEY)

# t-1개(부족한 지분)로 복원을 시도하면 완전히 다른(무의미한) 값이 나온다
recovered_with_t_minus_1 = lagrange_interpolate_at_zero(shares[:t - 1] + [(999, 12345)])
print(f"attempting recovery with only t-1 shares gives garbage:", recovered_with_t_minus_1)
print("=> below threshold, the polynomial is underdetermined: any value is equally consistent")

docs/code/algorithms/algorithms-86.py

연습

작은 소수 유한체 위에서 Shamir 비밀 분산을 직접 구현해 t개 지분으로는 복원되고 t-1개로는 모든 값이 동일하게 그럴듯함을 실험으로 확인하라.

실무 · Verex 연결

Verex의 오라클 제출이나 정산 권한을 단일 EOA 대신 임계 서명이나 멀티시그로 두면, 키 하나가 털려도 곧바로 시장 결과 조작으로 이어지지 않는다.

Jayverse에서의 위치

• Bridge: 락앤민트 릴레이어의 민팅 권한을 단일 EOA가 아니라 (t,n) 임계 서명 뒤에 둔다. 지금은 릴레이어 키 하나가 뚫리면 담보 없는 민팅으로 이어지는데, 임계 서명은 이 단일 실패 지점을 제거한다.
• Wallet: Wallet이 실제 자산을 다루게 되면 세션 키/매니데이트 철회 권한에 BLS의 덧셈적 임계 구조를 쓴다. BLS는 자연스럽게 임계화되지만 같은 것을 ECDSA에 이식하려면 훨씬 복잡한 MPC 프로토콜이 필요하므로, 설계를 굳히기 전에 서명 스킴 선택이 중요하다.
• Devnet: Verex, Bridge, Wallet 중 어디에 임계 서명을 먼저 넣을지 정하기 전에, 익서사이즈의 작은 소수체 구현으로 Shamir/DKG를 devnet에서 먼저 프로토타이핑한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.