فيتاليك: بينيوس، براهين فعالة للحقول الثنائية

المقال الأصلي بقلم: فيتاليك بوتيرين

الترجمة الأصلية: كيت، مارسبيت

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

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

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

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

مراجعة: الحقول المحدودة

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

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

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

نعيد تعريف:

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

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

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

2* 5 = 3

3/5 = 2

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

الحساب المعياري (أو الحقول الأولية) هو النوع الأكثر شيوعًا للحقول المحدودة، ولكن هناك نوع آخر: الحقول الممتدة. ربما تكون قد شاهدت حقلاً ملحقًا واحدًا: الأعداد المركبة. نتخيل عنصرًا جديدًا ونسميه i ونجري العمليات الحسابية معه: (3i+2)*(2i+4)=6i*i+12i+4i+8=16i+2. يمكننا أن نفعل الشيء نفسه مع امتداد الحقل الرئيسي. عندما نبدأ في التعامل مع الحقول الأصغر، يصبح امتداد الحقول الأولية ذا أهمية متزايدة للأمان، وتعتمد الحقول الثنائية (التي يستخدمها Binius) بالكامل على الامتداد للحصول على فائدة عملية.

مراجعة: الحساب

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

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

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

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

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

Plonky 2: من SNARKs وSTARKs 256 بت إلى 64 بت... فقط STARKs

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

تعمل STARKs من خلال التعامل مع البيانات باعتبارها كثيرة الحدود، وحساب حساب كثير الحدود، واستخدام جذر ميركل للبيانات الموسعة باعتباره "التزامًا متعدد الحدود".

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

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

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

في عام 2022، تم إصدار بلونكي 2. الابتكار الرئيسي في Plonky 2 هو القيام بمعامل حسابي لعدد أولي أصغر: 2 أس 64 - 2 أس 32 + 1 = 18446744067414584321. الآن، يمكن دائمًا إجراء كل إضافة أو ضرب في بعض التعليمات على أصبحت وحدة المعالجة المركزية وتجزئة جميع البيانات معًا أسرع 4 مرات من ذي قبل. ولكن هناك مشكلة: هذه الطريقة تعمل فقط مع STARKs. إذا حاولت استخدام SNARKs، تصبح المنحنيات الإهليلجية غير آمنة لمثل هذه المنحنيات الإهليلجية الصغيرة.

لضمان الأمان، يحتاج Plonky 2 أيضًا إلى تقديم حقول الامتداد. الأسلوب الرئيسي للتحقق من المعادلات الحسابية هو أخذ العينات العشوائية: إذا كنت تريد التحقق مما إذا كانت H(x) * Z(x) تساوي F(x+ 2)-F(x+ 1)-F(x)، يمكنك ذلك بشكل عشوائي اختر إحداثيًا r، وقدم التزامًا متعدد الحدود لإثبات H(r)، وZ(r)، وF(r)، وF(r+ 1) وF(r+ 2)، ثم تحقق مما إذا كان H(r) * Z(r) ) يساوي F(r+ 2)-F(r+ 1)- F(r). إذا تمكن المهاجم من تخمين الإحداثيات مسبقًا، فيمكنه خداع نظام الإثبات – ولهذا السبب يجب أن يكون نظام الإثبات عشوائيًا. ولكن هذا يعني أيضًا أنه يجب أخذ عينات من الإحداثيات من مجموعة كبيرة بما يكفي بحيث لا يستطيع المهاجم تخمينها بشكل عشوائي. من الواضح أن هذا صحيح إذا كان المعامل قريبًا من 2 أس 256. ومع ذلك، بالنسبة للمعامل 2^64 – 2^32 + 1، لم نصل إلى هذه المرحلة بعد، وبالتأكيد ليس هذا هو الحال إذا انتقلنا إلى 2^31 – 1. من ضمن قدرات المهاجم أن يحاول تزوير دليل ملياري مرة حتى يحالفه الحظ.

لمنع ذلك، نقوم بأخذ عينة r من حقل موسع، بحيث يمكنك، على سبيل المثال، تعريف y حيث y^3 = 5، وأخذ مجموعات من 1 وy وy^2. وبذلك يصل إجمالي عدد الإحداثيات إلى حوالي 2^93. معظم كثيرات الحدود التي يحسبها المثل لا تدخل في هذا المجال الممتد؛ إنها مجرد أعداد صحيحة modulo 2^31-1، لذلك لا تزال تحصل على كل الكفاءة من استخدام حقل صغير. لكن عمليات فحص النقاط العشوائية وحسابات FRI تصل إلى هذا المجال الأكبر للحصول على الأمان الذي يحتاجون إليه.

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

