ZK में स्टैक डेटा संरचना की मॉडलिंग

Last updated on Jan 3, 2026

यह ट्यूटोरियल दिखाता है कि Circom में स्टैक कैसे बनाया जाता है।

ध्यान दें — यह अध्याय लंबा है।

हालाँकि, स्टैक के बारे में ZK प्रूफ बनाने की यह रणनीति तब बहुत काम आएगी जब हम अगले अध्याय में एक साधारण ZK वर्चुअल मशीन (ZKVM) बनाएंगे। ZKVM कैसे काम करता है, इसे समझने का अधिकांश कार्य इसी अध्याय में पहले ही कवर कर लिया गया है।

स्टैक, स्टैक के शीर्ष (top) पर एक नंबर push (पुश) करने, स्टैक के शीर्ष को pop (पॉप) करने, या no changes (कोई बदलाव नहीं) करने में सक्षम है।

स्टैक मूल रूप से परिवर्तनीय (mutable) होते हैं, लेकिन Circom में, हमें केवल एक अपरिवर्तनीय (immutable) ऐरे का उपयोग करने की अनुमति है। इसलिए, स्टैक को एक अपरिवर्तनीय ऐरे के साथ मॉडल किया जाना चाहिए। हर बार जब स्टैक बदलता है (पॉप या पुश के माध्यम से), हम एक नया ऐरे बनाते हैं जो नए स्टैक स्टेट को दर्शाता है।

यह अक्षम (inefficient) लग सकता है, लेकिन इसका कोई दूसरा विकल्प नहीं है क्योंकि ZK में सिग्नल्स अपरिवर्तनीय होते हैं (अधिक उन्नत ZK तकनीकों में इसे ऑप्टिमाइज़ करने के तरीके हैं, लेकिन यह चर्चा इस लेख के दायरे से बाहर है)।

पहली आवश्यकता यह है कि स्टैक की एक निश्चित “अधिकतम ऊंचाई (maximum height)” होनी चाहिए — जो यह बताती है कि अपरिवर्तनीय ऐरे कितना लंबा है। स्टैक का कितना हिस्सा “उपयोग” किया गया है, इसे ट्रैक करने के लिए, हम “स्टैक पॉइंटर” नामक एक अलग वेरिएबल का उपयोग करते हैं, जो एक शून्य-आधारित (zero-based) इंडेक्स है और हमें बताता है कि अगला आइटम कहाँ पुश करना है। sp ऐरे में एक अप्रयुक्त (unused) स्थान को इंगित करता है जहाँ एक नया मान पुश किया जाना चाहिए, जो स्टैक के शीर्ष से एक इंडेक्स ऊपर होता है। नीचे दिया गया आरेख तीन आइटमों, 10, 16 और 20 वाले स्टैक को दर्शाता है:

\begin{align*}\texttt{sp}=3\\ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{array}&10 & 16 & 20 & \circ & \space & \space \\ \hline \text{index}&0 & 1 &2 &3 &4 &5\\ \hline \end{array} \end{align*}

स्टैक पॉइंटर sp इंडेक्स 3 को इंगित कर रहा है, जो खाली है और इसे $\circ$ से दर्शाया गया है। स्टैक इंडेक्स 3 (वर्तमान sp) या उससे अधिक के किसी भी मान को अनदेखा कर देता है। उनमें गैर-शून्य (non-zero) मान हो सकते हैं, लेकिन सर्किट उन पर विचार नहीं करेगा।

मान लीजिए कि हम आइटम 21 को स्टैक पर पुश करते हैं। इसका मतलब है कि हम स्टैक पॉइंटर को बढ़ाते (increment) हैं और पिछले सभी मानों को कॉपी करते हैं। अपडेटेड स्टैक में अब sp = 4 है।

\begin{align*}\texttt{sp}=4\\ \begin{array}{|c|c|c|c|c|c|} \hline 10& 16 & 20 & \circ & \space \\ \hline 10 & 16 & 20 & 21& \circ & \space \\ \hline \end{array} \end{align*}

यदि हम स्टैक से पॉप करते हैं, तो sp घट (decrement) जाता है और हम मान 21 को अगले स्टैक में कॉपी नहीं करते हैं:

\begin{align*}\texttt{sp}=3\\ \begin{array}{|c|c|c|c|c|c|} \hline 10 & 16 & 20 & \circ & \space \\ \hline 10 & 16 & 20 & 21& \circ & \space \\ \hline 10 & 16 & 20 & \circ& \space & \space \\ \hline \end{array} \end{align*}

यदि स्टैक में कोई बदलाव नहीं होता है, तो भी हम किसी प्रकार के कंप्यूटेशन चरण से गुजरते हैं, जहां हम बस पिछले सभी मानों को अगले स्टैक में कॉपी कर देते हैं।

\begin{align*}\texttt{sp}=3\\ \begin{array}{|c|c|c|c|c|c|} \hline 10 & 16 & 20 & \circ & \space \\ \hline 10 & 16 & 20 & 21& \circ & \space \\ \hline 10 & 16 & 20 & \circ& \space & \space \\ \hline 10 & 16 & 20 & \circ& \space & \space \\ \hline \end{array} \end{align*}

