# Hash Table

The instruction hash hashes the OpStack's 10 top-most elements in one cycle. Similarly, the Sponge instructions absorb_init, absorb, and squeeze all complete in one cycle. The main processor achieves this by using a hash coprocessor. The Hash Table is part of the arithmetization of that coprocessor, the other two parts being the Cascade Table and the Lookup Table.

Instruction hash and the Sponge instructions absorb_init, absorb, and squeeze are quite similar. The main differences are in updates to the state registers between executions of the pseudo-random permutation used in Triton VM, the permutation of Tip5. A summary of the four instructions' mechanics:

• Instruction hash
1. sets all the hash coprocessor's rate registers (state0 through state9) to equal the processor's stack registers st0 through st9,
2. sets all the hash coprocessor's capacity registers (state10 through state15) to 1,
3. executes the 5 rounds of the Tip5 permutation,
4. overwrites the processor's stack registers st0 through st4 with 0, and
5. overwrites the processor's stack registers st5 through st9 with the hash coprocessor's registers state0 through state4.
• Instruction absorb_init
1. sets all the hash coprocessor's rate registers (state0 through state9) to equal the processor's stack registers st0 through st9,
2. sets all the hash coprocessor's capacity registers (state10 through state15) to 0, and
3. executes the 5 rounds of the Tip5 permutation.
• Instruction absorb
1. overwrites the hash coprocessor's rate registers (state0 through state9) with the processor's stack registers st0 through st9, and
2. executes the 5 rounds of the Tip5 permutation.
• Instruction squeeze
1. overwrites the processor's stack registers st0 through st9 with the hash coprocessor's rate registers (state0 through state9), and
2. executes the 5 rounds of the Tip5 permutation.

The Hash Table first records all Sponge instructions in the order the processor executed them. Then, the Hash Table records all hash instructions in the order the processor executed them. This allows the processor to execute hash instructions without affecting the Sponge's state.

Note that state0 through state3, corresponding to those states that are being split-and-looked-up in the Tip permutation, are not stored as a single field element. Instead, four limbs “highest”, “mid high”, “mid low”, and “lowest” are recorded in the Hash Table. This (basically) corresponds to storing the result of \sigma(R \cdot \texttt{state_element}), except that the limbs resulting from are 16 bit wide, and hence, there are only 4 limbs; the split into 8-bit limbs happens in the Cascade Table.

## Base Columns

The Hash Table has 66 base columns:

• Round number indicator round_no, which can be one of . The Tip5 permutation has 5 rounds, indexed . The round number -1 indicates a padding row. The round number 5 indicates that the Tip5 permutation has been applied in full.
• Current instruction CI, holding the instruction the processor is currently executing.
• 16 columns state_i_highest_lkin, state_i_midhigh_lkin, state_i_midlow_lkin, state_i_lowest_lkin for the to-be-looked-up value of state0 through state4, each of which holds one 16-bit wide limb.
• 16 columns state_i_highest_lkout, state_i_midhigh_lkout, state_i_midlow_lkout, state_i_lowest_lkout for the looked-up value of state0 through state4, each of which holds one 16-bit wide limb.
• 12 columns state5 through state15.
• 4 columns state_i_inv establishing correct decomposition of state_0_*_lkin through state_4_*_lkin into 16-bit wide limbs.
• 16 columns constant_i, which hold the round constant for the round indicated by RoundNumber, or 0 if no round with this round number exists.

## Extension Columns

The Hash Table has 19 extension columns:

• RunningEvaluationHashInput for the Evaluation Argument for copying the input to the hash function from the processor to the hash coprocessor,
• RunningEvaluationHashDigest for the Evaluation Argument for copying the hash digest from the hash coprocessor to the processor,
• RunningEvaluationSponge for the Evaluation Argument for copying the 10 next to-be-absorbed elements from the processor to the hash coprocessor or the 10 next squeezed elements from the hash coprocessor to the processor, depending on the instruction,
• 16 columns state_i_limb_LookupClientLogDerivative (for i , limb highest, midhigh, midlow, lowest ) establishing correct lookup of the respective limbs in the Cascade Table.

Each padding row is the all-zero row with the exception of

