द्विघात अंकगणितीय प्रोग्राम्स

Last updated on Mar 22, 2026

एक quadratic arithmetic program एक arithmetic circuit है, विशेष रूप से एक Rank 1 Constraint System (R1CS) जिसे polynomials के एक सेट के रूप में दर्शाया गया है। इसे Rank 1 Constraint System पर Lagrange interpolation का उपयोग करके प्राप्त किया जाता है। R1CS के विपरीत, एक Quadratic Arithmetic Program (QAP) को Schwartz-Zippel Lemma के माध्यम से $\mathcal{O}(1)$ समय में समानता (equality) के लिए टेस्ट किया जा सकता है।

मुख्य विचार (Key ideas)

Schwartz-Zippel Lemma के अध्याय में, हमने देखा कि हम दो vectors को polynomials में बदलकर और फिर उन polynomials पर Schwartz-Zippel Lemma टेस्ट चलाकर, $\mathcal{O}(1)$ समय में यह टेस्ट कर सकते हैं कि क्या वे बराबर हैं। (स्पष्ट करने के लिए, टेस्ट $\mathcal{O}(1)$ समय लेता है, vectors को polynomials में बदलने से overhead उत्पन्न होता है)।

चूँकि Rank 1 Constraint System पूरी तरह से vector ऑपरेशन्स से बना होता है, हमारा लक्ष्य यह टेस्ट करना है कि क्या

\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}\stackrel{?}{=}\mathbf{O}\mathbf{a}

$\mathcal{O}(n)$ समय के बजाय $\mathcal{O}(1)$ समय में सही साबित होता है (जहाँ $n$ , $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ में पंक्तियों की संख्या है)।

लेकिन ऐसा करने से पहले, हमें vectors और उन्हें दर्शाने वाले polynomials के बीच के संबंध के कुछ प्रमुख गुणों को समझने की आवश्यकता है।

यहाँ सभी गणितीय गणनाओं के लिए, हम मान लेते हैं कि हम एक finite field में काम कर रहे हैं, लेकिन संक्षिप्तता के लिए हम $\mod p$ नोटेशन को छोड़ देते हैं।

Vector addition और polynomial addition के बीच Homomorphisms

Vector addition, polynomial addition के homomorphic है

यदि हम दो vectors लेते हैं, उन्हें polynomials के साथ interpolate करते हैं, और फिर polynomials को एक साथ जोड़ते हैं, तो हमें वही polynomial प्राप्त होता है जो हमें तब मिलता जब हम vectors को एक साथ जोड़ते और फिर उनके sum vector को interpolate करते।

अधिक गणितीय रूप में कहें तो, मान लीजिए $\mathcal{L}(\mathbf{v})$ वह polynomial है जो vector $\mathbf{v}$ पर Lagrange interpolation से प्राप्त होता है, जिसमें $x$ वैल्यू के रूप में $(1, 2, ..., n)$ का उपयोग किया गया है, जहाँ $n$ , $\mathbf{v}$ की लंबाई है। निम्नलिखित सत्य है:

\mathcal{L}(\mathbf{v} + \mathbf{w}) = \mathcal{L}(\mathbf{v}) + \mathcal{L}(\mathbf{w})

दूसरे शब्दों में, vectors $\mathbf{v}$ और $\mathbf{w}$ को अलग-अलग interpolate करके उनके polynomials को जोड़ने पर वही परिणाम मिलता है जो vectors $\mathbf{v} + \mathbf{w}$ को interpolate करने पर मिलता है।

हल किया गया उदाहरण

मान लीजिए $f_1(x) = x^2$ और $f_2(x) = x^3$ है। $f_1$ , $(1, 1), (2, 4), (3, 9)$ या vector $[1,4,9]$ को interpolate करता है और $f_2$ , $[1,8,27]$ को interpolate करता है।

इन vectors का योग $[2,12,36]$ है और यह स्पष्ट है कि $x^3 + x^2$ इसे interpolate करता है। मान लीजिए $f_3(x) = f_1(x) + f_2(x) = x^3 + x^2$ ।

\begin{align*} f_3(1) &= 1 + 1 = 2\\ f_3(2) &= 8 + 4 = 12\\ f_3(3) &= 27 + 9 = 36 \end{align*}

Python में गणित को टेस्ट करना

किसी प्रस्तावित गणितीय identity की unit testing करने से वह सत्य नहीं हो जाती, लेकिन यह यह ज़रूर दर्शाती है कि क्या हो रहा है। पाठकों को प्रोत्साहित किया जाता है कि वे कुछ अलग-अलग vectors आज़माकर देखें कि यह identity सही साबित होती है या नहीं।

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# two arbitrary vectors
v1 =  GF(np.array([4,8,2])) 
v2 =  GF(np.array([1,6,12]))

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(v1 + v2) == L(v1) + L(v2)

