Assigner efficiency on large data

[ETatuzova]

On large data assigner needs too much memory and spends too much time for tables and constraint systems generation.

#ifndef __ZKLLVM__
//#include "../../read_boost_json.hpp"
#include <cstdint>
#include <fstream>
#endif

#include <nil/crypto3/algebra/curves/pallas.hpp>
#include <nil/crypto3/hash/algorithm/hash.hpp>
#include <nil/crypto3/hash/sha2.hpp>

using namespace nil::crypto3;

#ifdef __ZKLLVM__
typename hashes::sha2<256>::block_type
    balance(std::array<typename hashes::sha2<256>::block_type, 0x200> layer_0_leaves) {

    const std::size_t layer_1_size = 0x100;
    std::array<typename hashes::sha2<256>::block_type, layer_1_size> layer_1_leaves;

    const std::size_t layer_2_size = 0x80;
    std::array<typename hashes::sha2<256>::block_type, layer_2_size> layer_2_leaves;

    const std::size_t layer_3_size = 0x40;
    std::array<typename hashes::sha2<256>::block_type, layer_3_size> layer_3_leaves;

    const std::size_t layer_4_size = 0x20;
    std::array<typename hashes::sha2<256>::block_type, layer_4_size> layer_4_leaves;

    const std::size_t layer_5_size = 0x10;
    std::array<typename hashes::sha2<256>::block_type, layer_5_size> layer_5_leaves;

    const std::size_t layer_6_size = 0x8;
    std::array<typename hashes::sha2<256>::block_type, layer_6_size> layer_6_leaves;

    const std::size_t layer_7_size = 0x4;
    std::array<typename hashes::sha2<256>::block_type, layer_7_size> layer_7_leaves;

    const std::size_t layer_8_size = 0x2;
    std::array<typename hashes::sha2<256>::block_type, layer_8_size> layer_8_leaves;

    typename hashes::sha2<256>::block_type root;

    for (std::size_t leaf_index = 0; leaf_index < layer_1_size; leaf_index++) {
        layer_1_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_0_leaves[2 * leaf_index], layer_0_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_2_size; leaf_index++) {
        layer_2_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_1_leaves[2 * leaf_index], layer_1_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_3_size; leaf_index++) {
        layer_3_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_2_leaves[2 * leaf_index], layer_2_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_4_size; leaf_index++) {
        layer_4_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_3_leaves[2 * leaf_index], layer_3_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_5_size; leaf_index++) {
        layer_5_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_4_leaves[2 * leaf_index], layer_4_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_6_size; leaf_index++) {
        layer_6_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_5_leaves[2 * leaf_index], layer_5_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_7_size; leaf_index++) {
        layer_7_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_6_leaves[2 * leaf_index], layer_6_leaves[2 * leaf_index + 1]);
    }

    for (std::size_t leaf_index = 0; leaf_index < layer_8_size; leaf_index++) {
        layer_8_leaves[leaf_index] =
            hash<hashes::sha2<256>>(layer_7_leaves[2 * leaf_index], layer_7_leaves[2 * leaf_index + 1]);
    }

    root = hash<hashes::sha2<256>>(layer_8_leaves[0], layer_8_leaves[1]);

    return root;
}

