{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The manuscript \"SLVer Bullet: Straight-Line Verification for Bulletproofs\" by Goodell, Salazar, Slaughter, Szramowski contains a modification of the verification equations obtained by Eagen in the manuscript \"Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity\". Below is a modification of a SAGE implementation by Eagen in order to check these equations on particular examples. There also seems to be an additional 2y factor in the terms in SLVer Bullet. We also provide the corresponding values for these modified expressions.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize an elliptic curve\n",
    "p=103\n",
    "Fp = GF(p)  # Base Field\n",
    "A = 0\n",
    "B = 7\n",
    "E = EllipticCurve(GF(p), [A,B])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "K.<x> = Fp[]\n",
    "L.<y> = K[]\n",
    "eqn = y^2 - x^3 - A * x - B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Returns line passing through points, works for all points and returns 1 for O + O = O\n",
    "def line(A, B):\n",
    "    if A == 0 and B == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        [a, b, c] = Matrix([A, B, -(A+B)]).transpose().kernel().basis()[0]\n",
    "        return a*x + b*y + c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Works for A == B but not A == -A, as the line has no slope or intercept\n",
    "def slope_intercept(A, B):\n",
    "    [a, b, c] = Matrix([A, B, -(A+B)]).transpose().kernel().basis()[0]\n",
    "    return (-a/b, -c/b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fails at 0\n",
    "def eval_point(f, P):\n",
    "    (x, y) = P.xy()\n",
    "    return f(x=x, y=y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# f(x) + y g(x) -> (f(x), g(x)), should reduce mod eqn first\n",
    "def get_polys(D):\n",
    "    return ( K(D(y=0)), K(D(y=1) - D(y=0)) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Accepts arbitrary list of points, including duplicates and inverses, and constructs function\n",
    "# intersecting exactly those points if they form a principal divisor (i.e. sum to zero).\n",
    "def construct_function(Ps):\n",
    "    # List of intermediate sums/principal divisors, removes 0\n",
    "    xs = [(P, line(P, -P)) for P in Ps if P != 0]\n",
    "\n",
    "    while len(xs) != 1:\n",
    "        assert(sum(P for (P, _) in xs) == 0)\n",
    "        xs2 = []\n",
    "\n",
    "        # Carry extra point forward\n",
    "        if mod(len(xs), 2) == 1:\n",
    "            x0 = xs[0]\n",
    "            xs = xs[1:]\n",
    "        else:\n",
    "            x0 = None\n",
    "\n",
    "        # Combine the functions for all pairs\n",
    "        for n in range(0, floor(len(xs)/2)):\n",
    "            (A, aNum) = xs[2*n]\n",
    "            (B, bNum) = xs[2*n+1]\n",
    "\n",
    "            # Divide out intermediate (P, -P) factors\n",
    "            num = L((aNum * bNum * line(A, B)).mod(eqn))\n",
    "            den = line(A, -A) * line(B, -B)\n",
    "            D = num / K(den)\n",
    "            \n",
    "            # Add new element\n",
    "            xs2.append((A+B, D))\n",
    "        \n",
    "        if x0 != None:\n",
    "            xs2.append(x0)\n",
    "\n",
    "        xs = xs2\n",
    "    \n",
    "    assert(xs[0][0] == 0)\n",
    "    \n",
    "    # Normalize, might fail but negl probability for random points. Must be done for zkps\n",
    "    # although free to use any coefficient\n",
    "    return D / D(x=0, y=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Random principal divisor with n points\n",
    "def random_principal(n):\n",
    "    # For general elliptic curves, might want to clear cofactor depending on application\n",
    "    # Works for arbitrary curve groups\n",
    "    Ps = [E.random_element() for _ in range(0, n-1)]\n",
    "    Ps.append(-sum(Ps))\n",
    "    return Ps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "N=5\n",
    "DIV = random_principal(N)  #create a random principal divisor with N elements in its support\n",
    "D = construct_function(DIV)\n",
    "(a,b)=get_polys(D)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "Dx = D.differentiate(x)\n",
    "Dy = D.differentiate(y)\n",
    "Dz = Dx + Dy * ((3*x^2 + A) / (2*y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Generate random challenge points, compute slope lam and intercept cons\n",
    "[A0, A1] = [E.random_element() for _ in range(0, 2)]\n",
    "(lam,cons)=slope_intercept(A0,A1)\n",
    "A2 = -(A0 + A1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Value of expression for the logarithmic derivative of L(div f):\n",
      "40\n",
      "Value of expression derived by Eagen for the logarithmic derivative of the norm:\n",
      "40\n",
      "Value of expression derived in SLVer Bullet for the logarithmic derivative of the norm (with extra 2y factors in denominator removed):\n",
      "82\n",
      "Value of expression derived in SLVer Bullet for the logarithmic derivative of the norm as given in the manuscript:\n",
      "81\n"
     ]
    }
   ],
   "source": [
    "#the common expression for the numerator appearing in Eagen and for the terms c1 and c3 in SLVer Bullet\n",
    "NUM=2*y*Dx+(3*x^2+A)*b \n",
    "#the common expression for the numerator appearing in Eagen and for the terms c1 and c3 in SLVer Bullet\n",
    "DENOM=D*(3*x^2+A-lam*2*y) \n",
    "\n",
    "print(\"Value of expression for the logarithmic derivative of L(div f):\")\n",
    "print(sum(eval_point(1/(cons-(y-lam*x)), P) for P in DIV))\n",
    "\n",
    "print(\"Value of expression derived by Eagen for the logarithmic derivative of the norm:\")\n",
    "print(sum(eval_point(NUM, P)/eval_point(DENOM, P) for P in [A0, A1, A2]))\n",
    "\n",
    "#c2, b3, c4, b4 according to SLVer Bullet with 2y factor in the denominator removed\n",
    "c2=-(2*lam*A0[1]*(2*A2[1]*eval_point(Dx, A2)+(3*A2[0]^2+A)*eval_point(b, A2))*(3*A0[0]^2+A-2*A0[1]*(lam+A1[0]-A0[0])))\n",
    "b2=A2[1]*eval_point(D, A2)*(3*A0[0]^2+A-2*A0[1]*lam)*(A1[0]-A0[0])\n",
    "c4=(2*lam*A1[1]*(2*A2[1]*eval_point(Dx, A2)+(3*A2[0]^2+A)*eval_point(b, A2))*(3*A1[1]^2+A-2*A1[1]*(lam+A1[0]-A0[0])))\n",
    "b4=A2[1]*eval_point(D, A2)*(3*A1[0]^2+A-2*A1[1]*lam)*(A1[0]-A0[0])\n",
    "print(\"Value of expression derived in SLVer Bullet for the logarithmic derivative of the norm (with extra 2y factors in denominator removed):\")\n",
    "print(c2/b2+c4/b4+sum(eval_point(NUM, P)/eval_point(DENOM, P) for P in [A0, A1]))\n",
    "\n",
    "#expressions given in SLVer Bullet without correcting the denominators\n",
    "NUMp=2*y*Dx+(3*x^2+A)*b\n",
    "DENOMp=2*y*D*(3*x^2+A-lam*2*y) #here 2y is added\n",
    "c2p=-(2*lam*A0[1]*(2*A2[1]*eval_point(Dx, A2)+(3*A2[0]^2+A)*eval_point(b, A2))*(3*A0[0]^2+A-2*A0[1]*(lam+A1[0]-A0[0])))\n",
    "b2p=2*A0[1]*A2[1]*eval_point(D, A2)*(3*A0[0]^2+A-2*A0[1]*lam)*(A1[0]-A0[0]) #here 2y is added\n",
    "c4p=(2*lam*A1[1]*(2*A2[1]*eval_point(Dx, A2)+(3*A2[0]^2+A)*eval_point(b, A2))*(3*A1[1]^2+A-2*A1[1]*(lam+A1[0]-A0[0])))\n",
    "b4p=2*A1[1]*A2[1]*eval_point(D, A2)*(3*A1[0]^2+A-2*A1[1]*lam)*(A1[0]-A0[0]) #here 2y is added\n",
    "print(\"Value of expression derived in SLVer Bullet for the logarithmic derivative of the norm as given in the manuscript:\")\n",
    "print(c2p/b2p+c4p/b4p+sum(eval_point(NUMp, P)/eval_point(DENOMp, P) for P in [A0, A1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.6",
   "language": "sage",
   "name": "sagemath"
  },
  "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.12.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}