Secret Sharing

┌─────────────────────────────────────────────────────────────────┐
│              Shamir's Secret Sharing                            │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Secret: S                                                      │
│  Threshold: t (minimum shares to reconstruct)                   │
│  Shares: n (total shares)                                       │
│                                                                 │
│  Polynomial: f(x) = S + a₁x + a₂x² + ... + aₜ₋₁xᵗ⁻¹ (mod p)     │
│                                                                 │
│  Where:                                                         │
│  • S is the constant term (the secret)                          │
│  • a₁, a₂, ..., aₜ₋₁ are random coefficients                    │
│  • p is a large prime                                           │
│                                                                 │
│  Shares: (1, f(1)), (2, f(2)), ..., (n, f(n))                   │
│                                                                 │
│  Reconstruction: Lagrange interpolation at x=0                  │
│                                                                 │
│             n                                                   │
│  S = f(0) = Σ  yᵢ × Lᵢ(0)                                       │
│            i=1                                                  │
│                                                                 │
│  Where Lᵢ(x) = ∏(j≠i) (x - xⱼ)/(xᵢ - xⱼ)                        │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

import { randomBytes } from "crypto";

// Finite field arithmetic over a prime
const PRIME = BigInt(
  "52435875175126190479447740508185965837690552500527637822603658699938581184513",
); // Baby JubJub prime

function mod(a: bigint, p: bigint = PRIME): bigint {
  return ((a % p) + p) % p;
}

function modInverse(a: bigint, p: bigint = PRIME): bigint {
  let [old_r, r] = [p, mod(a, p)];
  let [old_t, t] = [0n, 1n];

  while (r !== 0n) {
    const quotient = old_r / r;
    [old_r, r] = [r, old_r - quotient * r];
    [old_t, t] = [t, old_t - quotient * t];
  }

  return mod(old_t, p);
}

interface Share {
  x: bigint;
  y: bigint;
}

export class ShamirSecretSharing {
  private prime: bigint;

  constructor(prime: bigint = PRIME) {
    this.prime = prime;
  }

  // Generate random coefficients for polynomial
  private generateCoefficients(secret: bigint, threshold: number): bigint[] {
    const coefficients: bigint[] = [secret];

    for (let i = 1; i < threshold; i++) {
      const randomValue = BigInt("0x" + randomBytes(32).toString("hex"));
      coefficients.push(mod(randomValue, this.prime));
    }

    return coefficients;
  }

  // Evaluate polynomial at x
  private evaluatePolynomial(coefficients: bigint[], x: bigint): bigint {
    let result = 0n;
    let power = 1n;

    for (const coef of coefficients) {
      result = mod(result + mod(coef * power, this.prime), this.prime);
      power = mod(power * x, this.prime);
    }

    return result;
  }

  // Split secret into shares
  split(secret: bigint, threshold: number, numShares: number): Share[] {
    if (threshold > numShares) {
      throw new Error("Threshold cannot exceed number of shares");
    }

    if (threshold < 2) {
      throw new Error("Threshold must be at least 2");
    }

    const coefficients = this.generateCoefficients(secret, threshold);
    const shares: Share[] = [];

    for (let i = 1; i <= numShares; i++) {
      const x = BigInt(i);
      const y = this.evaluatePolynomial(coefficients, x);
      shares.push({ x, y });
    }

    return shares;
  }

  // Lagrange basis polynomial evaluated at 0
  private lagrangeBasis(shares: Share[], i: number): bigint {
    let numerator = 1n;
    let denominator = 1n;
    const xi = shares[i].x;

    for (let j = 0; j < shares.length; j++) {
      if (i !== j) {
        const xj = shares[j].x;
        numerator = mod(numerator * mod(-xj, this.prime), this.prime);
        denominator = mod(denominator * mod(xi - xj, this.prime), this.prime);
      }
    }

    return mod(numerator * modInverse(denominator, this.prime), this.prime);
  }

  // Reconstruct secret from shares
  reconstruct(shares: Share[]): bigint {
    if (shares.length < 2) {
      throw new Error("Need at least 2 shares");
    }

    let secret = 0n;

    for (let i = 0; i < shares.length; i++) {
      const basis = this.lagrangeBasis(shares, i);
      secret = mod(secret + mod(shares[i].y * basis, this.prime), this.prime);
    }

    return secret;
  }

  // Refresh shares without revealing secret
  refreshShares(shares: Share[], threshold: number): Share[] {
    // Generate a polynomial with zero constant term
    const zeroSecret = 0n;
    const refreshPoly = this.generateCoefficients(zeroSecret, threshold);

    // Add refresh values to existing shares
    return shares.map((share) => ({
      x: share.x,
      y: mod(
        share.y + this.evaluatePolynomial(refreshPoly, share.x),
        this.prime,
      ),
    }));
  }
}

