💻 computer science

Protocols for Univariate Sumcheck

تقدم هذه الورقة ثلاثة نهج مرشحة لبروتوكول التحقق من المجموع أحادي المتغير فوق جذور الوحدة، بما في ذلك بروتوكول تقييم متعدد الحدود واختزالين للتقييم متعدد المتغيرات متوافقين مع Gemini، وكلها تدعم اختزالات اختيارية للجولات مع الحفاظ على زمن إثبات خطي.

المؤلفون الأصليون: Malcom Mohamed

نُشر 2026-03-24

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Malcom Mohamed

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك شيف ماهر (المُثبِت) تحاول إقناع ناقد طعام متشكك (المُتحقِّق) بأنك قد طهوت مأدبة ضخمة مكونة من $2^m$ طبقاً، وأن إجمالي درجات النكهة لجميع تلك الأطباق مجتمعة يساوي رقماً محدداً، وليكن "100".

المشكلة؟ الناقد كسول. فهو لا يريد تذوق كل طبق (لأن ذلك سيستغرق وقتاً طويلاً جداً). هو فقط يريد ضماناً رياضياً سريعاً بأنك لا تكذب.

هذه الورقة البحثية تدور حول ابتكار طرق جديدة، أسرع، ليلعب فيها الشيف والناقد "لعبة الثقة" هذه عندما تكون الأطباق مرتبة في نمط دائري محدد (يسمى "جذور الوحدة").

إليك تفصيل الأفكار الثلاث الرئيسية للورقة، باستخدام تشبيهات بسيطة:

الخلفية: مطبخان مختلفان

في عالم التشفير (تحديداً الـ SNARKs، والتي تشبه "براهين المعرفة الصفرية")، هناك طريقتان لتنظيم البيانات:

مطبخ متعدد المتغيرات (Multilinear Kitchen): تُنظم فيه البيانات في شبكة (مثل جداول البيانات). الطريقة القياسية للتحقق من إجمالي النكهة هنا تسمى Sumcheck متعدد المتغيرات. وهي فعالة جداً للشيف (طهي سريع) ولكنها تتطلب جولات كثيرة من الأسئلة من قِبل الناقد (أخذ ورد كثير).
المطبخ أحادي المتغير (Univariate Kitchen): تُنظم فيه البيانات في خط طويل واحد (دائرة). الطريقة القياسية للتحقق من هذا هي Aurora. وهي سريعة جداً للناقد (أسئلة قليلة) ولكنها بطيئة للشيف (يستغرق وقتاً طويلاً في إعداد البرهان).

الهدف: يريد المؤلف، مالكوم محمد، بناء جسر. يريد بروتوكولاً يسمح للشيف بالطهي في "المطبخ أحادي المتغير" (الخط الدائري) ولكن مع الاستمتاع بسرعة "المطبخ متعدد المتغيرات" (الطهي السريع)، دون جعل الناقد ينتظر طويلاً.

الحلول الثلاثة (البروتوكولات)

1. "المترجم السحري" (البروتوكول 2)

الفكرة: "دعونا نتظاهر بأن خط الأطبما الدائري هو في الواقع شبكة."
التشبيه: تخيل أن لدى الشيف خطاً طويلاً من المكونات. يسأل الناقد: "هل إجمالي نكهة هذا الخط يساوي 100؟"
الحيلة: يستخدم الشيف "مترجماً سحرياً" (محولاً) ليعيد ترتيب ذلك الخط الطويل فوراً إلى شبكة ثلاثية الأبعاد في ذهنه.
كيف يعمل: يقول الشيف: "أنا لا أتحقق من خط فحسب؛ أنا أتحقق من شبكة!" ثم يستخدم "فحص الشبكة" السريع القياسي (Multivariate Sumcheck) لإثبات النكهة.
العقبة: للقيام بذلك، يتعين على الشيف إرسال الكثير من رسائل "الأوراكل" (مثل إرسال قائمة بالمكونات للناقد) لإثبات أن عملية الترجمة صحيحة.
النتيجة: هو سريع للشيف، ولكنه يتطلب بضع خطوات إضافية لإعداد الترجمة.