चूंकि sp हर इटरेशन (iteration) के साथ बदलता है, हमें हर बार नए मान को एक नए सिग्नल में स्टोर करना होगा क्योंकि एक बार असाइन किए जाने के बाद सिग्नल का मान अपडेट नहीं किया जा सकता है। इसलिए, हम प्रत्येक इटरेशन पर sp के मान को ट्रैक करने के लिए एक ऐरे का उपयोग करते हैं:

\begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp}\downarrow & \\ \hline 3 & 10 & 16 & 20 & \circ & \space \\ \hline 4 & 10 & 16 & 20 & 21& \circ & \space \\ \hline 3 &10 & 16 & 20 & \circ& \space & \space \\ \hline 3 &10 & 16 & 20 & \circ& \space & \space \\ \hline \end{array}

जिस प्रकार स्टैक की अधिकतम ऊंचाई होती है, उसी प्रकार हम इसे अधिकतम कितनी बार अपडेट कर सकते हैं, इसकी भी एक सीमा होती है, क्योंकि स्टैक को मॉडल करने वाली टेबल (आंतरिक रूप से एक 2D Circom ऐरे) का आकार निश्चित (fixed size) होना चाहिए।

अधिकतम आकार हमारे एप्लिकेशन पर निर्भर करता है। ब्लॉकचेन सेटिंग में, यह बहुत असंभव है कि 1 मिलियन इंस्ट्रक्शन निष्पादित (executed) किए जाएं, लेकिन अधिक गहन एप्लिकेशन्स के लिए सर्किट बनाते समय हमें संभावित स्टैक आकारों को समायोजित करने के लिए एक बड़ा सर्किट आवंटित (allocate) करने की आवश्यकता हो सकती है।

स्टैक के लिए कंस्ट्रेंट्स (Constraints)

भले ही हम पुश करें, पॉप करें, या कुछ न करें, 0 से लेकर sp - 2 (इसे मिलाकर) तक के आइटम्स को अगले स्टैक में कॉपी किया जाना चाहिए (और उनके समान होने का कंस्ट्रेंट होना चाहिए)। नीचे दिए गए उदाहरण में, स्टैक पॉइंटर 4 पर था, फिर हमने एक पॉप ऑपरेशन निष्पादित किया, और स्टैक पॉइंटर 3 हो गया। स्टैक पॉइंटर इंडेक्स 0, 1, 2 (नारंगी रंग में) के आइटम्स कॉपी किए गए थे।

\begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\ \hline 4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 21& \circ & \space \\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \\ \hline \end{array}

यदि इंस्ट्रक्शन पॉप है, तो हमें यह भी आवश्यकता होती है कि नया स्टैक पॉइंटर पिछले वाले से 1 कम हो।

पुश (push) के लिए कंस्ट्रेंट्स

पुश के दौरान, sp - 1 तक के सभी मानों को नए स्टैक में कॉपी किया जाना चाहिए (ध्यान दें कि स्टैक पॉइंटर एक खाली क्षेत्र को इंगित करता है, इसलिए इसे कॉपी करने की आवश्यकता नहीं है)। sp - 1 पर स्थित मान को उस मान के समान होने का कंस्ट्रेंट होना चाहिए जिसे पुश किया गया है।

\begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \\ \hline 4 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & 24& \circ & \space \\ \hline \end{array}

ऊपर दिए गए उदाहरण में, स्टैक पॉइंटर 3 था, और हमने 0, 1, 2 में आइटम्स को कॉपी किया। हम यह भी कंस्ट्रेंट लगाते हैं कि स्टैक पॉइंटर 1 से बढ़ जाए। हमें स्टैक पॉइंटर को पिछले वाले से एक अधिक होने का भी कंस्ट्रेंट लगाना चाहिए।

पॉप (pop) के लिए कंस्ट्रेंट्स

पॉप के दौरान, sp - 2 तक के सभी मानों को नए स्टैक में कॉपी किया जाना चाहिए। हम स्टैक पॉइंटर को एक से कम (decrement) होने का कंस्ट्रेंट लगाते हैं।

\begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \\ \hline 2 & \color{orange}{10} & \color{orange}{16} & \circ & & & \space \\ \hline \end{array}

नॉप (कुछ न करें) के लिए कंस्ट्रेंट्स

sp - 1 तक के सभी मानों को समान रहने का कंस्ट्रेंट होना चाहिए। sp को पिछले इटरेशन के मान के बराबर होने का कंस्ट्रेंट होना चाहिए।

\begin{array}{|c||c|c|c|c|c|c|} \hline \texttt{sp} & 0 & 1 & 2 &3 & 4 & 5\\ \hline 3 &\color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& \space & \space \space \\ \hline 3 & \color{orange}{10} & \color{orange}{16} & \color{orange}{20} & \circ& & \space \\ \hline \end{array}

इंस्ट्रक्शंस के सेट के अनुसार स्टैक को अपडेट करना

इंस्ट्रक्शंस के प्रत्येक इटरेशन पर, हमें यह जानना होगा कि क्या हम एक नंबर पुश करने जा रहे हैं, शीर्ष को पॉप करने जा रहे हैं, या कुछ नहीं करने जा रहे हैं, जिसे हम “ऑपकोड्स” या “इंस्ट्रक्शंस” PUSH, POP, या NOP के साथ दर्शाएंगे।

