snarkvm-console-algorithms 4.9.0

// Copyright (c) 2019-2026 Provable Inc.
// This file is part of the snarkVM library.

// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at:

// http://www.apache.org/licenses/LICENSE-2.0

// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use super::*;
use snarkvm_console_types::environment::Console;
use snarkvm_utilities::ToBytes;

// Test vectors. For each BHP{256, 512, 768, 1024}, we test the output on
// deterministic inputs of certain representative lengths. The second element of
// each pair is the x-coordinate of the hash.

// Display new expectations with:
// cargo test -p snarkvm-console-algorithms print_bhp_expectations -- --ignored --nocapture

static EXPECTATIONS_256: [(usize, [u8; 32]); 10] = [
    (172, [
        0x96, 0xcb, 0x38, 0x0e, 0x35, 0xac, 0xbe, 0xb0, 0xed, 0x80, 0x8b, 0x77, 0x5f, 0x80, 0xfe, 0x1b, 0x24, 0x06,
        0x96, 0x0d, 0xab, 0x26, 0xbb, 0xf2, 0xbf, 0x70, 0x9d, 0xe1, 0xba, 0x0e, 0x36, 0x0e,
    ]),
    (173, [
        0x96, 0xcb, 0x38, 0x0e, 0x35, 0xac, 0xbe, 0xb0, 0xed, 0x80, 0x8b, 0x77, 0x5f, 0x80, 0xfe, 0x1b, 0x24, 0x06,
        0x96, 0x0d, 0xab, 0x26, 0xbb, 0xf2, 0xbf, 0x70, 0x9d, 0xe1, 0xba, 0x0e, 0x36, 0x0e,
    ]),
    (174, [
        0x96, 0xcb, 0x38, 0x0e, 0x35, 0xac, 0xbe, 0xb0, 0xed, 0x80, 0x8b, 0x77, 0x5f, 0x80, 0xfe, 0x1b, 0x24, 0x06,
        0x96, 0x0d, 0xab, 0x26, 0xbb, 0xf2, 0xbf, 0x70, 0x9d, 0xe1, 0xba, 0x0e, 0x36, 0x0e,
    ]),
    (175, [
        0xcb, 0x9a, 0x09, 0xd9, 0xe7, 0xa3, 0xa4, 0x2d, 0x5e, 0x25, 0x75, 0x8f, 0xe9, 0x25, 0x38, 0x5f, 0x7a, 0x9e,
        0xf4, 0x46, 0x15, 0xfc, 0xd5, 0x55, 0x70, 0x50, 0x35, 0xf9, 0x3e, 0xfe, 0xd0, 0x0b,
    ]),
    (176, [
        0xaf, 0xee, 0x41, 0x1f, 0x7e, 0xd4, 0x0a, 0x09, 0x22, 0x74, 0x7c, 0xc4, 0xe3, 0x7d, 0x0f, 0xfc, 0x40, 0x3f,
        0xb5, 0xeb, 0xb2, 0xe7, 0x76, 0x7f, 0xfe, 0x58, 0x77, 0x7e, 0x3c, 0x09, 0x9b, 0x06,
    ]),
    (342, [
        0x13, 0x1c, 0x71, 0x01, 0x4b, 0x80, 0xae, 0x6f, 0x6b, 0x34, 0xc5, 0x8a, 0xc0, 0x17, 0xd4, 0x39, 0x69, 0xa5,
        0x42, 0xf3, 0xff, 0x3f, 0x2e, 0xda, 0x7b, 0x6d, 0x4e, 0x3e, 0xd2, 0xee, 0x70, 0x06,
    ]),
    (507, [
        0x79, 0xbb, 0xc2, 0x18, 0xcb, 0x0d, 0xfb, 0xc5, 0xc6, 0xf0, 0x38, 0x95, 0xf0, 0x84, 0x38, 0x82, 0xc8, 0xc7,
        0xe3, 0x22, 0x62, 0xbd, 0x44, 0x38, 0x3a, 0xaf, 0x3d, 0xa2, 0x60, 0x11, 0x2b, 0x12,
    ]),
    (510, [
        0x3b, 0x55, 0xe8, 0x4a, 0x83, 0xf2, 0x28, 0xd7, 0x3e, 0xa4, 0x4f, 0x37, 0xf0, 0x2b, 0x40, 0xdc, 0x6a, 0x14,
        0xb2, 0x06, 0xce, 0xc0, 0xba, 0x95, 0x4a, 0x41, 0x94, 0xc8, 0x63, 0x84, 0xec, 0x09,
    ]),
    (512, [
        0x4b, 0xc1, 0xc5, 0xa1, 0xa2, 0x23, 0xdf, 0xc5, 0x0d, 0x75, 0x7a, 0x88, 0x4b, 0x09, 0x3a, 0x28, 0xbd, 0x19,
        0x94, 0x1e, 0x8a, 0x1a, 0xba, 0xd0, 0xf1, 0x6b, 0xff, 0x46, 0x96, 0x5d, 0x0c, 0x07,
    ]),
    (513, [
        0xab, 0xd7, 0xa7, 0x84, 0x19, 0x2f, 0x41, 0xb3, 0x9b, 0x70, 0x85, 0x3b, 0x27, 0x8e, 0x92, 0xbf, 0x1e, 0x91,
        0x8d, 0xd0, 0xcd, 0x4e, 0xf7, 0xd0, 0x65, 0x32, 0xe3, 0x96, 0xb0, 0x31, 0xb3, 0x00,
    ]),
];