2. إصلاح "المخطط المكسور" (البروتوكول 3)

الفكرة: "لنطوِ الخط على نفسه، مراراً وتكراراً، حتى يصبح صغيراً."
التشبيه: تخيل أن لدى الشيف لفافة طويلة من الوصفات. يقول الناقد: "اطوِ هذه اللفافة من المنتصف. الآن، تحقق مما إذا كان النصف العلوي والنصف السفلي يتطابقان بطريقة معينة."
المشكلة: تشير الورقة إلى أن محاولة سابقة لهذا (تسمى بروتوكول DGM) كانت تحتوي على خطأ برمجي (Bug). كان الأمر يشبه مخططاً يقول: "اطوِ الورقة"، لكنه لم يخبرك كيف تلصق الحواف حتى لا تنهار. الرياضيات لم تكن متطابقة تماماً.
الإصلاح: يقوم المؤلف بإصلاح المخطط. يضيف خطوة "لصق" (التحقق من معاملات محددة) لضمان أن الورقة المطوية لا تزال وصفة صالحة.
النتيجة: يسمح هذا للشيف بطي المشكلة لأسفل حتى تصل إلى حجم ضئيل جداً، ثم استخدام أداة تسمى Gemini لإنهاء المهمة. إنه يعمل، لكنه معقد بعض الشيء ويرسل الكثير من البيانات.

3. "الاختصار المباشر" (البروتوكول 4) - نجم العرض

الفكرة: "لماذا الترجمة أو الطي؟ لنقم بفحص الشبكة مباشرة، ولكن مع لمسة خاصة."
التشبيه: بدلاً من ترجمة الخط إلى شبكة (البروتوكول 1) أو طي الورقة (البروتوكول 2)، أدرك الشيف أن "الخط" و"الشبكة" هما في الواقع نفس الشيء، ولكن من زاوية رؤية مختلفة.
الحيلة: يستخدم الشيف خدعة رياضية ذكية (Kronecker substitution) ليعامل الخط الوحيد من البيانات كما لو كان شبكة منذ البداية.
كيف يعمل:
1. يرسل الشيف "متعدد حدود ملخص" (ملخص للنكهات).
2. يختار الناقد رقماً عشوائياً.
3. يثبت الشيف أن الملخص يطابق الرقم العشوائي.
4. يكررون العملية، مع تقليص حجم المشكلة إلى النصف في كل مرة، حتى تصبح صغيرة جداً.
النتيجة: هذه هي الطريقة الأسرع والأبسط. تتطلب أقل قدر من البيانات المرسلة وأقل وقت للشيف. الأمر يشبه قول الشيف: "لم أكن بحاجة للترجمة أو الطي؛ لقد كنت أعرف الإجابة في الشبكة طوال الوقت."

"تقليل الجولات" (دفعة السرعة)

هناك ميزة رائعة أخرى مذكورة: تقليل الجولات (Round Reduction).

المشكلة: حتى مع الطرق السريعة، إذا كان لديك مأدبة ضخمة ( $2^{100}$ طبقاً)، فقد تضطر للحديث ذهاباً وإياباً 100 مرة. هذا عدد كبير جداً من الجولات لنظام يعمل في الوقت الفعلي.
الحل: توضح الورقة أنه يمكنك إيقاف عملية "الطي" أو "الفحص" مبكراً (مثلاً بعد 10 جولات) عندما تصبح المشكلة صغيرة بما يكفي.
التشبيه: بدلاً من طي الورقة 100 مرة حتى تصبح نقطة صغيرة، تطويها 10 مرات حتى تصبح مربعاً صغيراً. ثم تسلم ذلك المربع الصغير إلى آلة أخرى فائقة السرعة (مثل Aurora) يمكنها فحصها في خطوة نهائية واحدة فقط.
الفائدة: هذا يخفض المحادثة من 100 جولة إلى 10 جولات فقط (أو حتى $\sqrt{m}$ جولة)، مما يجعل العملية سريعة للغاية للناقد، بينما لا يزال الشيف يقوم بالعمل في زمن خطي (سريع جداً).

الملخص

الورقة البحثية تدور حول تحسين "لعبة الثقة" للبراهين التشفيرية.

