R1CS से QAP में परिवर्तन को कम अमूर्त (abstract) बनाने के लिए, आइए एक वास्तविक उदाहरण का उपयोग करें।

मान लीजिए कि हम arithmetic circuit को एनकोड कर रहे हैं

एक Rank 1 Constraint System में परिवर्तित होने पर, यह बन जाता है

हमें उस finite field की एक विशेषता (characteristic) चुननी होगी जिस पर हम यह काम करेंगे। जब हम बाद में इसे elliptic curves के साथ जोड़ते हैं, तो हमारे prime field का ऑर्डर elliptic curve के ऑर्डर के बराबर होना चाहिए। (इन दोनों का मेल न होना एक बहुत ही सामान्य गलती है)।

लेकिन अभी के लिए, हम इसे प्रबंधनीय (manageable) बनाने के लिए एक छोटी संख्या चुनेंगे। हम अभाज्य संख्या (prime number) 79 चुनेंगे।

सबसे पहले, हम अपने मैट्रिसेस $\mathbf{L}$, $\mathbf{R}$, और $\mathbf{O}$ को इस प्रकार परिभाषित करते हैं:

Copy
import numpy as np

# 1, out, x, y, v1, v2, v3
L = np.array([
    [0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, -5, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 1],
])

R = np.array([
    [0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
])

O = np.array([
    [0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, -1, 0],
])

यह सत्यापित करने के लिए कि हमने R1CS का निर्माण सही ढंग से किया है (मैन्युअल रूप से करते समय गलती करना बहुत आसान है!) हम एक वैध (valid) witness बनाते हैं और मैट्रिक्स गुणा (matrix multiplication) करते हैं:

Copy
x = 4
y = -2
v1 = x * x
v2 = v1 * v1        # x^4
v3 = -5*y * y
z = v3*v1 + v2    # -5y^2 * x^2

# witness
a = np.array([1, z, x, y, v1, v2, v3])

assert all(np.equal(np.matmul(L, a) * np.matmul(R, a), np.matmul(O, a))), "not equal"

Python में Finite Field Arithmetic

अगला कदम इसे एक field array में बदलना है। Numpy में मॉड्यूलर अंकगणित (modular arithmetic) करना बहुत ही अव्यवस्थित हो जाएगा, लेकिन galois लाइब्रेरी के साथ यह सीधा और आसान है। इसे finite fields पर हमारे लेख में पेश किया गया था, लेकिन यहाँ इसका उपयोग करने के तरीके का एक त्वरित रीकैप (quick recap) दिया गया है:

Copy
import galois

GF = galois.GF(79)

a = GF(70)
b = GF(10)

print(a + b)
# prints 1

हम इसे नकारात्मक मान (negative values) जैसे GF(-1) नहीं दे सकते, अन्यथा यह एक अपवाद (exception) फेंक देगा। नकारात्मक संख्याओं को field में उनके सर्वांगसम प्रतिनिधित्व (congruent representation) में बदलने के लिए, हम उनमें curve order जोड़ सकते हैं। सकारात्मक मानों को “ओवरफ्लो” होने से बचाने के लिए, हम curve order के साथ modulus लेते हैं।

Copy
L = (L + 79) % 79
R = (R + 79) % 79
O = (O + 79) % 79

हमारे नए मैट्रिसेस हैं

Copy
## New values of L, R, O
'''
L

[[ 0  0  1  0  0  0  0]
 [ 0  0  0  0  1  0  0]
 [ 0  0  0 74  0  0  0]
 [ 0  0  0  0  0  0  1]]

R

[[ 0  0  1  0  0  0  0]
 [ 0  0  0  0  1  0  0]
 [ 0  0  0  1  0  0  0]
 [ 0  0  0  0  1  0  0]]

O

[[ 0  0  0  0  1  0  0]
 [ 0  0  0  0  0  1  0]
 [ 0  0  0  0  0  0  1]
 [ 0  1  0  0  0 78  0]]
'''

अब हम केवल GF के साथ रैप करके उन्हें field arrays में बदल सकते हैं। हमें अपने witness की फिर से गणना करने की भी आवश्यकता होगी, क्योंकि इसमें नकारात्मक मान हैं।

Copy
L_galois = GF(L)
R_galois = GF(R)
O_galois = GF(O)

x = GF(4)
y = GF(-2 + 79) # we are using 79 as the field size, so 79 - 2 is -2
v1 = x * x
v2 = v1 * v1         # x^4
v3 = GF(-5 + 79)*y * y
out = v3*v1 + v2    # -5y^2 * x^2

witness = GF(np.array([1, out, x, y, v1, v2, v3]))

assert all(np.equal(np.matmul(L_galois, witness) * np.matmul(R_galois, witness), np.matmul(O_galois, witness))), "not equal"

Finite fields में Polynomial interpolation

अब, हमें मैट्रिसेस के प्रत्येक कॉलम को galois पॉलिनॉमियल्स की एक सूची में बदलना होगा जो कॉलम को इंटरपोलेट करते हैं। जिन पॉइंट्स को हम इंटरपोलेट करेंगे वे x = [1,2,3,4] हैं, क्योंकि हमारे पास 4 पंक्तियाँ (rows) हैं।

Copy
def interpolate_column(col):
    xs = GF(np.array([1,2,3,4]))
    return galois.lagrange_poly(xs, col)

# axis 0 is the columns.
# apply_along_axis is the same as doing a for loop over the columns and collecting the results in an array
U_polys = np.apply_along_axis(interpolate_column, 0, L_galois)
V_polys = np.apply_along_axis(interpolate_column, 0, R_galois)
W_polys = np.apply_along_axis(interpolate_column, 0, O_galois)

यदि हम अपने मैट्रिसेस की सामग्री को फिर से देखें, तो हम यह उम्मीद करते हैं कि U_polys और V_polys के पहले दो पॉलिनॉमियल्स शून्य होंगे, और W_polys का पहला कॉलम भी शून्य होगा।

हम निम्नलिखित sanity check चलाते हैं:

Copy
print(U_polys[:2])
print(V_polys[:2])
print(W_polys[:1])

# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79)) Poly(0, GF(79))]# [Poly(0, GF(79))]

टर्म Poly(0, GF(79)) बस एक ऐसा पॉलिनॉमियल है जहाँ सभी गुणांक (coefficients) शून्य होते हैं।

पाठकों को प्रोत्साहित किया जाता है कि वे R1CS में दिए गए मानों पर पॉलिनॉमियल्स का मूल्यांकन करें ताकि यह देखा जा सके कि वे मैट्रिक्स मानों को सही ढंग से इंटरपोलेट करते हैं।

h(x) की गणना

हम पहले से ही जानते हैं कि $t(x)$, $(x - 1)(x - 2)(x - 3)(x - 4)$ होगा क्योंकि इसमें चार पंक्तियाँ हैं।

याद दिलाने के तौर पर, यह Quadratic Arithmetic Program का सूत्र है। वेक्टर $\mathbf{a}$ witness है:

प्रत्येक टर्म witness का कॉलम-इंटरपोलेटिंग पॉलिनॉमियल्स के साथ inner product ले रहा है। अर्थात्, प्रत्येक योग टर्म (summation term) प्रभावी रूप से $[a₁, …, aₘ]$ और $[u₁(x), ..., uₘ(x)]$ के बीच का inner product है।

Copy
def inner_product_polynomials_with_witness(polys, witness):
    mul_ = lambda x, y: x * y
    sum_ = lambda x, y: x + y
    return reduce(sum_, map(mul_, polys, witness))

term_1 = inner_product_polynomials_with_witness(U_polys, witness)

term_2 = inner_product_polynomials_with_witness(V_polys, witness)

term_3 = inner_product_polynomials_with_witness(W_polys, witness)

$h(x)$ की गणना करने के लिए, हम बस इसके लिए हल (solve) करते हैं। ध्यान दें कि हम $h(x)$ की गणना तब तक नहीं कर सकते जब तक कि हमारे पास एक वैध witness न हो, अन्यथा एक शेषफल (remainder) बचेगा।

Copy
# t = (x - 1)(x - 2)(x - 3)(x - 4)
t = galois.Poly([1, 78], field = GF) * galois.Poly([1, 77], field = GF) * galois.Poly([1, 76], field = GF) * galois.Poly([1, 75], field = GF)

h = (term_1 * term_2 - term_3) // t

poly1d from numpy के विपरीत, galois लाइब्रेरी हमें यह नहीं बताएगी कि कोई शेषफल है या नहीं, इसलिए हमें यह जांचने की आवश्यकता है कि क्या QAP सूत्र अभी भी सत्य है।

Copy
assert term_1 * term_2 == term_3 + h * t, "division has a remainder"

ऊपर निष्पादित (executed) की गई जांच काफी हद तक उसी के समान है जिसकी जांच verifier करेगा।

उपरोक्त योजना (scheme) काम नहीं करेगी जब हम किसी trusted setup से छिपे हुए बिंदु (hidden point) पर पॉलिनॉमियल्स का मूल्यांकन करेंगे। हालाँकि, trusted setup करने वाले कंप्यूटर को अभी भी उपरोक्त कई गणनाओं को निष्पादित करना होगा।

सारांश

इस लेख में, हम R1CS को QAP में बदलने के लिए Python कोड प्रस्तुत करते हैं।

RareSkills के साथ और जानें

यह सामग्री हमारे Zero Knowledge Course से है।