github-wownero/wownero
1
0
Fork 0
mirror of https://github.com/wownero/wownero.git synced 2026-10-18 16:11:41 +02:00
Code Issues Packages Projects Releases Wiki Activity
Files
fcmp-testnet
wownero/tests/unit_tests/fcmp_pp.cpp
T
+3
j-bermanjeffro256Luke ParkerLee *!* ClagettSyntheticBird45jeetrex17UkoeHBMrCyjaneKtobtohtselstaThomasnavidRBoog900
 a9145f9d38 FCMP++/Carrot mega commit [9/14/26] 
Co-authored-by: jeffro256 <jeffro256@tutanota.com>
Co-authored-by: Luke Parker <lukeparker5132@gmail.com>
Co-authored-by: Lee *!* Clagett <code@leeclagett.com>
Co-authored-by: SyntheticBird45 <someoneelse.is_on.github.rio7x@simplelogin.com>
Co-authored-by: jeetrex17 <jeetrex@tutamail.com>
Co-authored-by: UkoeHB <ukoehb@users.noreply.github.com>
Co-authored-by: MrCyjaneK
Co-authored-by: tobtoht
Co-authored-by: selsta
Co-authored-by: Thomas <thomas.giudici@proton.me>
Co-authored-by: navidR
Co-authored-by: Boog900 <boog900@tutanota.com>
2026-09-17 18:33:24 -07:00

1638 lines
79 KiB
C++
Raw Permalink Blame History

// 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);
}
}
}
//----------------------------------------------------------------------------------------------------------------------
Reference in New Issue View Git Blame Copy Permalink