تقوم أجهزة الكمبيوتر بإجراء العمليات الحسابية من خلال تمثيل الأرقام الأكبر كتسلسلات من 0 و1، وبناء دوائر فوق تلك البتات لحساب العمليات مثل الجمع والضرب. تم تحسين أجهزة الكمبيوتر بشكل خاص للأعداد الصحيحة 16 و32 و64 بت. على سبيل المثال، تم اختيار 2^64 – 2^32 + 1 و2^31 – 1 ليس فقط لأنها تتلاءم مع تلك الحدود، ولكن أيضًا لأنها تتلاءم جيدًا مع تلك الحدود: وحدة الضرب 2^64 – 2^32 + 1 يمكن إجراؤها عن طريق إجراء عملية ضرب عادية بطول 32 بت، ونقل الإخراج ونسخه في أماكن قليلة؛ تشرح هذه المقالة بعض الحيل بشكل جيد.

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

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

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

من متعددات الحدود أحادية المتغير إلى المكعبات الفائقة

لنفترض أننا نؤمن بهذا المنطق، ونريد أن نفعل كل شيء باستخدام البتات (0 و1). كيف يمكننا تمثيل مليار بت مع متعدد الحدود واحد؟

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

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

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

الفكرة الأساسية لـ Binius هي حل هاتين المشكلتين بشكل منفصل، وذلك من خلال تمثيل نفس البيانات بطريقتين مختلفتين. أولاً، كثيرات الحدود نفسها. تتعامل أنظمة مثل SNARKs القائمة على المنحنى الإهليلجي، وSTARKs من حقبة 2019، وPlonky 2، وغيرها عادةً مع كثيرات الحدود عبر متغير واحد: F(x). من ناحية أخرى، يأخذ Binius الإلهام من بروتوكول Spartan ويستخدم متعددات الحدود متعددة المتغيرات: F(x 1, x 2,… xk). في الواقع، نحن نمثل المسار الحسابي بأكمله على المكعب الزائد للحساب، حيث يكون كل xi إما 0 أو 1. على سبيل المثال، إذا أردنا تمثيل تسلسل فيبوناتشي، وما زلنا نستخدم حقلًا كبيرًا بما يكفي لتمثيلها، فيمكننا ذلك تخيل أول 16 تسلسلًا لهم مثل هذا:

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

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

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

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

يرى هنا لتنفيذ بيثون للبروتوكول.

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

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

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

إذا كنت تريد تجربة الامتداد والتحقق من الأرقام بنفسك، فيمكنك استخدام رمز الامتداد Reed-Solomon البسيط الخاص بي هنا.

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

الآن، لنفترض أن المُبرِح يريد إثبات حساب كثير الحدود r = {r 0, r 1, r 2, r 3 } في مرحلة ما. هناك اختلاف دقيق في Binius يجعله أضعف من مخططات الالتزام متعددة الحدود الأخرى: يجب ألا يعرف المُثبِّت أو يكون قادرًا على تخمين s قبل الالتزام بجذر Merkle (وبعبارة أخرى، يجب أن تكون r قيمة عشوائية زائفة تعتمد على جذر ميركل). وهذا يجعل المخطط عديم الفائدة لعمليات البحث في قاعدة البيانات (على سبيل المثال، حسنًا، لقد أعطيتني جذر Merkle، والآن أثبت لي P(0, 0, 1, 0)!). لكن بروتوكولات إثبات المعرفة الصفرية التي نستخدمها فعليًا لا تتطلب عادةً عمليات بحث في قاعدة البيانات؛ أنها تتطلب فقط التحقق من كثير الحدود عند نقطة تقييم عشوائية. لذا فإن هذا التقييد يخدم أغراضنا جيدًا.

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

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

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

[( 1-ر2)*( 1-ر3),( 1-ر3),( 1-ر2)*ر3,ر2*ر3 ]

مع r = { 1, 2, 3, 4 } (لذلك r 2 = 3 و r 3 = 4):

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

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

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

يزود المُثبت المدقق بالصف الجديد التالي: t وبرهان Merkle لبعض الأعمدة التي تم أخذ عينات منها بشكل عشوائي. في مثالنا التوضيحي، سنطلب من المُثِّل أن يقدم العمود الأخير فقط؛ في الحياة الواقعية، سيحتاج المُثبِّت إلى توفير عشرات الأعمدة لتحقيق الأمان الكافي.

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

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

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

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

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

الآن نأخذ هذه المجموعة الخطية t:

هذا هو نفس الحل المباشر لكثيرة الحدود.

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

الحقول الثنائية

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

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

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

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

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

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

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

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

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

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

