leanVM؛ نتیجه منفی برای folding در تجمیع امضاهای post-quantum

چرا مهم است

اگر روی تجمیع امضا کار می‌کنی، این اندازه‌گیری‌ها هزینه سه جایگزین recursion را برایت روشن می‌کنند. در همین آزمایش، کاهش cycle با batching به زمان تکمیل کمتر از baseline تنظیم‌شده منجر نشد.

قبل از خواندن، این‌ها را بدان۳ مفهوم
Folding

روشی در سامانه‌های اثبات برای ترکیب چند نمونه از یک مسئله اثباتی در نمونه‌ای واحد که سپس بررسی یا اثبات می‌شود.

در حال نگارش: Folding

Witness

داده‌ای که prover برای نشان‌دادن برقرار بودن رابطه مورد اثبات در اختیار دارد؛ لازم نیست همه این داده در proof نهایی قرار بگیرد.

در حال نگارش: Witness

zkVM

ماشین مجازی‌ای که اجرای برنامه در آن می‌تواند با یک proof رمزنگاری‌شده تأیید شود.

در حال نگارش: zkVM

یک بررسی روی leanVM در commit df7d122 نشان می‌دهد که سه طرح hash-based accumulation،؜ در محدوده یک aggregator،؜ از full-verifier recursion سریع‌تر نبودند. آزمایش‌ها روی MacBook Air با Apple M2 و ۸ گیگابایت حافظه انجام شده‌اند و موضوع آن‌ها تجمیع امضاهای leanXMSS است. در مسیر recursion،؜ بررسی کامل proof فرزند داخل zkVM انجام می‌شود؛ مسیر جایگزین از Folding و سپس اثبات یک decider استفاده می‌کند.

نخستین طرح، Folding مستقیم بررسی امضاها بود. برآورد پژوهش برای هر امضا دست‌کم ۷٫۱ میلیون R1CS constraint است؛ با استفاده از نرخ اندازه‌گیری‌شده WARP،؜ هزینه آن حدود ۴۵۰ برابر هزینه هر امضا در leanVM برآورد شد. طرح دوم، Folding کل رابطه گام leanVM بود: نرخ اندازه‌گیری‌شده آن ۲۶۰ نانوثانیه برای هر عنصر Witness،؜ در برابر ۵۵ نانوثانیه برای هر committed word در leanVM بود. طرح سوم نیز برای به‌تعویق‌انداختن حداکثر ۴۶ هزار cycle،؜ حدود ۵۷ هزار cycle هزینه می‌کرد.

تفکیک هزینه‌ها نشان داد بررسی هر فرزند در merge حدود ۱۸۶٫۸ هزار VM cycle مصرف می‌کند و WHIR opening سهمی ۵۵ درصدی دارد. طرح batching با یک WHIR opening مشترک از level 1،؜ طبق شبیه‌سازی هزینه، برای هر فرزند ۳۲٫۸ هزار cycle یا ۱۷٫۶ درصد صرفه‌جویی داشت. بااین‌حال، برای ۱۵۰۰ امضا، زمان تکمیل آن همچنان ۲٫۴ درصد بیشتر از baseline با بهترین تنظیماتش بود و به آستانه هدف ۱۵ درصد نرسید.

تنظیم اندازه leaf نقش مهمی داشت. عبور merge node از mu 25 به mu 26،؜ با حدود ۳ درصد committed word بیشتر، زمان را ۱٫۴ تا ۱٫۸ برابر می‌کرد. تقسیم ۱۵۰۰ امضا به پنج leaf با ۳۰۰ امضا، به‌جای شش leaf با ۲۵۰ امضا، node را در mu 25 نگه داشت: زمان آخرین leaf به‌علاوه merge از ۳٫۱۱ به ۲٫۲۴ ثانیه و مصرف CPU در هر slot از ۷٫۹۹ به ۶٫۴۷ ثانیه رسید.

دامنه نتیجه محدود به یک aggregator است؛ اشیای جابه‌جاشده با gossip همچنان proof‌های leanVM می‌مانند. accumulator باید Witness مربوط به leaf را حمل کند که برای ۱۵۰۰ امضا حدود ۱ GiB است، در برابر proof حدود ۲۶۵ KiB. نویسندگان همچنین تأکید می‌کنند که زمان‌ها فقط به‌صورت نسبت روی همین دستگاه معنا دارند؛ نوسان برخی تنظیمات به ۱۰ تا ۱۵ درصد می‌رسید.

نکته کلیدی

هنگام مقایسه، اندازه leaf و عبور از مرز mu را هم بررسی کن؛ مدل خطی این جهش هزینه را نشان نمی‌دهد. نسبت‌های زمانی این گزارش را به دستگاه‌های دیگر تعمیم نده؛ خود گزارش آن‌ها را به همین M2 محدود می‌کند.

خواندن مقاله اصلی (در زبانه‌ی جدید باز می‌شود)
برچسب‌ها (۱)