Portable hashes

[diogofriggo]

Abstract

SnarkVM's (and thus Aleo's) hashing implementations do not match off-chain implementations of the same algorithms.
Our practical interest lies mostly on having keccak256 working well but we are aware that it might be desirable to apply the same changes to all hashing algorithms for consistency.
If possible we would rather postpone the latter to a follow-up ARC. The proposal has been named "portable hashes" because the hash needs to be portable/understandable by Aleo and every other chain.

Motivation

This is a requirement for verifying data produced outside of Aleo. It is useful when communication between Aleo and other blockchains is needed.

While snarkVM's keccak hashing is implemented in-house the mismatch with external implementations (like the Rust crate tiny keccak's) seems to stem from the two points below.

Current hashing implementations

Looking at how the hashes are implemented sheds some light on possible issues:

        let output = match (VARIANT, &self.destination_type) {
            (0, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp256(&input.to_bits_le())?),
            (1, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp512(&input.to_bits_le())?),
            (2, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp768(&input.to_bits_le())?),
            (3, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp1024(&input.to_bits_le())?),
            (4, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp256(&N::hash_keccak256(&input.to_bits_le())?)?),
            (5, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp512(&N::hash_keccak384(&input.to_bits_le())?)?),
            (6, PlaintextType::Literal(..)) => Literal::Group(N::hash_to_group_bhp512(&N::hash_keccak512(&input.to_bits_le())?)?),
            ...
            ...
            ...
        // Cast the output to the destination type.
        let output = match self.destination_type {
            PlaintextType::Literal(literal_type) => output.cast_lossy(literal_type)?,
            PlaintextType::Struct(..) => bail!("Cannot hash into a struct"),
            PlaintextType::Array(..) => bail!("Cannot hash into an array (yet)"),
        };

For keccak256 we've verified that the hash_keccak256 function matches external implementations. We suspect the same holds for the other hash types.

Hashes start to differ in the subsequent wrapping call to hash_to_group_bhp### which modifies the hash making it incompatible with any other standard implementation of the hashing scheme just applied.

Furthermore, a second hash-modification step happens when the hash is converted to one of Leo's primitive types. Using keccak256 as an example, it needs 256 bits to be represented, however a necessarily lossy cast can easily be done to an aleo primitive type like u8 or i128 which we fail to understand the purpose of. Of particular importance is the fact that there's not a single primitive type that can fully hold the 256 bits (this can however be part of another ARC). This naturally introduces yet another layer of irreconcilable differences with respect to external implementations.

It would be very convenient to have a type that can hold the full contents of each hash. For keccak256, the only such type would be an array [u8; 32]. For keccak512 on the other hand, it's unclear how it could be represented in a lossless and idiomatic fashion given the 32-element limitation of arrays. One possible approach would be to have a dedicated type for hashes like for addresses. For the practical purpose of communicating with EVM chains, keccak256 would suffice. Should a larger design effort be required to support all hash types, then this ARC could be focused on keccak256 as a first milestone.

Data representation

The call to to_bits_le shown in the above code snippet introduces another modification to the input data before any hashing is done.

As an example calling to_bits_le(49u8) produces 00 10010000 0001000000000000 10001100 instead of just 0011 0001 or 1000 1100.

Hashing input:

The current implementation is hashing the internal representation of data in snarkVM.
a. The code snippet requires a group value returned from the hash, which in our case is not what we need.
b. When the function to_bits_le is called, it translates the snarkVM representation of the input to bits as the input with its metadata.

For example, let's take the execution of this Aleo instruction hash.keccak256 49u8 into r0 as field;

When the to_bits_le is called on the input 49u8 the result is:

[0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0] and not 0b0011 0001 or 0b1000 1100. The above result has metadata that describes the 49u8 as this:

The output of to_bits_le(49u8) carries metadata along with the actual result, the metadata and data represented by 00 10010000 0001000000000000 10001100 can be broken down as:

Plain text Variant	Literal variant	Literal size	Literal
00	10010000	0001000000000000	10001100

Suggested improvements

This proposal seeks to understand whether both the above limitations can be lifted, and if so, propose implementations for them, namely:

• Support the target type [u8; ##] so that full hash data can be kept untrimmed (or some other idiomatic alternative that preserves the full hash)
• Implement a new set of hashes that will be portable between Aleo and other implementations.
• Removal of the hash_to_group_bhp### step at least when the target type is [u8; #]
• Change the existing implementation of the keccak256 hashing function if necessary to match external implementations (this ARC's suggested initial scope would be to focus on keccak256 only)

The overarching goal of this ARC is compatibility with EVM chains (and possibly others) with the goal of interchain communication.

To achieve that goal it must be possible to hash data in exactly the same way in both chains.

Dependencies

This impacts the snarkVM, & Leo repositories. Impact to the snarkOS repository is not expected.

Backwards Compatibility

Casting to a byte array fundamentally does not introduce backward-compatibility issues whereas it does for existing casts. The latter is a breaking change and would require a mechanism to deal with it, this ARC's goal would be limited to the [u8; ##] type or an equivalent alternative

Security & Compliance

There should not be any security or compliance considerations.

References

snarkVM's hashing usage

snarkVM's hashing implementation

Tiny keccak Rust crate

[anstylian]

A primitive implementation for this proposal.
Currently is hashing only u8 numbers.

Branch: ARC #81
Instruction on how to test it can be found at ARC-81-testdrive.md