💻 computer science

Automating Bitvector and Finite Field Equivalence Proofs in Lean

تقدم هذه الورقة BitModEq، وهي تكتيك جديد في Lean يعمل على أتمتة براهين التكافؤ بين المتجهات الثنائية (bitvectors) والحقول المحدودة (finite fields) باستخدام ليمات النطاق وتحليل الحالات، متفوقاً بذلك على أدوات حل مشكلات التقييد (SMT solvers) الحديثة في التحقق من ترميزات دوائر براهين المعرفة الصفرية.

المؤلفون الأصليون: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

نُشر 2026-05-15

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

CC BY 4.0

المؤلفون الأصليون: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

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

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

الصورة الكبيرة: لغتان مختلفتان للرياضيات

تخ تخيل أنك تحاول التحقق مما إذا كانت وصفة سرية (برهان المعرفة الصفرية - Zero-Knowledge Proof) تعمل بشكل صحيح. المشكلة هي أن الوصفة مكتوبة بلغتين مختلفتين لا يمتزجان جيدًا:

الحقول المحدودة (Finite Fields): فكر في هذا كعالم "حساب الساعة". إذا كان لديك ساعة بـ 17 ساعة، فإن جمع 10 و10 لا يعطيك 20؛ بل يعطيك 3 (لأن الرقم يعود للبداية/يدور). هذه هي الطريقة التي تعمل بها العديد من الأنظمة التشفيرية الحديثة (مثل تلك المستخدمة في العملات الرقمية).
المتجهات الثنائية (Bitvectors): فكر في هذا كـ "حساب الكمبيوتر". الحواسيب لا تدور مثل الساعات؛ بل لديها ببساطة عدد محدد من المفاتيح (البتات - bits) التي تكون إما "تشغيل" أو "إيقاف". إذا أضفت أرقامًا ونفدت المفاتيح، يتم قطع الأجزاء الزائدة ببساطة.

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

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

الحل: المترجم "BitModEq"

بنى المؤلفون أداة جديدة تسمى BitModEq داخل نظام يسمى Lean (وهو يشبه معلم رياضيات صارم جدًا يدقق في كل خطوة من خطوات البرهان).

فكر في BitModEq كمترجم متخصص لا يكتفي فقط باستبدال الكلمات؛ بل يفهم المنطق الكامن وراء الكلمات. إنه يستخدم عملية من ثلاث خطوات لإثبات أن وصفة "حساب الساعة" هي تمامًا نفس وصفة "حساب الكمبيوتر":

الخطوة 1: "فك اللف" (الترجمة)

تأخذ الأداة "حساب الساعة" (الحقول المحدودة) وتحاول "فك لفها" إلى أرقام عادية (الأعداد الطبيعية).

التحدي: في حساب الساعة، $5 - 10$ قد يكون رقمًا موجبًا بسبب عملية الدوران. في الرياضيات العادية، هو رقم سالب.
الحيلة: تنظر الأداة إلى الأرقام وتسأل: "هل من الممكن أن يدور هذا الرقم؟" إذا كانت الأرقام صغيرة بما يكفي (مثل بتات الكمبيوتر)، فهي تعرف أن الدوران لن يحدث. تقوم بإزالة قواعد "الساعة" بأمان وتعاملها كرياضيات عادية. وإذا لم تكن متأكدة، فإنها تحتفظ بقواعد "الساعة" ولكنها تضيف فحص سلامة.

الخطوة 2: "شبكة الأمان" (تحليل النطاق)

هذا هو السر الذي يميز هذه الورقة البحثية. قبل أن تحاول الأداة تحويل الرياضيات إلى بتات كمبيوتر، تقوم بإجراء "تحليل نطاق" (Range Analysis).

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

الخطوة 3: "تفكيك البتات" (البرهان النهائي)

بمجرد أن تقوم الأداة بتبسيط المشكلة إلى "رياضيات كمبيوتر" بحتة (بتات)، تستخدم تقنية تسمى "تفكيك البتات" (Bit-blasting).

