Cairo for Rust devs I (محاسبات قابل تأیید)

Summarize this content to 400 words in Persian Lang
این مجموعه ای از مقالات در مورد قاهره است که معمولاً در چارچوب قراردادهای هوشمند web3 و Starknet ذکر می شود، اما در اینجا می خواهیم آن را به عنوان زبانی برای ایجاد برنامه های قابل اثبات و تأیید ارائه کنیم که به شما امکان می دهد محاسبات را به روشی غیرقابل اعتماد برون سپاری کنید.1.

این یک کار در حال انجام است. به روز رسانی انتظار می رود. از کایرونات های باتجربه استقبال می شود تا اشاره کنند که در کجا اشتباه می کنم.

چرا قاهره در حالی که Rust در حال حاضر بسیار عالی است

فرض کنید، شما وظیفه پیدا کردن فرصت های آربیتراژ بین بازارهای مختلف ارز را دارید2. شما می توانید این مشکل را از طریق یافتن چرخه منفی در نمودار مدل کنید که در آن راس ها ارز و یال ها بازارهای جفت هستند. نمودار هدایت و وزن دهی می شود که وزن ها لگاریتمی نرخ ارز هستند. الگوریتم کوتاه‌ترین مسیر بلمن-فورد معمولاً در این مورد استفاده می‌شود (ما در اینجا روی محاسبات قابل تأیید و در مقاله بعدی روی پیاده‌سازی تمرکز خواهیم کرد، بنابراین اکنون نگران الگوریتم نباشید).

پیچیدگی زمانی الگوریتم است O(|V||E|) (جایی که V مجموعه ای از رئوس است و E مجموعه ای از لبه ها است) بنابراین شما می خواهید این محاسبات را برای نمودارهای بزرگ به یک ارائه دهنده ابری برون سپاری کنید، اما به دلیل ماهیت پولی مشکل، می خواهید آن را به طور قابل اعتماد حل کنید – می خواهید نتیجه را بدون نیاز به بررسی مجدد تأیید کنید. اجرای الگوریتم (یعنی مطمئن شوید که ارائه دهنده واقعاً باینری را با الگوریتم اجرا کرده است). به عبارت دیگر، شما می خواهید اطمینان حاصل کنید که a یکپارچگی محاسباتی دور به مختصر تایید خروجی3.

هوم… چطوری درستش کنیم؟

تفکر مرسوم به ما پیشنهاد می کند که از هش باینری ها استفاده کنیم (در واقع هش ها جهت درستی هستند) اما زمان اجرا بدون تغییر را تضمین نمی کند (حافظه را می توان تغییر داد)، ورودی ها را می توان تغییر داد. بنابراین رویکردهای سنتی بر چگونگی محافظت از باینری و ورودی از دستکاری به هر طریقی تمرکز می‌کنند. اما همیشه جایی برای تقلب وجود دارد.

برای تسکین ما، رمزنگاران باهوش طرح‌های اثبات مختلفی ارائه کرده‌اند. در مثال ما، ارائه دهنده ابر است یک اثبات کننده که محاسبات گران قیمت را اجرا می کند و خروجی را ارائه می دهد و مدرک4 به تایید کننده (ما). یکی از جدیدترین طرح‌های اثبات پیشرفته، STARK است که به زبان ساده (من) اساساً رد اجرای محاسباتی را ثبت می‌کند که سپس به‌طور تصادفی توسط تأییدکننده نمونه‌برداری می‌شود و در برابر محدودیت‌های از پیش تعریف‌شده بررسی می‌شود.5.

امکان ادغام این ردیابی اجرا در یک برنامه Rust موجود با استفاده از برخی از کتابخانه های عمومی STARK (مانند Winterfell) وجود دارد، اما نیاز به دانستن چیزهای سطح پایین بسیار خوب دارد (برای محاسبه بسیار ساده به مثال مراجعه کنید) و مطمئن باشید که همه محاسبات ردیابی می شوند (و همه محدودیت ها اعمال می شوند).آیا خوب است که پیچیدگی های سطح پایین را انتزاع کنیم و با نحو آشنای Rust کار کنیم؟ به قاهره خوش آمدید!

قاهره

Cairo زبانی برای ایجاد برنامه هایی است که امکان تأیید محاسبات را بدون اجرای مجدد برنامه فراهم می کند. قاهره به شدت از Rust الهام گرفته شده است6 (معناشناسی حرکت و مالکیت، صفات، انواع هسته، ابزار) اما به دلیل ماهیت محاسبات قابل تأیید، ماشین آلات زیربنایی (مدل حافظه و اجرای غیر قطعی) کاملاً متفاوت است. دانش ما از Rust باید به عادت کردن سریع به نحو و کنترل جریان کمک کند، اما باید مراقب محاسبات باشیم.

