Add Cairo Zero Hints

[rodrigo-pino]

Cairo Zero Hints

The following is a (big!) list of hints required by Cairo Zero. They might be an overlap between Cairo Zero hints and Cairo One hints #36 .

The list was extracted from sister VM in Go by LambdaClass where they gathered all Pythonic hints.

👀 For specific instructions on how to implement these hints you can check out the readme file in the zero package

Uint256 Operations

• Implement Uint256Add Cairo 0 Hint #187
• Uint256AddLow #219
• Split64 #221
• Uint256SignedNN #223
• Uint256UnsignedDivRem #224
• Uint256MulDivMod #226
• Uint256Sqrt #227

Math Operations

• IsNn: Checks if a value is non-negative within a specific range.
• IsNnOutOfRange: Checks if the negation of a value (minus one) is non-negative within a specific range.
• IsLeFelt: Determines if one value is less than or equal to another within a finite field.
• AssertLtFelt: Asserts that one value is strictly less than another within a finite field.
• Pow #238
• IsPositive: Checks if a value is positive within a specific range and prime context.
• SplitFelt #239
• SplitInt: Splits an integer based on a base and asserts the result is within a certain range.
• SplitIntAssertRange: Asserts that the value for SplitInt is within the expected range.
• AssertNotZero: Asserts that a value is not zero.
• AssertNn: Asserts that a given integer is non-negative within a specified range.
• AssertNotEqual: Asserts that two given values are not equal.
• Assert250Bits: Asserts that a value is within the range of 250 bits.
• AssertLeFelt: Asserts that one value is less than or equal to another within a finite field.
• AssertLeFeltExcluded0: Custom assertion related to AssertLeFelt.
• AssertLeFeltExcluded1: Another custom assertion related to AssertLeFelt.
• AssertLeFeltExcluded2: Final custom assertion related to AssertLeFelt.
• Sqrt #240
• UnsignedDivRem #241
• SignedDivRem #242
• IsQuadResidue #243

Usort

• UsortEnterScope #244
• UsortBody #232
• UsortVerify #233
• UsortVerifyMultiplicityAssert #234
• UsortVerifyMultiplicityBody #235

Other

• SetAdd #246
• AddSegment #247
• VmExitScope #248
• VmEnterScope #249
• MemcpyEnterScope #250
• MemcpyContinueCopying #251
• MemsetEnterScope #430
• MemsetContinueLoop #431
• FindElement #252
• SearchSortedLower #253
• NondetElementsOverTen hint (poseidon builtin hint) #491
• NondetElementsOverTwo hint (poseidon builtin hint) #492

Elliptic Curve Operations

• EcNegate #254
• EcDoubleSlopeV1 #256
• ComputeSlopeV1 #257
• EcDoubleAssignNewXV1 #258
• EcDoubleAssignNewYV1 #386
• NondetBigint3V1 #265
• FastEcAddAssignNewX #267
• FastEcAddAssignNewY #270
• EcMulInner #453
• + IsZeroDivMod Hint Implementation #470 + IsZeroPack Hint Implementation #469 + ZeroNonDec Hint Implementation #468

Signatures (ECDSA & SEC_P)

• VerifyEcdsaSignature #271
• ImportSecp256R1P #273
• VerifyZero #274
• ReduceV1 #275
• DivModNPackedDivmodV1: Calculates the division modulo N for packed values. #276
• DivModNSafeDiv #277
• GetPointFromX #278

Blake Hash

• Blake2sCompute #279
• Blake2sAddUint256 #312
• Blake2sAddUint256Bigend #281
• Blake2sFinalize #280

Keccak

• UnsafeKeccak #286
• UnsafeKeccakFinalize #287
• BlockPermutation #282
• CairoKeccakFinalize #283
• KeccakWriteArgs #285
• CompareBytesInWord hint (Keccak hint) #479
• compareKeccakFullRateInBytes hint (Keccak hint) #480

Dictionaries

• DefaultDictNew #294
• DictRead #289
• DictWrite #290
• DictUpdate #291
• SquashDict #295
• SquashDictInnerSkipLoop #297
• SquashDictInnerFirstIteration #296
• SquashDictInnerCheckAccessIndex #298
• SquashDictInnerContinueLoop #299
• SquashDictInnerAssertLenKeys #302
• SquashDictInnerLenAssert #300
• SquashDictInnerUsedAccessesAssert #301
• SquashDictInnerNextKey #303
• DictSquashCopyDict #292
• DictSquashUpdatePtr #293
• DictNew #288

[cicr99]

To implement the hints in this issue you'll need to follow the next steps:

• Add the string that is the code of the hint in the hintcode file. The code of the hint is always the same string and can be found in the lambdaclass vm or if you look for it in the python vm
• Then add your hint in the switch-case in the GetHintFromCode method in zerohint file. You'll need to implement a method for your hint there called Create<HintName>Hinter
• The method Create<HintName>Hinter should check the parameters are correct and should return the corresponding Hinter structure. If the hint is already implemented, as is the case for AllocSegment, you don't need to do anything else, just return it
• If the hint hasn't been implemented, you'll need to add it in the corresponding file in the zero package of the hintrunner, and add unit tests for it.

⚠️ The description has been updated with a link to the readme inside the hintunner/zero package with more detailed instructions on how to implement new Cairo 0 hints