बीजगणितीय सर्किट को R1CS (Rank One Constraint System) में बदलना

Last updated on Jan 22, 2026

यह लेख समझाता है कि arithmetic constraints के एक सेट को Rank One Constraint System (R1CS) में कैसे बदला जाए।

इस संसाधन का ध्यान कार्यान्वयन (implementation) पर है: हम इस रूपांतरण (transformation) को करने के अन्य सामग्रियों की तुलना में बहुत अधिक कॉर्नर केसेस (corner cases) को कवर करते हैं, ऑप्टिमाइज़ेशन (optimizations) पर चर्चा करते हैं, और समझाते हैं कि Circom लाइब्रेरी इसे कैसे पूरा करती है।

पूर्व आवश्यकताएँ (Prerequisites)

हम मान कर चलते हैं कि पाठक यह समझता है कि गणना (computation) की वैधता को दर्शाने के लिए arithmetic circuits (zk circuits) का उपयोग कैसे किया जाता है।
पाठक modular arithmetic से परिचित है। यहाँ सभी ऑपरेशन एक finite field में होते हैं, इसलिए $-5$ का वास्तव में अर्थ है $p$ के मॉड्यूलो $5$ का additive inverse और $2/3$ का अर्थ है $p$ के मॉड्यूलो $3$ का multiplicative inverse गुणा $2$ ।

Rank 1 Constraint System का अवलोकन (Overview)

Rank 1 Constraint System (R1CS) एक arithmetic circuit है जिसमें यह आवश्यकता होती है कि प्रत्येक equality constraint में एक गुणा (multiplication) हो (और जोड़/additions की संख्या पर कोई प्रतिबंध नहीं होता है)।

यह arithmetic circuit के प्रतिनिधित्व (representation) को bilinear pairings के उपयोग के अनुकूल बनाता है। पेयरिंग $G_1 \bullet G_2 \rightarrow G_T$ के आउटपुट को फिर से पेयर नहीं किया जा सकता है, क्योंकि $G_T$ के किसी एलिमेंट का उपयोग किसी अन्य पेयरिंग के इनपुट के हिस्से के रूप में नहीं किया जा सकता है। इसलिए, हम प्रति constraint केवल एक गुणा की अनुमति देते हैं।

Witness वेक्टर

एक arithmetic circuit में, witness उन सभी सिग्नल्स के लिए एक असाइनमेंट है जो समीकरण (equation) के constraints को संतुष्ट करता है।

Rank 1 Constraint System में, witness वेक्टर एक $1 \times n$ वेक्टर होता है जिसमें सभी इनपुट वेरिएबल्स, आउटपुट वेरिएबल और मध्यवर्ती (intermediate) मानों का मान होता है। यह दर्शाता है कि आपने इनपुट, आउटपुट और सभी मध्यवर्ती मानों को जानते हुए, शुरू से अंत तक सर्किट को निष्पादित (execute) किया है।

परंपरा के अनुसार, कुछ गणनाओं को आसान बनाने के लिए पहला एलिमेंट हमेशा 1 होता है, जिसे हम बाद में प्रदर्शित करेंगे।

उदाहरण के लिए, यदि हमारे पास constraint है

z = x^2y

जिसके समाधान को जानने का हम दावा करते हैं, तो इसका मतलब यह होना चाहिए कि हम $x$ , $y$ , और $z$ को जानते हैं। क्योंकि Rank One Constraint Systems में प्रति constraint ठीक एक गुणा की आवश्यकता होती है, उपरोक्त constraints वाले बहुपद (polynomial) को इस प्रकार लिखा जाना चाहिए:

\begin{align*} v₁ = xx \\ z = v₁y \end{align*}

Witness का मतलब है कि हम न केवल $x$ , $y$ , और $z$ को जानते हैं, बल्कि हमें इस विस्तारित रूप (expanded form) में हर मध्यवर्ती (intermediate) वेरिएबल को भी जानना चाहिए। विशेष रूप से, हमारा witness एक वेक्टर है:

[1, z, x, y, v₁]

जहाँ प्रत्येक पद (term) का एक मान होता है जो ऊपर दिए गए constraints को संतुष्ट करता है।

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

[1, 18, 3, 2, 9]

एक वैध (valid) witness है क्योंकि जब हम मानों को रखते हैं,

[\text{constant} = 1, z = 18, x = 3, y = 2, v₁ = 9]

यह constraints को संतुष्ट करता है

\begin{align*} v_1 = x*x \rightarrow 9 = 3\cdot3\\ z = v_1*y \rightarrow 18 = 9\cdot2 \end{align*}

इस उदाहरण में अतिरिक्त 1 पद (term) का उपयोग नहीं किया गया है और यह एक सुविधा है जिसे हम बाद में समझाएंगे।

उदाहरण 1: $z = x \cdot y$ को Rank 1 Constraint System में बदलना

हमारे उदाहरण के लिए, हम कहेंगे कि हम $41 \times 103 = 4223$ साबित कर रहे हैं।

इसलिए, हमारा witness वेक्टर $[1, z, x, y]$ के असाइनमेंट के रूप में $[1, 4223, 41, 103]$ है।

इससे पहले कि हम एक R1CS बना सकें, हमारे constraints का रूप (form) यह होना चाहिए:

result = left_hand_side × right_hand_side

हमारे लिए सौभाग्य से, यह पहले से ही है

\underbrace{z}_\text{result} = \underbrace{x}_\text{left hand side} \times \underbrace{y}_\text{right hand side}

यह स्पष्ट रूप से एक सामान्य (trivial) उदाहरण है, लेकिन सामान्य उदाहरण आमतौर पर शुरुआत करने के लिए एक बेहतरीन जगह होते हैं।

एक वैध (valid) R1CS बनाने के लिए, आपको ऐसे सूत्रों की एक सूची की आवश्यकता होती है जिनमें ठीक एक गुणा (multiplication) हो।

हम बाद में चर्चा करेंगे कि उन मामलों को कैसे संभाला जाए जिनमें ठीक एक गुणा नहीं होता है जैसे $z = x³$ या $z = x³ + y$ ।