نقشه ذهنی

زنگ
قاهره
هدف

rustc
قاهره
کامپایلر

محموله
اسکارب
چند ابزار (وابستگی، ساخت، تست)

cargo.toml
Scarb.toml
پیکربندی پروژه

زنگ زدگی
asdf
مدیریت زنجیره ابزار

crates.io
scarbs.xyz
رجیستری بسته

زمین بازی زنگ
cairovm.codes
گردآوری آنلاین

برپایی

من انتظار دارم Rust را قبلاً نصب کرده باشید. بیایید اسکارب را هم نصب کنیم (asdf یک راه توصیه شده است) و یک پروژه بسازید7:

$ scarb new bellman_ford_cairo

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اگر مخزن تولید شده را باز کنیم (پسوند رسمی کد VS وجود دارد8 برای برجسته کردن نحو)، ساختار آشنا را خواهیم دید.

ورودی و خروجی

بگذارید روی ورودی داده ها فکر کنیم. در زمینه داده‌های قیمت‌گذاری و جفت ارزهای مختلف، می‌توان انتظار یک نمودار پراکنده را داشت. بنابراین یک نمایش ناب استفاده از بردار چندتایی است Vec که در آن رشته ها نام ارز (مانند USD یا EUR) را نشان می دهند و f32 نرخ ارز است. همه چیز خوب به نظر می رسد به جز … به جز موارد جزئی:

هیچ رشته utf8 در قاهره وجود ندارد – رشته‌های جایگزین رشته‌های کوتاه (تا ۳۱ بایت ascii) و رشته‌های بلند (آرایه‌های بایت بایت‌های ascii) هستند.
هیچ آرایه قابل تغییری شبیه به رشد پویا وجود ندارد Vec در Rust. فقط قابل ضمیمه (و از جلو قابل پاشیدن) وجود دارد Array که می تواند به عنوان صف FIFO و Felt252Dict که می تواند به عنوان پایه ای برای پیاده سازی تعریف شده توسط کتابخانه عمل کند Vec.
هیچ شناوری در قاهره وجود ندارد. بنابراین یا می‌توانیم به اعداد نقطه ثابت تعریف‌شده توسط کتابخانه برگردیم یا شناورهای ورودی را از قبل در مقداری ثابت عدد صحیح ضرب کنیم و قسمت کسری را رها کنیم.

و همچنین ممکن است نحوه ارائه ورودی را گیر بیاوریم زیرا چیزی به نام std wrappers در libc برای خواندن stdin یا یک فایل وجود ندارد. مثل Rust in است #[no_std]. بیایید بررسی کنیم که کدام گزینه داریم:

$ scarb cairo-run –help

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یک بخش وجود دارد Arguments که می گوید که یک آرگومان برنامه “یک آرایه JSON از اعداد، اعشاری بیجنت یا آرایه های بازگشتی از آن ها” است و تابع اصلی باید یک امضای متناظر داشته باشد (مثالی وجود دارد [1, 2, [3, 4, 5]]` to `fn main(t: (u64, u64), v: Array)). بنابراین بیایید یک کد نمونه را از آن حذف کنیم lib.cairo و موارد زیر را امتحان کنید main تابع:

fn main(data: Array(u16, u16, felt252)>) {
println!(“number of edges: {}”, data.len());
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

در اینجا نام ارزها را با رمزگذاری می کنیم u16 (آنها لبه های گراف را به صورت یک جفت رئوس نشان می دهند) و felt252 نشان دهنده نرخ مبادله (وزن لبه) است. در اینجا ما باید کمی بیشتر در مورد معماری CPU که توسط برنامه Cairo انتظار می رود صحبت کنیم. کلمه ماشین 252 بیت عرض دارد و با نشان داده می شود felt252 نوع (افبازده اواینجا*تی*، به دلیل ریاضیات اساسی). بنابراین هر نوع سریال سازی انواع قاهره در نهایت از طریق نمایش داده می شود felt252. بنابراین اساساً حداکثر عددی که می توانیم به دست آوریم 252 بیت است و اگر بخواهیم شناورها را با ضرب آنها در مقداری ثابت عدد صحیح رمزگذاری کنیم، felt252 به نظر می رسد انتخاب درستی باشد

بیایید برنامه را کامپایل و اجرا کنیم (فکر کنید cargo run):

$ scarb cairo-run “[[1, 2, 300]]”

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خروجی:

number of edges: 1
Run completed successfully, returning []

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

کار می کند! خوب، در مورد خروجی چطور؟ returning [] اشاره می کند که ما می توانیم به همان روش به عنوان ورودی امتحان کنیم. انتظار داریم که الگوریتم مسیری مطابق با فرصت آربیتراژ را برگرداند. بیایید سعی کنیم:

fn main(data: Array(u16, u16, felt252)>) -> Arrayu16> {
println!(“number of edges: {}”, data.len());
array![1, 2, 3, 4] // path 1 -> 2 -> 3 -> 4
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خروجی:

number of edges: 1
Run completed successfully, returning [2837, 2841]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

چی؟؟؟ به هر حال، ممکن است اعداد دیگری مانند من در اجراهای دیگر دریافت کنید، زیرا اجرا غیر قطعی است. بیایید ابتدا بررسی کنیم array! کلان. می بینیم که این یک پلاگین تولید کد برای کامپایلر است که اساساً یک آرایه را نمونه سازی می کند ArrayTrait::new() و هر عنصری را به آن اضافه می کند. چرا ArrayTrait و نه فقط Array? حفاری بیشتر ما را به سمت آن سوق می دهد Array پیاده سازی.

ما نمی توانیم یک آشنا پیدا کنیم trait ArrayTrait اما دوباره یک ماکرو وجود دارد:

#[generate_trait] pub impl ArrayImplT> of ArrayTraitT> {

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

جستجو در پایگاه کد قاهره – و اینجاست. چه چیزی تولید می کند؟ در قاهره، تعریف روش‌ها برای یک نوع به یک ویژگی نیاز دارد، زیرا روش‌ها فقط برای یک صفت تعریف می‌شوند. بنابراین #[generate_trait] یک دیگ بخار را کاهش می دهد و یک تعریف مشخصه مربوطه را از پیاده سازی برای یک نوع ایجاد می کند. شما همیشه می توانید یک ویژگی متناظر را به صورت دستی تعریف کنید (مثلاً صف اجرا شده در کتابخانه را بررسی کنید). بنابراین روش مرتبط (یعنی به یک نمونه نیاز ندارد). new فراخوانی می شود ArrayTrait.بیایید به خروجی بازگردیم. ما خروجی را به صورت مشخص می کنیم Array. و خروجی 2 عدد به جای 4 نشان می دهد که ما با یک طرح سریال سازی فشرده سروکار داریم.بیایید این فرضیه را با یک آرایه int بزرگتر و بزرگتر آزمایش کنیم:

fn main(data: Array(u16, u16, felt252)>) -> Arrayu128> {
println!(“number of edges: {}”, data.len());
// u128::MAX but there is not MAX const
// for unsigned integers
let elem = 340282366920938463463374607431768211455;
array![elem, elem, elem, elem, elem, elem] }

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

دوباره دو عدد را برمی گرداند:

number of edges: 1
Run completed successfully, returning [2845, 2851]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

لعنتی! توجه کنید که 2851 – 2845 = 6 در حالی که قبل از آن بود 2841 – 2837 = 4 بنابراین مانند کران های تکه ای به نظر می رسد زیرا با تعداد اعداد صحیحی مطابقت دارد که امیدواریم خروجی داشته باشیم. بیایید پیدا کنیم Run completed successfully, returning در کد منبع کامپایلر به نظر می رسد که scarb این باینری را اجرا می کند. و خروجی آن است Vec.

/// The ran function return value.
#[derive(Debug, Eq, PartialEq, Clone)] pub enum RunResultValue {
/// Run ended successfully, returning the memory of the non-implicit returns.
Success(VecFelt252>),
/// Run panicked, returning the carried error data.
Panic(VecFelt252>),
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

«بازگرداندن حافظه غیر ضمنی بازده»… در اینجا اشاره – خاطره است. مدل حافظه قاهره یک آرایه غیرقابل تغییر پیوسته است. شاید این دوتا felt252 اعداد شاخص شروع و پایان در حافظه را نشان می دهند؟ scarb cairo-run –help استدلالی را پیشنهاد می کند –print-full-memory. بیایید آن را برای برنامه اصلی امتحان کنیم:

fn main(data: Array(u16, u16, felt252)>) -> Arrayu16> {
println!(“number of edges: {}”, data.len());
array![1, 2, 3, 4] }

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و اجرا

$ scarb cairo-run “[[1, 2, 300]]” –print-full-memory

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خروجی

number of edges: 1
Run completed successfully, returning [2837, 2841] Full memory: [_, 290341444919459839, 1,
…
6744073709483335, 4130, 594, 4166, 500, 1, 2, 300, 49, 1997209042069643135709344952807065910992472029923670688473712229447419591075,
0, 2463311330861459210825190905860592116187541770, 19,
1, 2, 3, 4, ]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

هوم… سعی کنیم استفاده کنیم 2837 به عنوان شاخصی برای این آرایه “پیوسته” حافظه. فقط “_” را با 0 جایگزین کنید (این فقط برای وارد کردن آن به پایتون است) و اجازه دهید آرایه حافظه را به یک مفسر پایتون تغذیه کنیم:

>>> memory = [0, 290341444919459839, 1,
…
6744073709483335, 4130, 594, 4166, 500, 1, 2, 300, 49, 1997209042069643135709344952807065910992472029923670688473712229447419591075,
0, 2463311330861459210825190905860592116187541770, 19,
1, 2, 3, 4] >>> memory[2837] 1
>>> memory[2838] 2
>>> memory[2839] 3
>>> memory[2840] 4
>>> memory[2841] Traceback (most recent call last):
File “”, line 1, in module>
IndexError: list index out of range

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خوب. حداقل اکنون می فهمیم که این دو عدد در خروجی به چه معنا هستند – آنها شاخص های شروع و پایان خروجی را در یک آرایه حافظه نشان می دهند. خوب، اما بیایید هدف اولیه خود را به خاطر بسپاریم – باید محاسبات را برون سپاری کنیم و سپس بتوانیم آن را تأیید کنیم. شاید برای آن چیز راه راحت تری برای دریافت خروجی وجود داشته باشد؟9

پروورز

چندین پروور برای STARK ها و چند بسته بندی مناسب برای برنامه های قاهره وجود دارد. من می خواهم از Stone همانطور که Starknet استفاده می کند استفاده کنم. بیایید سعی کنیم برنامه خود را اثبات و تأیید کنیم. readme یک مثال ارائه می دهد.

Prover به یک حافظه خالی، یک فایل ردیابی و یک AIR نیاز دارد10 ورودی بعد از اجرا اما cairo-run cli این استدلال ها را افشا نمی کند.

ما هنوز بررسی نکرده ایم که “باینری” کامپایل شده ما چگونه به نظر می رسد. بازرسی کنیم target فهرست راهنما. آن شامل bellman_ford_cairo.sierra.json. این برنامه ما به عنوان یک نمایندگی میانی سیرا است، مانند LLVM IR فکر کنید. من وارد هیچ جزئیاتی نمی شوم، فقط مقالات Mathieu Saugier را توصیه می کنم

ما نمی توانیم یک فایل json را اجرا کنیم. باید در یک هدف کامپایل شود:

اگه چک کنیم چیه cairo-run استفاده می کند، Rust vm است. بیایید مخزن vm را کلون کنیم و اجرا کنیم

$ cargo install –bin cairo1-run –path cairo1-run

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

سپس یک مترجم cairo vm دریافت می کنیم و اجازه دهید این مفسر را در مخزن خود اجرا کنیم:

$ cairo1-run src/lib.cairo \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

باید مشخص کنیم:

چیدمان همانطور که به یک خروجی نیاز داریم

ورودی عمومی (گراف ما) به‌عنوان ارائه‌دهنده باید تأیید کند که او یک مسیر بهینه برای گراف خاص را می‌داند و نه اینکه یک مسیر بهینه برای یک گراف ناشناس را می‌شناسد. به عبارت دیگر ورودی ما عمومی است.

اگر دستور بالا را اجرا کنیم با یک خطا مواجه می شویم:

thread ‘main’ panicked at cairo1-run/src/main.rs:181:18:
called `Result::unwrap()` on an `Err` value: Failed to find development corelib.
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

بنابراین 1) نوعی پیوند وجود دارد 2) اگر یک corelib توسعه وجود دارد، پس یک نسخه انتشار وجود دارد. یک دستورالعمل در README برای پروژه‌های scarb وجود دارد – می‌توانیم یک برنامه Sierra را به مترجم ارائه کنیم و اضافه کنیم.

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