• round_no, which is -1,
• CI, which is the opcode of instruction hash, and
• state_i_inv for i , which is .

# Arithmetic Intermediate Representation

Let all household items (🪥, 🛁, etc.) be challenges, concretely evaluation points, supplied by the verifier. Let all fruit & vegetables (🥝, 🥥, etc.) be challenges, concretely weights to compress rows, supplied by the verifier. Both types of challenges are X-field elements, i.e., elements of .

## Initial Constraints

1. The round number is -1 or 0.
2. The current instruction is hash or absorb_init.
3. If the current instruction is hash and the round number is 0, then RunningEvaluationHashInput has accumulated the first row with respect to challenges 🧄₀ through 🧄₉ and indeterminate 🚪. Otherwise, RunningEvaluationHashInput is 1.
4. RunningEvaluationHashDigest is 1.
5. If the current instruction is absorb_init, then RunningEvaluationSponge has accumulated the first row with respect to challenges 🧅 and 🧄₀ through 🧄₉ and indeterminate 🧽. Otherwise, RunningEvaluationSponge is 1.
6. For i , limb highest, midhigh, midlow, lowest :
If the round number is 0, then state_i_limb_LookupClientLogDerivative has accumulated state_i_limb_lkin and state_i_limb_lkout with respect to challenges 🍒, 🍓 and indeterminate 🧺. Otherwise, state_i_limb_LookupClientLogDerivative is 0.

Written as Disjunctive Normal Form, the same constraints can be expressed as:

1. round_no is -1 or 0.
2. CI is the opcode of hash or of absorb_init.
3. (CI is the opcode of absorb_init or round_no is -1 or RunningEvaluationHashInput has accumulated the first row with respect to challenges 🧄₀ through 🧄₉ and indeterminate 🚪)
and (CI is the opcode of hash or RunningEvaluationHashInput is 1)
and (round_no is 0 or RunningEvaluationHashInput is 1).
4. (CI is the opcode of hash or RunningEvaluationSponge has accumulated the first row with respect to challenges 🧅 and 🧄₀ through 🧄₉ and indeterminate 🧽)
and (CI is the opcode of absorb_init or RunningEvaluationSponge is 1).
5. For i , limb highest, midhigh, midlow, lowest :
(round_no is -1 or state_i_limb_LookupClientLogDerivative has accumulated the first row)
and (round_no is 0 or state_i_limb_LookupClientLogDerivative is the default initial).

### Initial Constraints as Polynomials

1. (round_no + 1)·round_no
2. (CI - opcode(hash))·(CI - opcode(absorb_init))
3. (CI - opcode(absorb_init))·(round_no + 1)·(RunningEvaluationHashInput - 🚪 - 🧄₀·st0 - 🧄₁·st1 - 🧄₂·st2 - 🧄₃·st3 - 🧄₄·st4 - 🧄₅·st5 - 🧄₆·st6 - 🧄₇·st7 - 🧄₈·st8 - 🧄₉·st9)
+ (CI - opcode(hash))·(RunningEvaluationHashInput - 1)
+ round_no·(RunningEvaluationHashInput - 1)
4. RunningEvaluationHashDigest - 1
5. (CI - opcode(hash))·(RunningEvaluationSponge - 🧽 - 🧅·CI - 🧄₀·st0 - 🧄₁·st1 - 🧄₂·st2 - 🧄₃·st3 - 🧄₄·st4 - 🧄₅·st5 - 🧄₆·st6 - 🧄₇·st7 - 🧄₈·st8 - 🧄₉·st9)
+ (CI - opcode(absorb_init))·(RunningEvaluationSponge - 1)
6. For i , limb highest, midhigh, midlow, lowest :
(round_no + 1)·(state_i_limb_LookupClientLogDerivative·(🧺 - 🍒·state_i_limb_lkin - 🍓·state_i_limb_lkout) - 1)
+ round_no·state_i_limb_LookupClientLogDerivative

## Consistency Constraints