static EXPECTATIONS_512: [(usize, [u8; 32]); 11] = [
    (130, [
        0xbf, 0xeb, 0x52, 0xa0, 0x3a, 0xcb, 0x3f, 0x38, 0x58, 0xd0, 0x1a, 0x8d, 0x24, 0x5f, 0x70, 0xf0, 0xce, 0x34,
        0x98, 0xf0, 0x61, 0x63, 0xda, 0x84, 0x0b, 0xc8, 0x4b, 0x5d, 0xe7, 0x4d, 0x0b, 0x10,
    ]),
    (131, [
        0xbf, 0xeb, 0x52, 0xa0, 0x3a, 0xcb, 0x3f, 0x38, 0x58, 0xd0, 0x1a, 0x8d, 0x24, 0x5f, 0x70, 0xf0, 0xce, 0x34,
        0x98, 0xf0, 0x61, 0x63, 0xda, 0x84, 0x0b, 0xc8, 0x4b, 0x5d, 0xe7, 0x4d, 0x0b, 0x10,
    ]),
    (132, [
        0xbf, 0xeb, 0x52, 0xa0, 0x3a, 0xcb, 0x3f, 0x38, 0x58, 0xd0, 0x1a, 0x8d, 0x24, 0x5f, 0x70, 0xf0, 0xce, 0x34,
        0x98, 0xf0, 0x61, 0x63, 0xda, 0x84, 0x0b, 0xc8, 0x4b, 0x5d, 0xe7, 0x4d, 0x0b, 0x10,
    ]),
    (133, [
        0x42, 0x50, 0x5a, 0x03, 0x91, 0x44, 0x9a, 0x39, 0xac, 0xbb, 0x1d, 0xf4, 0x71, 0x7b, 0xed, 0xff, 0x0e, 0x05,
        0x87, 0x6b, 0x52, 0x22, 0x83, 0x35, 0x7c, 0x6f, 0xfd, 0x41, 0xa6, 0xa4, 0x1f, 0x0e,
    ]),
    (134, [
        0xab, 0x66, 0xd7, 0xba, 0x51, 0x8c, 0x0c, 0x55, 0xb0, 0x8e, 0x78, 0x48, 0x04, 0xe4, 0x5e, 0xda, 0xf3, 0x41,
        0xed, 0x4d, 0x2a, 0xd5, 0x3f, 0xec, 0x80, 0x2d, 0x8f, 0x11, 0x07, 0x93, 0x42, 0x0d,
    ]),
    (450, [
        0x33, 0xc1, 0xff, 0xb3, 0x2a, 0xb0, 0xfd, 0x6e, 0xd3, 0x10, 0xee, 0xbb, 0x7d, 0x26, 0x20, 0xc8, 0x39, 0xfc,
        0x00, 0x35, 0xd3, 0x77, 0x67, 0xa2, 0x2e, 0x90, 0xb2, 0xea, 0x7b, 0x76, 0x62, 0x0e,
    ]),
    (452, [
        0x8f, 0xf3, 0x9e, 0xc3, 0x53, 0x6a, 0x76, 0x0a, 0x3b, 0x8d, 0x32, 0x29, 0x83, 0x69, 0x7f, 0x7c, 0x89, 0x36,
        0xb6, 0xe8, 0x28, 0x60, 0x1f, 0x0b, 0xa6, 0x75, 0x3b, 0xdf, 0x7f, 0x2f, 0xed, 0x11,
    ]),
    (768, [
        0x9b, 0x07, 0x98, 0x7b, 0x7e, 0xe4, 0xe6, 0x4b, 0xa2, 0xab, 0x8a, 0x0e, 0x77, 0x8f, 0x08, 0x53, 0x3d, 0x9d,
        0x6c, 0x3e, 0xdf, 0x2f, 0x6d, 0x4e, 0xf0, 0xee, 0x28, 0xd3, 0xb9, 0x8c, 0x7e, 0x03,
    ]),
    (771, [
        0xc2, 0x2e, 0x61, 0x41, 0xec, 0x3a, 0xb4, 0x37, 0x3a, 0xfc, 0xbb, 0x76, 0xeb, 0xa2, 0x82, 0x5c, 0xa4, 0x65,
        0x0d, 0xfb, 0x3d, 0xd5, 0x11, 0x65, 0x6d, 0x7e, 0xc1, 0x11, 0x19, 0xd2, 0x5d, 0x00,
    ]),
    (773, [
        0xac, 0xc3, 0xad, 0x40, 0xbb, 0x69, 0x73, 0x08, 0xa5, 0x24, 0xe0, 0xa0, 0xfc, 0xf8, 0x36, 0x0b, 0x56, 0xb2,
        0xe9, 0xc6, 0x42, 0xbb, 0x07, 0x7a, 0x52, 0xc2, 0x51, 0xbd, 0xbf, 0x8d, 0x6d, 0x0c,
    ]),
    (774, [
        0x7a, 0x3b, 0x4d, 0xb5, 0x7e, 0x47, 0xe4, 0xe0, 0x15, 0x4b, 0x8d, 0x31, 0x3f, 0x25, 0x7c, 0x79, 0x6d, 0xa5,
        0x6a, 0xf3, 0x8d, 0x6f, 0x99, 0x8f, 0xda, 0x85, 0x3e, 0xad, 0x26, 0x8a, 0x33, 0x12,
    ]),
];