Scalar multiplication

मान लीजिए $\lambda$ एक scalar है (विशेष रूप से, finite field में एक field element)। तब

\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})

हल किया गया उदाहरण

मान लीजिए हमारे 3 points $[3, 6, 11]$ हैं। वह polynomial जो इसे interpolate करता है, वह $f(x) = x^2 + 2$ है। यदि हम इस vector को 3 से गुणा करते हैं, तो हमें $[9, 18, 33]$ मिलता है। जो polynomial इसे interpolate करता है वह है

from scipy.interpolate import lagrange

x_values = [1, 2, 3]
y_values = [9, 18, 33]

print(lagrange(x_values, y_values))

#    2
# 3 x + 6

$3x^2 + 6$ , जो $3 \cdot (x^2 + 2)$ के बराबर है।

कोड में हल किया गया उदाहरण

import galois
import numpy as np

p = 17
GF = galois.GF(p)

xs = GF(np.array([1,2,3]))

# arbitrary vector
v =  GF(np.array([4,8,2]))

# arbitrary constant
lambda_ =  GF(15)

def L(v):
    return galois.lagrange_poly(xs, v)

assert L(lambda_ * v) == lambda_ * L(v)

Scalar multiplication वास्तव में vector addition है

जब हम कहते हैं कि “एक vector को 3 से गुणा करें”, तो हम वास्तव में यह कह रहे होते हैं कि “vector को उसी में तीन बार जोड़ें”। चूँकि हम केवल finite fields में काम कर रहे हैं, हमें “0.5” जैसे scalars की व्याख्या से कोई सरोकार नहीं है।

हम element-wise addition (एक finite field में) के अंतर्गत vectors और addition के अंतर्गत polynomials (यह भी finite field में) दोनों को groups के रूप में मान सकते हैं।

इस अध्याय से सबसे महत्वपूर्ण निष्कर्ष यह है:

एक finite field में addition के अंतर्गत vectors का group, एक finite field में addition के अंतर्गत polynomials के group के homomorphic होता है।

यह बहुत महत्वपूर्ण है क्योंकि vector समानता (equality) की टेस्टिंग में $\mathcal{O}(n)$ समय लगता है, लेकिन polynomial समानता की टेस्टिंग में $\mathcal{O}(1)$ समय लगता है।

इसलिए, जहाँ R1CS समानता को टेस्ट करने में $\mathcal{O}(n)$ समय लगता था, हम इस homomorphism का लाभ उठाकर R1CSs की समानता को $\mathcal{O}(1)$ समय में टेस्ट कर सकते हैं।

यही Quadratic Arithmetic Program होता है।

Polynomials में Rank 1 Constraint System

ध्यान दें कि एक rectangular matrix और एक vector के बीच matrix multiplication को vector addition और scalar multiplication के रूप में लिखा जा सकता है।

उदाहरण के लिए, यदि हमारे पास $3 \times 4$ matrix $A$ और एक 4 डायमेंशनल vector $v$ है, तो हम इस matrix multiplication को इस प्रकार लिख सकते हैं:

\mathbf{A} \cdot \mathbf{v} = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix} \begin{bmatrix} v_1\\ v_2\\ v_3\\ v_4 \end{bmatrix}

हम आमतौर पर सोचते हैं कि vector $v$ “फ़्लिप” होकर प्रत्येक पंक्ति के साथ एक inner product (सामान्यीकृत dot product) करता है, अर्थात

\mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11}\cdot v_1 + a_{12}\cdot v_2 + a_{13}\cdot v_3 + a_{14}\cdot v_4\\ a_{21}\cdot v_1 + a_{22}\cdot v_2 + a_{23}\cdot v_3 + a_{24}\cdot v_4\\ a_{31}\cdot v_1 + a_{32}\cdot v_2 + a_{33}\cdot v_3 + a_{34}\cdot v_4 \end{bmatrix}

हालाँकि, इसके बजाय हम matrix $A$ को कई vectors के समूह में विभाजित करने के बारे में सोच सकते हैं, कुछ इस प्रकार:

\mathbf{A} = \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \end{bmatrix} , \begin{bmatrix} a_{12} \\ a_{22} \\ a_{32} \end{bmatrix} , \begin{bmatrix} a_{13} \\ a_{23} \\ a_{33} \end{bmatrix} , \begin{bmatrix} a_{14} \\ a_{24} \\ a_{34} \end{bmatrix}