به Scarb.toml11.

پس بیایید تلاش کنیم

$ scarb –release build
$ cairo1-run target/release/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و می گیریم… Error: Runner(MissingMain). >_

$ scarb build
$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خطا Error: IlegalInputValue. آه، باید یک ورودی ارائه کنیم:

$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode \
–args “[[1, 2, 300]]”

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

دوباره در readme “فقط مجاز است Array به عنوان مقدار بازگشتی و ورودی در حالت اثبات”. خوب، بیایید کد را تغییر دهیم:

fn main(data: Arrayfelt252>) -> Arrayfelt252> {
println!(“number of edges: {}”, data.len());
array![1, 2, 3, 4] }

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

$ scarb build
$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode \
–args “[1 2 300]”

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و کار می کند!!! هورا!! دو استدلال مفید دیگر وجود دارد: –print_output و –args_file که امکان خروجی قابل خواندن و نمودار ورودی بزرگ را فراهم می کند.

$ cat graph.txt
[1 2 300] $ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode \
–args_file graph.txt \
–print_output
[DEBUG] (raw: 1997209042069643135709344952807065910992472029923670688473712229447419591075)
[DEBUG] (raw: 0)
[DEBUG] number of edges: 3
(raw: 2463311330861459210825190905860592116187542282)
[DEBUG] (raw: 19 )

