// Copyright (c) 2014, The Monero Project
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are
// permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this list of
//    conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice, this list
//    of conditions and the following disclaimer in the documentation and/or other
//    materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its contributors may be
//    used to endorse or promote products derived from this software without specific
//    prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
// THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
// STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
// THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "gtest/gtest.h"

#include "carrot_core/device_ram_borrowed.h"
#include "carrot_impl/format_utils.h"
#include "carrot_impl/address_device_ram_borrowed.h"
#include "carrot_impl/spend_device_ram_borrowed.h"
#include "carrot_impl/subaddress_map_legacy.h"
#include "common/container_helpers.h"
#include "common/threadpool.h"
#include "crypto/crypto.h"
#include "crypto/generators.h"
#include "cryptonote_basic/cryptonote_format_utils.h"
#include "cryptonote_basic/verification_context.h"
#include "cryptonote_core/tx_verification_utils.h"
#include "curve_trees.h"
#include "fcmp_pp/fcmp_pp_serialization.h"
#include "fcmp_pp/fcmp_pp_types.h"
#include "fcmp_pp/prove.h"
#include "fcmp_pp/tower_cycle.h"
#include "misc_log_ex.h"
#include "profile_tools.h"
#include "ringct/rctOps.h"
#include "ringct/rctSigs.h"
#include "unit_tests_utils.h"
#include "string_tools.h"
#include "wallet/tx_builder.h"

#include <utility>
#include <vector>

#undef MONERO_DEFAULT_LOG_CATEGORY
#define MONERO_DEFAULT_LOG_CATEGORY "unit_tests.fcmp_pp"

