-
Notifications
You must be signed in to change notification settings - Fork 50
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement hints documentation #378
Conversation
docs/docs/vm-fundamentals/hints.md
Outdated
Sequencers and provers are tools used in formal verification, a process of accurately proving the correctness of programs. | ||
Applying hints in the Cario virtual machine leverages the execution trace and uses it to guide the verification process. Integration of hints with the Cairo VM's execution trace and verification tools enables developers to guide and customize the verification process, improving the efficiency and effectiveness of formal verification for smart contracts. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Could you point out the resource you used for this part? I'm not sure hints are related to formal verification techniques.
Also I would like to add in this documentation some information regarding the way we implement hints. You can use the content from https://github.com/NethermindEth/cairo-vm-go/blob/main/pkg/hintrunner/zero/README.md as reference.
… hint_examples_docs
… hint_examples_docs
docs/package-lock.json
Outdated
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
De-commit this file please
docs/docs/vm-fundamentals/hints.md
Outdated
# Hints | ||
# Hint | ||
## HINTS IN CAIRO VIRTUAL MACHINE | ||
Hints in Cairo are pieces of Python code only seen and executed by the prover and are not included in the bytecode. They instruct the prover on how to handle nondeterministic instructions. These nondeterministic instructions are programs that have different outcomes at execution. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Only executed by the sequencer, and are not known during proving time
docs/docs/vm-fundamentals/hints.md
Outdated
In Cairo, execution hints use the *hint* keyword, followed by a *hint name* and *a value*. | ||
|
||
@example: | ||
|
||
```cairo | ||
func main() -> felt*: | ||
// some code here | ||
hint memory_behavior = MemoryBehavior.Sequential; | ||
// more code here | ||
``` | ||
The memory_behavior hint informs the Cairo compiler that the code following the hint | ||
sequentially accesses memory. | ||
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Are you sure? I think hints are enclosed in a block defined by the following symbols %{
and }%
docs/docs/vm-fundamentals/hints.md
Outdated
### MEMORY HINTS | ||
These hints are memory aids that provide additional information to the prover on computing values in the Cairo program. They are functional when provers can't handle certain expressions implicitly. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
That is not actual essence of hints. Cairo is a non-deterministic language, meaning, imagine a Turing Machine where you can visit different states at the same time (in theory). In practice, that's super expensive and can grow exponentially in memory. Hints are used to avoid all of this, and "hint" the VM to which state it should jump into (of the many possible)
docs/docs/vm-fundamentals/hints.md
Outdated
### RESOURCE MANAGEMENT HINTS | ||
These hints provide additional information on managing resources like memory and stack space. They help the virtual Machine optimize resource usage and prevent resource leaks. Resource management hints need to be applied judiciously and only when necessary. | ||
|
||
@example: | ||
|
||
``` cairo | ||
%{__resource_management_hint__ memory_pages_allocated = 10 %} | ||
[ap] = 0, ap++; | ||
for i in range(10): | ||
[ap] = i, ap++; | ||
%{__resource_management_hint__ memory_pages_allocated = %} | ||
for i in range(5): | ||
[ap] = i * i, ap++; | ||
``` | ||
|
||
The first hint will ensure the program has *`10`* memory pages to execute the first loop that stores *`10`* integers on the stack. | ||
The second hint will ensure the program does not use more memory than necessary. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is not true. What source do you have?
docs/docs/vm-fundamentals/hints.md
Outdated
### DEBUGGING HINTS | ||
They aid in troubleshooting and debugging Cairo programs. They identify and diagnose issues in the program. It debugs errors related to memory access and manipulation. Debugging hints are deleted from the program once the debugging is complete. | ||
|
||
@example: | ||
|
||
```cairo | ||
%{ | ||
import os | ||
print("Debugging hint: Memory at address {}".format(memory[ap - 1])) | ||
%} | ||
[ap - 1] = 42, ap++; | ||
``` | ||
|
||
The debugging hint prints the value stored in memory and the address stored in the register *ap - 1*. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Untrue
docs/docs/vm-fundamentals/hints.md
Outdated
### SECURITY HINTS | ||
Security hints in Cairo VM provide security features and protections for programs through directions for input validation, access control, or encryption to safeguard against potential vulnerabilities and threats. | ||
|
||
@example: | ||
|
||
```cairo | ||
%{ | ||
import cairo | ||
cairo.set_max_stack_size(1024) | ||
%} | ||
[ap] = 42, ap++; | ||
``` | ||
The security hint sets the maximum stack size for the program to *1024*. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Untrue
docs/docs/vm-fundamentals/hints.md
Outdated
## HOW HINTS WORK IN CAIRO VIRTUAL MACHINE | ||
|
||
1. **Execution Trace**: When executing a smart contract( a digital agreement signed and stored on a blockchain network, which executes automatically when the contract's terms and conditions (T&C) are satisfied) written in Cairo, the VM generates an execution trace. This trace contains information about the sequence of instructions executed, the values of variables at different points, and the instructions or function calls of an important program that are executed or evaluated. | ||
|
||
2. **Hinting Mechanism**: Cairo VM gives a procedure for developers to provide hints to the verification tool. These hints can come in various forms, such as assertions, assumptions, or annotations within the Cairo code. | ||
|
||
3. **Integration with Verification Tools**: Cairo VM integrates with external verification tools that analyze the execution traces and verify the features of the smart contracts. These tools can include assumptions provers, model checkers, or symbolic execution engines. | ||
|
||
4. **Guiding Verification with Hints**: During the verification process, the hints provided by developers serve as guides for analysis performed by the verification tools. | ||
|
||
For example: | ||
- **Assertion Checking**: Developers or testers use specific statements, known as assertions, to validate the expected behavior of a program or system. Verification tools check whether these assertions fail during the analysis. | ||
|
||
- **Invariant Detection**: Hints may guide the tool to identify the uniformity of loop iteration or other program properties responsible for the accuracy of the contract. The tool then attempts to prove these properties using the execution trace. | ||
|
||
- **Path Exploration**: Hints can help the tools explore specific paths or branches of the program that are considered fit for verification. It helps in focusing the analysis on relevant parts of the code. | ||
|
||
|
||
5. **Feedback Loop**: As the verification tool analyzes the execution trace and attempts to prove properties guided by the hints, it may encounter challenges or limitations. In such cases, feedback mechanisms allow developers to refine their hints or modify the code to improve the chances of successful verification. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This seems awfully generic, and untrue
docs/docs/vm-fundamentals/hints.md
Outdated
|
||
Sequencers in Cairo are responsible for organizing the execution of transactions, managing instruction ordering and dependencies, exploiting multiple processors, and ensuring the integrity of the program's state throughout the execution process. | ||
|
||
Provers attempt to mathematically prove the correctness of a program concerning a given specification. The prover uses these hints to access the program's behavior and verify that it satisfies specified properties and constraints. In this context, hints could guide the prover towards particular properties or parts of the codebase that are relevant to the proof. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Could you tell me what source you have? I don't think this to be correct
docs/docs/vm-fundamentals/hints.md
Outdated
Sequencers in Cairo are responsible for organizing the execution of transactions, managing instruction ordering and dependencies, exploiting multiple processors, and ensuring the integrity of the program's state throughout the execution process. | ||
|
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This seems awfully generic. Sequencers are the actors that produces blocks by executing transaction and updating the blockchain state. Everything else seems overly ambiguous to be of any use.
Hey @Iwueseiter how is it going, let me know if I can help with anything |
I pushed some commits to the PR, you can look at it and leave a review. |
|
||
### WHY HINTS RUN ON SEQUENCERS/ PROVERS AND NOT VERIFIERS | ||
|
||
The verifier in Cairo is responsible for ensuring that a program attaches safety and accuracy features. It checks that the program satisfies limitations such as memory safety, type safety, and functional correctness. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is not true, the verifier doesn't do this. Please, let us not put anything which is not right. As a rule of a thumb if you don't know about it then don't write it. Let's discuss first if it is true or not. We have community calls every Wednesday if you want to pop in and ask all questions you might have.
Hints in Cairo are pieces of Python code only executed by the sequencer and are not included in the bytecode. They instruct the prover on how to handle nondeterministic instructions. These nondeterministic instructions are programs that have different outcomes at execution. | ||
Hints are guides that developers can provide to the Cairo virtual machine to optimize execution or provide additional information about the program. These hints help improve performance or help the VM make better decisions during the execution of programs. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This part is partially correct, I understand is a complex subject and that you want to explain the "why" of the hints. Let's reduce this paragraph to something simpler: "Hints are used to help the Virtual Machine determine the next path of execution it should take"
Example: | ||
The *'random'* instruction generates a random number, which can be different each time of instruction execution. The verifier cannot implement these instructions, as it would require access to nondeterministic information, which would beat the purpose of the zero-knowledge proof. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think this random instruction exists
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Regarding this file, it should be actually included. It was so different from the old one that I thought it was a miss addition. This begs the question why did it changed so much
@@ -18,6 +18,7 @@ | |||
"@docusaurus/preset-classic": "2.4.1", | |||
"@mdx-js/react": "^1.6.22", | |||
"clsx": "^1.2.1", | |||
"docusaurus": "^1.14.7", |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't understand why do you added this extra dependency here? This must be the reason why the lockfile is very different.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I didn't add up any dependency separately, I installed docusaurus. And that should be why they are differences.
Resolves #327