static EXPECTATIONS_768: [(usize, [u8; 32]); 10] = [
    (70, [
        0xb3, 0x54, 0x5e, 0x94, 0x56, 0x61, 0xf2, 0xfd, 0xc2, 0xd9, 0x1d, 0x1e, 0x1b, 0xb7, 0xec, 0xb4, 0x75, 0x6d,
        0xb4, 0x36, 0x93, 0x77, 0xc1, 0x81, 0xb5, 0xe1, 0x9f, 0xaa, 0xf0, 0xa4, 0xb2, 0x09,
    ]),
    (71, [
        0xb3, 0x54, 0x5e, 0x94, 0x56, 0x61, 0xf2, 0xfd, 0xc2, 0xd9, 0x1d, 0x1e, 0x1b, 0xb7, 0xec, 0xb4, 0x75, 0x6d,
        0xb4, 0x36, 0x93, 0x77, 0xc1, 0x81, 0xb5, 0xe1, 0x9f, 0xaa, 0xf0, 0xa4, 0xb2, 0x09,
    ]),
    (72, [
        0xb3, 0x54, 0x5e, 0x94, 0x56, 0x61, 0xf2, 0xfd, 0xc2, 0xd9, 0x1d, 0x1e, 0x1b, 0xb7, 0xec, 0xb4, 0x75, 0x6d,
        0xb4, 0x36, 0x93, 0x77, 0xc1, 0x81, 0xb5, 0xe1, 0x9f, 0xaa, 0xf0, 0xa4, 0xb2, 0x09,
    ]),
    (73, [
        0x4e, 0x39, 0xe2, 0xb6, 0x0b, 0x83, 0x05, 0x83, 0x76, 0x89, 0x1f, 0xee, 0x4d, 0x78, 0x10, 0x71, 0xb6, 0x44,
        0x6d, 0xc3, 0x5b, 0x99, 0x94, 0x1c, 0x20, 0xf3, 0x46, 0x75, 0x2d, 0x7b, 0xdf, 0x0a,
    ]),
    (74, [
        0x19, 0xb5, 0x3e, 0x97, 0x21, 0x8b, 0x09, 0xfd, 0x9b, 0xdc, 0x2c, 0xb3, 0xc2, 0xe8, 0x68, 0x13, 0x28, 0x07,
        0x62, 0x7e, 0xd4, 0x88, 0xb9, 0x9f, 0xb8, 0x36, 0xa4, 0x97, 0x77, 0x29, 0xa4, 0x01,
    ]),
    (552, [
        0xf5, 0x86, 0x95, 0x07, 0x77, 0x77, 0x98, 0x1d, 0x1b, 0x21, 0x99, 0xf6, 0xa3, 0x05, 0x2f, 0xc0, 0xb5, 0x4d,
        0x4b, 0x47, 0x77, 0x43, 0x9a, 0xe2, 0x15, 0xb9, 0x65, 0xab, 0x0a, 0x3a, 0xfe, 0x0d,
    ]),
    (1029, [
        0x51, 0x2b, 0x29, 0xa1, 0x7e, 0x70, 0xc1, 0x10, 0x2c, 0xd8, 0x25, 0xbf, 0x1e, 0xb5, 0x6d, 0x52, 0x27, 0xfe,
        0x38, 0xa5, 0xbb, 0x56, 0x91, 0x0f, 0xe9, 0xb1, 0x60, 0xcd, 0x83, 0x60, 0x6f, 0x02,
    ]),
    (1032, [
        0x6a, 0xbd, 0x2e, 0xf7, 0x0f, 0xd1, 0x46, 0x03, 0x40, 0x02, 0x0d, 0xd6, 0x81, 0xdb, 0x0c, 0x2f, 0x88, 0x90,
        0x29, 0xef, 0x81, 0xd2, 0x29, 0x29, 0x7b, 0x84, 0xde, 0xd8, 0xaf, 0x2b, 0x57, 0x0f,
    ]),
    (1034, [
        0x18, 0xf1, 0x7f, 0xfe, 0x3c, 0x2e, 0xdf, 0x47, 0xda, 0xb3, 0x8f, 0x6c, 0x17, 0x32, 0x8c, 0x77, 0xc7, 0x73,
        0xe9, 0xaa, 0xfd, 0x6e, 0x7a, 0x55, 0xe5, 0x12, 0x20, 0x9b, 0xc0, 0xa8, 0x33, 0x06,
    ]),
    (1035, [
        0x18, 0xf1, 0x7f, 0xfe, 0x3c, 0x2e, 0xdf, 0x47, 0xda, 0xb3, 0x8f, 0x6c, 0x17, 0x32, 0x8c, 0x77, 0xc7, 0x73,
        0xe9, 0xaa, 0xfd, 0x6e, 0x7a, 0x55, 0xe5, 0x12, 0x20, 0x9b, 0xc0, 0xa8, 0x33, 0x06,
    ]),
];