हमारा लक्ष्य इस रूप के समीकरणों की एक प्रणाली (system) बनाना है:

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

जहाँ $O$ , $L$ , और $R$ , $n$ x $m$ ( $n$ पंक्तियाँ/rows और $m$ स्तंभ/columns) आकार के मैट्रिक्स (matrices) हैं।

मैट्रिक्स $\mathbf{L}$ गुणा के बाईं ओर के वेरिएबल को एन्कोड करता है और $\mathbf{R}$ गुणा के दाईं ओर के वेरिएबल्स को एन्कोड करता है। $\mathbf{O}$ परिणाम (result) वेरिएबल्स को एन्कोड करता है। वेक्टर $\mathbf{a}$ witness वेक्टर है।

विशेष रूप से, $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ ऐसे मैट्रिक्स हैं जिनमें witness वेक्टर $\mathbf{a}$ के समान ही स्तंभों (columns) की संख्या है, और प्रत्येक स्तंभ उसी वेरिएबल का प्रतिनिधित्व करता है जिसका उपयोग इंडेक्स (index) कर रहा है।

तो हमारे उदाहरण के लिए, witness में 4 एलिमेंट्स $(1, z, x, y)$ हैं इसलिए हमारे प्रत्येक मैट्रिक्स में 4 स्तंभ होंगे, इसलिए $m = 4$ ।

पंक्तियों (rows) की संख्या सर्किट में constraints की संख्या के अनुरूप होगी। हमारे मामले में, हमारे पास केवल एक constraint है: $z = x * y$ , इसलिए हमारे पास केवल एक पंक्ति होगी, इसलिए $n = 1$ ।

आइए सीधे उत्तर पर चलते हैं और समझाते हैं कि हमने इसे कैसे प्राप्त किया।

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

\underbrace{\begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix}}_{\mathbf{O}}\mathbf{a} = \underbrace{\begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix}}_{\mathbf{L}}\mathbf{a}\circ \underbrace{\begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix}}_{\mathbf{R}}\mathbf{a}

\begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}= \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}\circ \begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ 4223 \\ 41 \\ 103 \\ \end{bmatrix}

इस उदाहरण में, मैट्रिक्स का प्रत्येक आइटम एक इंडिकेटर (indicator) वेरिएबल के रूप में कार्य करता है कि जिस वेरिएबल से स्तंभ संबंधित है वह मौजूद है या नहीं। (तकनीकी रूप से, यह वेरिएबल का गुणांक/coefficient है, लेकिन हम उस पर बाद में आएंगे)।

बाएं हाथ के पदों (left hand terms) के लिए, गुणा के बाईं ओर मौजूद एकमात्र वेरिएबल $x$ है, इसलिए यदि स्तंभ $[1, z, x, y]$ का प्रतिनिधित्व करते हैं, तो…

$\mathbf{L}$ $[0, 0, 1, 0]$ है, क्योंकि $x$ मौजूद है, और अन्य कोई भी वेरिएबल मौजूद नहीं है।

$\mathbf{R}$ $[0, 0, 0, 1]$ है क्योंकि गुणा के दाईं ओर एकमात्र वेरिएबल $y$ है, और

$\mathbf{O}$ $[0, 1, 0, 0]$ है क्योंकि गुणा के “आउटपुट” में हमारे पास केवल $z$ वेरिएबल है।

हमारे पास कहीं भी कोई स्थिरांक (constants) नहीं हैं इसलिए 1 का स्तंभ हर जगह शून्य है (हम बाद में चर्चा करेंगे कि यह गैर-शून्य (non-zero) कब होता है)।

यह समीकरण सही है, जिसे हम Python में सत्यापित (verify) कर सकते हैं

import numpy as np

# define the matrices
O = np.matrix([[0,1,0,0]])
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])

# witness vector
a = np.array([1, 4223, 41, 103])

# Multiplication `*` is element-wise, not matrix multiplication.
# Result contains a bool indicating an element-wise indicator that the equality is true for that element.
result = np.matmul(O, a) == np.matmul(L, a) * np.matmul(R, a) 

# check that every element-wise equality is true
assert result.all(), "result contains an inequality"

आप सोच रहे होंगे कि इसका क्या मतलब है, क्या हम बस यह नहीं कह रहे हैं कि $41 \times 103 = 4223$ बहुत कम संक्षिप्त (compact) तरीके से?

आप सही होंगे।

एक R1CS काफी विस्तृत (verbose) हो सकता है, लेकिन वे Quadratic Arithmetic Programs (QAPs) में अच्छी तरह से मैप होते हैं, जिन्हें संक्षिप्त (succinct) बनाया जा सकता है। लेकिन हम यहाँ QAPs पर विचार नहीं करेंगे।

लेकिन यह R1CS का एक महत्वपूर्ण बिंदु है। एक R1CS बिल्कुल वही जानकारी संप्रेषित (communicate) करता है जो मूल arithmetic constraints करते हैं, लेकिन प्रति equality constraint केवल एक गुणा के साथ। इस उदाहरण में, हमारे पास केवल एक constraint है, लेकिन हम अगले उदाहरण में और जोड़ेंगे।

उदाहरण 2: r = x * y * z * u को बदलना

इस थोड़े अधिक जटिल उदाहरण में, अब हमें मध्यवर्ती (intermediate) वेरिएबल्स से निपटना होगा। हमारी गणना की प्रत्येक पंक्ति में केवल एक गुणा हो सकता है, इसलिए हमें अपने समीकरण को इस प्रकार तोड़ना होगा:

\begin{align*} v_1 &= xy \\ v_2 &= zu \\ r &= v_1v_2 \end{align*}

ऐसा कोई नियम नहीं है जो कहता हो कि हमें इसे इस तरह तोड़ना था, निम्नलिखित भी वैध है:

\begin{align*} v_1 &= xy \\ v_2 &= v_1z \\ r &= v_2u \end{align*}

हम इस उदाहरण के लिए पहले रूपांतरण (transformation) का उपयोग करेंगे।