और प्रत्येक vector को vector $\mathbf{v}$ के एक scalar से गुणा करके:

\mathbf{A}\cdot \mathbf{v} = \begin{bmatrix} a_{11} \\ a_{21} \\ a_{31} \end{bmatrix}\cdot v_1 + \begin{bmatrix} a_{12} \\ a_{22} \\ a_{32} \end{bmatrix}\cdot v_2 + \begin{bmatrix} a_{13} \\ a_{23} \\ a_{33} \end{bmatrix}\cdot v_3 + \begin{bmatrix} a_{14} \\ a_{24} \\ a_{34} \end{bmatrix}\cdot v_4

हमने $\mathbf{A}$ और $\mathbf{v}$ के बीच matrix multiplication को पूरी तरह से vector addition और scalar multiplication के रूप में व्यक्त किया है।

चूँकि हमने पहले यह स्थापित किया था कि एक finite field में addition के अंतर्गत vectors का group, finite field में addition के अंतर्गत polynomials के group के homomorphic होता है, इसलिए हम उपरोक्त गणना को vectors को दर्शाने वाले polynomials के रूप में व्यक्त कर सकते हैं।

संक्षेप में यह टेस्ट करना कि $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$

मान लीजिए कि हमारे पास matrix $\mathbf{A}$ और $\mathbf{B}$ हैं, जैसे कि

\begin{align*} \mathbf{A} = \begin{bmatrix} 6 & 3\\ 4 & 7\\ \end{bmatrix}\\ \mathbf{B} = \begin{bmatrix} 3 & 9 \\ 12 & 6\\ \end{bmatrix} \end{align*}

और vectors $\mathbf{v}_1$ तथा $\mathbf{v}_2$ हैं

\begin{align*} \mathbf{v}_1 = \begin{bmatrix} 2 \\ 4 \\ \end{bmatrix}\\ \mathbf{v}_2 = \begin{bmatrix} 2 \\ 2 \\ \end{bmatrix} \end{align*}

हम यह टेस्ट करना चाहते हैं कि क्या

\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2

सत्य है।

जाहिर है कि हम matrix arithmetic को हल कर सकते हैं, लेकिन अंतिम जाँच में $n$ तुलनाओं (comparisons) की आवश्यकता होगी, जहाँ $n$ , $\mathbf{A}$ और $\mathbf{B}$ में पंक्तियों की संख्या है। हम इसे $\mathcal{O}(1)$ समय में करना चाहते हैं।

सबसे पहले, हम matrix multiplication $\mathbf{A}\mathbf{v}_1$ और $\mathbf{B}\mathbf{v}_2$ को addition के अंतर्गत vectors के group में बदलते हैं:

\begin{align*} \mathbf{A} &= \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix} , \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\\ \mathbf{B} &= \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix} , \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix} \end{align*}

अब हम polynomial group में

\begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}\cdot 2+ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}\cdot 4\stackrel{?}{=} \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}\cdot 2+ \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}\cdot 2

का homomorphic समतुल्य (equivalent) खोजना चाहते हैं।

आइए इनमें से प्रत्येक vector को $x$ वैल्यू $[1,2]$ पर polynomials में बदलें:

\underbrace{ \begin{bmatrix} 6 \\ 4 \\ \end{bmatrix}}_{p_1(x)}\cdot 2+ \underbrace{ \begin{bmatrix} 3 \\ 7 \\ \end{bmatrix}}_{p_2(x)}\cdot 4\stackrel{?}{=} \underbrace{ \begin{bmatrix} 3 \\ 12 \\ \end{bmatrix}}_{q_1(x)}\cdot 2+ \underbrace{ \begin{bmatrix} 9 \\ 6 \\ \end{bmatrix}}_{q_2(x)}\cdot 2

Langrage interpolation की गणना करने के लिए हम कुछ Python कोड का उपयोग करेंगे:

import galois
import numpy as np

p = 17
GF = galois.GF(p)

x_values = GF(np.array([1, 2]))

def L(v):
    return galois.lagrange_poly(x_values, v)

p1 = L(GF(np.array([6, 4])))
p2 = L(GF(np.array([3, 7])))
q1 = L(GF(np.array([3, 12])))
q2 = L(GF(np.array([9, 6])))

print(p1)
# 15x + 8 (mod 17)
print(p2)
# 4x + 16 (mod 17)
print(q1)
# 9x + 11 (mod 17)
print(q2)
# 14x + 12 (mod 17)

अंत में, हम Schwartz-Zippel Lemma का उपयोग करके यह जाँच कर सकते हैं कि क्या

p_1(x) \cdot 2+ p_2(x) \cdot 4 \stackrel{?}= q_1(x) \cdot 2 + q_2(x) \cdot 2

