العنوان الأصلي المُعاد توجيهه 'فيتاليك يشرح Binius بالتفصيل: نظام دليل فعال يعتمد على الحقول الثنائية'

هذا المنشور موجه في المقام الأول للقراء الذين يملكون تقريبًا معرفة بتقنية التشفير في عام 2019، وخاصة SNARKs و STARKs. إذا لم تكن كذلك، فأوصي بقراءة تلك المقالات أولا. شكر خاص لجاستن دريك، جيم بوسن، بنجامين دياموند ورادي كوجباسيتش على التغذية الراجعة والمراجعة.

خلال السنتين الماضيتين، أصبحت STARKs تكنولوجيا حاسمة ولا يمكن استبدالها لجعل البراهين الكربتوغرافية سهلة التحقق للبيانات المعقدة جدًا (على سبيل المثال، إثبات صحة كتلة Ethereum). سبب رئيسي في ذلك هو أحجام الحقل الصغيرة: حيث تتطلب SNARKs القائمة على المنحنيات البيضاوية منك أن تعمل على مدى أعداد صحيحة بـ 256 بت من أجل أن تكون آمنة بما فيه الكفاية، تتيح لك STARKs استخدام أحجام حقول أصغر بكثير، والتي تكون أكثر كفاءة: أولاً حقل Goldilocks (أعداد صحيحة بـ 64 بت)، ثم Mersenne31 و BabyBear (كليهما 31 بت). بفضل هذه المكاسب في الكفاءة، فإن Plonky2، الذي يستخدم Goldilocks، أسرع بمئات المرات في إثبات أنواع متعددة من الحسابات مقارنة بأسلافه.

سؤال طبيعي يمكن طرحه هو: هل يمكننا أن نأخذ هذه الاتجاه إلى استنتاجه المنطقي، بناء نظم البرهان التي تعمل بشكل أسرع حتى عن طريق العمل مباشرة على الأصفار والواحدات؟ هذا بالضبط ما يحاول Binius القيام به، باستخدام عدد من الحيل الرياضية التي تجعلها مختلفة تمامًا عن SNARKs و STARKs منذ ثلاث سنوات. يتناول هذا المنشور الأسباب التي تجعل الحقول الصغيرة تجعل إنشاء البرهان أكثر كفاءة، ولماذا الحقول الثنائية قوية بشكل فريد، والحيل التي يستخدمها Binius لجعل البراهين على الحقول الثنائية تعمل بفعالية.

بينيوس. بحلول نهاية هذا المنشور، يجب أن تكون قادرًا على فهم كل جزء من هذا الرسم التوضيحي.

ملخص: حقول محدودة

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

للقيام بالحسابات الحسابية المعقدة مع الحفاظ على أرقام صغيرة، يستخدم المشفرين عموما الحساب المتناوب. نختار بعض الأعداد الأولية "الموديولوس" p. يعني عامل ال٪ "خذ الباقي من": 15 ٪ 7=1، 53 ٪ 10=3، وما إلى ذلك (لاحظ أن الجواب دائما غير سالب، لذا على سبيل المثال -1 ٪ 10=9).

ربما رأيت بالفعل الحسابات الحسابية النمطية، في سياق جمع وطرح الوقت (على سبيل المثال، ما هو الوقت بعد أربع ساعات من الساعة 9:00؟). ولكن هنا، نحن لا نقوم فقط بجمع وطرح بقية القسمة على عدد معين، بل نقوم أيضًا بالضرب والقسمة وأخذ الأسية.

نحن نعيد تعريفها:

القواعد أعلاه جميعها متناسقة في حد ذاتها. على سبيل المثال، إذا كان p=7، فإن:

5+3=1 (لأن 8%7=1)

1-3=5 (لأن -2%7=5)

2*5=3

3/5=2

مصطلح أكثر عمومية لهذا النوع من الهياكل هو حقل محدد. حقل محدد هو هيكل رياضي يطيع القوانين المعتادة للحساب، ولكن هناك عدد محدود من القيم الممكنة، وبالتالي يمكن تمثيل كل قيمة بحجم ثابت.

الحساب الم modulare (أو الحقول الأساسية) هو النوع الأكثر شيوعًا من الحقل المحدد، ولكن هناك نوع آخر أيضًا: حقول التمديد. ربما رأيت بالفعل حقل تمديد من قبل: الأعداد المركبة. نحن "نتخيل" عنصرًا جديدًا، نسميه 𝑖، ونعلن أنه يرضي المعادلة 𝑖2=−1. يمكنك بعد ذلك أخذ أي تركيبة من الأرقام العادية و𝑖، والقيام بعمليات رياضية بها: (3𝑖+2)∗(2𝑖+4)= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2. يمكننا بالمثل أن نأخذ تمديدات للحقول الأساسية. كلما بدأنا العمل فوق حقول أصغر، أصبحت تمديدات الحقول الأساسية أكثر أهمية للحفاظ على الأمان، وتعتمد الحقول الثنائية (التي يستخدمها بينيوس) تمامًا على التمديدات لديها لتحقيق الفائدة العملية.

تلخيص: التحصيص الحسابي

الطريقة التي تثبت من خلالها SNARKs و STARKs أمورًا حول البرامج الحاسوبية هي من خلال التعداد: تحويل البيان حول برنامج ترغب في إثباته إلى معادلة رياضية تتضمن متعددات. الحل الصحيح للمعادلة يتوافق مع تنفيذ صحيح للبرنامج.