$\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ का आकार

चूँकि हम 7 वेरिएबल्स $(r, x, y, z, u, v_1, v_2)$ के साथ काम कर रहे हैं, हमारे witness वेक्टर में आठ एलिमेंट्स होंगे (पहला स्थिरांक 1 होगा) और हमारे मैट्रिक्स में आठ स्तंभ (columns) होंगे।

क्योंकि हमारे पास तीन constraints हैं, मैट्रिक्स में तीन पंक्तियाँ (rows) होंगी।

बाएं हाथ के पद (Left hand terms) और दाएं हाथ के पद (right hand terms)

यह उदाहरण “left hand term” और “right hand term” के विचार को दृढ़ता से लागू करेगा। विशेष रूप से, $x$ , $z$ , और $v_1$ left hand terms हैं, और $y$ , $u$ , और $v_2$ right hand terms हैं।

\underbrace{ \begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} }_\text{ Output Terms } \begin{matrix} =\\ =\\ = \end{matrix} \underbrace{ \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} }_\text{ Left Hand Terms } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underbrace{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix} }_\text{ Right Hand Terms }

Left hand terms से मैट्रिक्स $\mathbf{L}$ का निर्माण

आइए मैट्रिक्स $\mathbf{L}$ का निर्माण करें। हम जानते हैं कि इसमें तीन पंक्तियाँ होंगी (चूँकि तीन constraints हैं) और आठ स्तंभ होंगे (चूँकि आठ वेरिएबल्स हैं)।

\begin{bmatrix} & l_{1,2} & l_{1,3} & l_{1,4} & l_{1,5} & l_{1,6} & l_{1,7} & l_{1,8} \\ & l_{2,2} & l_{2,3} & l_{2,4} & l_{2,5} & l_{2,6} & l_{2,7} & l_{2,8} \\ & l_{3,2} & l_{3,3} & l_{3,4} & l_{3,5} & l_{3,6} & l_{3,7} & l_{3,8} \\ \end{bmatrix}

हमारे witness वेक्टर को इसके द्वारा गुणा किया जाएगा, इसलिए आइए अपने witness वेक्टर को निम्नलिखित लेआउट के साथ परिभाषित करें:

\begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2 \end{bmatrix}

यह हमें सूचित करता है कि $\mathbf{L}$ के स्तंभ क्या दर्शाते हैं:

\mathbf{L} = \begin{bmatrix} l_{1, 1} & l_{1, r} & l_{1, x} & l_{1, y} & l_{1, z} & l_{1, u} & l_{1, v_1} & l_{1, v_2} \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_1} & l_{2, v_2} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

$\mathbf{L}$ की पहली पंक्ति

पहली पंक्ति में, पहले बाएं वेरिएबल के लिए, हमारे पास $v₁ = xy$ है:

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \\ z \\ v_1 \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

इसका मतलब है कि बाईं ओर के संबंध में, वेरिएबल $x$ मौजूद है, और अन्य कोई भी वेरिएबल्स मौजूद नहीं हैं। इसलिए, हम पहली पंक्ति को इस प्रकार बदलते हैं:

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ l_{2, 1} & l_{2, r} & l_{2, x} & l_{2, y} & l_{2, z} & l_{2, u} & l_{2, v_1} & l_{2, v_2} \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

याद करें कि $\mathbf{L}$ के स्तंभों को इस प्रकार लेबल किया गया है:

\begin{bmatrix} 1 & r &x & y & z & u & v_1 & v_2\\ \end{bmatrix}

और हम देखते हैं कि $1$ , $x$ स्तंभ में है।

$\mathbf{L}$ की दूसरी पंक्ति

नीचे की ओर काम करते हुए, हम देखते हैं कि हमारे समीकरणों की प्रणाली (systems of equations) के बाईं ओर के लिए केवल $z$ मौजूद है।

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \\ \color{green}{z} \\ v_1 \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

इसलिए, हम उस पंक्ति में सब कुछ शून्य पर सेट करते हैं, सिवाय उस स्तंभ के जो $z$ का प्रतिनिधित्व करता है।

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ l_{3, 1} & l_{3, r} & l_{3, x} & l_{3, y} & l_{3, z} & l_{3, u} & l_{3, v_1} & l_{3, v_2} \\ \end{bmatrix}

$\mathbf{L}$ की तीसरी पंक्ति

अंत में, तीसरी पंक्ति में बाएं हाथ के ऑपरेटरों (left hand operators) में हमारे पास केवल $v₁$ मौजूद वेरिएबल के रूप में है

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} x \\ z \\ \color{violet}{v_1} \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

यह मैट्रिक्स $\mathbf{L}$ को पूरा करता है

\mathbf{L}=\begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \\ \end{bmatrix}

निम्नलिखित छवि (image/diagram) मैपिंग को अधिक स्पष्ट करेगी:

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \underset{\mathbf{L}}{\boxed{ \begin{matrix} \color{red}{x} \\ \color{green}{z} \\ \color{violet}{v_1} \\ \end{matrix} }} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix} \space\space\space\space \begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & \color{violet}{1} & 0 \\ \end{bmatrix} \end{array} \end{array}

$\mathbf{L}$ का वैकल्पिक रूपांतरण (Alternative transformation)

हम निम्नलिखित के बाएं हाथ के मानों (left hand values) का विस्तार (expand) करके भी यही अभ्यास पूरा कर सकते हैं

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

इस प्रकार:

\begin{align*} v_1 &= (0\cdot 1 + 0\cdot r + \boxed{1\cdot x} + 0\cdot y + 0\cdot z + 0\cdot u + 0\cdot v_1 + 0\cdot v_2) \times y\\ v_2 &= (0\cdot 1 + 0\cdot r + 0\cdot x + 0\cdot y + \boxed{1\cdot z} + 0\cdot u + 0\cdot v_1 + 0\cdot v_2) \times u\\ r &= (0\cdot 1 + 0\cdot r + 0\cdot x + 0\cdot y + 0\cdot z + 0\cdot u + \boxed{1\cdot v_1} + 0\cdot v_2) \times v_2 \\ \end{align*}