सत्य है:

import random
u = random.randint(0, p)
tau = GF(u) # a random point

left_hand_side = p1(tau) * GF(2) + p2(tau) * GF(4)
right_hand_side = q1(tau) * GF(2) + q2(tau) * GF(2)

assert left_hand_side == right_hand_side

अंतिम assert स्टेटमेंट $n$ की बजाय केवल एक तुलना (comparison) करके यह टेस्ट करने में सक्षम है कि क्या $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$ है।

R1CS से QAP: संक्षेप में यह टेस्ट करना कि $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$

चूँकि हम जानते हैं कि $\mathbf{A}\mathbf{v}_1 = \mathbf{B}\mathbf{v}_2$ का संक्षेप में टेस्ट कैसे किया जाता है, क्या हम यह भी संक्षेप में टेस्ट कर सकते हैं कि $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}=\mathbf{O}\mathbf{a}$ है?

Matrices में $m$ कॉलम होते हैं, इसलिए आइए प्रत्येक matrices को $m$ कॉलम vectors में विभाजित करें और प्रत्येक के लिए $m$ polynomials उत्पन्न करने के लिए उन्हें $(1, 2, ..., n)$ पर interpolate करें।

मान लीजिए $u_1(x), u_2(x), ..., u_m(x)$ वे polynomials हैं जो $\mathbf{L}$ के कॉलम vectors को interpolate करते हैं।

मान लीजिए $v_1(x), v_2(x), ..., v_m(x)$ वे polynomials हैं जो $\mathbf{R}$ के कॉलम vectors को interpolate करते हैं।

मान लीजिए $w_1(x), w_2(x), ..., w_m(x)$ वे polynomials हैं जो $\mathbf{O}$ के कॉलम vectors को interpolate करते हैं।

व्यापकता खोए बिना (Without loss of generality), मान लीजिए कि हमारे पास 4 कॉलम ( $m = 4$ ) और तीन पंक्तियाँ ( $n = 3$ ) हैं।

विज़ुअल रूप से, इसे इस प्रकार दर्शाया जा सकता है:

\begin{array}{c} \mathbf{L} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \\ \\ \qquad u_1(x) \quad u_2(x) \quad u_3(x) \quad u_4(x) \end{array} \begin{array}{c} \mathbf{R} = \begin{bmatrix} \quad r_{11} \quad& r_{12} \quad& r_{13} \quad& r_{14} \quad\\ \quad r_{21} \quad& r_{22} \quad& r_{23} \quad& r_{24} \quad\\ \quad r_{31} \quad& r_{32} \quad& r_{33} \quad& r_{34} \quad \end{bmatrix} \\ \\ \qquad v_1(x) \quad v_2(x) \quad v_3(x) \quad v_4(x) \end{array}

\begin{array}{c} \mathbf{O} = \begin{bmatrix} \quad o_{11} \quad& o_{12} \quad& o_{13} \quad& o_{14} \quad\\ \quad o_{21} \quad& o_{22} \quad& o_{23} \quad& o_{24} \quad\\ \quad o_{31} \quad& o_{32} \quad& o_{33} \quad& o_{34} \quad \end{bmatrix} \\ \\ \qquad w_1(x) \quad w_2(x) \quad w_3(x) \quad w_4(x) \end{array}

चूँकि किसी कॉलम vector को एक scalar से गुणा करना किसी polynomial को scalar से गुणा करने के homomorphic होता है, इसलिए प्रत्येक polynomials को witness के संबंधित एलिमेंट से गुणा किया जा सकता है।

उदाहरण के लिए,

\mathbf{L}\mathbf{a} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}

बन जाता है

\begin{align*} &=\begin{bmatrix} u_1(x) & u_2(x) & u_3(x) & u_4(x) \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}\\ &=a_1u_1(x) + a_2u_2(x) + a_3u_3(x) + a_4u_4(x)\\ &=\sum_{i=1}^4 a_iu_i(x) \end{align*}

ध्यान दें कि अंतिम परिणाम अधिकतम $n - 1$ डिग्री वाला एक एकल (single) polynomial है, क्योंकि $u_1(x), \ldots, u_n(x)$ में से प्रत्येक की डिग्री अधिकतम $n - 1$ है।
यह इस बात से स्पष्ट होता है कि हमने उन्हें कैसे बनाया: $\mathbf{L}$ के प्रत्येक कॉलम में $n$ एंट्रीज़ होती हैं, और Lagrange interpolation के माध्यम से $n$ पॉइंट्स को interpolate करने पर अधिकतम $n - 1$ डिग्री का polynomial उत्पन्न होता है।

