يتم اشتقاق STARK غير التفاعلي من دليل Oracle التفاعلي (IOP)، والذي تم تجميعه في دليل غير تفاعلي في نموذج أوراكل العشوائي.
تشرح هذه المقالة آخر التحديثات لوثائق ethSTARK وتوفر تحليلاً شاملاً ومفصلاً لأمان بروتوكول ethSTARK في نموذج أوراكل العشوائي.
شرح تفصيلي لأمن STARK
يعد نظام إثبات STARK، أو حجة المعرفة الشفافة القابلة للتطوير، أداة قوية للسلامة الحسابية: فهو يسمح بالتحقق غير الموثوق من صحة الحسابات التي يتم إجراؤها على البيانات العامة. في هذه المقالة، سوف نتعمق في الأمان الذي توفره إثباتات STARK، ونحددها، ونستكشف تقنيات إثبات أمان المخططات.
(اقرأ القسم 6 من وثائق ethSTARK (الإصدار 1.2) للحصول على التفاصيل، بالإضافة إلى العمل المستقل المهم والشامل حول هذا الموضوع بواسطة Block et al.).
ما الذي نحاول تحقيقه من خلال التحليلات الأمنية؟ نريد منع "الهجمات الناجحة" على نظام STARK بسبب بيان كاذب وإثبات STARK الذي قبله مدقق STARK ردًا على هذا البيان (الزائف). نظرًا لأن التحريفات خطيرة ويمكن أن تأتي بجميع الأحجام والأشكال، فإننا نريد أن نكون آمنين ضدها جميعًا. أي عبارة خاطئة، حتى لو كانت تافهة مثل 1+1=3، عند دمجها مع دليل STARK المقبول من قبل مدقق STARK، سيتم اعتبارها هجومًا ناجحًا على النظام. (أولئك الذين لديهم خلفية في التشفير قد يكونون مهتمين بمعرفة أن STARK يمكنه أيضًا تلبية مفاهيم أمنية أقوى مثل موثوقية المعرفة، ولكن من أجل البساطة، ستركز هذه المقالة على حالات بسيطة حول الموثوقية).
كيف يمكننا تحديد أمان نظام STARK بشكل رسمي؟ نحدد ذلك من خلال تحليل "خطأ الموثوقية". يقيس "خطأ الموثوقية" تقريبًا "التكلفة" المتوقعة التي سيكلفها المهاجم لشن هجوم ناجح (على سبيل المثال، العثور على دليل STARK لبيان كاذب، ولكن يتم قبول الدليل من قبل مدقق STARK). من الناحية الرياضية، خطأ الموثوقية هو دالة (t) مدخلاتها هي المعلمة الزمنية t، التي تمثل الوقت الحسابي الذي يرغب المهاجم في إنفاقه لشن هجوم، والإخراج هو احتمال نجاح هجوم المهاجم (وجد في الأقوال الكاذبة دليل مقنع). كلما زادت "التكلفة" التي يرغب المهاجم في إنفاقها، زادت احتمالية نجاحه.
لقد قمنا حتى الآن بتعريف أمان STARK كوظيفة (t)، والتي تختلف عن الطريقة التي يناقش بها الجميع الأمان على تويتر المشفر كل يوم. على تويتر، قد تسمع شيئًا كهذا: "يحتوي هذا الحل على 96 بتًا من الأمان". كيف يترجم هذا إلى تعريفنا للأمن؟ لا توجد إجابة واحدة لهذا السؤال، حيث يفهم الناس "x بتات الأمان" بشكل مختلف قليلاً:
بتفسير دقيق، هذا يعني أنه بالنسبة لأي t بين 1 و2⁹⁶، فإن خطأ الموثوقية هو (t) 2⁹⁶. المهاجم الذي يبلغ وقت تشغيله 2⁹⁶ أو أقل لديه احتمالية ضئيلة جدًا للنجاح، أقل من 2⁹⁶، وهو أقل من 1 في المليار مرة 1 في المليار.
التفسير الأكثر مرونة، وربما الأكثر شيوعًا، هو أن أمان 96 بت يعني أنه بالنسبة لأي t، هناك موقف حيث t/(t) 2⁹⁶. وهذا يعني أن احتمال النجاح يكون خطيًا (عكسيًا) مع وقت التشغيل. إذا كان لدى المهاجم وقت تشغيل يبلغ 2⁸⁶، فإن احتمالية نجاحه تكون على الأكثر 2¹⁰.
وفي هذه المقالة سنناقش الخيار الثاني.
من IOP إلى STARK بأمان 96 بت
إذن، كيف نثبت أن الحل يحتوي على 96 بت من الأمان؟ للإجابة على هذا السؤال، نحتاج إلى فهم البنية عالية المستوى التي تم بناء ستارك عليها. يتكون STARK من ثلاثة أجزاء رئيسية: IOP (دليل Oracle التفاعلي)، وشجرة Merkle، وتجزئة Fiat-Shamir؛ وتركيزنا الرئيسي هو IOP. بمجرد تحديد هذه الأجزاء المكونة، يمكننا تجميعها لإنشاء STARK. سنتناول هذه المكونات بالتفصيل، بما في ذلك ماهيتها وكيفية تناسبها معًا.
المكون الأول الذي سنراجعه هو IOP: يشبه IOP الدليل التفاعلي القياسي، حيث يتفاعل المثبت والمدقق في جولات متعددة (نقتصر على بروتوكولات العملة العامة، حيث يرسل المدقق تحديات عشوائية فقط إلى المثبت). في عملية IOP، لا يقرأ المدقق رسالة المثبت بشكل كامل، ولكنه بدلاً من ذلك يأخذ عينات من جزء صغير من البتات من رسالة كل محقق. هذا هو السبب في أن STARK الذي تم تجميعه لاحقًا يحقق البساطة.
بالنظر إلى IOP، كيف يمكنني بناء STARK منه؟ يمكن أن تكون رسائل المُثبت طويلة جدًا (في الواقع، تكون أطول من الحساب نفسه). لضغط هذه المعلومات نستخدم أشجار ميركل. شجرة Merkle هي شجرة تجزئة ثنائية حيث تمثل كل عقدة طرفية استعلامًا أو ردًا في IOP. الجذور هي وعد الرسالة بأكملها. عندما يريد المدقق قراءة موقع معين في رسالة، يوفر المثبت قيمة ذلك الموقع ومسار التحقق. يمكن للمدقق بعد ذلك استخدام هذا المسار للتحقق من صحة القيمة. يقرأ مدقق IOP كمية صغيرة فقط من معلومات الموقع من معلومات المثبت. لذلك، يمكن تنفيذ البروتوكولات المختصرة (البروتوكولات ذات حجم الاتصال المنخفض) باستخدام أشجار Merkle.
جولات الضغط
يمكننا اختيار STARK التفاعلي، ولكن لتبسيط عملية إنشاء STARK، نختار عادةً STARK غير التفاعلي، بحيث لا يحتاج المدقق إلى انتظار معلومات خارجية عند بناء STARK. في الواقع، هذه هي الطريقة التي يتم بها نشر جميع أنظمة STARK الحالية وكيفية بناء بروتوكول ethSTARK. تعد STARKs غير التفاعلية أيضًا حالة خاصة من SNARKs الشفافة (الشفافة تعني عدم الحاجة إلى إعداد موثوق لإنشاء مثيل لها؛ "بروتوكول Arthur Merlin" أو "Public Coin IOP"). وللقيام بذلك، تتمثل الخطوة الأخيرة في تطبيق خوارزمية فيات شامير لضغط جولات متعددة من التفاعلات في رسالة واحدة، وهو ما نسميه برهان ستارك. تحويل فيات-شمير هو طريقة لتحويل بروتوكول تفاعلي إلى بروتوكول غير تفاعلي. يحاكي المثل بروتوكولًا تفاعليًا أثناء التحدث إلى وظيفة التجزئة. لاشتقاق التحدي العشوائي للجولة i، يقوم المُمثل بتجزئة السجل الجزئي للجولة i ويفسر الناتج على أنه التحدي التالي.
وهذا يضمن عدم قدرة المُثبت على تغيير إجابته بعد إنشاء التحدي. ومع ذلك، فإن مُثبت الغش لديه بعض الطرق الإستراتيجية الجديدة التي لا تتوفر في عمليات IOP التفاعلية. يستطيع المُثبِّت إعادة إنشاء تحدي المدقق عن طريق تعديل معلومات المُثبِّت الأخير، بحيث يحصل على سجل جديد وبالتالي تحدي جديد. وتبين أن مفهوم الموثوقية القياسي لـ IOP غير كافٍ لإثبات سلامة تحويل فيات-شمير.
على سبيل المثال، احصل على IOP مكون من 96 جولة وأضف الاختراق التالي إلى المدقق: إذا كان البت الأول من عشوائية المدقق هو 0 في كل جولة من الجولات الـ 96، فسيقبله المدقق (دون رؤية أي دليل). يمكننا أن نرى أن إضافة هذا الاختراق إلى المدقق يضيف فقط مصطلح 2⁹⁶ إلى خطأ موثوقية IOP. ومع ذلك، بعد تحويل فيات-شمير، يمكن للمهاجم تعديل معلومات المثبت بسهولة للتأكد من أن كل قيمة تجزئة تبدأ بالصفر، وبالتالي اقتحام النظام في وقت قصير جدًا. كن مطمئنًا، هذا السيناريو الرهيب هو مجرد مثال نظري ولا ينطبق على صواريخ ستارك المنتشرة. لذلك، دعونا نلقي نظرة على سبب كون STARK الخاص بنا آمنًا بعد كل شيء. باختصار، سوف نبين أن المهاجم يركض بخطوات t على الأكثر، وأن احتمال نجاح الهجوم هو على الأكثر (t) t 2⁹⁶.
IOP والموثوقية الشاملة
يعتمد أمان STARK على IOP الأساسي الخاص به. ولكن ماذا يعني أن يكون لدى IOP 96 بت من الأمان؟ وفقًا للتعريف القياسي، فإن خطأ موثوقية IOP هو 2⁹⁶: وهذا يعني أن احتمال أن يتمكن أي مهاجم (بغض النظر عن وقت التشغيل) من خداع المدقق هو 2-96 على الأكثر. ومع ذلك، كما ناقشنا، فإن موثوقية IOP هي واحدة فقط من المكونات الثلاثة، وهو ما لا يكفي للحصول على 96 بت من الأمان من STARK المجمعة من الخطوات الثلاث جميعها. في المقابل، تم إثبات سلامة STARK المجمعة على افتراض أن STARK لديه خطأ موثوقية جولة تلو الأخرى يبلغ 96 بت (يتم استخدام تعريف مماثل يسمى موثوقية استرداد الحالة أحيانًا).
بشكل بديهي، تعني "سلامة الجولة تلو الأخرى" أن كل جولة تحتوي على 96 بت من الأمان، وليس فقط البروتوكول بأكمله. لكي نكون أكثر تحديدًا، تشير الموثوقية الدائرية إلى وجود مسند يمكنه الحصول على جزء من سجل البروتوكول وإخبارنا ما إذا كان هذا السجل "خادعًا": "السجل الفارغ" ليس "خادعًا"، و عندما يكون السجل الكامل "مخادعًا" فقط إذا تم قبوله من قبل المدقق. أخيرًا، بالنسبة لأي سجل جزئي لا "ينتحل" المدقق، فإن احتمال أن يصبح السجل "انتحالًا" في الجولة التالية هو 2⁹⁶ على الأكثر. إذا كان هناك مسند بهذه الخصائص، فإننا نقول أن البروتوكول يحتوي على 96 بت من الموثوقية الشاملة (لا يتطلب هذا المسند حسابًا فعالاً).
في كثير من الحالات، يقوم الأشخاص فقط بتحليل موثوقية IOP وليس موثوقيتها الشاملة. من المسلم به أنه من الصعب التفكير في مثال (باستثناء الأمثلة المصنعة) لـ IOP يتمتع بموثوقية قياسية ولكن ليس بموثوقية شاملة. ومع ذلك، عند استخلاص حدود أمان محددة، قد تنشأ اختلافات بين الاثنين، وكل بتة لها أهميتها. ولذلك، لاشتقاق حدود ضيقة ومحددة، من الضروري إجراء تحليل دقيق لموثوقية IOP الشاملة. وهذا هو بالضبط ما نفعله مع بروتوكول FRI وethSTARK IOP الذي يعتمد عليه STARK IOP. التحليل في حد ذاته أبعد ما يكون عن التافه ويخرج عن نطاق هذه المقالة. باستخدام التحليل الجديد، يمكننا تعيين معلمات دقيقة لإثباتنا.
إن الموثوقية الشاملة تمنحنا بالفعل الضمان الذي نحتاجه. يمكن للمُثبِّت إعادة إنشاء التحدي عدة مرات، ولكننا نعلم أنه في أي جولة، يكون احتمال إنشاء سجل احتيالي هو 2⁹⁶. لذلك، إذا كان لدى المُثبِّت t مرات (تُقاس بعدد مكالمات التجزئة)، فيمكنه المحاولة معظم t مرات للحصول على سجل خادع، مما يحد من احتمالية نجاحه إلى (t) t2⁹⁶.
إضافة كافة عناصر الخطأ
وأخيرا، لكي يصبح كل هذا صحيحا، يتعين علينا أن نتأكد من أن المثل لا يستطيع التلاعب بشجرة ميركل. يمكننا أن نبين أنه طالما لم يجد المُثبِّت أي تصادمات في دالة التجزئة، فلن يتمكن من الغش في شجرة ميركل. احتمالية عثور المهاجم على تصادم باستخدام استدعاءات t (دالة التجزئة العشوائية) هي على الأكثر t2/2، وهو طول إخراج دالة التجزئة (الناجمة عن "مفارقة عيد الميلاد"). ولهذا السبب نحتاج إلى تعيين دالة التجزئة الطول هو ضعف الأمان المطلوب، لذلك إذا كانت لدينا دالة تجزئة بطول إخراج يبلغ 192 وIOP بموثوقية جولة تلو الأخرى تبلغ 96 بت، فسنحصل على STARK مجمع موثوق به للخطأ الجنسي (t )=t2-⁹⁶ + t2 2¹⁹⁶. بما أن t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵، فإن هذا المخطط يحتوي على 95 بت من الجنس الآمن.
لخص
مجتمعة، يوفر STARK طريقة قوية للتحقق بشكل موثوق من صحة الحسابات التي يتم إجراؤها على البيانات العامة. يتم قياس أمان STARK عادةً من خلال "خطأ الموثوقية"، والذي يمثل احتمالية نجاح المهاجم في تقديم بيان كاذب وإقناع المدقق بالدليل. من أجل تحقيق مستوى الأمان المطلوب، مثل 96 بت، يجب أن يحقق IOP الأساسي موثوقية جولة تلو الأخرى لضمان الحفاظ على مستويات أمان عالية في كل جولة. لقد قمنا بتحليل الموثوقية الشاملة لعمليات IOP التي يعتمد عليها STARK الخاص بنا لاشتقاق حدود أمان محددة.
شاهد النسخة الأصلية
قد تحتوي هذه الصفحة على محتوى من جهات خارجية، يتم تقديمه لأغراض إعلامية فقط (وليس كإقرارات/ضمانات)، ولا ينبغي اعتباره موافقة على آرائه من قبل Gate، ولا بمثابة نصيحة مالية أو مهنية. انظر إلى إخلاء المسؤولية للحصول على التفاصيل.
تحليل متعمق للأمن الكامل لـ STARK
الموقع: الأمان والصوت — الغوص العميق في أمان STARK
** الترجمة والتدقيق اللغوي **: "مجتمع Starknet الصيني"
حقائق سريعة مميزة
شرح تفصيلي لأمن STARK
يعد نظام إثبات STARK، أو حجة المعرفة الشفافة القابلة للتطوير، أداة قوية للسلامة الحسابية: فهو يسمح بالتحقق غير الموثوق من صحة الحسابات التي يتم إجراؤها على البيانات العامة. في هذه المقالة، سوف نتعمق في الأمان الذي توفره إثباتات STARK، ونحددها، ونستكشف تقنيات إثبات أمان المخططات.
(اقرأ القسم 6 من وثائق ethSTARK (الإصدار 1.2) للحصول على التفاصيل، بالإضافة إلى العمل المستقل المهم والشامل حول هذا الموضوع بواسطة Block et al.).
ما الذي نحاول تحقيقه من خلال التحليلات الأمنية؟ نريد منع "الهجمات الناجحة" على نظام STARK بسبب بيان كاذب وإثبات STARK الذي قبله مدقق STARK ردًا على هذا البيان (الزائف). نظرًا لأن التحريفات خطيرة ويمكن أن تأتي بجميع الأحجام والأشكال، فإننا نريد أن نكون آمنين ضدها جميعًا. أي عبارة خاطئة، حتى لو كانت تافهة مثل 1+1=3، عند دمجها مع دليل STARK المقبول من قبل مدقق STARK، سيتم اعتبارها هجومًا ناجحًا على النظام. (أولئك الذين لديهم خلفية في التشفير قد يكونون مهتمين بمعرفة أن STARK يمكنه أيضًا تلبية مفاهيم أمنية أقوى مثل موثوقية المعرفة، ولكن من أجل البساطة، ستركز هذه المقالة على حالات بسيطة حول الموثوقية).
كيف يمكننا تحديد أمان نظام STARK بشكل رسمي؟ نحدد ذلك من خلال تحليل "خطأ الموثوقية". يقيس "خطأ الموثوقية" تقريبًا "التكلفة" المتوقعة التي سيكلفها المهاجم لشن هجوم ناجح (على سبيل المثال، العثور على دليل STARK لبيان كاذب، ولكن يتم قبول الدليل من قبل مدقق STARK). من الناحية الرياضية، خطأ الموثوقية هو دالة (t) مدخلاتها هي المعلمة الزمنية t، التي تمثل الوقت الحسابي الذي يرغب المهاجم في إنفاقه لشن هجوم، والإخراج هو احتمال نجاح هجوم المهاجم (وجد في الأقوال الكاذبة دليل مقنع). كلما زادت "التكلفة" التي يرغب المهاجم في إنفاقها، زادت احتمالية نجاحه.
لقد قمنا حتى الآن بتعريف أمان STARK كوظيفة (t)، والتي تختلف عن الطريقة التي يناقش بها الجميع الأمان على تويتر المشفر كل يوم. على تويتر، قد تسمع شيئًا كهذا: "يحتوي هذا الحل على 96 بتًا من الأمان". كيف يترجم هذا إلى تعريفنا للأمن؟ لا توجد إجابة واحدة لهذا السؤال، حيث يفهم الناس "x بتات الأمان" بشكل مختلف قليلاً:
وفي هذه المقالة سنناقش الخيار الثاني.
من IOP إلى STARK بأمان 96 بت
إذن، كيف نثبت أن الحل يحتوي على 96 بت من الأمان؟ للإجابة على هذا السؤال، نحتاج إلى فهم البنية عالية المستوى التي تم بناء ستارك عليها. يتكون STARK من ثلاثة أجزاء رئيسية: IOP (دليل Oracle التفاعلي)، وشجرة Merkle، وتجزئة Fiat-Shamir؛ وتركيزنا الرئيسي هو IOP. بمجرد تحديد هذه الأجزاء المكونة، يمكننا تجميعها لإنشاء STARK. سنتناول هذه المكونات بالتفصيل، بما في ذلك ماهيتها وكيفية تناسبها معًا.
المكون الأول الذي سنراجعه هو IOP: يشبه IOP الدليل التفاعلي القياسي، حيث يتفاعل المثبت والمدقق في جولات متعددة (نقتصر على بروتوكولات العملة العامة، حيث يرسل المدقق تحديات عشوائية فقط إلى المثبت). في عملية IOP، لا يقرأ المدقق رسالة المثبت بشكل كامل، ولكنه بدلاً من ذلك يأخذ عينات من جزء صغير من البتات من رسالة كل محقق. هذا هو السبب في أن STARK الذي تم تجميعه لاحقًا يحقق البساطة.
بالنظر إلى IOP، كيف يمكنني بناء STARK منه؟ يمكن أن تكون رسائل المُثبت طويلة جدًا (في الواقع، تكون أطول من الحساب نفسه). لضغط هذه المعلومات نستخدم أشجار ميركل. شجرة Merkle هي شجرة تجزئة ثنائية حيث تمثل كل عقدة طرفية استعلامًا أو ردًا في IOP. الجذور هي وعد الرسالة بأكملها. عندما يريد المدقق قراءة موقع معين في رسالة، يوفر المثبت قيمة ذلك الموقع ومسار التحقق. يمكن للمدقق بعد ذلك استخدام هذا المسار للتحقق من صحة القيمة. يقرأ مدقق IOP كمية صغيرة فقط من معلومات الموقع من معلومات المثبت. لذلك، يمكن تنفيذ البروتوكولات المختصرة (البروتوكولات ذات حجم الاتصال المنخفض) باستخدام أشجار Merkle.
جولات الضغط
يمكننا اختيار STARK التفاعلي، ولكن لتبسيط عملية إنشاء STARK، نختار عادةً STARK غير التفاعلي، بحيث لا يحتاج المدقق إلى انتظار معلومات خارجية عند بناء STARK. في الواقع، هذه هي الطريقة التي يتم بها نشر جميع أنظمة STARK الحالية وكيفية بناء بروتوكول ethSTARK. تعد STARKs غير التفاعلية أيضًا حالة خاصة من SNARKs الشفافة (الشفافة تعني عدم الحاجة إلى إعداد موثوق لإنشاء مثيل لها؛ "بروتوكول Arthur Merlin" أو "Public Coin IOP"). وللقيام بذلك، تتمثل الخطوة الأخيرة في تطبيق خوارزمية فيات شامير لضغط جولات متعددة من التفاعلات في رسالة واحدة، وهو ما نسميه برهان ستارك. تحويل فيات-شمير هو طريقة لتحويل بروتوكول تفاعلي إلى بروتوكول غير تفاعلي. يحاكي المثل بروتوكولًا تفاعليًا أثناء التحدث إلى وظيفة التجزئة. لاشتقاق التحدي العشوائي للجولة i، يقوم المُمثل بتجزئة السجل الجزئي للجولة i ويفسر الناتج على أنه التحدي التالي.
وهذا يضمن عدم قدرة المُثبت على تغيير إجابته بعد إنشاء التحدي. ومع ذلك، فإن مُثبت الغش لديه بعض الطرق الإستراتيجية الجديدة التي لا تتوفر في عمليات IOP التفاعلية. يستطيع المُثبِّت إعادة إنشاء تحدي المدقق عن طريق تعديل معلومات المُثبِّت الأخير، بحيث يحصل على سجل جديد وبالتالي تحدي جديد. وتبين أن مفهوم الموثوقية القياسي لـ IOP غير كافٍ لإثبات سلامة تحويل فيات-شمير.
على سبيل المثال، احصل على IOP مكون من 96 جولة وأضف الاختراق التالي إلى المدقق: إذا كان البت الأول من عشوائية المدقق هو 0 في كل جولة من الجولات الـ 96، فسيقبله المدقق (دون رؤية أي دليل). يمكننا أن نرى أن إضافة هذا الاختراق إلى المدقق يضيف فقط مصطلح 2⁹⁶ إلى خطأ موثوقية IOP. ومع ذلك، بعد تحويل فيات-شمير، يمكن للمهاجم تعديل معلومات المثبت بسهولة للتأكد من أن كل قيمة تجزئة تبدأ بالصفر، وبالتالي اقتحام النظام في وقت قصير جدًا. كن مطمئنًا، هذا السيناريو الرهيب هو مجرد مثال نظري ولا ينطبق على صواريخ ستارك المنتشرة. لذلك، دعونا نلقي نظرة على سبب كون STARK الخاص بنا آمنًا بعد كل شيء. باختصار، سوف نبين أن المهاجم يركض بخطوات t على الأكثر، وأن احتمال نجاح الهجوم هو على الأكثر (t) t 2⁹⁶.
IOP والموثوقية الشاملة
يعتمد أمان STARK على IOP الأساسي الخاص به. ولكن ماذا يعني أن يكون لدى IOP 96 بت من الأمان؟ وفقًا للتعريف القياسي، فإن خطأ موثوقية IOP هو 2⁹⁶: وهذا يعني أن احتمال أن يتمكن أي مهاجم (بغض النظر عن وقت التشغيل) من خداع المدقق هو 2-96 على الأكثر. ومع ذلك، كما ناقشنا، فإن موثوقية IOP هي واحدة فقط من المكونات الثلاثة، وهو ما لا يكفي للحصول على 96 بت من الأمان من STARK المجمعة من الخطوات الثلاث جميعها. في المقابل، تم إثبات سلامة STARK المجمعة على افتراض أن STARK لديه خطأ موثوقية جولة تلو الأخرى يبلغ 96 بت (يتم استخدام تعريف مماثل يسمى موثوقية استرداد الحالة أحيانًا).
بشكل بديهي، تعني "سلامة الجولة تلو الأخرى" أن كل جولة تحتوي على 96 بت من الأمان، وليس فقط البروتوكول بأكمله. لكي نكون أكثر تحديدًا، تشير الموثوقية الدائرية إلى وجود مسند يمكنه الحصول على جزء من سجل البروتوكول وإخبارنا ما إذا كان هذا السجل "خادعًا": "السجل الفارغ" ليس "خادعًا"، و عندما يكون السجل الكامل "مخادعًا" فقط إذا تم قبوله من قبل المدقق. أخيرًا، بالنسبة لأي سجل جزئي لا "ينتحل" المدقق، فإن احتمال أن يصبح السجل "انتحالًا" في الجولة التالية هو 2⁹⁶ على الأكثر. إذا كان هناك مسند بهذه الخصائص، فإننا نقول أن البروتوكول يحتوي على 96 بت من الموثوقية الشاملة (لا يتطلب هذا المسند حسابًا فعالاً).
في كثير من الحالات، يقوم الأشخاص فقط بتحليل موثوقية IOP وليس موثوقيتها الشاملة. من المسلم به أنه من الصعب التفكير في مثال (باستثناء الأمثلة المصنعة) لـ IOP يتمتع بموثوقية قياسية ولكن ليس بموثوقية شاملة. ومع ذلك، عند استخلاص حدود أمان محددة، قد تنشأ اختلافات بين الاثنين، وكل بتة لها أهميتها. ولذلك، لاشتقاق حدود ضيقة ومحددة، من الضروري إجراء تحليل دقيق لموثوقية IOP الشاملة. وهذا هو بالضبط ما نفعله مع بروتوكول FRI وethSTARK IOP الذي يعتمد عليه STARK IOP. التحليل في حد ذاته أبعد ما يكون عن التافه ويخرج عن نطاق هذه المقالة. باستخدام التحليل الجديد، يمكننا تعيين معلمات دقيقة لإثباتنا.
إن الموثوقية الشاملة تمنحنا بالفعل الضمان الذي نحتاجه. يمكن للمُثبِّت إعادة إنشاء التحدي عدة مرات، ولكننا نعلم أنه في أي جولة، يكون احتمال إنشاء سجل احتيالي هو 2⁹⁶. لذلك، إذا كان لدى المُثبِّت t مرات (تُقاس بعدد مكالمات التجزئة)، فيمكنه المحاولة معظم t مرات للحصول على سجل خادع، مما يحد من احتمالية نجاحه إلى (t) t2⁹⁶.
إضافة كافة عناصر الخطأ
وأخيرا، لكي يصبح كل هذا صحيحا، يتعين علينا أن نتأكد من أن المثل لا يستطيع التلاعب بشجرة ميركل. يمكننا أن نبين أنه طالما لم يجد المُثبِّت أي تصادمات في دالة التجزئة، فلن يتمكن من الغش في شجرة ميركل. احتمالية عثور المهاجم على تصادم باستخدام استدعاءات t (دالة التجزئة العشوائية) هي على الأكثر t2/2، وهو طول إخراج دالة التجزئة (الناجمة عن "مفارقة عيد الميلاد"). ولهذا السبب نحتاج إلى تعيين دالة التجزئة الطول هو ضعف الأمان المطلوب، لذلك إذا كانت لدينا دالة تجزئة بطول إخراج يبلغ 192 وIOP بموثوقية جولة تلو الأخرى تبلغ 96 بت، فسنحصل على STARK مجمع موثوق به للخطأ الجنسي (t )=t2-⁹⁶ + t2 2¹⁹⁶. بما أن t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵، فإن هذا المخطط يحتوي على 95 بت من الجنس الآمن.
لخص
مجتمعة، يوفر STARK طريقة قوية للتحقق بشكل موثوق من صحة الحسابات التي يتم إجراؤها على البيانات العامة. يتم قياس أمان STARK عادةً من خلال "خطأ الموثوقية"، والذي يمثل احتمالية نجاح المهاجم في تقديم بيان كاذب وإقناع المدقق بالدليل. من أجل تحقيق مستوى الأمان المطلوب، مثل 96 بت، يجب أن يحقق IOP الأساسي موثوقية جولة تلو الأخرى لضمان الحفاظ على مستويات أمان عالية في كل جولة. لقد قمنا بتحليل الموثوقية الشاملة لعمليات IOP التي يعتمد عليها STARK الخاص بنا لاشتقاق حدود أمان محددة.