हम ऐसा कर सकते हैं क्योंकि शून्य पदों (zero terms) को जोड़ने से मान नहीं बदलते हैं। हमें बस शून्य वेरिएबल्स का विस्तार करने के लिए सावधान रहना होगा ताकि उनमें वही “स्तंभ” हों जैसे हमने witness वेक्टर को परिभाषित किया है।

और फिर, यदि हम उपरोक्त विस्तार से गुणांकों (coefficients - बॉक्स में दिखाए गए) को बाहर निकालते हैं,

\begin{align*} v_1 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{1}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times y\\ v_2 &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{1}\cdot z + \boxed{0}\cdot u + \boxed{0}\cdot v_1 + \boxed{0}\cdot v_2) \times u\\ r &= (\boxed{0}\cdot 1 + \boxed{0}\cdot r + \boxed{0}\cdot x + \boxed{0}\cdot y + \boxed{0}\cdot z + \boxed{0}\cdot u + \boxed{1}\cdot v_1 + \boxed{0}\cdot v_2) \times v_2 \\ \end{align*}

हमें $\mathbf{L}$ के लिए वही मैट्रिक्स मिलता है जो हमने कुछ क्षण पहले उत्पन्न किया था।

\mathbf{L}=\begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}

Right hand terms से मैट्रिक्स $\mathbf{R}$ का निर्माण

R = \begin{bmatrix} r_{1,1} & r_{1,r} & r_{1,x} & r_{1,y} & r_{1,z} & r_{1,u} & r_{1,v_1} & r_{1,v_2} \\ r_{2,1} & r_{2,r} & r_{2,x} & r_{2,y} & r_{2,z} & r_{2,u} & r_{2,v_1} & r_{2,v_2} \\ r_{3,1} & r_{3,r} & r_{3,x} & r_{3,y} & r_{3,z} & r_{3,u} & r_{3,v_1} & r_{3,v_2} \\ \end{bmatrix}

मैट्रिक्स $\mathbf{R}$ हमारे समीकरण के दाएं हाथ के पदों (right hand terms) का प्रतिनिधित्व करता है:

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}}{\boxed{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}}}

मैट्रिक्स $\mathbf{R}$ में $y$ , $u$ , और $v_2$ का प्रतिनिधित्व करने वाले 1s होने चाहिए। मैट्रिक्स की पंक्ति arithmetic constraint की पंक्ति से मेल खाती है, यानी हम constraints (पंक्तियों) को इस प्रकार क्रमांकित (number) कर सकते हैं:

\begin{matrix} (1) \\ (2) \\ (3) \\ \end{matrix} \space\space \begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} { \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} } \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}}{\boxed{ \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}}}

तो पहली पंक्ति के $y$ स्तंभ में 1 है, दूसरी पंक्ति के $u$ स्तंभ में 1 है, और तीसरी पंक्ति के $v_2$ स्तंभ में 1 है। बाकी सब कुछ शून्य है।

इसका परिणाम मैट्रिक्स $\mathbf{R}$ के लिए निम्नलिखित है:

\begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \end{array} \end{array}

यह आरेख (diagram) रूपांतरण (transformation) को स्पष्ट करता है।

\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix} \begin{matrix} =\\ =\\ = \end{matrix} \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} \begin{matrix} \times\\ \times\\ \times \end{matrix} \underset{\mathbf{R}} {\boxed{ \begin{matrix} \color{red}{y} \\ \color{green}{u} \\ \color{violet}{v_2} \\ \end{matrix} }} \space\space\space\space \begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & \color{red}{1} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & \color{green}{1} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 &\color{violet}{1} \\ \end{bmatrix} \end{array} \end{array}

मैट्रिक्स $\mathbf{O}$ का निर्माण

पाठक के लिए यह निर्धारित करना एक अभ्यास है कि मैट्रिक्स $\mathbf{O}$ है

\mathbf{O}=\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}

पहले के मैट्रिक्स के अनुरूप स्तंभ लेबलों (column labels) का उपयोग करते हुए।

याद दिलाने के लिए, $\mathbf{C}$ गुणा के परिणाम से प्राप्त होता है

\underset{\mathbf{C}}{ \boxed{\begin{matrix} v_1 \\ v_2 \\ r \\ \end{matrix}}} \begin{matrix} =\\ =\\ = \end{matrix} \begin{matrix} x \\ z \\ v_1 \\ \end{matrix} \begin{matrix} \times\\ \times\\ \times \end{matrix} \begin{matrix} y \\ u \\ v_2 \\ \end{matrix}

और स्तंभ लेबल इस प्रकार हैं

\begin{array}{c} \begin{array}{cc} \begin{matrix} 1 & r & x & y & z & u & v_1 & v_2 \\ \end{matrix} \end{array} \\[10pt] \begin{array}{cc} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{array} \end{array}

$r = x \cdot y \cdot z \cdot u$ के लिए हमारे काम की जाँच करना

import numpy as np

# enter the A B and C from above
L = np.matrix([[0,0,1,0,0,0,0,0],
              [0,0,0,0,1,0,0,0],
              [0,0,0,0,0,0,1,0]])
              
R = np.matrix([[0,0,0,1,0,0,0,0],
              [0,0,0,0,0,1,0,0],
              [0,0,0,0,0,0,0,1]])
              
O = np.matrix([[0,0,0,0,0,0,1,0],
              [0,0,0,0,0,0,0,1],
              [0,1,0,0,0,0,0,0]])

# random values for x, y, z, and u
import random
x = random.randint(1,1000)
y = random.randint(1,1000)
z = random.randint(1,1000)
u = random.randint(1,1000)

# compute the algebraic circuit
r = x * y * z * u
v1 = x*y
v2 = z*u

# create the witness vector
a = np.array([1, r, x, y, z, u, v1, v2])

# element-wise multiplication, not matrix multiplication
result = np.matmul(O, a) == np.multiply(np.matmul(L, a), np.matmul(R, a))