उदाहरण के लिए, मान लीजिए कि हमें PUSH 10 POP PUSH 16 PUSH 15 PUSH 4 NOP POP इंस्ट्रक्शंस दिए गए हैं। हम इंस्ट्रक्शंस के इस सेट को एक ऐरे के रूप में प्रस्तुत कर सकते हैं:

[PUSH, 10, POP, 0, PUSH, 16, PUSH, 15, PUSH, 4, NOP, 0, POP, 0]

व्यापकता (generality) खोए बिना, हम PUSH को संख्या 1, POP को 2, और NOP को 0 के रूप में संदर्भित कर सकते हैं, इसलिए इंस्ट्रक्शंस को इस प्रकार एन्कोड किया जा सकता है।

\begin{matrix} 1 & 10 & 2 & 0 & 1 & 16 & 1 & 15 & 1 & 4 & 0 & 0 & 2& 0\\ \texttt{PUSH}&&\texttt{POP}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{PUSH}&&\texttt{NOP}&&\texttt{POP} \end{matrix}

ध्यान दें कि प्रत्येक इंस्ट्रक्शन के बाद हमेशा एक स्थिरांक (constant) होता है। PUSH के लिए, यह पुश किया जाने वाला मान है, लेकिन POP और NOP के लिए, बाद वाले स्थिरांक को अनदेखा कर दिया जाता है। इंस्ट्रक्शन को 0, 2, 4, … आदि इंडेक्स पर रखने से हम दो के स्टेप्स में इंस्ट्रक्शंस के माध्यम से इटरेशन कर सकते हैं। दूसरे शब्दों में, यदि इंस्ट्रक्शंस में कोई तर्क (argument) हो सकता है या नहीं, तो तर्क होने या न होने के आधार पर हमें स्टेप साइज बदलना होगा। यह सशर्त (conditional) स्टेप साइज हमारे उदाहरण की जटिलता को बढ़ाता है, इसलिए हम ऑपकोड्स को सम (even) अंतराल पर रखते हैं ताकि हम हमेशा दो का स्टेप ले सकें।

अब, आइए एक “metaTable” जनरेट करें जो हमें बताती है कि निष्पादन (execution) की प्रत्येक पंक्ति पर कौन सा ऑपरेशन होगा। यदि हम कॉलम is_push, is_pop, या is_nop जोड़ते हैं जो यह दर्शाते हैं कि कौन सा इंस्ट्रक्शन सक्रिय है, तो हमें निम्न टेबल मिलती है।

अंतिम परिणाम निम्नलिखित जैसा दिखेगा, लेकिन हम इस टेबल को आगामी अनुभाग में चरण-दर-चरण फिर से बनाएंगे:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & - & - & - \\\hline0 & \color{orange}{1} & 0 & - & 1 & - & - & - & - \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & - & - & - \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & 16 & 15 & - & - \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & 16 & 15 & 4 & - \\\hline0 & 0 & \color{orange}{1} & - & 3 & 16 & 15 & 4 & - \\\hline0 & \color{orange}{1} & 0 & - & 3 & 16 & 15 & - & - \\\hline\end{array}

sp की व्याख्या यह है कि यदि वर्तमान इंस्ट्रक्शन पुश है तो अगला मान कहाँ लिखा जाना चाहिए। यदि इंस्ट्रक्शन pop है, तो sp - 1 वह आइटम है जिसे कॉपी नहीं किया जाना चाहिए।

टेबल में डेटा भरना (Populating the table)

is_push से arg तक टेबल को भरने के लिए, हम बस एक लूप में इंस्ट्रक्शंस को कॉपी कर सकते हैं और यदि वर्तमान इंस्ट्रक्शन PUSH है तो is_push को 1 पर सेट कर सकते हैं, और इसी तरह अन्य इंस्ट्रक्शंस के लिए भी कर सकते हैं। हमें निम्नलिखित परिणाम मिलेगा:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & & & & & \\\hline0 & \color{orange}{1} & 0 & - & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & - & & & & & \\\hline0 & \color{orange}{1} & 0 & - & & & & & \\\hline\end{array}

स्टैक पॉइंटर हमेशा शून्य से शुरू होना चाहिए, इसलिए हम बस इसे हार्डकोड कर सकते हैं:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_apop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\\hline0 & \color{orange}{1} & 0 & - & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & - & & & & & \\\hline0 & \color{orange}{1} & 0 & - & & & & & \\\hline\end{array}

हम स्टैक पॉइंटर कॉलम के शेष भाग को भर सकते हैं: यदि इंस्ट्रक्शन PUSH है तो इसे बढ़ाकर (increment), POP के लिए घटाकर (decrement), और NOP के लिए इसे समान रखकर। ध्यान दें कि हम वर्तमान पंक्ति के आधार पर sp के लिए अगले को अपडेट करते हैं। इसलिए, इटरेशन 0 पर, हम पंक्ति 1 को इस प्रकार अपडेट करते हैं:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_apop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & \boxed{0}& & & & \\\hline0 & \color{orange}{1} & 0 & - & \boxed{1}& & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & & & & & \\\hline0 & 0 & \color{orange}{1} & - & & & & & \\\hline0 & \color{orange}{1} & 0 & - & & & & & \\\hline\end{array}

अर्थात्, क्योंकि वर्तमान is_push 1 है, और वर्तमान sp 0 है, हम अगले सेल में 0 + 1 लिखते हैं। फिर हम शेष sp कॉलम को निम्नानुसार भरते हैं:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & \\\hline0 & \color{orange}{1} & 0 & - & 3 & & & & \\\hline\end{array}