सामान्य मामले में, $\mathbf{L}\mathbf{a}$ को प्रत्येक $m$ कॉलम को polynomials में बदलने के बाद

\sum_{i=1}^m a_iu_i(x)

के रूप में लिखा जा सकता है।

ऊपर दिए गए समान चरणों का उपयोग करके, R1CS $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}$ में प्रत्येक matrix-witness गुणनफल (product) को इस प्रकार बदला जा सकता है:

\begin{align*} \mathbf{L}\mathbf{a} \rightarrow \sum_{i=1}^m a_iu_i(x) \\ \mathbf{R}\mathbf{a} \rightarrow \sum_{i=1}^m a_iv_i(x) \\ \mathbf{O}\mathbf{a} \rightarrow \sum_{i=1}^m a_iw_i(x) \end{align*}

चूँकि प्रत्येक योग (sum) पद एक एकल (single) polynomial उत्पन्न करता है, हम उन्हें इस प्रकार लिख सकते हैं:

\begin{align*} \mathbf{L}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iu_i(x) = u(x)\\ \mathbf{R}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iv_i(x) = v(x)\\ \mathbf{O}\mathbf{a} &\rightarrow \sum_{i=1}^m a_iw_i(x) = w(x) \end{align*}

सभी कॉलम को interpolate क्यों करें?

Homomorphisms $\mathcal{L}(\mathbf{v}_1) + \mathcal{L}(\mathbf{v}_2) = \mathcal{L}(\mathbf{v}_1 + \mathbf{v}_2)$ और $\mathcal{L}(\lambda \mathbf{v}) = \lambda \mathcal{L}(\mathbf{v})$ के कारण, यदि हम $u(x)$ की गणना $\mathcal{L}(\mathbf{L}\mathbf{a})$ के रूप में करते हैं, तो हमें वही परिणाम मिलता है जो $\mathbf{L}$ के कॉलम पर Lagrange interpolation लागू करने और फिर प्रत्येक polynomials को $\mathbf{a}$ में मौजूद संबंधित एलिमेंट से गुणा करके परिणाम जोड़ने पर मिलता है।

दूसरे शब्दों में कहें तो,

\sum_{i=1}^m a_iu_i(x) = \mathcal{L}(\mathbf{L}\mathbf{a}) \mid u_i(x) \text{ is the Lagrange interpolation of column } i \text{ of } \mathbf{L}

तो फिर $m$ के बजाय केवल एक ही Lagrange interpolation की गणना क्यों न की जाए?

हमें इस बात में अंतर करना होगा कि QAP का उपयोग कौन कर रहा है। Verifier (और trusted setup जिसे हम बाद में कवर करेंगे) witness $\mathbf{a}$ को नहीं जानता है और इसलिए $\mathcal{L}(\mathbf{L}\mathbf{a})$ की गणना नहीं कर सकता है। यह एक ऑप्टिमाइज़ेशन है जो prover कर सकता है, लेकिन ZK प्रोटोकॉल में अन्य पक्ष इस ऑप्टिमाइज़ेशन का उपयोग नहीं कर सकते।

इसमें शामिल सभी पक्षों को QAP पर एक साझा सहमति होनी चाहिए – किसी भी proof और वेरिफिकेशन से पहले matrices के polynomial interpolations पर।

Polynomial डिग्री का असंतुलन (Polynomial degree imbalance)

हालाँकि, हम अंतिम परिणाम को सरलता से इस प्रकार व्यक्त नहीं कर सकते:

u(x)v(x) = w(x)

क्योंकि डिग्रियाँ मेल नहीं खाएँगी।

दो polynomials को एक साथ गुणा करने पर एक गुणनफल polynomial (product polynomial) प्राप्त होता है जिसकी डिग्री उन दो polynomials की डिग्री का योग होती है जिन्हें एक साथ गुणा किया जा रहा है।

चूँकि $u(x)$ , $v(x)$ , और $w(x)$ में से प्रत्येक की डिग्री $n - 1$ होगी, $u(x)v(x)$ की डिग्री सामान्यतः $2n - 2$ होगी और $w(x)$ की डिग्री $n - 1$ होगी, इसलिए वे बराबर नहीं होंगे, भले ही जिन अंतर्निहित (underlying) vectors को उन्होंने गुणा किया है, वे बराबर हों।

ऐसा इसलिए है क्योंकि जो homomorphisms हमने पहले स्थापित किए थे, वे केवल vector addition के बारे में दावा करते हैं, Hadamard product के बारे में नहीं।

हालाँकि, वह vector जिसे $u(x)v(x)$ interpolate करता है, अर्थात