assert result.all(), "system contains an inequality"

उदाहरण 3: एक स्थिरांक (constant) के साथ जोड़ (Addition)

क्या होगा यदि हम निम्नलिखित के लिए एक rank one constraint system बनाना चाहते हैं?

z = x * y + 2

यहीं पर वह 1 का स्तंभ काम आता है।

जोड़ (Addition) मुफ़्त है

आपने शायद ZK-SNARKs के संदर्भ में “addition is free” (जोड़ मुफ़्त है) कथन सुना होगा। इसका मतलब यह है कि जब हमारे पास एक जोड़ का ऑपरेशन होता है तो हमें एक अतिरिक्त constraint बनाने की आवश्यकता नहीं होती है।

हम उपरोक्त सूत्र (formula) को इस प्रकार लिख सकते हैं

\begin{align*} v_1 = xy \\ z = v_1 + 2 \\ \end{align*}

लेकिन वह हमारे R1CS को आवश्यकता से अधिक बड़ा बना देगा।

इसके बजाय, हम इसे इस प्रकार लिख सकते हैं

-2 + z = xy

फिर वेरिएबल $z$ और स्थिरांक $-2$ स्वचालित रूप से “संयुक्त” (combined) हो जाते हैं जब हम अपने witness वेक्टर के साथ $\mathbf{a}$ को $\mathbf{O}$ से गुणा करते हैं।

हमारे witness वेक्टर का रूप [1, z, x, y] है, इसलिए हमारे मैट्रिक्स $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ इस प्रकार हैं:

\mathbf{L} = \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix}

\mathbf{R} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ \end{bmatrix}

\mathbf{O} = \begin{bmatrix} -2 & 1 & 0 & 0 \\ \end{bmatrix}

जब भी additive constants होते हैं, हम बस उन्हें $1$ स्तंभ में रख देते हैं, जो परंपरा के अनुसार पहला स्तंभ होता है।

फिर से, आइए अपने गणित (math) पर कुछ यूनिट टेस्ट करें:

import numpy as np
import random

# Define the matrices
L = np.matrix([[0,0,1,0]])
R = np.matrix([[0,0,0,1]])
O = np.matrix([[-2,1,0,0]])

# pick random values to test the equation
x = random.randint(1,1000)
y = random.randint(1,1000)
z = x * y + 2 # witness vector
a = np.array([1, z, x, y])

# check the equality
result = O.dot(a) == np.multiply(np.matmul(L, a), R.dot(a))
assert result.all(), "result contains an inequality"

उदाहरण 4: एक स्थिरांक (constant) के साथ गुणा

ऊपर दिए गए सभी उदाहरणों में, हमने कभी भी वेरिएबल्स को स्थिरांक (constants) से गुणा नहीं किया। इसलिए R1CS में प्रविष्टियां (entries) हमेशा 1 थीं। जैसा कि आपने उपरोक्त उदाहरण से अनुमान लगाया होगा, मैट्रिक्स में प्रविष्टि उसी स्थिरांक का मान होती है जिससे वेरिएबल को गुणा किया जाता है, जैसा कि निम्नलिखित उदाहरण दिखाएगा।

आइए इसके लिए समाधान निकालते हैं

z = 2x^2 + y

ध्यान दें कि जब हम “प्रति constraint एक गुणा” कहते हैं तो हमारा मतलब दो वेरिएबल्स के गुणा से होता है। एक स्थिरांक के साथ गुणा “वास्तविक” गुणा नहीं है क्योंकि यह वास्तव में एक ही वेरिएबल का बार-बार किया जाने वाला जोड़ है।

निम्नलिखित समाधान वैध (valid) है, लेकिन अनावश्यक पंक्तियाँ बनाता है:

\begin{align*} v_1 &= xx \\\\ z &= 2v_1 + y\\\\ \end{align*}

अधिक अनुकूलतम (optimal) समाधान इस प्रकार है:

-y + z = 2xx

अधिक अनुकूलतम समाधान का उपयोग करते हुए, हमारे witness वेक्टर का रूप [1, out, x, y] होगा।

मैट्रिक्स को इस प्रकार परिभाषित किया जाएगा:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 2 & 0 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & -1 \\ \end{bmatrix} \\ \end{align*}

R1CS रूप में उपरोक्त को प्रतीकात्मक रूप से (symbolically) [1, z, x, y] से गुणा करने पर हमें हमारा मूल समीकरण वापस मिल जाता है:

\begin{bmatrix} 0 & 1 & 0 & -1 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix} = \begin{bmatrix} 0 & 0 & 2 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix}\circ \begin{bmatrix} 0 & 0 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 \\ z \\ x \\ y \\ \end{bmatrix}

z - y = 2xx

z = 2x^2 + y

इसलिए हम जानते हैं कि हमने $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ को सही ढंग से सेट किया है।

यहाँ हमारे पास एक पंक्ति (constraints) और एक “सच्चा” गुणा है। एक सामान्य नियम के रूप में:

Rank One Constraint System में constraints की संख्या गैर-स्थिर गुणाओं (non-constant multiplications) की संख्या के बराबर होनी चाहिए।

उदाहरण 5: एक बड़ा constraint

आइए कुछ कम सामान्य (less trivial) करें जो ऊपर सीखी गई हर चीज़ को शामिल करता हो

मान लीजिए हमारे पास निम्नलिखित constraint है:

z = 3x^2y + 5xy - x - 2y + 3

हम इसे इस प्रकार तोड़ेंगे:

\begin{align*} v_1 &= 3xx \\ v_2 &= v_1y \\ -v_2 + x + 2y - 3 + z &= 5xy \\ \end{align*}

ध्यान दें कि कैसे सभी जोड़ वाले पदों को बाईं ओर ले जाया गया है (यही हमने जोड़ वाले उदाहरण में किया था, लेकिन यह यहाँ अधिक स्पष्ट है)।

तीसरी पंक्ति में दाईं ओर $5xy$ छोड़ना मनमाना (arbitrary) है। हम दोनों पक्षों को 5 से विभाजित कर सकते हैं और अंतिम constraint यह हो सकता है