फिर हम पुश मानों को उचित सेल में लिखते हैं, जो केवल इस शर्त पर sp और arg कॉलम का उपयोग करके किया जाता है कि क्या is_push 1 है। ध्यान दें कि इस चरण में केवल वे पंक्तियाँ भरी जाती हैं जहाँ is_push == 1 है:

\begin{array}{|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & \\\hline0 & \color{orange}{1} & 0 & - & 3 & & & & \\\hline\end{array}

ध्यान दें कि पिछले मान कॉपी नहीं किए गए हैं — हम इसे बाद के अनुभाग में ठीक करेंगे।

शून्यवीं (zeroth) पंक्ति को हैंडल करना

शून्यवीं पंक्ति अद्वितीय है क्योंकि यह अपने ऊपर की पंक्ति से मान कॉपी नहीं करती है। इस आधार पर ब्रांचिंग से बचने के लिए कि हम शून्यवीं पंक्ति में हैं या नहीं, हम टेबल को आवश्यकता से एक पंक्ति बड़ा बनाते हैं, और फिर हम पंक्ति 1 से अपने कंस्ट्रेंट्स बनाना शुरू करते हैं। इस तरह, प्रत्येक पंक्ति हमेशा अपने ऊपर की पंक्ति को कॉपी करती है।

आगामी कोड डेमो में, हम 0वीं पंक्ति में कंस्ट्रेंट्स को हार्डवायर (hardwire) करते हैं क्योंकि बाद में, 0वीं पंक्ति को इस बात के लिए एक कॉर्नर केस (corner case) के रूप में मानना असुविधाजनक होगा कि हम पिछली पंक्ति के मानों को कॉपी करते हैं या नहीं।

पिछली पंक्ति को कॉपी करना

अब, हमें यह सुनिश्चित करने की आवश्यकता है कि एक पंक्ति से दूसरी पंक्ति में मान ठीक से कॉपी किए गए हैं। एक सेल अपने ऊपर के मान को अगली पंक्ति के स्टैक पॉइंटर माइनस 1 तक कॉपी करता है। याद रखें, sp स्टैक के ऊपर खाली स्थान को इंगित करता है, इसलिए sp - 1 स्टैक के शीर्ष को इंगित करता है।

कॉलम और स्टैक शब्दावली (Terminology)

चूँकि हम स्टैक को एक टेबल में “बगल में (sideways)” स्टोर कर रहे हैं, इसलिए हम स्टैक के निचले भाग को कॉलम 0, उस कॉलम के शीर्ष पर स्थित आइटम (यदि यह मौजूद है) को कॉलम 1, और इसी तरह आगे संदर्भित करेंगे। जब हम “कॉलम” कहते हैं तो हमारा मतलब स्टैक के “इंडेक्स” से होता है यदि सबसे निचला वाला शून्य है।

कॉपी करने के लिए कंस्ट्रेंट्स

यदि is_push = 1 है, तो स्टैक 0..sp - 1 (इन्हें मिलाकर) के सभी आइटम्स कॉपी किए जाने चाहिए। sp वाले सेल में नया बढ़ाया गया (incremented) मान होगा। यह पूरे स्टैक को कॉपी करता है।
यदि is_nop = 1 है, तो स्टैक 0..sp - 1 (इन्हें मिलाकर) के सभी आइटम्स कॉपी किए जाने चाहिए। sp वाले सेल में कुछ भी नहीं लिखा जाता है। यह पूरे स्टैक को कॉपी करता है।
यदि is_pop = 1 है, तो स्टैक 0..sp - 2 (इन्हें मिलाकर) के सभी आइटम्स कॉपी किए जाने चाहिए। याद रखें, sp स्टैक के ऊपर एक खाली सेल को इंगित करता है, इसलिए sp - 1 वह मान है जिसे पॉप किया जाएगा। sp - 2 और उससे नीचे की सभी चीजों को कॉपी किया जाना चाहिए। यह स्टैक के शीर्ष को छोड़कर सब कुछ कॉपी करता है।

2 और 3 की शर्तों में कॉर्नर केस होते हैं यदि स्टैक पॉइंटर क्रमशः 0 या 1 है, क्योंकि अंडरफ्लो (underflow) हो जाएगा। इसलिए, हमें विशेष कॉलम चाहिए जो यह दर्शाते हों कि क्या sp 2 या 1 से कम है, और हमें कॉपी करने की प्रक्रिया को अलग तरह से संभालना होगा। विशेष रूप से:

यदि sp = 0 है, तो कुछ भी कॉपी नहीं किया जाएगा
यदि sp = 1 है, तो हम कॉलम 0 के सेल को तभी कॉपी करेंगे जब इंस्ट्रक्शन NOP या PUSH हो

हम अतिरिक्त कॉलम (copy0, copy1, copy2, copy3) बनाते हैं जो फ़्लैग के रूप में काम करते हैं जो यह दर्शाते हैं कि क्या (column0, column1, column2, column3) के लिए मान अगली पंक्ति में कॉपी किया जाएगा।

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & & & & & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

प्रारंभिक स्थितियों (initial conditions) को हैंडल करना

0वीं पंक्ति के लिए कंस्ट्रेंट्स बनाते समय हमारे पास एक और कॉर्नर केस है — यदि हम पिछली पंक्ति से मानों को कॉपी करने का प्रयास करते हैं, तो हम ऐरे को अंडरफ्लो कर देंगे। इसलिए, हमें इस पंक्ति को अलग तरह से मानना होगा — हम पहली पंक्ति के मान को अधिक “हार्डकोडेड” तरीके से भरते हैं और फिर पुनरावृत्त (iteratively) रूप से पंक्ति 1 से शुरू करके कंस्ट्रेंट्स बनाते हैं।

यह निर्धारित करना कि `copy` शून्य होना चाहिए या एक

पहले के कंस्ट्रेंट्स को याद करें:

यदि is_push = 1 है, तो सभी मान 0..sp - 1 (इन्हें मिलाकर) कॉपी किए जाने चाहिए। sp वाले सेल में नया मान होगा।
यदि is_nop = 1 है, तो सभी मान 0..sp - 1 (इन्हें मिलाकर) कॉपी किए जाने चाहिए। sp वाले सेल में कुछ भी नहीं लिखा जाता है।
यदि is_pop = 1 है, तो सभी मान 0..sp - 2 (इन्हें मिलाकर) कॉपी किए जाने चाहिए। याद रखें, sp स्टैक के ऊपर एक खाली सेल को इंगित करता है, इसलिए sp - 1 वह मान है जिसे पॉप किया जाएगा। sp - 2 और उससे नीचे की सभी चीजों को कॉपी किया जाना चाहिए।

हम इन्हें दो शर्तों A और B में संक्षेप में प्रस्तुत कर सकते हैं:

A. यदि sp 1 या उससे अधिक है, और हमारा कॉलम sp से 1 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन PUSH या NOP है, तो हमें कॉपी करना चाहिए

B. यदि sp 2 या उससे अधिक है, और हमारा कॉलम sp से 2 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन POP है, तो हमें कॉपी करना चाहिए

यदि हमारा कॉलम उपरोक्त शर्तों में से किसी को पूरा नहीं करता है, तो हम कॉपी नहीं करते हैं। इनमें शामिल हैं:

वर्तमान कॉलम स्टैक पॉइंटर पर या उसके ऊपर है
वर्तमान कॉलम स्टैक पॉइंटर से 1 नीचे है, और वर्तमान इंस्ट्रक्शन पॉप है
स्टैक पॉइंटर = 0

उपरोक्त नियमों का उपयोग करते हुए, आइए टेबल को भरें। 0वीं पंक्ति पर, sp = 0 है, इसलिए सभी कॉपी कॉलम 0 होंगे:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

पहले (1st) इंडेक्स वाली पंक्ति पर, sp 1 या उससे अधिक है, लेकिन इंस्ट्रक्शन POP है, लेकिन किसी भी कॉलम के लिए स्थिति A या B पूरी नहीं होती है, इसलिए हम कॉपी नहीं करते हैं:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & & & & & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

दूसरी (2nd) पंक्ति पर, sp 0 है, इसलिए कुछ भी कॉपी नहीं होता है:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & & & & & & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

तीसरी (3rd) पंक्ति पर, sp 1 है और इंस्ट्रक्शन PUSH है, इसलिए column0 स्थिति A को पूरा करता है:

“यदि sp 1 या उससे अधिक है, और हमारा कॉलम sp से 1 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन PUSH या NOP है, तो हमें कॉपी करना चाहिए”

और copy0 को 1 पर सेट किया गया है:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & \boxed{1} & 0 & 0 & 0 & 16 & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & & & & & & & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

चौथी (4th) पंक्ति पर, sp 2 है और इंस्ट्रक्शन PUSH है, इसलिए column 0 और column 1 स्थिति A को पूरा करते हैं:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & 1 & 0 & 0 & 0 & 16 & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & \boxed{1} & \boxed{1} & 0 & 0 & 16 & 15 & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & & & & & & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & & & & & & & & \\\hline\end{array}

पाँचवीं (5th) पंक्ति पर, sp 3 है और इंस्ट्रक्शन NOP है, इसलिए column 0, 1, और 2 स्थिति A को पूरा करते हैं, जो है “यदि sp 1 या उससे अधिक है, और हमारा कॉलम sp से 1 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन PUSH या NOP है, तो हमें कॉपी करना चाहिए”:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} & & & & \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 &0 & 0& 0&0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0& & & & \\\hline\color{orange}{1} & 0 & 0 & \texttt{16} & 0 & 0 & 0& 0& 0& 16 & & & \\\hline\color{orange}{1} & 0 & 0 & \texttt{15} & 1 & 1& 0& 0& 0& 16& 15 & & \\\hline\color{orange}{1} & 0 & 0 & \texttt{4} & 2 & 1& 1& 0& 0&16 &15 & 4 & \\\hline0 & 0 & \color{orange}{1} & \texttt{-} & 3 &\boxed{1} &\boxed{1} & \boxed{1}&0 & 16& 15& 4& \\\hline0 & \color{orange}{1} & 0 & \texttt{-} & 1 & & & & & & & & \\\hline\end{array}