((1, u(1)v(1)), (2, u(2)v(2)), ..., (n, u(n)v(n)))

वही vector है जिसे $w(x)$ interpolate करता है, अर्थात

((1, w(1)), \quad (2, w(2)), \quad ..., \quad (n, w(n)))

दूसरे शब्दों में

((1, u(1)v(1)), (2, u(2)v(2)), ..., (n, u(n)v(n))) = ((1, w(1)), (2, w(2)), ..., (n, w(n)))

यद्यपि “अंतर्निहित (underlying)” vectors बराबर हैं, उन्हें interpolate करने वाले polynomials बराबर नहीं हैं।

Underlying equality का उदाहरण

मान लीजिए कि $u(x)$ वह polynomial है जो

(1,\boxed{2}), (2,\boxed{4}), (3,\boxed{8})

को interpolate करता है, और $v(x)$ वह polynomial है जो

(1,\boxed{4}), (2,\boxed{2}), (3,\boxed{8})

को interpolate करता है।

यदि हम $u(x)$ को vector $[2,4,8]$ को interpolate करने वाला और $v(x)$ को vector $[4,2,8]$ को interpolate करने वाला मानते हैं, तो हम देख सकते हैं कि उनका product polynomial दोनों vectors के Hadamard product को interpolate करता है। $[2,4,8]$ और $[4,2,8]$ का Hadamard product $[8,8,64]$ है।

यदि हम $u(x)$ और $v(x)$ को एक साथ गुणा करते हैं, तो हमें $w(x) = 4x^4 - 18x^3 + 36x^2 - 42x + 28$ प्राप्त होता है।

हम नीचे दिए गए प्लॉट में देख सकते हैं कि product polynomial दोनों vectors के Hadamard product $[8, 8, 64]$ को interpolate करता है।

तो हम $w(x)$ को $u(x)v(x)$ के बराबर कैसे “बना” सकते हैं यदि वे $(1,2,...,n)$ पर समान $y$ वैल्यू को interpolate करते हैं?

$\mathbf{0}$ vector को interpolate करना

यदि $\mathbf{v_1} \circ \mathbf{v_2} = \mathbf{v_3}$ है, तो $\mathbf{v_1} \circ \mathbf{v_2} = \mathbf{v_3} + \mathbf{0}$ होगा।

$\mathbf{0}$ को Lagrange interpolation के साथ interpolate करने और $f(x) = 0$ प्राप्त करने के बजाय (याद रखें कि Lagrange interpolation सबसे कम डिग्री वाले interpolating polynomial को खोजता है), हम एक उच्च डिग्री वाले polynomial का उपयोग कर सकते हैं जो डिग्री के असंतुलन (mismatch) को संतुलित करेगा।

उदाहरण के लिए, नीचे दी गई छवि में काला polynomial ( $b(x)$ ), $[(1,0), (2,0), (3,0)]$ को interpolate करता है:

अब, चूँकि $4x^4 -18x^3 + 8x^2 + 42x - 36$ , $[0,0,0]$ का एक मान्य (valid) interpolation है, हम अपने मूल समीकरण को इस प्रकार लिख सकते हैं:

$u(x)v(x) = w(x) + b(x)$

और यह समीकरण संतुलित (balanced) हो जाएगा!

$b(x)$ की गणना आसानी से $u(x)v(x) - w(x)$ के रूप में की गई थी (नीला polynomial माइनस लाल polynomial)।

हालाँकि, हम prover को कोई भी $b(x)$ चुनने की अनुमति नहीं दे सकते, अन्यथा वे एक ऐसा $b(x)$ चुन सकते हैं जो $u(x)v(x)$ और $w(x)$ को संतुलित कर दे, भले ही वे समान vector (हमारे उदाहरण में $[8, 8, 64]$ ) को interpolate न करते हों। $b(x)$ को चुनने में prover के पास बहुत अधिक लचीलापन (flexibility) है। विशेष रूप से, हम यह आवश्यक करना चाहते हैं कि $b(x)$ के roots $x = 1,2,\dots,n$ पर हों – अर्थात्, $\mathbf{0}$ vector को interpolate करें। इस तरह, $\mathbf{v}_1 \circ \mathbf{v}_2 = \mathbf{v}_3 + \mathbf{0}$ का polynomial ट्रांसफॉर्मेशन अभी भी अंतर्निहित (underlying) vectors का सम्मान करता है।

$b(x)$ के उनके चुनाव को सीमित करने के लिए, हम निम्नलिखित प्रमेय (theorem) का उपयोग कर सकते हैं:

Polynomial गुणनफल (product) के roots का union

