تقني › FCMP++

Curve Trees وHelios وSelene

شجرة Merkle بنقاط بدلًا من التجزئات، يستغرق إثبات المسار فيها كيلوبايتات

باختصار

شجرة المنحنيات (Curve Tree) شجرة Merkle تكون فيها "تجزئة" الأب التزام Pedersen متجهيًا بإحداثيات أبنائه. تتناوب مستويات الشجرة بين منحنيين، Helios وSelene، يشكلان دورة: إحداثيات نقاط أحد المنحنيين أعداد قياسية للآخر. وهذا يجعل إثبات كل مستوى من المسار رخيصًا.

تذكير بشجرة Merkle

تجزّئ شجرة Merkle البيانات أزواجًا (أو مجموعات)، ثم تجزّئ التجزئات، حتى جذر واحد. ولإثبات أن عنصرًا موجود في الشجرة تُظهر المسار — الأشقاء في كل مستوى. وطول المسار log n.

لكننا نحتاج إلى إثبات المسار بمعرفة صفرية — دون إظهار الورقة ولا الأشقاء. وهذا يعني ترميز "حساب التجزئة" في دارة حسابية وإثبات الدارة. ودوال التجزئة العادية (Keccak، SHA) مكلفة جدًا في هذه الدارات: عشرات الآلاف من القيود لكل تجزئة.

فكرة Curve Trees

استخدم التزام Pedersen متجهيًا بوصفه "التجزئة":

parent = x₁·G₁ + x₂·G₂ + … + x_k·G_k xᵢ — الإحداثيات x لنقاط الأبناء؛ G₁…G_k — مولّدات ثابتة

إنها تجزئة جيدة لغرضنا (إيجاد تصادم صعب بقدر صعوبة اللوغاريتم المتقطع)، وهي في الدارة الحسابية شبه مجانية — إذا كانت الأعداد xᵢ أعدادًا قياسية للمنحنى الذي تقع عليه Gᵢ.

المشكلة: الأبناء نقاط على المنحنى E₁، لذا فإحداثياتها عناصر من الحقل الأساسي لـ E₁. ولاستخدامها كأعداد قياسية نحتاج إلى منحنى E₂ يكون حقل أعداده القياسية مساويًا للحقل الأساسي لـ E₁. وفي المستوى التالي، العكس. ويُسمى هذا الزوج دورة منحنيات.

الجذر المستوى: Helios المستوى: Selene O,I,C O,I,C O,I,C الأوراق: المخرجات الأوراق (إحداثيات نقاط Ed25519) ← Selene ← Helios ← Selene ← … ← الجذر
مخطط تقريبي. في الشجرة الحقيقية لكل عقدة عشرات الأبناء، لذا لا يتجاوز العمق بضعة مستويات.

Helios وSelene

اختيرت لـ Monero دورة خاصة "مرتكزة" على Ed25519: إحداثيات نقاط Ed25519 تقع في الحقل F_p، حيث p = 2²⁵⁵ − 19، وأحد منحنيي الدورة (Selene) حقل أعداده القياسية هو F_p هذا بالضبط. لذا يمكن "تجزئة" الأوراق (إحداثيات O, I, C على Ed25519) مباشرة على Selene، ثم إحداثيات نقاط Selene على Helios، وهكذا بالتناوب.

الاسمان مأخوذان من إلهَي الشمس (Helios) والقمر (Selene) عند الإغريق: منحنيان "يدور" كل منهما حول الآخر.

كيف يُثبت المسار

في كل مستوى لا يُظهر المُثبِت نقطة الأب نفسها بل نسخة معاد تعشيتها منها (النقطة مضافًا إليها مضاعف عشوائي لمولّد آخر)، ويُثبت في دارة على المنحنى المقابل:

  1. "أعرف الأبناء، وأحدهم هو النقطة المعاد تعشيتها من المستوى السابق"؛
  2. "هؤلاء الأبناء، مجموعين مع المولّدات، يعطون الأب (المعاد تعشيته)".

للتحقق بكفاءة من العمليات على المنحنى داخل الدارة، تُستخدم القواسم (تقنية Liam Eagen): بدلًا من الضرب القياسي خطوة بخطوة، تُثبت خاصية لدالة كسرية على المنحنى، وهذا أرخص بكثير. انظر Generalized Bulletproofs والقواسم.

تُثبت جميع المستويات على أحد المنحنيين ببرهان Generalized Bulletproof واحد، وعلى الآخر — ببرهان ثانٍ. والنتيجة برهانان يكبر حجمهما مع عمق الشجرة، أي لوغاريتميًا مع عدد المخرجات.

تحديث الشجرة

عندما يتجاوز مخرج فترة القفل البالغة 10 كتل، تضيفه العقدة إلى الشجرة وتعيد حساب المسار إلى الجذر. يتحدث الالتزام المتجهي تدريجيًا: إضافة ابن تعني إضافة x·Gᵢ إلى الأب، دون إعادة حساب الآخرين. وعند إعادة تنظيم السلسلة، تُلغى التغييرات.

لماذا ليس zk-SNARK؟

كان يمكن إثبات مسار في شجرة Merkle عادية باستخدام SNARK (كما يفعل Zcash). لكن SNARKs الشائعة تحتاج إما إلى إعداد موثوق أو إلى افتراضات تشفيرية تتجاوز اللوغاريتم المتقطع. أما Curve Trees + Bulletproofs فتبقى في عالم "اللوغاريتم المتقطع فقط، بلا إعداد" الذي عاش فيه Monero منذ البداية.