على اليسار: جدول إضافة لعناصر الحقل الثنائي ذات أربع بتات (أي 1 فقط، x 0، x 1، x 0x 1). على اليمين: جدول الضرب لعناصر الحقل الثنائي المكونة من أربعة بتات.

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

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

أخيرًا، تعد الحقول الثنائية ملائمة لمعالجة البتات: إذا كنت تقوم بالرياضيات باستخدام أرقام تناسب 2 كيلو بايت، فإن كل مخرجاتك سوف تتناسب مع 2 كيلو بايت أيضًا. وهذا يتجنب الإحراج. في Ethereums EIP-4844، يجب أن تكون الكتل الفردية للنقطة عبارة عن أرقام modulo 52435875175126190479447740508185965837690552500527637822603658699938581184513، لذا يتطلب تشفير البيانات الثنائية التخلص من بعض المساحة وإجراء فحوصات إضافية في طبقة التطبيق للتأكد من أن القيمة المخزنة في كل عنصر أقل من 2248. هذا ويعني أيضًا أن العمليات الميدانية الثنائية تتم بسرعة فائقة على أجهزة الكمبيوتر - سواءً وحدات المعالجة المركزية (CPU) أو تصميمات FPGA وASIC المثالية من الناحية النظرية.

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

بينيوس كامل

يرى هنا لتنفيذ بيثون للبروتوكول.

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

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

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

ما الجديد في Complete Binius؟ في الأساس ثلاثة أشياء:

• يجب أن تكون القيم الفردية في المكعب الفائق والمربع بت (0 أو 1).

• تعمل عملية التوسيع على توسيع البتات إلى المزيد من البتات عن طريق تجميعها في أعمدة وافتراض أنها عناصر من حقل أكبر مؤقتًا.

• بعد خطوة تجميع الصفوف، توجد خطوة تحليل العناصر إلى البتات التي تحول التوسيع مرة أخرى إلى البتات.

حسنًا، ناقش كلتا الحالتين على التوالي. أولاً، إجراء التمديد الجديد. رموز Reed-Solomon لها قيود أساسية، إذا كنت تريد تمديد n إلى k*n، فأنت بحاجة إلى العمل في حقل بقيم k*n مختلفة يمكن استخدامها كإحداثيات. مع F 2 (ويعرف أيضًا باسم البتات)، لا يمكنك فعل ذلك. إذن ما نقوم به هو تجميع العناصر المتجاورة من F 2 معًا لتكوين قيم أكبر. في المثال هنا، قمنا بجمع بتتين في المرة الواحدة في العناصر { 0 , 1 , 2 , 3 } , وهو ما يكفي بالنسبة لنا نظرًا لأن الامتداد الخاص بنا يحتوي على أربع نقاط حسابية فقط. في دليل حقيقي، قد نعود 16 بت في المرة الواحدة. نقوم بعد ذلك بتنفيذ كود Reed-Solomon على هذه القيم المجمعة وتفكيكها إلى أجزاء مرة أخرى.

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

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

تتمثل خدعة Binius في القيام بذلك شيئًا فشيئًا: ننظر إلى جزء واحد من كل قيمة (على سبيل المثال، بالنسبة للشيء الذي أطلقنا عليه 11، وهو [1، 1، 0، 1])، ثم نقوم بتوسيعه صفًا تلو الآخر. أي أننا نقوم بتوسيعها على الصف الأول من كل عنصر، ثم على الصف x0، ثم على الصف x1، ثم على الصف x0x1، وهكذا (حسنًا، في مثال لعبتنا نتوقف عند هذا الحد، ولكن في مثال حقيقي سنصل إلى 128 صفًا (آخر صف هو x6*...*x0))

مراجعة:

• نقوم بتحويل البتات الموجودة في المكعب الفائق إلى شبكة

• ثم نتعامل مع مجموعات البتات المتجاورة في كل صف كعناصر لحقل أكبر ونجري عمليات حسابية عليها لكي يقوم ريد-سولومون بتوسيع الصف

• نأخذ بعد ذلك مجموعة الصفوف من كل عمود من البتات ونحصل على عمود البتات لكل صف كإخراج (أصغر بكثير للمربعات الأكبر من 4 × 4)

• بعد ذلك، نعتبر المخرجات كمصفوفة والبتات الخاصة بها كصفوف

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

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

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

ثم اضرب كل مكون في 11.

ضع كل شيء معا