على سبيل المثال البسيط، لنفترض أنني حسبت العدد الفيبوناتشي رقم 100، وأريد أن أثبت لك ما هو. أنشئ متعدداً فقرياً 𝐹 الذي يشفر أعداد فيبوناتشي: لذا 𝐹(0)=𝐹(1)=1، 𝐹(2)=2، 𝐹(3)=3، 𝐹(4)=5، وهكذا لمرحلة 100. الشرط الذي أحتاج إلى إثباته هو أن 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) عبر المدى 𝑥={0,1…98}. يمكنني إقناعك بذلك من خلال إعطائك النسبة:

حيث Z(x) = (x-0) (x-1) إذا كنت قادرًا على توفير أن هناك F و H يرضيان هذا المعادلة، فإنه يجب أن يرضي F المعادلة F(x+2)-F(x+1)-F(x) في النطاق. إذا قمت بالتحقق إضافةً من أن F يرضي أيضًا، F(0)=F(1)=1، فإنه يجب أن يكون F(100) في الواقع الرقم الفيبوناتشي الـ 100.

إذا كنت ترغب في إثبات شيء أكثر تعقيدًا، فيمكنك استبدال العلاقة 'البسيطة' 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) بمعادلة أكثر تعقيدًا، التي تقول في الأساس '𝐹(𝑥+1) هو الإخراج من تهيئة جهاز افتراضي بالحالة 𝐹(𝑥)، وتشغيل خطوة حسابية واحدة'. يمكنك أيضًا استبدال الرقم 100 برقم أكبر، على سبيل المثال 100000000، لاستيعاب مزيد من الخطوات.

جميع SNARKs و STARKs مستندة إلى هذه الفكرة باستخدام معادلة بسيطة على العديد من العلاقات بين القيم الفردية. ليس جميعها يشمل التحقق من المعادلة بين الخطوات الحسابية المجاورة بنفس الطريقة كما في الأعلى: PLONK لا يفعل ذلك، على سبيل المثال، ولا يفعل R1CS. ولكن العديد من الأنواع الأكثر كفاءة تفعل ذلك، لأن فرض نفس التحقق (أو التحققات القليلة نفسها) عدة مرات يجعل من السهل تقليل الفوقية.

Plonky2: من 256 بت SNARKs و STARKs إلى 64 بت… فقط STARKs

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

تعمل STARKs عن طريق معاملة البيانات على أنها متعددة الحدود، وحساب تقييمات لهذه المتعددة الحدود عبر عدد كبير من النقاط، واستخدام جذر Merkle لهذه البيانات الموسعة كـ "التزام متعدد الحدود"

جزء أساسي من التاريخ هنا هو أن SNARKs القائمة على المنحنى الإهليلجي دخلت حيز الاستخدام على نطاق واسع أولا: استغرق الأمر حتى عام 2018 تقريبا حتى تصبح STARKs فعالة بما يكفي للاستخدام ، وذلك بفضل FRI ، وبحلول ذلك الوقت كان Zcash يعمل بالفعل لأكثر من عام. SNARKs القائمة على المنحنى الإهليلجي لها قيود رئيسية: إذا كنت ترغب في استخدام SNARKs القائمة على المنحنى الإهليلجي ، فيجب إجراء الحساب في هذه المعادلات باستخدام الأعداد الصحيحة التي تمثل عدد النقاط على المنحنى الإهليلجي. هذا رقم كبير ، عادة بالقرب من 2256: على سبيل المثال ، بالنسبة لمنحنى bn128 ، فهو 21888242871839275222246405745257275088548364400416034343698204186575808495617. لكن الحساب الفعلي يستخدم أرقاما صغيرة: إذا كنت تفكر في برنامج "حقيقي" بلغتك المفضلة ، فإن معظم الأشياء التي يعمل معها هي عدادات ، ومؤشرات في الحلقات ، ومواضع في البرنامج ، وبتات فردية تمثل صواب أو خطأ ، وأشياء أخرى ستكون دائما بضعة أرقام فقط.

حتى لو كانت بياناتك "الأصلية" مكونة من "أرقام" "صغيرة"، فإن عملية الإثبات تتطلب حساب النسب، وتمديدات، ومجموعات خطية عشوائية، وتحويلات أخرى للبيانات، مما يؤدي إلى عدد متساوٍ أو أكبر من الكائنات التي، بمتوسط، بحجم كامل لحقلك. هذا يخلق عدم كفاءة رئيسية: لإثبات عملية على n قيم صغيرة، عليك أن تقوم بمزيد من الحساب على n قيمة أكبر بكثير. في البداية، استمدت STARKs عادة استخدام حقول بت 256 من SNARKs، ولذلك عانت من نفس عدم الكفاءة.

امتداد Reed-Solomon لبعض التقييمات المتعلقة بالمتعددات الحسابية. على الرغم من صغر القيم الأصلية، فإن القيم الإضافية تنتفخ جميعها إلى الحجم الكامل للمجال (في هذه الحالة 2 إلى القوة 31 - 1)

في عام 2022، تم إصدار بلونكي 2. الابتكار الرئيسي في بلونكي 2 كان القيام بعمليات حسابية بقسمة أصغر عدد أولي: 2⁶⁴−2³²+1=18446744069414584321. الآن، يمكن دائمًا إجراء كل عملية جمع أو ضرب في عدد قليل من التعليمات فقط على وحدة المعالجة المركزية، وتجزئة جميع البيانات معًا أسرع بمعدل 4 مرات من السابق. ولكن هذا يأتي بشرط: هذا النهج يعتمد فقط على STARK. إذا حاولت استخدام SNARK، مع منحنى بيضاوي بحجم صغير من هذا القبيل، فإن المنحنى البيضاوي يصبح غير آمن.

