Add Keccak Opcode which allows the message size to vary at prover time

[kevaundray]

Problem

For most of our hash functions, we have the property that the length of the message needs to be known at compile time.

We have recently discovered that this usecase is not sufficient for real-world applications like RLP.

The difference here being that the size of the message may be known by the prover.

Happy Case

The solution to this is to introduce an extra parameter to Keccak, lets name it actual_length which is a witness and determines the actual length of the message.

Lets discuss the idiosyncranicities of this.

Before this proposal

We can do the following:

let hash_a = keccak([1,2,3,4])

let hash_b = keccak([1,2,3,4,0,0,0,0])

The second function is padded with four zeroes, while the first is not. It is evident that hash_a and hash_b are not the same due to the collision resistance property of keccak.

Given a circuit, it is not possible to produce hash_a and hash_b because the message size needs to be fixed.

After this proposal

We can do the following:

let message_size = 4;
let hash_a = keccak([1,2,3,4], message_size)

let message_size = 4;
let hash_b = keccak([1,2,3,4,0,0,0,0], message_size)

hash_a and hash_b will produce the same value. This is because the message_size indicates how many bytes in the message we should actually be hashing.

Note that even though hash_a and hash_b produce the same hash. hash_b is more expensive because the fixed message_size is 8 bytes. This is due to us passing [1,2,3,4,0,0,0,0].

The hash function can then be seen to have two configuration parameters:

• MAX_MESSAGE_SIZE : This is a circuit constant.
• ACTUAL_MESSAGE_SIZE: This is a prover provided value, that must be less than MAX_MESSAGE_SIZE. One can separately add a constraint to make this equal to a constant, so that it has the same behaviour as the previous Keccak method.

Things to Note

• Keccak with this extra argument, will always be more expensive than the Keccak that only allows constant messages. For this reason, it makes sense to use a separate opcode, If the backend wants to under the hood wants to use one implementation, then they are welcome to .

• We ideally want this for all hash functions, however this will need to be done iteratively over time.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response