फाइनाइट फील्ड्स में एलिप्टिक कर्व्स कैसे दिखते हैं?

स्मूथ एलिप्टिक कर्व्स की कल्पना करना आसान है, लेकिन एक फाइनाइट फील्ड पर एलिप्टिक कर्व्स कैसे दिखते हैं?

नीचे $y² = x³ + 3 \pmod {23}$ का एक प्लॉट दिया गया है:

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

जब हम समीकरण को हल करते हैं, तो हर $x$ वैल्यू के परिणामस्वरूप $y$ के लिए इंटिजर वैल्यू नहीं मिलेगी, इसलिए $x$ की उस वैल्यू पर कोई बिंदु मौजूद नहीं होगा। आप ऊपर दिए गए प्लॉट में ऐसे गैप्स देख सकते हैं।

इस प्लॉट को जनरेट करने का कोड बाद में प्रदान किया जाएगा।

अभाज्य संख्या (prime number) प्लॉट को काफी हद तक बदल देती है

यहाँ क्रमशः मॉड्यूलो 11, 23, 31 और 41 पर $y² = x³ + 3$ के कुछ प्लॉट दिए गए हैं। मॉड्युलस जितना अधिक होगा, उसमें उतने ही अधिक बिंदु होंगे, और प्लॉट उतना ही अधिक जटिल दिखाई देगा।

हमने पिछले लेख में स्थापित किया था कि “कनेक्ट एंड फ्लिप” ऑपरेशन के साथ एलिप्टिक कर्व के बिंदु एक ग्रुप होते हैं। जब हम इसे एक फाइनाइट फील्ड पर करते हैं, तो यह एक ग्रुप ही रहता है, लेकिन यह एक साइक्लिक ग्रुप बन जाता है, जो हमारे एप्लिकेशन के लिए बेहद उपयोगी है। यह साइक्लिक क्यों है, इसके लिए दुर्भाग्य से कुछ बहुत जटिल गणित की आवश्यकता होगी, इसलिए आपको अभी के लिए इसे ऐसे ही स्वीकार करना होगा। लेकिन यह बहुत आश्चर्यजनक नहीं होना चाहिए। हमारे पास सीमित संख्या में बिंदु हैं, इसलिए $(x + 1)G, (x + 2)G, … (x + \text{order} - 1)G$ को निष्पादित करके प्रत्येक बिंदु को जनरेट करना कम से कम तर्कसंगत तो लगना ही चाहिए।

क्रिप्टोग्राफी के एप्लिकेशन में, $p$ का बड़ा होना आवश्यक है। व्यवहार में, यह 200 बिट्स से अधिक होता है। हम बाद के सेक्शन में इस पर फिर से विचार करेंगे।

बैकग्राउंड

फील्ड एलिमेंट

हम इस लेख में “फील्ड एलिमेंट” शब्द का बहुत उपयोग करने वाले हैं, और उम्मीद है कि हमारे पिछले ट्यूटोरियल (विशेष रूप से finite fields पर) से आप पहले से ही इस शब्द से सहज होंगे। लेकिन यदि नहीं, तो यह एक धनात्मक पूर्णांक (positive integer) है जो मॉड्यूलो ऑपरेशन के अंदर होता है।

अर्थात्, यदि हम मॉड्यूलो 11 पर जोड़ (addition) करते हैं, तो उस सेट से फाइनाइट फील्ड एलिमेंट्स $\set{0,1,…,9,10}$ होंगे। “इंटिजर्स” कहना सही नहीं है, भले ही हमारे Python उदाहरणों में हम उसी डेटा प्रकार का उपयोग करेंगे। एक अभाज्य संख्या के मॉड्यूलो पर जोड़ करते समय आपके पास ऋणात्मक (negative) फील्ड एलिमेंट नहीं हो सकता है (यद्यपि इंटिजर्स ऋणात्मक हो सकते हैं)। एक फाइनाइट फील्ड में एक “ऋणात्मक” संख्या बस किसी अन्य संख्या का एडिटिव इनवर्स (additive inverse) होती है, अर्थात्, एक ऐसी संख्या जिसे एक साथ जोड़ने पर परिणाम शून्य होता है। उदाहरण के लिए, मॉड्यूलो 11 के एक फाइनाइट फील्ड में, 4 को “-7” माना जा सकता है क्योंकि $7 + 4 \pmod {11}$ $0$ होता है, यह तुलनात्मक रूप से वैसा ही है जैसे सामान्य संख्याओं के लिए 7 + (-7) शून्य होता है।

रैशनल नंबर्स (rational numbers) के फील्ड पर, गुणा (multiplication) का आइडेंटिटी एलिमेंट 1 होता है, और किसी संख्या का इनवर्स बस अंश (numerator) और हर (denominator) को उलट देना होता है। उदाहरण के लिए, 500/303, 303/500 का इनवर्स है क्योंकि यदि आप उन्हें गुणा करते हैं, तो आपको 1 मिलता है।

एक फाइनाइट फील्ड में, किसी एलिमेंट का इनवर्स वह संख्या है जिससे आप उसे गुणा करके फाइनाइट फील्ड एलिमेंट 1 प्राप्त करते हैं। उदाहरण के लिए, मॉड्यूलो 23 में, 6, 4 का इनवर्स है क्योंकि जब आप उन्हें मॉड्यूलो 23 पर एक साथ गुणा करते हैं, तो आपको 1 मिलता है। जब फील्ड का ऑर्डर एक अभाज्य संख्या होता है, तो शून्य को छोड़कर हर संख्या का एक इनवर्स होता है।

साइक्लिक ग्रुप्स

एक साइक्लिक group एक ऐसा ग्रुप है जिसमें प्रत्येक एलिमेंट को एक जनरेटर एलिमेंट से शुरू करके और ग्रुप के बाइनरी ऑपरेटर को बार-बार लागू करके कंप्यूट किया जा सकता है।

जोड़ के अंतर्गत इंटिजर्स मॉड्यूलो 11 इसका एक बहुत ही सरल उदाहरण है। यदि आपका जनरेटर 1 है, और आप जनरेटर को स्वयं में जोड़ते रहते हैं, तो आप ग्रुप में 0 से 10 तक के प्रत्येक एलिमेंट को जनरेट कर सकते हैं।

यह कहना कि एलिप्टिक कर्व पॉइंट्स एक साइक्लिक ग्रुप बनाते हैं (एलिप्टिक कर्व एडिशन के अंतर्गत), इसका अर्थ है कि हम एक फाइनाइट फील्ड में प्रत्येक संख्या को एक एलिप्टिक कर्व पॉइंट के रूप में दर्शा सकते हैं और उन्हें एक साथ वैसे ही जोड़ सकते हैं जैसे हम एक फाइनाइट फील्ड में नियमित इंटिजर्स को जोड़ते हैं।

अर्थात्,

$5 + 7 \pmod p$, $5G + 7G$ के होमोमोर्फिक (homomorphic) है।

जहाँ G एलिप्टिक कर्व साइक्लिक ग्रुप का जनरेटर है।

यह केवल उन फाइनाइट फील्ड्स पर एलिप्टिक कर्व्स के लिए सत्य है जिनमें बिंदुओं की संख्या अभाज्य (prime) है, जो कि उसी प्रकार के कर्व्स हैं जिनका हम व्यवहार में उपयोग करते हैं। यह एक ऐसी चीज़ है जिस पर हम बाद में फिर से विचार करेंगे।

BN128 फॉर्मूला

BN128 कर्व, जिसका उपयोग ZK प्रूफ़्स को सत्यापित करने के लिए Ethereum प्रीकंपाइल्स (precompiles) द्वारा किया जाता है, इस प्रकार निर्दिष्ट किया गया है:

यहाँ $p$ फील्ड मॉड्युलस है।

field_modulus को कर्व ऑर्डर (curve order) के साथ भ्रमित नहीं किया जाना चाहिए, जो कि कर्व पर बिंदुओं की संख्या है।

bn128 कर्व के लिए, कर्व ऑर्डर इस प्रकार है:

Copy
from py_ecc.bn128 import curve_order
# 21888242871839275222246405745257275088548364400416034343698204186575808495617
print(curve_order)

फील्ड मॉड्युलस बहुत बड़ा है, जो इसके साथ प्रयोग करना कठिन बना देता है। अगले सेक्शन में, हम उसी फॉर्मूले का उपयोग करके, लेकिन एक छोटे मॉड्युलस के साथ, फाइनाइट फील्ड्स में एलिप्टिक कर्व पॉइंट्स के लिए एक समझ (intuition) विकसित करेंगे।

एलिप्टिक कर्व साइक्लिक ग्रुप $y² = x³ + 3 \pmod {11}$ जनरेट करना

उपरोक्त समीकरण को हल करने और यह निर्धारित करने के लिए कि कर्व पर कौन से $(x, y)$ बिंदु हैं, हमें $\sqrt{(x³ + 3)} \pmod {11}$ को कंप्यूट करना होगा।

मॉड्यूलर स्क्वायर रूट्स

हम मॉड्यूलर स्क्वायर रूट्स को कंप्यूट करने के लिए Tonelli Shanks Algorithm का उपयोग करते हैं। यदि आप उत्सुक हैं तो आप पढ़ सकते हैं कि एल्गोरिदम कैसे काम करता है, लेकिन अभी के लिए आप इसे एक ब्लैक बॉक्स के रूप में मान सकते हैं जो एक मॉड्युलस पर किसी फील्ड एलिमेंट के गणितीय स्क्वायर रूट को कंप्यूट करता है, या आपको बताता है कि स्क्वायर रूट मौजूद नहीं है।

उदाहरण के लिए, 5 मॉड्यूलो 11 का स्क्वायर रूट 4 $(4 \times 4 \mod 11 = 5)$ है, लेकिन 6 मॉड्यूलो 11 का कोई स्क्वायर रूट नहीं है। (पाठक को ब्रूट फोर्स के माध्यम से यह पता लगाने के लिए प्रोत्साहित किया जाता है कि यह सत्य है)।

स्क्वायर रूट्स के अक्सर दो समाधान होते हैं, एक धनात्मक और एक ऋणात्मक। हालाँकि हमारे पास फाइनाइट फील्ड में ऋणात्मक चिह्न वाली संख्याएँ नहीं होती हैं, फिर भी एक इनवर्स होने के अर्थ में हमारे पास “ऋणात्मक संख्याओं” की अवधारणा होती है।

ऊपर वर्णित एल्गोरिदम को लागू करने के लिए आप ऑनलाइन कोड पा सकते हैं, लेकिन इस ट्यूटोरियल में कोड के बड़े हिस्से को रखने से बचने के लिए, हम इसके बजाय एक Python लाइब्रेरी इंस्टॉल करेंगे।

Copy
python3 -m pip install libnum

libnum इंस्टॉल करने के बाद, हम इसके उपयोग को प्रदर्शित करने के लिए निम्न कोड चला सकते हैं।

Copy
from libnum import has_sqrtmod_prime_power, sqrtmod_prime_power

# the functions take arguments# has_sqrtmod_prime_power(n, field_mod, k), where n**k,
# but we aren't interested in powers in modular fields, so we set k = 1
# check if sqrt(8) mod 11 exists
print(has_sqrtmod_prime_power(8, 11, 1))
# False

# check if sqrt(5) mod 11 exists
print(has_sqrtmod_prime_power(5, 11, 1))
# True

# compute sqrt(5) mod 11
print(list(sqrtmod_prime_power(5, 11, 1)))
# [4, 7]

assert (4 ** 2) % 11 == 5
assert (7 ** 2) % 11 == 5

# we expect 4 and 7 to be additive inverses of each other, because in "regular" math, the two solutions to a square root are sqrt and -sqrt
assert (4 + 7) % 11 == 0

अब जब हम जानते हैं कि मॉड्यूलर स्क्वायर रूट्स की गणना कैसे करनी है, तो हम $x$ की वैल्यूज को इटरेट कर सकते हैं और फॉर्मूला $y² = x³ + b$ से $y$ की गणना कर सकते हैं। $y$ के लिए हल करना केवल दोनों पक्षों का मॉड्यूलर स्क्वायर रूट (यदि यह मौजूद है) लेने और परिणामी $(x, y)$ जोड़े को सहेजने का मामला है ताकि हम बाद में उन्हें प्लॉट कर सकें।

आइए एक एलिप्टिक कर्व का एक सरल प्लॉट बनाएँ

Copy
import libnum
import matplotlib.pyplot as plt

def generate_points(mod):
    xs = []
    ys = []
    def y_squared(x):
        return (x**3 + 3) % mod

    for x in range(0, mod):
        if libnum.has_sqrtmod_prime_power(y_squared(x), mod, 1):
            square_roots = libnum.sqrtmod_prime_power(y_squared(x), mod, 1)

            # we might have two solutions
            for sr in square_roots:
                ys.append(sr)
                xs.append(x)
    return xs, ys


xs, ys = generate_points(11)
fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod p)');
fig.set_size_inches(6, 6);
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
plt.grid()
plt.scatter(xs, ys)
plt.plot();

प्लॉट का परिणाम नीचे दिखाया गया है:

कुछ अवलोकन (Observations):

• हमारे द्वारा उपयोग किए जाने वाले मॉड्युलस के बराबर या उससे अधिक कोई x या y वैल्यू नहीं होगी
• वास्तविक-मूल्य (real-valued) वाले प्लॉट की तरह ही, मॉड्यूलर प्लॉट “सममित (symmetric) प्रतीत होता है”

एलिप्टिक कर्व पॉइंट एडिशन

इससे भी अधिक दिलचस्प बात यह है कि एलिप्टिक कर्व्स की गणना करने के लिए हमारा “कनेक्ट द डॉट्स एंड फ्लिप” ऑपरेशन अभी भी काम करता है!

लेकिन यह देखते हुए कि हम इसे एक फाइनाइट फील्ड पर कर रहे हैं, यह आश्चर्यजनक नहीं होना चाहिए। वास्तविक संख्याओं पर हमारे सूत्र जोड़ और गुणा के सामान्य फील्ड संचालन का उपयोग करते हैं। यद्यपि हम यह निर्धारित करने के लिए स्क्वायर रूट्स का उपयोग करते हैं कि कोई बिंदु कर्व पर है या नहीं, और स्क्वायर रूट्स एक वैध फील्ड ऑपरेटर नहीं हैं, फिर भी हम बिंदुओं के जोड़ और दोगुने (doubling) की गणना करने के लिए स्क्वायर रूट्स का उपयोग नहीं करते हैं।

पाठक ऊपर दिए गए प्लॉट्स से दो बिंदुओं को चुनकर इसे सत्यापित कर सकते हैं, फिर बिंदुओं को जोड़ने के लिए नीचे दिए गए कोड में प्लग इन करके देख सकते हैं कि वे हमेशा दूसरे बिंदु (या यदि बिंदु एक-दूसरे के इनवर्स हैं तो इन्फिनिटी पर बिंदु) पर आते हैं। ये सूत्र Wikipedia page on elliptic curve point multiplication से लिए गए हैं।

Copy
def double(x, y, a, p):
    lambd = (((3 * x**2 + a) % p ) *  pow(2 * y, -1, p)) % p
    newx = (lambd**2 - 2 * x) % p
    newy = (-lambd * newx + lambd * x - y) % p
    return (newx, newy)

def add_points(xq, yq, xp, yp, p, a=0):
    if xq == yq == None:
        return xp, yp
    if xp == yp == None:
        return xq, yq
    
    assert (xq**3 + 3) % p == (yq ** 2) % p, "q not on curve"
    assert (xp**3 + 3) % p == (yp ** 2) % p, "p not on curve"
    
    if xq == xp and yq == yp:
        return double(xq, yq, a, p)
    elif xq == xp:
        return None, None
    
    lambd = ((yq - yp) * pow((xq - xp), -1, p) ) % p
    xr = (lambd**2 - xp - xq) % p
    yr = (lambd*(xp - xr) - yp) % p
    return xr, yr

एक फाइनाइट फील्ड में “कनेक्ट एंड फ्लिप” कैसा दिखता है, इसके कुछ विज़ुअलाइज़ेशन यहाँ दिए गए हैं:

एक साइक्लिक ग्रुप में प्रत्येक एलिप्टिक कर्व बिंदु का एक “नंबर” होता है

परिभाषा के अनुसार, एक साइक्लिक ग्रुप को जनरेटर को स्वयं में बार-बार जोड़कर जनरेट किया जा सकता है।

आइए $y² = x³ + 3 \pmod {11}$ के एक वास्तविक उदाहरण का उपयोग करें जिसमें जनरेटर बिंदु $(4, 10)$ है।

उपरोक्त Python फ़ंक्शंस का उपयोग करते हुए, हम बिंदु $(4, 10)$ से शुरू कर सकते हैं और ग्रुप में प्रत्येक बिंदु को जनरेट कर सकते हैं:

Copy
# for our purposes, (4, 10) is the generator point G
next_x, next_y = 4, 10
print(0, 4, 10)
points = [(next_x, next_y)]
for i in range(1, 13):
    # repeatedly add G to the next point to generate all the elements
    next_x, next_y = add_points(next_x, next_y, 4, 10, 11)
    print(i, next_x, next_y)
    points.append((next_x, next_y))

आउटपुट होगा

Copy
0 4 10
1 7 7
2 1 9
3 0 6
4 8 8
5 2 0
6 8 3
7 0 5
8 1 2
9 7 4
10 4 1
11 None None
12 4 10 # note that this is the same point as the first one

ध्यान दें कि $(\text{order} + 1)G = G$। मॉड्यूलर एडिशन की तरह ही, जब हम “ओवरफ्लो” करते हैं, तो चक्र फिर से शुरू हो जाता है।

यहाँ, None का अर्थ है इन्फिनिटी (infinity) पर बिंदु, जो वास्तव में ग्रुप का हिस्सा है। जनरेटर में इन्फिनिटी पर बिंदु जोड़ने से जनरेटर वापस मिल जाता है, क्योंकि आइडेंटिटी एलिमेंट को इसी तरह व्यवहार करना चाहिए।

हम प्रत्येक बिंदु को एक “नंबर” निर्दिष्ट कर सकते हैं, जो इस बात पर आधारित है कि उस बिंदु तक पहुँचने के लिए हमने जनरेटर को स्वयं में कितनी बार जोड़ा है।

हम कर्व को प्लॉट करने और उसके आगे एक नंबर निर्दिष्ट करने के लिए निम्न कोड का उपयोग कर सकते हैं

Copy
xs11, ys11 = generate_points(11)

fig, (ax1) = plt.subplots(1, 1);
fig.suptitle('y^2 = x^3 + 3 (mod 11)');
fig.set_size_inches(13, 6);

ax1.set_title("modulo 11")
ax1.scatter(xs11, ys11, marker='o');
ax1.set_xticks(range(0,11));
ax1.set_yticks(range(0,11));
ax1.grid()

for i in range(0, 11):
    plt.annotate(str(i+1), (points[i][0] + 0.1, points[i][1]), color="red");

लाल टेक्स्ट को आइडेंटिटी एलिमेंट से शुरू करने के रूप में सोचा जा सकता है, और यह भी कि हमने इसमें कितनी बार जनरेटर जोड़ा है।

पॉइंट इनवर्स अभी भी वर्टिकली सिमेट्रिक (vertically symmetric) हैं

यहाँ एक दिलचस्प अवलोकन है: ध्यान दें कि जो बिंदु समान x-वैल्यू साझा करते हैं उनका योग 12 होता है, जो आइडेंटिटी एलिमेंट $(12 \mod 12 = 0)$ से मेल खाता है। यदि हम बिंदु $(4, 1)$, जो कि हमारे प्लॉट में 11वाँ बिंदु है, को $(4, 10)$ में जोड़ते हैं, तो हमें इन्फिनिटी पर बिंदु मिलेगा, जो ग्रुप में 12वाँ एलिमेंट होगा।

ऑर्डर मॉड्युलस नहीं है

इस उदाहरण में, ग्रुप का ऑर्डर 12 है (हमारे ग्रुप में कुल एलिप्टिक कर्व बिंदुओं की संख्या), बावजूद इसके कि एलिप्टिक कर्व का सूत्र मॉड्यूलो 11 है। इस पर कई बार जोर दिया जाएगा, लेकिन आपको यह नहीं मान लेना चाहिए कि एलिप्टिक कर्व में मॉड्युलस ही ग्रुप ऑर्डर है। हालाँकि, आप Hasse’s Theorem का उपयोग करके स्वयं फील्ड मॉड्युलस से कर्व की ऑर्डर रेंज का अनुमान लगा सकते हैं।

यदि बिंदुओं की संख्या अभाज्य (prime) है, तो बिंदुओं का जोड़ एक फाइनाइट फील्ड की तरह व्यवहार करता है

उपरोक्त प्लॉट में 12 बिंदु (0 सहित) हैं। एडिशन मॉड्यूलो 12 एक फाइनाइट फील्ड नहीं है क्योंकि 12 एक अभाज्य संख्या नहीं है।

हालाँकि, यदि हम कर्व के लिए अपने पैरामीटर्स को सावधानी से चुनते हैं, तो हम एक एलिप्टिक कर्व बना सकते हैं जहाँ बिंदु एक फाइनाइट फील्ड में एलिमेंट्स के अनुरूप होते हैं। अर्थात्, कर्व का ऑर्डर फाइनाइट फील्ड के ऑर्डर के बराबर होता है।

उदाहरण के लिए, $y^2 = x^3 + 7 \pmod {43}$ कुल 31 बिंदुओं के साथ एक कर्व बनाता है जैसा कि नीचे दिए गए प्लॉट में देखा जा सकता है:

जब कर्व का ऑर्डर फाइनाइट फील्ड के ऑर्डर से मेल खाता है, तो फाइनाइट फील्ड में आपके द्वारा किए जाने वाले प्रत्येक ऑपरेशन का एलिप्टिक कर्व में एक होमोमोर्फिक समकक्ष (homomorphic equivalent) होता है।

एक फाइनाइट फील्ड से एलिप्टिक कर्व में जाने के लिए, हम जनरेटर होने के लिए एक बिंदु (स्वेच्छा से) चुनते हैं, फिर हम फाइनाइट फील्ड के एलिमेंट को जनरेटर से गुणा करते हैं।

गुणा वास्तव में बार-बार जोड़ना (repeated addition) है

एलिप्टिक कर्व पॉइंट मल्टीप्लिकेशन जैसी कोई चीज़ नहीं होती है। जब हम “स्केलर मल्टीप्लिकेशन” कहते हैं तो हमारा मतलब वास्तव में बार-बार जोड़ना होता है। आप दो एलिप्टिक कर्व बिंदुओं को नहीं ले सकते और उन्हें एक साथ गुणा नहीं कर सकते (खैर, आप bilinear pairings के साथ ऐसा कुछ हद तक कर सकते हैं, लेकिन वह कुछ ऐसा है जिस पर हम बाद में चर्चा करेंगे)।

जब हम multiply(G1, x) करने के लिए Python लाइब्रेरी का उपयोग करते हैं, तो यह वास्तव में x बार G1 + G1 + … + G1 के समान है। अंदरूनी तौर पर, हम वास्तव में इतनी बार स्वयं-जोड़ नहीं करते हैं, हम लॉगरिदमिक समय (logarithmic time) में ऑपरेशन को पूरा करने के लिए पॉइंट डबलिंग (point doubling) के साथ कुछ चतुर शॉर्टकट्स का उपयोग करते हैं।

उदाहरण के लिए, यदि हम 135G की गणना करना चाहते हैं, तो हम पॉइंट डबलिंग का उपयोग करके निम्नलिखित वैल्यूज की कुशलतापूर्वक गणना करेंगे, उन्हें कैश करेंगे,

Copy
G, 2G, 4G, 8G, 16G, 32G, 64G, 128G

…फिर 128G + 4G + 2G + G = 135G का योग करेंगे।

जब हम कहते हैं कि 5G + 6G = 11G, तो हम अनिवार्य रूप से G को स्वयं में 11 बार जोड़ रहे हैं। ऊपर बताए गए शॉर्टकट का उपयोग करके, हम गणनाओं की एक लॉगरिदमिक संख्या के साथ 11G की गणना कर सकते हैं, लेकिन अंत में, यह केवल बार-बार जोड़ना है।

Python bn128 लाइब्रेरी

EVM इम्प्लीमेंटेशन pyEVM एलिप्टिक कर्व प्रीकंपाइल्स के लिए जिस लाइब्रेरी का उपयोग करता है वह py_ecc है, और हम इस लाइब्रेरी पर बहुत अधिक निर्भर रहेंगे। नीचे दिया गया कोड दिखाता है कि जनरेटर बिंदु कैसा दिखता है, और कुछ जोड़ और स्केलर मल्टीप्लिकेशन भी दिखाता है।

यहाँ G1 बिंदु ऐसा दिखता है:

Copy
from py_ecc.bn128 import G1, multiply, add, eq, neg

print(G1)
# (1, 2)

print(add(G1, G1))
# (1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

print(multiply(G1, 2))
#(1368015179489954701390400359078579693043519447331113978918064868415326638035, 9918110051302171585080402603319702774565515993150576347155970296011118125764)

# 10G + 11G = 21G
assert eq(add(multiply(G1, 10), multiply(G1, 11)), multiply(G1, 21))

यद्यपि संख्याएँ बड़ी हैं और पढ़ने में कठिन हैं, हम देख सकते हैं कि किसी बिंदु को स्वयं में जोड़ने पर वही वैल्यू प्राप्त होती है जो किसी बिंदु को 2 से “गुणा” करने पर मिलती है। ऊपर दिए गए दो बिंदु स्पष्ट रूप से एक ही बिंदु हैं। ट्यूपल (tuple) अभी भी एक $(x, y)$ जोड़ा है, बस एक बहुत बड़े डोमेन पर है।

ऊपर मुद्रित संख्या एक कारण से बहुत बड़ी है। हम नहीं चाहते कि हमलावर (attackers) एक एलिप्टिक कर्व पॉइंट लेने और उस फील्ड एलिमेंट की गणना करने में सक्षम हों जिसने इसे जनरेट किया है। यदि हमारे साइक्लिक ग्रुप का ऑर्डर बहुत छोटा है, तो हमलावर इसे ब्रूट फोर्स से निकाल सकते हैं।

यहाँ पहले 1000 बिंदुओं का एक प्लॉट दिया गया है:

और उपरोक्त प्लॉट को जनरेट करने का कोड यह है:

Copy
import matplotlib.pyplot as plt
from py_ecc.bn128 import G1, multiply, neg
import math
import numpy as np
xs = []
ys = []
for i in range(1,1000):
    xs.append(i)
    ys.append(int(multiply(G1, i)[1]))
    xs.append(i)
    ys.append(int(neg(multiply(G1, i))[1]))
plt.scatter(xs, ys, marker='.')

यह डरावना लग सकता है, लेकिन पिछले सेक्शन में हमने जो किया उससे एकमात्र अंतर बहुत बड़े मॉड्युलस का उपयोग करना और जनरेटर के लिए एक अलग बिंदु का उपयोग करना है।

लाइब्रेरी में जोड़ (Addition)

py_ecc लाइब्रेरी हमारे लिए पॉइंट एडिशन को सुविधाजनक बनाती है, और सिंटैक्स स्वयं-व्याख्यात्मक होना चाहिए:

Copy
from py_ecc.bn128 import G1, multiply, add, eq

# 5 = 2 + 3
assert eq(multiply(G1, 5), add(multiply(G1, 2), multiply(G1, 3)));

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

इस बिंदु पर, उम्मीद है कि पाठक को सैद्धांतिक और व्यावहारिक दोनों रूप से एलिप्टिक कर्व बिंदुओं को एक साथ जोड़ने की अच्छी समझ हो गई होगी, क्योंकि आधुनिक ज़ीरो नॉलेज एल्गोरिदम इस पर बहुत अधिक निर्भर करते हैं।

मॉड्यूलर एडिशन और एलिप्टिक कर्व एडिशन के बीच होमोमोर्फिज़्म के बारे में इम्प्लीमेंटेशन डिटेल

हमें यहाँ शब्दावलियों के बीच सावधानीपूर्वक अंतर करने की आवश्यकता है:

फील्ड मॉड्युलस (field modulus) वह मॉड्यूलो है जिस पर हम कर्व बनाते हैं। कर्व ऑर्डर (curve order) कर्व पर मौजूद बिंदुओं की संख्या है।

यदि आप एक बिंदु $R$ से शुरू करते हैं और कर्व ऑर्डर $o$ जोड़ते हैं, तो आपको $R$ वापस मिलेगा। यदि आप फील्ड मॉड्युलस जोड़ते हैं, तो आपको एक अलग बिंदु मिलेगा।

Copy
from py_ecc.bn128 import curve_order, field_modulus, G1, multiply, eq

x = 5 # chosen randomly
# This passes
assert eq(multiply(G1, x), multiply(G1, x + curve_order))

# This fails
assert eq(multiply(G1, x), multiply(G1, x + field_modulus))

इसका निहितार्थ यह है कि (x + y) mod curve_order == xG + yG।

Copy
x = 2 ** 300 + 21
y = 3 ** 50 + 11

# (x + y) == xG + yG
assert eq(multiply(G1, (x + y)), add(multiply(G1, x), multiply(G1, y)))

भले ही x + y ऑपरेशन स्पष्ट रूप से कर्व ऑर्डर पर “ओवरफ्लो” हो जाएगा, इससे कोई फर्क नहीं पड़ता। एक फाइनाइट फील्ड की तरह ही, हम इसी व्यवहार की अपेक्षा करते हैं। एलिप्टिक कर्व मल्टीप्लिकेशन अंतर्निहित रूप से गुणा करने से पहले मॉड्युलस लेने के समान ही ऑपरेशन निष्पादित कर रहा है।

वास्तव में, अगर हम केवल धनात्मक संख्याओं की परवाह करते हैं तो हमें मॉड्युलस करने की भी आवश्यकता नहीं है, निम्नलिखित पहचान भी सत्य है:

Copy
x = 2 ** 300 + 21
y = 3 ** 50 + 11

assert eq(multiply(G1, (x + y) % curve_order), add(multiply(G1, x), multiply(G1, y)))

हालाँकि, यदि हम गलत संख्या (कर्व ऑर्डर के अलावा किसी अन्य संख्या) के साथ फाइनाइट मैथ मॉड्यूलो करते हैं, तो यदि हम “ओवरफ्लो” करते हैं तो समानता टूट जाएगी

Copy
x = 2 ** 300 + 21
y = 3 ** 50 + 11 # these values are large enough to overflow:

assert eq(multiply(G1, (x + y) % (curve_order - 1)), add(multiply(G1, x), multiply(G1, y))), "this breaks"

रैशनल नंबर्स (rational numbers) को एनकोड करना

जब हम मॉड्युलस लेते हैं, तो हम भाग (division) की अवधारणा को एनकोड करने में सक्षम होते हैं।

उदाहरण के लिए, हम नियमित इंटिजर्स का उपयोग करके निम्नलिखित कार्य नहीं कर सकते हैं।

Copy
# this throws an exception
eq(add(multiply(G1, 5 / 2), multiply(G1, 1 / 2), multiply(G1, 3)

हालाँकि, एक फाइनाइट फील्ड में, 1/2 को 2 के मल्टीप्लिकेटिव इनवर्स के रूप में अर्थपूर्ण ढंग से कंप्यूट किया जा सकता है। इसलिए, 5 / 2 को $5 \cdot \mathsf{inv}(2)$ के रूप में एनकोड किया जा सकता है।

यहाँ बताया गया है कि हम इसे Python में कैसे कर सकते हैं:

Copy
five_over_two = (5 * pow(2, -1, curve_order)) % curve_order
one_half = pow(2, -1, curve_order)

# Essentially 5/2 = 2.5# 2.5 + 0.5 = 3
# but we are doing this in a finite field
assert eq(add(multiply(G1, five_over_two), multiply(G1, one_half)), multiply(G1, 3))

एसोसिएटिविटी (Associativity)

हम जानते हैं कि ग्रुप एसोसिएटिव होते हैं, इसलिए हम उम्मीद करते हैं कि सामान्य तौर पर निम्नलिखित पहचान सत्य होगी:

Copy
x = 5
y = 10
z = 15

lhs = add(add(multiply(G1, x), multiply(G1, y)), multiply(G1, z))

rhs = add(multiply(G1, x), add(multiply(G1, y), multiply(G1, z)))

assert eq(lhs, rhs)

पाठक को अपने लिए x, y, और z के विभिन्न वैल्यूज को आज़माने के लिए प्रोत्साहित किया जाता है।

प्रत्येक एलिमेंट का एक इनवर्स होता है

py_ecc लाइब्रेरी हमें neg फ़ंक्शन प्रदान करती है जो किसी दिए गए एलिमेंट को (एक फाइनाइट फील्ड में) x-अक्ष पर फ़्लिप करके उसका इनवर्स प्रदान करेगा। लाइब्रेरी “पॉइंट एट इन्फिनिटी” को Python None के रूप में एनकोड करती है।

Copy
from py_ecc.bn128 import G1, multiply, neg, is_inf, Z1

# pick a field element
x = 12345678
# generate the point
p = multiply(G1, x)

# invert
p_inv = neg(p)

# every element added to its inverse produces the identity element assert is_inf(add(p, p_inv))

# Z1 is just None, which is the point at infinity
assert Z1 is None

# special case: the inverse of the identity is itself
assert eq(neg(Z1), Z1)

वास्तविक संख्याओं पर एलिप्टिक कर्व्स के मामले की तरह, एक एलिप्टिक कर्व पॉइंट के इनवर्स का x वैल्यू समान होता है, लेकिन y वैल्यू इनवर्स होता है।

Copy
from py_ecc.bn128 import G1, neg, multiply

field_modulus = 21888242871839275222246405745257275088696311157297823662689037894645226208583
for i in range(1, 4):
    point = multiply(G1, i)
    print(point)
    print(neg(point))
    print('----')
    
    # x values are the same
    assert int(point[0]) == int(neg(point)[0])
    
    # y values are inverses of each other, we are adding y values
    # not ec points
    assert int(point[1]) + int(neg(point)[1]) == field_modulus

प्रत्येक एलिमेंट एक जनरेटर द्वारा जनरेट किया जा सकता है

जब हम $2^{200}$ से अधिक बिंदुओं से निपट रहे होते हैं, तो ब्रूट फोर्स द्वारा इसे सत्यापित करना संभव नहीं है। हालाँकि, इस तथ्य पर विचार करें कि eq(multiply(G1, x), multiply(G1, x + order)) हमेशा सत्य होता है। इसका अर्थ है कि हम ऑर्डर के बिंदुओं तक जनरेट करने में सक्षम हैं, फिर यह वापस वहीं आ जाता है जहाँ से शुरू हुआ था।

optimized_bn128 के बारे में क्या?

लाइब्रेरी की जाँच करने पर, आपको optimized_bn128 नामक एक इम्प्लीमेंटेशन दिखाई देगा। यदि आप इसके एक्ज़ीक्यूशन समय को बेंचमार्क करते हैं, तो आप देखेंगे कि यह संस्करण बहुत तेज़ी से चलता है, और यह pyEvm द्वारा उपयोग किया जाने वाला इम्प्लीमेंटेशन है। हालाँकि, शैक्षिक उद्देश्यों के लिए, गैर-अनुकूलित (non-optimized) संस्करण का उपयोग करना बेहतर है क्योंकि यह बिंदुओं को अधिक सहज तरीके से (सामान्य x, y ट्यूपल) संरचना करता है। अनुकूलित (optimized) संस्करण EC बिंदुओं को 3-ट्यूपल के रूप में संरचना करता है, जिनकी व्याख्या करना कठिन है।

Copy
from py_ecc.optimized_bn128 import G1, multiply, neg, is_inf, Z1
print(G1)
# (1, 2, 1)

एलिप्टिक कर्व्स के साथ बेसिक ज़ीरो नॉलेज प्रूफ़्स

इस काफी तुच्छ उदाहरण पर विचार करें:

दावा: “मैं दो वैल्यूज $x$ और $y$ जानता हूँ कि $x + y = 15$”

प्रमाण (Proof): मैं x को G1 से और y को G1 से गुणा करता हूँ और उन्हें आपको A और B के रूप में देता हूँ।

सत्यापनकर्ता (Verifier): आप 15 को G1 से गुणा करते हैं और जांचते हैं कि A + B == 15G1 है।

यहाँ यह Python में है:

Copy
from py_ecc.bn128 import G1, multiply, add

# Prover
secret_x = 5
secret_y = 10

x = multiply(G1, 5)
y = multiply(G1, 10)

proof = (x, y, 15)

# verifier
if multiply(G1, proof[2]) == add(proof[0], proof[1]):
    print("statement is true")
else:
    print("statement is false")

यद्यपि सत्यापनकर्ता को यह नहीं पता है कि x और y क्या हैं, वे यह सत्यापित कर सकते हैं कि x और y एलिप्टिक कर्व स्पेस में 15 तक जुड़ते हैं, इसलिए secret_x और secret_y फाइनाइट फील्ड एलिमेंट्स के रूप में 15 तक जुड़ते हैं।

पाठक के लिए यह एक अभ्यास है कि वे कुछ अधिक परिष्कृत करें, जैसे कि रैखिक समीकरणों की एक प्रणाली के समाधान के ज्ञान को सिद्ध करना।

एक (बहुत महत्वपूर्ण) संकेत के रूप में, किसी संख्या को स्थिरांक से गुणा करना बार-बार जोड़ने के समान है। बार-बार जोड़ना एलिप्टिक कर्व स्केलर मल्टीप्लिकेशन के समान है। इस प्रकार, यदि x एक एलिप्टिक कर्व पॉइंट है, तो हम इसे एक स्केलर 9 से multiply(x, 9) के रूप में गुणा कर सकते हैं। यह हमारे इस कथन के अनुरूप है कि हम एलिप्टिक कर्व बिंदुओं को गुणा नहीं कर सकते - हम वास्तव में एक एलिप्टिक कर्व बिंदु को एक स्केलर से गुणा कर रहे हैं, किसी अन्य बिंदु से नहीं।

क्या आप साबित कर सकते हैं कि आप $x$ को जानते हैं जिससे $23x = 161$ हो? क्या आप इसे अधिक चरों में सामान्यीकृत कर सकते हैं?

एक और संकेत के रूप में: आपको (प्रूवर) और सत्यापनकर्ता को पहले से फॉर्मूले पर सहमत होने की आवश्यकता है, क्योंकि सत्यापनकर्ता उस मूल फॉर्मूले की उसी “संरचना” को चलाएगा जिसके समाधान को जानने का आप दावा करते हैं।

सुरक्षा मान्यताएँ (Security assumptions)

उपरोक्त योजना को सुरक्षित होने के लिए, हम यह मान रहे हैं कि यदि हम multiply(G1, x) जैसा कोई बिंदु प्रकाशित करते हैं, तो एक हमलावर बनाए गए $(x, y)$ वैल्यू से यह अनुमान नहीं लगा सकता है कि $x$ के लिए मूल वैल्यू क्या थी। यह डिस्क्रीट लॉगरिथम धारणा है। यही कारण है कि जिस अभाज्य संख्या पर हम फॉर्मूले की गणना करते हैं उसका बड़ा होना आवश्यक है, ताकि हमलावर ब्रूट फोर्स से अनुमान न लगा सके।

baby step giant step एल्गोरिदम जैसे अधिक परिष्कृत एल्गोरिदम हैं जो ब्रूट फोर्स से बेहतर प्रदर्शन कर सकते हैं।

नोट: BN128 इस धारणा से आता है कि इसमें 128 बिट्स की सुरक्षा है। एलिप्टिक कर्व की गणना 254 बिट्स के एक फाइनाइट फील्ड में की जाती है, लेकिन माना जाता है कि इसमें 128 बिट्स की सुरक्षा है क्योंकि डिस्क्रीट लॉगरिथम की गणना करने के लिए नेव ब्रूट फोर्स की तुलना में बेहतर एल्गोरिदम मौजूद हैं।

ट्रू ज़ीरो नॉलेज (True zero knowledge)

हमें यह भी बताना चाहिए कि हमारा A + B = 15G उदाहरण वास्तव में ज़ीरो नॉलेज नहीं है। यदि कोई हमलावर a और b का अनुमान लगाता है, तो वे जनरेट किए गए एलिप्टिक कर्व बिंदुओं की तुलना हमारे बिंदुओं से करके अपने अनुमान की पुष्टि कर सकते हैं।

इस समस्या का समाधान बाद के अध्याय में किया जाएगा।

फाइनाइट फील्ड्स पर एलिप्टिक कर्व्स को एक मैजिक ब्लैक बॉक्स मानना

जिस तरह आपको इसका उपयोग करने के लिए यह जानने की आवश्यकता नहीं है कि हुड के नीचे हैश फ़ंक्शन कैसे काम करता है, उसी तरह आपको एलिप्टिक कर्व बिंदुओं को जोड़ने और उन्हें स्केलर से गुणा करने के इम्प्लीमेंटेशन डिटेल्स को जानने की आवश्यकता नहीं है।

हालाँकि, आपको उन नियमों को जानने की आवश्यकता है जिनका वे पालन करते हैं। इस बिंदु पर एक टूटे हुए रिकॉर्ड की तरह लगने के जोखिम पर, वे साइक्लिक ग्रुप्स के नियमों का पालन करते हैं:

• एलिप्टिक कर्व बिंदुओं को जोड़ना क्लोज्ड है: यह एक और एलिप्टिक कर्व बिंदु उत्पन्न करता है
• एलिप्टिक कर्व बिंदुओं को जोड़ना एसोसिएटिव है
• एक आइडेंटिटी एलिमेंट मौजूद होता है
• प्रत्येक एलिमेंट का एक इनवर्स होता है जिसे जोड़ने पर आइडेंटिटी एलिमेंट उत्पन्न होता है

जब तक आप इसे समझते हैं, आप कुछ भी अमान्य किए बिना अपने दिल की सामग्री को जोड़, गुणा और उल्टा (invert) कर सकते हैं। इन ऑपरेशन्स में से प्रत्येक का py_ecc लाइब्रेरी में एक संबंधित फ़ंक्शन है।

इस पाठ के लिए याद रखने वाली सबसे महत्वपूर्ण बात यह है:

फाइनाइट फील्ड्स पर एलिप्टिक कर्व्स एक फाइनाइट फील्ड में जोड़ को होमोमोर्फिक रूप से एन्क्रिप्ट करते हैं।

मून मैथ (Moon math): हम कर्व के ऑर्डर को कैसे जानते हैं?

पाठक सोच रहे होंगे कि हम फॉर्मूले के सभी वैध समाधानों को गिने बिना bn128 कर्व का ऑर्डर कैसे निर्धारित करने में सक्षम हैं। किसी भी कंप्यूटर की गणना से अधिक वैध बिंदु होते हैं, तो हम कर्व के ऑर्डर पर कैसे पहुँचे?

यह उस तरह के गणित का एक उदाहरण है जिससे हम बचने की कोशिश कर रहे हैं, क्योंकि यह काफी एडवांस है। यह पता चला है कि बिंदुओं की संख्या की गणना Schoof’s Algorithm के साथ पॉलीनोमिअल समय में की जा सकती है। आपसे यह समझने की अपेक्षा नहीं की जाती है कि यह एल्गोरिदम कैसे काम करता है, बल्कि यह जानना पर्याप्त है कि एल्गोरिदम मौजूद है। हम कर्व ऑर्डर पर कैसे पहुँचे, यह इम्प्लीमेंटेशन के दृष्टिकोण से महत्वपूर्ण नहीं है, हम केवल इस बात की परवाह करते हैं कि डिज़ाइनरों ने इसकी सही गणना की है।

RareSkills पर यहाँ मौजूद सामग्री को इन गणितीय बारूदी सुरंगों से दूर रहने के लिए सावधानीपूर्वक डिज़ाइन किया गया है।

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

यही कारण है कि हमारा zero knowledge course एब्सट्रैक्ट अल्जेब्रा की मूल बातों पर बहुत अधिक जोर देता है। एलिप्टिक कर्व्स के इम्प्लीमेंटेशन डिटेल्स को समझना बेहद कठिन है। लेकिन साइक्लिक ग्रुप्स के व्यवहार को समझना, यद्यपि पहले असामान्य लगता है, अधिकांश प्रोग्रामर्स के लिए पूरी तरह से समझने योग्य है। एक बार जब हम इसे समझ लेते हैं, तो एलिप्टिक कर्व बिंदुओं को जोड़ने का सामान्य व्यवहार सहज हो जाता है, भले ही ऑपरेशन की कल्पना करना कठिन हो।

मूल रूप से 19 सितंबर, 2023 को प्रकाशित