Add Core Hints to the VM

[rodrigo-pino]

We need to define all possible Hints applicable a program execution. The following is a list extracted from the Rust CASM compiler which defines all Core hints. Hints will be implemented in pkg/hintrunner/hint.go. AllocSegment and TestLessThan are already implemented as use examples. Tools that allow abstractions from the VM have been implemented as well, so minimal understanding of the VM is required. Of course if the hint directly affects the VM this may not apply.

The workflow is as follows: a contributor asks to get assigned one of the not-implemented hints and a dedicated issue is created. Once the issue is solved, the hint is marked accordingly.

Core Hints

• AllocSegment Create a Hint Layout for the VM #31
  • Params: dst: CellRef
• TestLessThanOrEqual #36 Feat: Implement TestLessThanOrEqual #102
  • Params: lhs: ResOperand, rhs: ResOperand, dst: CellRef
• TestLessThan Create a Hint Layout for the VM #31
  • Params: lhs: ResOperand, rhs: ResOperand, dst: CellRef
• WideMul128 Feat: Implement WideMul128 Hint #37
  • Params: lhs: ResOperand, rhs: ResOperand, high: CellRef, low: CellRef
  • Description: Multiplies two 128-bit integers and returns two 128-bit integers: the high and low parts of the product.
• DivMod Feat: Implement DivMod Hint #41
  • Params: lhs: ResOperand, rhs: ResOperand, quotient: CellRef, remainder: CellRef
  • Description: Computes lhs/rhs and returns the quotient and remainder. Note: the hint may be used to write an already assigned memory cell.
• Uint256DivMod Feat: Implement Uint256DivMod Hint #46
  • Params: dividend0: ResOperand, dividend1: ResOperand, divisor0: ResOperand, divisor1: ResOperand, quotient0: CellRef, quotient1: CellRef, remainder0: CellRef, remainder1: CellRef
  • Description: Divides dividend (represented by 2 128bit limbs) by divisor (represented by 2 128bit limbs). Returns the quotient (represented by 2 128bit limbs) and remainder (represented by 2 128bit limbs). In all cases - name0 is the least significant limb.
• Uint512DivModByUint256 Feat: Implement Uint512DivModByUint256 Div Mod Hint #112
  • Params: dividend0: ResOperand, dividend1: ResOperand, dividend2: ResOperand, dividend3: ResOperand, divisor0: ResOperand, divisor1: ResOperand, quotient0: CellRef, quotient1: CellRef, quotient2: CellRef, quotient3: CellRef, remainder0: CellRef, remainder1: CellRef
  • Description: Divides dividend (represented by 4 128bit limbs) by divisor (represented by 2 128bit limbs). Returns the quotient (represented by 4 128bit limbs) and remainder (represented by 2 128bit limbs). In all cases - name0 is the least significant limb.
• SquareRoot Feat: Implement SquareRoot hint #110
  • Params: value: ResOperand, dst: CellRef
• Uint256SquareRoot Feat: Implement Uint256SquareRoot hint #131
  • Params: value_low: ResOperand, value_high: ResOperand, sqrt0: CellRef, sqrt1: CellRef, remainder_low: CellRef, remainder_high: CellRef, sqrt_mul_2_minus_remainder_ge_u128: CellRef
  • Description: Computes the square root of value_high<<128+value_low, stores the 64bit limbs of the result in sqrt0 and sqrt1 as well as the 128bit limbs of the remainder in remainder_low and remainder_high. The remainder is defined as value - sqrt**2. Lastly it checks whether 2*sqrt - remainder >= 2**128.
• LinearSplit Feat: Implement LinearSplit Hint #111
  • Params: value: ResOperand, scalar: ResOperand, max_x: ResOperand, x: CellRef, y: CellRef
  • Description: Finds some x and y such that x * scalar + y = value and x <= max_x.
• AllocFelt252Dict Feat: Add Dictionaries #146
  • Params: segment_arena_ptr: ResOperand