Theorem: यदि $h(x) = f(x)g(x)$ है और $f(x)$ के roots का सेट $\set{r_f}$ है तथा $g(x)$ के roots का सेट $\set{r_g}$ है, तो $h(x)$ के roots $\set{r_f} \cup \set{r_g}$ होंगे।

उदाहरण

मान लीजिए $f(x) = (x - 3)(x - 4)$ और $g(x) = (x - 5)(x - 6)$ है। तब $h(x) = f(x)g(x)$ के roots $\set{3,4,5,6}$ होंगे।

हम यह लागू करने (enforce) के लिए उपरोक्त theorem का उपयोग कर सकते हैं कि $b(x)$ के roots $x = 1,2,\dots,n$ पर हों।

$b(x)$ को zero vector होने के लिए बाध्य करना

हम $b(x)$ को $b(x) = h(x)t(x)$ में विघटित (decompose) करते हैं जहाँ $t(x)$ यह polynomial है:

t(x) = (x-1)(x-2)\dots(x-n)

तब $t(x)$ के साथ गुणा किया गया कोई भी polynomial भी zero vector होगा, क्योंकि इसके roots $x = 1,2,\dots,n$ पर होने चाहिए।

इसलिए, हम अपने समीकरण में $b(x)$ को $h(x)t(x)$ से बदल देंगे।

इस प्रकार, हमारी समानता (equality) बन जाएगी:

u(x)v(x) = w(x) + h(x)t(x)

हम बुनियादी बीजगणित (algebra) का उपयोग करके $h(x)$ की गणना कर सकते हैं:

h(x) = \frac{u(x)v(x) - w(x)}{t(x)}

QAP एंड-टू-एंड

मान लीजिए कि हमारे पास matrices $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ तथा witness vector $\mathbf{a}$ के साथ एक R1CS है।

\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} = \mathbf{O}\mathbf{a}

Matrices में $n$ कॉलम और $m$ पंक्तियाँ हैं जहाँ $n = 4$ और $m = 3$ है।

अर्थात्, $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ इस प्रकार हैं:

\begin{array}{c} \mathbf{L} = \begin{bmatrix} \quad l_{11} \quad& l_{12} \quad& l_{13} \quad& l_{14} \quad\\ \quad l_{21} \quad& l_{22} \quad& l_{23} \quad& l_{24} \quad\\ \quad l_{31} \quad& l_{32} \quad& l_{33} \quad& l_{34} \quad \end{bmatrix} \\ \\ \mathbf{R} = \begin{bmatrix} \quad r_{11} \quad& r_{12} \quad& r_{13} \quad& r_{14} \quad\\ \quad r_{21} \quad& r_{22} \quad& r_{23} \quad& r_{24} \quad\\ \quad r_{31} \quad& r_{32} \quad& r_{33} \quad& r_{34} \quad \end{bmatrix} \\ \\ \mathbf{O} = \begin{bmatrix} \quad o_{11} \quad& o_{12} \quad& o_{13} \quad& o_{14} \quad\\ \quad o_{21} \quad& o_{22} \quad& o_{23} \quad& o_{24} \quad\\ \quad o_{31} \quad& o_{32} \quad& o_{33} \quad& o_{34} \quad \end{bmatrix} \end{array}

और witness vector $\mathbf{a}$ है:

\mathbf{a} = \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix}

हम प्रत्येक matrices को $m$ कॉलम vectors में विभाजित करते हैं और प्रत्येक के लिए $m$ polynomials उत्पन्न करने के लिए उन्हें $(1, 2, ..., n)$ पर interpolate करते हैं।

\begin{array}{c} \mathbf{L} = \underbrace{\begin{bmatrix} l_{11} \\l_{12} \\ l_{13} \\ l_{14} \\ \end{bmatrix}}_{u_1(x)} \quad \underbrace{\begin{bmatrix} l_{21} \\ l_{22} \\ l_{23} \\ l_{24} \end{bmatrix}}_{u_2(x)} \quad \underbrace{\begin{bmatrix} l_{31} \\ l_{32} \\ l_{33} \\ l_{34} \\ \end{bmatrix}}_{u_3(x)} \quad \underbrace{\begin{bmatrix} l_{41} \\ l_{42} \\ l_{43} \\ l_{44} \end{bmatrix}}_{u_4(x)} \end{array}

\begin{array}{c} \mathbf{R} = \underbrace{\begin{bmatrix} r_{11} \\r_{12} \\ r_{13} \\ r_{14} \\ \end{bmatrix}}_{v_1(x)} \quad \underbrace{\begin{bmatrix} r_{21} \\ r_{22} \\ r_{23} \\ r_{24} \end{bmatrix}}_{v_2(x)} \quad \underbrace{\begin{bmatrix} r_{31} \\ r_{32} \\ r_{33} \\ r_{34} \\ \end{bmatrix}}_{v_3(x)} \quad \underbrace{\begin{bmatrix} r_{41} \\ r_{42} \\ r_{43} \\ r_{44} \end{bmatrix}}_{v_4(x)} \end{array}