\frac{-v_2}{5} + \frac{x}{5} + \frac{2y}{5} - \frac{3}{5} + \frac{z}{5}= xy

हालाँकि यह witness को नहीं बदलता है, इसलिए दोनों वैध हैं। चूँकि सब कुछ एक finite field में किया जाता है, यह ऑपरेशन left-hand-side और right-hand-side को 5 के multiplicative inverse से गुणा कर रहा है।

हमारा witness वेक्टर इस रूप का होगा

[1, z, x, y, v_1, v_2]

और हमारे मैट्रिक्स में तीन पंक्तियाँ होंगी, चूँकि हमारे पास तीन constraints हैं:

\begin{align*} \color{red}{v_1} &= \color{green}{3x}\color{violet}{x} \\ \color{red}{v_2} &= \color{green}{v_1}\color{violet}{y} \\ \color{red}{-v_2 + x + 2y - 3 + z} &= \color{green}{5x}\color{violet}{y} \\ \end{align*}

हमने आउटपुट $\mathbf{O}$ को लाल रंग में, बाईं ओर $\mathbf{L}$ को हरे रंग में, और दाईं ओर $\mathbf{R}$ को बैंगनी रंग में चिह्नित किया है। यह निम्नलिखित मैट्रिक्स उत्पन्न करता है:

L = \begin{bmatrix} 0 & 0 & \textcolor{green}{3} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \textcolor{green}{1} & 0 \\ 0 & 0 & \textcolor{green}{5} & 0 & 0 & 0 \\ \end{bmatrix}

R = \begin{bmatrix} 0 & 0 & \textcolor{violet}{1} & 0 & 0 & 0 \\ 0 & 0 & 0 & \textcolor{violet}{1} & 0 & 0 \\ 0 & 0 & 0 & \textcolor{violet}{1} & 0 & 0 \\ \end{bmatrix}

O = \begin{bmatrix} 0 & 0 & 0 & 0 & \textcolor{red}{1} & 0 \\ 0 & 0 & 0 & 0 & 0 & \textcolor{red}{1} \\ \textcolor{red}{-3} & \textcolor{red}{1} & \textcolor{red}{1} & \textcolor{red}{2} & 0 & \textcolor{red}{-1} \\ \end{bmatrix}

स्तंभ लेबलों (column labels) के साथ

\begin{bmatrix}1 & \text{out} & x & y & v_1 & v_2\end{bmatrix}

आइए हमेशा की तरह अपने काम की जाँच करें।

import numpy as np
import random

# Define the matrices
L = np.array([[0,0,3,0,0,0],
               [0,0,0,0,1,0],
               [0,0,5,0,0,0]])

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

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

# pick random values for x and y
x = random.randint(1,1000)
y = random.randint(1,1000)

# this is our orignal formula
out = 3 * x * x * y + 5 * x * y - x - 2 * y + 3 # the witness vector with the intermediate variables inside
v1 = 3*x*x
v2 = v1 * y
w = np.array([1, out, x, y, v1, v2])

result = O.dot(w) == np.multiply(L.dot(w),R.dot(w))
assert result.all(), "result contains an inequality"

Rank 1 Constraint Systems को एक ही बहुपद (single polynomial) से शुरू करने की आवश्यकता नहीं होती है

चीजों को सरल रखने के लिए, हम $z = xy + ...$ के रूप के उदाहरणों का उपयोग कर रहे हैं लेकिन अधिकांश वास्तविक arithmetic constraints, arithmetic constraints का एक सेट (set) होने वाले हैं, न कि केवल एक।

उदाहरण के लिए, मान लीजिए कि हम साबित कर रहे हैं कि एक ऐरे $[x₁, x₂, x₃, x₄]$ बाइनरी (binary) है और $v$ , 16 से कम है। constraints का सेट होगा:

\begin{align*} x₁² &= x₁\\ x₂² &= x₂\\ x₃² &= x₃\\ x₄² &= x₄ \\ v &= 8x₄ + 4x₃ + 2x₂ + x₁ \end{align*}

इसे rank one constraint system में प्राप्त करने के लिए, हम ध्यान देते हैं कि अंतिम पंक्ति में कोई गुणा नहीं है, इसलिए हम $x_1$ को पहले constraint में प्रतिस्थापित (substitute) कर सकते हैं:

\begin{align*} x₁² &= v - 8x₄ - 4x₃ - 2x₂\\ x₂² &= x₂\\ x₃² &= x₃\\ x₄² &= x₄ \\ \end{align*}

यह मानते हुए कि हमारा witness वेक्टर $[1, v, x_1, x_2, x_3, x_4]$ है, हम इस प्रकार R1CS बना सकते हैं:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & -2 & -4 & -8 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \\ \end{align*}

प्रतिस्थापन (substitution) करना पूरी तरह से आवश्यक नहीं है, लेकिन यह R1CS में एक पंक्ति बचाता है। बाद के एक भाग में, हम एक वैध R1CS दिखाएंगे जहाँ हम प्रतिस्थापन नहीं करते हैं।

R1CS में सब कुछ modulo prime किया जाता है

उपरोक्त उदाहरणों में, हमने सादगी के लिए पारंपरिक अंकगणित (traditional arithmetic) का उपयोग किया, लेकिन वास्तविक दुनिया के कार्यान्वयन (real world implementations) इसके बजाय modular arithmetic का उपयोग करते हैं।

कारण सरल है: 2/3 जैसी संख्याओं को एन्कोड करने से ill-behaved फ्लोट्स (floats) बनते हैं जो कम्प्यूटेशनल रूप से गहन (computationally intensive) और त्रुटि-प्रवण (error prone) होते हैं।

यदि हम अपना सारा गणित एक अभाज्य संख्या (prime number), मान लीजिए 23 के मॉड्यूलो (modulo) में करते हैं, तो $2/3$ को एन्कोड करना सीधा है। यह $2 \cdot 3^{-1}$ के समान है, और दो से गुणा करना और ऋणात्मक 1 की घात (power of negative 1) तक बढ़ाना modular arithmetic में सीधे हैं।

