تحلل هذه المقالة خوارزمية MSM ، وخوارزمية إضافة نقطة المنحنى البيضاوي ، وخوارزمية مونتغمري للضرب ، وما إلى ذلك بالتفصيل ، وتقارن فرق الأداء بين GPU و FPGA في إضافة نقطة المنحنى BLS12 \ _381.
** بقلم: ستار لي **
يتم استخدام تقنية إثبات المعرفة الصفرية على نطاق واسع ، مثل إثبات الخصوصية وإثبات الحساب وإثبات الإجماع وما إلى ذلك. أثناء البحث عن سيناريوهات تطبيق أكثر وأفضل ، اكتشف العديد تدريجيًا أن إثبات عدم المعرفة يثبت أن الأداء يمثل عنق الزجاجة. أجرى فريق Trapdoor Tech أبحاثًا عميقة حول تقنية إثبات عدم المعرفة الصفرية منذ عام 2019 ، وكان يستكشف حلول تسريع فعالة لإثبات عدم المعرفة. GPU أو FPGA هي منصات تسريع شائعة نسبيًا في السوق حاليًا. تبدأ هذه المقالة بحساب MSM ، وتحلل مزايا وعيوب FPGA و GPU المعجل لإثبات المعرفة الصفرية.
TL ؛ DR
ZKP هي تقنية ذات آفاق واسعة للمستقبل. المزيد والمزيد من التطبيقات تعتمد تكنولوجيا إثبات المعرفة الصفرية. ومع ذلك ، هناك العديد من خوارزميات ZKP ، والمشاريع المختلفة تستخدم خوارزميات ZKP مختلفة. في نفس الوقت ، الأداء الحسابي لإثبات ZKP ضعيف نسبيًا. تحلل هذه الورقة خوارزمية MSM ، وخوارزمية إضافة نقطة المنحنى البيضاوي ، وخوارزمية مونتغمري للضرب ، وما إلى ذلك بالتفصيل ، وتقارن فرق الأداء بين GPU و FPGA في إضافة نقطة المنحنى BLS12 \ _381. بشكل عام ، من حيث الحوسبة المقاومة لـ ZKP ، تتمتع وحدة معالجة الرسومات قصيرة المدى بمزايا واضحة ، وإنتاجية عالية ، وأداء عالي التكلفة ، وإمكانية البرمجة وما إلى ذلك. بشكل نسبي ، تتمتع FPGA بمزايا معينة في استهلاك الطاقة. على المدى الطويل ، قد تكون هناك رقائق FPGA مناسبة لحسابات ZKP ، أو رقائق ASIC المخصصة لـ ZKP.
خوارزمية ZKP المعقدة
ZKP هو مصطلح عام لتقنية إثبات المعرفة الصفرية (Zero Knowledge Proof). يوجد تصنيفان رئيسيان: zk-SNARK و zk-STARK. الخوارزميات الشائعة الحالية لـ zk-SNARK هي Groth16 و PLONK و PLOOKUP و Marlin و Halo / Halo2. يتم تكرار خوارزمية zk-SNARK بشكل أساسي في اتجاهين: 1 / ما إذا كانت هناك حاجة إلى إعداد موثوق 2 / أداء بنية الدائرة. تتمثل ميزة خوارزمية zk-STARK في عدم الحاجة إلى إعداد موثوق به ، ولكن مقدار حساب التحقق هو سجل خطي.
بقدر ما يتعلق الأمر بتطبيق خوارزمية zk-SNARK / zk-STARK ، فإن خوارزميات إثبات المعرفة الصفرية المستخدمة في المشاريع المختلفة مبعثرة نسبيًا. في تطبيق خوارزمية zk-SNARK ، نظرًا لأن خوارزمية PLONK / Halo2 عالمية (لا حاجة إلى إعداد موثوق به) ، فقد يكون هناك المزيد والمزيد من التطبيقات.
يتكون مقدار حساب جزء الإثبات PLONK من أربعة أجزاء:
1 / MSM - الضرب العددي المتعدد. غالبًا ما يستخدم MSM لحساب الالتزامات متعددة الحدود.
2 / حساب NTT - تحويل متعدد الحدود بين قيمة النقطة وتمثيل المعامل.
3 / حساب متعدد الحدود - الجمع والطرح والضرب والقسمة كثيرات الحدود. تقييم متعدد الحدود (uation) وما إلى ذلك.
4 / دارة توليف - توليف الدائرة. يرتبط حساب هذا الجزء بمقياس / تعقيد الدائرة.
بشكل عام ، فإن مقدار الحساب في جزء تجميع الدائرة هو حكم ومنطق حلقة أكثر ، ودرجة التوازي منخفضة نسبيًا ، وهو أكثر ملاءمة لحساب وحدة المعالجة المركزية. بشكل عام ، يشير تسريع إثبات المعرفة الصفرية عمومًا إلى تسارع الحساب للأجزاء الثلاثة الأولى. من بينها ، تعد كمية حساب MSM هي الأكبر نسبيًا ، تليها NTT.
ما هو MSM
يشير MSM (الضرب القياسي المتعدد) إلى سلسلة معينة من النقاط والقياسات على المنحنى البيضاوي ، ويحسب النقاط المقابلة لنتائج إضافة هذه النقاط.
على سبيل المثال ، بالنظر إلى سلسلة من النقاط على منحنى ناقص:
إعطاء مجموعة ثابتة من نقاط المنحنى الإهليلجي من منحنى محدد واحد:
[G \ _1، G \ _2، G \ _3، ...، G \ _n]
والمعاملات العشوائية:
وعناصر حقل محدودة تم أخذ عينات منها عشوائيًا من حقل قياسي محدد:
[ق \ _1 ، ث \ _2 ، ق \ _3 ، ... ، ق \ _ ن]
MSM هو الحساب للحصول على نقطة منحنى Elliptic Q:
Q = \ sum \ _ {i = 1} ^ {n} s \ _i \ * G \ _i
تعتمد الصناعة عمومًا خوارزمية Pippenger لتحسين حساب MSM. ألق نظرة فاحصة على الرسم التخطيطي لعملية خوارزمية Pippenger:
تنقسم عملية حساب خوارزمية Pippenger إلى خطوتين:
1 / Scalar مقسم إلى Windows. إذا كان Scalar هو 256 بت ، والنافذة 8 بت ، فإن جميع Scalars مقسمة إلى 256/8 = 32 Windows. تستخدم كل طبقة من النوافذ "مجموعات" لتخزين النتائج الوسيطة مؤقتًا. GW \ _x هي نقطة تراكم النتيجة على طبقة واحدة. يعد حساب GW \ _x أيضًا بسيطًا نسبيًا ، فهو يجتاز كل مقياس في طبقة بدوره ، ويستخدم قيمة الطبقة القياسية كفهرس ، ويضيف G \ _x المقابل إلى المجموعات المقابلة. في الواقع ، المبدأ بسيط نسبيًا ، إذا كانت معاملات جمع النقطتين متطابقة ، أضف النقطتين أولاً ثم أضف المقياس مرة أخرى ، بدلاً من إضافة النقطتين مرتين قبل إضافة العدد القياسي.
2 / يتم تجميع النقاط التي تحتسبها كل نافذة عن طريق الإضافة المزدوجة للحصول على النتيجة النهائية.
تحتوي خوارزمية Pippenger أيضًا على العديد من خوارزميات تحسين التشوه. على أي حال ، فإن الحساب الأساسي لخوارزمية MSM هو إضافة نقاط على المنحنى الإهليلجي. تتوافق خوارزميات التحسين المختلفة مع عدد مختلف من النقاط المضافة.
إضافة نقطة منحنى إهليلجي (إضافة نقطة)
يمكنك إلقاء نظرة على خوارزميات مختلفة لإضافة النقاط على المنحنيات الناقصية باستخدام نموذج "قصير Weierstrass" من هذا الموقع.
بافتراض أن الإحداثيات الإسقاطية للنقطتين هي (x1 ، y1 ، z1) و (x2 ، y2 ، z2) على التوالي ، يمكن حساب نتيجة إضافة النقطة (x3 ، y3 ، z3) باستخدام صيغة الحساب التالية.
سبب إعطاء عملية الحساب بالتفصيل هو إظهار أن عملية الحساب بأكملها هي في الغالب عمليات عدد صحيح. عرض البت للعدد الصحيح يعتمد على معاملات المنحنى البيضاوي. أعط عروض البت لبعض المنحنيات الإهليلجية الشائعة:
BN256 - 256bits
BLS12 \ _381 - 381 بت
BLS12_377 - 377bits
الاهتمام الخاص هو أن هذه العمليات الصحيحة هي عمليات في حقل modulo. الجمع المعياري / الطرح المعياري بسيط نسبيًا ، مع التركيز على مبدأ وتنفيذ الضرب المعياري.
模 乘 （تعدد الوحدات）
إعطاء قيمتين في حقل معياري: x و y. يشير حساب الضرب النمطي إلى x \ * y mod p. لاحظ أن عرض البت لهذه الأعداد الصحيحة هو عرض البت للمنحنى الناقص. الخوارزمية الكلاسيكية للضرب المعياري هي مضاعفة مونتغمري (MontgomeryMulplication). قبل إجراء عملية الضرب في مونتغمري ، يجب تحويل المضاعفات إلى تمثيل مونتغمري:
صيغة حساب الضرب في مونتغمري هي كما يلي:
هناك العديد من خوارزميات تنفيذ المضاعفة في مونتغمري: CIOS (المسح الضوئي المتكامل للتشغيل) و FIOS (المسح المتكامل الدقيق للعمل) و FIPS (المسح المتكامل الدقيق للمنتج) وما إلى ذلك. لا تقدم هذه المقالة تفاصيل حول تطبيقات الخوارزمية المختلفة في العمق ، ويمكن للقراء المهتمين إجراء أبحاثهم الخاصة.
لمقارنة فرق الأداء بين FPGA و GPU ، اختر الطريقة الأساسية لتطبيق الخوارزمية:
ببساطة ، يمكن تقسيم خوارزمية الضرب المعيارية إلى عمليتين حسابيتين: مضاعفة عدد كبير وإضافة عدد كبير. بعد فهم منطق حساب MSM ، يمكنك اختيار أداء الضرب المعياري (الإنتاجية) لمقارنة أداء FPGA و GPU.
لاحظ وفكر
في ظل هذا التصميم FPGA ، يمكن تقدير أن VU9P بأكمله يمكن أن يوفر الإنتاجية عند نقاط المنحنى البيضاوي BLS12 \ _381. تتطلب إضافة النقطة (طريقة الجمع / المزج) حوالي 12 عملية ضرب معيارية. ساعة نظام FPGA هي 450 م.
في ظل نفس خوارزمية الضرب المعياري / إضافة المعامل ، باستخدام نفس خوارزمية إضافة النقطة ، تتجاوز النقطة بالإضافة إلى Troughput لـ Nvidia 3090 (مع الأخذ في الاعتبار عوامل نقل البيانات) 500M / s. بالطبع ، تتضمن العملية الحسابية بأكملها مجموعة متنوعة من الخوارزميات ، وقد تكون بعض الخوارزميات مناسبة لـ FPGA ، وبعض الخوارزميات مناسبة لوحدة معالجة الرسومات. سبب استخدام نفس مقارنة الخوارزمية هو مقارنة قدرات الحوسبة الأساسية لكل من FPGA و GPU.
بناءً على النتائج المذكورة أعلاه ، لخص المقارنة بين GPU و FPGA من حيث أداء إثبات ZKP:
لخص
المزيد والمزيد من التطبيقات تعتمد تكنولوجيا إثبات المعرفة الصفرية. ومع ذلك ، هناك العديد من خوارزميات ZKP ، والمشاريع المختلفة تستخدم خوارزميات ZKP مختلفة. من خلال خبرتنا الهندسية العملية ، يعد FPGA خيارًا ، لكن GPU يعد حاليًا خيارًا فعالاً من حيث التكلفة. تفضل FPGA الحوسبة القطعية ، والتي لها مزايا زمن الوصول واستهلاك الطاقة. تتميز وحدة معالجة الرسومات (GPU) بقدرة عالية على البرمجة ، ولديها إطار عمل حوسبة عالي الأداء ناضج نسبيًا ، ولها دورة تكرار تطوير قصيرة ، وتفضل سيناريوهات الإنتاجية.
شاهد النسخة الأصلية
المحتوى هو للمرجعية فقط، وليس دعوة أو عرضًا. لا يتم تقديم أي مشورة استثمارية أو ضريبية أو قانونية. للمزيد من الإفصاحات حول المخاطر، يُرجى الاطلاع على إخلاء المسؤولية.
مقال لفهم مزايا وعيوب FPGA و GPU تسريع الحوسبة الصفرية المعرفة
** بقلم: ستار لي **
يتم استخدام تقنية إثبات المعرفة الصفرية على نطاق واسع ، مثل إثبات الخصوصية وإثبات الحساب وإثبات الإجماع وما إلى ذلك. أثناء البحث عن سيناريوهات تطبيق أكثر وأفضل ، اكتشف العديد تدريجيًا أن إثبات عدم المعرفة يثبت أن الأداء يمثل عنق الزجاجة. أجرى فريق Trapdoor Tech أبحاثًا عميقة حول تقنية إثبات عدم المعرفة الصفرية منذ عام 2019 ، وكان يستكشف حلول تسريع فعالة لإثبات عدم المعرفة. GPU أو FPGA هي منصات تسريع شائعة نسبيًا في السوق حاليًا. تبدأ هذه المقالة بحساب MSM ، وتحلل مزايا وعيوب FPGA و GPU المعجل لإثبات المعرفة الصفرية.
TL ؛ DR
ZKP هي تقنية ذات آفاق واسعة للمستقبل. المزيد والمزيد من التطبيقات تعتمد تكنولوجيا إثبات المعرفة الصفرية. ومع ذلك ، هناك العديد من خوارزميات ZKP ، والمشاريع المختلفة تستخدم خوارزميات ZKP مختلفة. في نفس الوقت ، الأداء الحسابي لإثبات ZKP ضعيف نسبيًا. تحلل هذه الورقة خوارزمية MSM ، وخوارزمية إضافة نقطة المنحنى البيضاوي ، وخوارزمية مونتغمري للضرب ، وما إلى ذلك بالتفصيل ، وتقارن فرق الأداء بين GPU و FPGA في إضافة نقطة المنحنى BLS12 \ _381. بشكل عام ، من حيث الحوسبة المقاومة لـ ZKP ، تتمتع وحدة معالجة الرسومات قصيرة المدى بمزايا واضحة ، وإنتاجية عالية ، وأداء عالي التكلفة ، وإمكانية البرمجة وما إلى ذلك. بشكل نسبي ، تتمتع FPGA بمزايا معينة في استهلاك الطاقة. على المدى الطويل ، قد تكون هناك رقائق FPGA مناسبة لحسابات ZKP ، أو رقائق ASIC المخصصة لـ ZKP.
خوارزمية ZKP المعقدة
ZKP هو مصطلح عام لتقنية إثبات المعرفة الصفرية (Zero Knowledge Proof). يوجد تصنيفان رئيسيان: zk-SNARK و zk-STARK. الخوارزميات الشائعة الحالية لـ zk-SNARK هي Groth16 و PLONK و PLOOKUP و Marlin و Halo / Halo2. يتم تكرار خوارزمية zk-SNARK بشكل أساسي في اتجاهين: 1 / ما إذا كانت هناك حاجة إلى إعداد موثوق 2 / أداء بنية الدائرة. تتمثل ميزة خوارزمية zk-STARK في عدم الحاجة إلى إعداد موثوق به ، ولكن مقدار حساب التحقق هو سجل خطي.
بقدر ما يتعلق الأمر بتطبيق خوارزمية zk-SNARK / zk-STARK ، فإن خوارزميات إثبات المعرفة الصفرية المستخدمة في المشاريع المختلفة مبعثرة نسبيًا. في تطبيق خوارزمية zk-SNARK ، نظرًا لأن خوارزمية PLONK / Halo2 عالمية (لا حاجة إلى إعداد موثوق به) ، فقد يكون هناك المزيد والمزيد من التطبيقات.
PLONK يثبت مقدار الحساب
بأخذ خوارزمية PLONK كمثال ، قم بتحليل مقدار حساب برهان PLONK.
يتكون مقدار حساب جزء الإثبات PLONK من أربعة أجزاء:
1 / MSM - الضرب العددي المتعدد. غالبًا ما يستخدم MSM لحساب الالتزامات متعددة الحدود.
2 / حساب NTT - تحويل متعدد الحدود بين قيمة النقطة وتمثيل المعامل.
3 / حساب متعدد الحدود - الجمع والطرح والضرب والقسمة كثيرات الحدود. تقييم متعدد الحدود (uation) وما إلى ذلك.
4 / دارة توليف - توليف الدائرة. يرتبط حساب هذا الجزء بمقياس / تعقيد الدائرة.
بشكل عام ، فإن مقدار الحساب في جزء تجميع الدائرة هو حكم ومنطق حلقة أكثر ، ودرجة التوازي منخفضة نسبيًا ، وهو أكثر ملاءمة لحساب وحدة المعالجة المركزية. بشكل عام ، يشير تسريع إثبات المعرفة الصفرية عمومًا إلى تسارع الحساب للأجزاء الثلاثة الأولى. من بينها ، تعد كمية حساب MSM هي الأكبر نسبيًا ، تليها NTT.
ما هو MSM
يشير MSM (الضرب القياسي المتعدد) إلى سلسلة معينة من النقاط والقياسات على المنحنى البيضاوي ، ويحسب النقاط المقابلة لنتائج إضافة هذه النقاط.
على سبيل المثال ، بالنظر إلى سلسلة من النقاط على منحنى ناقص:
إعطاء مجموعة ثابتة من نقاط المنحنى الإهليلجي من منحنى محدد واحد:
[G \ _1، G \ _2، G \ _3، ...، G \ _n]
والمعاملات العشوائية:
وعناصر حقل محدودة تم أخذ عينات منها عشوائيًا من حقل قياسي محدد:
[ق \ _1 ، ث \ _2 ، ق \ _3 ، ... ، ق \ _ ن]
MSM هو الحساب للحصول على نقطة منحنى Elliptic Q:
Q = \ sum \ _ {i = 1} ^ {n} s \ _i \ * G \ _i
تعتمد الصناعة عمومًا خوارزمية Pippenger لتحسين حساب MSM. ألق نظرة فاحصة على الرسم التخطيطي لعملية خوارزمية Pippenger:
تنقسم عملية حساب خوارزمية Pippenger إلى خطوتين:
1 / Scalar مقسم إلى Windows. إذا كان Scalar هو 256 بت ، والنافذة 8 بت ، فإن جميع Scalars مقسمة إلى 256/8 = 32 Windows. تستخدم كل طبقة من النوافذ "مجموعات" لتخزين النتائج الوسيطة مؤقتًا. GW \ _x هي نقطة تراكم النتيجة على طبقة واحدة. يعد حساب GW \ _x أيضًا بسيطًا نسبيًا ، فهو يجتاز كل مقياس في طبقة بدوره ، ويستخدم قيمة الطبقة القياسية كفهرس ، ويضيف G \ _x المقابل إلى المجموعات المقابلة. في الواقع ، المبدأ بسيط نسبيًا ، إذا كانت معاملات جمع النقطتين متطابقة ، أضف النقطتين أولاً ثم أضف المقياس مرة أخرى ، بدلاً من إضافة النقطتين مرتين قبل إضافة العدد القياسي.
2 / يتم تجميع النقاط التي تحتسبها كل نافذة عن طريق الإضافة المزدوجة للحصول على النتيجة النهائية.
تحتوي خوارزمية Pippenger أيضًا على العديد من خوارزميات تحسين التشوه. على أي حال ، فإن الحساب الأساسي لخوارزمية MSM هو إضافة نقاط على المنحنى الإهليلجي. تتوافق خوارزميات التحسين المختلفة مع عدد مختلف من النقاط المضافة.
إضافة نقطة منحنى إهليلجي (إضافة نقطة)
يمكنك إلقاء نظرة على خوارزميات مختلفة لإضافة النقاط على المنحنيات الناقصية باستخدام نموذج "قصير Weierstrass" من هذا الموقع.
بافتراض أن الإحداثيات الإسقاطية للنقطتين هي (x1 ، y1 ، z1) و (x2 ، y2 ، z2) على التوالي ، يمكن حساب نتيجة إضافة النقطة (x3 ، y3 ، z3) باستخدام صيغة الحساب التالية.
سبب إعطاء عملية الحساب بالتفصيل هو إظهار أن عملية الحساب بأكملها هي في الغالب عمليات عدد صحيح. عرض البت للعدد الصحيح يعتمد على معاملات المنحنى البيضاوي. أعط عروض البت لبعض المنحنيات الإهليلجية الشائعة:
模 乘 （تعدد الوحدات）
إعطاء قيمتين في حقل معياري: x و y. يشير حساب الضرب النمطي إلى x \ * y mod p. لاحظ أن عرض البت لهذه الأعداد الصحيحة هو عرض البت للمنحنى الناقص. الخوارزمية الكلاسيكية للضرب المعياري هي مضاعفة مونتغمري (MontgomeryMulplication). قبل إجراء عملية الضرب في مونتغمري ، يجب تحويل المضاعفات إلى تمثيل مونتغمري:
صيغة حساب الضرب في مونتغمري هي كما يلي:
هناك العديد من خوارزميات تنفيذ المضاعفة في مونتغمري: CIOS (المسح الضوئي المتكامل للتشغيل) و FIOS (المسح المتكامل الدقيق للعمل) و FIPS (المسح المتكامل الدقيق للمنتج) وما إلى ذلك. لا تقدم هذه المقالة تفاصيل حول تطبيقات الخوارزمية المختلفة في العمق ، ويمكن للقراء المهتمين إجراء أبحاثهم الخاصة.
لمقارنة فرق الأداء بين FPGA و GPU ، اختر الطريقة الأساسية لتطبيق الخوارزمية:
ببساطة ، يمكن تقسيم خوارزمية الضرب المعيارية إلى عمليتين حسابيتين: مضاعفة عدد كبير وإضافة عدد كبير. بعد فهم منطق حساب MSM ، يمكنك اختيار أداء الضرب المعياري (الإنتاجية) لمقارنة أداء FPGA و GPU.
لاحظ وفكر
في ظل هذا التصميم FPGA ، يمكن تقدير أن VU9P بأكمله يمكن أن يوفر الإنتاجية عند نقاط المنحنى البيضاوي BLS12 \ _381. تتطلب إضافة النقطة (طريقة الجمع / المزج) حوالي 12 عملية ضرب معيارية. ساعة نظام FPGA هي 450 م.
في ظل نفس خوارزمية الضرب المعياري / إضافة المعامل ، باستخدام نفس خوارزمية إضافة النقطة ، تتجاوز النقطة بالإضافة إلى Troughput لـ Nvidia 3090 (مع الأخذ في الاعتبار عوامل نقل البيانات) 500M / s. بالطبع ، تتضمن العملية الحسابية بأكملها مجموعة متنوعة من الخوارزميات ، وقد تكون بعض الخوارزميات مناسبة لـ FPGA ، وبعض الخوارزميات مناسبة لوحدة معالجة الرسومات. سبب استخدام نفس مقارنة الخوارزمية هو مقارنة قدرات الحوسبة الأساسية لكل من FPGA و GPU.
بناءً على النتائج المذكورة أعلاه ، لخص المقارنة بين GPU و FPGA من حيث أداء إثبات ZKP:
لخص
المزيد والمزيد من التطبيقات تعتمد تكنولوجيا إثبات المعرفة الصفرية. ومع ذلك ، هناك العديد من خوارزميات ZKP ، والمشاريع المختلفة تستخدم خوارزميات ZKP مختلفة. من خلال خبرتنا الهندسية العملية ، يعد FPGA خيارًا ، لكن GPU يعد حاليًا خيارًا فعالاً من حيث التكلفة. تفضل FPGA الحوسبة القطعية ، والتي لها مزايا زمن الوصول واستهلاك الطاقة. تتميز وحدة معالجة الرسومات (GPU) بقدرة عالية على البرمجة ، ولديها إطار عمل حوسبة عالي الأداء ناضج نسبيًا ، ولها دورة تكرار تطوير قصيرة ، وتفضل سيناريوهات الإنتاجية.