التشبيه: هذا يشبه أخذ قفل معقد ومحاولة تجربة كل تركيبة مفاتيح ممكنة حتى تجد المفتاح الذي يفتحه.
نظرًا لأن الأداة قامت بتبسيط المشكلة في الخطوة 2، أصبح "القفل" الآن صغيرًا بما يكفي ليقوم الكمبيوتر بتجربة كل التراكيب فورًا وإثبات صحة الرياضيات.

لماذا يهم هذا الأمر (النتائج)

اختبر المؤلفون أداتهم على أنظمة تشفيرية حقيقية (تحديدًا Jolt و CirC).

المنافسة: قارنوا أداتهم مع أفضل برامج الحل التلقائية الموجودة (مثل cvc5).
النتيجة: غالبًا ما تعثرت البرامج الموجودة أو استغرقت وقتًا طويلاً (Time out) عندما تصبح المشكلات كبيرة (مثل الأرقام ذات 32 بت). كانت مثل مدقق إملائي يحاول قراءة قاموس.
فوز BitModEq: حلت الأداة الجديدة 19% أكثر من المشكلات مقارنة بأفضل الأدوات الموجودة. واستطاعت التعامل مع أرقام أكبر بكثير (تصل إلى 32 بت) حيث فشلت الأدوات الأخرى.
ميزة إضافية: نظرًا لأنها تعمل داخل نظام Lean، فإن البرهان مدقق بواسطة النواة (Kernel-checked). وهذا يعني أن الكمبيوتر لم يتكهن فحسب؛ بل اتبع مجموعة صارمة من القواعد المنطقية المضمونة الصحة، مما يقلل من خطر وجود أخطاء خفية.

اكتشاف من العالم الحقيقي

خلال اختباراتهم، اكتشفت الأداة بالفعل خطأً (Bug) في مترجم (Compiler) الخاص بـ CirC. كان لدى المترجم خطأ في كيفية التعامل مع الأرقام الكبيرة (تحديدًا إزاحة اليمين بمقدار 32 بت). لم يظهر الخطأ إلا مع الأرقام الكبيرة، ولهذا السبب فاتته الاختبارات السابقة ذات النطاق الأصغر. وقام المطورون بإصلاح الخطأ بعد أن أبلغ عنه المؤلفون.

الملخص

تقدم الورقة البحثية طريقة جديدة للتحقق تلقائيًا من أن رياضيات التشفير تعمل بشكل صحيح. بدلًا من المعاناة لترجمة "حساب الساعة" إلى "حساب الكمبيوتر" يدويًا أو باستخدام أدوات بدائية، بنوا مترجمًا ذكيًا يقوم بـ:

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

هذا يجعل التحقق من الأنظمة الأمنية المعقدة أسرع، وأكثر موثوقية، وقادرًا على اكتشاف الأخطاء التي تفوتها الأدوات الأخرى.

ملخص تقني: أتمتة إثبات التكافؤ بين المتجهات البتية والحقول المنتهية في Lean

بيان المشكلة

تواجه عملية التحقق من ترميزات دوائر إثبات المعرفة الصفرية (ZKP) تحديًا حرجًا: وهو إثبات صحة العبارات الخالية من المكممات (quantifier-free) التي تستخدم في آن واحد عمليات المتجهات البتية (حساب الآلة القياسي بمقياس $2^N$ ) وعمليات الحقول المنتهية (الحساب بمقياس عدد أولي كبير $P$ ). غالبًا ما تتطلب أنظمة ZKP "أرثمتة" (arithmetizations) تقوم بترميز منطق المتجهات البتية كمتعددات حدود للحقول المنتهية. ويعد ضمان صحة هذه الترميزات أمرًا حيويًا لسلامة أنظمة ZKP، ومع ذلك فإن بناءها عرضة للخطأ.

تعاني سير عمل التحقق الحالية من قصورين أساسيين:

التحقق اليدوي: يوفر دمج أنظمة ZKP الكاملة في أدوات الإثبات التفاعلية (ITPs) مثل Lean ضمانات قوية، ولكنه يتطلب جهدًا بشريًا هائلًا. ومع تطور تحسينات ZKP بسرعة، غالبًا ما تتطلب هذه البراهيد اليدوية إعادة عمل كبيرة.
التحقق عبر SMT الآلي: يوفر تقليل التحقق إلى استعلامات نظرية التشبع (Satisfiability Modulo Theories - SMT) قدرة أكبر على الأتمتة، ولكنه يعاني من مشكلتين جوهريتين:
- تحويل النظريات: تفتقر أدوات حل SMT إلى الدعم الأصيل للتحويل بين الحقول المنتهية والمتجهات البتية. وتؤدي الحلول البديلة مثل "تقسيم البتات" (bit-splitting) إلى إدخال متغيرات مفرطة، كما تتطلب فحوصات النطاق متعددات حدود معقدة تؤدي إلى تدهور أداء الحلّال (solver).
- قاعدة الكود الموثوقة (TCB): تمتلك أدوات حل SMT قاعدة TCB أكبر بكثير من أدوات ITP، مما يزيد من خطر الثغرات البرمجية.

المنهجية

يقدم المؤلفون BitModEq، وهو "تكتيك" (tactic) مبتكر في Lean مصمم لإثبات التكافؤ تلقائيًا بين ترميزات الحقول المنتهية ودلالاتها المقابلة في المتجهات البتية. يستفيد هذا النهج من الدلالات الغنية لأدوات ITP لإجراء تحويلات مباشرة بين الأنواع مع الاحتفاظ بأتمتة حل SMT من خلال سير عمل متخصص.

سير العمل الأساسي

يعمل BitModEq في أربع مراحل متميزة (كما هو موضح في الشكل 1 من الورقة البحثية):

التحويل من الحقل المنتهي إلى العدد الطبيعي: يتم تحويل جميع الحدود من النوع الحقل المنتهي ( $FP$ ) إلى أعداد طبيعية ( $N$ ). يتضمن ذلك دفع معاملات التحويل (مثل toNat) للداخل عبر التعبيرات الحسابية.
تحليل النطاق: يتم تفريغ عدم المساواة فوق الأعداد الطبيعية الناتجة أثناء التحويل باستخدام خوارزمية تحليل نطاق مخصصة.
التحويل من العدد الطبيعي إلى المتجه البتي: يتم تحويل حدود الأعداد الطبيعية المتبقية إلى متجهات بتية ( $BV_N$ ).
تفكيك البتات (Bit-Blasting): يتم تفريغ أهداف تساوي المتجهات البتية النهائية باستخدام bv_decide، وهو إجراء قرار لتفكيك البتات مطبق في Lean.

المكونات التقنية الرئيسية

1. حساب الترجمة (الأقسام 4.2)
يستخدم التكتيك مجموعة من قواعد الترجمة للانتقال بين المجالات:

$FP \to N$ : توزع قواعد مثل distNat عملية toNat على الجمع والضرب. ومن الضروري أن يميز التكتيك بين الحالات التي يمكن فيها استبعاد تجاوز الدور (wraparound) (مما يسمح بالطرح البسيط) والحالات التي لا يمكن فيها ذلك (مما يتطلب إضافة المقياس $P$ متبوعًا بعملية المقياس/modulo). وتكتشف قواعد sqrBds ترميزات البتات (حيث $x^2 = x$ ) وترجمها إلى حدود ( $x \le 1$ ).
$N \to BV$ : توزع قواعد مثل distBV عملية toBV على العمليات. وعلى عكس خطوة $FP \to N$ ، لا تتطلب هذه القواعد إضافة عامل المقياس لأن الفضاء المستهدف هو بطبيعته بمقياس $2^N$ .

2. تحليل النطاق (القسم 4.3)
غالبًا ما تفشل تكتيكات Lean القياسية (مثل omega أو linarith) في أرثمتة ZKP بسبب المعاملات الكبيرة وتبعية المتغيرات المعقدة. يقدم BitModEq حساب تحليل نطاق مخصص وموجه نحو بناء الجمل (syntax-directed):

متغيرات نائبة (Placeholder Variables): تُدخل الخوارزمية متغيرات نائبة وجودية لتفكيك عدم المساواة المعقدة.
التفكيك والإزالة: تفكك القواعد عدم المساواة (على سبيل المثال، $a + b \le w$ تصبح $a \le w_1, b \le w_2, w_1+w_2 \le w$ ) وتزيل المتغيرات النائبة عن طريق استبدالها بحدود مستمدة من الفرضيات أو الخصائص المعروفة (مثل كون عناصر الحقل المنتهي محصورة بـ $P-1$ ).
معالجة التبعية: تقوم قواعد متخصصة (ineqCases, ineqXOR) بإجراء تحليل حالات مستهدف للمتغيرات التي تحاكي البتات (0 أو 1) لحل التبعيات التي تغفل عنها أدوات الحساب القياسية.

