Skip to content
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

Closed
wants to merge 14 commits into from
Closed

Implement hints documentation #378

wants to merge 14 commits into from

Conversation

Iwueseiter
Copy link

Resolves #327

Comment on lines 137 to 138
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.
Copy link
Contributor

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.

Copy link
Contributor

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

# 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.
Copy link
Contributor

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

Comment on lines 14 to 26
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.

Copy link
Contributor

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 }%

Comment on lines 44 to 45
### 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.
Copy link
Contributor

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)

Comment on lines 60 to 76
### 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.
Copy link
Contributor

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?

Comment on lines 78 to 91
### 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*.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Untrue

Comment on lines 93 to 105
### 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*.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Untrue

Comment on lines 107 to 125
## 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.
Copy link
Contributor

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


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.
Copy link
Contributor

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

Comment on lines 131 to 132
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.

Copy link
Contributor

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.

@rodrigo-pino
Copy link
Contributor

Hey @Iwueseiter how is it going, let me know if I can help with anything

@Iwueseiter
Copy link
Author

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.
Copy link
Contributor

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.

Comment on lines +7 to +8
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. 
Copy link
Contributor

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"

Comment on lines +41 to +42
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.
Copy link
Contributor

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

Copy link
Contributor

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",
Copy link
Contributor

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.

Copy link
Author

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.

@Iwueseiter Iwueseiter closed this by deleting the head repository May 13, 2024
@rodrigo-pino rodrigo-pino mentioned this pull request May 14, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Hints Documentation
3 participants