للاستمرار في الأمان ، احتاج Plonky2 أيضا إلى إدخال حقول التمديد. إحدى التقنيات الرئيسية في التحقق من المعادلات الحسابية هي "أخذ العينات عند نقطة عشوائية": إذا كنت تريد التحقق مما إذا كانت H (x) ∗ Z (x) تساوي بالفعل F (x + 2) − F (x + 1) − F (x) ، يمكنك اختيار بعض الإحداثيات العشوائية r ، وتوفير براهين فتح التزام متعدد الحدود تثبت H (r) و Z (r) و F (r + 1) و F (r + 2) ، ثم تحقق فعليا مما إذا كانت H (r) ∗ Z (r) تساوي F (r + 2) −F (r + 1) −F (r). إذا تمكن المهاجم من تخمين الإحداثيات في وقت مبكر ، فيمكن للمهاجم خداع نظام الإثبات - ولهذا السبب يجب أن يكون عشوائيا. ولكن هذا يعني أيضا أنه يجب أخذ عينات من الإحداثيات من مجموعة كبيرة بما يكفي بحيث لا يستطيع المهاجم تخمينها عن طريق الصدفة العشوائية. إذا كان المعامل بالقرب من 2²⁵⁶, هذا هو الحال بوضوح. ولكن مع الباقي 2⁶⁴−2³²+1، لم نصل بعد، وإذا انخفضنا إلى 2³¹−1، بالتأكيد ليس الحال. محاولة تزوير دليل ملياري مرة حتى يحالف الحظ شيء مطلقا ضمن نطاق قدرات المهاجم.

لإيقاف هذا، نأخذ عينة من حقل الامتداد. على سبيل المثال، يمكنك تحديد 𝑦 حيث 𝑦³=5, واتخاذ تركيبات من 1، 𝑦 و 𝑦². يزيد هذا العدد الإجمالي للإحداثيات مرة أخرى إلى حوالي 2⁹³يتمحور معظم متعددات الحدود التي يقوم بها البرهان في هذا الحقل الممتد؛ فهي تستخدم فقط الأعداد الصحيحة بوحدة 2³¹−1، وبالتالي لا تزال تحصل على جميع الكفاءات من استخدام الحقل الصغير. ولكن فحص النقطة العشوائية، وحساب FRI، يغوص في هذا الحقل الأكبر، من أجل الحصول على الأمان اللازم.

من الأعداد الأولية الصغيرة إلى الثنائية

الحواسيب تقوم بعمليات الحساب عن طريق تمثيل الأرقام الأكبر بصورة سلاسل من الأصفار والواحدات، وبناء "دوائر" فوق تلك البتات لحساب أشياء مثل الجمع والضرب. الحواسيب مُحسَّنة بشكل خاص لأداء الحسابات باستخدام الأعداد الصحيحة 16 بت و32 بت و64 بت. وحسابات مثل 2⁶⁴−2³²+1 و 2³¹تم اختيار -1 ليس فقط لأنها تناسب تلك الحدود، ولكن أيضًا لأنها تتناسب جيدًا مع تلك الحدود: يمكنك القيام بالضرب بالقسمة على 2⁶⁴−2³²+1 عن طريق القيام بعمليات الضرب بت 32 ، ونقل ونسخ النواتج بت بعض الأماكن. يشرح هذا المقال بعض الحيل بشكل جيد.

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

التقاط هذه المزايا من القيام بالحساب الثنائي مباشرة هو بالضبط ما يحاول Binius القيام به. يوضح جدول من عرض فريق Binius zkSummit مكاسب الكفاءة:

على الرغم من كونها تقريبًا نفس "الحجم"، فإن عملية حقل ثنائي 32 بت تستغرق خمس مرات أقل من الموارد الحسابية مقارنة بعملية على حقل ميرسين بـ 31 بت.

من الدوال الأحادية إلى الهيبركوبات

لنفترض أننا مقتنعون بهذا الاستدلال، ونريد أن نقوم بكل شيء عبر البتات (الأصفار والواحدات). كيف نلتزم فعليًا بمتعدد تمثيل لمليار بت؟

هنا، نواجه مشكلتين عمليتين:

1. لكي يمثل متعدد القيم، يجب أن تكون هذه القيم متاحة عند تقييمات المتعدد: في مثال فيبوناتشي لدينا أعلاه، 𝐹(0)، 𝐹(1) ... 𝐹(100)، وفي حساب أكبر، ستذهب المؤشرات إلى الملايين. والمجال الذي نستخدمه يجب أن يحتوي على أرقام تصل إلى تلك الحجم.

2. إثبات أي شيء عن قيمة نحن ملتزمون بها في شجرة Merkle (كما تفعل جميع التوقيعات الرقمية القوية) يتطلب ترميز Reed-Solomon: توسيع قيم 𝑛 إلى على سبيل المثال 8𝑛 قيمة، باستخدام التكرار لمنع مثبت خبيث من الغش عن طريق تقليد قيمة واحدة في منتصف العملية. هذا يتطلب أيضًا وجود مجال كبير بما فيه الكفاية: لتوسيع مليون قيمة إلى 8 ملايين، تحتاج إلى 8 ملايين نقطة مختلفة لتقييم الدالة العديدية.

