FROST.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Welcome to the FROST Notebook\n",
    "We'll be taking a look at FROST internals through implementing FROST.\n",
    "FROST (Flexible Round-Optimized Schnorr Threshold) is a cryptographic protocol that allows multiple parties to collaboratively sign a message while maintaining security against various types of attacks. It utilizes threshold cryptography, where a signature can be generated only when a threshold number of parties cooperate.\n",
    "We'll divide the discussion of FROST into three steps: key generation, signing, and verification.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Lets set up our global constants \n",
    "# Prime order of curve\n",
    "P = 2**256 - 2**32 - 977\n",
    "# The order of the base point (also known as the generator point G),\n",
    "# which is the number of distinct points on the curve that can be generated by\n",
    "# repeatedly adding the base point to itself.\n",
    "Q = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\n",
    "# Generator point Cordinates\n",
    "G_x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798\n",
    "G_y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8\n",
    "# We'll use these cordinates to set up ECC point in a later step\n",
    "# string context - protect against replay attacks\n",
    "CONTEXT = b'FROST-BIP340'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define ECC point class\n",
    "class Point:\n",
    "        \"\"\"Class representing an elliptic curve point.\"\"\"\n",
    "        def __init__(self, x=float('inf'), y=float('inf')):\n",
    "            self.x = x\n",
    "            self.y = y\n",
    "\n",
    "        @classmethod\n",
    "        def secret_deserialize(self, hex_public_key):\n",
    "            hex_bytes = bytes.fromhex(hex_public_key)\n",
    "            is_even = hex_bytes[0] == 2\n",
    "            x_bytes = hex_bytes[1:]\n",
    "            x = int.from_bytes(x_bytes, 'big')\n",
    "            y_squared = (pow(x, 3, P) + 7) % P\n",
    "            y = pow(y_squared, (P + 1) // 4, P)\n",
    "\n",
    "            if y % 2 == 0:\n",
    "                even_y = y\n",
    "                odd_y = (P - y) % P\n",
    "            else:\n",
    "                even_y = (P - y) % P\n",
    "                odd_y = y\n",
    "            y = even_y if is_even else odd_y\n",
    "\n",
    "            return self(x, y)\n",
    "\n",
    "        def secret_serialize(self):\n",
    "            # Return compressed key\n",
    "            prefix = b'\\x02' if self.y % 2 == 0 else b'\\x03'\n",
    "\n",
    "            return prefix + self.x.to_bytes(32, 'big')\n",
    "\n",
    "        @classmethod\n",
    "        def xonly_deserialize(self, hex_public_key):\n",
    "            hex_bytes = bytes.fromhex(hex_public_key)\n",
    "            x = int.from_bytes(hex_bytes, 'big')\n",
    "            y_squared = (pow(x, 3, P) + 7) % P\n",
    "            y = pow(y_squared, (P + 1) // 4, P)\n",
    "\n",
    "            if y % 2 != 0:\n",
    "                y = (P - y) % P\n",
    "\n",
    "            return self(x, y)\n",
    "\n",
    "        def xonly_serialize(self):\n",
    "            return self.x.to_bytes(32, 'big')\n",
    "\n",
    "        # point at infinity\n",
    "        def is_zero(self):\n",
    "            return self.x == float('inf') or self.y == float('inf')\n",
    "\n",
    "        def __eq__(self, other):\n",
    "            return self.x == other.x and self.y == other.y\n",
    "\n",
    "        def __ne__(self, other):\n",
    "            return not self == other\n",
    "\n",
    "        def __neg__(self):\n",
    "            if self.is_zero():\n",
    "                return self\n",
    "\n",
    "            return self.__class__(self.x, P - self.y)\n",
    "\n",
    "        # Double point\n",
    "        def dbl(self):\n",
    "            x = self.x\n",
    "            y = self.y\n",
    "            s = (3 * x * x * pow(2 * y, P - 2, P)) % P\n",
    "            sum_x = (s * s - 2 * x) % P\n",
    "            sum_y = (s * (x - sum_x) - y) % P\n",
    "\n",
    "            return self.__class__(sum_x, sum_y)\n",
    "\n",
    "        def __add__(self, other):\n",
    "            if self == other:\n",
    "                return self.dbl()\n",
    "            if self.is_zero():\n",
    "                return other\n",
    "            if other.is_zero():\n",
    "                return self\n",
    "            if self.x == other.x and self.y != other.y:\n",
    "                return self.__class__()\n",
    "            s = ((other.y - self.y) * pow(other.x - self.x, P - 2, P)) % P\n",
    "            sum_x = (s * s - self.x - other.x) % P\n",
    "            sum_y = (s * (self.x - sum_x) - self.y) % P\n",
    "\n",
    "            return self.__class__(sum_x, sum_y)\n",
    "\n",
    "        def __rmul__(self, scalar):\n",
    "            p = self\n",
    "            r = self.__class__()\n",
    "            i = 1\n",
    "\n",
    "            while i <= scalar:\n",
    "                if i & scalar:\n",
    "                    r = r + p\n",
    "                p = p.dbl()\n",
    "                i <<= 1\n",
    "\n",
    "            return r\n",
    "\n",
    "        def __str__(self):\n",
    "            if self.is_zero():\n",
    "                return '0'\n",
    "            return 'X: 0x{:x}\\nY: 0x{:x}'.format(self.x, self.y)\n",
    "\n",
    "        def __repr__(self) -> str:\n",
    "            return self.__str__()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create ECC Generator point\n",
    "G = Point(G_x, G_y)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distributed Key Generation (DKG)\n",
    "Pedersen-style Distributed Key Generation (DKG) is a cryptographic protocol used to securely generate and distribute cryptographic keys in a decentralized manner. The protocol is named after its creator, Torben Pedersen. DKG is particularly useful in scenarios where a group of parties need to collaboratively generate a shared secret key while ensuring that no subset of participants can determine the key on their own.\n",
    "\n",
    "The key goal of DKG is to ensure that the final generated key is both unpredictable and secure, even in the presence of malicious participants or communication failures. This is achieved through a series of interactive steps that involve multiple participants working together to contribute information and perform computations.\n",
    "\n",
    "Here's a simplified overview of how a Pedersen-style DKG protocol might work:\n",
    "\n",
    "- Setup: Before the protocol begins, participants agree on certain parameters and cryptographic assumptions. These might include the choice of a mathematical group (such as an elliptic curve group), security parameters, and other relevant settings.\n",
    "- Commitment Phase: Each participant generates a commitment to their secret share (a partial key) without revealing the actual value. These commitments are shared with the entire group. This phase ensures that participants are committed to their shares and prevents them from altering their values later in the protocol.\n",
    "- Communication and Verification Phases: In a series of rounds, participants share information and perform verifiable computations. They exchange commitments, proofs, and other cryptographic constructs to ensure that their commitments are consistent with the protocol rules and that everyone is following the correct steps. These phases might involve various mathematical operations and interactive proofs.\n",
    "- Reconstruction Phase: After all the necessary computations and interactions, the protocol reaches a point where the final shared key can be reconstructed. This involves combining the secret shares contributed by each participant to compute the group's shared secret key. Importantly, no individual participant can determine the key on their own.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the purpose of the lesson plan we'll be setting up a 2 out of 3 (2:3) threshold FROST setup."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "THRESHOLD = 2\n",
    "N = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "import secrets\n",
    "from hashlib import sha256\n",
    "\n",
    "def new_polynomial(threshold):\n",
    "    # Generate Shamir polynomial with random coefficients, and with degree\n",
    "    # equal to the threshold minus one.\n",
    "    coefficients = [secrets.randbits(256) % Q for _ in range(threshold)]\n",
    "    return coefficients"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initiating the Distributed Key Generation (DKG) procedure involves every participant generating a set of random numbers. A set with length = N-1. These random numbers are then utilized to construct a mathematical entity known as a \"Shamir polynomial\".\n",
    "In the context of a 2-out-of-3 (2:3), Alice's polynomial would be $f_i(x) = a_0x^0 + a_1x^1 = a_0 + a_1x^1$. Where $i$ is Alice's index in the multiset. Therefore the numbers Alice would generate would be the coeffecients of her polynomial. i.e $a_0$ and $a_1$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1 = new_polynomial(THRESHOLD)\n",
    "p2 = new_polynomial(THRESHOLD)\n",
    "p3 = new_polynomial(THRESHOLD)\n",
    "\n",
    "p1_commitments = [coefficient * G for coefficient in p1]\n",
    "p2_commitments = [coefficient * G for coefficient in p2]\n",
    "p3_commitments = [coefficient * G for coefficient in p3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We take the polynomial’s coefficients, and raise them to $g$ to produce the public commitments. The only value relevant for producing a public key is the commitment derived from the first coefficient. We'll get more into that later.\n",
    "To recap so far we have 3 participants and 3 polynomials.\n",
    "* Alice -> $f_1(x) = a_0x^0 + a_1x^1$\n",
    "* Bob -> $f_2(x) = a_0x^0 + a_1x^1$\n",
    "* Carol -> $f_3(x) = a_0x^0 + a_1x^1$\n",
    "\n",
    "\n",
    "Each participant have public commitments which are just the coeffecients ($a_i$) multiplied by the generator. $g^{a_i}$\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next up is the commitment phase of DKG.\n",
    "> Each participant generates a commitment to their secret share (a partial key) without revealing the actual value. These commitments are shared with the entire group. This phase ensures that participants are committed to their shares and prevents them from altering their values later in the protocol "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Participant needs to commit to their partial key\n",
    "# And commit to their index in the signing session\n",
    "# This is done by signing a nonce and their index\n",
    "def proof_of_knowledge(index, coefficients):\n",
    "    nonce = secrets.randbits(256) % Q\n",
    "    nonce_point = nonce * G\n",
    "    # a_0 (first coef) is always the partial private key\n",
    "    secret = coefficients[0]\n",
    "    secret_commitment = secret * G\n",
    "\n",
    "    # The challenge below is composed of the\n",
    "    # Index in multiset, starting at 1\n",
    "    # The frost tag\n",
    "    # Your partial secret key (a_0)\n",
    "    # Your nonce\n",
    "    challenge_input = index.to_bytes(1, 'big') + CONTEXT + secret_commitment.secret_serialize() + nonce_point.secret_serialize()\n",
    "    challenge_hash = sha256(challenge_input)\n",
    "    challenge_hash_bytes = challenge_hash.digest()\n",
    "    challenge_hash_int = int.from_bytes(challenge_hash_bytes, 'big')\n",
    "    \n",
    "    s = (nonce + secret * challenge_hash_int) % Q\n",
    "\n",
    "    return [nonce_point, s]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To provide a commitment to FROST signing session we produce a signature with our partial key.\n",
    "The challenge is composed of $c = H(i | Ω | a_0 | K)$\n",
    "Where $K$ is public nonce point and $Ω$ is the FROST tag. Note that the proof primarily involves verifying familiarity with the initial coefficient ($a_0$) without disclosing its actual value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1_proof = proof_of_knowledge(1, p1)\n",
    "p2_proof = proof_of_knowledge(2, p2)\n",
    "p3_proof = proof_of_knowledge(3, p3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We want to verify a participant verifies knowledge of their coeffcients\n",
    "# Proof is a normal schnorr signature (s,r)\n",
    "def verify_proof_of_knowledge(index, proof, first_coeffecient):\n",
    "    [nonce_point, s] = proof\n",
    "    # Recalculate the challenge from above\n",
    "    challenge_input = index.to_bytes(1, 'big') + CONTEXT + first_coeffecient.secret_serialize() + nonce_point.secret_serialize()\n",
    "    challenge_hash_bytes = sha256(challenge_input).digest()\n",
    "    challenge_hash_int = int.from_bytes(challenge_hash_bytes, 'big')\n",
    "\n",
    "    return nonce_point == (s * G) + (Q - challenge_hash_int) * first_coeffecient\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We verify each proof by checking if $R = s * G + C * g^{a_0}$. Note this is not any different than the naive Shnorr verification algorithm "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Verify proofs\n",
    "# Each participant needs to do this for each proof provided\n",
    "assert(verify_proof_of_knowledge(1, p1_proof, p1_commitments[0]) == True)\n",
    "assert(verify_proof_of_knowledge(2, p2_proof, p2_commitments[0]) == True)\n",
    "assert(verify_proof_of_knowledge(3, p3_proof, p3_commitments[0]) == True)\n",
    "\n",
    "assert(not verify_proof_of_knowledge(2, p1_proof, p1_commitments[0]))\n",
    "assert(not verify_proof_of_knowledge(1, p1_proof, p2_commitments[0]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prior to the reconstruction of the shared aggregated secret or the aggregated public key, every participant must possess their respective partial share. A partial share is the result of summing up the evaluations of each participant's polynomial at every index within the multiset. Essentially, a share represents a fractional element of the aggregated secret. A single share alone is insufficient to derive the complete secret, but a specified set or the threshold number of shares has the capability to do so.\n",
    "For example, $s_i = \\sum_{j=1}^{n} f_j(i)$ Where $i$ is the particiapants index.\n",
    "\n",
    "In essence:\n",
    "* Alice sums up $f_1(1) + f_2(1) + f_3(1) $ to create $s_1$ \n",
    "* Bob sums up $f_1(2) + f_2(2) + f_3(2) $ to create $s_2$\n",
    "* Carol sums up $f_1(3) + f_2(3) + f_3(3) $ to create $s_3$\n",
    "\n",
    "\n",
    "![Shares](\"images/shamir_sharing.png\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lets generate aggregate shares\n",
    "# Coefs here are ints, not ecc points\n",
    "# However the partial share is a point on the ecc graph\n",
    "def evaluate_polynomial(index, participant_coefficients):\n",
    "    share = 0\n",
    "    for i in range(len(participant_coefficients) - 1, -1, -1):\n",
    "        share = share * index + participant_coefficients[i]\n",
    "\n",
    "    return share % Q\n",
    "\n",
    "\n",
    "def generate_share(n, participant_coefficients):\n",
    "    # Evaluate a participants poly at each index\n",
    "    # Remeber we index at 1\n",
    "    shares = [evaluate_polynomial(i, participant_coefficients) for i in range(1, n + 1)]\n",
    "    return shares\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1_share = generate_share(N, p1)\n",
    "p2_share = generate_share(N, p2)\n",
    "p3_share = generate_share(N, p3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# lets verify each share was calculated correctly\n",
    "def verify_share(shares, coefficient_commitments, index):\n",
    "    expected_y_commitment = Point()\n",
    "    for coef_index, coef in enumerate(coefficient_commitments):\n",
    "        expected_y_commitment = expected_y_commitment + \\\n",
    "                    ((index ** coef_index % Q) * coef)\n",
    "    return shares * G == expected_y_commitment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Is our aggregated share for participant #1 correct\n",
    "verify_share(p1_share[0], p1_commitments, 1)\n",
    "# TODO verify shares for other participants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From here calculating the aggregated share is simply the sumation of the partial shares. Each participant will calculate it differently, by putting their partial share first and store is seperately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def aggregate_shares(participant_share, shares):\n",
    "    aggregate_share = participant_share\n",
    "    for share in shares:\n",
    "        aggregate_share = aggregate_share + share\n",
    "    return aggregate_share % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "p1_agg = aggregate_shares(p1_share[0],[p2_share[0], p3_share[0]])\n",
    "p2_agg = aggregate_shares(p2_share[1],[p1_share[1], p3_share[1]])\n",
    "p3_agg = aggregate_shares(p3_share[2],[p2_share[2], p1_share[2]])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As previously indicated, when it comes to generating the public key, our focus is solely on the initial coefficient. In other words, $a_0$, which repersents the exact point of intersection between the polynomial and the y-axis. \n",
    "\n",
    "The aggregate public key is therfore the summation of all y intercept points.\n",
    "$P = \\sum_{i=1}^{n} g^{f(0)}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# x_0 for each participant polynomials\n",
    "def derive_public_key(first_coeffecients):\n",
    "    public_key = first_coeffecients[0]\n",
    "    for commitment in first_coeffecients[1:]:\n",
    "        public_key = public_key + commitment\n",
    "\n",
    "    return public_key\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: Any combination of the participant coeffecient should produce the same outcome. We'll leave this as an exercise for the reader"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X: 0x298b04ed55ba26d197f2794e418af941917f6474fb01d9c3ef6c45119a868160\n",
       "Y: 0xb9f8a188cad6561adeb84d4e3de18feb275849f68184688b161db568ac088bfd"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aggregate_public_key = derive_public_key([p1_commitments[0], p2_commitments[0], p3_commitments[0]])\n",
    "aggregate_public_key\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Job done! We have a aggregate public key and shares used to provide a threshold signature. Let's throw a party...\n",
    "\n",
    "\n",
    "Not just yet. Before we sign and verify lets ensure we can reconstruct the aggregate public key given a set of aggregate shares formed by 2:3 participants. \n",
    "\n",
    "To do this we need to compute a coefficient that when multiplied by the corresponding polynomial value at a specific index, contributes to the reconstruction of the original polynomial based on the given participant indexes and the index of interest.\n",
    "\n",
    "$L = \\frac{{\\prod_{i=1, i \\neq my\\_index}^{n} index_i}}{{\\prod_{i=1, i \\neq my\\_index}^{n} (index_i - my\\_index)}} \\cdot (index\\_denominator^{Q - 2} \\mod Q)$\n",
    "\n",
    "Where:\n",
    "- $( index\\_denominator = \\prod_{i=1, i \\neq my\\_index}^{n} (index_i - my\\_index)$\n",
    "\n",
    "\n",
    "In summary, the function calculates the Lagrange coefficient $L$ by dividing the product of all participant indices (excluding my_index) by the product of the differences between each participant index and my_index. It then multiplies this by the modular inverse of index_denominator modulo $Q$, resulting in the final Lagrange coefficient.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    " def lagrange_coefficient(participant_indexes, my_index):\n",
    "    numerator = 1\n",
    "    denominator = 1\n",
    "    for index in participant_indexes:\n",
    "        if index == my_index:\n",
    "            continue\n",
    "        numerator = numerator * index\n",
    "        denominator = denominator * (index - my_index)\n",
    "    return (numerator * pow(denominator, Q - 2, Q)) % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lets reconstruct the secret\n",
    "# First we construct a lagrange coefficient for the first participant\n",
    "l1 = lagrange_coefficient([2], 1)\n",
    "# And one for the second participant\n",
    "l2 = lagrange_coefficient([1], 2)\n",
    "# Verify we get the same aggregate public key\n",
    "secret = ((p1_agg * l1) + (p2_agg * l2)) % Q\n",
    "assert(secret * G == aggregate_public_key)\n",
    "\n",
    "# Lets repeat the same exercise for the third and second participants\n",
    "l3 = lagrange_coefficient([2], 3)\n",
    "l2 = lagrange_coefficient([3], 2)\n",
    "secret = ((p3_agg * l3) + (p2_agg * l2)) % Q\n",
    "assert(secret * G == aggregate_public_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note here that we are able to reconstruct aggregated public key by simply $g^s$. In the previous steps we needed to sum all first coeffecients. So it worked!\n",
    "\n",
    "To recap:\n",
    "The overall process of DKG can be outlined as follows:\n",
    "* Each participant initiates the creation of a Shamir polynomial, establishing the polynomial's coefficients.\n",
    "* They subsequently produce their respective shares and corresponding commitments.\n",
    "* The shares and commitments are then disseminated, allowing each individual participant to conduct verification.\n",
    "* By combining the commitments, the public key is computed, serving as a culmination of this procedure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Signature Procedure\n",
    "\n",
    "The signature procedure is executed in adherence to a comprehensive two-step protocol. In this procedural framework, all involved participants execute the subsequent actions:\n",
    "\n",
    "1. Generation of nonce pairs.\n",
    "2. Dissemination of these generated nonce pairs among peers or a designated central coordinator.\n",
    "3. Subsequent creation of partial signatures, pertaining to a message of universal significance.\n",
    "\n",
    "It's worth noting that an alternative signing protocol, as outlined in the referenced document, involves the pre-computation and batch sharing of nonces.\n",
    "\n",
    "\n",
    "### Note about nonce generation\n",
    "It is imperative to be acutely aware of the potential hazards associated with nonce generation when dealing with the Schnorr or any elleptical curve operation. Mishandling nonce values can lead to severe vulnerabilities that compromise the security of cryptographic operations.\n",
    "Inadequate or predictable nonce generation may expose a system to various attacks, including private key leakage, signature forgery, and even complete cryptographic breaches. Attackers exploiting weak nonces can exploit patterns and repetitions to derive private keys or duplicate signatures.\n",
    "TLDR; nonce generation is tricky; read more about it [here](https://blog.blockstream.com/en-musig-a-new-multisignature-standard/#uniform-randomness) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lets first define utility method for generating random nonce pairs\n",
    "def generate_nonces():\n",
    "    nonce_pair = [secrets.randbits(256) % Q, secrets.randbits(256) % Q]\n",
    "    return nonce_pair\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "p1_nonce_pair = generate_nonces()\n",
    "p2_nonce_pair = generate_nonces()\n",
    "p3_nonce_pair = generate_nonces()\n",
    "\n",
    "p1_nonce_point = [p1_nonce_pair[0] * G, p1_nonce_pair[1] * G]\n",
    "p2_nonce_point = [p2_nonce_pair[0] * G, p2_nonce_pair[1] * G]\n",
    "p3_nonce_point = [p3_nonce_pair[0] * G, p3_nonce_pair[1] * G]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Round 1: Message and Nonces\n",
    "\n",
    "At this point a signature aggregator is designated, which might be a participant or a third-party coordinator.\n",
    "\n",
    "The role of this signature aggregator entails collecting the previously generated nonce commitments from each signer $i$, resulting in a set $B = \\{(i, D_i, E_i)\\}$, where $D$ and $E$ signify the nonce pairs for each participant.\n",
    "\n",
    "The signature aggregator becomes capable of disseminating both the message $m$ and the set $B$ to every participant engaged in the signing process.\n",
    "\n",
    "\n",
    "Each signing participant then embarks on the task of verifying the message. This can be business logic specific to the application, for exmaple validate outputs in Bitcoin transaction.\n",
    "\n",
    "Before calculating partial signatures signers need to generate a binding value $p_i = H(i | m | B)$.\n",
    "The binding commitment is crututial to concurrent FROST signing operation while preventing known forgery attacks. By signing the hash of the message, set of nonces, and your index, this garuntees that this signature cannot be manuplicated in a seperated FROST signing session by malicious signing group.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binding_value(index, message, nonce_commitment_pairs, participant_indexes):\n",
    "    bv = sha256()\n",
    "    nonce_commitment_pairs_bytes = []\n",
    "    for index in participant_indexes:\n",
    "        participant_pair = nonce_commitment_pairs[index-1]\n",
    "        participant_pair_bytes = b''.join([commitment.secret_serialize() for commitment in participant_pair])\n",
    "        nonce_commitment_pairs_bytes.append(participant_pair_bytes)\n",
    "    nonce_commitment_pairs_bytes = b''.join(nonce_commitment_pairs_bytes)\n",
    "    pre_image = index.to_bytes(1, 'big') + message + nonce_commitment_pairs_bytes\n",
    "    bv = sha256(pre_image)\n",
    "    binding_value_bytes = bv.digest()\n",
    "\n",
    "    return int.from_bytes(binding_value_bytes, 'big')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lastly, binding values are used to derive the group commitment $R$.\n",
    "\n",
    "Each participant calculates the commitment $Ri$ for every individual within the set $S$. This calculation involves deriving $R_i = D_i * E_i*p_i$. This procedural step establishes a binding relationship between the message, the consortium of signing participants, and the commitment of each participant to their respective signature share. The adoption of this binding technique effectively neutralizes the attack strategy outlined by Drijvers et al. As a result of this approach, potential attackers are hindered from amalgamating signature shares across disparate signing operations, or manipulating the order of signers, or altering the published commitments associated with each signer.\n",
    "\n",
    "The group commitment is therfore defined as $R = \\prod_{i=1}^{n}D_i * (E_i*{p_i})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def group_commitment(message, nonce_commitment_pairs, participant_indexes):\n",
    "    gc = Point()\n",
    "    for index in participant_indexes:\n",
    "        bv = binding_value(index, message, nonce_commitment_pairs, participant_indexes)\n",
    "        first_commitment = nonce_commitment_pairs[index-1][0]\n",
    "        second_commitment = nonce_commitment_pairs[index-1][1]\n",
    "        gc = gc + (first_commitment + (bv * second_commitment))\n",
    "    return gc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And finally our challenge $c$, defined as\n",
    "\n",
    "$c = H(Ω|Ω|R|Y|m)$, where $Y$ is the aggregate public key and $Ω$ is the FROST tag.\n",
    "The moment we've all been waiting for, signing!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def challenge_hash(nonce_commitment, aggregate_public_key, message):\n",
    "    tag_hash = sha256(b'BIP0340/challenge').digest()\n",
    "    challenge_hash = sha256()\n",
    "    challenge_hash.update(tag_hash)\n",
    "    challenge_hash.update(tag_hash)\n",
    "    challenge_hash.update(nonce_commitment.xonly_serialize())\n",
    "    challenge_hash.update(aggregate_public_key.xonly_serialize())\n",
    "    challenge_hash.update(message)\n",
    "    challenge_hash_bytes = challenge_hash.digest()\n",
    "\n",
    "    return int.from_bytes(challenge_hash_bytes, 'big') % Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Round 2: Signing\n",
    "Partial signature are defined as\n",
    "$z_i = d_i + (e_i + p_i) + \\lambda_i * s_i * c$.\n",
    "\n",
    "Recall $\\lambda_i$ is the lagrange coefficient as defined before. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sign(message, nonce_commitment_pairs, participant_indexes, signing_nonce_pair, signer_index, aggregate_public_key, aggregate_share):\n",
    "    gc = group_commitment(message, nonce_commitment_pairs, participant_indexes)\n",
    "    challenge = challenge_hash(gc, aggregate_public_key, message)\n",
    "    [first_nonce, second_nonce] = signing_nonce_pair\n",
    "\n",
    "    bv = binding_value(signer_index, message, nonce_commitment_pairs, participant_indexes)\n",
    "    \n",
    "    lagrange = lagrange_coefficient(participant_indexes, my_index=signer_index)\n",
    "\n",
    "    # Negate nonce pair if group commitment is odd\n",
    "    if gc.y % 2 != 0:\n",
    "        first_nonce = Q - first_nonce\n",
    "        second_nonce = Q - second_nonce\n",
    "    \n",
    "    # Negate aggregate share if aggregate public key point is odd\n",
    "    if aggregate_public_key.y % 2 != 0:\n",
    "        aggregate_share = Q - aggregate_share\n",
    "\n",
    "    return (first_nonce + (second_nonce * bv) + lagrange * aggregate_share * challenge) % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Lets sign with the first and second participants\n",
    "msg = b'craigwrightisnotsatoshi!'\n",
    "participant_indexes = [1, 2]\n",
    "nonce_commitment_pairs = [p1_nonce_point, p2_nonce_point]\n",
    "\n",
    "s1 = sign(\n",
    "    message=msg,\n",
    "    nonce_commitment_pairs=nonce_commitment_pairs,\n",
    "    participant_indexes=participant_indexes,\n",
    "    signing_nonce_pair=p1_nonce_pair,\n",
    "    signer_index=1,\n",
    "    aggregate_public_key=aggregate_public_key,\n",
    "    aggregate_share=p1_agg\n",
    ")\n",
    "\n",
    "s2 = sign(\n",
    "    message=msg,\n",
    "    nonce_commitment_pairs=nonce_commitment_pairs,\n",
    "    participant_indexes=participant_indexes,\n",
    "    signing_nonce_pair=p2_nonce_pair,\n",
    "    signer_index=2,\n",
    "    aggregate_public_key=aggregate_public_key,\n",
    "    aggregate_share=p2_agg\n",
    ")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If all participants correctly distributed their partial signature the signature aggregator can produce the final aggregate signature by summing all partial signature and providing the final signature.\n",
    "\n",
    "$z = \\sum_{i=1}^{t} z_i$\n",
    "\n",
    "The aggreagtor can now share $\\sigma = (R, z)$ along with $m$ for verification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def aggregate_signatures(signature_shares, gc, challenge):\n",
    "    # TODO: verify each signature share\n",
    "    nonce_commitment = gc.xonly_serialize()\n",
    "    z = (sum(signature_shares) % Q).to_bytes(32, 'big')\n",
    "\n",
    "    return bytes.fromhex((nonce_commitment + z).hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Verification\n",
    "Verifying is no different than a normal Schnorr verification\n",
    "\n",
    "All parties involved (including the third party cordinator) can validate the aggregated signature if\n",
    "\n",
    "$R = (z * G) + (Q - c) * Y$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "gc = group_commitment(msg, nonce_commitment_pairs, participant_indexes)\n",
    "challenge = challenge_hash(gc, aggregate_public_key, msg)\n",
    "agg_sig = aggregate_signatures([s1, s2], gc=gc, challenge=challenge)\n",
    "nonce_commitment = Point.xonly_deserialize(agg_sig[0:32].hex())\n",
    "z = int.from_bytes(agg_sig[32:64], 'big')\n",
    "\n",
    "# verify\n",
    "# Negate Y if Y.y is odd\n",
    "if aggregate_public_key.y % 2 != 0:\n",
    "    aggregate_public_key = -aggregate_public_key\n",
    "\n",
    "assert(nonce_commitment == (z * G) +(Q - challenge) * aggregate_public_key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.13"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}