1. If the round number is -1, then the current instruction is hash.
2. If the round number is 0 and the current instruction is hash, then register state10 is 1.
3. If the round number is 0 and the current instruction is hash, then register state11 is 1.
4. If the round number is 0 and the current instruction is hash, then register state12 is 1.
5. If the round number is 0 and the current instruction is hash, then register state13 is 1.
6. If the round number is 0 and the current instruction is hash, then register state14 is 1.
7. If the round number is 0 and the current instruction is hash, then register state15 is 1.
8. If the round number is 0 and the current instruction is absorb_init, then register state10 is 0.
9. If the round number is 0 and the current instruction is absorb_init, then register state11 is 0.
10. If the round number is 0 and the current instruction is absorb_init, then register state12 is 0.
11. If the round number is 0 and the current instruction is absorb_init, then register state13 is 0.
12. If the round number is 0 and the current instruction is absorb_init, then register state14 is 0.
13. If the round number is 0 and the current instruction is absorb_init, then register state15 is 0.
14. If the round number is 0 and the current instruction is absorb_init, then register state10 is 0.
15. The round constants adhere to the specification of Tip5.

Written as Disjunctive Normal Form, the same constraints can be expressed as:

1. The round number is 0 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash.
2. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state10 is 1.
3. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state11 is 1.
4. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state12 is 1.
5. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state13 is 1.
6. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state14 is 1.
7. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of absorb_init or absorb or squeeze or state15 is 1.
8. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state10 is 0.
9. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state11 is 0.
10. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state12 is 0.
11. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state13 is 0.
12. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state14 is 0.
13. The round number is -1 or 1 or 2 or 3 or 4 or 5 or CI is the opcode of hash or absorb or squeeze or state15 is 0.
14. The constant_i equals interpolant(round_no), where “interpolant” is the lowest-degree interpolant through (i, constant_i) for .

### Consistency Constraints as Polynomials

1. (round_no - 0)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))
2. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state10 - 1)
3. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state11 - 1)
4. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state12 - 1)
5. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state13 - 1)
6. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state14 - 1)
7. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·(state15 - 1)
8. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state10
9. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state11
10. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state12
11. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state13
12. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state14
13. (round_no + 1)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no - 5)
·(CI - opcode(hash))·(CI - opcode(absorb))·(CI - opcode(squeeze))
·state15

## Transition Constraints

1. If the round number is -1, then the round number in the next row is -1.
2. If the round number is 1, 2, 3, or 4, then the round number in the next row is incremented by 1.
3. If the round number is 5, then the round number in the next row is either -1 or 0.
4. If the current instruction is hash, then the current instruction in the next row is hash.
5. If the round number is not 5, the current instruction in the next row is the current instruction in the current row.
6. If the round number in the next row is 0 and the current instruction in the next row is absorb, then the capacity's state registers don't change.
7. If the round number in the next row is 0 and the current instruction in the next row is squeeze, then none of the state registers change.
8. If the round number in the next row is 0 and the current instruction in the next row is hash, then RunningEvaluationHashInput accumulates the next row with respect to challenges 🧄₀ through 🧄₉ and indeterminate 🚪. Otherwise, it remains unchanged.
9. If the round number in the next row is 5 and the current instruction in the next row is hash, then RunningEvaluationHashDigest accumulates the next row with respect to challenges 🧄₀ through 🧄₄ and indeterminate 🪟. Otherwise, it remains unchanged.
1. If the round number in the next row is 0 and the current instruction in the next row is absorb_init, absorb, or squeeze, then RunningEvaluationSponge accumulates the next row with respect to challenges 🧅 and 🧄₀ through 🧄₉ and indeterminate 🧽.
2. If the round number in the next row is not 0, then RunningEvaluationSponge remains unchanged.
3. If the current instruction in the next row is hash, then RunningEvaluationSponge remains unchanged.
10. If the round number is 0, the state registers adhere to the rules of applying round 0 of the Tip5 permutation.
11. If the round number is 1, the state registers adhere to the rules of applying round 1 of the Tip5 permutation.
12. If the round number is 2, the state registers adhere to the rules of applying round 2 of the Tip5 permutation.
13. If the round number is 3, the state registers adhere to the rules of applying round 3 of the Tip5 permutation.
14. If the round number is 4, the state registers adhere to the rules of applying round 4 of the Tip5 permutation.
15. For i , limb highest, midhigh, midlow, lowest :
If the next round number is 0, 1, 2, 3, or 4, then state_i_limb_LookupClientLogDerivative has accumulated state_i_limb_lkin' and state_i_limb_lkout' with respect to challenges 🍒, 🍓 and indeterminate 🧺. Otherwise, state_i_limb_LookupClientLogDerivative remains unchanged.