بشكل عام، تعمل أنظمة إثبات المعرفة الصفرية عن طريق تقديم بيانات حول كثيرة الحدود التي تمثل بيانات حول التقييم الأساسي في نفس الوقت: تمامًا كما رأينا في مثال فيبوناتشي، F(X+ 2)-F(X+ 1)-F( X) = Z(X)*H(X) أثناء التحقق من جميع خطوات حساب فيبوناتشي. نحن نتحقق من البيانات حول كثير الحدود من خلال إثبات التقييم في نقاط عشوائية. يمثل هذا التحقق من النقاط العشوائية فحصًا لمتعددة الحدود بأكملها: إذا كانت المعادلة متعددة الحدود غير متطابقة، فهناك احتمال ضئيل أن تتطابق عند إحداثيات عشوائية محددة.

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

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

والآن، لننظر إلى هذا المخطط مرة ثالثة:

في Binius، نحن نعمل على متعدد الحدود متعدد الخطوط: مكعب زائد P(x0, x1,…xk) حيث التقييمات الفردية P(0, 0, 0, 0), P(0, 0, 0, 1) تصل إلى P( 1، 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. تصف ورقة Binius الحل. انظر القسم 4.3)، ولكن هذه حفرة عميقة في حد ذاتها.

• كيفية إجراء فحوصات قيمة محددة بأمان. يتطلب مثال فيبوناتشي التحقق من شروط الحدود الرئيسية: قيم F(0)=F(1)=1 وF(100). لكن بالنسبة لـ Binius الأصلي، فمن غير الآمن إجراء عمليات فحص عند نقاط حسابية معروفة. هناك بعض الطرق البسيطة إلى حد ما لتحويل عمليات التحقق من الحسابات المعروفة إلى عمليات حسابية غير معروفة، وذلك باستخدام ما يسمى ببروتوكولات التحقق من المجموع؛ لكننا لن نغطي تلك هنا.

• تُستخدم بروتوكولات البحث، وهي تقنية أخرى تم استخدامها على نطاق واسع مؤخرًا، لإنشاء أنظمة إثبات فائقة الكفاءة. يمكن استخدام Binius مع بروتوكولات البحث للعديد من التطبيقات.

• بعد وقت التحقق من الجذر التربيعي. الجذور التربيعية غالية الثمن: يبلغ طول دليل Binius الذي يبلغ 2^32 بت حوالي 11 ميغابايت. يمكنك التعويض عن ذلك باستخدام أنظمة إثبات أخرى لعمل بروفات Binius، مما يمنحك كفاءة إثبات Binius بحجم إثبات أصغر. هناك خيار آخر وهو بروتوكول FRI-Binius الأكثر تعقيدًا، والذي ينشئ دليلاً على الحجم اللوغاريتمي المتعدد (تمامًا مثل FRI العادي).

• كيف يؤثر Binius على ملاءمة SNARK. الملخص الأساسي هو أنه إذا كنت تستخدم Binius، فلن تحتاج بعد الآن إلى الاهتمام بجعل العمليات الحسابية صديقة للحساب: التجزئة العادية لم تعد أكثر كفاءة من التجزئة الحسابية التقليدية، أو معامل الضرب 2 أس 32 أو مودولو 2 أس 32. لم يعد 256 مؤلمًا مثل معامل الضرب 2، وما إلى ذلك. لكن هذا موضوع معقد. تتغير الكثير من الأشياء عندما يتم كل شيء بطريقة ثنائية.

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

تم الحصول على هذه المقالة من الإنترنت: Vitalik: Binius، البراهين الفعالة للحقول الثنائية

ذات صلة: عملة BNB تظهر علامات التعافي: ارتفاع سنوي جديد في الأفق

باختصار، ارتد سعر BNB من مستوى $550 ليقترب أكثر من اختراق مستوى المقاومة $593. استعادت المؤشرات السعرية الزخم الصعودي الذي يدعم الارتفاع بمقدار 8%. من المرجح أن تدفع نسبة Sharpe عند 4.03 المستثمرين الجدد نحو رمز البورصة. كان شهر مارس شهرًا مناسبًا لعملة BNB، حيث حققت العملة المشفرة ارتفاعين جديدين لهذا العام في غضون أيام قليلة قبل أن تشهد تصحيحًا. بعد فترة من التعافي دامت ما يقرب من أسبوعين، تظهر عملة BNB Coin علامات على احتمال وصولها إلى مستوى مرتفع جديد في عام 2024. ولكن هل يمكن تحقيق هذا الإنجاز؟ تبدو عملة BNB واعدة بعد الارتداد من مستوى الدعم $550، ارتفعت قيمة عملة BNB إلى $581 في وقت هذا التحليل. يعكس هذا التحسن انتعاشًا في ملف تعريف المخاطر والعائد للعملة البديلة، ...