• Felt252DictEntryInit Feat: Add Dictionaries #146
  • Params: dict_ptr: ResOperand, key: ResOperand
• Felt252DictEntryUpdate Feat: Add Dictionaries #146
  • Params: dict_ptr: ResOperand, value: ResOperand
• GetSegmentArenaIndex Feat: Add Dictionaries #146
  • Params: dict_end_ptr: ResOperand, dict_index: CellRef
• InitSquashData Feat: Add Dictionaries #146
  • Params: dict_accesses: ResOperand, ptr_diff: ResOperand, n_accesses: ResOperand, big_keys: CellRef, first_key: CellRef
• GetCurrentAccessIndex Feat: Add Dictionaries #146
  • Params: range_check_ptr: ResOperand
• ShouldSkipSquashLoop Feat: Add Dictionaries #146
  • Params: should_skip_loop: CellRef
• GetCurrentAccessDelta Feat: Add Dictionaries #146
  • Params: index_delta_minus1: CellRef
• ShouldContinueSquashLoop Feat: Add Dictionaries #146
  • Params: should_continue: CellRef
• GetNextDictKey Feat: Add Dictionaries #146
  • Params: next_key: CellRef
• AssertLeFindSmallArcs Implement AssertLeFindSmallArcs hint #155
  • Params: range_check_ptr: ResOperand, a: ResOperand, b: ResOperand
• AssertLeIsFirstArcExcluded Implement AssertLeIsFirstArcExcluded hint #165
  • Params: skip_exclude_a_flag: CellRef
• AssertLeIsSecondArcExcluded Implement AssertLeIsSecondArcExcluded hint #166
  • Params: skip_exclude_b_minus_a: CellRef
• RandomEcPoint Implement RandomEcPoint Hint #173
  • Params: x: CellRef, y: CellRef
• FieldSqrt Implement FieldSqrt hint #178
  • Params: val: ResOperand, sqrt: CellRef
  • Description: Computes the square root of val, if val is a quadratic residue, and of 3 * val otherwise. Since 3 is not a quadratic residue, exactly one of val and 3 * val is a quadratic residue (unless val is 0). This allows proving that val is not a quadratic residue.
• DebugPrint
  • Params: start: ResOperand, end: ResOperand
• AllocConstantSize Feat: Implement AllocConstantSize Hint #105
  • Params: size: ResOperand, dst: CellRef
• TestLessThanOrEqualAddress Feat : Implement TestLessThanOrEqualAddress hint #628
  • Params: lhs: ResOperand, rhs: ResOperand, dst: CellRef
  • Description: Variant of TestLessThanOrEqual that compares addresses.
• U256InvModN Feat : Implement U256InvModN hint #630
  • Params: b0: ResOperand, b1: ResOperand, n0: ResOperand, n1: ResOperand, g0_or_no_inv: CellRef, g1_option: CellRef, s_or_r0: CellRef, s_or_r1: CellRef, t_or_k0: CellRef, t_or_k1: CellRef
  • Description: Provides the inverse of b (represented by 2 128-bit limbs) modulo n (represented by 2 128-bit limbs), or a proof that b has no inverse. Check here for more information
• EvalCircuit Implemented EvalCircuit, Fixed bugs and wrote tests for Modbuiltin #669
  • Params: n_add_mods: ResOperand, add_mod_builtin: ResOperand, n_mul_mods: ResOperand, mul_mod_builtin: ResOperand

[greged93]

Hey @rodrigo-pino would love to start by an easy one like WideMul128

[0xcoburn]

Hey @rodrigo-pino can i try Uint256DivMod

[rodrigo-pino]

@coburn24 sure! Please comment on issue #46 so I can properly assign you!

[greged93]

hey @rodrigo-pino, I'm down to take Uint512DivModByUint256 if it's free

[cicr99]

Just added three more core hints to be implemented

[coxmars]

Just added three more core hints to be implemented

Hi @cicr99 how are you? I would like to help with "U256InvModN" if it's free 🫡