Written as Disjunctive Normal Form, the same constraints can be expressed as:

1. round_no is 0 or 1 or 2 or 3 or 4 or 5 or round_no' is -1.

2. round_no is -1 or 5 or round_no' is round_no + 1.

3. round_no is -1 or 0 or 1 or 2 or 3 or 4 or round_no' is -1 or 0.

4. CI is the opcode of absorb_init or absorb or squeeze or CI' is the opcode of hash.

5. round_no is 5 or CI' is CI.

6. round_no' is -1 or 1 or 2 or 3 or 4 or 5 or CI' is the opcode of hash or absorb_init or squeeze or the -randomized sum of differences of the state registers state10 through state15 in the next row and the current row is 0.

7. round_no' is -1 or 1 or 2 or 3 or 4 or 5 or CI' is the opcode of hash or absorb_init or absorb or the -randomized sum of differences of all state registers in the next row and the current row is 0.

8. (round_no' is -1 or 1 or 2 or 3 or 4 or 5 or CI' is the opcode of absorb_init or absorb or squeeze or RunningEvaluationHashInput accumulates the next row)
and (round_no' is 0 or RunningEvaluationHashInput remains unchanged)
and (CI' is the opcode of hash or RunningEvaluationHashInput remains unchanged).

9. (round_no' is -1 or 0 or 1 or 2 or 3 or 4 or CI' is the opcode of absorb_init or absorb or squeeze or RunningEvaluationHashDigest accumulates the next row)
and (round_no' is 5 or RunningEvaluationHashDigest remains unchanged)
and (CI' is the opcode of hash or RunningEvaluationHashDigest remains unchanged).

1. (round_no' is -1 or 1 or 2 or 3 or 4 or 5 or CI' is the opcode of hash or RunningEvaluationSponge accumulates the next row)
2. and (round_no' is 0 or RunningEvaluationSponge remains unchanged)
3. and (CI' is the opcode of absorb_init or absorb or squeeze or RunningEvaluationSponge remains unchanged).
10. round_no is -1 or 1 or 2 or 3 or 4 or 5 or the state registers adhere to the rules of applying round 0 of the Tip5 permutation.

11. round_no is -1 or 0 or 2 or 3 or 4 or 5 or the state registers adhere to the rules of applying round 1 of the Tip5 permutation.

12. round_no is -1 or 0 or 1 or 3 or 4 or 5 or the state registers adhere to the rules of applying round 2 of the Tip5 permutation.

13. round_no is -1 or 0 or 1 or 2 or 4 or 5 or the state registers adhere to the rules of applying round 3 of the Tip5 permutation.

14. round_no is -1 or 0 or 1 or 2 or 3 or 5 or the state registers adhere to the rules of applying round 4 of the Tip5 permutation.

15. For i , limb highest, midhigh, midlow, lowest :
(round_no' is -1 or 5 or state_i_limb_LookupClientLogDerivative has accumulated the next row)
and (round_no is 0 or 1 or 2 or 3 or 4 or state_i_limb_LookupClientLogDerivative' is state_i_limb_LookupClientLogDerivative).

### Transition Constraints as Polynomials

1. (round_no - 0)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no' + 1)
2. (round_no + 1)·(round_no - 5)·(round_no' - round_no - 1)
3. (round_no + 1)·(round_no - 0)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(round_no' + 1)·(round_no' - 0)
4. (CI - opcode(absorb_init))·(CI - opcode(absorb))·(CI - opcode(squeeze))·(CI' - opcode(hash))
5. (round_no - 5)·(CI' - CI)
6. (round_no' + 1)·(round_no' - 1)·(round_no' - 2)·(round_no' - 3)·(round_no' - 4)·(round_no' - 5)
·(CI' - opcode(hash))·(CI' - opcode(absorb_init))·(CI' - opcode(squeeze))
·(🧄₁₀·(st10' - st10) + 🧄₁₁·(st11' - st11) + 🧄₁₂·(st12' - st12) + 🧄₁₃·(st13' - st13) + 🧄₁₄·(st14' - st14) + 🧄₁₅·(st15' - st15))
7. (round_no' + 1)·(round_no' - 1)·(round_no' - 2)·(round_no' - 3)·(round_no' - 4)·(round_no' - 5)
·(CI' - opcode(hash))·(CI' - opcode(absorb_init))·(CI' - opcode(absorb))
·(🧄₀·(st0' - st0) + 🧄₁·(st1' - st1) + 🧄₂·(st2' - st2) + 🧄₃·(st3' - st3) + 🧄₄·(st4' - st4) + 🧄₅·(st5' - st5) + 🧄₆·(st6' - st6) + 🧄₇·(st7' - st7) + 🧄₈·(st8' - st8) + 🧄₉·(st9' - st9) + 🧄₁₀·(st10' - st10) + 🧄₁₁·(st11' - st11) + 🧄₁₂·(st12' - st12) + 🧄₁₃·(st13' - st13) + 🧄₁₄·(st14' - st14) + 🧄₁₅·(st15' - st15))
8. (round_no' + 1)·(round_no' - 1)·(round_no' - 2)·(round_no' - 3)·(round_no' - 4)·(round_no' - 5)
·(CI' - opcode(absorb_init))·(CI' - opcode(absorb))·(CI' - opcode(squeeze))
·(RunningEvaluationHashInput' - 🚪·RunningEvaluationHashInput - 🧄₀·st0' - 🧄₁·st1' - 🧄₂·st2' - 🧄₃·st3' - 🧄₄·st4' - 🧄₅·st5' - 🧄₆·st6' - 🧄₇·st7' - 🧄₈·st8' - 🧄₉·st9')
+ round_no'·(RunningEvaluationHashInput' - RunningEvaluationHashInput)
+ (CI' - opcode(hash))·(RunningEvaluationHashInput' - RunningEvaluationHashInput)
9. (round_no' + 1)·(round_no' - 0)·(round_no' - 1)·(round_no' - 2)·(round_no' - 3)·(round_no' - 4)
·(CI' - opcode(absorb_init))·(CI' - opcode(absorb))·(CI' - opcode(squeeze))
·(RunningEvaluationHashDigest' - 🪟·RunningEvaluationHashDigest - 🧄₀·st0' - 🧄₁·st1' - 🧄₂·st2' - 🧄₃·st3' - 🧄₄·st4')
+ (round_no' - 5)·(RunningEvaluationHashDigest' - RunningEvaluationHashDigest)
+ (CI' - opcode(hash))·(RunningEvaluationHashDigest' - RunningEvaluationHashDigest)
1. (round_no' + 1)·(round_no' - 1)·(round_no' - 2)·(round_no' - 3)·(round_no' - 4)·(round_no' - 5)
·(CI' - opcode(hash))
·(RunningEvaluationSponge' - 🧽·RunningEvaluationSponge - 🧅·CI' - 🧄₀·st0' - 🧄₁·st1' - 🧄₂·st2' - 🧄₃·st3' - 🧄₄·st4' - 🧄₅·st5' - 🧄₆·st6' - 🧄₇·st7' - 🧄₈·st8' - 🧄₉·st9')
2. + (round_no' - 0)·(RunningEvaluationSponge' - RunningEvaluationSponge)
3. + (CI' - opcode(absorb_init))·(CI' - opcode(absorb))·(CI' - opcode(squeeze))·(RunningEvaluationSponge' - RunningEvaluationSponge)
10. For i , limb highest, midhigh, midlow, lowest :
(round_no + 1)·(round_no - 5)·((state_i_limb_LookupClientLogDerivative' - state_i_limb_LookupClientLogDerivative)·(🧺 - 🍒·state_i_limb_lkin' - 🍓·state_i_limb_lkout') - 1)
+ (round_no - 0)·(round_no - 1)·(round_no - 2)·(round_no - 3)·(round_no - 4)·(state_i_limb_LookupClientLogDerivative' - state_i_limb_LookupClientLogDerivative)
11. The remaining constraints are left as an exercise to the reader. For hints, see the Tip5 paper.

None.