Verifiable Secret Sharing for Coordinate Integrity

from __future__ import annotations

import secrets
from dataclasses import dataclass
from typing import Sequence

# A 2048-bit safe prime would be used in production; this smaller one keeps the
# example runnable while preserving the structure.
P = (1 << 521) - 1
Q = (P - 1) // 2
G = 4                       # a generator of the order-Q subgroup for this prime


class ShareRejected(RuntimeError):
    """A share failed verification against the published commitments."""


@dataclass(frozen=True)
class VSSDealing:
    """What the dealer publishes: shares (privately) and commitments (publicly)."""

    shares: tuple[tuple[int, int], ...]
    commitments: tuple[int, ...]
    threshold: int


def deal(secret_scaled: int, *, threshold: int, parties: int) -> VSSDealing:
    """Split a scaled coordinate and publish coefficient commitments.

    The commitments are g^a_i mod p. They are public and reveal nothing about the
    coefficients under the discrete-log assumption, but they bind the dealer: any
    share inconsistent with them is detectable by its holder alone.
    """
    if not 1 < threshold <= parties:
        raise ValueError("need 1 < threshold <= parties")
    coeffs = [secret_scaled % Q] + [secrets.randbelow(Q) for _ in range(threshold - 1)]
    shares = []
    for x in range(1, parties + 1):
        y = 0
        for c in reversed(coeffs):
            y = (y * x + c) % Q
        shares.append((x, y))
    commitments = tuple(pow(G, c, P) for c in coeffs)
    return VSSDealing(tuple(shares), commitments, threshold)


def verify_share(share: tuple[int, int], commitments: Sequence[int]) -> bool:
    """Check g^y == prod(C_i ^ (x^i)) — the share lies on the committed polynomial.

    Each party runs this on its OWN share, with no interaction and no knowledge of
    any other share. That is what makes VSS practical: detection is local.
    """
    x, y = share
    lhs = pow(G, y, P)
    rhs = 1
    for i, c in enumerate(commitments):
        rhs = (rhs * pow(c, pow(x, i), P)) % P
    return lhs == rhs


def reconstruct(shares: Sequence[tuple[int, int]], commitments: Sequence[int],
                *, threshold: int) -> int:
    """Verify every share, then interpolate. Refuses to use an unverified share.

    Verifying first is the whole point: interpolating over a corrupted share yields
    a valid-looking coordinate with no indication that anything went wrong.
    """
    good = []
    bad = []
    for share in shares:
        (good if verify_share(share, commitments) else bad).append(share)
    if bad:
        raise ShareRejected(
            f"{len(bad)} share(s) failed verification: parties {[x for x, _ in bad]} — "
            "reconstruction would have returned a plausible wrong coordinate"
        )
    if len(good) < threshold:
        raise ShareRejected(f"only {len(good)} valid shares, threshold is {threshold}")

    total = 0
    picked = good[:threshold]
    for i, (xi, yi) in enumerate(picked):
        num, den = 1, 1
        for j, (xj, _) in enumerate(picked):
            if i != j:
                num = (num * (-xj)) % Q
                den = (den * (xi - xj)) % Q
        total = (total + yi * num * pow(den, Q - 2, Q)) % Q
    return total

def _validate() -> None:
    lat_scaled = 51_507_351          # 51.507351 deg at 1e6 fixed point

    dealing = deal(lat_scaled, threshold=3, parties=5)

    # 1. Every honestly dealt share verifies.
    assert all(verify_share(s, dealing.commitments) for s in dealing.shares)

    # 2. Reconstruction from any t verified shares returns the exact coordinate.
    assert reconstruct(dealing.shares[:3], dealing.commitments, threshold=3) == lat_scaled
    assert reconstruct(dealing.shares[2:5], dealing.commitments, threshold=3) == lat_scaled

    # 3. A tampered share fails verification — locally, with no interaction.
    x, y = dealing.shares[1]
    tampered = (x, (y + 12_345) % Q)
    assert not verify_share(tampered, dealing.commitments)

    # 4. Reconstruction refuses to proceed with a bad share, rather than returning
    #    a plausible wrong coordinate — the failure plain Shamir cannot detect.
    mixed = [dealing.shares[0], tampered, dealing.shares[2]]
    try:
        reconstruct(mixed, dealing.commitments, threshold=3)
    except ShareRejected as exc:
        assert "failed verification" in str(exc)
    else:
        raise AssertionError("a corrupted share must be rejected before interpolation")

    # 5. Demonstrate what plain Shamir would have done: interpolating the tampered
    #    set yields a well-formed but WRONG value.
    def naive_interpolate(shares):
        total = 0
        for i, (xi, yi) in enumerate(shares):
            num, den = 1, 1
            for j, (xj, _) in enumerate(shares):
                if i != j:
                    num = (num * (-xj)) % Q
                    den = (den * (xi - xj)) % Q
            total = (total + yi * num * pow(den, Q - 2, Q)) % Q
        return total

    wrong = naive_interpolate(mixed)
    assert wrong != lat_scaled and 0 <= wrong < Q

    # 6. Fewer than t valid shares must fail loudly.
    try:
        reconstruct(dealing.shares[:2], dealing.commitments, threshold=3)
    except ShareRejected:
        pass
    else:
        raise AssertionError("insufficient shares must raise")

    print("verifiable secret sharing: all assertions passed")


_validate()