\begin{array}{c} \mathbf{O} = \underbrace{\begin{bmatrix} o_{11} \\o_{12} \\ o_{13} \\ o_{14} \\ \end{bmatrix}}_{w_1(x)} \quad \underbrace{\begin{bmatrix} o_{21} \\ o_{22} \\ o_{23} \\ o_{24} \end{bmatrix}}_{w_2(x)} \quad \underbrace{\begin{bmatrix} o_{31} \\ o_{32} \\ o_{33} \\ o_{34} \\ \end{bmatrix}}_{w_3(x)} \quad \underbrace{\begin{bmatrix} o_{41} \\ o_{42} \\ o_{43} \\ o_{44} \end{bmatrix}}_{w_4(x)} \end{array}

प्रत्येक matrix-vector गुणनफल (products) $\mathbf{L}\mathbf{a}$ , $\mathbf{R}\mathbf{a}$ , और $\mathbf{O}\mathbf{a}$ निम्नलिखित polynomials के homomorphically समतुल्य (equivalent) हैं:

\begin{align*} \sum_{i=1}^4 a_iu_i(x) &= a_1u_1(x) + a_2u_2(x) + a_3u_3(x) + a_4u_4(x) = u(x) \\ \sum_{i=1}^m a_iv_i(x) &= a_1v_1(x) + a_2v_2(x) + a_3v_3(x) + a_4v_4(x) = v(x) \\ \sum_{i=1}^m a_iw_i(x) &= a_1w_1(x) + a_2w_2(x) + a_3w_3(x) + a_4w_4(x) = w(x) \\ \end{align*}

हमारे मामले में, $t(x)$ होगा

t(x) = (x - 1)(x - 2)(x - 3)

और $h(x)$ होगा

h(x) = \frac{u(x)v(x) - w(x)}{t(x)}

मूल R1CS के QAP प्रतिनिधित्व (representation) का अंतिम सूत्र (formula) है:

\sum_{i=1}^4 a_iu_i(x)\sum_{i=1}^4 a_iv_i(x) = \sum_{i=1}^4 a_iw_i(x) + h(x)t(x)

QAP के लिए अंतिम सूत्र (Final formula)

एक QAP निम्नलिखित सूत्र है:

\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m a_iv_i(x) = \sum_{i=1}^m a_iw_i(x) + h(x)t(x)

जहाँ $u_i(x)$ , $v_i(x)$ , और $w_i(x)$ वे polynomials हैं जो क्रमशः $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ के कॉलम को interpolate करते हैं, $t(x)$ , $(x - 1)(x - 2)...(x - n)$ है, जहाँ $n$ , $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ में पंक्तियों की संख्या है, तथा $h(x)$ है:

h(x) = \frac{\sum_{i=1}^ma_iu_i(x)\sum_{i=1}^ma_iv_i(x) - \sum_{i=1}^ma_iw_i(x)}{t(x)}

Quadratic Arithmetic Programs के साथ Succinct Zero Knowledge Proofs

मान लीजिए हमारे पास एक ऐसा तरीका हो जिससे verifier, prover को एक रैंडम वैल्यू $\tau$ भेज सके और prover इसके जवाब में यह दे:

\begin{align*} A &= u(\tau)\\ B &= v(\tau)\\ C &= w(\tau) + h(\tau)t(\tau) \end{align*}

Verifier यह जाँच कर सकता है कि $AB = C$ है और यह स्वीकार कर सकता है कि prover के पास एक मान्य (valid) witness $\mathbf{a}$ है जो R1CS और QAP दोनों को संतुष्ट करता है।

हालाँकि, इसके लिए verifier को यह विश्वास करना होगा कि prover, polynomials का सही मूल्यांकन (evaluate) कर रहा है, और हमारे पास prover को ऐसा करने के लिए मजबूर करने का कोई तंत्र (mechanism) नहीं है।

अगले अध्याय में, हम इस अध्याय में हमारी चर्चा के आधार पर एक R1CS को QAP में बदलने के लिए Python कोड दिखाएंगे।

फिर हम यह समस्या हल करने के लिए trusted setups पर चर्चा करेंगे कि prover से ईमानदारी से polynomials का मूल्यांकन कैसे करवाया जाए।

मूल रूप से 23 अगस्त, 2023 को प्रकाशित