Program Output : [1 2 3 4]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

یییییییی! قبل از اتمام این بخش، اجازه دهید حالت انتشار را اصلاح کنیم. همانطور که نمایه توسعه دهنده کار می کند، به نظر می رسد که در پروفایل ها تفاوت وجود دارد. به نظر می رسد که sierra-replace-ids بر این امر تأثیر می گذارد.

که در Scarb.toml ما داریم:

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

و

$ scarb –release build
$ cairo1-run target/release/bellman_ford_cairo.sierra.json \
–layout=small \
–air_public_input=public_input.json \
–air_private_input=private_input.json \
–trace_file=trace.bin \
–memory_file=memory.bin \
–proof_mode \
–args_file graph.txt \
–print_output
[DEBUG] (raw: 1997209042069643135709344952807065910992472029923670688473712229447419591075)
[DEBUG] (raw: 0)
[DEBUG] number of edges: 3
(raw: 2463311330861459210825190905860592116187542282)
[DEBUG] (raw: 19 )

Program Output : [1 2 3 4]

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

خروجی یکسان است. توجه داشته باشید [DEBUG] خروجی مربوط است cairo1-run. اکنون در مخزن باید فایل هایی داشته باشیم:

memory.bin
private_input.json
public_input.json
trace.bin

به نظر می رسد که ما تمام مصنوعات را برای اثبات اثبات داریم.

اثبات

من یک پروور سنگی آماده برای استفاده (و سازگار با arm64!) با Docker آماده کرده ام (بنابراین شما کامپایل پروور را به من برون سپاری کردید و من ساختن تصویر Docker را به روشی قابل اعتماد به Github برون سپاری کردم :)).

سپس در مخزن ما اجرا کنید:

$ docker run –rm -it -v $(pwd):/tmp maksimryndin/starknet-stone:latest prover \
-logtostderr \
–out_file=/tmp/proof.json \
–private_input_file=/tmp/private_input.json \
–public_input_file=/tmp/public_input.json \
–prover_config_file=/tmp/cpu_air_prover_config.json \
–parameter_file=/tmp/cpu_air_params.json

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

فایل ها cpu_air_prover_config.json و cpu_air_params.json من از تست Stone e2e گرفتم.

خروجی:

what(): src/starkware/stark/stark.cc:187: Fri parameters do not match stark degree bound. Expected FRI degree from FriParameters: 8192. STARK: 131072
Stack trace (most recent call last):

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

آیا هیچ ایده ای به معنای آن دارید؟ من نه :)). بیایید سعی کنیم کد منبع پروور را بررسی کنیم. شماره 131072 نشان دهنده درجه واقعی است – trace_length ویژگی از Air کلاسی که به نظر می‌رسد از عبارت نمونه‌سازی شده است. بیانیه ترکیبی از ورودی های عمومی و خصوصی، فایل پارامترهای هوا است. 8192 نشان دهنده انتظاری است که از آن محاسبه می شود cpu_air_params.json با عملکرد GetFriExpectedDegreeBound. مثال cpu_air_params.json است:

{
“field”: “PrimeField0”,
“stark”: {
“fri”: {
“fri_step_list”: [
0,
4,
3
],
“last_layer_degree_bound”: 64,
“n_queries”: 18,
“proof_of_work_bits”: 24
},
“log_n_cosets”: 4
},
“use_extension_field”: false
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

بنابراین GetFriExpectedDegreeBound مانند آن را محاسبه می کند 8192 = last_layer_degree_bound * 2.pow(0) * 2.pow(4) * 2.pow(3) یا در پایه لگاریتمی 2 عبارت: log(trace_length) = log(last_layer_degree_bound) + ∑fri_step_list (این تقریباً همان یادداشت است). این خطا در آزمایش برابری بین درجات واقعی و مورد انتظار افزایش می یابد. برای تنظیم پیکربندی هوا به روشی معنی‌دار، باید تئوری‌هایی را یاد بگیریم، اما فعلاً اجازه دهید یک مرحله FRI اضافی 4 را برای حفظ معادله اضافه کنیم:

{
“field”: “PrimeField0”,
“stark”: {
“fri”: {
“fri_step_list”: [
0,
4,
3,
4
],
“last_layer_degree_bound”: 64,
“n_queries”: 18,
“proof_of_work_bits”: 24
},
“log_n_cosets”: 4
},
“use_extension_field”: false
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اگر دوباره پروور را اجرا کنیم (مطمئن شوید که حافظه و مسیرهای ردیابی را در آن به روز کنید private_input.json، خروجی می دهد:

I0730 10:39:04.829474 1 profiling.cc:58] Prover started
I0730 10:39:05.030071 1 memory_cell.inl:121] Filled 12256 vacant slots in memory: 171 holes and 12085 spares.
I0730 10:39:19.560891 1 stark.cc:425] Trace cells count:
Log number of rows: 17, first trace n_cols: 23, interaction trace n_cols: 2, Total trace cells: 3276800
I0730 10:40:03.643604 1 prover_main_helper_impl.cc:178] Byte count: 88424
Hash count: 1344
Commitment count: 6
Field element count: 1419
Data count: 1
I0730 10:40:03.658634 1 profiling.cc:85] Prover finished in 58.8287 sec

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

توجه داشته باشید که تعداد کل ردیف ها (2.pow(17)) است 131072. و ما می توانیم محاسبات را تأیید کنیم:

$ docker run –rm -it -v $(pwd):/tmp maksimryndin/starknet-stone:latest verifier \
-logtostderr \
–in_file=/tmp/proof.json
I0730 11:14:42.393836 1 cpu_air_verifier_main.cc:39] Proof verified successfully.

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

نتیجه

در این مقاله با محاسبات قابل تأیید با قاهره آشنا شدیم، یک برنامه پایه را گردآوری کردیم، ورودی/خروجی برنامه‌های قاهره را بررسی کردیم و برنامه اصلی را اثبات/تأیید کردیم. در نتیجه مسیر آزمون و خطای ما، ابزارهای Wrapper مناسب به وجود آمدند که در ادامه از آنها استفاده خواهیم کرد. تمام کد منبع در مخزن است.

اکنون وقت آن است که آن را هضم کنید و چیزهای جالبی را از منابع 8 – 12 یاد بگیرید (ترتیب یک روش توصیه شده است).

در مقاله(های) بعدی، الگوریتم بلمن-فورد را پیاده سازی می کنیم، سعی می کنیم طرح اثبات را بشکنیم/به آن حمله کنیم، پیچیدگی زمانی تایید را بررسی کنیم، هزینه ای بیش از نسخه Rust.

منابع

کتاب قاهره (در ژوئیه 2024 قابل دسترسی است)

معرفی نکات در زبان برنامه نویسی قاهره (در جولای 2024 قابل دسترسی است)

اسناد Cairo0 (در ژوئیه 2024 قابل دسترسی است)

Stwo Prover: نسل بعدی مقیاس‌بندی STARK اینجاست (در جولای 2024 قابل دسترسی است)

زیر کاپوت Cairo 1.0: Exploring Sierra (در ژوئیه 2024 قابل دسترسی است)

سیستم‌های دانش صفر که می‌توانید به آن‌ها اعتماد کنید (در ژوئیه 2024 قابل دسترسی است)

Unleashing the Power of Stone Prover (در ژوئیه 2024 قابل دسترسی است)

STARK Math: The Journey Begins (در ژوئیه 2024 قابل دسترسی است)

Arithmetization I (در ژوئیه 2024 قابل دسترسی است)

Arithmetization II (در ژوئیه 2024 قابل دسترسی است)

آزمون درجه پایین (در جولای 2024 قابل دسترسی است)

Anatomy of a STARK (در جولای 2024 قابل دسترسی است)

عبارت “برون سپاری قابل اعتماد محاسبات” به زبان لورک اعتبار دارد. از داوطلبان دعوت می شود تا مقاله ای با عنوان “Lurk for List/Clojure develops” ایجاد کنند. مقایسه هر دو زبان برای محاسبات قابل تایید جالب خواهد بود. ↩

در این مقالات ما اصلاً برای وب 3 طراحی نشده ایم، اما آنها در تلاش مداوم من برای استفاده از فرصت های آربیتراژ در کریپتو هستند. برای علاقه مندان گروه تلگرامی وجود دارد که جستجوگران MEV را متحد می کند. ↩

یکی دیگر از موارد استفاده برجسته در زمینه web3: ما می‌توانیم برخی از محاسبات را از روی زنجیره به خارج از زنجیره به روشی غیرقابل اعتماد منتقل کنیم (Starknet در این زمینه وجود دارد). ↩