छठी (6th) पंक्ति पर, sp 1 है और इंस्ट्रक्शन POP है, इसलिए हम स्थिति B का उपयोग करते हैं:

“यदि sp 2 या उससे अधिक है, और हमारा कॉलम sp से 2 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन POP है, तो हमें कॉपी करना चाहिए”

इसका मतलब है कि columns 0 और 1 कॉपी किए जाएंगे:

\begin{array}{|c|c|c|c|c|c|c|c|c||c|c|c|c|}\hline\texttt{is\_push} & \texttt{is\_pop} & \texttt{is\_nop} & \texttt{arg} & \texttt{sp} & \texttt{copy0} & \texttt{copy1} & \texttt{copy2} & \texttt{copy3} \\\hline\color{orange}{1} & 0 & 0 & 10 & 0 & 0 & 0 & 0 & 0 & 10 & & & \\\hline0 & \color{orange}{1} & 0 & - & 1 & 0 & 0 & 0 & 0 & & & & \\\hline\color{orange}{1} & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 16 & & & \\\hline\color{orange}{1} & 0 & 0 & 15 & 1 & 1 & 0 & 0 & 0 & 16 & 15 & & \\\hline\color{orange}{1} & 0 & 0 & 4 & 2 & 1 & 1 & 0 & 0 & 16 & 15 & 4 & \\\hline0 & 0 & \color{orange}{1} & - & 3 & 1 & 1 & 1 & 0 & 16 & 15 & 4 & \\\hline0 & \color{orange}{1} & 0 & - & 1 & \boxed{1}&\boxed{1} & 0& 0& & & & \\\hline\end{array}

