[Bug] Execution for Pedersen `commit` instructions.

[d0cd]

🐛 Bug Report

The two Pedersen variants of the commit instruction take up-to 64 and 128 bit inputs respectively. However, using Value::to_bits_le (it's because of Plaintext::to_bits_le) introduces additional bits to appropriately serialize the variants, resulting in unexpected failures.

Test

This test is to be run with the fix in #1360.

program test.aleo;

function main:
    commit.ped64 1i64 1scalar into r0;
    output r0 as group.private;

Output

thread 'main' panicked at 'The Pedersen hash input cannot exceed 64 bits.',[...]/snarkVM/circuit/environment/src/circuit.rs:246:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

[howardwu]

The TLDR is we are going to hold off on this until boolean arrays are supported in Aleo instructions.

Problem

The reason this fails is that 1i64.to_bits_le() becomes [ 2 type bits || 8 variant bits || 16 size bits || 64 data bits ] which equals 90 bits and thus exceeds 64 bits for Pedersen64.

So, hash.ped64 and commit.ped64 support:

boolean
i8
i16
i32
u8
u16
u32

because they fit within the 64 bits with their respective metadata bits. The same case applies for its respective types in the Pedersen128 case.

For those who are wondering why we need to encode all this data, the problem is that these are supposed to be collision-resistant hash functions. If we didn't encode the type, variant, and size information, there is a risk that collision may occur when we hash HashLE(1u8), HashLE(1field), HashLE(1iu32), and HashLE(true) without further delineation.

Solution

One way to remedy this issue is to allow the developer in Aleo instructions to pack their own bitarray / boolean array, and pass it (as a register) to the commit.ped64 command, so they can forgo the metadata bits (i.e. type, variant, and size bits).

[zhiqiangxu]

@howardwu Is the design spec for boolean arrays available? I'm very interested in how leo is going to support dynamic arrays in circuit.

[howardwu]

We haven't drafted anything yet. Currently, we've been experimenting with using routing networks to facilitate the common memory-bound array operations.

[zhiqiangxu]

@howardwu Thanks for sharing. I've another question to confirm: Is the circuit StringType only for compile time fixed string? Because I see such logic which is using constant to constrain the length of StringType.

[howardwu]

Also a good question, we're planning to overhaul the StringType.

Currently, yes the StringType is fixed. Once we have array support, it will allow us to support an updatable StringType that can be dynamic in size.

[qy3u]

We haven't drafted anything yet. Currently, we've been experimenting with using routing networks to facilitate the common memory-bound array operations.

@howardwu Could you provide a more detailed explanation of the routing network? I am very interested in this topic but have not been able to find any relevant information. Thank you.