البروتوكول 1 يترجم المشكلة إلى تنسيق مختلف لاستخدام أدوات سريعة موجودة.
البروتوكول 3 يصلح طريقة "طي" مكسورة.
البروتوكول 4 يجد المسار الأكثر مباشرة وكفاءة من خلال إدراك أن التنسيقين متوافقان طبيعياً.

الخلاصة: وجد المؤلف طريقة لجعل Univariate Sumchecks (فحص خط طويل من البيانات) سريعاً وفعالاً مثل Multivariate Sumchecks (فحص شبكة)، مع الحفاظ على انخفاض عدد الأسئلة التي يطرحها الناقد. وهذا يجعل الأنظمة التشفيرية المستقبلية (مثل أدوات الخصوصية في البلوكشين) أسرع وأكثر قابلية للتوسع.

إليك ملخص تقني مفصل لورقة "بروتوكولات لمجموع أحادي المتغير" (Protocols for Univariate Sumcheck) للباحث مالكوم محمد.

1. بيان المشكلة

تتناول الورقة عدم التماثل الجوهري في تصميم براهين المعرفة غير التفاعلية الموجزة (SNARKs). تنقسم أنظمة SNARK عموماً إلى فئتين بناءً على كيفية ترميز البيانات:

الأنظمة متعددة الخطية (Multilinear Systems): تستخدم الامتدادات متعددة الخطوط (mlex) لمتجهات البيانات. وهي عادة ما تستخدم بروتوكول المجموع متعدد المتغيرات (multivariate sumcheck) القياسي (LFKN)، والذي يوفر كفاءة ممتازة للمُثبت (وقت خطي) ولكنه يتطلب $O(m)$ من جولات التفاعل، مما يجعله كثيف النطاق الترددي وغير صديق للمُتحقق.
الأنظمة أحادية المتغير (Univariate Systems): تستخدم الامتدادات أحادية المتغير (unex) فوق جذور الوحدة. وهي عادة ما تستخدم بروتوكول أورورا (Aurora)، وهو بروتوكول مجموع أحادي المتغير بجولة واحدة. ومع ذلك، غالباً ما تعاني بروتوكولات المجموع أحادية المتغير القياسية من تعقيد أعلى للمُثبت (زمن شبه خطي أو أسوأ) مقارنة بنظيراتها متعددة المتغيرات.

السؤال الجوهري: هل من الممكن بناء بروتوكول مجموع أحادي المتغير بزمن خطي يضاهي كفاءة المُثبت في المجموع متعدد المتغيرات مع الاحتفاظ بكفاءة الجولات (أو على الأقل المرونة) للأنظمة أحادية المتغير؟

إن "الموائمات" (adaptors) الحالية التي تربط بين كثيرات الحدود متعددة المتغيرات وأحادية المتغير (مثل Gemini وCaulk وZeromorph) موجودة بالفعل، ولكن العديد منها يعاني من زمن مُثبت شبه خطي، أو يتطلب عمليات ترجمة معقدة للقواعد (من القيم إلى المعاملات)، أو يعتمد على بروتوكولات معيبة (تحديداً بروتوكول DGM).

2. المنهجية

يقترح المؤلف ثلاثة توجهات مرشحة لسد هذه الفجوة، تهدف جميعها إلى تقليل مشكلات المجموع أحادي المتغير إلى تقنيات متعددة المتغيرات فعالة أو اختزالات مباشرة ذات زمن خطي.

أ. تقليل متعدد الخطية إلى أحادي المتغير (القسم 3)

يتعامل التوجه الأول مع كثير الحدود الامتدادي أحادي المتغير (unex) كـ "أوراكل" (oracle) ويثبت عبارات حول الامتداد متعدد الخطوط (mlex) المقابل له.