कॉपी शर्तों का Circom इम्प्लीमेंटेशन

यह निर्धारित करने के लिए कि क्या ऊपर से किसी मान को कॉपी किया जाना चाहिए, हम Circom में एक विशेष कंपोनेंट बना सकते हैं।

A. यदि sp 1 या उससे अधिक है, और हमारा कॉलम sp से 1 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन PUSH या NOP है, तो हमें कॉपी करना चाहिए
B. यदि sp 2 या उससे अधिक है, और हमारा कॉलम sp से 2 इंडेक्स नीचे है, और वर्तमान इंस्ट्रक्शन POP है, तो हमें कॉपी करना चाहिए

इस कंपोनेंट का उपयोग एक लूप में यह निर्धारित करने के लिए किया जाएगा कि किसी विशेष कॉलम j को कॉपी किया जाना चाहिए या नहीं। यह out = 1 सेट करता है यदि किसी विशेष कॉलम को कॉपी किया जाना चाहिए। यह कंपोनेंट प्रत्येक पंक्ति के लिए प्रत्येक कॉलम पर लागू होता है।

include "circomlib/comparators.circom";
include "circomlib/gates.circom";

// RETURNS 1 IF ALL THE INPUTS ARE 1
template AND3() {
  signal input in[3];
  signal output out;
  
  signal temp;
  temp <== in[0] * in[1];
  out <== temp * in[2];
}

// j is the column number
// bits is how many bits we need
// for the LessEqThan component
template ShouldCopy(j, bits) {
  signal input sp;
  signal input is_pop;
  signal input is_push;
  signal input is_nop;
  
  // out = 1 if should copy
  signal output out;
  
  // sanity checks
  is_pop + is_push + is_nop === 1;
  is_nop * (1 - is_nop) === 0;
  is_push * (1 - is_push) === 0;
  is_pop * (1 - is_pop) === 0;
  
  // it's cheaper to compute ≠ 0 than > 0 to avoid
  // converting the number to binary
  signal spEqZero;
  signal spGteOne;
  spEqZero <== IsZero()(sp);
  spGteOne <== 1 - spEqZero;
  
  // it's cheaper to compute ≠ 0 and ≠ 1 than ≥ 2
  signal spEqOne;
  signal spGteTwo;
  spEqOne <== IsEqual()([sp, 1]);
  spGteTwo <== (1 - spEqOne) * (1 - spEqZero);
  
  // the current column is 1 or more 
  // below the stack pointer
  signal oneBelowSp <== LessEqThan(bits)([j, sp - 1]);
  
  // the current column is 2 or more
  // below the stack pointer
  signal twoBelowSP <== LessEqThan(bits)([j, sp - 2]);
  
  // condition A
  component a3A = AND3();
  a3A.in[0] <== spGteOne;
  a3A.in[1] <== oneBelowSp;
  a3A.in[2] <== is_push + is_nop;
  
  // condition B
  component a3B = AND3();
  a3B.in[0] <== spGteTwo;
  a3B.in[1] <== twoBelowSP;
  a3B.in[2] <== is_pop;
  
  component or = OR();
  or.a <== a3A.out;
  or.b <== a3B.out;  
  out <== or.out;
}

हम यह निर्धारित करने के लिए कि पिछले स्टैक के किन हिस्सों को नए स्टैक में कॉपी किया जाना चाहिए, एक लूप में उपरोक्त कंपोनेंट का उपयोग कर सकते हैं। निम्नलिखित टेम्प्लेट यह निर्धारित करने के लिए 0 या 1 का ऐरे लौटाता है कि किन कॉलमों को कॉपी किया जाना चाहिए। उदाहरण के लिए, यदि 4 कॉलम हैं और पहले 2 कॉलमों को कॉपी किया जाना चाहिए, तो यह [1, 1, 0, 0] लौटाता है:

template CopyStack(m) {
  var nBits = 4;
    signal output out[m];
    signal input sp;
    signal input is_pop;
    signal input is_push;
    signal input is_nop;

    component ShouldCopys[m];
    
    // loop over the columns
    for (var j = 0; j < m; j++) {
        ShouldCopys[j] = ShouldCopy(j, nBits);
        ShouldCopys[j].sp <== sp;
        ShouldCopys[j].is_pop <== is_pop;
        ShouldCopys[j].is_push <== is_push;
        ShouldCopys[j].is_nop <== is_nop;
        out[j] <== ShouldCopys[j].out;
    }
}

फाइनल स्टैक

निम्नलिखित कोड हमारे स्टैक का फाइनल इम्प्लीमेंटेशन है, जो सभी कंपोनेंट्स को एक साथ जोड़ता है। चूँकि हम पहले ही ShouldCopy और CopyStack के लिए कंपोनेंट्स दिखा चुके हैं, पाठक सीधे अंतिम कंपोनेंट StackBuilder पर जा सकते हैं। पिछले कंपोनेंट्स पहले के अनुभागों से हैं। हम इसे एक ही फ़ाइल में रखते हैं ताकि पाठक इसे टेस्ट करने के लिए आसानी से zkrepl में कॉपी और पेस्ट कर सकें:

include "circomlib/comparators.circom";
include "circomlib/gates.circom";

template AND3() {
  signal input in[3];
  signal output out;
  
  signal temp;
  temp <== in[0] * in[1];
  out <== temp * in[2];
}

// j is the column number
// bits is how many bits we need
// for the LessEqThan component
template ShouldCopy(j, bits) {
  signal input sp;
  signal input is_pop;
  signal input is_push;
  signal input is_nop;
  
  // out = 1 if should copy
  signal output out;
  
  // sanity checks
  is_pop + is_push + is_nop === 1;
  is_nop * (1 - is_nop) === 0;
  is_push * (1 - is_push) === 0;
  is_pop * (1 - is_pop) === 0;
  
  // it's cheaper to compute ≠ 0 than > 0 to avoid
  // converting the number to binary
  signal spEqZero;
  signal spGteOne;
  spEqZero <== IsZero()(sp);
  spGteOne <== 1 - spEqZero;
  
  // it's cheaper to compute ≠ 0 and ≠ 1 than ≥ 2
  signal spEqOne;
  signal spGteTwo;
  spEqOne <== IsEqual()([sp, 1]);
  spGteTwo <== (1 - spEqOne) * (1 - spEqZero);
  
  // the current column is 1 or more 
  // below the stack pointer
  signal oneBelowSp <== LessEqThan(bits)([j, sp - 1]);
  
  // the current column is 2 or more
  // below the stack pointer
  signal twoBelowSP <== LessEqThan(bits)([j, sp - 2]);
  
  // condition A
  component a3A = AND3();
  a3A.in[0] <== spGteOne;
  a3A.in[1] <== oneBelowSp;
  a3A.in[2] <== is_push + is_nop;
  
  // condition B
  component a3B = AND3();
  a3B.in[0] <== spGteTwo;
  a3B.in[1] <== twoBelowSP;
  a3B.in[2] <== is_pop;
  
  component or = OR();
  or.a <== a3A.out;
  or.b <== a3B.out;  
  out <== or.out;
}

template CopyStack(m) {
  var nBits = 4;
    signal output out[m];
    signal input sp;
    signal input is_pop;
    signal input is_push;
    signal input is_nop;

    component ShouldCopys[m];
    signal copy[m];
    
    // loop over the columns
  for (var j = 0; j < m; j++) {
    ShouldCopys[j] = ShouldCopy(j, nBits);
    ShouldCopys[j].sp <== sp;
    ShouldCopys[j].is_pop <== is_pop;
    ShouldCopys[j].is_push <== is_push;
    ShouldCopys[j].is_nop <== is_nop;
    out[j] <== ShouldCopys[j].out;
  }
}