// Serialize/deserialize shares
export function serializeShare(share: Share): string {
  return JSON.stringify({
    x: share.x.toString(),
    y: share.y.toString(),
  });
}

export function deserializeShare(data: string): Share {
  const parsed = JSON.parse(data);
  return {
    x: BigInt(parsed.x),
    y: BigInt(parsed.y),
  };
}

import { Keypair, PublicKey } from "@solana/web3.js";
import {
  ShamirSecretSharing,
  Share,
  serializeShare,
  deserializeShare,
} from "./sss";

export class KeySplitter {
  private sss: ShamirSecretSharing;

  constructor() {
    this.sss = new ShamirSecretSharing();
  }

  // Split a Solana keypair
  splitKeypair(
    keypair: Keypair,
    threshold: number,
    numShares: number,
  ): {
    publicKey: PublicKey;
    shares: string[];
  } {
    // Convert secret key to bigint
    const secretKeyBytes = keypair.secretKey.slice(0, 32); // First 32 bytes
    const secretBigInt = BigInt(
      "0x" + Buffer.from(secretKeyBytes).toString("hex"),
    );

    // Split the secret
    const shares = this.sss.split(secretBigInt, threshold, numShares);

    return {
      publicKey: keypair.publicKey,
      shares: shares.map(serializeShare),
    };
  }

  // Reconstruct keypair from shares
  reconstructKeypair(shares: string[]): Keypair {
    const parsedShares = shares.map(deserializeShare);

    // Reconstruct the secret
    const secretBigInt = this.sss.reconstruct(parsedShares);

    // Convert back to bytes
    const secretHex = secretBigInt.toString(16).padStart(64, "0");
    const secretKeyBytes = Buffer.from(secretHex, "hex");

    // Recreate keypair (Solana uses 64-byte secret key)
    return Keypair.fromSeed(secretKeyBytes);
  }

  // Verify shares without reconstruction
  verifyShareConsistency(shares: string[], threshold: number): boolean {
    if (shares.length < threshold) {
      return false;
    }

    const parsedShares = shares.map(deserializeShare);

    // Take threshold number of different subsets and verify they reconstruct the same value
    const firstSubset = parsedShares.slice(0, threshold);
    const firstValue = this.sss.reconstruct(firstSubset);

    // Check with a different subset
    for (let i = threshold; i < parsedShares.length; i++) {
      const subset = [...parsedShares.slice(0, threshold - 1), parsedShares[i]];
      const value = this.sss.reconstruct(subset);

      if (value !== firstValue) {
        return false;
      }
    }

    return true;
  }
}

import { createHash, randomBytes } from "crypto";

interface VSSShare {
  x: bigint;
  y: bigint;
}

interface VSSCommitment {
  commitments: bigint[];
}

// Pedersen commitments for VSS
const G = BigInt(
  "5299619240641551281634865583518297030282874472190772894086521144482721001553",
);
const H = BigInt(
  "16950150798460657717958625567821834550301663161624707787222815936182638968203",
);
const ORDER = BigInt(
  "21888242871839275222246405745257275088548364400416034343698204186575808495617",
);

function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
  let result = 1n;
  base = base % mod;

  while (exp > 0n) {
    if (exp % 2n === 1n) {
      result = (result * base) % mod;
    }
    exp = exp / 2n;
    base = (base * base) % mod;
  }

  return result;
}

export class VerifiableSecretSharing {
  // Feldman VSS: Dealer creates commitments to polynomial coefficients
  static createSharesWithCommitments(
    secret: bigint,
    threshold: number,
    numShares: number,
  ): {
    shares: VSSShare[];
    commitments: bigint[];
  } {
    // Generate random coefficients
    const coefficients: bigint[] = [secret];
    for (let i = 1; i < threshold; i++) {
      const randomValue = BigInt("0x" + randomBytes(32).toString("hex"));
      coefficients.push(randomValue % ORDER);
    }

    // Create commitments: C_i = g^{a_i}
    const commitments = coefficients.map((coef) => modPow(G, coef, ORDER));

    // Create shares
    const shares: VSSShare[] = [];
    for (let i = 1; i <= numShares; i++) {
      const x = BigInt(i);
      let y = 0n;
      let power = 1n;

      for (const coef of coefficients) {
        y = (y + coef * power) % ORDER;
        power = (power * x) % ORDER;
      }

      shares.push({ x, y });
    }

    return { shares, commitments };
  }