//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
struct UnifiedOutputsAndKeys
{
    std::vector<crypto::secret_key> x_vec;
    std::vector<crypto::secret_key> y_vec;
    std::vector<fcmp_pp::UnifiedOutput> outputs;
};
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static rct::key biased_derive_key_image_generator(const rct::key O)
{
    crypto::public_key I;
    crypto::derive_key_image_generator(rct::rct2pk(O), true/*biased*/, I);
    return rct::pk2rct(I);
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static void store_key(uint8_t b[32], const rct::key &k)
{
    memcpy(b, k.bytes, 32);
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static rct::key load_key(const uint8_t b[32])
{
    rct::key k;
    memcpy(k.bytes, b, sizeof(k));
    return k;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static crypto::secret_key load_sk(const uint8_t b[32])
{
    crypto::secret_key sk;
    memcpy(sk.data, b, sizeof(sk));
    return sk;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
template <typename T>
static constexpr bool is_power_of_2(T v)
{
    static_assert(std::is_integral_v<T>);
    return (v > 0) && ((v & (v - 1)) == 0);
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static FcmpRerandomizedOutputCompressed rerandomize_output_manual(const rct::key &O, const rct::key &C)
{
    FcmpRerandomizedOutputCompressed res;

    // sample random r_o, r_i, r_r_i, r_c in [0, l)
    rct::key r_o = rct::skGen();
    rct::key r_i = rct::skGen();
    rct::key r_r_i = rct::skGen();
    rct::key r_c = rct::skGen();

    store_key(res.r_o, r_o);
    store_key(res.r_i, r_i);
    store_key(res.r_r_i, r_r_i);
    store_key(res.r_c, r_c);

    // O~ = O + r_o T
    rct::key O_tilde = rct::scalarmultKey(rct::pk2rct(crypto::get_T()), r_o);
    O_tilde = rct::addKeys(O_tilde, O);

    store_key(res.input.O_tilde, O_tilde);

    // I = Hp(O)
    // I~ = I + r_i U
    const rct::key I = biased_derive_key_image_generator(O);
    rct::key I_tilde = rct::scalarmultKey(rct::pk2rct(crypto::get_U()), r_i);
    I_tilde = rct::addKeys(I_tilde, I);

    store_key(res.input.I_tilde, I_tilde);

    // precomp T
    const ge_p3 T_p3 = crypto::get_T_p3();
    ge_dsmp T_dsmp;
    ge_dsm_precomp(T_dsmp, &T_p3);

    // R = r_i V + r_r_i T
    rct::key R;
    rct::addKeys3(R, r_i, rct::pk2rct(crypto::get_V()), r_r_i, T_dsmp);

    store_key(res.input.R, R);

    // C~ = C + r_c G
    rct::key C_tilde;
    rct::addKeys1(C_tilde, r_c, C);

    store_key(res.input.C_tilde, C_tilde);

    return res;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static const UnifiedOutputsAndKeys generate_random_outputs(const CurveTreesV1 &curve_trees,
    const std::size_t old_n_leaf_tuples,
    const std::size_t new_n_leaf_tuples)
{
    UnifiedOutputsAndKeys outs;
    outs.x_vec.resize(new_n_leaf_tuples);
    outs.y_vec.resize(new_n_leaf_tuples);
    outs.outputs.resize(new_n_leaf_tuples);

    tools::threadpool& tpool = tools::threadpool::getInstanceForCompute();
    tools::threadpool::waiter waiter(tpool);

    const std::size_t batch_size = 1 + (new_n_leaf_tuples / (std::size_t)tpool.get_max_concurrency());
    for (std::size_t i = 0; i < new_n_leaf_tuples; i+= batch_size)
    {
        const std::size_t end = std::min(i + batch_size, new_n_leaf_tuples);
        tpool.submit(&waiter, [&outs, i, end, old_n_leaf_tuples]()
        {
            for (std::size_t j = i; j < end; ++j)
            {
                const std::uint64_t unified_id = old_n_leaf_tuples + j;

                // Generate random output tuple
                // Note: lock contention slows this down quite a bit
                crypto::secret_key o,c;
                crypto::public_key O,C;
                crypto::generate_keys(O, o, o, false);
                crypto::generate_keys(C, c, c, false);

                const crypto::ec_point C_pt = rct::rct2pt(rct::pk2rct(C));
                const fcmp_pp::OutputPair output_pair = fcmp_pp::LegacyOutputPair{{O, C_pt}};

                auto unified_output = fcmp_pp::UnifiedOutput{
                        .unified_id  = unified_id,
                        .output_pair = std::move(output_pair)
                    };

                // Output pubkey O = xG + yT
                // In this test, x is o, y is zero
                crypto::secret_key x = std::move(o);
                crypto::secret_key y;
                sc_0((unsigned char *)y.data);

                outs.x_vec[j] = std::move(x);
                outs.y_vec[j] = std::move(y);
                outs.outputs[j] = std::move(unified_output);
            }
        });
    }

    CHECK_AND_ASSERT_THROW_MES(waiter.wait(), "Failed generating random outputs");

    return outs;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static void make_empty_fcmp_pp_pruned_tx_of_size(const size_t n_inputs,
    const size_t n_outputs,
    const size_t extra_len,
    const bool max_int_fields,
    cryptonote::transaction &tx_out)
{
    const cryptonote::txin_to_key in{};
    const cryptonote::txin_v in_v{in};

    const cryptonote::txout_to_carrot_v1 out_targ{};
    const cryptonote::tx_out out{.target = out_targ};

    tx_out.set_null();

    // prefix
    tx_out.version = 2;
    tx_out.vin = std::vector<cryptonote::txin_v>(n_inputs, in_v);
    tx_out.vout = std::vector<cryptonote::tx_out>(n_outputs, out);
    tx_out.extra.resize(extra_len);

    // rctSigBase
    rct::rctSig &rv = tx_out.rct_signatures;
    rv.type = rct::RCTTypeFcmpPlusPlus;
    rv.txnFee = max_int_fields ? std::numeric_limits<rct::xmr_amount>::max() : 0;
    rv.outPk.resize(n_outputs);
    rv.ecdhInfo.resize(n_outputs);

    tx_out.pruned = true;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static void make_empty_fcmp_pp_tx_of_size(const size_t n_inputs,
    const size_t n_outputs,
    const size_t extra_len,
    const uint8_t n_tree_layers,
    const bool max_int_fields,
    cryptonote::transaction &tx_out)
{
    make_empty_fcmp_pp_pruned_tx_of_size(n_inputs, n_outputs, extra_len, max_int_fields, tx_out);
    tx_out.pruned = false;

    // BulletproofPlus
    size_t nlr = 0;
    while ((1u << nlr) < n_outputs)
      ++nlr;
    nlr += 6;
    rct::BulletproofPlus bpp;
    bpp.L = rct::keyV(nlr);
    bpp.R = rct::keyV(nlr);

    // rctSigPrunable
    rct::rctSig &rv = tx_out.rct_signatures;
    rv.p.bulletproofs_plus = {bpp};
    rv.p.pseudoOuts.resize(n_inputs);
    rv.p.reference_block = max_int_fields ? CRYPTONOTE_MAX_BLOCK_NUMBER : 0;
    rv.p.n_tree_layers = n_tree_layers;
    rv.p.fcmp_pp.resize(fcmp_pp::fcmp_pp_proof_len(n_inputs, n_tree_layers));
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static bool is_canonical_serializable_fcmp_pp_tx(const cryptonote::transaction &tx)
{
    // To check canonical-ness: serialize, deserialize, then re-serialize and:
    //     a. check serialization success
    //     b. check blob equality
    //     c. check tx hash equality

    CHECK_AND_ASSERT_MES(tx.version == 2 && tx.rct_signatures.type == rct::RCTTypeFcmpPlusPlus,
        false,
        "not a FCMP++ tx");
    CHECK_AND_ASSERT_MES(!tx.pruned, false, "not an unpruned tx");

    // a
    cryptonote::blobdata tx_blob_1;
    CHECK_AND_ASSERT_MES(cryptonote::tx_to_blob(tx, tx_blob_1), false, "failed to serialize tx");

    crypto::hash tx_hash_1;
    CHECK_AND_ASSERT_MES(cryptonote::calculate_transaction_hash(tx, tx_hash_1, nullptr),
        false,
        "failed to calculate tx hash");

    cryptonote::transaction tx_2;
    CHECK_AND_ASSERT_MES(cryptonote::parse_and_validate_tx_from_blob(tx_blob_1, tx_2),
        false,
        "failed to deserialize tx");

    cryptonote::blobdata tx_blob_2;
    CHECK_AND_ASSERT_MES(cryptonote::tx_to_blob(tx_2, tx_blob_2), false, "failed to re-serialize tx");

    crypto::hash tx_hash_2;
    CHECK_AND_ASSERT_MES(cryptonote::calculate_transaction_hash(tx_2, tx_hash_2, nullptr),
        false,
        "failed to calculate tx 2 hash");

    // b
    CHECK_AND_ASSERT_MES(tx_blob_1 == tx_blob_2, false, "re-serialized tx blob differs");
    // c
    CHECK_AND_ASSERT_MES(tx_hash_1 == tx_hash_2, false, "deserialized tx hash differs");

    return true;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
static std::map<std::tuple<size_t, size_t, size_t>, uint64_t> get_all_fcmp_tx_weights()
{
    // return a map of (n_inputs, n_outputs, extra_len) -> FCMP++ weight for all valid values
    std::map<std::tuple<size_t, size_t, size_t>, uint64_t> res;
    for (size_t m = 1; m <= FCMP_PLUS_PLUS_MAX_INPUTS; ++m)
        for (size_t n = 2; n <= FCMP_PLUS_PLUS_MAX_OUTPUTS; ++n)
            for (size_t el = 0; el <= MAX_TX_EXTRA_SIZE; ++el)
                res.insert({{m, n, el},
                    cryptonote::get_fcmp_pp_transaction_weight_v1(m, n, el)});

    static constexpr size_t expected_n_weights =
        FCMP_PLUS_PLUS_MAX_INPUTS * (FCMP_PLUS_PLUS_MAX_OUTPUTS - 1) * (MAX_TX_EXTRA_SIZE + 1);
    CHECK_AND_ASSERT_THROW_MES(res.size() == expected_n_weights, "bad tx weights counts");

    return res;
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, prove)
{
    static const std::size_t selene_chunk_width = fcmp_pp::curve_trees::SELENE_CHUNK_WIDTH;
    static const std::size_t helios_chunk_width = fcmp_pp::curve_trees::HELIOS_CHUNK_WIDTH;
    static const std::size_t tree_depth = 3;

    LOG_PRINT_L1("Test prove with selene chunk width " << selene_chunk_width
        << ", helios chunk width " << helios_chunk_width << ", tree depth " << tree_depth);

    uint64_t min_leaves_needed_for_tree_depth = 0;
    const auto curve_trees = test::init_curve_trees_test(selene_chunk_width,
        helios_chunk_width,
        tree_depth,
        min_leaves_needed_for_tree_depth);

    LOG_PRINT_L1("Initializing tree with " << min_leaves_needed_for_tree_depth << " leaves");

    // Init tree in memory
    CurveTreesGlobalTree global_tree(*curve_trees);
    const auto new_outputs = generate_random_outputs(*curve_trees, 0, min_leaves_needed_for_tree_depth);
    LOG_PRINT_L1("Finished generating random outputs");
    ASSERT_TRUE(global_tree.grow_tree(0, min_leaves_needed_for_tree_depth, new_outputs.outputs, false/*audit_tree*/));

    LOG_PRINT_L1("Finished initializing tree with " << min_leaves_needed_for_tree_depth << " leaves");

    const auto tree_root = global_tree.get_tree_root();

    // Keep them cached across runs
    std::vector<fcmp_pp::SeleneBranchBlind> selene_branch_blinds;
    std::vector<fcmp_pp::HeliosBranchBlind> helios_branch_blinds;
    std::vector<FcmpRerandomizedOutputCompressed> rerandomized_outputs;
    std::vector<fcmp_pp::FcmpPpSalProof> sal_proofs;
    std::vector<fcmp_pp::FcmpPpProveMembershipInput> fcmp_prove_inputs;
    std::vector<crypto::key_image> key_images;
    std::vector<crypto::ec_point> pseudo_outs;
    std::unordered_set<std::size_t> selected_indices;

    CHECK_AND_ASSERT_THROW_MES(global_tree.get_n_leaf_tuples() >= FCMP_PLUS_PLUS_MAX_INPUTS, "too few leaves");

    // Create proofs with n inputs {1, 2, 2 < random value < 128, 128}
    static_assert(FCMP_PLUS_PLUS_MAX_INPUTS > 2, "Expected max inputs > 2");
    const std::size_t rand_n_inputs = crypto::rand_range(size_t(3), size_t(FCMP_PLUS_PLUS_MAX_INPUTS-1));
    const std::vector<std::size_t> n_inputs_test_vec{1, 2, rand_n_inputs, FCMP_PLUS_PLUS_MAX_INPUTS};

    const crypto::hash signable_tx_hash{};

    // Create proofs with random leaf idxs for each n_inputs
    for (const std::size_t n_inputs : n_inputs_test_vec)
    {
        LOG_PRINT_L1("Preparing for " << n_inputs << "-input proof");

        while (fcmp_prove_inputs.size() < n_inputs)
        {
            // Generate a random unique leaf tuple index within the tree
            const size_t leaf_idx = crypto::rand_idx(global_tree.get_n_leaf_tuples());
            if (selected_indices.count(leaf_idx))
                continue;
            selected_indices.insert(leaf_idx);

            LOG_PRINT_L1("Constructing proof inputs for leaf idx " << leaf_idx << " (" << fcmp_prove_inputs.size()+1 << "/" << n_inputs << ")");

            const auto path = global_tree.get_path_at_leaf_idx(leaf_idx);
            const std::size_t output_idx = leaf_idx % curve_trees->m_c1_width;

            const fcmp_pp::OutputPair output_pair = fcmp_pp::LegacyOutputPair{{
                (crypto::public_key&)path.leaves[output_idx].O,
                (crypto::ec_point&)path.leaves[output_idx].C}};
            const auto output_tuple = fcmp_pp::curve_trees::output_to_tuple(output_pair);

            // ASSERT_TRUE(curve_trees->audit_path(path, output_pair, global_tree.get_n_leaf_tuples()));
            // LOG_PRINT_L1("Passed the audit...\n");

            const auto &x = new_outputs.x_vec[leaf_idx];
            const auto &y = new_outputs.y_vec[leaf_idx];

            // Leaves
            const auto path_for_proof = curve_trees->path_for_proof(path, output_tuple);

            const FcmpRerandomizedOutputCompressed rerandomized_output = fcmp_pp::rerandomize_output(output_tuple);

            pseudo_outs.emplace_back(rct::rct2pt(load_key(rerandomized_output.input.C_tilde)));

            key_images.emplace_back();
            crypto::generate_key_image((crypto::public_key&)path.leaves[output_idx].O,
                new_outputs.x_vec[leaf_idx],
                key_images.back());

            // Set path
            const auto helios_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::HeliosT>(
                path_for_proof.c2_scalar_chunks);
            const auto selene_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::SeleneT>(
                path_for_proof.c1_scalar_chunks);

            const auto path_rust = fcmp_pp::path_new({path_for_proof.leaves.data(), path_for_proof.leaves.size()},
                path_for_proof.output_idx,
                {helios_scalar_chunks.data(), helios_scalar_chunks.size()},
                {selene_scalar_chunks.data(), selene_scalar_chunks.size()});

            // Collect blinds for rerandomized output
            const auto o_blind = fcmp_pp::o_blind(rerandomized_output);
            const auto i_blind = fcmp_pp::i_blind(rerandomized_output);
            const auto i_blind_blind = fcmp_pp::i_blind_blind(rerandomized_output);
            const auto c_blind = fcmp_pp::c_blind(rerandomized_output);

            const auto blinded_o_blind = fcmp_pp::blind_o_blind(o_blind);
            const auto blinded_i_blind = fcmp_pp::blind_i_blind(i_blind);
            const auto blinded_i_blind_blind = fcmp_pp::blind_i_blind_blind(i_blind_blind);
            const auto blinded_c_blind = fcmp_pp::blind_c_blind(c_blind);

            const auto output_blinds = fcmp_pp::output_blinds_new(blinded_o_blind,
                blinded_i_blind,
                blinded_i_blind_blind,
                blinded_c_blind);

            // Cache branch blinds
            if (selene_branch_blinds.empty())
                for (std::size_t i = 0; i < helios_scalar_chunks.size(); ++i)
                    selene_branch_blinds.emplace_back(fcmp_pp::gen_selene_branch_blind());

            if (helios_branch_blinds.empty())
                for (std::size_t i = 0; i < selene_scalar_chunks.size(); ++i)
                    helios_branch_blinds.emplace_back(fcmp_pp::gen_helios_branch_blind());

            // Construct SAL proof
            const auto sal_proof = fcmp_pp::prove_sal(
                signable_tx_hash,
                x,
                y,
                rerandomized_output);

            // Collect input for membership proof
            auto fcmp_pp_prove_input = fcmp_pp::fcmp_pp_prove_input_new(
                path_rust,
                output_blinds,
                selene_branch_blinds,
                helios_branch_blinds);

            rerandomized_outputs.emplace_back(std::move(rerandomized_output));
            sal_proofs.emplace_back(std::move(sal_proof.first));
            fcmp_prove_inputs.emplace_back(std::move(fcmp_pp_prove_input));
        }

        LOG_PRINT_L1("Constructing membership proof and verifying (n_inputs=" << n_inputs << ")");
        const std::size_t n_layers = curve_trees->n_layers(global_tree.get_n_leaf_tuples());

        // Create membership proof
        LOG_PRINT_L1("Proving " << n_inputs << "-in " << n_layers << "-layer FCMP");
        const auto membership_proof = fcmp_pp::prove_membership(fcmp_prove_inputs, n_layers);

        // Serialize FCMP++ proof and verify
        const auto fcmp_pp_proof = fcmp_pp::fcmp_pp_proof_from_parts_v1(rerandomized_outputs,
            sal_proofs,
            membership_proof,
            n_layers);

        LOG_PRINT_L1("Verifying (n_inputs=" << n_inputs << ")");
        bool verify = fcmp_pp::verify(
                signable_tx_hash,
                fcmp_pp_proof,
                n_layers,
                tree_root,
                pseudo_outs,
                key_images
            );
        ASSERT_TRUE(verify);
        LOG_PRINT_L1("Successfully verified (n_inputs=" << n_inputs << ")");
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, verify)
{
    const uint8_t n_layers = 7;

    const auto curve_trees = fcmp_pp::curve_trees::curve_trees_v1();

    // Generate full chunks of outputs, enough to construct a tx with max inputs
    std::size_t n_generated_outputs = FCMP_PLUS_PLUS_MAX_INPUTS;
    if (n_generated_outputs % curve_trees->m_c1_width)
        n_generated_outputs = curve_trees->m_c1_width * ((n_generated_outputs / curve_trees->m_c1_width) + 1);
    const auto new_outputs = generate_random_outputs(*curve_trees, 0, n_generated_outputs);

    // Make sure we generated enough outputs and calculate expected n leaves in a dummy tree
    uint64_t expected_n_leaves = curve_trees->m_c1_width;
    for (uint8_t i = 1; i < n_layers; ++i)
        expected_n_leaves *= (i % 2 != 0) ? curve_trees->m_c2_width : curve_trees->m_c1_width;
    ASSERT_EQ(curve_trees->n_layers(expected_n_leaves), n_layers);
    ASSERT_GE(expected_n_leaves, new_outputs.outputs.size());

    // Instantiate dummy paths
    const auto paths = curve_trees->get_dummy_paths(new_outputs.outputs, n_layers);

    const auto tree_root = n_layers % 2 == 0
        ? fcmp_pp::helios_tree_root(paths.c2_layers.back().find(0)->second.back())
        : fcmp_pp::selene_tree_root(paths.c1_layers.back().find(0)->second.back());

    // Make branch blinds once purely for performance reasons (DO NOT DO THIS IN PRODUCTION)
    const size_t expected_num_selene_branch_blinds = n_layers / 2;
    LOG_PRINT_L1("Calculating " << expected_num_selene_branch_blinds << " Selene branch blinds");
    std::vector<fcmp_pp::SeleneBranchBlind> selene_branch_blinds;
    for (size_t i = 0; i < expected_num_selene_branch_blinds; ++i)
        selene_branch_blinds.emplace_back(fcmp_pp::gen_selene_branch_blind());

    const size_t expected_num_helios_branch_blinds = (n_layers - 1) / 2;
    LOG_PRINT_L1("Calculating " << expected_num_helios_branch_blinds << " Helios branch blinds");
    std::vector<fcmp_pp::HeliosBranchBlind> helios_branch_blinds;
    for (size_t i = 0; i < expected_num_helios_branch_blinds; ++i)
        helios_branch_blinds.emplace_back(fcmp_pp::gen_helios_branch_blind());

    const crypto::hash signable_tx_hash{};

    // Reuse inputs across runs to minimize time to construct
    std::vector<FcmpRerandomizedOutputCompressed> rerandomized_outputs;
    std::vector<fcmp_pp::FcmpPpSalProof> sal_proofs;
    std::vector<fcmp_pp::FcmpPpProveMembershipInput> fcmp_prove_inputs;
    std::vector<crypto::key_image> key_images;
    std::vector<crypto::ec_point> pseudo_outs;
    std::unordered_set<std::size_t> selected_indices;

    // Create proofs with n inputs {1, 2, 2 < random value < 128, 128}
    static_assert(FCMP_PLUS_PLUS_MAX_INPUTS > 2, "Expected max inputs > 2");
    const std::size_t rand_n_inputs = crypto::rand_range(size_t(3), size_t(FCMP_PLUS_PLUS_MAX_INPUTS-1));
    const std::vector<std::size_t> n_inputs_test_vec{1, 2, rand_n_inputs, FCMP_PLUS_PLUS_MAX_INPUTS};

    // Create proofs with random leaf idxs for each n_inputs
    for (const std::size_t n_inputs : n_inputs_test_vec)
    {
        std::unordered_set<std::size_t> selected_indices;
        LOG_PRINT_L1("Preparing for " << n_inputs << "-input proof");

        while (fcmp_prove_inputs.size() < n_inputs)
        {
            // Generate a random unique leaf tuple index within the tree
            const size_t leaf_idx = crypto::rand_idx(new_outputs.outputs.size());
            if (selected_indices.count(leaf_idx))
                continue;
            selected_indices.insert(leaf_idx);

            LOG_PRINT_L1("Constructing proof inputs for leaf idx " << leaf_idx << " (" << fcmp_prove_inputs.size()+1 << "/" << n_inputs << ")");

            const uint64_t leaf_chunk_idx = leaf_idx / curve_trees->m_c1_width;
            const auto leaf_offset = leaf_idx % curve_trees->m_c1_width;
            const auto &leaf_chunk = paths.leaves_by_chunk_idx.find(leaf_chunk_idx)->second;
            const auto &leaf = leaf_chunk[leaf_offset];

            const fcmp_pp::OutputPair output_pair = fcmp_pp::LegacyOutputPair{{
                (crypto::public_key&)leaf.O,
                (crypto::ec_point&)leaf.C}};
            const auto output_tuple = fcmp_pp::curve_trees::output_to_tuple(output_pair);

            const auto &x = new_outputs.x_vec[leaf_idx];
            const auto &y = new_outputs.y_vec[leaf_idx];

            // Construct single path from dummy paths
            const auto path = curve_trees->get_single_dummy_path(paths, expected_n_leaves, leaf_idx);
            ASSERT_TRUE(curve_trees->audit_path(path, output_pair, expected_n_leaves));

            // Leaves
            const auto path_for_proof = curve_trees->path_for_proof(path, output_tuple);

            const FcmpRerandomizedOutputCompressed rerandomized_output = fcmp_pp::rerandomize_output(output_tuple);

            pseudo_outs.emplace_back(rct::rct2pt(load_key(rerandomized_output.input.C_tilde)));

            key_images.emplace_back();
            crypto::generate_key_image((crypto::public_key&)leaf.O,
                new_outputs.x_vec[leaf_idx],
                key_images.back());

            // Set path
            const auto helios_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::HeliosT>(
                path_for_proof.c2_scalar_chunks);
            const auto selene_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::SeleneT>(
                path_for_proof.c1_scalar_chunks);

            const auto path_rust = fcmp_pp::path_new({path_for_proof.leaves.data(), path_for_proof.leaves.size()},
                path_for_proof.output_idx,
                {helios_scalar_chunks.data(), helios_scalar_chunks.size()},
                {selene_scalar_chunks.data(), selene_scalar_chunks.size()});

            // Collect blinds for rerandomized output
            const auto o_blind = fcmp_pp::o_blind(rerandomized_output);
            const auto i_blind = fcmp_pp::i_blind(rerandomized_output);
            const auto i_blind_blind = fcmp_pp::i_blind_blind(rerandomized_output);
            const auto c_blind = fcmp_pp::c_blind(rerandomized_output);

            const auto blinded_o_blind = fcmp_pp::blind_o_blind(o_blind);
            const auto blinded_i_blind = fcmp_pp::blind_i_blind(i_blind);
            const auto blinded_i_blind_blind = fcmp_pp::blind_i_blind_blind(i_blind_blind);
            const auto blinded_c_blind = fcmp_pp::blind_c_blind(c_blind);

            const auto output_blinds = fcmp_pp::output_blinds_new(blinded_o_blind,
                blinded_i_blind,
                blinded_i_blind_blind,
                blinded_c_blind);

            // Construct SAL proof
            const auto sal_proof = fcmp_pp::prove_sal(
                signable_tx_hash,
                x,
                y,
                rerandomized_output);

            // Collect input for membership proof
            auto fcmp_pp_prove_input = fcmp_pp::fcmp_pp_prove_input_new(
                path_rust,
                output_blinds,
                selene_branch_blinds,
                helios_branch_blinds);

            rerandomized_outputs.emplace_back(std::move(rerandomized_output));
            sal_proofs.emplace_back(std::move(sal_proof.first));
            fcmp_prove_inputs.emplace_back(std::move(fcmp_pp_prove_input));
        }

        LOG_PRINT_L1("Constructing membership proof and verifying (n_inputs=" << n_inputs << ")");

        // Create membership proof
        LOG_PRINT_L1("Proving " << n_inputs << "-in " << std::to_string(n_layers) << "-layer FCMP");
        TIME_MEASURE_START(prove_ms);
        const auto membership_proof = fcmp_pp::prove_membership(fcmp_prove_inputs, n_layers);
        TIME_MEASURE_FINISH(prove_ms);

        LOG_PRINT_L0("Constructed membership proof (n_inputs=" << n_inputs << ", " << prove_ms << "ms)");

        // Serialize FCMP++ proof and verify
        const auto fcmp_pp_proof = fcmp_pp::fcmp_pp_proof_from_parts_v1(rerandomized_outputs,
            sal_proofs,
            membership_proof,
            n_layers);

        LOG_PRINT_L1("Verifying (n_inputs=" << n_inputs << ")");
        TIME_MEASURE_START(verify_ms);
        bool verify = fcmp_pp::verify(
                signable_tx_hash,
                fcmp_pp_proof,
                n_layers,
                tree_root,
                pseudo_outs,
                key_images
            );
        TIME_MEASURE_FINISH(verify_ms);
        ASSERT_TRUE(verify);
        LOG_PRINT_L0("Successfully verified (n_inputs=" << n_inputs << ", " << verify_ms << "ms)");

        // const crypto::ec_point tree_root_bytes = n_layers % 2 == 0
        //     ? curve_trees->m_c2->to_bytes(paths.c2_layers.back().find(0)->second.back())
        //     : curve_trees->m_c1->to_bytes(paths.c1_layers.back().find(0)->second.back());

        // unit_test::write_fcmp_pp_verify_input_to_file(
        //     n_inputs,
        //     signable_tx_hash,
        //     fcmp_pp_proof,
        //     n_layers,
        //     tree_root_bytes,
        //     pseudo_outs,
        //     key_images);
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, batch_verify_from_file)
{
    const std::size_t n_inputs = 128;

    // We want a proof per thread, or 4 proofs if < 4 threads
    tools::threadpool& tpool = tools::threadpool::getInstanceForCompute();
    const std::size_t n_proofs = std::max<std::size_t>(4, tpool.get_max_concurrency());

    // We repeat verify attempts in hopes of using all malloc arenas (glibc specific)
    const std::size_t repeat_n_times = 10;

    // Read from file
    crypto::hash signable_tx_hash;
    std::vector<uint8_t> fcmp_pp_proof;
    uint8_t n_layers;
    fcmp_pp::TreeRootShared tree_root;
    std::vector<crypto::ec_point> pseudo_outs;
    std::vector<crypto::key_image> key_images;

    unit_test::read_fcmp_pp_verify_input_from_file(
        n_inputs,
        signable_tx_hash,
        fcmp_pp_proof,
        n_layers,
        tree_root,
        pseudo_outs,
        key_images);

    // Test single verification
    LOG_PRINT_L1("Verifying (n_inputs=" << n_inputs << ")");
    bool verify = fcmp_pp::verify(
            signable_tx_hash,
            fcmp_pp_proof,
            n_layers,
            tree_root,
            pseudo_outs,
            key_images
        );
    ASSERT_TRUE(verify);
    LOG_PRINT_L1("Successfully verified (n_inputs=" << n_inputs << ")");

    // Repeat batch verify attempts and observe memory usage
    for (std::size_t i = 0; i < repeat_n_times; ++i)
    {
        // Collect the FCMP++ verify inputs
        std::vector<fcmp_pp::FcmpPpVerifyInput> fcmp_pp_verify_inputs;
        fcmp_pp_verify_inputs.reserve(n_proofs);
        for (std::size_t i = 0; i < n_proofs; ++i)
        {
            fcmp_pp_verify_inputs.emplace_back(fcmp_pp::fcmp_pp_verify_input_new(
                    signable_tx_hash,
                    fcmp_pp_proof,
                    n_layers,
                    tree_root,
                    pseudo_outs,
                    key_images
                ));
        }

        // Verify FCMP++ 128-in proofs in parallel using the batch verifier
        LOG_PRINT_L1("Batch verifying " << n_proofs << " FCMP++ txs, attempt " << i+1);
        ASSERT_TRUE(rct::batchVerifyFcmpPpProofs(std::move(fcmp_pp_verify_inputs)));
        LOG_PRINT_L1("Successfully batch verified " << n_proofs << " FCMP++ txs, attempt " << i+1);
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, sal_completeness)
{
    // O, I, C, L
    const rct::key x = rct::skGen();
    const rct::key y = rct::skGen();
    rct::key O;
    rct::addKeys2(O, x, y, rct::pk2rct(crypto::get_T())); // O = x G + y T
    const rct::key I = biased_derive_key_image_generator(O);
    const rct::key C = rct::pkGen();
    crypto::key_image L;
    crypto::generate_key_image(rct::rct2pk(O), rct::rct2sk(x), L);

    // Rerandomize
    const auto output = fcmp_pp::output_tuple_from_bytes(rct::rct2pt(O), rct::rct2pt(I), rct::rct2pt(C));
    const FcmpRerandomizedOutputCompressed rerandomized_output{fcmp_pp::rerandomize_output(output)};

    // Generate signable_tx_hash
    const crypto::hash signable_tx_hash = crypto::rand<crypto::hash>();

    // Prove
    const std::pair<fcmp_pp::FcmpPpSalProof, crypto::key_image> sal_proof = fcmp_pp::prove_sal(
        signable_tx_hash,
        rct::rct2sk(x),
        rct::rct2sk(y),
        rerandomized_output);

    EXPECT_EQ(L, sal_proof.second);

    // Verify
    const bool ver = fcmp_pp::verify_sal(signable_tx_hash,
        rerandomized_output.input,
        L,
        sal_proof.first);

    EXPECT_TRUE(ver);
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, membership_completeness)
{
    // TODO: raise max num inputs and make test execute in reasonable time
    static const std::size_t MAX_NUM_INPUTS = 8;

    static const std::size_t selene_chunk_width = fcmp_pp::curve_trees::SELENE_CHUNK_WIDTH;
    static const std::size_t helios_chunk_width = fcmp_pp::curve_trees::HELIOS_CHUNK_WIDTH;
    static const std::size_t tree_depth = 3;
    static const std::size_t n_layers = 1 + tree_depth;

    LOG_PRINT_L1("Test prove with selene chunk width " << selene_chunk_width
        << ", helios chunk width " << helios_chunk_width << ", tree depth " << tree_depth);

    uint64_t min_leaves_needed_for_tree_depth = 0;
    const auto curve_trees = test::init_curve_trees_test(selene_chunk_width,
        helios_chunk_width,
        tree_depth,
        min_leaves_needed_for_tree_depth);

    LOG_PRINT_L1("Initializing tree with " << min_leaves_needed_for_tree_depth << " leaves");

    // Init tree in memory
    CurveTreesGlobalTree global_tree(*curve_trees);
    const auto new_outputs = generate_random_outputs(*curve_trees, 0, min_leaves_needed_for_tree_depth);
    ASSERT_TRUE(global_tree.grow_tree(0, min_leaves_needed_for_tree_depth, new_outputs.outputs));

    LOG_PRINT_L1("Finished initializing tree with " << min_leaves_needed_for_tree_depth << " leaves");

    const size_t num_tree_leaves = global_tree.get_n_leaf_tuples();

    // Make branch blinds once purely for performance reasons (DO NOT DO THIS IN PRODUCTION)
    const size_t expected_num_selene_branch_blinds = (tree_depth + 1) / 2;
    LOG_PRINT_L1("Calculating " << expected_num_selene_branch_blinds << " Selene branch blinds");
    std::vector<fcmp_pp::SeleneBranchBlind> selene_branch_blinds;
    for (size_t i = 0; i < expected_num_selene_branch_blinds; ++i)
        selene_branch_blinds.emplace_back(fcmp_pp::gen_selene_branch_blind());

    const size_t expected_num_helios_branch_blinds = tree_depth / 2;
    LOG_PRINT_L1("Calculating " << expected_num_helios_branch_blinds << " Helios branch blinds");
    std::vector<fcmp_pp::HeliosBranchBlind> helios_branch_blinds;
    for (size_t i = 0; i < expected_num_helios_branch_blinds; ++i)
        helios_branch_blinds.emplace_back(fcmp_pp::gen_helios_branch_blind());

    // For every supported input size...
    for (size_t num_inputs = 1; num_inputs <= MAX_NUM_INPUTS; ++num_inputs)
    {
        LOG_PRINT_L1("Starting " << num_inputs << "-in " << n_layers << "-layer test case");

        // Build up a set of `num_inputs` inputs to prove membership on
        ASSERT_LE(num_inputs, num_tree_leaves);
        std::set<size_t> selected_indices;
        std::vector<FcmpInputCompressed> fcmp_raw_inputs;
        fcmp_raw_inputs.reserve(num_inputs);
        std::vector<fcmp_pp::FcmpPpProveMembershipInput> fcmp_provable_inputs;
        fcmp_provable_inputs.reserve(num_inputs);
        while (selected_indices.size() < num_inputs)
        {
            // Generate a random unique leaf tuple index within the tree
            const size_t leaf_idx = crypto::rand_idx(num_tree_leaves);
            if (selected_indices.count(leaf_idx))
                continue;
            else
                selected_indices.insert(leaf_idx);

            // Fetch path
            const auto path = global_tree.get_path_at_leaf_idx(leaf_idx);
            const std::size_t output_idx = leaf_idx % curve_trees->m_c1_width;

            // Set up rust path
            const fcmp_pp::OutputPair output_pair = fcmp_pp::LegacyOutputPair{{
                (crypto::public_key&)path.leaves[output_idx].O,
                (crypto::ec_point&)path.leaves[output_idx].C}};
            const auto output_tuple = fcmp_pp::curve_trees::output_to_tuple(output_pair);
            const auto path_for_proof = curve_trees->path_for_proof(path, output_tuple);

            const auto helios_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::HeliosT>(
                path_for_proof.c2_scalar_chunks);
            const auto selene_scalar_chunks = fcmp_pp::tower_cycle::scalar_chunks_to_chunk_vector<fcmp_pp::SeleneT>(
                path_for_proof.c1_scalar_chunks);

            const auto path_rust = fcmp_pp::path_new({path_for_proof.leaves.data(), path_for_proof.leaves.size()},
                path_for_proof.output_idx,
                {helios_scalar_chunks.data(), helios_scalar_chunks.size()},
                {selene_scalar_chunks.data(), selene_scalar_chunks.size()});

            // Rerandomize output. We use rerandomize_output_manual() here just to test out the U, V
            // generators and manually constructing a FcmpRerandomizedOutputCompressed. But
            // fcmp_pp::rerandomize_output() would work perfectly fine here as well, especially
            // since we're not balancing C~ and thus don't need to modify it.
            const FcmpRerandomizedOutputCompressed rerandomized_output = rerandomize_output_manual(
                (rct::key&)path.leaves.at(output_idx).O,
                (rct::key&)path.leaves.at(output_idx).C);

            // check the size of our precalculated branch blind cache
            ASSERT_EQ(helios_scalar_chunks.size(), expected_num_selene_branch_blinds);
            ASSERT_EQ(selene_scalar_chunks.size(), expected_num_helios_branch_blinds);

            // Calculate output blinds for rerandomized output
            LOG_PRINT_L1("Calculating output blind");
            const SeleneScalar o_blind = fcmp_pp::o_blind(rerandomized_output);
            const SeleneScalar i_blind = fcmp_pp::i_blind(rerandomized_output);
            const SeleneScalar i_blind_blind = fcmp_pp::i_blind_blind(rerandomized_output);
            const SeleneScalar c_blind = fcmp_pp::c_blind(rerandomized_output);

            const auto blinded_o_blind = fcmp_pp::blind_o_blind(o_blind);
            const auto blinded_i_blind = fcmp_pp::blind_i_blind(i_blind);
            const auto blinded_i_blind_blind = fcmp_pp::blind_i_blind_blind(i_blind_blind);
            const auto blinded_c_blind = fcmp_pp::blind_c_blind(c_blind);

            const auto output_blinds = fcmp_pp::output_blinds_new(blinded_o_blind,
                blinded_i_blind,
                blinded_i_blind_blind,
                blinded_c_blind);
            
            // make provable FCMP input
            fcmp_provable_inputs.push_back(fcmp_pp::fcmp_pp_prove_input_new(
                path_rust,
                output_blinds,
                selene_branch_blinds,
                helios_branch_blinds));

            // get FCMP input
            fcmp_raw_inputs.push_back(rerandomized_output.input);
        }

        ASSERT_EQ(fcmp_raw_inputs.size(), fcmp_provable_inputs.size());

        // Create FCMP proof
        LOG_PRINT_L1("Proving " << num_inputs << "-in " << n_layers << "-layer FCMP");
        const fcmp_pp::FcmpMembershipProof proof = fcmp_pp::prove_membership(fcmp_provable_inputs,
            n_layers);

        // Verify
        LOG_PRINT_L1("Verifying " << num_inputs << "-in " << n_layers << "-layer FCMP");
        EXPECT_TRUE(fcmp_pp::verify_membership(proof, n_layers, global_tree.get_tree_root(), fcmp_raw_inputs));
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, force_init_gen_u_v)
{
#ifdef NDEBUG
    GTEST_SKIP() << "Generator reproduction assert statements don't trigger on Release builds";
#endif

    // these will cause assertion failures in debug mode if the seeds are wrong
    const ge_p3 U_p3 = crypto::get_U_p3();
    const ge_p3 V_p3 = crypto::get_V_p3();
    const ge_cached U_cached = crypto::get_U_cached();
    const ge_cached V_cached = crypto::get_V_cached();

    (void) U_p3, (void) V_p3, (void) U_cached, (void) V_cached;
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, calculate_fcmp_input_for_rerandomizations_convergence)
{
    const rct::key onetime_address = rct::pkGen();
    const rct::key amount_commitment = rct::pkGen();
    const rct::key I = biased_derive_key_image_generator(onetime_address);

    const fcmp_pp::OutputTuple output = fcmp_pp::output_tuple_from_bytes(rct::rct2pt(onetime_address),
        rct::rct2pt(I),
        rct::rct2pt(amount_commitment));
    const FcmpRerandomizedOutputCompressed rerandomized_output = fcmp_pp::rerandomize_output(output);

    const FcmpInputCompressed recomputed_input = fcmp_pp::calculate_fcmp_input_for_rerandomizations(
        rct::rct2pk(onetime_address),
        rct::rct2pt(amount_commitment),
        /*use_biased_hash_to_point=*/true,
        load_sk(rerandomized_output.r_o),
        load_sk(rerandomized_output.r_i),
        load_sk(rerandomized_output.r_r_i),
        load_sk(rerandomized_output.r_c));

    EXPECT_EQ(0, memcmp(&rerandomized_output.input, &recomputed_input, sizeof(FcmpInputCompressed)));
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, proof_size_table)
{
    static const uint32_t PROOF_LEN_TABLE[FCMP_PLUS_PLUS_MAX_INPUTS][FCMP_PLUS_PLUS_MAX_LAYERS]
    {
        {3136, 3776, 4160, 4800, 5184, 5824, 6208, 6848, 6272, 5696, 5952, 6336, },
        {4288, 5568, 4992, 6272, 6784, 6592, 7104, 7872, 7424, 6976, 7360, 7872, },
        {3840, 5760, 6528, 6976, 6528, 6592, 7232, 8000, 8512, 9280, 9088, 8768, },
        {4352, 6912, 6592, 7168, 7936, 8000, 8768, 9792, 9600, 9408, 10048, 10816, },
        {4992, 6976, 6528, 7232, 8256, 9536, 9344, 9408, 10176, 11200, 11968, 12864, },
        {3904, 6272, 7424, 8256, 8192, 8640, 9664, 10816, 11712, 12864, 13056, 13120, },
        {4160, 6912, 7104, 8064, 9216, 9792, 10944, 12224, 12416, 12736, 13760, 14912, },
        {4416, 7552, 7744, 8832, 10112, 10688, 11968, 13504, 13824, 14144, 15296, 16576, },
        {4800, 7232, 7424, 8640, 10048, 11840, 12288, 12864, 14144, 15680, 16960, 18368, },
        {5056, 7744, 7936, 9280, 10944, 12864, 13312, 14016, 15424, 17088, 18496, 20032, },
        {3840, 6784, 8576, 10048, 10624, 11840, 13504, 15168, 16704, 18496, 20160, 20992, },
        {3968, 7168, 9088, 10688, 11392, 12608, 14400, 16320, 17984, 19904, 20864, 21696, },
        {4096, 7552, 9600, 11328, 12160, 13504, 15424, 17472, 19264, 20480, 21440, 23232, },
        {4224, 7936, 9024, 10880, 12928, 14400, 16448, 18624, 19712, 20928, 22848, 24896, },
        {4352, 8320, 9536, 11520, 13696, 15296, 17472, 19776, 20864, 22208, 24256, 26432, },
        {4480, 8704, 9920, 12032, 14336, 15936, 18240, 20800, 22144, 23488, 25664, 27968, },
        {4736, 8256, 9472, 11712, 14144, 16832, 18304, 20032, 22464, 24896, 27200, 29632, },
        {4864, 8512, 9856, 12224, 14784, 17728, 19328, 21056, 23488, 26176, 28608, 31168, },
        {4992, 8896, 10368, 12864, 15552, 18624, 20224, 22080, 24768, 27456, 30016, 32832, },
        {5120, 9152, 10624, 13248, 16192, 19392, 21120, 23104, 25792, 28736, 31424, 34240, },
        {5248, 9536, 11136, 13888, 15872, 19200, 22016, 24128, 27072, 30144, 32960, 35904, },
        {3904, 8320, 11520, 14400, 16384, 19008, 22080, 25152, 28096, 31296, 34368, 36608, },
        {3904, 8576, 11904, 14912, 17152, 19776, 22848, 26176, 29376, 32704, 34944, 37184, },
        {4032, 8832, 12288, 15424, 17664, 20416, 23744, 27200, 30400, 33856, 36352, 38720, },
        {4160, 9216, 12800, 16064, 18432, 21312, 24640, 28224, 31680, 35264, 37760, 40256, },
        {4160, 9344, 13056, 16448, 18944, 21952, 25536, 29248, 32704, 35584, 38208, 41664, },
        {4288, 9728, 13568, 17088, 19584, 22720, 26432, 30272, 33152, 36032, 39616, 43328, },
        {4288, 9856, 12736, 16384, 20224, 23488, 27328, 31296, 34176, 37184, 40896, 44736, },
        {4416, 10240, 13120, 16896, 20864, 24128, 28096, 32320, 35328, 38464, 42304, 46144, },
        {4416, 10368, 13504, 17408, 21504, 25024, 29120, 33344, 36352, 39616, 43584, 47680, },
        {4544, 10752, 13888, 17920, 22144, 25664, 29888, 34368, 37632, 40896, 44992, 49216, },
        {4544, 10880, 14144, 18304, 22656, 26304, 30656, 35264, 38656, 42048, 46272, 50624, },
        {4672, 10304, 13696, 17984, 22464, 27200, 30720, 34496, 38848, 43328, 47680, 52160, },
        {4800, 10560, 13952, 18368, 22976, 27840, 31488, 35392, 40000, 44608, 49088, 53696, },
        {4800, 10688, 14336, 18880, 23616, 28736, 32512, 36416, 41024, 45760, 50368, 55232, },
        {4928, 10944, 14592, 19264, 24128, 29376, 33280, 37312, 42048, 47040, 51776, 56640, },
        {4928, 11200, 14976, 19776, 24896, 30144, 34048, 38336, 43200, 48192, 53056, 58048, },
        {5056, 11456, 15360, 20288, 25408, 30912, 34944, 39232, 44352, 49472, 54464, 59712, },
        {5056, 11584, 15616, 20672, 25920, 31552, 35840, 40256, 45376, 50752, 55872, 61120, },
        {5184, 11840, 15872, 21056, 26560, 32320, 36608, 41152, 46400, 51904, 57152, 62528, },
        {5312, 12224, 16384, 21696, 26240, 32128, 37504, 42176, 47552, 53056, 58560, 64192, },
        {5312, 12352, 16640, 22080, 26752, 32768, 38272, 43072, 48704, 54464, 59968, 65600, },
        {3968, 11136, 16896, 22464, 27264, 32576, 38336, 44096, 49728, 55616, 61248, 66176, },
        {3968, 11264, 17280, 22976, 27776, 33216, 39104, 44992, 50752, 56768, 62656, 67712, },
        {3968, 11520, 17664, 23488, 28544, 33984, 39872, 46016, 51904, 58048, 64064, 69120, },
        {3968, 11648, 17920, 23872, 29056, 34624, 40640, 46912, 53056, 59328, 64512, 69696, },
        {4096, 11904, 18304, 24384, 29568, 35264, 41536, 47936, 54080, 60480, 65792, 71104, },
        {4096, 12032, 18560, 24768, 30080, 35904, 42304, 48832, 55104, 61632, 67200, 72640, },
        {4096, 12288, 18944, 25280, 30720, 36672, 43200, 49856, 56384, 63040, 68608, 74176, },
        {4224, 12544, 19328, 25792, 31360, 37440, 43968, 50752, 57408, 64192, 69888, 75584, },
        {4224, 12672, 19584, 26176, 31872, 38080, 44736, 51648, 58432, 65344, 71168, 76992, },
        {4224, 12800, 19840, 26560, 32384, 38720, 45632, 52672, 59456, 65664, 71616, 78400, },
        {4224, 13056, 20352, 27200, 33024, 39360, 46400, 53696, 60736, 66944, 72896, 79808, },
        {4352, 13312, 20608, 27584, 33536, 40128, 47296, 54592, 60928, 67264, 74304, 81472, },
        {4352, 13440, 19776, 26880, 34176, 40896, 48064, 55488, 61952, 68416, 75584, 82880, },
        {4352, 13568, 20032, 27264, 34688, 41536, 48960, 56512, 62976, 69568, 76864, 84288, },
        {4480, 13952, 20416, 27776, 35328, 42176, 49728, 57536, 64128, 70720, 78144, 85696, },
        {4480, 14080, 20672, 28160, 35840, 42816, 50496, 58432, 65152, 72000, 79552, 87104, },
        {4480, 14208, 21056, 28672, 36352, 43584, 51392, 59328, 66176, 73152, 80832, 88640, },
        {4480, 14336, 21312, 29056, 36992, 44352, 52288, 60352, 67200, 74304, 82112, 90048, },
        {4608, 14720, 21696, 29568, 37632, 44992, 53056, 61376, 68480, 75584, 83520, 91584, },
        {4608, 14848, 21952, 29952, 38144, 45632, 53824, 62272, 69504, 76736, 84800, 92992, },
        {4608, 14976, 22208, 30336, 38656, 46272, 54592, 63168, 70528, 77888, 86080, 94400, },
        {4608, 15104, 22464, 30720, 39168, 46912, 55360, 64064, 71552, 79040, 87360, 95808, },
        {4736, 14528, 22016, 30400, 38976, 47808, 55424, 63296, 71744, 80320, 88768, 97344, },
        {4736, 14656, 22272, 30784, 39488, 48448, 56192, 64192, 72768, 81472, 90048, 98752, },
        {4736, 14784, 22528, 31168, 40000, 49088, 56960, 65088, 73792, 82624, 91328, 100160, },
        {4864, 15040, 22784, 31552, 40512, 49728, 57728, 65984, 74944, 83904, 92736, 101696, },
        {4864, 15168, 23040, 31936, 41152, 50496, 58624, 67008, 75968, 85056, 94016, 103104, },
        {4864, 15296, 23424, 32448, 41664, 51264, 59520, 67904, 76992, 86208, 95296, 104640, },
        {4864, 15424, 23680, 32832, 42176, 51904, 60288, 68800, 78016, 87488, 96704, 106048, },
        {4992, 15680, 23936, 33216, 42688, 52544, 61056, 69696, 79040, 88640, 97984, 107456, },
        {4992, 15936, 24320, 33728, 43328, 53184, 61824, 70720, 80192, 89792, 99264, 108864, },
        {4992, 16064, 24576, 34112, 43968, 53952, 62592, 71616, 81216, 90944, 100544, 110272, },
        {5120, 16320, 24832, 34496, 44480, 54720, 63488, 72512, 82240, 92096, 101952, 111936, },
        {5120, 16448, 25216, 35008, 44992, 55360, 64256, 73408, 83392, 93376, 103232, 113344, },
        {5120, 16576, 25472, 35392, 45504, 56000, 65152, 74432, 84416, 94656, 104640, 114752, },
        {5120, 16704, 25728, 35776, 46016, 56640, 65920, 75328, 85440, 95808, 105920, 116160, },
        {5248, 16960, 25984, 36160, 46656, 57408, 66688, 76224, 86464, 96960, 107200, 117568, },
        {5248, 17088, 26240, 36544, 47168, 58048, 67456, 77120, 87488, 98112, 108480, 118976, },
        {5248, 17344, 26624, 37056, 47808, 58816, 68352, 78144, 88640, 99264, 109888, 120640, },
        {5376, 17600, 27008, 37568, 47360, 58496, 69120, 79040, 89664, 100416, 111168, 122048, },
        {5376, 17728, 27264, 37952, 47872, 59136, 69888, 79936, 90816, 101696, 112448, 123456, },
        {5376, 17856, 27520, 38336, 48384, 59776, 70656, 80832, 91840, 102976, 113856, 124864, },
        {3904, 16512, 27776, 38720, 48896, 60416, 71424, 81728, 92864, 104128, 115136, 126272, },
        {4032, 16768, 28032, 39104, 49408, 60224, 71488, 82752, 93888, 105280, 116416, 126848, },
        {4032, 16896, 28288, 39488, 49920, 60864, 72256, 83648, 94912, 106432, 117696, 128256, },
        {4032, 17024, 28672, 40000, 50432, 61504, 73024, 84544, 95936, 107584, 119104, 129792, },
        {4032, 17280, 29056, 40512, 51200, 62272, 73792, 85568, 97088, 108736, 120384, 131200, },
        {4032, 17408, 29312, 40896, 51712, 62912, 74560, 86464, 98112, 110016, 121792, 132608, },
        {4032, 17536, 29568, 41280, 52224, 63552, 75328, 87360, 99264, 111296, 123072, 134016, },
        {4032, 17664, 29824, 41664, 52736, 64192, 76096, 88256, 100288, 112448, 123520, 134592, },
        {4160, 17920, 30080, 42048, 53248, 64832, 76864, 89152, 101312, 113600, 124800, 136000, },
        {4160, 18048, 30464, 42560, 53760, 65472, 77760, 90176, 102336, 114752, 126080, 137408, },
        {4160, 18176, 30720, 42944, 54272, 66112, 78528, 91072, 103360, 115904, 127488, 138944, },
        {4160, 18304, 30976, 43328, 54784, 66752, 79296, 91968, 104384, 117056, 128768, 140352, },
        {4160, 18560, 31360, 43840, 55424, 67520, 80192, 92992, 105536, 118336, 130176, 141888, },
        {4160, 18688, 31616, 44224, 55936, 68160, 80960, 93888, 106688, 119616, 131456, 143296, },
        {4160, 18816, 32000, 44736, 56576, 68928, 81728, 94784, 107712, 120768, 132736, 144704, },
        {4288, 19072, 32256, 45120, 57088, 69568, 82496, 95680, 108736, 121920, 134016, 146112, },
        {4288, 19200, 32512, 45504, 57600, 70208, 83264, 96576, 109760, 123072, 135296, 147520, },
        {4288, 19328, 32768, 45888, 58112, 70848, 84032, 97472, 110784, 124224, 136576, 148928, },
        {4288, 19456, 33024, 46272, 58624, 71488, 84928, 98496, 111808, 124544, 137024, 150336, },
        {4288, 19584, 33280, 46656, 59136, 72128, 85696, 99392, 112832, 125696, 138304, 151744, },
        {4288, 19840, 33792, 47296, 59776, 72768, 86464, 100416, 113984, 126848, 139584, 153152, },
        {4288, 19968, 34048, 47680, 60288, 73408, 87232, 101312, 115136, 128128, 140864, 154560, },
        {4416, 20224, 34304, 48064, 60800, 74176, 88128, 102208, 116160, 129280, 142144, 156096, },
        {4416, 20352, 34560, 48448, 61312, 74816, 88896, 103104, 116352, 129600, 143552, 157632, },
        {4416, 20480, 34816, 48832, 61952, 75584, 89664, 104000, 117376, 130752, 144832, 159040, },
        {4416, 20608, 33984, 48128, 62464, 76224, 90432, 104896, 118400, 131904, 146112, 160448, },
        {4416, 20736, 34240, 48512, 62976, 76864, 91328, 105920, 119424, 133056, 147392, 161856, },
        {4416, 20864, 34496, 48896, 63488, 77504, 92096, 106816, 120448, 134208, 148672, 163264, },
        {4416, 21120, 34880, 49408, 64128, 78144, 92864, 107840, 121600, 135360, 149952, 164672, },
        {4544, 21376, 35136, 49792, 64640, 78784, 93632, 108736, 122624, 136512, 151232, 166080, },
        {4544, 21504, 35392, 50176, 65152, 79424, 94400, 109632, 123648, 137664, 152512, 167488, },
        {4544, 21632, 35648, 50560, 65664, 80064, 95168, 110528, 124672, 138944, 153920, 168896, },
        {4544, 21760, 36032, 51072, 66176, 80704, 95936, 111424, 125696, 140096, 155200, 170304, },
        {4544, 21888, 36288, 51456, 66688, 81472, 96832, 112320, 126720, 141248, 156480, 171840, },
        {4544, 22016, 36544, 51840, 67328, 82240, 97600, 113216, 127744, 142400, 157760, 173248, },
        {4544, 22144, 36800, 52224, 67840, 82880, 98496, 114240, 128768, 143552, 159040, 174656, },
        {4672, 22528, 37184, 52736, 68480, 83520, 99264, 115264, 130048, 144832, 160320, 176064, },
        {4672, 22656, 37440, 53120, 68992, 84160, 100032, 116160, 131072, 145984, 161728, 177600, },
        {4672, 22784, 37696, 53504, 69504, 84800, 100800, 117056, 132096, 147136, 163008, 179008, },
        {4672, 22912, 37952, 53888, 70016, 85440, 101568, 117952, 133120, 148288, 164288, 180416, },
        {4672, 23040, 38208, 54272, 70528, 86080, 102336, 118848, 134144, 149440, 165568, 181824, },
        {4672, 23168, 38464, 54656, 71040, 86720, 103104, 119744, 135168, 150592, 166848, 183232, },
        {4672, 23296, 38720, 55040, 71552, 87360, 103872, 120640, 136192, 151744, 168128, 184640, },
        {4672, 23424, 38976, 55424, 72064, 88000, 104640, 121536, 137216, 152896, 169408, 186048, },
    };

    for (std::size_t i = 1; i <= FCMP_PLUS_PLUS_MAX_INPUTS; ++i)
    {
        // Uncomment the prints to construct the table
        // printf("{");
        for (std::size_t j = 1; j <= FCMP_PLUS_PLUS_MAX_LAYERS; ++j)
        {
            const std::size_t membership_proof_len = fcmp_pp::membership_proof_len(i, j);
            const std::size_t fcmp_pp_proof_len = fcmp_pp::fcmp_pp_proof_len(i, j);

            EXPECT_EQ(membership_proof_len, PROOF_LEN_TABLE[i-1][j-1]);
            EXPECT_EQ(fcmp_pp_proof_len, ::fcmp_pp_proof_size(i, j));

            // printf("%lu, ", membership_proof_len);
        }
        // printf("},\n");
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, tx_weight_monotonicity)
{
    static_assert(is_power_of_2(FCMP_PLUS_PLUS_MAX_INPUTS), "max input count must be a power of 2");
    static_assert(is_power_of_2(FCMP_PLUS_PLUS_MAX_OUTPUTS), "max output count must be a power of 2");

    // build up table of weight by in/out/extra count
    const auto tx_weights = get_all_fcmp_tx_weights();

    // assert that weight calculation is strictly monotonically increasing in all dimensions
    uint64_t max_weight = 0;
    for (const auto &p : tx_weights)
    {
        size_t m, n, el;
        std::tie(m, n, el) = p.first;
        const uint64_t weight = p.second;
        max_weight = std::max(weight, max_weight);
        if (m > 1)
        {
            const size_t other_weight = tx_weights.at({m - 1, n, el});
            ASSERT_GT(weight, other_weight);
        }
        if (n > 2)
        {
            const size_t other_weight = tx_weights.at({m, n - 1, el});
            ASSERT_GT(weight, other_weight);
        }
        if (el > 0)
        {
            const size_t other_weight = tx_weights.at({m, n, el - 1});
            ASSERT_GT(weight, other_weight);
        }
    }

    MDEBUG("Max FCMP++ tx weight: " << max_weight);
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, max_tx_weight)
{
    const uint64_t max_weight = cryptonote::get_fcmp_pp_transaction_weight_v1(FCMP_PLUS_PLUS_MAX_INPUTS,
        FCMP_PLUS_PLUS_MAX_OUTPUTS,
        MAX_TX_EXTRA_SIZE);
    ASSERT_EQ(max_weight, FCMP_PLUS_PLUS_MAX_TX_WEIGHT);
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, tx_weight_accuracy)
{
    // see fake_n_tree_layers comment in cryptonote::get_fcmp_pp_transaction_weight_v1
    static constexpr uint8_t fake_n_tree_layers = 7;

    // build up table of weight by in/out/extra count
    const auto tx_weights = get_all_fcmp_tx_weights();

    // collect all pairs of valid (n_inputs, n_outputs)
    std::set<std::pair<size_t, size_t>> valid_inout_counts;
    for (const auto &p : tx_weights)
        valid_inout_counts.insert({std::get<0>(p.first), std::get<1>(p.first)});
    ASSERT_EQ(FCMP_PLUS_PLUS_MAX_INPUTS * (FCMP_PLUS_PLUS_MAX_OUTPUTS - 1), valid_inout_counts.size());

    // for each valid value of tx in/out count...
    cryptonote::transaction example_tx;
    for (const auto &inout_count : valid_inout_counts)
    {
        size_t m, n;
        std::tie(m, n) = inout_count;

        // once with max_int_fields=false, once with max_int_fields=true...
        for (unsigned max_int_fields = 0; max_int_fields < 2; ++max_int_fields)
        {
             make_empty_fcmp_pp_tx_of_size(
                m,
                n,
                /*extra_len=*/0,
                fake_n_tree_layers,
                max_int_fields,
                example_tx);
            ASSERT_TRUE(is_canonical_serializable_fcmp_pp_tx(example_tx));
            ASSERT_EQ(m, example_tx.vin.size());
            ASSERT_EQ(n, example_tx.vout.size());
            ASSERT_EQ(fake_n_tree_layers, example_tx.rct_signatures.p.n_tree_layers);
            ASSERT_EQ(2, example_tx.version);
            ASSERT_EQ(rct::RCTTypeFcmpPlusPlus, example_tx.rct_signatures.type);
            example_tx.extra.reserve(MAX_TX_EXTRA_SIZE);

            // for each valid length of tx_extra...
            for (size_t el = 0; el <= MAX_TX_EXTRA_SIZE; ++el)
            {
                MDEBUG("Testing prefix/unprunable weight accuracy for " << m << "-in " << n << "-out " << el << "-byte-extra tx");

                // make tx_extra the right size
                example_tx.extra.resize(el);

                // serialize example tx
                const cryptonote::blobdata example_tx_blob = cryptonote::tx_to_blob(example_tx);

                // check that prefix weight is always equal to actual byte size
                EXPECT_EQ(example_tx.prefix_size, cryptonote::get_fcmp_pp_prefix_weight_v1(m, n, el));

                // check that the unprunable weight is equal to actual byte size when integer fields
                // are maxed out, and ever so slightly pessimistic (within 9 bytes) if not
                const uint64_t unprunable_weight = cryptonote::get_fcmp_pp_unprunable_weight_v1(m, n, el);
                const uint64_t allowed_unprunable_weight_margin = max_int_fields ? 0 : 9;
                ASSERT_GE(unprunable_weight, example_tx.unprunable_size);
                ASSERT_LE(unprunable_weight - example_tx.unprunable_size, allowed_unprunable_weight_margin);

                // check that the full weight is equal to actual byte size when integer fields
                // are maxed out, and ever so slightly pessimistic (within 13 bytes) if not
                const uint64_t full_weight = cryptonote::get_fcmp_pp_transaction_weight_v1(m, n, el);
                const uint64_t allowed_full_weight_margin = max_int_fields ? 0 : 13;
                ASSERT_GE(full_weight, example_tx_blob.size());
                ASSERT_LE(full_weight - example_tx_blob.size(), allowed_full_weight_margin);

                // check that the TX-based overload of `get_fcmp_pp_transaction_weight_v1` returns the same
                const uint64_t full_weight_2 = cryptonote::get_fcmp_pp_transaction_weight_v1(
                    static_cast<cryptonote::transaction_prefix&>(example_tx));
                ASSERT_EQ(full_weight, full_weight_2);
            }
        }
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, dump_tx_bytesizes)
{
    cryptonote::transaction example_tx;

    for (unsigned max_int_fields = 0; max_int_fields < 2; ++max_int_fields)
    {
        for (uint8_t n_tree_layers = 6; n_tree_layers <= 7; ++n_tree_layers)
        {
            std::cout << "layers=" << static_cast<int>(n_tree_layers) << " ";
            if (max_int_fields)
                std::cout << "maxvarint,";
            else
                std::cout << "minvarint,";

            for (std::size_t n = 2; n <= FCMP_PLUS_PLUS_MAX_OUTPUTS; ++n)
                std::cout << n << ',';
            std::cout << '\n';

            for (std::size_t m = 1; m <= FCMP_PLUS_PLUS_MAX_INPUTS; ++m)
            {
                std::cout << m << ',';
                for (std::size_t n = 2; n <= FCMP_PLUS_PLUS_MAX_OUTPUTS; ++n)
                {
                    make_empty_fcmp_pp_tx_of_size(
                        m,
                        n,
                        carrot::get_carrot_default_tx_extra_size(n),
                        n_tree_layers,
                        max_int_fields,
                        example_tx);

                    const cryptonote::blobdata serialized_blob = cryptonote::tx_to_blob(example_tx);

                    std::cout << serialized_blob.size() << ',';
                }
                std::cout << '\n';
            }

            std::cout << "-----------------------------------------\n";
        }
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, dump_pruned_tx_bytesizes)
{
    cryptonote::transaction example_tx;

    std::cout << ',';
    for (std::size_t n = 2; n <= FCMP_PLUS_PLUS_MAX_OUTPUTS; ++n)
        std::cout << n << ',';
    std::cout << '\n';

    for (std::size_t m = 1; m <= FCMP_PLUS_PLUS_MAX_INPUTS; ++m)
    {
        std::cout << m << ',';
        for (std::size_t n = 2; n <= FCMP_PLUS_PLUS_MAX_OUTPUTS; ++n)
        {
            make_empty_fcmp_pp_pruned_tx_of_size(
                m,
                n,
                carrot::get_carrot_default_tx_extra_size(n),
                /*max_int_fields=*/true,
                example_tx);

            const cryptonote::blobdata serialized_blob = cryptonote::tx_to_blob(example_tx);

            std::cout << serialized_blob.size() << ',';
        }
        std::cout << '\n';
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, output_serialization)
{
    static const crypto::public_key O{0x01};
    static const crypto::ec_point C{0x02};

    static const std::string O_str = "0100000000000000000000000000000000000000000000000000000000000000";
    static const std::string C_str = "0200000000000000000000000000000000000000000000000000000000000000";

    // 1. Check serialized bytes size
    const fcmp_pp::OutputPair legacy_output_pair = fcmp_pp::LegacyOutputPair{{O, C}};
    const fcmp_pp::OutputPair carrot_output_pair = fcmp_pp::CarrotOutputPairV1{{O, C}};
    ASSERT_FALSE(legacy_output_pair == carrot_output_pair);

    const cryptonote::blobdata legacy_serialized = cryptonote::t_serializable_object_to_blob(legacy_output_pair);
    const cryptonote::blobdata carrot_out_v1_ser = cryptonote::t_serializable_object_to_blob(carrot_output_pair);

    ASSERT_EQ(legacy_serialized.size(), (1+32+32));
    ASSERT_EQ(carrot_out_v1_ser.size(), (1+32+32));

    // 2. Check serialized byte string
    const std::string legacy_hex = epee::string_tools::buff_to_hex_nodelimer(legacy_serialized);
    const std::string carrot_hex = epee::string_tools::buff_to_hex_nodelimer(carrot_out_v1_ser);

    static const std::string LEGACY_TAG = "70";
    static const std::string CARROT_TAG = "71";

    ASSERT_EQ(legacy_hex, LEGACY_TAG + O_str + C_str);
    ASSERT_EQ(carrot_hex, CARROT_TAG + O_str + C_str);

    // 3. Check de-serialization
    const std::vector<std::pair<fcmp_pp::OutputPair, cryptonote::blobdata>> op_vec{
            {legacy_output_pair, legacy_serialized},
            {carrot_output_pair, carrot_out_v1_ser}
        };

    for (const auto &serialized : op_vec)
    {
        fcmp_pp::OutputPair output;
        ASSERT_TRUE(cryptonote::t_serializable_object_from_blob(output, serialized.second));
        ASSERT_EQ(output, serialized.first);
    }

    // 4. Check UnifiedOutput
    const uint64_t output_id = 8321;
    const fcmp_pp::UnifiedOutput legacy_unified_output{output_id, legacy_output_pair};
    const fcmp_pp::UnifiedOutput carrot_unified_output{output_id, carrot_output_pair};

    const cryptonote::blobdata legacy_unified_ser = cryptonote::t_serializable_object_to_blob(legacy_unified_output);
    const cryptonote::blobdata carrot_unified_ser = cryptonote::t_serializable_object_to_blob(carrot_unified_output);

    ASSERT_EQ(legacy_unified_ser.size(), SIZEOF_SERIALIZED_UNIFIED_OUTPUT);
    ASSERT_EQ(carrot_unified_ser.size(), SIZEOF_SERIALIZED_UNIFIED_OUTPUT);

    const std::string legacy_unified_hex = epee::string_tools::buff_to_hex_nodelimer(legacy_unified_ser);
    const std::string carrot_unified_hex = epee::string_tools::buff_to_hex_nodelimer(carrot_unified_ser);
    const std::string outpt_id_hex = epee::string_tools::buff_to_hex_nodelimer(
            cryptonote::t_serializable_object_to_blob(output_id)
        );

    ASSERT_EQ(legacy_unified_hex, outpt_id_hex + LEGACY_TAG + O_str + C_str);
    ASSERT_EQ(carrot_unified_hex, outpt_id_hex + CARROT_TAG + O_str + C_str);

    const std::vector<std::pair<fcmp_pp::UnifiedOutput, cryptonote::blobdata>> unified_vec{
            {legacy_unified_output, legacy_unified_ser},
            {carrot_unified_output, carrot_unified_ser}
        };

    for (const auto &serialized : unified_vec)
    {
        fcmp_pp::UnifiedOutput output;
        ASSERT_TRUE(cryptonote::t_serializable_object_from_blob(output, serialized.second));
        ASSERT_EQ(output, serialized.first);
    }
}
//----------------------------------------------------------------------------------------------------------------------
TEST(fcmp_pp, tx_sizes_and_verification_times)
{
    // 1. Make fake paths for a tree of 7 layers
    const uint8_t n_layers = 7;
    const auto curve_trees = fcmp_pp::curve_trees::curve_trees_v1();

    // Generate full chunks of outputs, enough to construct a tx with max inputs
    std::size_t n_generated_outputs = FCMP_PLUS_PLUS_MAX_INPUTS;
    if (n_generated_outputs % curve_trees->m_c1_width)
        n_generated_outputs = curve_trees->m_c1_width * ((n_generated_outputs / curve_trees->m_c1_width) + 1);

    // Make sure we generated enough outputs and calculate expected n leaves in a dummy tree
    uint64_t expected_n_leaves = curve_trees->m_c1_width;
    for (uint8_t i = 1; i < n_layers; ++i)
        expected_n_leaves *= (i % 2 != 0) ? curve_trees->m_c2_width : curve_trees->m_c1_width;
    ASSERT_EQ(curve_trees->n_layers(expected_n_leaves), n_layers);

    // Init an account we're going to "receive" the outputs to and "send" from
    cryptonote::account_base account;
    account.generate();
    const auto account_keys = account.get_keys();

    const crypto::secret_key &k_s = account_keys.m_spend_secret_key;
    const crypto::secret_key &k_v = account_keys.m_view_secret_key;
    const crypto::public_key &K_s = account_keys.m_account_address.m_spend_public_key;
    const auto k_view_incoming_dev = std::make_shared<carrot::cryptonote_view_incoming_key_ram_borrowed_device>(k_v);
    const carrot::cryptonote_hierarchy_address_device cn_addr_dev(k_view_incoming_dev, K_s);

    // Generate a bunch of miner txs, we'll use outputs from the miner txs to make the tree
    std::vector<fcmp_pp::UnifiedOutput> outputs;
    std::vector<cryptonote::transaction> txs;
    std::unordered_map<rct::xmr_amount, crypto::ec_point> transparent_amount_commitments;
    for (std::size_t i = 0; i < n_generated_outputs; ++i)
    {
        bool r = cryptonote::construct_miner_tx(0, 0, 5000, 500, 500, account_keys.m_account_address, txs.emplace_back());
        ASSERT_TRUE(r);

        const auto tx_out = txs.back().vout.back();
        crypto::public_key out_pubkey;
        ASSERT_TRUE(cryptonote::get_output_public_key(tx_out, out_pubkey));

        if (transparent_amount_commitments.find(tx_out.amount) == transparent_amount_commitments.end())
            transparent_amount_commitments[tx_out.amount] = rct::rct2pt(rct::zeroCommitVartime(tx_out.amount));

        fcmp_pp::LegacyOutputPair legacy_out{{out_pubkey, transparent_amount_commitments[tx_out.amount]}};

        outputs.push_back(fcmp_pp::UnifiedOutput{
                .unified_id = i,
                .output_pair = std::move(legacy_out),
            });
    }
    ASSERT_GE(expected_n_leaves, outputs.size());

    // Instantiate dummy paths in the truee
    const auto paths = curve_trees->get_dummy_paths(outputs, n_layers);

    // 2. Initialize tree cache
    fcmp_pp::curve_trees::TreeCacheV1 tree_cache(curve_trees);
    tree_cache.force_set_top_block_unsafe({ .blk_idx = 60/*coinbase unlock*/, .blk_hash = {}, .n_leaf_tuples = expected_n_leaves });

    // 3. Force add paths for every input
    for (std::size_t n_inputs = 1; n_inputs <= FCMP_PLUS_PLUS_MAX_INPUTS; ++n_inputs)
    {
        const size_t leaf_idx = n_inputs - 1;
        const auto &output = outputs.at(leaf_idx).output_pair;
        const auto path = curve_trees->get_single_dummy_path(paths, expected_n_leaves, leaf_idx);
        tree_cache.register_output(output);

        const auto path_idxs = curve_trees->get_path_indexes(expected_n_leaves, leaf_idx);
        std::vector<fcmp_pp::UnifiedOutput> unified_outputs;
        for (std::size_t l_idx = path_idxs.leaf_range.first; l_idx < path_idxs.leaf_range.second; ++l_idx)
            unified_outputs.push_back(outputs.at(l_idx));

        const auto compressed_path = curve_trees->compress_path(path, unified_outputs);
        tree_cache.force_add_output_path(output, leaf_idx, compressed_path, expected_n_leaves);
    }

    crypto::ec_point tree_root;
    tree_cache.get_tree_root(tree_root);
    const auto tree_root_ptr = curve_trees->get_tree_root_from_bytes(n_layers, tree_root);
    const std::unordered_map<crypto::public_key, cryptonote::subaddress_index> subaddrs{{ account_keys.m_account_address.m_spend_public_key, {0,0} }};

    // 4. Build the txs
    printf("Inputs, Outputs, Tx Size (bytes), Verify (ms), Membership Proof Size (bytes), Membership Proof Verify (ms)\n");
    for (std::size_t n_inputs = 1; n_inputs <= FCMP_PLUS_PLUS_MAX_INPUTS; ++n_inputs)
    {
        if (!is_power_of_2(n_inputs))
            continue;

        // 4a. Collect inputs
        std::vector<wallet2_basic::transfer_details> inputs;
        inputs.reserve(n_inputs);
        for (std::size_t i = 0; i < n_inputs; ++i)
        {
            const auto &input_tx = txs.at(i);
            const auto &output = outputs.at(i);
            const size_t internal_output_idx = input_tx.vout.size() - 1;

            const crypto::public_key in_tx_pub_key = cryptonote::get_tx_pub_key_from_extra(input_tx);
            cryptonote::keypair in_ephemeral;
            crypto::key_image key_image;
            bool r = cryptonote::generate_key_image_helper(
                account_keys,
                subaddrs,
                fcmp_pp::output_pubkey_cref(output.output_pair),
                in_tx_pub_key,
                {},
                internal_output_idx,
                in_ephemeral,
                key_image,
                hw::get_device("default"));
            ASSERT_TRUE(r);

            wallet2_basic::transfer_details wallet2_td{
                    .m_block_height = 0,
                    .m_tx = input_tx,
                    .m_txid = cryptonote::get_transaction_hash(input_tx),
                    .m_internal_output_index = internal_output_idx,
                    .m_global_output_index = i,
                    .m_spent = false,
                    .m_frozen = false,
                    .m_spent_height = 0,
                    .m_key_image = key_image,
                    .m_mask = rct::identity(),
                    .m_amount = input_tx.vout.at(internal_output_idx).amount,
                    .m_rct = input_tx.version >= 2,
                    .m_key_image_known = true,
                    .m_key_image_request = false,
                    .m_pk_index = 0,
                    .m_subaddr_index = {},
                    .m_key_image_partial = false,
                    .m_multisig_k = {},
                    .m_multisig_info = {},
                    .m_uses = {},
                };

            inputs.emplace_back(std::move(wallet2_td));
        }

        // 4b. Make the txs with the inputs
        for (std::size_t n_outputs = 2; n_outputs <= 2/*FCMP_PLUS_PLUS_MAX_OUTPUTS*/; ++n_outputs)
        {
            const auto tx_proposals = tools::wallet::make_carrot_transaction_proposals_wallet2_sweep_all(
                inputs,
                carrot::subaddress_map_legacy(subaddrs),
                /*only_below*/MONEY_SUPPLY,
                /*address*/account_keys.m_account_address,
                /*is_subaddress*/false,
                /*n_dests_per_tx*/n_outputs,
                /*fee_per_weight=*/1,
                /*extra=*/{},
                /*subaddr_account=*/0,
                /*subaddr_indices=*/{},
                /*top_block_index*/tree_cache.n_synced_blocks()-1);

            ASSERT_EQ(tx_proposals.size(), 1);

            const cryptonote::transaction finalized_tx = tools::wallet::finalize_all_fcmp_pp_proofs(
                tx_proposals.front(),
                tree_cache,
                *curve_trees,
                cn_addr_dev,
                *k_view_incoming_dev,
                /*s_view_balance_dev=*/nullptr,
                carrot::spend_device_ram_borrowed(k_s, k_v));

            // Serialize and de-serialize, then validate the de-serialized tx
            cryptonote::blobdata tx_blob;
            ASSERT_TRUE(cryptonote::tx_to_blob(finalized_tx, tx_blob));

            // 4c. Validate the tx
            const uint64_t start_validate = tools::get_tick_count();

            // Parse the tx
            const uint64_t start_parse = tools::get_tick_count();
            cryptonote::transaction tx;
            ASSERT_TRUE(cryptonote::parse_and_validate_tx_from_blob(tx_blob, tx));
            const uint64_t end_parse = tools::get_tick_count();

            // Verify non-input consensus rules
            const uint64_t start_non_input = tools::get_tick_count();
            cryptonote::tx_verification_context tvc{};
            ASSERT_TRUE(cryptonote::ver_non_input_consensus(tx, tvc, HF_VERSION_FCMP_PLUS_PLUS));
            ASSERT_FALSE(tvc.m_verifivation_failed);
            const uint64_t end_non_input = tools::get_tick_count();

            // Verify input proofs
            const uint64_t start_input = tools::get_tick_count();
            ASSERT_TRUE(cryptonote::ver_input_proofs_fcmps(tx, tree_root));
            const uint64_t end_input = tools::get_tick_count();

            // 4d. Print byte size and verification time
            // Collect timings
            const auto ticks_to_ms = [](const uint64_t ticks) -> uint64_t { return tools::ticks_to_ns(ticks) / 1e6; };
            const uint64_t validate_ms = ticks_to_ms(end_input - start_validate);
            const uint64_t parse_ms = ticks_to_ms(end_parse - start_parse);
            const uint64_t non_input_ms = ticks_to_ms(end_non_input - start_non_input);
            const uint64_t input_ms = ticks_to_ms(end_input - start_input);

            // 5. Do the membership proof only
            fcmp_pp::FcmpMembershipProof membership_proof;
            std::vector<FcmpInputCompressed> fcmp_raw_inputs;

            // Collect the membership proof inputs only
            {
                std::vector<crypto::ec_point> pseudo_outs;
                for (const auto &po : finalized_tx.rct_signatures.p.pseudoOuts)
                    pseudo_outs.emplace_back(rct::rct2pt(po));

                std::vector<fcmp_pp::FcmpPpSalProof> sal_proofs;
                fcmp_pp::fcmp_pp_parts_from_proof_v1(
                    tx.rct_signatures.p.fcmp_pp,
                    pseudo_outs,
                    n_layers,
                    membership_proof,
                    sal_proofs,
                    fcmp_raw_inputs);
            }

            const uint64_t start_membership = tools::get_tick_count();
            ASSERT_TRUE(fcmp_pp::verify_membership(membership_proof, n_layers, tree_root_ptr, fcmp_raw_inputs));
            const uint64_t end_membership = tools::get_tick_count();

            const uint64_t membership_ms = ticks_to_ms(end_membership - start_membership);

            LOG_PRINT_L1("Tx: " << obj_to_json_str(tx));
            LOG_PRINT_L1("Timings (ms) ... validate: " << validate_ms
                << " , parse: "                        << parse_ms
                << " , non_input_ms: "                 << non_input_ms
                << " , input_ms: "                     << input_ms
                << " , membership_ms: "                << membership_ms);

            // Inputs, Outputs, Tx Size (bytes), Verify (ms), Membership Proof Size (bytes), Membership Proof Verify (ms)
            printf("%lu, %lu, %lu, %lu, %lu, %lu\n",
                tx.vin.size(),
                tx.vout.size(),
                tx_blob.size(),
                validate_ms,
                membership_proof.size(),
                membership_ms);
        }
    }
}
//----------------------------------------------------------------------------------------------------------------------