How does Monero pick fake inputs?

门罗在生成交易时如何选择ringCT中除真实inputs以外的假inputs?

门罗的交易虽然被ringCT和bulletproof协议保护,但是内在仍然是遵守着bitcoin的UTXO模型。即每次交易的实际input,都需要对应上一个交易的output。

但是又由于ringCT的存在,门罗的交易需要选择之前出现过的他人的output来掩盖自己的output。

因为monerod本身不具备生成交易功能,我们可以确定这个pick过程发生并不在monerod中,而是在monero-wallet-rpc与monero-wallet-cli中。

由于cli(即simplewallet)操作较为直观因此从cli中的transfer命令作为切入点。

cli的源码在src/simplewallet/simplewallet.cpp

可以看到它直接调用了transfer_main,这个函数也在这个cpp源码中,主要负责的是对arguments的parsing,最后调用wallet的create_transactions_2

wallet对应的就是源码wallet模块,位于src/wallet/wallet2.cpp

接着我们逐行查看这个create_transactions_2在做什么

首先是函数头:

1
2
3
4
5
6
7
8
std::vector<wallet2::pending_tx> wallet2::create_transactions_2(
std::vector<cryptonote::tx_destination_entry> dsts,
const size_t fake_outs_count,
const uint64_t unlock_time,
uint32_t priority,
const std::vector<uint8_t>& extra,
uint32_t subaddr_account,
std::set<uint32_t> subaddr_indices)
  • dsts是指定的转账目标,可能有多个
  • fake_outs_count是指定的(除真实上个output以外)假output的数量,
  • unlock_time是指定的交易解锁时间(区块高度
  • priority是指定的交易优先级,钱包内部的
  • extra是指定的交易额外信息
  • subaddr_account是指定的转账子地址账户,仅一个。但是一个账户内可能有多个地址(对应多个index
  • subaddr_indices是指定的转账子地址的index,一个交易中可能有多个

然后我们直接跳到它使用fake_outs_count的地方

第一处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// early out if we know we can't make it anyway
// we could also check for being within FEE_PER_KB, but if the fee calculation
// ever changes, this might be missed, so let this go through
const uint64_t min_fee = (fee_multiplier * base_fee * estimate_tx_size(use_rct, 1, fake_outs_count, 2, extra.size(), bulletproof, clsag));
uint64_t balance_subtotal = 0;
uint64_t unlocked_balance_subtotal = 0;
for (uint32_t index_minor : subaddr_indices)
{
balance_subtotal += balance_per_subaddr[index_minor];
unlocked_balance_subtotal += unlocked_balance_per_subaddr[index_minor].first;
}
THROW_WALLET_EXCEPTION_IF(needed_money + min_fee > balance_subtotal, error::not_enough_money,
balance_subtotal, needed_money, 0);
// first check overall balance is enough, then unlocked one, so we throw distinct exceptions
THROW_WALLET_EXCEPTION_IF(needed_money + min_fee > unlocked_balance_subtotal, error::not_enough_unlocked_money,
unlocked_balance_subtotal, needed_money, 0);

for (uint32_t i : subaddr_indices)
LOG_PRINT_L2("Candidate subaddress index for spending: " << i);

这里是利用fake_outs_count计算出最小fee,然后检查账户余额是否足够发起交易(>fee+amount)。

紧跟着是两次调用

1
2
3
4
5
6
// determine threshold for fractional amount
const size_t tx_weight_one_ring = estimate_tx_weight(use_rct, 1, fake_outs_count, 2, 0, bulletproof, clsag);
const size_t tx_weight_two_rings = estimate_tx_weight(use_rct, 2, fake_outs_count, 2, 0, bulletproof, clsag);
THROW_WALLET_EXCEPTION_IF(tx_weight_one_ring > tx_weight_two_rings, error::wallet_internal_error, "Estimated tx weight with 1 input is larger than with 2 inputs!");
const size_t tx_weight_per_ring = tx_weight_two_rings - tx_weight_one_ring;
const uint64_t fractional_threshold = (fee_multiplier * base_fee * tx_weight_per_ring) / (use_per_byte_fee ? 1 : 1024);

这两次都是用在了estimate_tx_weight函数上,计算出了tx_weight_one_ring和tx_weight_two_rings两个值,用来得到fractional_threshold。

这个阈值在后面被拿来筛选outs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// gather all dust and non-dust outputs belonging to specified subaddresses
size_t num_nondust_outputs = 0;
size_t num_dust_outputs = 0;
for (size_t i = 0; i < m_transfers.size(); ++i)
{
const transfer_details& td = m_transfers[i];
if (m_ignore_fractional_outputs && td.amount() < fractional_threshold)
{
MDEBUG("Ignoring output " << i << " of amount " << print_money(td.amount()) << " which is below fractional threshold " << print_money(fractional_threshold));
continue;
}
if (!is_spent(td, false) && !td.m_frozen && !td.m_key_image_partial && (use_rct ? true : !td.is_rct()) && is_transfer_unlocked(td) && td.m_subaddr_index.major == subaddr_account && subaddr_indices.count(td.m_subaddr_index.minor) == 1)
{
if (td.amount() > m_ignore_outputs_above || td.amount() < m_ignore_outputs_below)
{
MDEBUG("Ignoring output " << i << " of amount " << print_money(td.amount()) << " which is outside prescribed range [" << print_money(m_ignore_outputs_below) << ", " << print_money(m_ignore_outputs_above) << "]");
continue;
}
const uint32_t index_minor = td.m_subaddr_index.minor;
auto find_predicate = [&index_minor](const std::pair<uint32_t, std::vector<size_t>>& x) { return x.first == index_minor; };
if ((td.is_rct()) || is_valid_decomposed_amount(td.amount()))
{
auto found = std::find_if(unused_transfers_indices_per_subaddr.begin(), unused_transfers_indices_per_subaddr.end(), find_predicate);
if (found == unused_transfers_indices_per_subaddr.end())
{
unused_transfers_indices_per_subaddr.push_back({index_minor, {i}});
}
else
{
found->second.push_back(i);
}
++num_nondust_outputs;
}
else
{
auto found = std::find_if(unused_dust_indices_per_subaddr.begin(), unused_dust_indices_per_subaddr.end(), find_predicate);
if (found == unused_dust_indices_per_subaddr.end())
{
unused_dust_indices_per_subaddr.push_back({index_minor, {i}});
}
else
{
found->second.push_back(i);
}
++num_dust_outputs;
}
}
}

如注释所述,这段代码开始收集属于指定的子地址的所有dust和非dust的outs

有关于什么是dust,可以看这个MRL-0004,举个例子就是发103.32111111时候有个0.00111111的output。

这里主要是统计出这些dust数量。当然这个算是个历史遗留问题了,现在的ringct上amount已经不可见所以不存在根据dust反推的问题。

暂时不管这个,继续看fake_outs_count的调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// for rct, since we don't see the amounts, we will try to make all transactions
// look the same, with 1 or 2 inputs, and 2 outputs. One input is preferable, as
// this prevents linking to another by provenance analysis, but two is ok if we
// try to pick outputs not from the same block. We will get two outputs, one for
// the destination, and one for change.
LOG_PRINT_L2("checking preferred");
std::vector<size_t> preferred_inputs;
uint64_t rct_outs_needed = 2 * (fake_outs_count + 1);
rct_outs_needed += 100; // some fudge factor since we don't know how many are locked
if (use_rct)
{
// this is used to build a tx that's 1 or 2 inputs, and 2 outputs, which
// will get us a known fee.
uint64_t estimated_fee = estimate_fee(use_per_byte_fee, use_rct, 2, fake_outs_count, 2, extra.size(), bulletproof, clsag, base_fee, fee_multiplier, fee_quantization_mask);
preferred_inputs = pick_preferred_rct_inputs(needed_money + estimated_fee, subaddr_account, subaddr_indices);
if (!preferred_inputs.empty())
{
string s;
for (auto i: preferred_inputs) s += boost::lexical_cast<std::string>(i) + " (" + print_money(m_transfers[i].amount()) + ") ";
LOG_PRINT_L1("Found preferred rct inputs for rct tx: " << s);

// bring the list of available outputs stored by the same subaddress index to the front of the list
uint32_t index_minor = m_transfers[preferred_inputs[0]].m_subaddr_index.minor;
for (size_t i = 1; i < unused_transfers_indices_per_subaddr.size(); ++i)
{
if (unused_transfers_indices_per_subaddr[i].first == index_minor)
{
std::swap(unused_transfers_indices_per_subaddr[0], unused_transfers_indices_per_subaddr[i]);
break;
}
}
for (size_t i = 1; i < unused_dust_indices_per_subaddr.size(); ++i)
{
if (unused_dust_indices_per_subaddr[i].first == index_minor)
{
std::swap(unused_dust_indices_per_subaddr[0], unused_dust_indices_per_subaddr[i]);
break;
}
}
}
}
LOG_PRINT_L2("done checking preferred");

对于 rct,由于我们没有看到金额,我们将尝试使所有交易看起来都相同,具有 1 或 2 个输入和 2 个输出。 1个input是可取的,因为这可以防止通过出处分析链接到另一个,但是如果我们尝试选择不是来自同一个块的输出,2个input也是可以的。 我们将得到两个输出,一个用于目的地,一个用于更改。

这里对fake_outs_count的利用是先计算出了rct_outs_needed,然后使用estimate_fee函数得到了预计的fee

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// while:
// - we have something to send
// - or we need to gather more fee
// - or we have just one input in that tx, which is rct (to try and make all/most rct txes 2/2)
unsigned int original_output_index = 0;
std::vector<size_t>* unused_transfers_indices = &unused_transfers_indices_per_subaddr[0].second;
std::vector<size_t>* unused_dust_indices = &unused_dust_indices_per_subaddr[0].second;

hwdev.set_mode(hw::device::TRANSACTION_CREATE_FAKE);
while (
(!dsts.empty() && dsts[0].amount > 0) || adding_fee ||
!preferred_inputs.empty() ||
should_pick_a_second_output(use_rct, txes.back().selected_transfers.size(), *unused_transfers_indices, *unused_dust_indices)
) {
TX &tx = txes.back();

后面的在这个while里,这个while实在是太大了所以先看看头部。

// while:
// - 我们有东西要发送
// - 或者我们需要收取更多费用
// - 或者我们在该 tx 中只有一个输入,即 rct(尝试使所有/大多数 rct txes 为 2/2)

这里就是在把以前交易的outputs一条条理过去,看需要哪几个以前的outputs能支持这次transfer

1
estimate_tx_weight(use_rct, tx.selected_transfers.size(), fake_outs_count, tx.dsts.size()+1, extra.size(), bulletproof, clsag) < TX_WEIGHT_TARGET(upper_transaction_weight_limit)

while中是使用了estimate_tx_weight来判断tx的weight是否超出限制

最后使用transfer_selected_rct(如果不用ringCT那就是transfer_selected,但是现在怎么可能不rct)

1
2
3
4
5
6
7
8
9
10
transfer_selected_rct(tx.dsts,                    /* NOMOD std::vector<cryptonote::tx_destination_entry> dsts,*/
tx.selected_transfers, /* const std::list<size_t> selected_transfers */
fake_outs_count, /* CONST size_t fake_outputs_count, */
tx.outs, /* MOD std::vector<std::vector<tools::wallet2::get_outs_entry>> &outs, */
unlock_time, /* CONST uint64_t unlock_time, */
tx.needed_fee, /* CONST uint64_t fee, */
extra, /* const std::vector<uint8_t>& extra, */
test_tx, /* OUT cryptonote::transaction& tx, */
test_ptx, /* OUT cryptonote::transaction& tx, */
rct_config);

这个是个将近300行的相比上一个“较为简单的”函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
if (outs.empty())
get_outs(outs, selected_transfers, fake_outputs_count, all_rct); // may throw

//prepare inputs
LOG_PRINT_L2("preparing outputs");
size_t i = 0, out_index = 0;
std::vector<cryptonote::tx_source_entry> sources;
std::unordered_set<rct::key> used_L;
for(size_t idx: selected_transfers)
{
...
...

THROW_WALLET_EXCEPTION_IF(outs.size() < out_index + 1 , error::wallet_internal_error, "outs.size() < out_index + 1");
THROW_WALLET_EXCEPTION_IF(outs[out_index].size() < fake_outputs_count , error::wallet_internal_error, "fake_outputs_count > random outputs found");

typedef cryptonote::tx_source_entry::output_entry tx_output_entry;
for (size_t n = 0; n < fake_outputs_count + 1; ++n)
{
tx_output_entry oe;
oe.first = std::get<0>(outs[out_index][n]);
oe.second.dest = rct::pk2rct(std::get<1>(outs[out_index][n]));
oe.second.mask = std::get<2>(outs[out_index][n]);
src.outputs.push_back(oe);
}
++i;

...
...

所以我们基本上可以确定了outs是从函数get_outs中得到

1
2
3
4
5
6
void wallet2::get_outs(
std::vector<std::vector<tools::wallet2::get_outs_entry>> &outs,
const std::vector<size_t> &selected_transfers,
size_t fake_outputs_count,
std::vector<uint64_t> &rct_offsets)
{

源码里有俩get_outs,千万别看错
transfer_selected_rct调用的第四个参数是all_rct,为一个vec
transfer_selected调用的第四个参数是false,为bool

这个函数非常nb的有将近600行……当然主要是因为兼顾了各个fork

主要的选妃流程差不多就这么点代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// make sure the real outputs we asked for are really included, along
// with the correct key and mask: this guards against an active attack
// where the node sends dummy data for all outputs, and we then send
// the real one, which the node can then tell from the fake outputs,
// as it has different data than the dummy data it had sent earlier
bool real_out_found = false;
for (size_t n = 0; n < requested_outputs_count; ++n)
{
size_t i = base + n;
if (req.outputs[i].index == td.m_global_output_index)
if (daemon_resp.outs[i].key == boost::get<txout_to_key>(td.m_tx.vout[td.m_internal_output_index].target).key)
if (daemon_resp.outs[i].mask == mask)
if (daemon_resp.outs[i].unlocked)
real_out_found = true;
}
THROW_WALLET_EXCEPTION_IF(!real_out_found, error::wallet_internal_error,
"Daemon response did not include the requested real output");

// pick real out first (it will be sorted when done)
outs.back().push_back(std::make_tuple(td.m_global_output_index, boost::get<txout_to_key>(td.m_tx.vout[td.m_internal_output_index].target).key, mask));

// then pick outs from an existing ring, if any
if (td.m_key_image_known && !td.m_key_image_partial)
{
std::vector<uint64_t> ring;
if (get_ring(get_ringdb_key(), td.m_key_image, ring))
{
for (uint64_t out: ring)
{
if (out < num_outs)
{
if (out != td.m_global_output_index)
{
bool found = false;
for (size_t o = 0; o < requested_outputs_count; ++o)
{
size_t i = base + o;
if (req.outputs[i].index == out)
{
LOG_PRINT_L2("Index " << i << "/" << requested_outputs_count << ": idx " << req.outputs[i].index << " (real " << td.m_global_output_index << "), unlocked " << daemon_resp.outs[i].unlocked << ", key " << daemon_resp.outs[i].key << " (from existing ring)");
tx_add_fake_output(outs, req.outputs[i].index, daemon_resp.outs[i].key, daemon_resp.outs[i].mask, td.m_global_output_index, daemon_resp.outs[i].unlocked);
found = true;
break;
}
}
THROW_WALLET_EXCEPTION_IF(!found, error::wallet_internal_error, "Falied to find existing ring output in daemon out data");
}
}
}
}
}

// then pick others in random order till we reach the required number
// since we use an equiprobable pick here, we don't upset the triangular distribution
std::vector<size_t> order;
order.resize(requested_outputs_count);
for (size_t n = 0; n < order.size(); ++n)
order[n] = n;
std::shuffle(order.begin(), order.end(), crypto::random_device{});

LOG_PRINT_L2("Looking for " << (fake_outputs_count+1) << " outputs of size " << print_money(td.is_rct() ? 0 : td.amount()));
for (size_t o = 0; o < requested_outputs_count && outs.back().size() < fake_outputs_count + 1; ++o)
{
size_t i = base + order[o];
LOG_PRINT_L2("Index " << i << "/" << requested_outputs_count << ": idx " << req.outputs[i].index << " (real " << td.m_global_output_index << "), unlocked " << daemon_resp.outs[i].unlocked << ", key " << daemon_resp.outs[i].key);
tx_add_fake_output(outs, req.outputs[i].index, daemon_resp.outs[i].key, daemon_resp.outs[i].mask, td.m_global_output_index, daemon_resp.outs[i].unlocked);
}
if (outs.back().size() < fake_outputs_count + 1)
{
scanty_outs[td.is_rct() ? 0 : td.amount()] = outs.back().size();
}
else
{
// sort the subsection, so any spares are reset in order
std::sort(outs.back().begin(), outs.back().end(), [](const get_outs_entry &a, const get_outs_entry &b) { return std::get<0>(a) < std::get<0>(b); });
}
base += requested_outputs_count;