আধুনিক ক্রিপ্টোগ্রাফি ও জিরো-নলেজ প্রুফ (পর্ব ১৪): স্বচ্ছ প্রমাণ ব্যবস্থা: zk-STARKs, FRI প্রোটোকল ও পোস্ট-কোয়ান্টাম নিরাপত্তা

পেয়ারিং-ভিত্তিক zk-SNARKs আকারে অত্যন্ত ছোট হলেও তাদের দুটি মারাত্মক তাত্ত্বিক দুর্বলতা ছিল: সেগুলোর জন্য প্রয়োজন হতো বিপজ্জনক ট্রাস্টেড সেটআপ (Trusted Setup), এবং শোরের কোয়ান্টাম অ্যালগরিদমের সামনে উপবৃত্তাকার বক্ররেখা ভেঙে পড়ায় তারা কোয়ান্টাম-নিরাপদ ছিল না। ২০১৮ সালে এলি বেন-সাসন ও তার সহকর্মীরা আবিষ্কার করেন zk-STARKs (Scalable Transparent ARguments of Knowledge)। এটি ট্রাস্টেড সেটআপ চিরতরে বর্জন করে (Transparent), কোয়ান্টাম আক্রমণ প্রতিরোধ করে এবং ক্রিপ্টোগ্রাফিক হ্যাশ ও FRI প্রোটোকলের সাহায্যে অসম্ভব দ্রুত গণনা প্রমাণ করে।

১. অ্যালজেব্রাইক ইন্টারমিডিয়েট রিপ্রেজেন্টেশন (AIR)

zk-STARK-এ প্রোগ্রামকে প্রকাশ করা হয় AIR এক্সিকিউশন ট্রেস আকারে: যেখানে (T) সংখ্যক সারি (সময়ের ধাপ) এবং (W) সংখ্যক কলাম (মেমরি রেজিস্টার) থাকে। পুরো ট্রেসটি দুটি বহুপদী শর্ত মেনে চলে:

• বাউন্ডারি শর্ত: ইনপুট ও আউটপুট নির্দিষ্ট সারিতে ঠিক থাকা: (P(0) = ext{input})।
• ট্রানজিশন শর্ত: এক সারি থেকে পরের সারিতে যাওয়ার বৈধ নিয়ম: (C(T(X), T(g cdot X)) = 0)।

যদি সম্পূর্ণ ট্রেস সত্য হয়, তবে কম্পোজিশন পলিনোমিয়াল (CP(X)) একটি নির্দিষ্ট লো-ডিগ্রি (Low-Degree) বহুপদী হবে। কিন্তু যদি এক লাইনেও কোনো প্রতারণা করা হয়, তবে পলিনোমিয়ালের ডিগ্রি কোটি কোটি গুণে বেড়ে যাবে।

২. ফাস্ট রিড-সলোমন FRI প্রোটোকল

একটি কমিট করা ফাংশন আসলেই একটি লো-ডিগ্রি বহুপদী কিনা তা ভেরিফায়ার কীভাবে সাব-লিনিয়ার সময়ে (মাত্র কয়েক মিলিসেকেন্ডে) পরীক্ষা করবে? এর সমাধান হলো FRI প্রোটোকল (Fast Reed-Solomon IOP of Proximity)।

FRI মূলত ফাস্ট ফুরিয়ার ট্রান্সফর্মের (FFT) উল্টো প্রক্রিয়ায় বহুপদীকে ভাঁজ (fold) করতে থাকে:

1. প্রতি রাউন্ডে প্রুভার পলিনোমিয়াল (f_i(X))-কে জোড় ও বিজোড় ঘাতে ভাগ করে: (f_i(X) = g_i(X^2) + X cdot h_i(X^2))।
2. ভেরিফায়ার একটি র্যান্ডম সংখ্যা (alpha_i) চ্যালেঞ্জ পাঠায়।
3. প্রুভার অর্ধেক ডিগ্রির নতুন পলিনোমিয়াল তৈরি করে:
   [
   f_{i+1}(Y) = g_i(Y) + alpha_i cdot h_i(Y)
   ]
4. নতুন পলিনোমিয়ালের মানগুলোকে একটি সাধারণ মারকেল ট্রিতে (Merkle Tree) হ্যাশ করে কমিট করে।

(log_2 d) ধাপ পর বহুপদীর ডিগ্রি শূন্যে (একটি কনস্ট্যান্ট সংখ্যায়) নেমে আসে। ভেরিফায়ার তখন মারকেল ট্রির কিছু শাখা পরীক্ষা করে নিশ্চিত হয় যে প্রুভার কোনো মিথ্যা বলেনি।

৩. পোস্ট-কোয়ান্টাম নিরাপত্তা ও প্রুফ সাইজের তুলনা

যেহেতু STARK-এ কোনো উপবৃত্তাকার বক্ররেখা বা পেয়ারিং নেই এবং নিরাপত্তার একমাত্র ভিত্তি সাধারণ মারকেল ট্রি ও ক্রিপ্টোগ্রাফিক হ্যাশ (Blake2 / Poseidon), তাই এটি কোয়ান্টাম কম্পিউটারের যেকোনো আক্রমণ শতভাগ প্রতিরোধ করতে সক্ষম।

এর একমাত্র ট্রেড-অফ হলো প্রুফের আকার: Groth16 যেখানে মাত্র ১২৮ বাইট, STARK প্রুফ সেখানে ৪০ থেকে ১০০ কিলোবাইট। তবে প্রুভারের গতি অবিশ্বাস্য রকমের দ্রুত হওয়ায় আধুনিক লেয়ার-২ রোল-আপগুলোতে (যেমন Starknet) STARK প্রযুক্তি রাজত্ব করছে।

শাকিল মাহমুদ সজল

সফটওয়্যার প্রকৌশলী ও লেখক, ঢাকা, বাংলাদেশ। কম্পিউটার বিজ্ঞান, পদার্থবিজ্ঞান, ইতিহাস ও ভাবনার সমন্বয়ে ব্যক্তিগত নোট ও প্রবন্ধ সংকলন।