الآلية: تقدم الورقة البروتوكول 2، وهو بروتوكول طي تكراري (recursive folding protocol). يقوم بتفكيك كثير الحدود أحادي المتغير $f$ إلى مكونات "مربعة" ( $f_{sq}$ ) و"غير مربعة" ( $f_{no}$ ) بناءً على جذور الوحدة.
الرؤية الجوهرية: باستخدام صيغة استكمال لاجرانج المعممة، يرسل المُثبت "أوراكلز" لهذه المكونات. ويقوم المُتحقق بالتحقق من الاتساق عند نقطة عشوائية. يسمح هذا بتشغيل بروتوكول المجموع متعدد المتغيرات القياسي مباشرة على تمثيل الـ mlex دون الحاجة لترجمة قواعد معقدة.
التعقيد: يحقق زمناً خطياً للمُثبت $O(2^m)$ وزمن $O(m)$ للمُتحقق.

ب. المجموع أحادي المتغير المباشر عبر تصحيح DGM (القسم 4.1 و4.2)

تحلل الورقة بروتوكولاً مقترحاً سابقاً من قبل دريك، غابيزون، ومكلر (DGM) حاول تقليل هوية النطاق أحادي المتغير إلى بروتوكول Gemini.

تحديد الخلل: يحدد المؤلف خللاً حرجاً في بروتوكول DGM الأصلي: التحقق من هوية كثير الحدود المقترح (المعادلة 3 في الورقة) يفشل لأن درجات كثيرات الحدود في الطرفين الأيسر والأيمن غير متطابقة، مما يجعل البروتوكول غير مكتمل ولا سليماً (neither complete nor sound).
التصحيح: تقترح الورقة البروتوكول 3، وهو نسخة مصححة. حيث تقدم فحوصات إضافية لضمان حدود الدرجة والاتساق بين الأجزاء "الزوجية/الفردية" لكثيرات الحدود وكثير الحدود الأصلي.
النتيجة: ينجح هذا البروتوكول المصحح في تقليل المجموع أحادي المتغير إلى Gemini، لكنه يظل أقل كفاءة من النهج المباشر بسبب الحاجة لأوراكلز وعناصر حقل إضافية.

ج. التقليل المباشر إلى Gemini (القسم 4.3)

المساهمة الأهم هي البروتوكول 4، وهو مجموع أحادي متغير مباشر بزمن خطي يتجنب خطوة "هوية النطاق" الوسيطة الخاصة بـ DGM.

الآلية: يستفيد البروتوكول من ملاحظة أن تقييم كثير حدود أحادي المتغير عند جذور الوحدة يكافئ تقييم الامتداد متعدد الخطوط الخاص به عند نقاط محددة مشتقة من تلك الجذور.
- تحديداً: $f(w^i) = \text{mlin}[f](w^i, w^{2i}, \dots, w^{2^{m-1}i})$ .
العملية: يرسل المُثبت كثير حدود دوري $p_1(y)$ يمثل المجموع على نصف النطاق. ويتحقق المُتحقق من أن $p_1(1) + p_1(-1) = s$ . ومن ثم يتم تقليص الادعاء إلى مجموع أحادي المتغير أصغر يتضمن كثيرات حدود يتم تقييمها عند $r_1 w^i, w^{2i}, \dots$ .
الكفاءة: يكرر هذا البروتوكول جوهرياً كفاءة بروتوكول المجموع متعدد المتغيرات القياسي، ولكنه يعمل مباشرة على النطاق أحادي المتغير دون أي تكلفة إضافية للترجمة بين القواعد.

د. تقليل الجولات (الأقسام 3.3 و4.3)

توضح الورقة كيفية تقليل عدد جولات التفاعل من $m$ إلى $\log(m)$ أو حتى $O(\sqrt{m})$ .

الاستراتيجية: يمكن "إيقاف" البروتوكولات مبكراً بعد $k$ من الجولات. ثم يتم التعامل مع الادعاء أحادي المتغير الأصغر المتبقي باستخدام بروتوكول ذي جولة واحدة مثل Aurora.
الميزة: على عكس الأعمال السابقة (مثل HybridPlonk)، لا يتطلب هذا النهج مراحل ترجمة قواعد مكلفة (التحويل بين صيغ المعاملات وصيغ التقييم) لأن الخريطة بين مكعب هيبر (hypercube) البولياني وجذور الوحدة تظل محفوظة طبيعياً.

3. المساهمات الرئيسية

