ساختار درختی ورکل | وبلاگ بنیاد اتریوم

درخت ورکل یک طرح تعهد است که شبیه درخت مرکل عمل می‌کند، اما شاهدان بسیار کوچک‌تری دارد. این با جایگزینی هش در درخت مرکل با تعهد برداری عمل می کند، که فاکتورهای انشعاب گسترده تر را کارآمدتر می کند.

با تشکر از Kevaundray Wedderburn برای بازخورد در مورد پست.

بررسی اجمالی

برای جزئیات بیشتر در مورد نحوه عملکرد درختان ورکل، نگاه کنید به:

هدف این پست توضیح چیدمان بتن است پیش نویس درخت ورکل EIP. هدف آن توسعه‌دهندگان مشتری است که می‌خواهند درخت‌های verkle را پیاده‌سازی کنند و قبل از بررسی عمیق‌تر در EIP به دنبال معرفی هستند.

درختان ورکل تعدادی تغییر در ساختار درخت ایجاد می کنند. مهمترین تغییرات عبارتند از:

• تغییر از کلیدهای 20 بایتی به کلیدهای 32 بایتی (نباید با آدرس های 32 بایتی اشتباه گرفته شود، که یک تغییر جداگانه است).
• تلاش برای ادغام حساب و ذخیره سازی؛ و در نهایت
• معرفی خود verkle trye که از تعهدات برداری به جای هش استفاده می کند.

به عنوان طرح تعهد برداری برای درخت ورکل، از آن استفاده می کنیم تعهدات پدرسن. تعهدات پدرسن بر اساس منحنی های بیضوی است. برای مقدمه ای بر تعهدات پدرسن و نحوه استفاده از آنها به عنوان تعهدات چند جمله ای یا برداری با استفاده از آرگومان های محصول داخلی، رجوع کنید به اینجا.

منحنی که ما استفاده می کنیم این است Bandersnatch. این منحنی به این دلیل انتخاب شد که عملکردی دارد، و همچنین به این دلیل که به SNARK های کارآمد در BLS12_381 اجازه می دهد تا در مورد درخت verkle در آینده استدلال کنند. این می‌تواند برای جمع‌آوری‌ها مفید باشد و همچنین اجازه می‌دهد تا به‌روزرسانی را انجام دهیم که در آن همه شاهدان می‌توانند پس از عملی شدن، بدون نیاز به به‌روزرسانی تعهد بیشتر در یک SNARK فشرده شوند.

ترتیب منحنی / اندازه میدان اسکالر Bandersnatch است p = 13108968793781547619861935127046491459309155893440570251786403306729687672801، که یک عدد اول 253 بیتی است. در نتیجه، ما فقط می‌توانیم با خیال راحت رشته‌های بیت حداکثر ۲۵۲ بیتی را متعهد شویم، در غیر این صورت میدان سرریز می‌شود. ما یک ضریب انشعاب (عرض) 256 را برای درخت verkle انتخاب کردیم، به این معنی که هر تعهد می تواند تا 256 مقدار 252 بیتی را متعهد شود (یا به طور دقیق، اعداد صحیح تا p – 1). این را به صورت می نویسیم تعهد (v0، v1، …، v255) برای متعهد شدن به لیست v به طول 256.

چیدمان درخت ورکل

یکی از اهداف طراحی با درخت verkle EIP این است که دسترسی به موقعیت های همسایه (مثلاً ذخیره سازی با آدرس تقریباً یکسان یا تکه های کد همسایه) ارزان برای دسترسی باشد. برای انجام این کار، یک کلید از a ساقه از 31 بایت و یک پسوند یک بایت برای مجموع 32 بایت. طرح کلید به گونه ای طراحی شده است که مکان های ذخیره سازی “نزدیک” به یک ساقه و یک پسوند متفاوت نگاشت می شوند. برای جزئیات لطفا به پیش نویس EIP.

سپس خود درخت ورکل از دو نوع گره تشکیل شده است:

• گره های پسوند، که نشان دهنده 256 مقدار با ریشه یکسان اما پسوندهای متفاوت است
• گره های داخلی، که حداکثر 256 فرزند دارند که می توانند گره های داخلی یا گره های گسترش دهنده باشند.

تعهد به یک گره توسعه، تعهد به یک بردار 4 عنصری است. موقعیت های باقی مانده 0 خواهد بود.

C1 و C2 دو تعهد دیگر هستند که به تمام مقادیر با ساقه برابر با ساقه. دلیل اینکه ما به تعهدات نیاز داریم این است که مقادیر 32 بایت دارند، اما ما فقط می توانیم 252 بیت در هر عنصر فیلد را ذخیره کنیم. بنابراین یک تعهد واحد برای ذخیره 256 مقدار کافی نیست. بنابراین در عوض C1 مقادیر پسوند 0 تا 127 را ذخیره می کند و C2 مقادیر 128 تا 255 را ذخیره می کند، جایی که مقادیر به دو قسمت تقسیم می شوند تا در اندازه فیلد قرار گیرند (بعدا به آن خواهیم رسید.)