Circom का कार्यान्वयन (implementation)

Circom में, जो Rank 1 Constraint Systems बनाने के लिए एक भाषा है, finite field अभाज्य संख्या (prime number) $21888242871839275222246405745257275088548364400416034343698204186575808495617$ का उपयोग करता है (यह BN128 कर्व (curve) के क्रम (order) के बराबर है जिस पर हमने Elliptic Curves over Finite Fields में चर्चा की थी)।

इसका मतलब है कि उस प्रतिनिधित्व (representation) में $-1$ है

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

# 1 - 2 = -1
(1 - 2) % p

# 21888242871839275222246405745257275088548364400416034343698204186575808495616

out = x * y के लिए Circom

यदि हम Circom में out = x * y लिखते हैं, तो यह निम्नलिखित की तरह दिखेगा:

pragma circom 2.0.0;

template Multiply2() {
    signal input x;
    signal input y;
    signal output out;

    out <== x * y;
 }

component main = Multiply2();

आइए इसे एक R1CS फ़ाइल में बदलें और R1CS फ़ाइल को प्रिंट करें

circom multiply2.circom --r1cs --sym
snarkjs r1cs print multiply2.r1cs

हमें निम्नलिखित आउटपुट मिलता है:

यह हमारे R1CS समाधान से काफी अलग दिखता है, लेकिन यह वास्तव में उसी जानकारी को एन्कोड कर रहा है।

Circom के कार्यान्वयन (implementation) में ये अंतर हैं:

शून्य (zero) मान वाले स्तंभ प्रिंट नहीं किए जाते हैं
Circom $\mathbf{O}\mathbf{a} = \mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a}$ को $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ के रूप में लिखता है

21888242871839275222246405745257275088548364400416034343698204186575808495616 के बारे में क्या जो वास्तव में -1 है?

Circom का समाधान है

\begin{align*} A &= \begin{bmatrix} 0 & 0 & -1 & 0 \end{bmatrix}\\ B &= \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix}\\ C &= \begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix} \end{align*}

भले ही ऋणात्मक (negative) वाले अप्रत्याशित (unexpected) हो सकते हैं, witness वेक्टर [1 out x y] के साथ, यह वास्तव में $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ के रूप के अनुरूप है। (हम एक सेकंड में देखेंगे कि Circom ने वास्तव में इसी स्तंभ असाइनमेंट का उपयोग किया था)।

आप $x$ , $y$ , और out के लिए मानों को रख सकते हैं और देख सकते हैं कि समीकरण $\mathbf{L}\mathbf{a}\circ\mathbf{R}\mathbf{a} - \mathbf{O}\mathbf{a} = \mathbf{0}$ सही साबित होता है।

आइए Circom के वेरिएबल से स्तंभ (column) असाइनमेंट को देखें। आइए wasm सॉल्वर (solver) के साथ अपने सर्किट को फिर से संकलित (recompile) करें:

circom multiply2.circom --r1cs --wasm --sym

cd multiply2_js/

हम input.json फ़ाइल बनाते हैं

echo '{"x": "11", "y": "9"}' > input.json

और witness की गणना करते हैं

node generate_witness.js multiply2.wasm input.json witness.wtns

snarkjs wtns export json witness.wtns witness.json

cat witness.json

हमें निम्नलिखित परिणाम मिलता है:

यह स्पष्ट है कि Circom उसी स्तंभ लेआउट (column layout) का उपयोग कर रहा है जिसका हम उपयोग कर रहे हैं: [1, out, x, y], चूँकि हमारे input.json में $x$ को $11$ और $y$ को $9$ पर सेट किया गया था।

यदि हम Circom के उत्पन्न (generated) witness का उपयोग करते हैं (पढ़ने में आसानी के लिए बड़ी संख्या को -1 से बदलते हुए), तो हम देखते हैं कि Circom का R1CS सही है

\begin{align*} \mathbf{a} &= \begin{bmatrix} 1 & 99 & 11 & 9 \end{bmatrix}\\ \mathbf{L} &= \begin{bmatrix} 0 & 0 & -1 & 0 \end{bmatrix} \rightarrow \mathbf{L}\mathbf{a} = -11\\ \mathbf{R} &= \begin{bmatrix} 0 & 0 & 0 & 1 \end{bmatrix} \rightarrow \mathbf{R}\mathbf{a} = 9\\ \mathbf{O} &= \begin{bmatrix} 0 & -1 & 0 & 0 \end{bmatrix} \rightarrow \mathbf{O}\mathbf{a} = -99 \end{align*}

\begin{align*} Aw \cdot Bw - Cw &= 0\\ (-11)(9) - (-99) &= 0 \\ -99 + 99 &= 0 \end{align*}

$\mathbf{L}$ में $x$ के लिए $-1$ का एक गुणांक (coefficient) है, $\mathbf{R}$ में $y$ के लिए $+1$ का एक गुणांक है, और $\mathbf{O}$ में $\text{out}$ के लिए $-1$ है। मॉड्यूलर (modular) रूप में, यह बिल्कुल वैसा ही है जैसा टर्मिनल ने ऊपर आउटपुट किया था:

हमारे बाकी काम की जाँच करना

समीक्षा (review) के तौर पर, हमने जिन सूत्रों का अन्वेषण किया था, वे थे:

\begin{align} z &= x * y \\ z &= x * y * z * u \\ z &= x * y + 2 \\ z &= 3x^2 y + 5xy - x - 2y + 3 \end{align}

हमने अभी ऊपर के भाग में (1) किया था, इस भाग के लिए हम इस सिद्धांत (principle) को स्पष्ट करेंगे कि गैर-स्थिर गुणाओं (non-constant multiplications) की संख्या constraints की संख्या होती है।

(2) के लिए सर्किट है:

pragma circom 2.0.8;

template Multiply4() {
    signal input x;
    signal input y;
    signal input z;
    signal input u;
    
    signal v1;
    signal v2;
    
    signal out;
    
    v1 <== x * y;
    v2 <== z * u;
    
    out <== v1 * v2;
}