[[circuit]]
typename hashes::sha2<256>::block_type compute_root(
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_0_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_1_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_2_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_3_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_4_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_5_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_6_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_7_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_8_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_9_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_10_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_11_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_12_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_13_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_14_leaves,
    std::array<typename hashes::sha2<256>::block_type, 0x200> tree_15_leaves
) {
    typename hashes::sha2<256>::block_type root0 = balance(tree_0_leaves);
#pragma zk_multi_prover 1
    typename hashes::sha2<256>::block_type root1 = balance(tree_1_leaves);
#pragma zk_multi_prover 2
    typename hashes::sha2<256>::block_type root2 = balance(tree_2_leaves);
#pragma zk_multi_prover 3
    typename hashes::sha2<256>::block_type root3 = balance(tree_3_leaves);
#pragma zk_multi_prover 4
    typename hashes::sha2<256>::block_type root4 = balance(tree_4_leaves);
#pragma zk_multi_prover 5
    typename hashes::sha2<256>::block_type root5 = balance(tree_5_leaves);
#pragma zk_multi_prover 6
    typename hashes::sha2<256>::block_type root6 = balance(tree_6_leaves);
#pragma zk_multi_prover 7
    typename hashes::sha2<256>::block_type root7 = balance(tree_7_leaves);
#pragma zk_multi_prover 8
    typename hashes::sha2<256>::block_type root8 = balance(tree_8_leaves);
#pragma zk_multi_prover 9
    typename hashes::sha2<256>::block_type root9 = balance(tree_9_leaves);
#pragma zk_multi_prover 10
    typename hashes::sha2<256>::block_type root10 = balance(tree_10_leaves);
#pragma zk_multi_prover 11
    typename hashes::sha2<256>::block_type root11 = balance(tree_11_leaves);
#pragma zk_multi_prover 12
    typename hashes::sha2<256>::block_type root12 = balance(tree_12_leaves);
#pragma zk_multi_prover 13
    typename hashes::sha2<256>::block_type root13 = balance(tree_13_leaves);
#pragma zk_multi_prover 14
    typename hashes::sha2<256>::block_type root14 = balance(tree_14_leaves);
#pragma zk_multi_prover 15
    typename hashes::sha2<256>::block_type root15 = balance(tree_15_leaves);
#pragma zk_multi_prover 16
    root0 = hash<hashes::sha2<256>>(root0, root1);
    root1 = hash<hashes::sha2<256>>(root2, root3);
    root2 = hash<hashes::sha2<256>>(root4, root5);
    root3 = hash<hashes::sha2<256>>(root6, root7);
    root4 = hash<hashes::sha2<256>>(root8, root9);
    root5 = hash<hashes::sha2<256>>(root10, root11);
    root6 = hash<hashes::sha2<256>>(root12, root13);
    root7 = hash<hashes::sha2<256>>(root14, root15);

    root0 = hash<hashes::sha2<256>>(root0, root1);
    root1 = hash<hashes::sha2<256>>(root2, root3);
    root2 = hash<hashes::sha2<256>>(root4, root5);
    root3 = hash<hashes::sha2<256>>(root6, root7);

    root0 = hash<hashes::sha2<256>>(root0, root1);
    root1 = hash<hashes::sha2<256>>(root2, root3);

    return hash<hashes::sha2<256>>(root0, root1);
}
#endif

#ifndef __ZKLLVM__

int main (int argc, char *argv[]){
    if (argc != 2) {
        std::cerr << "one command line argument must be provided\n";
        std::abort();
    }
/*
    boost::json::value input_json = read_boost_json(std::string(argv[1]));

    uint32_t a = read_uint<uint32_t>(input_json, 0);

    shift_add(a);*/
    return 0;
}
#endif

[ETatuzova]

Arithmetization for this test:

constexpr std::size_t ComponentConstantColumns = 2;
constexpr std::size_t LookupConstantColumns = 14;
constexpr std::size_t ComponentSelectorColumns = 30;
constexpr std::size_t LookupSelectorConstantColumns = 6;
constexpr std::size_t WitnessColumns = 15;
constexpr std::size_t PublicInputColumns = 1;

const std::uint32_t max_usable_rows = 1048575; // SHA256 2^20 configuration

[akokoshn]

Input file: tree512.inp.txt

[akokoshn]

Troubles:

• Print assignment:

  total time ~ 600 sec per prover
  plonk_assignment_table(...) ~ 30 sec per prover
  write to file ~ 550 sec per prover

• Rename copy constraint:

  rename takes about 40 min

• Not enough memory for parallel printing

Improve printing assignment/circuit: https://github.com/NilFoundation/zkLLVM/tree/439-improve-print-time

1. Resize table_values vector instead using push: reduce print time per prover 680 to 600 sec.

[akokoshn]

Suggestions:

• Directly write to file from table_values
• Rename copy constraints on generating nil::marshalling::types::bundle

[akokoshn]

Current solution for satisfy customer's needs: generate and print only part circuit/assignment table related to one prover: https://github.com/NilFoundation/zkLLVM/issues/406

[nkaskov]

Duplicates https://github.com/NilFoundation/zkLLVM/issues/406