Skip to content

Instantly share code, notes, and snippets.

@shubham-kanodia
Last active November 2, 2023 06:16
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save shubham-kanodia/dc9590531a3df230fc8063e499443932 to your computer and use it in GitHub Desktop.
Save shubham-kanodia/dc9590531a3df230fc8063e499443932 to your computer and use it in GitHub Desktop.

R1CS

Equation

$$x^2 + x + 2 == 32$$

Gates

  • $x * x = sym_1$
  • $x + sym_1 = sym_2$
  • $sym_2 + 2 = out$

Gates #1

$\vec{a} = [0, 1, 0, 0, 0]$

$\vec{b} = [0, 1, 0, 0, 0]$

$\vec{c} = [0, 0, 0, 1, 0]$

Gate #2

$\vec{a} = [1, 0, 0, 0, 0]$

$\vec{b} = [0, 1, 0, 1, 0]$

$\vec{c} = [0, 0, 0, 0, 1]$

Gate #3

$\vec{a} = [1, 0, 0, 0, 0]$

$\vec{b} = [2, 0, 0, 0, 1]$

$\vec{c} = [0, 0, 1, 0, 0]$

Solution Vector

$\vec{s} = [1, x, out, sym_1, sym_2]$

$\therefore \vec{s} = [1, 5, 32, 25, 30]$

R1CS

$$ A = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix} $$

$$ B = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 2 & 0 & 0 & 0 & 1 \end{bmatrix} $$

$$ C = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} $$

Lagrange Polynomials

$L_1(x)= \frac{1}{2}x^2 - \frac{5}{2}x + 3$

$L_2(x)= -x^2 + 4x - 3$

$L_3(x)= \frac{1}{2}x^2 - \frac{3}{2}x + 1$

QAP

$$ A(x) = \begin{bmatrix} \frac{-1}{2}x^2 + \frac{5}{2}x - 2 \\ \frac{1}{2}x^2 - \frac{5}{2}x + 3 \\ 0 \\ 0 \\ 0 \end{bmatrix} $$

$$ B(x) = \begin{bmatrix} x^2 - 3x + 2 \\ \frac{-1}{2}x^2 + \frac{3}{2}x \\ 0 \\ -x^2 + 4x - 3 \\ \frac{1}{2}x^2 - \frac{3}{2}x + 1 \end{bmatrix} $$

$$ C(x) = \begin{bmatrix} 0 \\ 0 \\ \frac{1}{2}x^2 - \frac{3}{2}x + 1 \\ \frac{1}{2}x^2 - \frac{5}{2}x + 3 \\ -x^2 + 4x - 3 \end{bmatrix} $$

$A(x).\vec{s} = 2x^2 - 10x + 13$

$B(x).\vec{s} = -\frac{23}{2}x^2 + \frac{119}{2}x - 43$

$C(x).\vec{s} = \frac{-3}{2}x^2 + \frac{19}{2}x + 17$

$A(x).\vec{s} * B(x).\vec{s} - C(x).\vec{s} = -23x^4 + 234x^3 - 829x^2 + 1194x - 576$

Introducing a circuit error

Changing Gate #2

$\vec{a} = [1, 0, 0, 0, 0]$

$\vec{b} = [0, 1, 0, 0, 1]$

$\vec{c} = [0, 0, 0, 0, 1]$

We get, $A(x).\vec{s} * B(x).\vec{s} - C(x).\vec{s} = -33x^4 + 324x^3 - 1124x^2 + 1604x - 771$

The above polynomial only has roots x=1, x=3 - Wolfram view

Introducing solution error

$\vec{s} = [1, 5, 32, 25, 35]$

$A(x).\vec{s} * B(x).\vec{s} - C(x).\vec{s} = -18x^4 + 194x^3 - \frac{1413}{2}x^2 + \frac{2053}{2}x - 496$

Root only at x=1 - Wolfram view

Important Reading Links

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment