अपडेट किया गया: 4 अगस्त, 2023

Suthan Somadeva और Michael Burke द्वारा

ECDSA बनाम RSA का परिचय

एक ऐसा contract बनाना जो विशिष्ट addresses को अनुमति देता है, कई नामों से जाना जाता है: airdrops, presale, whitelist, allowlist, इत्यादि। लेकिन इस विचार का मूल यह है कि addresses का एक समूह होता है जिन्हें एक उच्च मांग वाले token को वांछित कीमत (कभी-कभी मुफ्त) पर खरीदने की विशेष अनुमति होती है।

इसके लिए तीन स्थापित समाधान हैं: mappings, Merkle trees, और ECDSA signatures।

इन दृष्टिकोणों के सापेक्ष गुणों पर पहले ही कहीं और चर्चा की जा चुकी है, इसलिए हम परिणामों को संक्षेप में प्रस्तुत करेंगे:

• ECDSA Signature Verification (Gas: 29,293)
• Merkle proofs का उपयोग (Gas: 30, 517, 128 addresses)

एक mapping presale इस तरह काम करता है कि विक्रेता ग्राहकों के addresses को एक mapping में दर्ज करता है जो address से boolean तक जाता है ताकि यह नोट किया जा सके कि address विशेषाधिकार प्राप्त है या नहीं। खरीदार द्वारा transaction पूरा करने के बाद mapping को false पर सेट कर दिया जाता है। यह सुनिश्चित करता है कि केवल वे addresses जिन्हें true के रूप में चिह्नित किया गया है, खरीदारी कर सकते हैं। यह खरीदार के लिए बहुत gas efficient है, लेकिन विक्रेता हजारों addresses को allowlisting करने में लाखों gas खर्च कर सकता है (allowlist में एक address जोड़ने के लिए कम से कम 22,100 gas का खर्च आएगा)।

इस कारण से, Merkle Trees और ECDSA signatures (OpenZeppelin द्वारा प्रकाशित ethereum precompile ecerecover का उपयोग करते हुए, या इससे भी बेहतर, इसके चारों ओर अधिक सुरक्षित wrapper का उपयोग करते हुए) को अक्सर mappings की तुलना में प्राथमिकता दी जाती है। ECDSA signature verification को निष्पादित करने की gas cost (खरीदार के लिए) 29,293 gas है। इसमें transaction शुरू करने के लिए 21,000 शामिल हैं, इसलिए ECDSA की लागत 8,293 है। ध्यान दें कि इसमें storage से signing address को पढ़ना शामिल है, लेकिन यह लागत आवश्यक है अन्यथा हम signatures को अमान्य (invalidate) नहीं कर पाएंगे।

Merkle Trees की लागत tree के आकार के आधार पर भिन्न होती है (बड़े trees के लिए बड़े Merkle proofs की आवश्यकता होती है), लेकिन यदि Merkle tree में 1,000 से अधिक addresses हैं, तो address को सत्यापित करने में कम से कम 32,000 gas (या अधिक) का खर्च आएगा। यह लागत स्पष्ट रूप से ECDSA की तुलना में कमतर है।

तब लक्ष्य ECDSA को हराना है जिसकी लागत 8,293 gas है। समाधानों की निष्पक्ष तुलना (apples-to-apples) बनाए रखने के लिए, वैकल्पिक समाधान को यह करना चाहिए:

1. allowlisted addresses को अमान्य (nullify) करने में सक्षम होना चाहिए। Merkle trees अपने root को बदल सकते हैं, ECDSA अपने signing address को बदल सकता है, और mappings value को false पर सेट कर सकते हैं।
2. विक्रेता पर उस तरह का भारी लागत का बोझ नहीं डालना चाहिए जैसा mappings डालते हैं।
3. खरीदार के लिए 8,200 gas से कम लागत (एक storage load सहित) होनी चाहिए।
4. सुरक्षा के साथ कोई समझौता नहीं होना चाहिए।

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

प्रस्तावित कार्यप्रणाली को समझने के लिए, पाठक को निम्नलिखित विषयों से परिचित होना चाहिए:

• Precompiled smart contracts (अनुशंसित पठन, stackexchange)
• Metamorphic contracts (परिचय, अनुशंसित पठन)
• Access lists (अनुशंसित पठन)
• Digital signatures का उपयोग कैसे करें और blockchain अनुप्रयोगों में उनके उचित उपयोग के मामले
• Gas cost की गणना कैसे की जाती है, विशेष रूप से calldata, opcodes, storage, और memory के उपयोग के संबंध में।

RSA Algorithm

यदि हम ECDSA को काफी हद तक पछाड़ना चाहते हैं, तो हमें एक अलग cryptographic algorithm खोजने की आवश्यकता है जो set membership के प्रमाण की अनुमति देता हो। ECDSA वास्तव में मूल digital signature algorithm, RSA का एक नया और बेहतर संस्करण है। ECDSA इस बात पर निर्भर करता है कि elliptic curves पर discrete logarithms कठिन होते हैं (इसलिए इसका नाम – elliptic curve digital signature algorithm है)। RSA (इसके लेखकों, Rivest, Shamir, Adleman के नाम पर) इस बात पर निर्भर करता है कि बड़े पूर्णांकों (integers) का गुणनखंड (factor) करना कठिन होता है। उम्र के संदर्भ में, RSA को 1970 के दशक में प्रकाशित किया गया था, लेकिन ECDSA 2000 के दशक की शुरुआत में एक औपचारिक विशिष्टता बन गया।

Admiral Piett RSA cryptography को स्वीकृति देते हैं

हम यहां RSA को विस्तार से नहीं समझाएंगे, लेकिन कुछ पूर्व-आवश्यकताओं को जानना जरूरी है।

Signer दो बड़े prime numbers p और q चुनता है, और n बनाने के लिए उन्हें एक साथ गुणा करता है। यह n public key का पहला भाग है। दूसरा, signer एक छोटा prime e चुनता है (हमारे उपयोग के मामले के लिए इसे 3 पर hardcode किया जा सकता है), और जोड़े (n, e) को public key के रूप में प्रकाशित करता है। पर्दे के पीछे, signer गणना करता है:

Copy
t = (p - 1) * (q - 1)
d = t^(-1) % n

संख्या d private key है। यदि कोई विरोधी n को p और q में विघटित कर सके, तो d की गणना करना बहुत आसान होगा। लेकिन यह ज्ञात है कि पूर्णांकों का गुणनखंड करना कठिन है। किसी message पर sign करने के लिए, signer h प्राप्त करने के लिए message m को hash करता है और h को d की घात तक बढ़ाता है। अर्थात्,

Copy
s = h(m) ^ d % n

इसके बाद signer (m, s) को message और signature के रूप में प्रकाशित करता है।

Verifier फिर m को hash करता है और इसे e mod n की घात तक बढ़ाता है। याद रखें, e और n public key हैं। यदि और केवल यदि

Copy
s == s ^ e % n

तो signature, public key (n, e) के लिए मान्य है। ध्यान दें कि यदि n बहुत बड़ा है, तो यादृच्छिक संयोग से s == s ^ e % n होने की संभावना न के बराबर है। यदि समानता सही साबित होती है, तो हम जानते हैं कि signature, public key के लिए मान्य है।

Ethereum में ऐसा करने के लिए, हम बस एक address को इस प्रकार sign करेंगे

Copy
s = buyerAddress ^ d % n

और smart contract सत्यापित करेगा

Copy
msg.sender == s ^ e % n

केवल 256 bits का उपयोग करना असुरक्षित है

हम कहते हैं “पूर्णांकों का गुणनखंड करना कठिन है” लेकिन स्पष्ट रूप से इसका अर्थ है कि संख्या पर्याप्त रूप से बड़ी होनी चाहिए। उदाहरण के लिए, 33 दो prime numbers से बना है और इसे विघटित करना बहुत आसान है। शुक्र है, हमारे पास इस बात के वास्तविक दुनिया के मानक हैं कि अत्याधुनिक तकनीक RSA Factoring Challenge में क्या हासिल कर सकती है।

स्पष्ट करने के लिए, “bits” की संख्या public key के आकार को संदर्भित करती है। इसलिए, जब हम “RSA 2048” कहते हैं, तो इसका मतलब है कि संख्या n, जो कि modulus है, में 2048 bits हैं। Key sizes की तुलना करते समय, यह याद रखना महत्वपूर्ण है कि प्रत्येक अतिरिक्त bit संख्या के आकार को दोगुना कर देता है। इसलिए 700 bits, 350 bits की तुलना में केवल दोगुना नहीं, बल्कि घातांकीय रूप से (exponentially) अधिक सुरक्षित है।

