herodotusdev / integrity Goto Github PK

Good resources:

• https://blog.lambdaclass.com/how-to-code-fri-from-scratch/
• https://eprint.iacr.org/2022/1216.pdf
• ethSTARK 3.9

Reference: https://github.com/starkware-libs/cairo-lang/tree/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/fri

This issue will be further divided in more issues.

Described in ethSTARK paper 3.7 and 3.8.
This requires parsing StarkWare's autogenerated files to cairo1.

Example autogenerated file (small layout): https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/air/layouts/small/autogenerated.cairo

Reference: https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/stark.cairo#L297
Note that in the referencing implementation verification is only implemented for 2 composition polynomial columns.

Also note that there are some details described in various paper that are actually not implemented in practice:

• No degree adjustment is happening
• The OODS point is from the native field and not an extension field (the native field is big enough)

This task involves the development of the public_input_hash function, which is essential for computing the hash of the public input used as the initial seed in the Fiat-Shamir heuristic. The function's primary objective is to ensure a secure and accurate hashing process, incorporating various elements of the public input. This includes handling the main page hash, utilizing different hashing algorithms like Blake2s, and processing various public input parameters.
Reference: https://vscode.dev/github/Okm165/cairo-lang/blob/v0.11.0-run-proof-sw-patch/cairo-lang-0.11.0/starkware/cairo/stark_verifier/air/public_input.cairo#L59

The goal of this task is to implement the public_input_validate function. This function is crucial for verifying that the public input represents a valid Cairo statement, ensuring there exists a memory assignment and a valid corresponding program trace that satisfies the public memory requirements. Key aspects of this validation include checking range configurations, validating the layout, and ensuring the segments for the builtins do not exceed their maximum length. This task requires careful attention to detail to guarantee the function accurately assesses the validity of Cairo statements, while also noting that it does not cover validations related to public memory, which should be handled separately.
Reference: https://vscode.dev/github/Okm165/cairo-lang/blob/v0.11.0-run-proof-sw-patch/cairo-lang-0.11.0/starkware/cairo/stark_verifier/air/layouts/all_cairo/public_verify.cairo#L79

Is cairo 1 currently supported? If so can you show an example for verifying a proof obtained here?

https://github.com/starkware-libs/stone-prover/blob/main/README.md?plain=1#L72-L77
https://github.com/starkware-libs/stone-prover/blob/main/e2e_test/Cairo/fibonacci.cairo

Using small layout, error in verifier:

Currently trying to verify such proof panics with:

thread 'main' panicked at runner/src/main.rs:78:13:
[155785504329508738615720351733824384887]

Where 155785504329508738615720351733824384887 = u32_sub Overflow

Using recursive layout

thread 'main' panicked at runner/src/main.rs:78:13:
[97607197389754475647955493984074166371]

97607197389754475647955493984074166371 = Invalid final_pc

Verification command:

./integrity/target/release/runner integrity/target/dev/cairo_verifier.sierra.json < result/proof.json

Implement the blake2s hashing function and make sure there is compatibility with the cairo0 StarkWare's implementation.
The work started on https://github.com/HerodotusDev/cairo-blake2s should be migrated to this repo.

Official spec for reference: https://www.blake2.net

Described in ethSTARK paper 3.11.3.

Reference: https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/proof_of_work.cairo

Reference: https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/channel.cairo

Reference: https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/cairo_verifier/layouts/all_cairo/cairo_verifier.cairo#L55

Description

This task focuses on understanding the functioning of bootloaders and managing tasks within a scheduler. The primary objective is to implement a recursive proofs scheme. The implementation will be carried out in two main phases:

1. Cairo Verifier Integration: The first step involves integrating the Cairo verifier into our system. This will lay the groundwork for handling recursive proofs and ensuring that the system can effectively verify each step of the recursion.

2. Progressive Recursion Implementation: After the Cairo verifier is in place, the next phase is to develop and integrate the recursion mechanism.

Goals

• Gain a deeper understanding of bootloader functionality.
• Efficiently manage tasks within the scheduler.
• Integrate the Cairo verifier as the foundation for recursive proofs.

Here is the repo: https://github.com/neotheprogramist/cairo-playground

We are initiating a task to develop a validation function for StarkConfig objects. This function, to be named stark_config_validate, will be responsible for ensuring the integrity and correctness of StarkConfig objects. It will include a series of checks and validations tailored to our specific operational and security needs.
Reference: https://vscode.dev/github/Okm165/cairo-lang/blob/v0.11.0-run-proof-sw-patch/cairo-lang-0.11.0/starkware/cairo/stark_verifier/core/config.cairo#L42

It's crucial to make sure we have hash function compatibility.

Reference: https://github.com/starkware-libs/cairo-lang/blob/9e6e0e96d208608d98635ccfad5b26285c4936e1/src/starkware/cairo/stark_verifier/core/vector_commitment.cairo

The objective of this task is to develop the generate_queries function, a crucial component for sampling random queries from the verifier in cryptographic protocols. This function will play a vital role in generating query indices and ensuring the randomness and integrity of the sampling process. It involves intricate handling of the sampling mechanism, including the efficient generation of random query indices within specified bounds and the subsequent sorting and deduplication of these queries.
Reference: https://vscode.dev/github/Okm165/cairo-lang/blob/v0.11.0-run-proof-sw-patch/cairo-lang-0.11.0/starkware/cairo/stark_verifier/core/queries.cairo#L11