الفكرة الرئيسية في Binius هي حل هاتين المشكلتين بشكل منفصل ، والقيام بذلك من خلال تمثيل نفس البيانات بطريقتين مختلفتين. أولا ، كثير الحدود نفسه. تتعامل SNARKs القائمة على المنحنى الإهليلجي ، و STARKs في عصر 2019 ، و Plonky2 والأنظمة الأخرى بشكل عام مع كثيرات الحدود على متغير واحد: F (x). من ناحية أخرى ، يستلهم بينيوس من بروتوكول سبارتان ، ويعمل مع كثيرات الحدود متعددة المتغيرات: F (x1، x2 ... xk). في الواقع ، نحن نمثل التتبع الحسابي الكامل على "hypercube" للتقييمات حيث يكون كل xi إما 0 أو 1. على سبيل المثال ، إذا أردنا تمثيل سلسلة من أرقام فيبوناتشي ، وما زلنا نستخدم حقلا كبيرا بما يكفي لتمثيلها ، فقد نتخيل أول ستة عشر منها على أنها شيء من هذا القبيل:

هذا هو، 𝐹(0,0,0,0) سيكون 1، 𝐹(1,0,0,0) سيكون 1 أيضًا، 𝐹(0,1,0,0) سيكون 2، وهكذا، حتى نصل إلى 𝐹(1,1,1,1)=987. بالنظر إلى مثل هذا الهايبركوب من التقييمات، هناك دقيقة واحدة فقط من الدرجة المتعددة (درجة 1 في كل متغير) متعددة التقديرات تنتج تلك التقييمات. لذلك يمكننا أن نفكر في ذلك المجموعة من التقييمات كتمثيل للمتعددة التقديرات. نحن في الواقع لسنا بحاجة أبدًا للتعامل مع حساب المعاملات.

هذا المثال بالطبع للتوضيح فقط: في الممارسة العملية ، بيت القصيد من الذهاب إلى hypercube هو السماح لنا بالعمل مع بتات فردية. ستكون طريقة "Binius-native" لحساب أرقام فيبوناتشي هي استخدام مكعب عالي الأبعاد ، باستخدام كل مجموعة من على سبيل المثال. 16 بت لتخزين رقم. يتطلب هذا بعض الذكاء لتنفيذ إضافة عدد صحيح أعلى البتات ، ولكن مع Binius ليس الأمر صعبا للغاية.

الآن ، نصل إلى ترميز المحو. الطريقة التي تعمل بها STARKs هي: تأخذ قيم n ، وتمتد Reed-Solomon إلى عدد أكبر من القيم (غالبا 8n ، عادة بين 2n و 32n) ، ثم تختار بشكل عشوائي بعض فروع Merkle من الامتداد وتجري نوعا من الفحص عليها. المكعب الفائق له طول 2 في كل بعد. وبالتالي ، ليس من العملي توسيعه مباشرة: لا توجد "مساحة" كافية لأخذ عينات من فروع Merkle من 16 قيمة. إذن ماذا نفعل بدلا من ذلك؟ نتظاهر بأن المكعب الفائق مربع!

بينيوس البسيط - مثال

انظرهنالتنفيذ بروتوكول هذا باستخدام Python.

دعونا نقوم بمراجعة مثال، باستخدام الأعداد الصحيحة العادية كحقل لراحة (في تنفيذ حقيقي سيكون هذا عناصر حقل ثنائي). أولاً، نأخذ المكعب الفائق الذي نريد الالتزام به، ونرمز إليه كمربع:

الآن، نقوم بتوسيع ريد-سولومون المربع. وهذا يعني أننا نعامل كل صف على أنه متعدد درجات 3 يقدر عند x = {0، 1، 2، 3}، ونقوم بتقدير نفس المتعدد الدرجات عند x = {4، 5، 6، 7}.

لاحظ أن الأرقام تنمو بسرعة! هذا هو السبب في أننا في التنفيذ الحقيقي، نستخدم دائمًا حقل محدود لهذا، بدلاً من الأعداد الصحيحة العادية: إذا استخدمنا الأعداد الصحيحة بالقسمة على 11، على سبيل المثال، فإن تمديد الصف الأول سيكون فقط [3، 10، 0، 6].

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

بعد ذلك، نعامل هذا التمديد كأعمدة، ونقوم بإنشاء شجرة Merkle من الأعمدة. جذر شجرة Merkle هو التزامنا.

الآن ، لنفترض أن البروفير يريد إثبات تقييم كثير الحدود هذا عند نقطة ما r = {r0، r1، r2، r3}. هناك فارق بسيط واحد في Binius يجعله أضعف إلى حد ما من مخططات الالتزام متعددة الحدود الأخرى: يجب ألا يعرف المحترف ، أو يكون قادرا على تخمين ، s ، إلا بعد التزامه بجذر Merkle (بمعنى آخر ، يجب أن تكون r قيمة عشوائية زائفة تعتمد على جذر Merkle). هذا يجعل المخطط عديم الفائدة ل "البحث عن قاعدة البيانات" (على سبيل المثال. "حسنا ، لقد أعطيتني جذر Merkle ، أثبت لي الآن P (0،0،1،0)!"). لكن بروتوكولات إثبات المعرفة الصفرية الفعلية التي نستخدمها بشكل عام لا تحتاج إلى "بحث في قاعدة البيانات". يحتاجون ببساطة إلى التحقق من كثير الحدود عند نقطة تقييم عشوائية. ومن ثم ، فإن هذا التقييد لا بأس به لأغراضنا.

نفترض أننا نختار 𝑟={1,2,3,4} (المتعددة، في هذه النقطة، تقوم بالتقييم على -137; يمكنك تأكيدهمع هذا الرمز). الآن ، ندخل في عملية صنع الدليل بالفعل. قمنا بتقسيم r إلى جزأين: الجزء الأول {1،2} يمثل مجموعة خطية من الأعمدة داخل صف ، والجزء الثاني {3،4} يمثل مجموعة خطية من الصفوف. نحسب "منتج موتر" ، لكل من جزء العمود:

وبالنسبة لجزء الصف:

ما يعنيه هو: قائمة بجميع المنتجات الممكنة لقيمة واحدة من كل مجموعة. في حالة الصف، نحصل على:

[(1-r2)(1-r3), (1-r3), (1-r2)r3، r2*r3]

استخدم r={1,2,3,4} (لذا r2=3 و r3=4):

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6، -9 -8 -12]

الآن ، نحسب "صفا" جديدا t ′ ، بأخذ هذه المجموعة الخطية من الصفوف الموجودة. وهذا هو ، نحن نأخذ:

يمكنك عرض ما يحدث هنا كتقييم جزئي. إذا قمنا بضرب الضرب الناتج الكامل ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) بالمتجه الكامل لجميع القيم، ستحصل على التقييم 𝑃(1,2,3,4)=−137. هنا نقوم بضرب ضرب جزئي يستخدم فقط نصف إحداثيات التقييم، ونقوم بتقليل شبكة من القيم إلى صف من القيم 𝑁. إذا قمت بإعطاء هذا الصف لشخص آخر، فيمكنه استخدام الضرب الناتج بنصف الإحداثيات التقييمية الأخرى لاستكمال باقي الحساب.

يزود البرهان الدليل بصف جديد، 𝑡′، بالإضافة إلى دلائل ميركل لبعض الأعمدة المختارة عشوائيًا. هذه بيانات 𝑂(𝑁). في مثالنا التوضيحي، سيقوم البرهان بتقديم آخر عمود فقط؛ في الحياة الواقعية، سيحتاج البرهان إلى تقديم عدة عشرات من الأعمدة لتحقيق أمان كافٍ.

الآن، نستفيد من الخطية لرموز ريد-سولومون. الخاصية الرئيسية التي نستخدمها هي: أن أخذ التركيب الخطي لامتداد ريد-سولومون يعطي نفس النتيجة كتمديد ريد-سولومون لتركيب خطي. هذا النوع من "استقلال النظام" يحدث في كثير من الأحيان عندما تكون لديك عمليتان خطيتان.

المدقق يفعل بالضبط ذلك. يقومون بحساب تمديد 𝑡′، ويقومون بحساب نفس التركيب الخطي للأعمدة التي قام بها الباحث من قبل (ولكن فقط للأعمدة التي قدمها الباحث)، والتحقق من أن هاتين الإجراءتين تعطيان نفس الإجابة.

في هذه الحالة، تمديد 𝑡′، وحساب نفس التركيب الخطي ([6،−9،−8،12]) للعمود، كلاهما يعطي الإجابة نفسها: −10746. يثبت هذا أن جذر Merkle تم بناؤه "بنية طيبة" (أو على الأقل "قريب بما فيه الكفاية"، وأنه يتطابق مع 𝑡′: على الأقل الغالبية العظمى من الأعمدة متوافقة مع بعضها البعض ومع 𝑡′.

ولكن يحتاج المدقق للتحقق من شيء آخر: فعليًا التحقق من تقييم المتعددات في {𝑟0..𝑟3}. حتى الآن، لم تعتمد أي من خطوات المدقق فعليًا على القيمة التي ادعى بها البروفر. إليك كيف نفعل ذلك التحقق. نأخذ الضرب القاعدي لما قمنا بتسميته بـ "جزء العمود" من نقطة التقييم:

في مثالنا، حيث r={1,2,3,4} لذا نصف العمود المحدد هو {1,2}، هذا يساوي:

إذاً، نأخذ الجمع المتسلسل لهذا 𝑡′:

الذي يساوي بالضبط الإجابة التي تحصل عليها إذا قمت بتقييم متعدد الحدود مباشرة.

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

حقل ثنائي

أصغر حقل ممكن هو الحساب وراء 2، وهو صغير جدًا بحيث يمكننا كتابة جداول الجمع والضرب الخاصة به:

يمكننا عمل حقول ثنائية أكبر عن طريق أخذ الامتدادات: إذا بدأنا بـ 𝐹2 (الأعداد الصحيحة مودولو 2) ثم قمنا بتعريف 𝑥 حيث 𝑥2=𝑥+1، سنحصل على الجدول التالي للجمع والضرب:

اتضح أنه يمكننا توسيع الحقل الثنائي إلى أحجام كبيرة بشكل تعسفي من خلال تكرار هذا البناء. على عكس الأعداد المركبة على الأعداد الحقيقية، حيث يمكنك إضافة عنصر جديد واحد 𝑖، ولكن لا يمكنك إضافة أي عناصر أخرى (الرباعيات موجودة، لكنها غريبة رياضياً، على سبيل المثال: 𝑎𝑏≠𝑏𝑎)، مع الحقول المحددة يمكنك الاستمرار في إضافة تمديدات جديدة إلى الأبد. على وجه الخصوص، نحدد العناصر على النحو التالي:

وهكذا. يُسمى هذا في كثير من الأحيان ببناء البرج، بسبب كيف يمكن اعتبار كل امتداد تالٍ كإضافة طبقة جديدة إلى البرج. هذه ليست الطريقة الوحيدة لبناء حقول ثنائية الحجم التعسفي، لكن لها بعض المزايا الفريدة التي يستفيد بينيوس منها.

يمكننا تمثيل هذه الأرقام كقائمة من البتات، على سبيل المثال 1100101010001111. البت الأول يمثل مضاعفات الواحد، البت الثاني يمثل مضاعفات x0، ثم البتات التالية تمثل مضاعفات: x1، x1*x0، x2، x2*x0، وهكذا. هذا الترميز جميل لأنه يمكنك تحليله إلى أجزاء:

هذه علامة نسبياً غير شائعة، ولكنني أحب تمثيل عناصر حقل البت كأعداد صحيحة، باعتبار التمثيل بالبت حيث تكون البتات الأكثر أهمية على اليمين. وهذا يعني، 1=1، 𝑥₀=01=2، 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19، وهكذا. 1100101010001111 هو، في هذا التمثيل، 61779.

الإضافة في مجال ثنائي هي فقط XOR (كما يفعل الطرح، بالمناسبة)؛ لاحظ أن هذا يعني x+x=0 لأي x. لضرب عنصرين x*y، هناك خوارزمية تكرارية بسيطة جدًا: قسّم كل رقم إلى نصفين:

ثم، قم بتقسيم الضرب:

القطعة الأخيرة هي الوحيدة القليل صعوبة، لأنه يجب تطبيق قاعدة الانخفاض، واستبدال 𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 بـ 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘-1∗𝑥𝑘+1). هناك طرق أكثر فعالية للقيام بالضرب، مثيلات خوارزمية كاراتسوبا والتحولات السريعة لفوريه، ولكن سأتركها كتمرين للقارئ المهتم لمعرفة تلك.

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

