लगभग सभी ZK-Proof एल्गोरिदम संक्षिप्तता (succinctness) प्राप्त करने के लिए Schwartz-Zippel Lemma पर निर्भर करते हैं।

Schwartz-Zippel Lemma यह बताता है कि यदि हमें दो बहुपद (polynomials) $p(x)$ और $q(x)$ दिए गए हैं जिनकी डिग्री क्रमशः $d_p$ और $d_q$ है, और यदि $p(x) \neq q(x)$ है, तो उन बिंदुओं की संख्या जहाँ $p(x)$ और $q(x)$ एक-दूसरे को काटते हैं (intersect करते हैं), $\mathsf{max}(d_p, d_q)$ से कम या उसके बराबर होती है।

आइए कुछ उदाहरणों पर विचार करें।

उदाहरण बहुपद (polynomials) और Schwartz-Zippel Lemma

एक परवलय (parabola) को पार करती हुई एक सीधी रेखा

मान लीजिए कि बहुपद $p(x) = x$ और $q(x) = x^2$ हैं। वे $x = 0$ और $x = 1$ पर एक-दूसरे को काटते हैं।

वे दो बिंदुओं पर एक-दूसरे को काटते हैं, जो कि बहुपद $y = x$ और $y = x^2$ के बीच की अधिकतम डिग्री (maximum degree) है।

एक डिग्री तीन का बहुपद और एक डिग्री एक का बहुपद

मान लीजिए कि बहुपद $p(x) = x^3$ और $q(x) = x$ हैं। ये बहुपद $x = -1$, $x = 0$, और $x = 1$ पर एक-दूसरे को काटते हैं और इसके अलावा कहीं नहीं। प्रतिच्छेदन (intersections) की संख्या बहुपदों की अधिकतम डिग्री द्वारा सीमित होती है, जो इस मामले में 3 है।

Finite fields में बहुपद और Schwartz-Zippel Lemma

Schwartz-Zippel Lemma finite fields में बहुपदों के लिए लागू होता है (अर्थात, सभी गणनाएँ एक अभाज्य (prime) $p$ के modulo की जाती हैं)।

बहुपद समानता परीक्षण (Polynomial equality testing)

हम यह परीक्षण कर सकते हैं कि दो बहुपद समान हैं या नहीं, यह जाँच कर कि क्या उनके सभी गुणांक (coefficients) समान हैं, लेकिन इसमें $\mathcal{O}(d)$ समय लगता है, जहाँ $d$ बहुपद की डिग्री है।

इसके बजाय हम एक यादृच्छिक बिंदु (random point) $u$ पर बहुपदों का मूल्यांकन कर सकते हैं और $\mathcal{O}(1)$ समय में मूल्यांकनों की तुलना कर सकते हैं।

अर्थात, एक finite field $\mathbb{F}_{p}$ में, हम $[0,p)$ से एक यादृच्छिक मान (random value) $u$ चुनते हैं। फिर हम $y_f=f(u)$ और $y_g=g(u)$ का मूल्यांकन करते हैं। यदि $y_f = y_g$ है, तो दो में से एक बात सत्य होनी चाहिए:

1. $f(x) = g(x)$
2. $f(x) \neq g(x)$ और हमने उन $d$ बिंदुओं में से एक को चुना है जहाँ वे एक-दूसरे को काटते हैं जहाँ $d = \mathsf{max}(\deg(f), \deg(g))$ है।

यदि $d \ll p$ है, तो स्थिति 2 के होने की संभावना इतनी कम होती है कि उसे नगण्य (negligible) माना जा सकता है।

उदाहरण के लिए, यदि field $\mathbb{F}_{p}$ में $p \approx 2^{254}$ (एक uint256 से थोड़ा छोटा) है, और यदि बहुपद एक मिलियन (दस लाख) डिग्री से अधिक बड़े नहीं हैं, तो उस बिंदु को चुनने की प्रायिकता (probability) जहाँ वे एक-दूसरे को काटते हैं, निम्नलिखित है:

इस पैमाने को समझने के लिए, ब्रह्मांड में परमाणुओं (atoms) की संख्या लगभग $10^{78}$ से $10^{82}$ के बीच है, इसलिए यह अत्यंत असंभव है कि हम एक ऐसा बिंदु चुनेंगे जहाँ बहुपद एक-दूसरे को काटते हैं, यदि बहुपद समान नहीं हैं।

दो वेक्टर्स (vectors) समान हैं या नहीं, यह जाँचने के लिए Schwartz-Zippel Lemma का उपयोग करना

हम दो वेक्टर्स समान हैं या नहीं, यह जाँचने के लिए Lagrange interpolation को Schwartz-Zippel Lemma के साथ जोड़ सकते हैं।

सामान्यतः, हम वेक्टर समानता (vector equality) का परीक्षण यह तुलना करके करेंगे कि क्या वेक्टर्स के सभी $n$ घटक (components) समान हैं।

इसके बजाय, यदि हम वेक्टर्स को इंटरपोलेट (interpolate) करने के लिए $x$ मानों के एक सामान्य सेट (मान लें $[1,2,..,n]$) का उपयोग करते हैं:

1. हम प्रत्येक वेक्टर के लिए एक बहुपद $f(x)$ और $g(x)$ इंटरपोलेट कर सकते हैं
2. एक यादृच्छिक बिंदु (random point) $u$ चुनें
3. $u$ पर बहुपदों का मूल्यांकन (evaluate) करें
4. जाँचें कि क्या $f(u) = g(u)$ है

हालाँकि बहुपदों की गणना करने में अधिक काम लगता है, लेकिन अंतिम जाँच बहुत सस्ती (कम खर्चीली) होती है।

Python में इस गणना को करने का एक उदाहरण यहाँ दिया गया है:

Copy
import galois
import numpy as np

p = 103
GF = galois.GF(p)

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

# arbitrary vectors
v1 =  GF(np.array([4,8,19]))
v2 =  GF(np.array([4,8,19]))


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

p1 = L(v1)
p2 = L(v2)

import random
u = random.randint(0, p)

lhs = p1(u)
rhs = p2(u)

# only one check required
assert lhs == rhs

ZK Proofs में Schwartz-Zippel Lemma का उपयोग करना

हमारा अंतिम लक्ष्य यह है कि प्रूवर (prover) वेरिफायर (verifier) को डेटा की एक छोटी स्ट्रिंग भेजे जिसे वेरिफायर जल्दी से जाँच सके।

ज्यादातर समय, एक ZK proof मूल रूप से एक यादृच्छिक बिंदु पर मूल्यांकित (evaluated) किया गया एक बहुपद ही होता है।

हमें जिस कठिनाई को हल करना है वह यह है कि हम नहीं जानते कि क्या बहुपद का मूल्यांकन ईमानदारी से किया गया है – किसी तरह हमें यह भरोसा करना होगा कि प्रूवर $f(u)$ का मूल्यांकन करते समय झूठ नहीं बोल रहा है।

लेकिन इससे पहले कि हम वहां पहुंचें, हमें यह सीखना होगा कि एक संपूर्ण अर्थमेटिक सर्किट (arithmetic circuit) को एक यादृच्छिक बिंदु पर मूल्यांकित बहुपदों के एक छोटे सेट के रूप में कैसे दर्शाया जाए, जो कि Quadratic Arithmetic Programs के लिए मुख्य प्रेरणा (motivation) है।