تو سیستم های غیر متمرکز حجم داده های تقریبا زیادی داریم ، این داده ها از مبدا های مختلفی میاد و همشون ماله یک نفر نیست . نیازه که ما این داده ها رو به طریقی در کنار هم به شکل ایمن نگه داریم . از اونجایی که اطلاعات تو سیستم بلاکچینی تو بلاک ها ثبت می شن و بلاک ها باید غیر قابل تغییر باشن باید این موضوع رو هم مدنظر قرار بدیم . پس به چیزی احتیاج داریم که مجموعه بزرگی از داده ها رو نگه داره در مقابل تغییر روی خوش نشون نده . راه حل ساختار داده ای به اسم درخت مرکل (Merkle Tree) یا binary hash tree هم بهش میگن .
درخت مرکل چیه؟
برخلاف درخت های واقعی ، درختا تو دنیای کامپیوتری برعکس هستن و ریشه بالاتر از برگاس ! درخت مرکل هم همینطوریه ، برگای این درخت حاوی هش تک تک عناصر دیتاستمون هستن و یه لول بالاتر از برگا یعنی پدرای برگا حاوی هش دو تا از برگا هستن که فرزندشون محسوب میشه . پس ابتدا مقدار هش دیتاها تک تک محاسبه میشه و تو برگای درخت ذخیره میشه بعد مقدار هشا دو تا دو تا کنار هم قرار میگیرن و دوباره ازشون هش گرفته میشه hash(t1+t2) و این روند تا جایی ادامه پیدا می کنه که به یه مقدار هش برسیم که بهش مرکل روت می گن (Merkle root) . امکانش هست که تعداد برگامون فرد باشه و در آخر یه برگ بدون شریک بمونه و برگی نباشه در اینصورت با خودش ترکیب میشه hash(t5+t5)
توابع هش
احتمالا با توابع هش آشنایی کافی رو دارید در صورتی که نمی دونید این توابع یه دیتایی مثلا متن یا عکس رو میگیرین و یه رشته متنی با طول ثابت رو تولید می کنن . مثلا تابع هش معروف SHA-256 دیتا با طول متغیر رو میگیره و در خروجی همیشه یه رشته متن ۲۵۶ بیتی تحویلمون میده . یه تابع هش خوب باید ویژگی هایی مثل :
- وروردی ثابت همیشه خروجی ثابت تولید کنه ( هش علی همیشه مساوی ۱۲۳۴ باشه)
- یکطرفه باشه : وقتی ورودی x رو به تابع میدیم و اون خروجی y رو میده ، از لحاظ الگوریتمی غیر ممکن باشه که با y بتونیم x رو به دست بیاریم
- کالیژن نداشته باشه : دوتا ورودی وجود نداشته باشه که خروجی یکسانی تولید می کنن . ( یا حداقل پیدا کردنش سخت باشه )
- اثر بهمنی (avalanche effect) :کوچیکترین تغییری در ورودی باعث تولید خروجی کاملا متفاوتی بشه یا حداقل نیمی از بیت ها تغییر کنن . اینطور نباشه که بگیم h میشه ۱۰۰۵ و وقتی he میشه ۱۰۵۵ !!
ویژگی های Merkle Tree
- یکپارچگی داده : روت درخت با کوچکترین تغییر در برگ ها و عناصر میانی تغییر می کنه . حتی جا به جا شدن عناصر دیتاست مرکل روت متفاوتی تولید می کنه .
- اعتبارسنجی قسمتی از درخت : برای اعتبارسنجی یه داده نیازی نیست کل درختو داشته باشیم فقط لازم مسیری که از برگ شروع میشه و به ریشه میرسه رو داشته باشیم .
چه مشکلاتی رو حل میکنه ؟
به عنوان یه نمونه زنده و قابل لمس بیت کوین رو مثال میزنم که از مرکل تری برای مطمئن شدن از تراکنش های داخل یه بلاک ازش استفاده می کنه . بیت کوین برای هر بلاکی که به زنجیرش اضافه میشه فیلدی به اسم مرکل روت داره یعنی میاد تمام تراکنش های داخل یه بلاک رو تو یه مرکل تری ذخیره میکنه . وقتی یه بلاک ماین میشه بقیه نود ها مرکل تری تراکنش ها رو دوباره حساب می کنن و با مقداری که تو بلاک نوشته شده مقایسه می کنن و اینطوری تایید میشه . البته از اونجایی که یه نود می تونه یک سری چرت و پرت به عنوان تراکنش تولید کنه و بعد مرکل روتش رو بدست بیاره نود ها باید تراکنش ها رو با mem pool خودشون هم مقایسه بکنن .
پیاده سازی مرکل تری با پایتون
خب برای پیاده سازی مرکل تری منطقی تر و راحت تر اینه که کمی از مفاهیم شی گرایی استفاده کنیم تا حجم کدنویسی، کپسوله سازی و قابلیت استفاده مجدد بهتری داشته باشیم. کارو با ساخت یه کلاس به نام MerkeleNode شروع می کنیم. که ۴ تا صفت داره یکی برای نگهداری نود پدر و دوتا برای نگهداری نودهای فرزندان و یک فیلد هم برای نگهداری مقدار تابع هش.
class MerkleNode:
'''Stores the hash and the parent'''
def __init__(self,hash):
self.hash = hash
self.parent = None
self.left_child = None
self.right_child = Noneحالا که کوچک ترین عضو این فضای مسئله که درخت مرکل هست رو ساختیم احتیاج به یک ساختار بزرگتری داریم که بتونیم از مرکل نودهایی که داریم استفاده کنیم و اون اعضای کوچک رو درونش سازماندهی کنیم. برای همین یک کلاس دیگه به اسم MerkleTree می سازیم که فیلدی داره یک آرایه برای نگهداری نود هاست و یک نود به عنوان ریشه یا روت. همچنین داخل همین تابع سازنده کلاسمون در صورتی که دیتا ورودی داشته باشیم باید درخت رو بسازیم.
class MerkleTree:
'''Stores the leaves and the root hash '''
def __init__(self, string_chunks = None):
self.leaves=[]
if string_chunks is not None :
for data in string_chunks :
node = MerkleNode(self.compute_hash(data))
self.leaves.append(node)
self.root = self.build_merkle_tree(self.leaves)قبل از نوشتن هر تابع دیگه به یک تابع برای تولید هش نیاز داریم. دیتا ورودی رو میگیره و هش رو تحویل میده. خیلی سرراست و کاربردی.
from hashlib import sha256
@staticmethod
def compute_hash(data):
data = data.encode()
return sha256(data).hexdigest()الآن باید تابعی که درخت رو میسازه رو بنویسیم که ورودیش در واقع آرایه نود های ماست. که فقط مقدار هش براش تولید شده و هنوز پدر و فرزندانش مشخص نیستن. دقت کنید که برای ساخت مرکل تری باید از پایین به بالا حرکت کنیم در واقع ما دوتا نود رو که قبلا مقدار هش براشون تولید کردیم رو برمیداریم باهم ترکیب می کنیم و یکبار دیگه هش میگریم ازشون تا نود که از ترکیب این دوتاس به وجود بیاد که بهش پدر میگیم.
این تابع یک تابع بازگشتی هست که فرزندان راست و چپ رو انتخاب میکنه در صورتی که تعداد نود های ما فرد باشه یکی از این نود ها تنها می مونه که درست نیست پس برای حلش باید مقدار هش خودش رو با خودش ترکیب کنیم. بعد این دوتا نود رو به یک تابع دیگه ای پاس میدیم تا مقدار هش پدر رو حساب کنه.
def build_merkle_tree(self , leaves):
'''Builds the merkle tree form a list of leaves , recursive function'''
leaves_len = len(leaves)
if leaves_len == 1 :
return leaves[0]
parents = []
for i in range(0 , leaves_len , 2):
left_child = leaves[i]
right_child = leaves[i + 1 ] if i + 1 < leaves_len else left_child
parents.append(self.create_parent(left_child , right_child))
return self.build_merkle_tree(parents)قسمتی که نود پدر رو میسازه همونطور که توضیح دادم مقدار هش فرزندانشو میگیره کنار هم میزاره و دوباره هش میگیره. اگه یادتون باشه تو کلاس MerkleNode که ساختیم دوتا فیلد به اسم نود راست و چپ داشتیم که تو این تابع نود ها ارسالی به این تابع هستن و همچنین فیلد پدر نودهای ارسالی به این تابع هم تغییر می کنن و به نود جدیدی که تو این تابع ساخته شده به عنوان نود پدر تغییر می کنن.
def create_parent(self , left_child , right_child):
'''Creates the parent node form children '''
parent = MerkleNode ( self.compute_hash(left_child.hash + right_child.hash ))
parent.left_child , parent.right_child = left_child , right_child
left_child.parent , right_child.parent = parent , parent
print("Left Child : {} , Right Child : {} ,Parent :{}".format(left_child.hash , right_child.hash , parent.hash))
return parent
تکرار این فرآیند در نهایت مارو به مرکل روت می رسونه که حاوی یک رشته به عنوان مقدار هش هست. چون با ترکیب هر دوتا از نود ها یک نود پدر به وجود میاد و با ادامه دادن این عمل در نهایت به یک مقدار هش میرسیم. الآن برای اینکه ما از immutable بود داده هامون مطمئن بشیم. فقط کافیه که دوباره همین عمل کنار هم قرار دادن هش نود ها و دوباره هش کردن رو ادامه بدیم تا به مرکل روت برسیم و در صورتی که با مقدار قبلی مرکل روت برابر بود یعنی که دیتا های ما بدون دستکاری باقی موندن .
می تونید کل کدهایی که برای پیاده سازی درخت مرکل رو این پایین ببینید.
def create_parent(self , left_child , right_child):
'''Creates the parent node form children '''
parent = MerkleNode ( self.compute_hash(left_child.hash + right_child.hash ))
parent.left_child , parent.right_child = left_child , right_child
left_child.parent , right_child.parent = parent , parent
print("Left Child : {} , Right Child : {} ,Parent :{}".format(left_child.hash , right_child.hash , parent.hash))
return parent
دارم سعی می کنم تا از مرخصیام استفاده خوبی بکنم. چون همونطور که بعضیاتون می دونید تو خدمت سربازی هستم پس اگه کمبود و نقصی بود به پای کم بودن زمان بزارید :)فعلا