component main = Multiply4();

हमने अब तक जो कुछ भी चर्चा की है, उसके साथ Circom का आउटपुट और एनोटेशन (annotations) स्व-व्याख्यात्मक (self-explanatory) होने चाहिए।

इसे ध्यान में रखते हुए, हमारे अन्य सूत्रों में इस प्रकार के constraints होने चाहिए:

\begin{align} z &= x * y && \text{1 constraint} \\ z &= x * y * z * u && \text{3 constraints} \\ z &= x * y + 2 && \text{1 constraint} \\ z &= 3x^2 y + 5xy - x - 2y + 3 && \text{3 constraints} \end{align}

Circom सर्किट लिखना और उपरोक्त को सत्यापित (verify) करना पाठक के लिए एक अभ्यास है।

R1CS की गणना करने के लिए आपको witness की आवश्यकता नहीं होती है

ध्यान दें कि Circom कोड में हमने R1CS की गणना करने से पहले कभी भी witness की आपूर्ति (supply) नहीं की। हमने उदाहरण को कम अमूर्त (abstract) बनाने और अपने काम की जाँच को आसान बनाने के लिए पहले witness की आपूर्ति की थी, लेकिन यह आवश्यक नहीं है। यह महत्वपूर्ण है, क्योंकि यदि किसी वेरीफायर (verifier) को R1CS बनाने के लिए witness की आवश्यकता होती, तो प्रूवर (prover) को अपना छिपा हुआ समाधान (hidden solution) देना पड़ता!

जब हम “witness” कहते हैं तो हमारा मतलब भरे हुए मानों (populated values) वाले एक वेक्टर से होता है। वेरीफायर (verifier) witness की “संरचना” (structure), यानी वेरिएबल से स्तंभ (column) असाइनमेंट को जानता है, लेकिन मानों को नहीं जानता।

एक R1CS वैध (valid) होता है भले ही वह ऑप्टिमाइज़्ड (optimized) न हो

एक बहुपद (polynomial) से R1CS में एक वैध रूपांतरण (transformation) अद्वितीय (unique) नहीं होता है। आप उसी समस्या को अधिक constraints के साथ एन्कोड कर सकते हैं, जो कम कुशल (efficient) है। यहाँ एक उदाहरण है।

कुछ R1CS ट्यूटोरियल्स में, इस तरह के सूत्र (formula) के लिए constraints

z = x² + y

को इसमें बदल दिया जाता है:

\begin{align*} v₁ &= x x \\ z &= v₁ + y \end{align*}

जैसा कि हमने ध्यान दिया है, यह कुशल (efficient) नहीं है। हालाँकि, आप इस लेख में दी गई कार्यप्रणाली (methodology) का उपयोग करके इसके लिए एक वैध R1CS बना सकते हैं। हम बस इस तरह एक डमी गुणा (dummy multiplication) जोड़ते हैं:

\begin{align*} v₁ &= x x \\ z &= (v₁ + y) * 1 \end{align*}

हमारा witness वेक्टर $[1, z, x, y, v1]$ के रूप का है और $\mathbf{L}$ , $\mathbf{R}$ , और $\mathbf{O}$ इस प्रकार परिभाषित हैं:

\mathbf{L} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}

\mathbf{R} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{bmatrix}

\mathbf{O} = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \end{bmatrix}

$\mathbf{L}$ की दूसरी पंक्ति जोड़ को पूरा करती है, और एक (one) से गुणा $\mathbf{R}$ की दूसरी पंक्ति के पहले एलिमेंट का उपयोग करके पूरा किया जाता है।

यह पूरी तरह से वैध है, लेकिन समाधान में इसकी आवश्यकता से एक अधिक पंक्ति और एक अधिक स्तंभ है।

क्या होगा यदि कोई गुणा (multiplications) न हो?

क्या होगा यदि हम निम्नलिखित सर्किट को एन्कोड करना चाहते हैं?

z = x + y

अभ्यास (practice) में यह काफी बेकार है, लेकिन पूर्णता के लिए, इसे एक (one) के डमी गुणा के साथ हल किया जा सकता है।

out = (x + y)*1

$[1, z, x, y]$ के हमारे सामान्य witness वेक्टर लेआउट के साथ, हमारे पास निम्नलिखित मैट्रिक्स हैं:

\begin{align*} \mathbf{L} &= \begin{bmatrix} 0 & 0 & 1 & 1 \\ \end{bmatrix} \\ \mathbf{R} &= \begin{bmatrix} 1 & 0 & 0 & 0 \\ \end{bmatrix} \\ \mathbf{O} &= \begin{bmatrix} 0 & 1 & 0 & 0 \\ \end{bmatrix} \end{align*}

Rank One Constraint Systems सुविधा के लिए हैं

Groth16 के मूल पेपर में Rank One Constraint System शब्द का कोई संदर्भ नहीं है। कार्यान्वयन (implementation) के दृष्टिकोण से एक R1CS उपयोगी है, लेकिन शुद्ध गणित के दृष्टिकोण से, यह स्पष्ट रूप से विभिन्न वेरिएबल्स के गुणांकों (coefficients) को लेबल करने और समूहीकृत करने के बारे में है। इसलिए जब आप इस विषय पर अकादमिक पेपर (academic papers) पढ़ते हैं, तो यह आमतौर पर गायब होता है क्योंकि यह एक अधिक अमूर्त अवधारणा (abstract concept) का एक कार्यान्वयन विवरण (implementation detail) है।

उपयोगी संसाधन (Handy Resources)

यह वेब टूल R1CS की गणना करता है constraints के एक सेट के लिए (लेकिन यह केवल एक इनपुट और आउटपुट वेरिएबल के साथ काम करता है)।
Vitalik का x**3 + x + 5 == 35 का प्रसिद्ध उदाहरण
Zero knowledge ब्लॉग का R1CS ट्यूटोरियल

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

यह ब्लॉग पोस्ट हमारे zero knowledge कोर्स की शिक्षण सामग्री (learning materials) से ली गई है।