Segfault on merkle tree.

[martun]

I receive segmentation fault on assigner call like this:

Circuit and inputs.zip

./build/bin/assigner/assigner -b build/examples/cpp/merkle_tree_256_1_cpp.ll -p examples/inputs/merkle_tree_256x1_private.inp -i examples/inputs/merkle_tree_256x1_public.inp -t merkle_tree_256_1_cpp_assignment.tbl -c merkle_tree_256_1_cpp_circuit.crct -e pallas
UNREACHABLE at /root/martun/zkLLVM/libs/assigner/include/nil/blueprint/parser.hpp:800
    Offset does not match memory
 #0 0x00007f1b30cd68d7 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/root/martun/zkLLVM/build/libs/circifier/llvm/lib/libLLVMSupport.so.17+0x1778d7)
 #1 0x00007f1b30cd484c llvm::sys::RunSignalHandlers() (/root/martun/zkLLVM/build/libs/circifier/llvm/lib/libLLVMSupport.so.17+0x17584c)
 #2 0x00007f1b30cd6f7a SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f1b2e4ed520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #4 0x00007f1b2e5419fc __pthread_kill_implementation ./nptl/./nptl/pthread_kill.c:44:76
 #5 0x00007f1b2e5419fc __pthread_kill_internal ./nptl/./nptl/pthread_kill.c:78:10
 #6 0x00007f1b2e5419fc pthread_kill ./nptl/./nptl/pthread_kill.c:89:10
 #7 0x00007f1b2e4ed476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #8 0x00007f1b2e4d37f3 abort ./stdlib/./stdlib/abort.c:81:7
 #9 0x000000000042e746 (./build/bin/assigner/assigner+0x42e746)
#10 0x000000000042e7bc (./build/bin/assigner/assigner+0x42e7bc)
#11 0x00000000006e071e (./build/bin/assigner/assigner+0x6e071e)
#12 0x00000000004d6dc0 nil::blueprint::parser<nil::crypto3::algebra::fields::pallas_base_field, nil::crypto3::zk::snark::plonk_arithmetization_params<15ul, 1ul, 35ul, 36ul> >::handle_gep(llvm::Value const*, llvm::Value const*, llvm::Type*, std::vector<int, std::allocator<int> > const&, nil::blueprint::stack_frame<nil::crypto3::zk::snark::plonk_variable<nil::crypto3::algebra::fields::detail::element_fp<nil::crypto3::algebra::fields::params<nil::crypto3::algebra::fields::pallas_base_field> > > >&) (./build/bin/assigner/assigner+0x4d6dc0)
#13 0x000000000049fb0b nil::blueprint::parser<nil::crypto3::algebra::fields::pallas_base_field, nil::crypto3::zk::snark::plonk_arithmetization_params<15ul, 1ul, 35ul, 36ul> >::handle_instruction(llvm::Instruction const*) (./build/bin/assigner/assigner+0x49fb0b)
#14 0x000000000045bb18 nil::blueprint::parser<nil::crypto3::algebra::fields::pallas_base_field, nil::crypto3::zk::snark::plonk_arithmetization_params<15ul, 1ul, 35ul, 36ul> >::evaluate(llvm::Module const&, boost::json::array const&, boost::json::array const&) (./build/bin/assigner/assigner+0x45bb18)
#15 0x000000000043a499 int curve_dependent_main<nil::crypto3::algebra::fields::pallas_base_field>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, long, bool, boost::log::v2s_mt_posix::trivial::severity_level, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, unsigned int, unsigned int, unsigned int, nil::blueprint::print_format) (./build/bin/assigner/assigner+0x43a499)
#16 0x0000000000433967 main (./build/bin/assigner/assigner+0x433967)
#17 0x00007f1b2e4d4d90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#18 0x00007f1b2e4d4e40 call_init ./csu/../csu/libc-start.c:128:20
#19 0x00007f1b2e4d4e40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#20 0x000000000041b5b5 _start (./build/bin/assigner/assigner+0x41b5b5)
Aborted (core dumped)

[ETatuzova]

Examples like this were assigned successfully few weeks ago.

[akokoshn]

The original issue caused by wrong memory access:

auto begin = layer0.begin();
result = evaluate_root<256>(begin, begin + 256, 256);

begin + 256 - leads invalid getelementptr, max allowed value is begin + 255 (size - 1)

Any way need to modify code of example because we don't support dynamic loops

[akokoshn]

If the final result is hash(hash(hash(0, 1), hash(2, 3)), hash(hash(4, 5), hash(6, 7)))

I suggest to use follow code without dynamic loops:

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

using namespace nil::crypto3;
using namespace nil::crypto3::algebra::curves;

using value_type = typename hashes::poseidon::block_type;

template<std::size_t size>
value_type evaluate_root(typename std::array<value_type, size>::iterator begin)
{
    std::size_t stride = 2;

    // stride = 2, 128 iter: hash(0, 1), ..., hash(254, 255)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 4, 64 iter: hash(0, 2), ..., hash(252, 254)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 8, 32 iter: hash(0, 4), ..., hash(248, 252)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 16, 16 iter: hash(0, 8), ..., hash(240, 248)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 32, 8 iter: hash(0, 16), hash(32, 48), hash(64, 80), hash(96, 112), ..., hash(224, 240)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 64, 4 iter: hash(0, 32), hash(64, 96), hash(128, 160), hash(192, 224)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 128, 2 iter: hash(0, 64), hash(64, 128)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }
    stride *= 2;
    // stride = 256, 1 iter: hash(0, 128)
    for(std::size_t i = 0; i < size; i += stride) {
        begin[i] = hash<hashes::poseidon>(begin[i], begin[i+(stride / 2)]);
    }

    return *begin;
}

/* parameters summary:
 * total number of leaves: 256
 * per prover: 256
 * total provers: 0
 */

[[circuit]] value_type merkle_tree (
    [[private_input]] std::array<value_type, 256> layer0)
{

    /* Last layer can be evaluated with one prover */
    value_type result;
    {
        auto begin = layer0.begin();
        result = evaluate_root<256>(begin);
    }

    return result;
}

[ETatuzova]

Yeah, but we have an error even without any loops. We can't use end() iterator at all. Is that right?

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

using namespace nil::crypto3;
using namespace nil::crypto3::algebra::curves;

using value_type = typename hashes::poseidon::block_type;

value_type evaluate_root(
    typename std::array<value_type, 4>::iterator begin,
    typename std::array<value_type, 4>::iterator end
)
{
    return *begin;
}

/* parameters summary:
 * total number of leaves: 4
 * per prover: 4
 * total provers: 0
 */

[[circuit]] value_type merkle_tree (
    [[private_input]] std::array<value_type, 4> layer0)
{
    /* Last layer can be evaluated with one prover */
    value_type result;
    result = evaluate_root(layer0.begin(), layer0.end());
    return result;
}

When we remove layer0.end(), this piece assignes well. Is that right, that we can't use end() iterator of array at all?

[martun]

Solution of @akokoshn works for me, we can close this.

[akokoshn]

@ETatuzova , we can use end() iterator, but can't access it: v = *arr.end(), because it out of memory access.

[akokoshn]

So @ETatuzova , @martun , can we close issue?