static EXPECTATIONS_1024: [(usize, [u8; 32]); 10] = [
    (163, [
        0x7d, 0x7e, 0x51, 0x79, 0x94, 0xe8, 0xcc, 0x2a, 0x83, 0x04, 0x06, 0xb2, 0x0c, 0xc0, 0xd5, 0xb2, 0x3c, 0x77,
        0x5e, 0xe4, 0x3f, 0x06, 0x06, 0x08, 0xff, 0xa8, 0x6f, 0x23, 0xdf, 0x48, 0xdc, 0x0f,
    ]),
    (164, [
        0xc3, 0x0a, 0xdf, 0x59, 0x9d, 0x89, 0x45, 0x39, 0x7a, 0x21, 0x01, 0xc3, 0x1f, 0xd9, 0xcc, 0xac, 0x0c, 0x38,
        0xf3, 0x76, 0x93, 0xc7, 0x30, 0xb9, 0x67, 0x65, 0xb8, 0x42, 0x25, 0x82, 0x41, 0x0b,
    ]),
    (165, [
        0xc3, 0x0a, 0xdf, 0x59, 0x9d, 0x89, 0x45, 0x39, 0x7a, 0x21, 0x01, 0xc3, 0x1f, 0xd9, 0xcc, 0xac, 0x0c, 0x38,
        0xf3, 0x76, 0x93, 0xc7, 0x30, 0xb9, 0x67, 0x65, 0xb8, 0x42, 0x25, 0x82, 0x41, 0x0b,
    ]),
    (166, [
        0xdd, 0x6a, 0x1e, 0x62, 0x2b, 0x85, 0x93, 0x42, 0xbd, 0x87, 0x86, 0x8c, 0xc1, 0x4f, 0x7e, 0x3b, 0x7a, 0xb7,
        0x60, 0xbd, 0xfe, 0x09, 0x36, 0x57, 0x84, 0x46, 0xd5, 0x8a, 0x77, 0xed, 0x1e, 0x11,
    ]),
    (167, [
        0xdd, 0x6a, 0x1e, 0x62, 0x2b, 0x85, 0x93, 0x42, 0xbd, 0x87, 0x86, 0x8c, 0xc1, 0x4f, 0x7e, 0x3b, 0x7a, 0xb7,
        0x60, 0xbd, 0xfe, 0x09, 0x36, 0x57, 0x84, 0x46, 0xd5, 0x8a, 0x77, 0xed, 0x1e, 0x11,
    ]),
    (729, [
        0xf0, 0x73, 0x89, 0xfc, 0x5a, 0xfb, 0x91, 0x51, 0x8c, 0xc0, 0x96, 0x00, 0x56, 0x29, 0x8a, 0xdf, 0x6d, 0x79,
        0x02, 0xb6, 0xda, 0x73, 0xe7, 0x28, 0x1c, 0x39, 0xbd, 0x97, 0xbd, 0xdb, 0x58, 0x0e,
    ]),
    (1290, [
        0x18, 0x70, 0xa0, 0xef, 0x6a, 0xee, 0x4f, 0xbd, 0x8b, 0xdc, 0x9a, 0xb8, 0x8d, 0x71, 0xc3, 0x8d, 0x88, 0xf6,
        0xe3, 0x08, 0xc2, 0xdd, 0x53, 0x0b, 0x29, 0x7a, 0x75, 0x98, 0xe6, 0x58, 0xd2, 0x0d,
    ]),
    (1293, [
        0x6d, 0x21, 0x12, 0x60, 0xee, 0xd8, 0xc3, 0xa6, 0x21, 0xae, 0x1d, 0xc0, 0xb2, 0x7d, 0xb9, 0x4d, 0x27, 0x38,
        0x6e, 0x35, 0x98, 0xed, 0x06, 0x90, 0x8d, 0x5d, 0xec, 0x0d, 0xe0, 0x4b, 0x83, 0x07,
    ]),
    (1295, [
        0x6c, 0x0d, 0x33, 0xc0, 0x3f, 0x3d, 0x2e, 0x8e, 0xf3, 0x44, 0x66, 0xb3, 0x36, 0x99, 0x42, 0x18, 0xe9, 0x8f,
        0x5f, 0x74, 0xea, 0xfd, 0x32, 0xbf, 0x7a, 0x92, 0xee, 0x03, 0x8c, 0x21, 0x71, 0x0e,
    ]),
    (1296, [
        0x6c, 0x0d, 0x33, 0xc0, 0x3f, 0x3d, 0x2e, 0x8e, 0xf3, 0x44, 0x66, 0xb3, 0x36, 0x99, 0x42, 0x18, 0xe9, 0x8f,
        0x5f, 0x74, 0xea, 0xfd, 0x32, 0xbf, 0x7a, 0x92, 0xee, 0x03, 0x8c, 0x21, 0x71, 0x0e,
    ]),
];

