Merkle Tree: العامل المشترك بين Git & TLS & Dynamo
Merkle Tree: العامل المشترك بين Git & TLS & Dynamo
في 2011 حدث إختراق من قبل هاكر إيراني لأحد وسطاء بيع شهادات TLS وقام بإنشاء شهادة لموقع قوقل، وأصبح بإمكانه التنصت على كل شيء يمر بإستخدام HTTPS وإمكانية التعديل عليه أيضًا. وحدثت حادثة مشابهة لها لاحقًا في نفس السنة لإستهداف Gmail. إستدعى هذا الشيء عمل قوقل على إنشاء ستاندرد جديد لحل مشكلة إنشاء شهادات مزورة لفك التشفير، من هنا خرج مشروع شفافية الشهادات Certificate Transperancy.
لهذا المشروع و Git وقاعدة البيانات Cassandra وBitTorrent وحتى للأسف Blockchain عامل مشترك جوهري ألا وهو Merkle Tree وهي شكل بيانات أنيق متعدد الإستخدامات في التأكد من صحة البيانات وإيجاد النواقص منها أيضًا!
محتوى المقالة:
ماهو Merkle Tree
إستخدامها في مزامنة قواعد البيانات - Dynamo & Cassandra
إستخدامها في إثبات وجود وصحّة البيانات - Tampering-Evident Logs
إستخدامها في إدارة الأكواد - Git
ماهو Merkle Tree
أولًا لنفترض أن لديك ملف تود مشاركته مع أحدهم والتأكد انه وصل إليه بشكل سليم.. الحل هنا أن تقوم بإرسال الملف بشكله الطبيعي وأيضًا إرسال Checksum وهو عبارة عن جملة بسيطة تستخرجها عن طريق تمرير الملف كاملًا على Cryptographic Hash Function كـ sha256 مستخرجًا منها هذا النص الذي يمكن الشخص على الطرف الاخر تمرير الملف الذي قام بتحميله عليها للتأكد أن يحصل على نفس النص. هذه طريقة مستخدمة بكثرة عند تحميلك لأي برنامج على سبيل المثال تحميل كومبايلر لغة Go
حسنًا، تخيّل الآن أنك تود مشاركة مئات الملفات هذا يعني إن إستخدمنا الطريقة المذكورة بالاعلى أننا سنقوم بالمقارنات حتمًا لكل ملف على حدى أي أننا سنرسل الملفات وسنرسل سلسة كبيرة من الهاشات التي سيصل مجموع حجمها لعدد لايستهان به. ولكن Merkle Tree تقوم ببناء طريقة أكثر كفاءة من ناحية عدد المقارنات والبيانات المنقولة.
نبدأ ببناء الشجرة من الأسفل للأعلى بأن نضع البيانات بشكلها الطبيعي بالقسم السفلي للشجرة (Data Blocks) ويجب أن تكون بالترتيب نفسه دائمًا.. ونقوم ببناء الطبقة الأعلى منها بإستخراج الـ Hash عن طريق استخدام دالة تشفير ومن ثم بالطبقة الأعلى نبدأ بمرحلة جمع كل إثنان من الـ Hash السابقة وتشفيرهما معًا ونعيد هذه الخطوات الى أن نصل الى رأس هرم الشجرة Root وهكذا يصبح لدنيا مايعرف بالـ Root Hash. الأفضل أن تنظر الى كود قام ببناءها حتى تعي كل التفاصيل هنا بلغة Python.
للإستزادة:
إستخدامها في مزامنة قواعد البيانات -
Dynamo & Cassandra
أحد أول إستخدام رأيته كان في قواعد البيانات المتوزعة التي تكون Eventually Consistent على سبيل المثال Cassandra وDynamo بحيث تقوم هذه القواعد بعمل Anti-Entropy process تقوم بمقارنة الـ Root Hash بين خوادم البيانات وفي حال وجود إختلاف يتم تبادل مجموعة الـHashes التي تندرج تحتها الى أن يتم إيجاد الفرق بينهما. هذه الطريقة تحفظ الكثير من الـ Bandwidth وتقدم ضمانات ثابتة لحد كبير بغض النظر حجم البيانات
للإستزادة:
إستخدامها في إثبات وجود وصحّة البيانات - Tampering-Evident Logs
لحل مشكلة الهاكر الايراني تم إستخدام Merkle Tree لبناء Tamper-evident Logs ويتم نشر هذه البيانات والتأكد منها بإستخدام أدوات مثل Trillian بحيث تنشر كل عملية ومعها إمكانية إنتاج Proof نستطيع إستخدامها للتأكد من أن هذه العملية بالفعل قد تمت. بالاسفل طريقة عملها مع إنشاء الشهادات SSL Certificates.
للإستزادة:
إستخدامها في إدارة الاكواد - Git
يقوم Git بمعرفة الاختلافات في الكود ومزامنتها وربطها ببعضها البعض عن طريق بناء مستودع الكود على طريقة Merkle Tree تحتوى على الملفات ويتم معرفة الفروقات عن طريقة مقارنة الـ Hash للنسخة الجديدة. وحتى الـ Commit هي عبارة عن إنشاء Node جديد يتم الإشارة له بالـ Hash لمحتواه ويؤشر لـ Root Hash للشجرة الجديدة التي تحتوي التعديلات التي قمت بها في هذه الـ Commit.
للإستزادة:
ختامًا
معرفة هياكل البيانات والتعمق بها هي من أهم الأدوات التي بإمكانك إستخدامها عند كتابة الكود وتصميم الأنظمة، فغالبًا بإمكانك تحسين أداء ماتقوم بكتابته بأضعاف مضاعفة بإستخدام هيكلة البيانات الأمثل.
في حال كان لديك أسئلة شاركها معنا في تويتر، وأن أعجبتك المقالة لاتنسى مشاركتها مع الآخرين.