আধুনিক ক্রিপ্টোগ্রাফি ও জিরো-নলেজ প্রুফ (পর্ব ১২): অ্যারিথমেটিক সার্কিট ও Groth16 zk-SNARKs: R1CS থেকে QAP রূপান্তর

জিরো-নলেজ সাকসিনক্ট নন-ইন্টারেক্টিভ আর্গুমেন্ট অব নলেজ বা zk-SNARKs হলো আধুনিক কম্পিউটার বিজ্ঞানের এক পরম বিস্ময়: কোটি কোটি গণনার জটিল কাজকে মাত্র ১২৮ বাইটের একটি ক্ষুদ্র ফাইলে সংকুচিত করে ৩ মিলিসেকেন্ডের মধ্যে যাচাই করা যায়, অথচ গণনার গোপন তথ্য এক বিন্দুও প্রকাশ পায় না। এই অধ্যায়ে আমরা দেখব সাধারণ কোডকে ধাপে ধাপে রূপান্তর করার পূর্ণাঙ্গ পাইপলাইন: কোড থেকে অ্যারিথমেটিক সার্কিট, সার্কিট থেকে R1CS ম্যাট্রিক্স, লাগ্রাঞ্জ ইন্টারপোলেশন দিয়ে QAP বহুপদী সমীকরণ, এবং পরিশেষে জেনস গ্রোথের অমর Groth16 প্রোটোকল।

১. কোড থেকে R1CS ম্যাট্রিক্স ফ্ল্যাটেনিং

zk-SNARK কোনো প্রসেসরের অ্যাসেম্বলি কোডে কাজ করে না; যেকোনো প্রোগ্রামকে প্রথমে একটি সসীম ফিল্ড (mathbb{F}_p)-এর যোগ ও গুণ গেটের অ্যারিথমেটিক সার্কিটে রূপান্তর করা হয়। এরপর প্রতিটি গুণের গেটকে প্রকাশ করা হয় Rank-1 Constraint System (R1CS) সমীকরণে:

[
(A w) circ (B w) = (C w)
]

যেখানে (A, B, C) হলো কনস্ট্রেইন্ট ম্যাট্রিক্স, (w) হলো উইটনেস ভেক্টর (ইনপুট ও অভ্যন্তরীণ তারের মান) এবং (circ) হলো ভেক্টরের ইলিমেন্ট-ওয়াইজ গুণ। প্রতিটি সারি মূলত একটি গেটের শর্ত পরীক্ষা করে: (( ext{Left}) imes ( ext{Right}) = ( ext{Output}))।

২. কোয়াড্রেটিক অ্যারিথমেটিক প্রোগ্রাম (QAP)

যদি সার্কিটে ১০ লাখ গেট থাকে, তবে ভেরিফায়ারকে ১০ লাখ সমীকরণ পরীক্ষা করতে হবে, যা অত্যন্ত ধীরগতির। সিস্টেমকে সাকসিনক্ট (Succinct – সংক্ষিপ্ত) করতে ২০১৩ সালে জেনারো, জেনট্রি, পার্নো এবং রায়কোভা উদ্ভাবন করেন QAP: যেখানে ১০ লাখ ম্যাট্রিক্স সমীকরণকে লাগ্রাঞ্জ ইন্টারপোলেশনের সাহায্যে কয়েকটি একক বহুপদীতে (পলিনোমিয়ালে) রূপান্তর করা হয়।

টার্গেট পলিনোমিয়াল (T(X) = prod_{j=1}^m (X – r_j)) সংজ্ঞায়িত করা হয়। পুরো সার্কিটের সকল গেট শতভাগ সঠিকভাবে সম্পন্ন হয়েছে যদি এবং কেবল যদি:

[
L(X) cdot R(X) – O(X) = H(X) cdot T(X)
]

সমীকরণটি সত্য হয়, অর্থাৎ (T(X)) দিয়ে (L cdot R – O)-কে ভাগ করলে কোনো ভাগশেষ না থাকে। শোয়ার্টজ-জিপেল উপপাদ্য (Schwartz-Zippel Lemma) অনুযায়ী, এই জটিল বহুপদী সমীকরণটি পুরো গ্রাফ জুড়ে সত্য কিনা তা একটিমাত্র র্যান্ডম গোপন বিন্দু ( au)-তে পেয়ারিং দিয়ে পরীক্ষা করলেই শতভাগ নিশ্চিত হওয়া যায়।

৩. Groth16 zk-SNARK প্রোটোকল

২০১৬ সালে জেনস গ্রোথ উদ্ভাবন করেন Groth16, যা আজ পর্যন্ত ক্রিপ্টোগ্রাফির ইতিহাসে সর্বনিম্ন প্রুফ সাইজ ও দ্রুততম ভেরিফিকেশনের অবিসংবাদিত রেকর্ড ধরে রেখেছে:

• ট্রাস্টেড সেটআপ: গোপন সংখ্যা ((alpha, beta, gamma, delta, au)) তৈরি করে প্রুভিং কি ও ভেরিফিকেশন কি তৈরি করা হয়, এবং সাথে সাথে গোপন সংখ্যাগুলো চিরতরে ধ্বংস (Toxic Waste) করে ফেলা হয়।
• প্রুফ তৈরি: প্রুভার তার উইটনেস ব্যবহার করে ব্লাইন্ডিং ফ্যাক্টর যোগ করে মাত্র ৩টি গ্রুপ উপাদান তৈরি করে:
  [
  A in G_1, quad B in G_2, quad C in G_1
  ]
• সাকসিনক্ট ভেরিফিকেশন: ভেরিফায়ার মাত্র ৩টি পেয়ারিং সমীকরণের মাধ্যমে পুরো প্রমাণের সত্যতা নিশ্চিত করে:
  [
  e(A, B) stackrel{?}{=} e(alpha, beta) cdot e(x_{ ext{pub}}, gamma) cdot e(C, delta)
  ]

Groth16-এর প্রুফ সাইজ হলো তাত্ত্বিক সর্বনিম্ন সীমা: মাত্র ৩টি গ্রুপ উপাদান (১২৮ বাইট) এবং ভেরিফাই করতে সময় লাগে মাত্র ১.৫ মিলিসেকেন্ড। তবে এর প্রধান ট্রেড-অফ হলো প্রতিটি ভিন্ন ভিন্ন সার্কিটের জন্য আলাদা আলাদা ট্রাস্টেড সেটআপ অনুষ্ঠান আয়োজন করতে হয়।

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

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