अब तक क्रैक (गुणनखंड) की गई सबसे बड़ी key 829 bits की थी, और ऐसा करने के लिए एक आधुनिक सुपरकंप्यूटर की आवश्यकता थी। टीम ने 2.1 GHz Intel Xeon Gold 6130 CPU का उपयोग करते हुए लगभग 2700 CPU core-years का उपयोग किया। AWS पर सबसे सस्ते 16 core CPU की कीमत $0.40 सेंट प्रति घंटा है, इसलिए इस key को क्रैक करने की लागत लगभग $9.4 मिलियन डॉलर है। यहां तक कि cloud provider से भारी छूट मान लेने पर भी, इसकी लागत लाखों में है।

Solidity में 256 bits से अधिक के साथ Modular arithmetic

Ethereum केवल 32 byte data types का समर्थन करता है, इसलिए डिफ़ॉल्ट रूप से, हम निष्पादित नहीं कर सकते हैं

Copy
s ^ e % n

शुक्र है, ethereum blockchain ने विशेष रूप से modular arithmetic का समर्थन करने के लिए EIP 198 में एक precompiled contract जोड़ा है। इसका उपयोग करने के लिए, base, exponent, और modulus को abi encoded प्रारूप में memory में लोड किया जाना चाहिए। फिर address 0x05 पर स्थित contract को invoke किया जाता है।

यदि आप bits की एक सुरक्षित मात्रा का उपयोग करते हैं तो public key को store करना थोड़ा समस्याग्रस्त हो जाता है। यदि key size 1024 bits है, तो इसके लिए 4 storage slots की आवश्यकता होती है। Storage से public key को पढ़ने के लिए चार SLOAD operations होंगे, जिसके लिए कुल 8,400 gas खर्च होगी। यह अपने आप में पहले से ही ऊपर benchmark किए गए ECDSA समाधान की तुलना में कम कुशल है।

यदि हम immutable variables का उपयोग करते हैं, तो यह लागत काफी हद तक समाप्त हो जाती है, लेकिन यह एक कमजोरी पैदा करता है यदि हम पूर्वव्यापी रूप से किसी को presale से नहीं हटा सकते। पारंपरिक ECDSA या Merkle Trees में, हम केवल signing address या Merkle Root को बदल देते हैं। यदि हम एक immutable variable का उपयोग करते हैं तो यह संभव नहीं है।

हालाँकि, public key को storage के बजाय bytecode में store करना मुख्य विचार है। किसी external contract के bytecode (EXTCODECOPY) को पढ़ने में 2,600 gas का खर्च आता है, जो public key के प्रत्येक भाग को चार टुकड़ों में पढ़ने की 8,400 gas की तुलना में बहुत कम है।

किसी public key को अमान्य करने के लिए, हम आसानी से एक नया contract बना सकते हैं, और नए address को इंगित करने के लिए एक storage variable को अपडेट कर सकते हैं। लेकिन यह अतिरिक्त 2,100 gas वापस जोड़ देता है।

यह पता चला है कि external contract के address (जिसका bytecode public key को store करता है) को एक immutable variable में store करना संभव है, लेकिन फिर भी external smart contract के bytecode को mutate करके public key को अमान्य किया जा सकता है।

Metamorphic contract pattern के साथ public key को अमान्य करना

deployment bytecode को memory में लोड करके, और फिर runtime code वाली bytecode की सीमा को वापस करके एक smart contract बनाया जाता है।

जब create2 कमांड के साथ एक smart contract बनाया जाता है, तो contract के address की पहले से भविष्यवाणी की जा सकती है। Address की गणना salt, deployer, और initialization bytecode के संयोजन से की जाती है। यदि contract selfdestruct हो जाता है, तो उसी address पर एक नया contract deploy किया जा सकता है।

ध्यान दें कि address initialization code का एक function है, न कि deployed code का। Initialization code द्वारा एक अलग runtime code लोड करवाकर विभिन्न bytecode deploy करना संभव है। समान initialization code लेकिन अलग deployment code के साथ selfdestructing और फिर से redeploy करके, contract का bytecode mutate हो सकता है।

इसलिए, हमारे पास एक ऐसा smart contract हो सकता है जिसके पहले k bytes एक निश्चित शर्त के तहत selfdestructing के लिए हों, लेकिन बाकी bytes केवल RSA public key हों।

चूंकि address पहले से निर्धारित होता है, इसलिए हम इस metamorphic contract के address को एक immutable variable में store कर सकते हैं। जब हमें public key की आवश्यकता होती है तो हम उस address से EXTCODECOPY कर सकते हैं। Public key को बदलने के लिए, हम contract को selfdestruct का निर्देश देते हैं, फिर उस address पर एक नया contract deploy करते हैं।

