A Complexity-Theoretic Approach to Proofs of Space

عملية سطو كبرى على التخزين الرقمي

تخيل عالماً يمكنك فيه إثبات ملكيتك لمكتبة ضخمة من الكتب دون أن تضطر لإظهار صفحة واحدة منها. هذا هو جوهر "إثباتات المساحة" (Proofs of Space)، وهو مفهوم في مجال التشفير وعلوم الحاسوب. الأمر يشبه مالك عقار رقمي يريد التأكد من أن المستأجر لديه بالفعل مستودع مليء بالأثاث، وليس مجرد رسم ذكي للأثاث. يحتاج المالك (المُتحقِّق - Verifier) إلى التأكد من أن المستأجر (المُثبِت - Prover) يستخدم كمية هائلة من الذاكرة المستمرة لتخزين البيانات، بدلاً من مجرد الاحتفاظ بملاحظة صغيرة تقول "لدي الأثاث" ثم استحضره سحرياً فقط عندما يُطلب منه ذلك.

لسنوات، كانت الطريقة الوحيدة لبناء هذه المستودعات الرقمية تعتمد على أداة خيالية سحرية تسمى "الأوراكل العشوائي" (Random Oracle). فكر في هذا كصندوق أسود سحري يخرج إجابات عشوائية تماماً وغير متوقعة في كل مرة تسأل فيها. ورغم فائدته من الناحية النظرية، إلا أنه يشبه بناء منزل على أساس من السحر الخالص؛ فنحن لا نعرف ما إذا كان سيصمد في العالم الحقيقي. كان السؤال الكبير للعلماء هو: هل يمكننا بناء "إثبات مساحة" آمن باستخدام القوانين الفيزيائية الحقيقية للحوسبة فقط، دون الاعتماد على صناديق سحرية؟ تغوص هذه الورقة البحثية في ذلك السؤال تحديداً، باستخدام أدوات نظرية التعقيد (Complexity Theory) — وهي دراسة مدى صعوبة حل المسائل — لمعرفة ما إذا كان بإمكاننا بناء هذه الإثباتات من الصفر.

الفكرة الكبرى للورقة: السلسلة "العميقة"

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

لفهم حيلتهما، تخيل أنك بحاجة لإثبات امتلاكك لكومة ضخمة وفوضوية من الرمل (البيانات). الطريقة القديمة كانت تتطلب صندوقاً سحرياً لضمان عدم إمكانية ضغط الرمل. أدرك المؤلفان أنه في العالم الحقيقي، لسنا بحاجة لأن يكون ضغط الرمل "مستحيلاً"؛ بل نحتاج فقط لأن يكون صعب الضغط بسرعة.

لقد قدما مفهوماً يسمى العمق الحسابي (Computational Depth). فكر في سلسلة البيانات كسلسة من القصص:

1. الإعداد: يأخذ المُثبِت بذرة صغيرة (ملخص قصة قصيرة) ويقضي وقتاً طويلاً (المرحلة الأولى) لتوسيعها إلى رواية ضخمة ومفصلة (البيانات).
2. الفخ: يقوم المُتحقِّق بعد ذلك بطلب صفحات محددة من تلك الرواية.
3. المصيدة: إذا لم يقم المُثبِت بكتابة الرواية بأكملها واكتفى بالاحتفاظ بالملخص القصير فقط، فسيتعين عليه إعادة كتابة الصفحات من الصفر. لكن المُتحقِّق يمنحه وقتاً ضئيلاً جداً (المرحلة الثانية) للقيام بذلك.

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

كيف يعمل الإثبات: "شجرة ميركل" و"التعويذة السحرية"

توضح الورقة بروتوكولاً يتكون من خطوتين لاختبار هذا "العمق".

المرحلة 1: الإعداد (الانتظار الطويل)
يرسل المُتحقِّق بذرة عشوائية إلى المُثبِت. يقضي المُثبِت وقتاً طويلاً (لنفترض ساعات) باستخدام دالته "العميقة" الخاصة لتحويل تلك البذرة إلى ملف ضخم من البيانات. ثم يبني شجرة ميركل (Merkle Tree) فوق هذه البيانات. تخيل شجرة ميركل كبصمة رقمية للملف بأكمله. إنها تشبه شجرة العائلة حيث كل ورقة هي قطعة من البيانات، وكل فرع هو "هاش" (بصمة رقمية فريدة) للفرعين اللذين يقعان تحتها. وفي أعلى الشجرة يوجد "جذر" (Root) واحد يمثل الملف بأكمله. يقوم المُثبِت بتخزين هذا الملف الضخم وهذا الجذر.

المرحلة 2: الفحص (الاختبار السريع)
يسأل المُتحقِّق فجأة عن صفحات محددة من الملف (مواقع عشوائية). يجب على المُثبِت تقديم تلك الصفحات بسرعة مع "المسار" عبر شجرة ميركل الذي يثبت أن تلك الصفحات تنتمي إلى الملف الأصلي.

هنا تبرز براعة المؤلفين. لمنع المُثبِت من محاولة التحايل على البروتوكول (عبر الاحتفاظ بالبذرة القصيرة فقط ومحاولة تخمين الصفحات)، يضيفون حجة موجزة (Succinct Argument) (إثبات قصير).

• الخيار (أ) (الافتراض الأقوى): يستخدمون "SNARG" (إثبات قصير غير تفاعلي) لإثبات أن جذر الهاش الذي أرسلوه جاء بالفعل من الملف الناتج عن البذرة. يتطلب هذا افتراضاً قوياً بوجود أدوات تشفير معينة، لكنه يحافظ على انخفاض تكلفة التخزين الإضافية.
• الخيار (ب) (الافتراض الأضعف): يستخدمون حجة من نوع "كيلين" (Kilian-style) تعتمد على دالات الهاش مقاومة التصادم. هذا افتراض أكثر معيارية و"أماناً"، لكنه يجبر المُثبِت النزيه على تخزين المزيد من البيانات (سلسلة PCP) لإثبات أن شجرة ميركل بُنيت بشكل صحيح.

ما الذي ينفونه وما الذي يثبتونه

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

كما يتناولون نوعاً معيناً من محاولات التحايل على البروتوكول: ماذا لو قام المُثبِت بتخزين كمية ضئيلة من البيانات وحاول "ضغط" الملف الكبير أثناء التشغيل؟ يثبت المؤلفون أنه إذا تمكن المُثبِت من إقناع المُتحقِّق بقبول الإثبات، فيجب أن يكون قد خزن كمية كبيرة من البيانات. وتحديداً، يظهرون أن المُثبِت الذي يحاول التحايل على البروتوكول لا يمكنه تخزين أقل بكثير من المُثبِت النزيه (على سبيل المثال، إذا كان المُثبِت النزيه يخزن $N$ من البتات، فإن المُثبِت الذي يحاول التحايل لا يمكنه الهروب بتخزين أقل بكثير من $N$ بت، اعتماداً على البناء المحدد المستخدم).

الخلاصة

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

لقد أظهروا أن:

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

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