پسوند همراه با تعهدات C1 و C2 به عنوان “درخت گسترش و پسوند” (به اختصار EaS) نامیده می شود.

شکل 1 نمایش پیاده روی از طریق درخت ورکل برای کلید 0xfe0002abcd..ff04: مسیر از طریق 3 گره داخلی با 256 فرزند (254، 0، 2) می گذرد که یک گره گسترش دهنده نشان دهنده abcd..ff و دو تعهد درخت پسوند، از جمله مقدار برای 04، v4. توجه داشته باشید که ساقه در واقع 31 بایت اول کلید شامل مسیر عبور از گره های داخلی است.

تعهد به گره های برگ ارزش

هر گره درخت پسوند و پسوند 256 مقدار دارد. از آنجایی که یک مقدار 256 بیت عرض دارد و ما فقط می‌توانیم 252 بیت را به طور ایمن در یک عنصر فیلد ذخیره کنیم، اگر به سادگی سعی کنیم یک مقدار را در یک عنصر فیلد ذخیره کنیم، چهار بیت از بین می‌رود.

برای دور زدن این مشکل، ما گروه 256 مقدار را به دو گروه 128 مقداری تقسیم کردیم. هر مقدار 32 بایتی در یک گروه به دو مقدار 16 بایتی تقسیم می شود. بنابراین یک مقدار Vᵢ∈ 𝔹₃₂ به V⁽ˡᵒʷᵉʳ⁾ᵢ ∈ 𝔹₁₆ و V⁽ᵘᵖᵖᵉʳ⁾ᵢ∈ 𝔹₁₆ تبدیل می شود به گونه ای که V⁽ˡᵒʷᵉʳ⁾ᵢ ++ V⁽ᵘᵖᵖᵉʳ⁾ᵢ = Vᵢ.

یک “نشانگر برگ” به v⁽ˡᵒʷᵉʳ6ᵢ اضافه می شود تا بین برگه ای که هرگز به آن دسترسی پیدا نشده و برگه ای که با 0 ها رونویسی شده است تمایز قائل شود. هیچ ارزشی هرگز از درخت verkle حذف نمی شود. این برای طرح های انقضای ایالتی آتی مورد نیاز است. این نشانگر در بیت 129 تنظیم شده است ، یعنی V⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = V⁽ˡᵒʷᵉʳ⁾ᵢ + 2¹²⁸ اگر قبلاً به Vᵢ دسترسی داشته باشد ، و V⁽ˡᵒʷᵉʳ ᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ = 0 اگر Vᵢ هرگز به آن دسترسی پیدا نکرده باشد.

سپس دو تعهد C1 و C2 به صورت تعریف می شوند

تعهد گره های توسعه

تعهد به یک گره پسوندی از یک “نشانگر پسوند” تشکیل شده است که فقط عدد 1 است، دو تعهد زیر درخت C1 و C2 و ساقه کلید منتهی به این گره پسوند.

بر خلاف گره های توسعه در درخت Merkle-Patricia، که فقط شامل بخشی از کلید است که گره داخلی والد را به گره داخلی فرزند متصل می کند، ساقه کل کلید را تا آن نقطه پوشش می دهد. این به این دلیل است که درخت‌های ورکل با اثبات‌های بدون حالت در ذهن طراحی شده‌اند: اگر کلید جدیدی درج شود که پسوند را به دو قسمت تقسیم کند، خواهر یا برادر بزرگ‌تر نیازی به به‌روزرسانی ندارند، که امکان اثبات کوچک‌تر را فراهم می‌کند.

تعهد گره های داخلی

گره های داخلی روش محاسبه ساده تری را برای تعهدات خود دارند: گره به عنوان بردار 256 مقدار دیده می شود که (نمایش میدانی) تعهد ریشه هر یک از 256 زیردرخت آنها هستند. تعهد برای یک زیردرخت خالی 0 است. اگر زیردرخت خالی نباشد، تعهد برای گره داخلی است.

که در آن Cᵢ فرزندان گره داخلی هستند و 0 اگر فرزند خالی باشد.

درج در درخت

شکل 2 تصویری از فرآیند درج یک مقدار جدید در درخت است که وقتی ساقه ها روی چندین بایت اولیه با هم برخورد می کنند جالب می شود.

شکل 2 مقدار v192 در محل درج شده است 0000010000…0000 در یک درخت ورکل که فقط حاوی مقدار v127 در مکان است 00000000000…0000. از آنجا که ساقه ها در بایت سوم متفاوت هستند، دو گره داخلی تا بایت متفاوت اضافه می شود. سپس یک درخت «بسط و پسوند» دیگر با ساقه کامل 31 بایت وارد می شود. گره اولیه دست نخورده است و C20 همان مقدار C⁰0 را قبل از درج دارد.

درختان کم عمق تر، پروفیل های کوچکتر

ساختار درخت ورکل باعث ایجاد درختان کم عمق می شود که میزان داده های ذخیره شده را کاهش می دهد. با این حال، قدرت واقعی آن از توانایی ارائه شواهد کوچکتر، یعنی شاهدها ناشی می شود. این در مقاله بعدی توضیح داده خواهد شد.