// n is how many instructions we can handle
// since all the instructions might be push,
// our stack needs capacity of up to n
template StackBuilder(n) {
  var NOP = 0;
  var PUSH = 1;
  var POP = 2;

  signal input instr[2 * n];
  
  // we add one extra row for sp because
  // our algorithm always writes to the
  // next row and we don't want to conditionally
  // check for an array-out-of-bounds
  signal output sp[n + 1];

  signal output stack[n][n];

  var IS_NOP = 0;
  var IS_PUSH = 1;
  var IS_POP = 2;
  var ARG = 3;
  
  // metaTable is the columns IS_NOP, IS_PUSH, IS_POP, ARG
  signal metaTable[n][4];

  // first instruction must be PUSH or NOP
  (instr[0] - PUSH) * (instr[0] - NOP) === 0;

  signal first_op_is_push;
  first_op_is_push <== IsEqual()([instr[0], PUSH]);

  // if the first op is NOP, we are forcing the first
  // value to be zero, but this is where the stack
  // pointer is, so it doesn't matter
  stack[0][0] <== first_op_is_push * instr[1];

  // initialize the rest of the first stack to be zero
  for (var i = 1; i < n; i++) {
      stack[0][i] <== 0;
  }

  // we fill out the 0th elements to avoid
  // uninitialzed signals. For a particular
  // execution, we only want one possible witness
  // to correspond to a particular execution
  sp[0] <== 0;
  sp[1] <== first_op_is_push;
  metaTable[0][IS_PUSH] <== first_op_is_push;
  metaTable[0][IS_POP] <== 0;
  metaTable[0][IS_NOP] <== 1 - first_op_is_push;
  metaTable[0][ARG] <== instr[1];

  // spBranch is what we add to the previous
  // stack pointer based on the opcode.
  // Could be 1, 0, or -1 depending on the
  // opcode. Since the first opcode
  // cannot be POP, -1 is not an option here.
  var SAME = 0;
  var INC = 1;
  var DEC = 2;
  signal spBranch[n][3];
  spBranch[0][INC] <== first_op_is_push * 1;
  spBranch[0][SAME] <== (1 - first_op_is_push) * 0;
  spBranch[0][DEC] <== 0;

  // populate the first row of the metaTable
  // and the stack pointer
  component EqPush[n];
  component EqNop[n];
  component EqPop[n];

  component eqSP[n][n];
  signal eqSPAndIsPush[n][n];
  for (var i = 0; i < n; i++) {
      eqSPAndIsPush[0][i] <== 0;
  }

  // signals and components for copying
  component CopyStack[n];
  signal previousCellIfShouldCopy[n][n];
  for (var i = 0; i < n; i++) {
    previousCellIfShouldCopy[0][i] <== 0;
  }
  for (var i = 1; i < n; i++) {
    // check which opcode we are executing
    EqPush[i] = IsEqual();
    EqPush[i].in[0] <== instr[2 * i];
    EqPush[i].in[1] <== PUSH;
    metaTable[i][IS_PUSH] <== EqPush[i].out;

    EqNop[i] = IsEqual();
    EqNop[i].in[0] <== instr[2 * i];
    EqNop[i].in[1] <== NOP;
    metaTable[i][IS_NOP] <== EqNop[i].out;

    EqPop[i] = IsEqual();
    EqPop[i].in[0] <== instr[2 * i];
    EqPop[i].in[1] <== POP;
    metaTable[i][IS_POP] <== EqPop[i].out;

    // get the instruction argument
    metaTable[i][ARG] <== instr[2 * i + 1];

    // if it is a push, write to the stack
    // if it is a copy, write to the stack
    CopyStack[i] = CopyStack(n);
    CopyStack[i].sp <== sp[i];
    CopyStack[i].is_push <== metaTable[i][IS_PUSH];
    CopyStack[i].is_nop <== metaTable[i][IS_NOP];
    CopyStack[i].is_pop <== metaTable[i][IS_POP];
    for (var j = 0; j < n; j++) {
      previousCellIfShouldCopy[i][j] <== CopyStack[i].out[j] * stack[i - 1][j];

      eqSP[i][j] = IsEqual();
      eqSP[i][j].in[0] <== j;
      eqSP[i][j].in[1] <== sp[i];
      eqSPAndIsPush[i][j] <== eqSP[i][j].out * metaTable[i][IS_PUSH];

      // we will either PUSH or COPY or implicilty assign 0
      stack[i][j] <== eqSPAndIsPush[i][j] * metaTable[i][ARG] + previousCellIfShouldCopy[i][j];
    }

    // write to the next row's stack pointer
    spBranch[i][INC] <== metaTable[i][IS_PUSH] * (sp[i] + 1);
    spBranch[i][SAME] <== metaTable[i][IS_NOP] * (sp[i]);
    spBranch[i][DEC] <== metaTable[i][IS_POP] * (sp[i] - 1);
    sp[i + 1] <== spBranch[i][INC] + spBranch[i][SAME] + spBranch[i][DEC];
  }
}

component main = StackBuilder(3);

/* INPUT = {
  "instr": [1, 16, 1, 20, 1, 22]
} */

सारांश (Summary)

समय के साथ बदलने वाले डेटा स्ट्रक्चर को मॉडल करने के लिए, हम सभी संभावित स्टेट ट्रांज़िशन (state transitions) के लिए कंस्ट्रेंट्स लिखते हैं, फिर फ़्लैग्स के आधार पर उन स्टेट ट्रांज़िशन को सक्रिय करते हैं। फ़्लैग्स को उस विशेष स्टेट ट्रांज़िशन के इंस्ट्रक्शन से मेल खाने के लिए कंस्ट्रेंट किया जाता है।

यद्यपि स्टैक डेटा स्ट्रक्चर के एरिथमेटिज़ेशन (arithmetization) को समझना कठिन लग सकता है, लेकिन अब हम वह लगभग सब कुछ जानते हैं जो हमें यह समझने के लिए आवश्यक है कि स्टैक-आधारित ZKVM कैसे बनाया जाए, जिसे हम अगले अध्याय में कवर करेंगे। एक स्टैक-आधारित ZKVM बनाने के लिए, हम बस इस अध्याय में प्रस्तुत इंस्ट्रक्शंस और उनके संबंधित कंस्ट्रेंट्स को ZKVM के लिए ऑपकोड से मेल खाने के लिए संशोधित करते हैं।

सामान्य तौर पर, अधिकांश सार्थक कंप्यूटेशन्स को एक प्रारंभिक स्टेट के रूप में मॉडल किया जा सकता है जो अंतिम परिणाम तक पहुंचने तक वृद्धिशील (incrementally) रूप से अपडेट होता है। इस अध्याय में हमने जो स्टैक दिखाया है वह इसका एक विशेष मामला (special case) मात्र है।