3. التنفيذ
تم تنفيذ التكتيك في الإصدار 4.23.0 من Lean، باستخدام mathlib للنماذج (lemmas) و bv_decide لخطوة تفكيك البتات النهائية. ويعتمد على نواة (kernel) Lean للتحقق من البراهيد، مما يضمن قاعدة TCB دنيا.

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

تكتيك BitModEq: تكتيك في Lean يترجم عمليات الحقول المنتهية إلى متجهات بتية ويحل الأهداف الناتجة عبر تفكيك البتات، مع الحفاظ على ضمانات الصحة التي توفرها أدوات ITP.
التحقق المحدود لترميزات العالم الحقيقي: إثبات مفهوم للتحقق من نظامي ZKP حقيقيين (Jolt و CirC) يحقق حدود عرض بتات أعلى من التقنيات السابقة.
تحليل نطاق متخصص: تكتيك جديد في Lean لإثبات الأهداف الناتجة عن الترجمة، مصمم خصيصًا للتعامل مع تبعيات المتغيرات وقيود عدم المساواة الشائعة في أرثمتة ZKP.

النتائج والتقييم

قام المؤلفون بتقييم BitModEq مقابل أحدث أدوات حل SMT (تحديدًا cvc5 مع قواعد Gröbner كاملة ومنقسمة) على اختبارات مستخرجة من Jolt (zkVM) و CirC (مترجم zkVM).

الأداء: حل BitModEq 19% أكثر من الاختبارات مقارنة بأفضل تكوينات SMT أداءً.
- في اختبارات Jolt (جداول البحث بعرض 8 بت و 32 بت)، حل BitModEq 3 حالات إضافية من فئة 8 بت و 7 حالات إضافية من فئة 32 بت مقارنة بـ cvc5 (الترميز الضعيف).
- في اختبارات CirC، حل BitModEq حالات أكثر لـ 13 حالة من أصل 17 عرض بت تم اختباره.
القابلية للتوسع: بينما كان cvc5 أفضل أداءً في عروض البتات الصغيرة، إلا أن أداءه تدهور بشكل كبير مع زيادة عرض البتات بسبب انفجار المتغيرات الناتج عن تقسيم البتات. توسع BitModEq بفعالية حتى مدخلات 32 بت.
الكفاءة: أظهرت دراسة الاستئصال (ablation study) أن تحليل النطاق المخصص أمر بالغ الأهمية؛ حيث أدى إزالة تقسيم الحالات إلى تقليل عدد الاختبارات التي تم حلها بشكل كبير (من 737 إلى 720 في CirC، ومن 24 إلى 21 في Jolt). كما أدى استبدال التحليل المخصص بالتكتيكات القياسية لـ Lean (مثل ring_nf و linarith إلخ) إلى انخفاض حاد في الحالات التي تم حلها (434 مقابل 737 في CirC).
وقت التشغيل: يستحوذ تحليل النطاق على حوالي 52% من إجمالي وقت التشغيل، يليه الترجمة (23%) ثم تفكيك البتات (21%).
اكتشاف الأخطاء: أثناء تقييم CirC، حدد المؤلفون خطأً في سلامة (soundness bug) تنفيذ الإزاحة الحسابية لليمين بعرض 32 بت المتعلق بتجاوز العدد الصحيح (integer overflow)، وهو ما لم يتم اكتشافه في عروض البتات الأصغر.

الأهمية والادعاءات

تدعي الورقة أن BitModEq يعالج القيود المحددة لسير عمل التحقق من ZKP الحالية من خلال الجمع بين سلامة أدوات ITP والاستدلال المؤتمت. ومن خلال ترجمة قيود الحقول المنتهية إلى متجهات بتية، يتجنب النهج اختناقات الأداء الناتجة عن تحويل نظريات SMT وقاعدة TCB الكبيرة لأدوات SMT.

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