Merkle Tree ও Hashing
- ●Cryptographic hash হলো এক ধরনের one-way fingerprint — input সামান্য বদলালে output সম্পূর্ণ পাল্টে যায়।
- ●Merkle tree অনেক data-এর hash জোড়ায় জোড়ায় মিলিয়ে একটি একক Merkle root-এ পরিণত করে।
- ●Merkle proof দিয়ে পুরো data না নিয়েই অল্প কয়েকটি hash দিয়ে একটি item-এর অন্তর্ভুক্তি যাচাই করা যায়।
সমস্যাটা কী?
ধরো একটা block-এ ১০,০০০ transaction আছে। তুমি একজন lightweight user — তোমার ফোনে পুরো blockchain রাখার জায়গা নেই। এখন তুমি জানতে চাও: "আমার একটা নির্দিষ্ট transaction কি সত্যিই ওই block-এ আছে?"
সহজ উপায় হলো পুরো block ডাউনলোড করে এক এক করে মেলানো — কিন্তু সেটা বিশাল, ধীর ও অপচয়মূলক। আবার শুধু একটা মোট hash রাখলে জানা যাবে block বদলেছে কিনা, কিন্তু কোন transaction-টা সমস্যা সেটা ধরা যাবে না, এবং একটি item আছে কিনা তা সরাসরি প্রমাণ করা যাবে না।
দরকার এমন একটা গঠন, যা দিয়ে (১) পুরো dataset-এর integrity এক নজরে যাচাই করা যায়, এবং (২) অল্প তথ্যে একটি নির্দিষ্ট item-এর অন্তর্ভুক্তি প্রমাণ করা যায়। এই দুটোই দেয় Merkle tree — আর তার ভিত্তি হলো hashing।
মূল ধারণা
Cryptographic hash function এমন একটি ফাংশন যা যেকোনো আকারের input থেকে নির্দিষ্ট দৈর্ঘ্যের একটি অনন্য-প্রায় fingerprint তৈরি করে, যা one-way (output থেকে input ফেরত পাওয়া যায় না) এবং collision-resistant (দুটো ভিন্ন input-এর একই output পাওয়া কার্যত অসম্ভব)। Merkle tree এই hash-গুলোকে গাছের মতো সাজিয়ে গোটা dataset-কে একটি একক Merkle Root-এ সংকুচিত করে।
কীভাবে কাজ করে
Cryptographic hash-এর বৈশিষ্ট্য
একটি ভালো hash function (যেমন SHA-256)-এর কয়েকটি মূল গুণ:
- Deterministic — একই input সবসময় একই output দেয়।
- One-way (preimage resistance) — output দেখে input বের করা যায় না।
- Avalanche effect — input-এ এক bit বদলালে output প্রায় অর্ধেক bit বদলে যায়।
- Collision resistance — দুটো ভিন্ন input-এর একই hash খুঁজে বের করা কার্যত অসম্ভব।
এই গুণগুলোর কারণেই hash data-integrity যাচাইয়ের চমৎকার হাতিয়ার।
Merkle tree-এর গঠন
ধরো চারটি transaction: A, B, C, D। ধাপে ধাপে:
- প্রতিটির hash নাও —
Ha, Hb, Hc, Hd(এগুলো leaf node)। - জোড়ায় জোড়ায় মিলিয়ে আবার hash নাও —
Hab = hash(Ha + Hb),Hcd = hash(Hc + Hd)। - শেষ দুটোকে আবার মিলিয়ে —
Hroot = hash(Hab + Hcd)। এটাই Merkle root।
Hroot
/ \
Hab Hcd
/ \ / \
Ha Hb Hc Hd
| | | |
A B C D
Merkle root-টি গোটা dataset-এর একটি সংক্ষিপ্ত fingerprint। কোনো একটি transaction বদলালে তার leaf hash বদলায়, যা উপরের দিকে গিয়ে root-ও বদলে দেয়।
Merkle Proof (efficient verification)
ধরো তুমি প্রমাণ করতে চাও C সত্যিই এই tree-তে আছে। তোমার পুরো A, B, D লাগবে না — শুধু কয়েকটি sibling hash লাগবে:
Hd(C-এর পাশের পাতা)Hab(পরের স্তরের পাশের শাখা)
এই দুটো দিয়ে তুমি নিজে গণনা করবে: Hcd = hash(Hc + Hd), তারপর hash(Hab + Hcd)। যদি ফল পরিচিত Merkle root-এর সমান হয়, তাহলে C অবশ্যই অন্তর্ভুক্ত। এই কয়েকটি hash-ই হলো Merkle proof।
খরচের তুলনা
| পদ্ধতি | কতটা data লাগে | যাচাই খরচ |
|---|---|---|
| পুরো dataset ডাউনলোড | n item সবগুলো | O(n) |
| শুধু একক সামগ্রিক hash | খুব কম | অন্তর্ভুক্তি প্রমাণ করা যায় না |
| Merkle proof | log n hash | O(log n) |
১০,০০,০০০ item-এর জন্য Merkle proof-এ মাত্র প্রায় ২০টি hash লাগে — বিশাল সাশ্রয়।
ভাবো, একটা স্কুলে ৫১২ জন ছাত্রের পরীক্ষার খাতা। প্রিন্সিপাল চান নিশ্চিত হতে যে কোনো খাতায় কারচুপি হয়নি। প্রতি দুজনের খাতার মিলিত একটা সিল বানানো হলো, তারপর প্রতি দুটো সিলের মিলিত সিল — এভাবে শেষে পুরো স্কুলের একটি "মাস্টার সিল" (Merkle root)। এখন কোনো অভিভাবক যদি প্রমাণ চান যে তাঁর ছেলের খাতা গণনায় ছিল, প্রিন্সিপালকে গোটা ৫১২টি খাতা দেখাতে হবে না — শুধু সেই ছেলের খাতার পথ ধরে কয়েকটি পাশের সিল দেখালেই (Merkle proof) তা মাস্টার সিলের সাথে মিলিয়ে যাচাই করা যাবে।
কৌশল
Merkle tree ব্যবহারের সময় কিছু সাধারণ বিষয়:
- বিজোড় সংখ্যা handle করা — leaf-এর সংখ্যা বিজোড় হলে সাধারণত শেষেরটিকে নিজের সাথেই জোড়া (duplicate) দেওয়া হয়।
- নির্ধারিত ক্রম — leaf-গুলোর ক্রম স্থির রাখতে হয়, নইলে একই data থেকে ভিন্ন root আসবে।
- Hash function নির্বাচন — collision-resistant ও আধুনিক function (SHA-256 ইত্যাদি) ব্যবহার করা।
- Merkle Patricia Trie — Ethereum state-এর জন্য আরও উন্নত একটি রূপ, যেখানে দ্রুত আপডেট ও key-value lookup সম্ভব।
কখন ব্যবহার করবে / করবে না
ব্যবহার করো যখন:
- বিশাল dataset-এর integrity দ্রুত যাচাই করতে হবে।
- পুরো data না নিয়ে নির্দিষ্ট item-এর অন্তর্ভুক্তি (membership) প্রমাণ দরকার (যেমন light client)।
- দুটো বড় dataset-এর পার্থক্য কার্যকরভাবে খুঁজতে হবে (sync)।
কম প্রয়োজন যখন:
- dataset খুব ছোট, যেখানে সরাসরি তুলনাই যথেষ্ট।
- data ঘন ঘন বদলায় এবং প্রতিবার পুরো tree পুনর্গণনা ব্যয়বহুল (যদিও আংশিক আপডেট সম্ভব)।
Merkle proof শুধু প্রমাণ করে একটি item একটি নির্দিষ্ট root-এর অধীনে আছে — তা প্রমাণ করে না যে সেই root-টিই বৈধ/সঠিক chain-এর। বৈধতা আসে consensus থেকে। তাই Merkle proof-কে consensus-এর বিকল্প ভেবো না; এটি একটি verification টুল মাত্র।
বাস্তব উদাহরণ
Bitcoin-এ প্রতিটি block-এর header-এ ওই block-এর সব transaction-এর Merkle root থাকে। ফলে SPV (Simplified Payment Verification) wallet পুরো blockchain না রেখেই, শুধু block header ও একটি Merkle proof দিয়ে যাচাই করতে পারে যে তার transaction অন্তর্ভুক্ত।
Ethereum state, transaction ও receipt-এর জন্য Merkle (Patricia) tree ব্যবহার করে, যাতে account balance-এর মতো অবস্থা দক্ষভাবে যাচাই করা যায়।
Blockchain-এর বাইরেও Merkle tree সর্বত্র: Git কমিট ও ফাইল-ট্রির integrity রাখতে hash-tree ব্যবহার করে; distributed database (যেমন Cassandra, DynamoDB) replica গুলোর মধ্যে পার্থক্য খুঁজতে anti-entropy sync-এ Merkle tree চালায়; IPFS-ও content-addressing-এ এই ধারণা ব্যবহার করে।
ইন্টারভিউতে যদি "দুটো বড় distributed copy দ্রুত মেলাবে কীভাবে?" জিজ্ঞাসা করে — Merkle tree-র কথা বলো। দুই দিকের root আলাদা হলে শুধু যে subtree-তে root আলাদা, সেদিকেই নামতে থাকো — এভাবে O(log n)-এ ঠিক কোন অংশটা ভিন্ন তা খুঁজে পাওয়া যায়, পুরো data না মিলিয়েই।
মূল শব্দ (Key Terms)
মিনি কুইজ
1. Cryptographic hash function-এর কোন বৈশিষ্ট্যটি সবচেয়ে গুরুত্বপূর্ণ data-integrity যাচাইয়ের জন্য?
2. Merkle root কী?
3. Merkle proof-এর মূল সুবিধা কী?