Left: addition table for four-bit binary field elements (ie. elements made up only of combinations of 1، 𝑥₀،𝑥₁و 𝑥₀𝑥₁Gate

Right: جدول الضرب لعناصر حقل البيانات الثنائية من أربعة بت.

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

بعد 255 خطوة، أنت مرة أخرى إلى 42²⁵⁵= 1. تمامًا مثل الأعداد الصحيحة الإيجابية والحساب الوحداتي، فإنها تتبع القوانين الرياضية العادية: ab=bأ، أ(b+c)=a b+a*c، حتى هناك بعض القوانين الجديدة الغريبة.

أخيرًا، تجعل الحقول الثنائية من السهل التعامل مع البتات: إذا قمت بعمليات رياضية مع الأرقام التي تناسب 2 ^kبت، ثم سوف تتناسب جميع الناتج الخاص بك أيضًا مع 2 كيلو بت. هذا يتجنب الإحراج. في EIP-4844 لـ Ethereum ، يجب أن يكون كل "بلوك" من كتلة وحدية رقمية 52435875175126190479447740508185965837690552500527637822603658699938581184513، لذا يتطلب ترميز البيانات الثنائية التخلص من بعض المساحة والقيام بفحص إضافي لضمان أن كل عنصر يخزن قيمة أقل من 2²⁴⁸. وهذا يعني أيضًا أن عمليات حقل البيانات الثنائية سريعة للغاية على الحواسيب - كل من وحدات المعالجة المركزية والتصاميم النظرية المثلى للدوائر المتكاملة القابلة لإعادة البرمجة وتصميمات التطبيقات المتكاملة الخاصة.

ما يعنيه كل هذا هو أننا يمكن أن نفعل شيئًا مثل الترميز ريد-سولومون الذي فعلناه أعلاه، بطريقة تجنب تمامًا "انفجار" الأعداد الصحيحة، كما رأينا في مثالنا، وبطريقة "انفجارية" للغاية. الطريقة "الأصلية"، نوع الحوسبة التي تعتبر فيها الحواسيب جيدة. خاصية "التقسيم" للحقول الثنائية - كيف نفعل ذلك 1100101010001111=11001010+10001111*x₃ثم تقسيمه وفقًا لاحتياجاتنا أمر أساسي أيضًا لتحقيق الكثير من المرونة.

بينيوس الكامل

انظرهنالتنفيذ هذا البروتوكول باستخدام Python.

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

لنلق نظرة مرة أخرى على الرسم البياني الكامل:

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

ما الجديد في "البينيوس الكامل"؟ أساسًا ثلاثة أشياء:

• القيم الفردية في الهايبركوب والمربع يجب أن تكون بتات (0 أو 1)
• عملية التمديد تمد البتات إلى بتات أكثر، عن طريق تجميع البتات في أعمدة والتظاهر مؤقتًا بأنها عناصر حقل أكبر
• بعد خطوة الجمع بين الصفوف، هناك خطوة "تحليل العناصر إلى بتات"، التي تحول الامتداد مرة أخرى إلى بتات

سنقوم بالتعامل مع كلاهما بدوره. أولاً، إجراء الامتداد الجديد. يوجد لكود Reed-Solomon القيد الأساسي وهو أنه إذا كنت تمتد قيمًا 𝑛 إلى قيم 𝑘∗𝑛، فيجب أن تكون تعمل في مجال يحتوي على قيم مختلفة بحجم 𝑘∗𝑛 يمكنك استخدامها كإحداثيات. مع 𝐹₂(المعروف أيضًا بالبتات)، لا يمكنك فعل ذلك. ولذلك ما نقوم به هو "تعبئة" الحروف المجاورة 𝐹₂يجمع العناصر معًا في قيم أكبر. في المثال هنا، نقوم بتعبئة بتين في كل مرة في عناصر في {0،1،2،3}، لأن امتدادنا يحتوي فقط على أربع نقاط تقييم ولذا يكفي لنا. في إثبات "حقيقي"، سنقوم على الأرجح بتجميع 16 بتًا معًا في كل مرة. ثم نقوم بتنفيذ رمز ريد-سولومون على هذه القيم المعبأة، ونقوم بفكها مرة أخرى إلى بتات.

الآن، توصيل الصف. لجعل "تقييم في نقطة عشوائية" تحقق أمانًا تشفيريًا، نحتاج إلى أن تكون تلك النقطة مأخوذة عشوائيًا من مساحة كبيرة جدًا، أكبر بكثير من الهيبيركوب نفسه. لذا، بينما تكون النقاط داخل الهيبيركوب بتات، ستكون التقييمات خارج الهيبيركوب أكبر بكثير. في مثالنا أعلاه، ينتهي "توصيل الصف" بـ [11,4,6,1].

هذا يطرح مشكلة: نحن نعرف كيفية دمج أزواج البتات في قيمة أكبر، ثم نقوم بتمديد ريد-سولومون على ذلك، ولكن كيف تفعل الشيء نفسه لأزواج قيم أكبر بكثير؟

الحيلة في Binius هي القيام بها بتقديم البت: ننظر إلى البتات الفردية لكل قيمة (على سبيل المثال لما قمنا بوصفه بـ 11 ، هذا هو [1،1،0،1])، ثم نمدد صفيًا. وهذا يعني أننا نقوم بإجراء إجراء الامتداد على صف 1 من كل عنصر، ثم على صف 𝑥0، ثم على الـ "𝑥"₁"الصف، ثم على الإكس"₀∗𝑥₁صف، وهكذا (حسنًا، في مثالنا التوضيحي نتوقف هنا، ولكن في تنفيذ حقيقي سنذهب حتى 128 صفًا (الأخير يكون 𝑥₆∗ …∗ 𝑥₀)).

تلخيص:

• نأخذ البتات في الهايبركيوب، ونحولها إلى شبكة
• ثم نعامل المجموعات المتجاورة من البتات في كل صف على أنها عناصر حقل أكبر، ونقوم بعمليات حسابية عليها لتوسيع الصفوف بواسطة ريد-سولومون
• ثم نأخذ تركيبة صف من كل عمود من البتات، ونحصل على عمود من البتات (للمربعات أكبر من 4x4، أصغر بكثير) لكل صف كمخرج
• ثم ننظر إلى الإخراج كمصفوفة، ونعامل البتات كصفوف مرة أخرى

لماذا يعمل هذا؟ في الرياضيات 'العادية'، يتوقف القدرة على القيام (غالبًا) بعمليات خطية بأي ترتيب والحصول على نفس النتيجة عندما تبدأ في تقطيع العدد حسب الأرقام. على سبيل المثال، إذا بدأت بالعدد 345، وقمت بضربه في 8 ثم في 3، فسأحصل على 8280، وإذا قمت بهاتين العمليتين بالترتيب المعاكس، سأحصل أيضًا على 8280. ولكن إذا أدخلت عملية 'تقسيم حسب الرقم' بين الخطوتين، فإنها تنهار: إذا قمت بـ 8x ثم 3x، ستحصل على:

ولكن إذا قمت بعمل 3x ، ثم 8x ، فستحصل على:

ولكن في حقل ثنائي مبني بنية برجية، هذا النهج يعمل. تكمن السبب في قابليتها للفصل: إذا قمت بضرب قيمة كبيرة بقيمة صغيرة، فإن ما يحدث على كل قطاع يبقى في كل قطاع. إذا قمنا بضرب 1100101010001111 بـ 11، فهذا هو نفس تفكيك العامل الأول لـ 1100101010001111، الذي يكون

ومن ثم ضرب كل مكون بواحد عشر بشكل منفصل.

وضع كل شيء معًا

عمومًا، تعمل أنظمة دليل الأدلة الصفرية من خلال إدلاء ببيانات حول الجوابين التي تمثل بيانات حول التقييمات الأساسية: تمامًا كما رأينا في مثال سلسلة فيبوناتشي، 𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) يتحقق بشكل متزامن لجميع خطوات عملية الحساب فيبوناتشي. نحن نتحقق من بيانات حول الجوابين من خلال إثبات التقييمات في نقطة عشوائية. هذا الفحص في نقطة عشوائية يمثل فحص الجوابين الكامل: إذا لم تتطابق معادلة الجوابين، فإن فرصة مطابقتها في إحدى الإحداثيات العشوائية النوعية ضئيلة.