مجموع أحادي المتغير بزمن خطي: توفر الورقة أول بروتوكولات ملموسة وخطية الزمن للمجموع أحادي المتغير (البروتوكول 2 والبروتوكول 4) والتي تتوافق مع أنظمة SNARK أحادية المتغير.
تصحيح DGM: تحدد الورقة رسمياً وتصلح العيوب في بروتوكول DGM، وتوضح علاقته بموائم Gemini.
البروتوكول 4 (التقليل المباشر): تقدم بروتوكولاً جديداً وعالي الكفاءة يقلل المجموع أحادي المتغير مباشرة إلى التقييم متعدد المتغيرات دون خطوات وسيطة لـ "هوية النطاق"، متفوقاً على كل من DGM المصحح والنهج المعتمد على الموائمات.
تقليل الجولات بدون تكلفة إضافية: تثبت أن هذه البروتوكولات تدعم تقليل الجولات (إلى $\log m$ أو $\sqrt{m}$ ) دون عبء ترجمة القواعد، مما يجعلها متفوقة على HybridPlonk في حالات معينة.
تحليل شامل: تقدم مقارنة تفصيلية لزمن المُثبت، وزمن المُتحقق، وتكاليف الاتصال، وتعقيد الجولات في الجدول 2، مما يظهر أن البروتوكولات الجديدة تسمح للأنظمة أحادية المتغير بتحقيق كفاءة المُثبت التي كانت محصورة سابقاً في الأنظمة متعددة المتغيرات.

4. النتائج والأداء

تقدم الورقة تحليلاً مقارناً (الجدول 2) لمختلف الإعدادات:

زمن المُثبت: تحقق البروتوكولات المقترحة (تحديداً البروتوكول 4 + Gemini) زمناً خطياً للمُثبت $O(d^2 2^m)$ ، مما يطابق كفاءة المجموع متعدد المتغيرات القياسي. وهذا يمثل تحسناً كبيراً عن الزمن شبه الخطي للموائمات أحادية المتغير السابقة.
الاتصال: يرسل البروتوكول 4 عدد $O(dm) $من عناصر الحقل و$ O(m)$ من الأوراكلز. ورغم أنه أعلى قليلاً من بروتوكول Aurora ذي الجولة الواحدة، إلا أنه منافس للنهج متعدد المتغيرات.
الجولات:
- التنفيذ القياسي: $m$ من الجولات.
- مع تقليل الجولات: يمكن تقليصها إلى $\log(m)$ من الجولات (باستخدام Aurora للجزء المتبقي) أو $O(\sqrt{m})$ (باستخدام خريطة كرونيكر عكسية معممة).
تعقيد المُتحقق: يظل منخفضاً، وعادة ما يكون $O(m)$ أو $O(\log m)$ اعتماداً على استراتيجية تقليل الجولات.

5. الأهمية

هذا العمل مهم لمستقبل بناء SNARK لأنه يزيل المقايضة بين كفاءة المُثبت وكفاءة الجولات في الأنظمة أحادية المتغير.

التوحيد: يسمح للأنظمة القائمة على أحادي المتغير (التي غالباً ما تُفضل لبساطتها وتحققها في جولة واحدة) باستخدام تقنيات المجموع متعدد المتغيرات عالية الكفاءة دون تحمل التكاليف الباهظة لترجمة القواعد.
الواقعية: من خلال إصلاح بروتوكول DGM وتقديم البروتوكول 4، توفر الورقة حلولاً قابلة للتنفيذ وفعالة للمطورين الذين يبنون الجيل القادم من zk-SNARKs.
المرونة: القدرة على ضبط عدد الجولات (من خطي إلى لوغاريتمي إلى جذر تربيعي) دون التضحية بسرعة المُثبت تمنح مصممي الأنظمة درجات جديدة من الحرية لتحسين الأداء وفقاً لمتطلبات الأجهزة أو قيود الشبكة.

باختصار، تثبت الورقة أن المجموع أحادي المتغير بزمن خطي هو أمر ممكن بشكل عام من خلال الجمع بين الاختزالات والموائمات المناسبة، مما يجلب "أفضل ما في العالمين" (كفاءة متعدد المتغيرات وسلاسة جولات أحادي المتغير) إلى مشهد الـ SNARK.