graph_description_sha256.test.cpp

Go to the documentation of this file.

#include "barretenberg/boomerang_value_detection/graph.hpp"
#include "barretenberg/circuit_checker/circuit_checker.hpp"
#include "barretenberg/common/test.hpp"
#include "barretenberg/crypto/sha256/sha256.hpp"
#include "barretenberg/stdlib/hash/sha256/sha256.hpp"
#include "barretenberg/stdlib/primitives/byte_array/byte_array.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/plookup_tables.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
 
#include "barretenberg/numeric/bitop/rotate.hpp"
#include "barretenberg/numeric/bitop/sparse_form.hpp"
#include "barretenberg/numeric/random/engine.hpp"
 
using namespace bb;
using namespace bb::stdlib;
using namespace cdg;
 
using Builder = UltraCircuitBuilder;
using byte_array_ct = byte_array<Builder>;
using field_ct = field_t<Builder>;
 
std::vector<field_ct> pack_bytes_into_field_elements(const byte_array_ct& input, size_t num_bytes_in_chunk = 4)
{
    std::vector<field_t<Builder>> result;
    const size_t byte_len = input.size();
 
    for (size_t i = 0; i < byte_len; i += num_bytes_in_chunk) {
        byte_array_ct chunk = input.slice(i, std::min(num_bytes_in_chunk, byte_len - i));
        result.emplace_back(static_cast<field_ct>(chunk));
    }
 
    return result;
}
 
void fix_vector(std::vector<field_ct>& vector)
{
    for (auto& elem : vector) {
        elem.fix_witness();
    }
}
 
void fix_byte_array(byte_array_ct& input)
{
    for (size_t idx = 0; idx < input.size(); idx++) {
        input[idx].fix_witness();
    }
}
 
TEST(boomerang_stdlib_sha256, test_graph_for_sha256_55_bytes)
{
    // 55 bytes is the largest number of bytes that can be hashed in a single block,
    // accounting for the single padding bit, and the 64 size bits required by the SHA-256 standard.
    auto builder = Builder();
    byte_array_ct input(&builder, "An 8 character password? Snow White and the 7 Dwarves..");
    fix_byte_array(input);
 
    byte_array_ct output_bytes = stdlib::SHA256<Builder>::hash(input);
 
    std::vector<field_ct> output = pack_bytes_into_field_elements(output_bytes);
    fix_vector(output);
 
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    EXPECT_EQ(connected_components.size(), 1);
    auto variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
}
 
HEAVY_TEST(boomerang_stdlib_sha256, test_graph_for_sha256_NIST_vector_five)
{
    auto builder = Builder();
 
    byte_array_ct input(
        &builder,
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
        "AAAAAAAAAA");
 
    fix_byte_array(input);
    byte_array_ct output_bytes = stdlib::SHA256<bb::UltraCircuitBuilder>::hash(input);
 
    std::vector<field_ct> output = pack_bytes_into_field_elements(output_bytes);
    fix_vector(output);
 
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    auto variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
    EXPECT_EQ(connected_components.size(), 1);
}
 
TEST(boomerang_stdlib_sha256, test_graph_for_sha256_NIST_vector_one)
{
    auto builder = Builder();
    byte_array_ct input(&builder, "abc");
    fix_byte_array(input);
    byte_array_ct output_bytes = stdlib::SHA256<Builder>::hash(input);
    fix_byte_array(output_bytes);
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    EXPECT_EQ(connected_components.size(), 1);
    std::unordered_set<uint32_t> variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
}
 
TEST(boomerang_stdlib_sha256, test_graph_for_sha256_NIST_vector_two)
{
    auto builder = Builder();
    byte_array_ct input(&builder, "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq");
    fix_byte_array(input);
    byte_array_ct output_bytes = stdlib::SHA256<Builder>::hash(input);
    fix_byte_array(output_bytes);
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    EXPECT_EQ(connected_components.size(), 1);
    std::unordered_set<uint32_t> variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
}
 
TEST(boomerang_stdlib_sha256, test_graph_for_sha256_NIST_vector_three)
{
    auto builder = Builder();
 
    // one byte, 0xbd
    byte_array_ct input(&builder, std::vector<uint8_t>{ 0xbd });
    fix_byte_array(input);
    byte_array_ct output_bytes = stdlib::SHA256<Builder>::hash(input);
    fix_byte_array(output_bytes);
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    EXPECT_EQ(connected_components.size(), 1);
    std::unordered_set<uint32_t> variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
}
 
TEST(boomerang_stdlib_sha256, test_graph_for_sha256_NIST_vector_four)
{
    auto builder = Builder();
 
    // 4 bytes, 0xc98c8e55
    byte_array_ct input(&builder, std::vector<uint8_t>{ 0xc9, 0x8c, 0x8e, 0x55 });
    fix_byte_array(input);
    byte_array_ct output_bytes = stdlib::SHA256<Builder>::hash(input);
    fix_byte_array(output_bytes);
    StaticAnalyzer graph = StaticAnalyzer(builder);
    auto connected_components = graph.find_connected_components();
    EXPECT_EQ(connected_components.size(), 1);
    std::unordered_set<uint32_t> variables_in_one_gate = graph.show_variables_in_one_gate(builder);
    EXPECT_EQ(variables_in_one_gate.size(), 0);
}