Access lists के साथ अतिरिक्त 100 gas बचाना

EIP 2930 ने एक नए प्रकार का transaction जोड़ा है जो उपयोगकर्ता को पहले से निर्दिष्ट करने की अनुमति देता है कि किन addresses और storage slots तक पहुंचा जाएगा। यह nodes को storage से उन values को prefetch करने की अनुमति देता है, जिससे निष्पादन का समय तेज हो जाता है। किसी external contract को call करते समय access list transaction का उपयोग करने से 100 gas की बचत हो सकती है। ध्यान दें कि यह बचत तब लागू नहीं होती है जब कोई smart contract अपने स्वयं के storage variable को एक्सेस करता है। चूंकि यह RSA presale airdrop डिज़ाइन public key को store करने के लिए एक external contract पर निर्भर करता है, इसलिए access list का उपयोग करना उचित है।

मानक (Benchmarks): Gas cost बनाम key size

अधिकांश gas cost बड़े signatures के परिणामस्वरूप बहुत बड़े calldata होने के कारण आती है। यदि key size 1024 bits पर सेट है, तो calldata 128 bytes का होगा। प्रत्येक byte की लागत 16 gas है, इसलिए इतने बड़े calldata को रखने के लिए कुल gas cost 2,048 gas है।

अधिकांश अन्य उपयोग के मामलों की तुलना में, हमारा मामला काफी अधिक memory का उपयोग करता है और Ethereum इसके लिए शुल्क लेता है।

यह ECDSA की तुलना में gas क्यों बचाता है

Benchmarks यह स्पष्ट करते हैं कि key (और इसलिए signature) जितनी बड़ी होगी, gas cost उतनी ही अधिक होगी। हमारा डिज़ाइन इस तथ्य का फायदा उठाता है कि precompile संख्याओं को कम घात तक बढ़ाने के लिए कम कीमत निर्धारित करता है। उन परिस्थितियों में 0x05 पर precompiled contract को निष्पादित करने की लागत ECDSA के लिए precompile को निष्पादित करने के लिए लगने वाले हजारों की तुलना में केवल कुछ सौ gas है।

Key size चुनना

हालाँकि 829 bits वाली एक key का गुणनखंड किया गया है, लेकिन ऐसा करने के लिए एक आधुनिक सुपरकंप्यूटर की आवश्यकता होती है। कम मूल्य वाले tokens के airdropping या NFTs को presale पर रखने जैसे अनुप्रयोगों के लिए, किसी हमलावर के पास public key का गुणनखंड करने और presale में एक NFT प्राप्त करने के लिए लाखों डॉलर खर्च करने का कोई प्रोत्साहन नहीं है। लिखते समय सबसे महंगे Ethereum tokens (Fidenza और Bored Ape Yacht Club) की कीमत लगभग $100,000 प्रति पीस है, इसलिए अधिकांश अनुप्रयोगों के लिए, एक हमलावर के लिए public key का गुणनखंड करने की कोशिश करना किफायती नहीं है।

याद रखें, प्रत्येक bit पूर्णांक का गुणनखंड करने की कठिनाई को दोगुना कर देता है, इसलिए 2022 तक, अधिकांश कम मूल्य वाले token presales शायद 896 bits के साथ सुरक्षित हैं। इस मामले में, उपयोगकर्ताओं को ECDSA की तुलना में 2,500 से अधिक gas बचाना आकर्षक है।

Key Size मानक (Benchmarks)

• RSA-896 (Gas: 26,850)
• RSA-960 (Gas: 26,925)
• RSA-1024 (Gas: 27,033)
• RSA-2048 (Gas: 29,271)

निष्कर्ष

हम presale या airdrop के लिए addresses निर्दिष्ट करने की एक नई विधि प्रस्तुत करते हैं जो आज के ज्ञात समाधानों की तुलना में अधिक कुशल है। Modular exponentiation precompile को metamorphic contract pattern और access list transaction के साथ जोड़कर, हम एक gas efficient तरीके से on-chain सुरक्षित RSA signatures को मान्य कर सकते हैं।

हमारा काम इस स्तर पर केवल एक proof of concept है। डेवलपर्स को production में code का उपयोग करते समय सावधानी बरतने की सलाह दी जाती है।

यह प्रोजेक्ट Suthan Somadeva और Michael Burke द्वारा RareSkills Solidity Bootcamp के हिस्से के रूप में बनाया गया था। Code implementation और unit tests github पर उपलब्ध हैं।

मूल रूप से 7 दिसंबर, 2022 को प्रकाशित