  // Verify a share against commitments
  static verifyShare(share: VSSShare, commitments: bigint[]): boolean {
    // Compute g^{share.y}
    const lhs = modPow(G, share.y, ORDER);

    // Compute ∏ C_j^{x^j}
    let rhs = 1n;
    let power = 1n;

    for (const commitment of commitments) {
      rhs = (rhs * modPow(commitment, power, ORDER)) % ORDER;
      power = (power * share.x) % ORDER;
    }

    return lhs === rhs;
  }

  // Reconstruct with verification
  static reconstructWithVerification(
    shares: VSSShare[],
    commitments: bigint[],
  ): bigint | null {
    // Verify all shares first
    for (const share of shares) {
      if (!this.verifyShare(share, commitments)) {
        console.error(`Share ${share.x} failed verification`);
        return null;
      }
    }

    // Standard Lagrange reconstruction
    let secret = 0n;

    for (let i = 0; i < shares.length; i++) {
      let basis = 1n;

      for (let j = 0; j < shares.length; j++) {
        if (i !== j) {
          const num = (ORDER - shares[j].x) % ORDER;
          const den = (shares[i].x - shares[j].x + ORDER) % ORDER;
          const denInv = modPow(den, ORDER - 2n, ORDER); // Fermat's little theorem
          basis = (basis * num * denInv) % ORDER;
        }
      }

      secret = (secret + shares[i].y * basis) % ORDER;
    }

    return secret;
  }
}

interface DKGParticipant {
  id: number;
  secretPoly: bigint[];
  commitments: bigint[];
  receivedShares: Map<number, bigint>;
}

export class DKGProtocol {
  private participants: Map<number, DKGParticipant>;
  private threshold: number;
  private numParticipants: number;

  constructor(threshold: number, numParticipants: number) {
    this.threshold = threshold;
    this.numParticipants = numParticipants;
    this.participants = new Map();
  }

  // Round 1: Each participant generates polynomial and broadcasts commitments
  round1(participantId: number): {
    commitments: bigint[];
    sharesToSend: Map<number, bigint>;
  } {
    // Generate random polynomial
    const secretPoly: bigint[] = [];
    for (let i = 0; i < this.threshold; i++) {
      const randomValue = BigInt("0x" + randomBytes(32).toString("hex"));
      secretPoly.push(randomValue % ORDER);
    }

    // Create commitments
    const commitments = secretPoly.map((coef) => modPow(G, coef, ORDER));

    // Calculate shares for each participant
    const sharesToSend = new Map<number, bigint>();
    for (let j = 1; j <= this.numParticipants; j++) {
      let share = 0n;
      let power = 1n;
      const x = BigInt(j);

      for (const coef of secretPoly) {
        share = (share + coef * power) % ORDER;
        power = (power * x) % ORDER;
      }

      sharesToSend.set(j, share);
    }

    // Store participant state
    this.participants.set(participantId, {
      id: participantId,
      secretPoly,
      commitments,
      receivedShares: new Map(),
    });

    return { commitments, sharesToSend };
  }

  // Round 2: Participants receive and verify shares
  round2(
    participantId: number,
    fromId: number,
    share: bigint,
    commitments: bigint[],
  ): boolean {
    const participant = this.participants.get(participantId);
    if (!participant) throw new Error("Participant not initialized");

    // Verify share
    const x = BigInt(participantId);
    const lhs = modPow(G, share, ORDER);

    let rhs = 1n;
    let power = 1n;
    for (const commitment of commitments) {
      rhs = (rhs * modPow(commitment, power, ORDER)) % ORDER;
      power = (power * x) % ORDER;
    }

    if (lhs !== rhs) {
      return false;
    }

    participant.receivedShares.set(fromId, share);
    return true;
  }

  // Round 3: Combine shares to get final key share
  round3(participantId: number): {
    finalShare: bigint;
    publicKey: bigint;
  } {
    const participant = this.participants.get(participantId);
    if (!participant) throw new Error("Participant not initialized");

    // Sum all received shares including own
    let finalShare = participant.secretPoly[0]; // Own secret
    for (const [, share] of participant.receivedShares) {
      finalShare = (finalShare + share) % ORDER;
    }

    // Public key is the combined first commitment from all participants
    // (In practice, this would be computed from all participants' commitments)
    const publicKey = modPow(G, finalShare, ORDER);

    return { finalShare, publicKey };
  }
}

// Split a Solana keypair
const splitter = new KeySplitter();
const keypair = Keypair.generate();

const { publicKey, shares } = splitter.splitKeypair(keypair, 3, 5);

console.log("Public Key:", publicKey.toBase58());
console.log("Shares:", shares);

// Distribute shares to 5 parties...

// Reconstruct with any 3 shares
const reconstructedKeypair = splitter.reconstructKeypair([
  shares[0],
  shares[2],
  shares[4],
]);

console.log("Reconstructed:", reconstructedKeypair.publicKey.equals(publicKey)); // true