في الممارسة العملية ، يأتي المصدر الرئيسي لعدم الكفاءة من حقيقة أنه في البرامج الحقيقية ، فإن معظم الأرقام التي نعمل معها صغيرة: المؤشرات في الحلقات ، وقيم الصواب / الخطأ ، والعدادات ، وأشياء مماثلة. ولكن عندما "نمدد" البيانات باستخدام ترميز Reed-Solomon لمنحها التكرار اللازم لجعل فحوصات Merkle المستندة إلى إثبات آمنة ، فإن معظم القيم "الإضافية" ينتهي بها الأمر إلى شغل الحجم الكامل للحقل ، حتى لو كانت القيم الأصلية صغيرة.

للتغلب على هذا ، نريد أن نجعل الحقل صغيرا قدر الإمكان. خفضنا Plonky2 من أرقام 256 بت إلى أرقام 64 بت ، ثم ذهب Plonky3 إلى أبعد من ذلك إلى 31 بت. ولكن حتى هذا دون المستوى الأمثل. مع الحقول الثنائية ، يمكننا العمل على بتات فردية. هذا يجعل الترميز "كثيفا": إذا كانت بياناتك الأساسية الفعلية تحتوي على n بت ، فسيحتوي الترميز الخاص بك على n بت ، وسيحتوي الامتداد على 8 * n بت ، بدون حمل إضافي.

الآن، دعونا نلقي نظرة على الرسم البياني للمرة الثالثة:

في بينيوس، نحن ملتزمون بمتعدد الخطوط: متعدد الحدود 𝑃(x₀,x₁,…x_k) ، حيث التقييمات الفردية P (0,0 ... 0)، P(0,0... 1) ما يصل إلى P (1،1,... 1) يحتفظون بالبيانات التي نهتم بها. لإثبات التقييم عند نقطة ما ، "نعيد تفسير" نفس البيانات مثل المربع. ثم نقوم بتوسيع كل صف ، باستخدام ترميز Reed-Solomon عبر مجموعات من البتات ، لإعطاء البيانات التكرار اللازم لاستعلامات فرع Merkle العشوائية لتكون آمنة. ثم نحسب مجموعة خطية عشوائية من الصفوف ، مع معاملات مصممة بحيث يحمل الصف المدمج الجديد بالفعل التقييم الذي نهتم به. يتم تمرير كل من هذا الصف الذي تم إنشاؤه حديثا (والذي يتم إعادة تفسيره على أنه 128 صفا من البتات) ، وعدد قليل من الأعمدة المحددة عشوائيا مع فروع Merkle ، إلى المدقق.

ثم يقوم المحقق بـ "مزيج صف التمديد" (أو بالأحرى، بعض أعمدة التمديد)، و "تمديد مزيج الصف"، ويتحقق من تطابق الاثنين. ثم يحسب مزيج العمود، ويتحقق من أنه يُرجع القيمة التي يدّعيها البرهان. وها هو نظام البرهان لدينا (أو بحسب الدقة، مخطط التزام متعدد الحدود، وهو العنصر الأساسي الرئيسي لنظام البرهان).

ما الذي لم نغطيه؟

• خوارزميات فعالة لتوسيع الصفوف، التي تحتاج إليها فعلاً لجعل كفاءة المحقق الحوسبةية. نستخدم تحويلات فوريه سريعة على الحقول الثنائية، الموصوفةهنا (على الرغم من أن التنفيذ الدقيق سيكون مختلفًا، لأن هذا المنشور يستخدم بنية أقل كفاءة لا تعتمد على التمديد التكراري).
• الحساب. كثيرات الحدود أحادية المتغير مريحة لأنه يمكنك القيام بأشياء مثل F (X + 2) -F (X + 1) -F (X) = Z (X) * H (X) لربط الخطوات المجاورة في الحساب. في المكعب الفائق ، تكون "الخطوة التالية" أقل قابلية للتفسير من "X + 1". يمكنك أن تفعل X + k ، قوى k ، لكن سلوك القفز هذا سيضحي بالعديد من المزايا الرئيسية ل Binius. يتم تقديم الحل في ورقة بينيوس (انظر القسم 4.3)، ولكن هذا هو حفرة أرنب عميقة في حد ذاتها.
• كيفية القيام بفحوصات قيم محددة بشكل آمن في الواقع. يتطلب مثال فيبوناتشي التحقق من شروط الحدود الرئيسية: F(0)=F(1)=1 وقيمة F(100). ولكن مع "البينيوس" الخام، من غير الآمن التحقق من نقاط التقييم المعروفة مسبقًا. هناك طرق بسيطة نسبيًا لتحويل فحص التقييم المعروف إلى فحص التقييم غير المعروف، باستخدام ما يُسمى ببروتوكولات فحص المجموعات؛ لكننا لم نتطرق إلى ذلك هنا.
• بروتوكولات البحث، تقنية أخرى حصلت مؤخرًا على استخدام متزايد كوسيلة لجعل أنظمة الإثبات فائقة الكفاءة. يمكن دمج Binius مع بروتوكولات البحث للعديد من التطبيقات.
• تتجاوز وقت التحقق من الجذر التربيعي. الجذر التربيعي مكلف: بروف بينيوس للبتات يبلغ طوله حوالي 11 ميغابايت. يمكنك تصحيح هذا باستخدام نظام بروف آخر لعمل "برهان على بروف بينيوس"، مكتسبًا بذلك كفاءة بينيوس في إثبات البيان الرئيسي وحجم بروف صغيرًا. خيار آخر هو بروتوكول FRI-Binius الأكثر تعقيدًا بكثير، الذي ينشئ بروف بحجم مضغوط لوغاريتمي (مثل FRI العادي).
• كيف يؤثر Binius على ما يُعتبر "صديقًا للSNARK". الخلاصة الأساسية هي أنه إذا استخدمت Binius، فلن تحتاج بعد الآن إلى الاهتمام كثيرًا بجعل الحسابات "صديقة للحساب الحسابي": العلامات التجارية "العادية" لم تعد أكثر كفاءة من العلامات التجارية الحسابية التقليدية، والضرب النمودجي أو نمودجي لم يعد صداعًا كبيرًا مقارنة بالضرب النمودجي، وهكذا. ولكن هذا موضوع معقد؛ الكثير من الأشياء تتغير عندما يتم كل شيء بالنظام الثنائي.

أتوقع المزيد من التحسينات في تقنيات الإثبات القائمة على حقل البيانات في الأشهر القادمة.

إخلاء المسؤولية:

1. تم نشر هذه المقالة من [Gateبانيوز]. إعادة توجيه العنوان الأصلي 'Vitalik详解Binius：基于二进制字段的高效证明系统'. جميع حقوق الطبع والنشر تنتمي إلى الكاتب الأصلي [فيتاليك بوتيرين*]. إذا كانت هناك اعتراضات على هذا النشر، يرجى الاتصال بـبوابة تعلمفريق، وسوف يتعاملون معها على الفور.
2. إخلاء المسؤولية عن المسؤولية: الآراء والآراء المعبر عنها في هذه المقالة هي فقط تلك للكاتب ولا تشكل أي نصيحة استثمارية.
3. يتم إجراء ترجمات المقالة إلى لغات أخرى من قبل فريق Gate Learn. ما لم يذكر غير ذلك، فإن نسخ أو توزيع أو نسخ المقالات المترجمة ممنوع.