یک تأیید کننده در واقع در برابر a محافظت می شود محاسباتی محدود شده است اثبات کنید پس دلیل محکمی نیست، بلکه برهان معرفت اما برای جلوگیری از پیچیدگی بیش از حد، به کلمه “اثبات” می پردازم. ↩

علاوه بر یکپارچگی محاسباتی، می‌تواند نیاز (اختیاری) دیگری به دانش صفر (ZK) وجود داشته باشد، زمانی که ارائه‌دهنده اطلاعاتی در مورد ورودی فاش نمی‌کند. سوراخ خرگوش عمیق است که مقاله واحدی وجود ندارد – مطالعه پیشنهادی را دنبال کنید. به هر حال، بسیاری از ارائه دهندگان STARK هنوز (ژوئیه 2024) ZK کامل را پیاده سازی نمی کنند، به عنوان مثال Winterfell، miniSTARK، Stark Platinum Prover. همچنین به مقاله مراجعه کنید. ↩

در واقع، Cairo0 وجود دارد که اولین نسخه از زبانی برای محاسبات قابل تأیید با STARK بود. این اساسا یک زبان اسمبلی برای STARK CPU است. ممکن است هنوز در برخی پروژه ها با آن مواجه شوید. در این مقاله و به طور کلی، ذکر قاهره به معنای صحبت از قاهره1، زبانی شبیه زنگار است. ↩

به نظر می رسد که جدایی بین جعبه های دوتایی و کتابخانه ای در قاهره از طریق گنجاندن / حذف main عملکرد در lib.cairo. ↩

مطمئن شوید که Cairo1 را از Starkware Industries انتخاب کرده اید، با انتشار پیش بینی شده Cairo 2.7.0، افزونه لوگو را دریافت می کند. ↩

نکاتی نیز وجود دارد که برای اولین بار در Cairo0 معرفی شدند و هنوز در Cairo1 در کامپایلر رسمی پیاده سازی نشده اند. و احتمالاً می توانند امکان تعامل بیشتر با دنیای بیرون را فراهم کنند. ↩

مقالات ریاضی استارک در مورد حساب کردن را ببینید. ↩

اندازه گیری گاز باید از یک اثبات کننده در برابر حلقه های نامحدود محافظت کند زیرا روابط بین یک اثبات کننده و یک تأیید کننده غیر قابل اعتماد است. اما در حال حاضر هیچ ایده ای ندارم که چرا “cairo1-run هنگام دویدن از بررسی بنزین خودداری می کند”. ↩

$ scarb new bellman_ford_cairo

$ scarb cairo-run --help

fn main(data: Array(u16, u16, felt252)>) {
    println!("number of edges: {}", data.len());
}

$ scarb cairo-run "[[1, 2, 300]]"

number of edges: 1
Run completed successfully, returning []

fn main(data: Array(u16, u16, felt252)>) -> Arrayu16> {
    println!("number of edges: {}", data.len());
    array![1, 2, 3, 4] // path 1 -> 2 -> 3 -> 4
}

number of edges: 1
Run completed successfully, returning [2837, 2841]