// Deterministic input of a given length.
fn bits(len: usize) -> Vec<bool> {
    let mut rng = TestRng::from_seed(1012147);
    (0..len).map(|_| bool::rand(&mut rng)).collect()
}

/// Input lengths to test.
fn representative_lengths(min_len: usize, max_len: usize) -> Vec<usize> {
    let mid = (min_len + max_len) / 2;
    let mut v = vec![
        min_len,
        min_len + 1,
        min_len + BHP_CHUNK_SIZE - 1,
        min_len + BHP_CHUNK_SIZE,
        min_len + BHP_CHUNK_SIZE + 1,
        mid,
        mid - (mid % BHP_CHUNK_SIZE),
        max_len - 2 * BHP_CHUNK_SIZE,
        max_len - BHP_CHUNK_SIZE,
        max_len - 1,
        max_len,
    ];
    v.sort_unstable();
    v.dedup();
    v
}

macro_rules! bhp_hasher_uncompressed_vector_test {
    ($test_name:ident, $nw:literal, $ws:literal, $domain:literal, $expectations:ident) => {
        #[test]
        fn $test_name() -> Result<()> {
            type H = BHPHasher<Console, $nw, $ws>;
            let hasher = H::setup($domain)?;
            let window_size = $ws;
            let min_len = H::MIN_BITS + 1;
            let max_len = H::MAX_BITS;
            let lengths = representative_lengths(min_len, max_len);
            let expected: &[(usize, [u8; 32])] = &$expectations[..];

            assert_eq!(
                lengths.len(),
                expected.len(),
                "{}: representative_lengths vs expectations row count",
                stringify!($test_name)
            );

            let too_short = bits(window_size as usize * BHP_CHUNK_SIZE);
            assert!(hasher.hash_uncompressed(&too_short).is_err());
            assert!(hasher.hash_uncompressed(&bits(max_len + 1)).is_err());

            for (i, &n) in lengths.iter().enumerate() {
                assert_eq!(n, expected[i].0, "{}: length mismatch at index {i}", stringify!($test_name));
                let input = bits(n);
                assert_eq!(input.len(), n);
                let digest = hasher.hash_uncompressed(&input)?;
                let bytes = digest.to_bytes_le()?;
                assert_eq!(
                    digest,
                    hasher.hash_uncompressed(&input)?,
                    "determinism check for {} at length {n}",
                    stringify!($test_name)
                );
                assert_eq!(
                    bytes.as_slice(),
                    &expected[i].1[..],
                    "expectation mismatch for {} at input length {n}",
                    stringify!($test_name)
                );
            }

            Ok(())
        }
    };
}