#[generate_trait]
pub impl ArrayImplT> of ArrayTraitT> {

fn main(data: Array(u16, u16, felt252)>) -> Arrayu128> {
    println!("number of edges: {}", data.len());
    // u128::MAX but there is not MAX const 
    // for unsigned integers
    let elem = 340282366920938463463374607431768211455; 
    array![elem, elem, elem, elem, elem, elem]
}

number of edges: 1
Run completed successfully, returning [2845, 2851]

/// The ran function return value.
#[derive(Debug, Eq, PartialEq, Clone)]
pub enum RunResultValue {
    /// Run ended successfully, returning the memory of the non-implicit returns.
    Success(VecFelt252>),
    /// Run panicked, returning the carried error data.
    Panic(VecFelt252>),
}

fn main(data: Array(u16, u16, felt252)>) -> Arrayu16> {
    println!("number of edges: {}", data.len());
    array![1, 2, 3, 4]
}

$ scarb cairo-run "[[1, 2, 300]]" --print-full-memory

number of edges: 1
Run completed successfully, returning [2837, 2841]
Full memory: [_, 290341444919459839, 1, 
... 
6744073709483335, 4130, 594, 4166, 500, 1, 2, 300, 49, 1997209042069643135709344952807065910992472029923670688473712229447419591075, 
0, 2463311330861459210825190905860592116187541770, 19, 
1, 2, 3, 4, ]

>>> memory = [0, 290341444919459839, 1, 
... 
6744073709483335, 4130, 594, 4166, 500, 1, 2, 300, 49, 1997209042069643135709344952807065910992472029923670688473712229447419591075, 
0, 2463311330861459210825190905860592116187541770, 19, 
1, 2, 3, 4]
>>> memory[2837]
1
>>> memory[2838]
2
>>> memory[2839]
3
>>> memory[2840]
4
>>> memory[2841]
Traceback (most recent call last):
  File "", line 1, in module>
IndexError: list index out of range

$ cargo install --bin cairo1-run --path cairo1-run

$ cairo1-run src/lib.cairo \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode

thread 'main' panicked at cairo1-run/src/main.rs:181:18:
called `Result::unwrap()` on an `Err` value: Failed to find development corelib.
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[cairo]
enable-gas = false

$ scarb --release build
$ cairo1-run target/release/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode

$ scarb build
$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode

$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode \
    --args "[[1, 2, 300]]"

fn main(data: Arrayfelt252>) -> Arrayfelt252> {
    println!("number of edges: {}", data.len());
    array![1, 2, 3, 4]
}

$ scarb build
$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode \
    --args "[1 2 300]"

$ cat graph.txt
[1 2 300]
$ cairo1-run target/dev/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode \
    --args_file graph.txt \
    --print_output
[DEBUG]                                 (raw: 1997209042069643135709344952807065910992472029923670688473712229447419591075) 
[DEBUG]                                 (raw: 0)
[DEBUG] number of edges: 3
                (raw: 2463311330861459210825190905860592116187542282)
[DEBUG]                                 (raw: 19                             )

Program Output : [1 2 3 4]

[cairo]
enable-gas = false
sierra-replace-ids = false

$ scarb --release build
$ cairo1-run target/release/bellman_ford_cairo.sierra.json \
    --layout=small \
    --air_public_input=public_input.json \
    --air_private_input=private_input.json \
    --trace_file=trace.bin \
    --memory_file=memory.bin \
    --proof_mode \
    --args_file graph.txt \
    --print_output
[DEBUG]                                 (raw: 1997209042069643135709344952807065910992472029923670688473712229447419591075) 
[DEBUG]                                 (raw: 0)
[DEBUG] number of edges: 3
                (raw: 2463311330861459210825190905860592116187542282)
[DEBUG]                                 (raw: 19                             )

Program Output : [1 2 3 4]

$ docker run --rm -it -v $(pwd):/tmp maksimryndin/starknet-stone:latest prover \
    -logtostderr \
    --out_file=/tmp/proof.json \
    --private_input_file=/tmp/private_input.json \
    --public_input_file=/tmp/public_input.json \
    --prover_config_file=/tmp/cpu_air_prover_config.json \
    --parameter_file=/tmp/cpu_air_params.json

  what():  src/starkware/stark/stark.cc:187: Fri parameters do not match stark degree bound. Expected FRI degree from FriParameters: 8192. STARK: 131072
Stack trace (most recent call last):
<...>

{
    "field": "PrimeField0",
    "stark": {
        "fri": {
            "fri_step_list": [
                0,
                4,
                3
            ],
            "last_layer_degree_bound": 64,
            "n_queries": 18,
            "proof_of_work_bits": 24
        },
        "log_n_cosets": 4
    },
    "use_extension_field": false
}

{
    "field": "PrimeField0",
    "stark": {
        "fri": {
            "fri_step_list": [
                0,
                4,
                3,
                4
            ],
            "last_layer_degree_bound": 64,
            "n_queries": 18,
            "proof_of_work_bits": 24
        },
        "log_n_cosets": 4
    },
    "use_extension_field": false
}

I0730 10:39:04.829474     1 profiling.cc:58] Prover started
I0730 10:39:05.030071     1 memory_cell.inl:121] Filled 12256 vacant slots in memory: 171 holes and 12085 spares.
I0730 10:39:19.560891     1 stark.cc:425] Trace cells count:
Log number of rows: 17, first trace n_cols: 23, interaction trace n_cols: 2, Total trace cells: 3276800
I0730 10:40:03.643604     1 prover_main_helper_impl.cc:178] Byte count: 88424
Hash count: 1344
Commitment count: 6
Field element count: 1419
Data count: 1
I0730 10:40:03.658634     1 profiling.cc:85] Prover finished in 58.8287 sec

$ docker run --rm -it -v $(pwd):/tmp maksimryndin/starknet-stone:latest verifier \
    -logtostderr \
    --in_file=/tmp/proof.json
I0730 11:14:42.393836     1 cpu_air_verifier_main.cc:39] Proof verified successfully.