bhp_hasher_uncompressed_vector_test!(test_bhp_vector_256, 3, 57, "BHPVec256", EXPECTATIONS_256);
bhp_hasher_uncompressed_vector_test!(test_bhp_vector_512, 6, 43, "BHPVec512", EXPECTATIONS_512);
bhp_hasher_uncompressed_vector_test!(test_bhp_vector_768, 15, 23, "BHPVec768", EXPECTATIONS_768);
bhp_hasher_uncompressed_vector_test!(test_bhp_vector_1024, 8, 54, "BHPVec1024", EXPECTATIONS_1024);

#[test]
#[ignore]
fn print_bhp_expectations() -> Result<()> {
    let print_row = |label: &str, n: usize, bytes: &[u8]| {
        eprint!("EXPECTATIONS_{label} ({n}): [");
        for (i, b) in bytes.iter().enumerate() {
            if i > 0 {
                eprint!(", ");
            }
            eprint!("0x{b:02x}");
        }
        eprintln!("]");
    };

    macro_rules! display_expectations {
        ($label:literal, $nw:literal, $ws:literal, $domain:literal) => {{
            type H = BHPHasher<Console, $nw, $ws>;
            let h = H::setup($domain)?;
            let min = H::MIN_BITS + 1;
            let max = H::MAX_BITS;
            eprintln!(
                "--- BHP {} (WINDOW_SIZE = {} windows, NUM_WINDOWS = {}, domain = {}) ---",
                $label, $ws, $nw, $domain
            );
            for &n in &representative_lengths(min, max) {
                print_row($label, n, &h.hash_uncompressed(&bits(n))?.to_bytes_le()?);
            }
        }};
    }
    display_expectations!("256", 3, 57, "BHPVec256");
    display_expectations!("512", 6, 43, "BHPVec512");
    display_expectations!("768", 15, 23, "BHPVec768");
    display_expectations!("1024", 8, 54, "BHPVec1024");
    Ok(())
}