search

monero-project / research-lab

A general repo for Monero Research Lab work in progress and completed work
242 stars 78 forks source link

Ring Binning #84

Open UkoeHB opened 3 years ago

UkoeHB commented 3 years ago

note: tx chaining was removed after discussion (July 18, 2020)

Table Of Contents

Abstract

Reference on-chain outputs for ring membership deterministically to minimize storage, and introduce a binning strategy to mitigate failures of the decoy selection distribution (e.g. gamma distribution).

Motivation

Monero is planning to implement a next-gen protocol with sublinear scaling that should allow ring sizes on the order of 2^6 to 2^8 (64 to 256) (either Triptych or some alternative). Referencing each ring member individually is inefficient, so 'deterministic' references are beneficial. 'Deterministic' means being able to recover an arbitrary number of on-chain indices from a small tuple of variables that include some kind of entropy.

As discussed in An Empirical Analysis of Traceability in the Monero Blockchain, selecting ring decoys directly from a distribution that spans the entire ledger is not perfect. If an observer has special timing knowledge about a given transaction, and/or knows that the selection distribution does not match the true spend distribution, then they can gain a significant advantage when trying to guess the true spends in that transaction.

That problem can be mitigated by selecting 'clumps' of decoys from the ledger-spanning selection distribution. A 'clump' (or 'bin') of decoys is a small set of decoys that are located very close to each other on the ledger. This way, even if an observer can guess the age of a transaction's true spend to within a few hours or less, the true spend will still be hidden among some decoys.

It isn't ideal to only select decoys that are close to the real spend. Even if some observers have special timing information about transactions, other observers may not. It is therefore useful to combine clumping/binning with selection from the ledger-wide distribution (recommended by Foundations of Ring Sampling).

This proposal describes a deterministic ring member referencing strategy where clumps/bins of decoys are selected from a ledger-wide distribution. Privacy considerations are discussed where appropriate.

Algorithm summary

To set the stage, I will briefly summarize the ring member referencing algorithm here (glossing over all the details, which can be found in the actual algorithm below). Each output spent by a transaction will have its own ring member reference tuple (set of variables to recover its set of ring members from).

  1. Define binning_upper_bound, which is the index of the highest output in the ledger that can be referenced by this input. Defining this is necessary so interacting with the ledger-wide selection distribution is deterministic.
  2. Choose a random output from a fixed range around the true spend [true_spend_index - bin_radius, true_spend_index + bin_radius], which is equal to the width that bins will have.
  3. Map that random output from the ledger-wide selection distribution (defined based on binning_upper_bound) to a uniform distribution with a CDF. Its value in the uniform distribution is denoted mapped_real_spend_bin_center.
  4. Use a hash function and public entropy to generate n points in the uniform distribution.
  5. Select a point n' at random from those n points. Define bin_rotator = mapped_real_spend_bin_center - n' mod uniform_distribution.size().
  6. Redefine all n points: n += bin_rotator mod uniform_distribution.size(). Note that n' will now equal mapped_real_spend_bin_center.
  7. Map all n points from the uniform distribution back into the ledger-wide selection distribution with a reverse CDF. All points mapped_n are 'bin centers', the centers of each of the bins in the final ring member reference set. If bins should have only one member each (bin_radius = 0), then mapped_n can be treated directly as ring member references and you don't need to proceed further.
  8. Around each bin center mapped_n, use a hash function and public entropy to generate m bin members from the range [mapped_n - bin_radius, mapped_n + bin_radius].
  9. In the bin that contains the real spend, randomly select a bin member m'. Define bin_member_rotator = real_spend_index - m' mod 2*bin_radius + 1.
  10. Redefine all m points in all bins: m = [(m - [mapped_real_spend_bin_center - bin_radius]) + bin_member_rotator mod 2*bin_radius + 1] + [mapped_real_spend_bin_center - bin_radius]. Note that m' will now equal real_spend_index.
  11. Return: hash function, public entropy, binning_upper_bound, bin_rotator, and bin_member_rotator. In practice, only bin_rotator and bin_member_rotator need to be unique between transaction inputs.

Binning strategy

For a given tx, reference all its inputs' ring members with the following strategy inspired by How to Squeeze a Crowd.

Bin configuration details

Each transaction has:

Each input has:

Instead of public entropy, we will use a pseudo-random seed computed from parts of the transaction.

Bins

Define the number of bins for each input.

Given uneven_bins = RING_SIZE mod NUM_BINS, define the number of bin members in each bin.

if (index(bin, bins) + 1 > NUM_BINS - uneven_bins)
    num_bin_members = ceil(RING_SIZE/NUM_BINS);
else
    num_bin_members = floor(RING_SIZE/NUM_BINS);

Rationale/Discussion

Binning algorithm: tx construction

Define the bin configuration details and obtain the list of ring members for each input.

Constants and inputs

struct binning_config //[[[TODO: define these; consider using constructor to validate config settings]]]
{
    size_t BINNING_UPPER_BOUND_SELECTION_WIDTH;
    size_t BIN_RADIUS;
    size_t RING_SIZE;
    size_t NUM_BINS;
    ledger_distribution_config LEDGER_DIST_CONFIG;

    size_t max_index;   // max on-chain output index when making tx, assumed to be in 'spendable' range
    size_t min_index;   // min on-chain output index that can be used as a ring member
};

/// input variables
binning_config config;  // configuration for the binning algorithm
vector<size_t> spend_output_indices;    // indices of outputs to be spent

assert(max_index >= min_index);
assert(spend_output_indices.size() > 0);

/// leave early if there are not enough outputs on-chain to construct a ring
assert(height_from_output_index(max_index) - height_from_output_index(min_index) >= BINNING_UPPER_BOUND_SELECTION_WIDTH);

size_t min_binning_upper_bound_block = height_from_output_index(max_index) - BINNING_UPPER_BOUND_SELECTION_WIDTH;
size_t min_binning_upper_bound = get_last_output_index_of_block(min_binning_upper_bound_block);

assert(min_binning_upper_bound >= min_index);
assert(min_binning_upper_bound - min_index + 1 >= (2 x BIN_RADIUS + 1));

Rationale/Discussion

Ring seed

Compute a pseudo-random number for generating all the bins and bin members for the transaction's inputs. We use a pseudo-random number in place of public entropy.

// ring entropy
u128 ring_seed = H("ring_seed", tx.key_images, tx.pseudo_output_commitments);

Rationale/Discussion

Binning upper bound

Select the binning upper bound, which is the maximum index that can be referenced by a bin. The same upper bound will be used for all inputs.

size_t bound_selection_max;
size_t bound_selection_min;

/// block where highest spendable output can be found
size_t max_block_index = height_from_output_index(max_index);
bound_selection_max = max_block_index;

/// find highest real-spend
size_t max_spend_index{0};

for (const auto spend_output_index : spend_output_indices)
{
    assert(spend_output_index <= max_index);
    assert(spend_output_index >= min_index);

    if (spend_output_index > max_spend_index)
        max_spend_index = spend_output_index;
}

// block where highest real-spend can be found
size_t max_spend_block = height_from_output_index(max_spend_index);
assert(max_spend_block <= max_block_index);

/// binning upper bound must be >= all real-spends
bound_selection_min = max_block_index - BINNING_UPPER_BOUND_SELECTION_WIDTH;

if (bound_selection_min < max_spend_block)
    bound_selection_min = max_spend_block;

// rand_from_range<T>(): select integral of type T randomly from a range [a, b]
size_t binning_upper_bound_block = rand_from_range<size_t>(bound_selection_min, bound_selection_max);

/// binning upper bound is last output in the 'binning upper bound block'
size_t binning_upper_bound = get_last_output_index_of_block(binning_upper_bound_block);

/// set fee
u64 fee = get_fee_from_height(height_from_output_index(binning_upper_bound), priority);

return: binning_upper_bound, fee

Rationale/Discussion

Selecting bins

Deterministically select the bins for input input_index.

/// set input seed
u128 input_seed = H("input_seed", ring_seed, input_index);

/// prepare bin centers
vector<u64> bin_centers_flattened;
assert(NUM_BINS);
bin_centers_flattened.resize(NUM_BINS);

for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
    // rand_from_seed<T>(seed): pseudo-randomly generate integral type T using input 'seed' to seed the generator
    // note: this must be uniformly distributed
    // - simple solution: return seed mod T:max
    //  - requires: either seed_type:max mod T:max == 0, OR seed_type:max >>> T:max
    //  - and must assume input seed is uniformly distributed
    bin_centers_flattened[bin_index] = rand_from_seed<u64>(H("bin_centers", input_seed, bin_index));

/// set bin_rotator

// 1. randomly select the real bin's center from around the output
size_t real_bin_max = spend_output_indices[input_index] + BIN_RADIUS;
size_t real_bin_min = spend_output_indices[input_index] - BIN_RADIUS;

// snap bin bounds to allowed range (with adjustments in case of integer overflow)
if (real_bin_max > binning_upper_bound || real_bin_max < spend_output_indices[input_index])
    real_bin_max = binning_upper_bound;

if (real_bin_min < min_index || real_bin_min > spend_output_indices[input_index])
    real_bin_min = min_index;

size_t real_bin_center = rand_from_range<size_t>(real_bin_min, real_bin_max);

// 2. randomly select a bin to be the 'real one'
size_t real_bin_index = rand_from_range<size_t>(0, bin_centers_flattened.size() - 1);

// 3.map the real bin center into the uniform distribution
// map_index_to_ledger_probability_dist(ledger-wide distribution config, 'index' normalized, 'max-index' of binning normalized)
// returns: (probability a randomly generated number in ledger-wide selection distribution over range [0, 'max-index'] is <= than 'index') x max(u64)
// [[[TODO: implementation (may need to take into account block:output relationship, e.g. density issue)]]]
u64 real_bin_center_flattened = map_index_to_ledger_probability_dist(LEDGER_DIST_CONFIG, real_bin_center - min_index, binning_upper_bound - min_index);

// 3. map the selected bin onto the real spend's bin center via 'bin_rotator'

// mod_subtract(a, b, c): a - b mod c
u64 bin_rotator = mod_subtract(real_bin_center_flattened, bin_centers_flattened[real_bin_index], max(u64));

/// rotate all the bins

// mod_add(a, b, c): a + b mod c
for (auto &bin_center : bin_centers_flattened)
    bin_center = mod_add(bin_center, bin_rotator, max(u64));

/// convert bin centers to real index space
vector<size_t> bin_centers;
bin_centers.resize(NUM_BINS);

for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
{
    // map_ledger_probability_dist_to_index(ledger-wide distribution config, 'probability', 'max-index' of binning normalized)
    // returns: index in range [0, 'max-index'] where random selection from the ledger-wide distribution on that range will have 'probability' probability of being <= the return value
    // [[[TODO: implementation]]]
    bin_centers[bin_index] = map_ledger_probability_dist_to_index(LEDGER_DIST_CONFIG, static_cast<double>(bin_centers_flattened[bin_index])/max(u64), binning_upper_bound - min_index) + min_index;

    // snap bin centers into the available range for bin members
    if (bin_centers[bin_index] > binning_upper_bound - BIN_RADIUS)
        bin_centers[bin_index] = binning_upper_bound - BIN_RADIUS;

    if (bin_centers[bin_index] < min_index + BIN_RADIUS)
        bin_centers[bin_index] = min_index + BIN_RADIUS;

    assert(bin_centers[bin_index] <= binning_upper_bound - BIN_RADIUS);
    assert(bin_centers[bin_index] >= min_index + BIN_RADIUS);
}

/// sort the bin centers and update real bin index accordingly

size_t real_bin_center = bin_centers[real_bin_index];
bin_centers.sort();

// if there are duplicates of the real bin's center, then randomly select which bin will contain the spent output
size_t min_candidate_index{NUM_BINS};
size_t max_candidate_index;

for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
{
    if (bin_centers[bin_index] == real_bin_center)
    {
        if (min_candidate_index == NUM_BINS)
            min_candidate_index = bin_index;

        max_candidate_index = bin_index;
    }
}

real_bin_index = rand_from_range<size_t>(min_candidate_index, max_candidate_index);

return: input_seed, bin_centers, bin_rotator, real_bin_index

Rationale/Discussion

Selecting bin members

Deterministically select the bin members for input input_index.

/// select bin members

vector<vector<size_t>> bin_members_per_bin;
bin_members_per_bin.resize(NUM_BINS);

for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
{
    // get_num_bin_members(which bin, number of bins, number of ring members) - defined by secion 'Bins'
    size_t num_bin_members = get_num_bin_members(bin_index, NUM_BINS, RING_SIZE);
    assert(num_bin_members);
    assert(num_bin_members <= 2 x BIN_RADIUS + 1);
    bin_members_per_bin[bin_index].resize(num_bin_members);

    size_t bin_min_index = bin_centers[bin_index] - BIN_RADIUS;

    // deterministically generate bin members in the range [bin_min_index, bin_max_index]
    for (size_t bin_member_index{0}; bin_member_index < num_bin_members; bin_member_index++)
    {
        bool was_duplicate;
        size_t duplicate_nonce{0};

        // prevent duplicates within each bin
        do
        {
            was_duplicate = false;

            // mod_large(a, c): a mod c, where a >> c
            bin_members_per_bin[bin_index][bin_member_index] = mod_large(rand_from_seed<u128>(H("bin_members", input_seed, bin_index, bin_member_index, duplicate_nonce)), 2 x BIN_RADIUS + 1) + bin_min_index;

            for (size_t i{0}; i < bin_member_index; i++)
            {
                if (bin_members_per_bin[bin_index][i] == bin_members_per_bin[bin_index][bin_member_index])
                {
                    was_duplicate = true;
                    ++duplicate_nonce;

                    break;
                }
            }
        } while (was_duplicate);
    }
}

/// in real bin, randomly select a bin member to be the real one
size_t real_bin_member_index = rand_from_range<size_t>(0, bin_members_per_bin[real_bin_index].size() - 1);

/// define the bin member rotator
size_t bin_member_rotator;
size_t real_bin_min_index = bin_centers[real_bin_index] - BIN_RADIUS;

bin_member_rotator = mod_subtract(spend_output_indices[input_index] - real_bin_min_index, bin_members_per_bin[real_bin_index][real_bin_member_index] - real_bin_min_index, 2 x BIN_RADIUS + 1);

/// rotate all bin members and sort each bin
for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
{
    size_t real_bin_min_index = bin_centers[bin_index] - BIN_RADIUS;

    for (auto &bin_member : bin_members_per_bin[bin_index])
        bin_member = mod_add(bin_member - real_bin_min_index, bin_member_rotator, 2 x BIN_RADIUS + 1) + real_bin_min_index;

    bin_members_per_bin[bin_index].sort();
}

/// get real bin member index post-sorting

// note: there should be no duplicate bin members
for (size_t bin_member_index{0}; bin_member_index < bin_members_per_bin[real_bin_index].size(); bin_member_index++)
{
    if (bin_members_per_bin[real_bin_index][bin_member_index] == spend_output_indices[input_index])
    {
        real_bin_member_index = bin_member_index;

        break;
    }
}

return: bin_members_per_bin, bin_member_rotator, real_bin_member_index

Rationale/Discussion

Full ring member set

/// concatenate the bins together to get the full ring-member set; also get the real-spend's index in the ring
vector<size_t> all_bin_members;
all_bin_members.reserve(RING_SIZE);
size_t real_bin_member_index_in_ring{0};
bool passed_real;

for (const auto &bin_members : bin_members_per_bin)
{
    if (bin_members == bin_members_per_bin[real_bin_index])
    {
        real_bin_member_index_in_ring += real_bin_member_index;

        passed_real = true;
    }
    else if (!passed_real)
        real_bin_member_index_in_ring += bin_members.size();

    for (const auto bin_member: bin_members)
        all_bin_members.emplace_back(bin_member);
}

return: all_bin_members, real_bin_member_index_in_ring

Binning algorithm: tx validation

Recover the ring members of each input in a transaction tx from the bin configuration details.

/// inputs
Tx tx;
binning_config config;

/// recover ring members
u128 ring_seed = H("ring_seed", tx.key_images, tx.pseudo_output_commitments);
vector<vector<size_t>> all_ring_members_per_input;]

assert(NUM_BINS);
assert(tx.binning_upper_bound >= min_index + 2 x BIN_RADIUS + 1);

for (size_t input_index{0}; input_index < tx.inputs.size(); input_index++)
{
    u128 input_seed = H("input_seed", ring_seed, input_index);

    /// generate bin centers and rotate them
    vector<u64> bin_centers_flattened;
    bin_centers_flattened.resize(NUM_BINS);

    for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
        bin_centers_flattened[bin_index] = rand_from_seed<u64>(H("bin_centers", input_seed, bin_index));

    for (auto &bin_center : bin_centers_flattened)
        bin_center = mod_add(bin_center, tx.inputs[input_index].bin_rotator, max(u64));

    /// convert bin centers to real index space
    vector<size_t> bin_centers;
    bin_centers.resize(NUM_BINS);

    for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
    {
        // [[[TODO: implementation]]]
        bin_centers[bin_index] = map_ledger_probability_dist_to_index(LEDGER_DIST_CONFIG, static_cast<double>(bin_centers_flattened[bin_index])/max(u64), tx.binning_upper_bound - min_index) + min_index;

        if (bin_centers[bin_index] > tx.binning_upper_bound - BIN_RADIUS)
            bin_centers[bin_index] = tx.binning_upper_bound - BIN_RADIUS;

        if (bin_centers[bin_index] < min_index + BIN_RADIUS)
            bin_centers[bin_index] = min_index + BIN_RADIUS;

        assert(bin_centers[bin_index] <= tx.binning_upper_bound - BIN_RADIUS);
        assert(bin_centers[bin_index] >= min_index + BIN_RADIUS);
    }

    bin_centers.sort();

    /// generate bin members
    vector<vector<size_t>> bin_members_per_bin;
    bin_members_per_bin.resize(NUM_BINS);

    for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
    {
        size_t num_bin_members = get_num_bin_members(bin_index, NUM_BINS, RING_SIZE);
        assert(num_bin_members);
        bin_members_per_bin[bin_index].resize(num_bin_members);

        size_t bin_min_index = bin_centers[bin_index] - BIN_RADIUS;

        // deterministically generate bin members in the range [bin_min_index, bin_max_index]
        for (size_t bin_member_index{0}; bin_member_index < bin_members_per_bin[bin_index].size(); bin_member_index++)
        {
            bool was_duplicate;
            size_t duplicate_nonce{0};

            // prevent duplicates within each bin
            do
            {
                was_duplicate = false;

                bin_members_per_bin[bin_index][bin_member_index] = mod_large(rand_from_seed<u128>(H("bin_members", input_seed, bin_index, bin_member_index, duplicate_nonce)), 2 x BIN_RADIUS + 1) + bin_min_index;

                for (size_t i{0}; i < bin_member_index; i++)
                {
                    if (bin_members_per_bin[bin_index][i] == bin_members_per_bin[bin_index][bin_member_index])
                    {
                        was_duplicate = true;
                        ++duplicate_nonce;

                        break;
                    }
                }
            } while (was_duplicate);
        }
    }

    /// rotate all bin members
    assert(tx.inputs[input_index].bin_member_rotator < 2 x BIN_RADIUS + 1);

    for (size_t bin_index{0}; bin_index < NUM_BINS; bin_index++)
    {
        size_t bin_min_index = bin_centers[bin_index] - BIN_RADIUS;

        for (auto &bin_member : bin_members_per_bin[bin_index])
            bin_member = mod_add(bin_member - bin_min_index, tx.inputs[input_index].bin_member_rotator, 2 x BIN_RADIUS + 1) + bin_min_index;

        bin_members_per_bin[bin_index].sort();
    }

    /// concatenate bins for full set of ring members
    all_ring_members_per_input[input_index].reserve(RING_SIZE);

    for (const auto &bin_members : bin_members_per_bin)
        for (const auto bin_member: bin_members)
            all_ring_members_per_input[input_index].emplace_back(bin_member);
}

return: all_ring_members_per_input

Rationale/Discussion

Modifications for small ring sizes

This algorithm can be adjusted so all bins only have one member each, which can applied as an optimization/upgrade to Monero's current transaction protocol. Doing so would reduce input reference bytes from (num_inputs x ring_size x varint) to (varint + num_inputs x (u64 + varint)).

Tx changes

Modify the transaction input structure and the form of the message signed by transaction inputs.

m_p = Hash(version, unlock_time, binning_upper_bound, {txin_i}_i, {txout_i}_i, extra)

Tx validation

When you encounter a tx to validate, recover the ring members for each input from the bin configuration details defined in this proposal.

Blockchain and tx hashes

  1. A transaction hash includes all tx data.
  2. Output references (e.g. all binning details) are stored in the blockchain as part of tx structs. Since output references and the outputs themselves are part of tx hashes, the blockchain can only be re-validated with the correct output references for each tx.

Rationale

Why not use the binning strategy from this paper?

Backward compatibility

This proposal changes the structure of tx and tx validation rules, so it requires a hard fork. It is well-suited to being implemented in the same hard fork that rolls out Triptych (or a similar next-gen tx protocol with large ring sizes), but is also compatible with Monero's current transaction protocol.

License

MIT license

References

vtnerd commented 3 years ago

@UkoeHB

Not sure why I need to repeat myself. The prime stuff is irrelevant here, because I am not use polynomials. The bin_rotator is C from section 1.A. Section 1.A further only specifies that the hash function be 'keyed'. Sampling k randomly is only mentioned there as an example. All that matters is that each key be unique between different RSS instances, and determined by the tx author.

The polynomial P is a tuple of constants, and this is the order-0 case. The equations listed in section 1.A are mentioned to be "incomplete", and the authors may have done a "look how to simple it is" while pushing the complexity of uniform distributions to the latter sections and proofs (the proofs make use of the prime field). ... I don't see a security proof for the equations are you using (mod max(u64) followed by mod num_outputs doesn't have uniform distribution for instance).

Even if the adversary knows the key in advance of a tx being constructed, it can't be used to provide any information about the real spend (assuming they can't choose which key the tx author uses, and can't meaningfully choose the chain's composition after learning the key).

I'm possibly being overly conservative here - the key_images and (especially) pseudo_outs should have enough bits of unpredictability to match the requirements from the proofs. But injecting entropy via k leaves little doubt when auditing that portion of the code.

I think we're stuck either choosing tx chaining with larger tx sizes OR smaller compact txes without tx chaining.

Why do you think having all-floating-outputs solves the problems with floating outputs in this proposal? The problems you have pointed out are high-fidelity heuristics that cannot defended against (i.e. rapid appearance of a tx in the mempool after an output it spends appears, presence of a floating output in last 10 blocks, floating output outside decoy-selection-range).

This proposal selects pubkeys from two different processes then merges them into one for use in a single ring-signature. You'll need some good justification for this as all prior work (that I am aware of) is on uniform exponential selection to match the real spend patterns. ... There is a known bias towards newer pubkeys, so having two distinct sets means the spend is more likely to be in the "floating index" stage. Having 1-4 fixed number of floating indexes is arbitrary compared to the uniformity of the exponential distribution over all spendable blocks that we use now.

The best (partial) solution I can muster is to select num_floating_indexes based on expected/average number of bins that should be in blocks 1-10 given a specific bin_size. So num_floating_indexes will no longer be arbitrary and hopefully less likely to leak statistical information, but it still leaves the unexplored funkiness of having two selection processes for decoys.

more entropy from the first stage should be extracted

What?

log(RING_SIZE) or log2(RING_SIZE) provides too few bins.

There's still disk access time and bandwidth from memory -> CPU registers. There's always some cost to adding more bytes of stuff. This may be less than the penalty of larger sizes from the signature itself though. I mentioned solely to indicate that there are limitations on how large the bins can be.

Huh? I am recommending a maximally compact design. This proposal has no impact on or opinion about how many total decoys are selected for rings.

Then why list a formula for specifying how many bins there should be?

Alternative The alternative to floating offsets is to define a new input type with only 1 ring member whose on-chain reference (i.e. index) is not signed by tx authors (as discussed earlier in this thread).

This is identical in concept to the floating indexes concept ?

@SamsungGalaxyPlayer

I need to think more about the other two components of this proposal. I think the terrible UX of the 10 block locktime is significant and should be addressed (even with some reasonable tradeoffs) if possible. I care far less about accounting for the atomic swaps use-case.

There's plenty of work, testing, and auditing needed just to get tx-chaining implemented. Although, once implemented the RSS/hash decoy selection algorithm may never get merged because having two different decoy selection algorithms is suboptimal.

UkoeHB commented 3 years ago

The polynomial p is a tuple of constants, and this is the order-0 case.

Umm.. the order-0 case of a polynomial is a single constant. The whole paper boils down to proving the relation f_k(j) + P(j) = I_j mod l is legit. The term P(j) mod l reduces to a constant in the range 0 <= C < l if P(x) is a 0-order polynomial. In other words, the prime field used to construct P(x) is irrelevant if you can derive C = I_j - f_k(j) mod l directly.

The trivial case is literally so trivial the authors had full right to give it just one sentence.

I don't see a security proof for the equations are you using (mod max(u64) followed by mod num_outputs doesn't have uniform distribution for instance).

The modular operations in this proposal are all mod l like in the paper. Bin loci are selected from the transform-space (i.e. inverse transform sampling) of the gamma distribution (mod max(u64)), and bin members are selected from 'within a bin' (mod bin_size).

Then why list a formula for specifying how many bins there should be?

?????

The amount of data stored in transactions in this proposal is O(1). You could have 3 total decoys, or 3 million total decoys.

Do you have some fundamental misunderstanding about this proposal lurking under the surface?

This is identical in concept to the floating indexes concept ?

Huh? We already discussed this earlier in the thread. A 1-ring-member input is literally an input that only references the output being spent.

vtnerd commented 3 years ago

The polynomial p is a tuple of constants, and this is the order-0 case.

Umm.. the order-0 case of a polynomial is a single constant.

Yes, the P tuple contains 1+ constants. The sarcasm was unnecessary here.

The whole paper boils down to proving the relation f_k(j) + P(j) = I_j mod l is legit. The term P(j) mod l reduces to a constant in the range 0 <= C < l if P(x) is a 0-order polynomial. In other words, the prime field used to construct P(x) is irrelevant if you can derive C = I_j - f_k(j) mod l directly.

The trivial case is literally so trivial the authors had full right to give it just one sentence.

The paper shows the first relationship you describe then also attempts a security proof. It is the latter that I was concerned about in these responses. x + y mod l has uniform distribution only when l meets certain properties, otherwise some outputs from that expression are more likely than others. The difference is admittedly trivial though.

Do you know why a prime field is necessary for the 2+ case then?

I don't see a security proof for the equations are you using (mod max(u64) followed by mod num_outputs doesn't have uniform distribution for instance).

The modular operations in this proposal are all mod l like in the paper. Bin loci are selected from the transform-space (i.e. inverse transform sampling) of the gamma distribution (mod max(u64)), and bin members are selected from 'within a bin' (mod bin_size).

Where does BIN_RADIUS fit into all of this?

There's still disk access time and bandwidth from memory -> CPU registers. There's always some cost to adding more bytes of stuff. This may be less than the penalty of larger sizes from the signature itself though. I mentioned solely to indicate that there are limitations on how large the bins can be.

Huh? I am recommending a maximally compact design. This proposal has no impact on or opinion about how many total decoys are selected for rings.

Then why list a formula for specifying how many bins there should be?

?????

The amount of data stored in transactions in this proposal is O(1). You could have 3 total decoys, or 3 million total decoys.

Do you have some fundamental misunderstanding about this proposal lurking under the surface?

I provided more context. This discussion devolved due to terse responses.

I was specifying how I would determine bin_size and num_bins, regardless of how the decoys were encoded (as its not guaranteed to be implemented, tx-chaining itself is a big enough feature in a fork). In the RSS O(1) scheme, that would've been bin_size == 1; the utility of the bins seemed low with this scheme. You and Justin have persuaded me slightly otherwise - we'd probably have to take real chain-analysis into account though.

I'm still against the sqrt or log approaches, especially with RSS (there's no space savings), as it seems the bias should be towards exponentially selected decoys.

Huh? We already discussed this earlier in the thread. A 1-ring-member input is literally an input that only references the output being spent.

My apologies for responding poorly - it still has an obvious privacy leak, so its not really a viable alternative.

ArticMine commented 3 years ago

I have a question. How does this proposal impact transaction sizes? In particular ring 11 and say ring 17 (CLSAG) and say ring 64 and ring 128 (Trtptych)

UkoeHB commented 3 years ago

x + y mod l has uniform distribution only when l meets certain properties, otherwise some outputs from that expression are more likely than others.

I don't think this is quite right, and it is pertinent here. Whether or not x + y mod l is uniformly distributed depends on A) how x and y are generated, B) the relation between l and those generation methods. For example, if x is randomly selected from 0 <= x < l/2, and y from 0 <= y <= l/3, this would clearly not produce a random distribution in x + y mod l. But, if both x and y are selected randomly from 0 <= n < 2*l, then the result will be uniformly distributed.

Importantly, if ns generation space is >> l, then even if n is not uniformly distributed in its own selection space, n mod l will be uniformly distributed 'in practice' (i.e. probabilistically). This behavior is used in the paper for reducing polynomials into the index space, because most polynomials are not uniformly distributed. I assume the use of a 'prime' prevents subgroup issues when solving the polynomial for a given input.

EDIT: I just remembered the proposal uses this behavior too, when going from [hash output] -> [selection space]. A hash output is a multiple of 8 bytes, so it will be uniformly distributed in the bin loci space (u64), and the hash space is >> bin width (on the order of 100-10000, compared to 2^128-2^256) so bin members will be effectively uniformly distributed. I'm guessing this is what you have been talking about. It would help if you quote lines from the proposal directly.

If you look at Figure 1 in the paper, steps 5-7 simplify to the stuff in section 1.A when P() is 0-order, and step 1 (defining the prime) becomes irrelevant.

Where does BIN_RADIUS fit into all of this?

BIN_RADIUS is used to set the default 'bin width', which is the number of of outputs on-chain to select a bin's members from (i.e. the decoys for a ring sig). If BIN_RADIUS = 50, then each bin will have 101 outputs to select bin members from. The reason I don't use BIN_WIDTH directly is because most operations related to bins are with respect to bin loci, rather than e.g. the lower bounds.

I was specifying how I would determine bin_size and num_bins, regardless of how the decoys were encoded (as its not guaranteed to be implemented, tx-chaining itself is a big enough feature in a fork). In the RSS O(1) scheme, that would've been bin_size == 1; the utility of the bins seemed low with this scheme. You and Justin have persuaded me slightly otherwise - we'd probably have to take real chain-analysis into account though.

I see, thank you for clearing this up.

I'm still against the sqrt or log approaches, especially with RSS (there's no space savings), as it seems the bias should be towards exponentially selected decoys.

The reason I like sqrt is because it evenly distributes 'decoy selection' between the two timing attack vectors (spend-time selection, local-vicinity selection). Since we can't know in advance which vector is more prevalent or important, allocating selection to them equally is a solid compromise (in my view).

My apologies for responding poorly - it still has an obvious privacy leak, so its not really a viable alternative.

I think it is the most viable solution, even if the level of viability is too low for it to be accepted. Since it is most viable, it should at least be mentioned for context.

@ArticMine This proposal would reduce tx sizes compared to our current protocol.

The proposal is O(1) with respect to number of decoys.

Gingeropolous commented 3 years ago

if you imagine the extreme idea of a 128 member ring, where the first 117 members are chosen from the tip of the chain (or the txpool directly), then this set of 117 decoys can stand to lose some while maintaining the obfuscation.

The problem is some decoys will be permanently removed from the chain due to a double spend, so the transactions that reference them will be permanently invalid.

right.... I am imagining that there is some cryptomagic that allows you to still have a valid ring signature with some ring members missing. Sorta like how a multisig is possible with an incomplete set.

But that doesn't exist.... ?

luckysori commented 3 years ago

right.... I am imagining that there is some cryptomagic that allows you to still have a valid ring signature with some ring members missing. Sorta like how a multisig is possible with an incomplete set.

But that doesn't exist.... ?

I think in your scenario you just wouldn't get to the point of verifying the ring signature, because the transaction would reference non-existent outputs in the input ring. That is surely disallowed, but even if you could get past that you would not be able to produce the original signature hash to verify against, given that some data (e.g. output commitments) would be missing or wrong.

Gingeropolous commented 3 years ago

well, on second thought, in the case of a double spend / re-org,

given that some data (e.g. output commitments) would be missing or wrong.

those data aren't missing, they are just now on the orphaned chain.

but yeah. not saying that it should be done, but there's probably a hacky way that it could be done. But for sure, this avenue of thought is sufficiently bricked over for me at least.

Gingeropolous commented 3 years ago

well it seems I can't brick up this avenue that well.

you could call this a "fray", and its kinda like ethereums uncle blocks... but yeah, in the case of a re-org, you could carry the alt-chain to maintain the data references .... but yeah, pretty ugly and probably opens some attack surfaces.

j-berman commented 3 years ago

I think allowing for 1 member rings is actually a pretty solid alternative that makes the network safer/enables a stronger degree of privacy for most users.

Today there are some honest users who rely on making transactions transparent; mining pools making payouts to pool members are one such example. In this case, honest users who benefit Monero are revealing their spent outputs and negatively affecting others on the network, who then include those outputs in their rings. Another example: a potential Thorchain integration, where all transactions that happen on Thorchain would be made public. Allowing an alternative tx (1 member rings) for these good-faith users, without polluting the global output set for other users who want privacy by default (or bloating the chain with unnecessarily large rings), seems like a reasonable use case that makes the network safer for everyone.

Basically, if you're an honest user but you're going to make your transaction public anyway, just make it transparent on the chain in a silo'd part of the chain where others can't use your known spent outputs, so you won't negatively affect other users. Plus, you have the added benefit of marginally cheaper transactions, and it saves space.

Edit: it could work by designating an output as only usable in a 1 member ring going forward. For example, a mining pool knows it's going to pay out the block reward in a new tx in the future, so in the miner tx, the output would be designated as only being usable in a 1 member ring - something along those lines. That way no one else would attempt to use that output as a decoy in their ring.

trasherdk commented 3 years ago

So, what happens when a bunch of honest users makes a shitload of 1-ringmember outputs? Wouldn't that help the dishonest observers having a smaller set of outputs in need of analyzing?

j-berman commented 3 years ago

My assumption is that the feature would be used by people who are either already revealing their spent outputs anyway such as mining pools (this group is adding to the set of outputs in a way that is harmful today -- these additional outputs added to the global set of outputs are not beneficial in any way whatsoever), or would not otherwise add to the set of outputs at all.

I wasn't thinking that it would take away from people who are adding to the output set in a beneficial way (i.e. I didn't think this would alter normal usage of Monero, where the average user doesn't reveal their spent outputs to the world).

Though if there is an incentive of significantly lower fees, it might attract people to want to use it instead of normal ring tx's, and therefore potentially take away from the output set. Perhaps could require a fee on par with normal tx's, and so the only incentive to using it is either altruistic (i.e. can't do harm using it, but it's beneficial for other users), or it allows you to do something you wouldn't have otherwise done.

j-berman commented 3 years ago

Realized the above is basically one of the recommendations of An Empirical Analysis of Traceability in the Monero Blockchain (pg. 16)

Avoid including publicly deanonymized transaction outputs as mixins

We have empirically shown the harmful effect of publicly deanonymized (i.e. 0-mixin) transactions on the privacy of other users. Since non-privacy-conscious users may make 0-mixin transactions to reduce fees, Monero had instituted a 2-mixin minimum, and recently increased this to 4. However, even 4+mixin transactions may be publicly deanonymized; in particular, as discussed in Section 5.1, mining pools have a legitimate interest in forgoing anonymity by publicly announcing their blocks and transactions for the sake of accountability. Thus, we propose that Monero develop a convention for flagging such transactions as “public,” so that other users do not include them as mixins.

trasherdk commented 3 years ago

You are also assuming honest users actually exists, and would be the only ones to utilize this, while you should assume that any user is potential adversarial, and should maximize protection against those friendly honest users :smile:

j-berman commented 3 years ago

Fair enough. Thought it through more deeply and there are reasons to think honest users may be pulled into using this feature over using normal tx's, thereby reducing the size of the output set. Here are the scenarios where that might happen:

There are probably more I'm not seeing. Thorny tradeoffs.

Hueristic commented 3 years ago

Fair enough. Thought it through more deeply and there are reasons to think honest users may be pulled into using this feature over using normal tx's, thereby reducing the size of the output set. Here are the scenarios where that might happen:

* If the unlock time is done away with for 1-member rings, users who value being able to make quicker payments over privacy may now opt to use 1-member rings over normal tx's. Exchanges probably the largest source of tx's that fit the bill here.

* Users may atomic swap Monero for Bitcoin thanks to this feature instead of going to Haveno and exchanging for Bitcoin using their protocol (where spent output data wouldn't be published I believe).

* Users who value performance over privacy at the point of tx construction may opt to construct the quicker-to-construct and transmit 1-member ring tx's.

There are probably more I'm not seeing. Thorny tradeoffs.

Not at all, if you don't want to be part of the anonymity set then don't use the coin.

You smell like a plant with an agenda to weaken the coin.

j-berman commented 3 years ago

@Hueristic

My initial angle was to strengthen the anonymity set, which is currently actively being weakened by honest users, which is evident in that mining pool page I linked.

My last comment that you're responding to was fully fleshing out and acknowledging the downsides. If anything that would be the comment you should agree with most from your perspective.

In any case, I'm tapping out of this conversation, since I agree that those downsides, which I explained fully, are significant enough I don't feel comfortable pushing forward 1-member rings.

SamsungGalaxyPlayer commented 3 years ago

In theory it would be fine to grab the efficiency gains of the 1-output rings and the flagging that could be shown to wallets, but this isn't realistic or enforceable. Thus, the status quo of the minimum ringsizes seems to be the best option in practice. We already know marking outputs as spent on the wallet side is possible but terrible in practice. Most mining pools now share less information to the public anyway, and Monero network activity has far surpassed these mining pool outputs anyway so it's no longer a significant problem.

I share concerns about the visible outputs through something like Thorchain, and the desire to flag these outputs as a special kind so they can be avoided (along with whatever else should be flagged). From a consensus design decision however, it's best to limit on-chain fuckery as much as possible, or else it's like Monero's past where people widely used 1-ring transactions for no good reason.

We had a similar discussion for coinbase outputs and possibly requiring coinbase-only rings (since those are already marked, no avoiding that). This was passed on mostly for complexity and not-significant-enough-of-a-harm reasons.

Anyway, I'd rather steer this discussion back to the other main topics. Whether Monero should have a public output tier should be a completely separate issue.

Gingeropolous commented 3 years ago

@UkoeHB , i would recommend changing the title back and just starting a new issue for ring binning. If you change the original post, then the responses aren't gonna make sense etc etc.

I mean, you can do what you want obvi :) but in 2 years we'll have no idea what happened here.

and its good to have documented why a particular feature / solution was sent back to the drawing board.

UkoeHB commented 3 years ago

Github comments/etc. have a history of edits you can look at. I added the date to my comment about removing tx chaining if people want to look at the old version.

UkoeHB commented 3 years ago

I think @vtnerd has mentioned it might not be good to bake a selection algorithm directly into the consensus rules. This proposal can be modified for use in that context (generate bin locations locally, generate bin members deterministically).

The disadvantages compared to a baked-in selection algorithm are:

j-berman commented 3 years ago

I think I have a bit of a clearer explanation for the subtle leak @vtnerd talked about here. I don't yet see a perfect way around it with a simple client-side binning approach I've been trying to think through either.

It's easier to see it if you assume 100 bin members. You'll have a "jar of marbles" so to speak that revolve around the center. So the bin center would be clearly deducible.

If your real output is used as a bin center, then it's fairly trivial there would be no benefit to binning. An observer could just eliminate any outputs that aren't bin centers.

If you take your real output, and try to select a new bin center using the real output, the new bin center is still statistically more likely to be closer to the real output (can qualify this claim further with some kind of proof). Therefore, the outputs that are closer to the bin center are still more likely to be real than the outputs further away.

At this point, I'm trying to reason through if it's possible to avoid this leak by fixing the bin size to 2, and going with an approach that doesn't scale to >2 bin members. But with >2 bin members, I think the above should help make it a bit clearer a leak is introduced with an approach along these lines.

Perhaps the Moser paper's approach for fixing bins may be the best way to go after all.

UkoeHB commented 3 years ago

If you take your real output, and try to select a new bin center using the real output, the new bin center is still statistically more likely to be closer to the real output (can qualify this claim further with some kind of proof).

Unless I am missing something, selecting a bin center at random from around the real spend means the real spend - center delta will be uniformly distributed (equally likely to be any value).

j-berman commented 3 years ago

Yep, nevermind I believe you are right @UkoeHB -- that was me tripping up. Fairly simple python script that should support your claim and show I was wrong:

import random
import statistics

BIN_WIDTH = 100
BIN_RADIUS = int(BIN_WIDTH / 2)
REAL_OUTPUT_INDEX = 150

NUM_SIMULATIONS = 100000
BIN_MEMBERS = 50

init_bin = range(REAL_OUTPUT_INDEX - BIN_RADIUS, REAL_OUTPUT_INDEX + BIN_RADIUS)

real_is_closer_than_bin_members = 0
real_is_further_than_bin_members = 0
deltas = []

for i in range(NUM_SIMULATIONS):
    bin_center = random.choice(init_bin)
    final_bin = range(bin_center - BIN_RADIUS, bin_center + BIN_RADIUS)

    bin_member_distances = []

    for j in range(BIN_MEMBERS):
        bin_member = random.choice(final_bin)

        # on average, expect this distance to be BIN_WIDTH / 4
        distance_from_bin_center = abs(bin_member - bin_center)
        bin_member_distances.append(distance_from_bin_center)

    avg_bin_member_distance_from_bin_center = sum(bin_member_distances) / len(bin_member_distances)
    median_bin_member_distance = statistics.median(bin_member_distances)

    # on average, expect this to be BIN_WIDTH / 4
    real_distance_from_bin_center = abs(REAL_OUTPUT_INDEX - bin_center)

    if real_distance_from_bin_center < median_bin_member_distance:
        real_is_closer_than_bin_members += 1
    elif real_distance_from_bin_center > median_bin_member_distance:
        real_is_further_than_bin_members += 1

    # my initial claim was that this would be negative with significance
    real_and_bin_member_delta = real_distance_from_bin_center - avg_bin_member_distance_from_bin_center
    deltas.append(real_and_bin_member_delta)

# but not the case
print("Delta should be close to 0 to show initial claim was wrong:", sum(deltas) / len(deltas))

# my claim was the real would tend to be closer to the bin center than other bin members, not the case with significance
print("Real is closer to bin center than other bin members:   ", real_is_closer_than_bin_members, "times")
print("Real is further than bin center than other bin members:", real_is_further_than_bin_members, "times")

EDIT: another sanity check from a different angle:

import random

BIN_WIDTH = 100
BIN_RADIUS = int(BIN_WIDTH / 2)
REAL_OUTPUT_INDEX = 150

NUM_SIMULATIONS = 1000000
BIN_MEMBERS = 20

init_bin = range(REAL_OUTPUT_INDEX - BIN_RADIUS, REAL_OUTPUT_INDEX + BIN_RADIUS)

# is the real's distance from bin center uniformly distributed?
real_output_bin_member_distance_index_counts = {}
for i in range(BIN_MEMBERS + 1):
    real_output_bin_member_distance_index_counts[i] = 0

for i in range(NUM_SIMULATIONS):
    bin_center = random.choice(init_bin)
    final_bin = range(bin_center - BIN_RADIUS, bin_center + BIN_RADIUS)

    bin_member_distances = []
    selected_bin_members = { REAL_OUTPUT_INDEX: True }
    real_distance_from_bin_center = abs(REAL_OUTPUT_INDEX - bin_center)
    bin_member_distances.append(real_distance_from_bin_center)

    for j in range(BIN_MEMBERS):
        bin_member = random.choice(final_bin)

        # no duplicates
        while bin_member in selected_bin_members:
            bin_member = random.choice(final_bin)
        selected_bin_members[bin_member] = True

        distance_from_bin_center = abs(bin_member - bin_center)
        bin_member_distances.append(distance_from_bin_center)

    bin_member_distances.sort()

    real_output_bin_member_index = bin_member_distances.index(real_distance_from_bin_center)

    # sometimes there will be duplicate distances, and index() will always choose the closer one.
    # to avoid this, check the next elem in the bin_member_distances array. if it's the same, then
    # 50% of the time, just bump the real_output_bin_member_index by 1
    if real_output_bin_member_index < len(bin_member_distances) - 1:
        if real_distance_from_bin_center == bin_member_distances[real_output_bin_member_index + 1]:
            if random.choice(range(2)) == 1:
                real_output_bin_member_index += 1

    real_output_bin_member_distance_index_counts[real_output_bin_member_index] += 1

# expect roughly equivalent counts for each index
for i in range(BIN_MEMBERS + 1):
    print("Idx:", i, " Count:", real_output_bin_member_distance_index_counts[i])

EDIT 2:

A more visual way of seeing the problem:

 . is some other output in the chain
 x is the real output
 y is the bin center
 bin radius is 2

Start with x:

..x..

Now here are all plausible bin centers:

x.y..
.xy..
..x..     <- x & y are the same
..yx.
..y.x

Knowing the indexes of x and y yields no useful information about x being real, because x can be in any position of the bin with equal likelihood.

(Edited again for clarity.)

j-berman commented 3 years ago

Question on this part:

// 1. randomly select the real bin's center from around the output
size_t real_bin_max = spend_output_indices[input_index] + BIN_RADIUS;
size_t real_bin_min = spend_output_indices[input_index] - BIN_RADIUS;

// snap bin bounds to allowed range (with adjustments in case of integer overflow)
if (real_bin_max > binning_upper_bound || real_bin_max < spend_output_indices[input_index])
    real_bin_max = binning_upper_bound;

if (real_bin_min < min_index || real_bin_min > spend_output_indices[input_index])
    real_bin_min = min_index;

size_t real_bin_center = rand_from_range<size_t>(real_bin_min, real_bin_max);

Am I following right that the bin width is likely to shrink if you're at the edge? If your real output is the max output allowed, your theoretical bin center could be between the real output and the real output - BIN_RADIUS, which would mean in most cases the upper part of the bin is cut off at the edge

UkoeHB commented 3 years ago

Am I following right that the bin width is likely to shrink if you're at the edge?

The bin center selection zone is shrunken/cropped. There isn't any other way to do it, because upper/lower bounds are just that - the boundaries of your data set, and because bin width is fixed - the bin center must be within +/- BIN_RADIUS of the real spend.

which would mean in most cases the upper part of the bin is cut off at the edge

Yep

j-berman commented 3 years ago

I think there may be an issue at the edge. Am I missing something here?

assume bin radius = 2

real output 0 can have bin center at 0, 1, 2
real output 1 can have bin center at 0, 1, 2, 3
real output 2 can have bin center at 0, 1, 2, 3, 4
real output 3 can have bin center at    1, 2, 3, 4, 5
...

Real output 0 has 0 bin center 1/3 times, real output 1 has 0 bin center 1/4 times, real output 2 has 0 bin center 1/5 times. Assuming you have roughly the same number of 0's, 1's, and 2's, then you would expect a higher % of the 0 bin centers to be real output 0.

Therefore, if you know the bin center is 0 (or in real terms, if you know the bin center is the closest possible bin center to the upper bound), your best guess for the real is output 0, next best guess is output 1, etc.

What am I missing?

UkoeHB commented 3 years ago

I don't think you are missing anything, that is correct (and unavoidable).

On the other hand, you will also have a slightly disproportionate 'piling up' of decoys bins at the boundaries. I think if the true spend distribution matches the bin selection distribution, then these two effects cancel each other out (from a high-level statistical pov; if you have special timing knowledge about an output, then binning is less effective at the boundaries of the data set).

j-berman commented 3 years ago

I think I have a way to avoid it in the wallet-side algorithm (at least for the tip of the chain), though I'm not sure it's possible to apply here: using fixed bins, similar to how the Moser paper suggests. I.e. you know a group of outputs must fall into a particular bin.

You could say outputs 0-99 in the chain = bin 0, outputs 100-199 in the chain = bin 1, etc. all the way until the back of the chain, where the final bin is likely to be smaller. Which seems fine to deal with because the chances of the final bin being used are extremely tiny versus the tip of the chain's bin.

UkoeHB commented 3 years ago

I think that can be applied here. Just define the binning upper bound, pre-define bins relative to the binning upper bound ((upper_bound - BIN_RADIUS) - (2*BIN_RADIUS + 1)*bin_selector). Then instead of defining bin centers directly, you deterministically select a bin member, then find which bin it belongs to. For the real spend's bin, you'd randomly select a bin member from its bin to map into the uniform distribution.

r4v3r23 commented 2 years ago

so transaction chaining is out? is this something that Seraphis can allow?

UkoeHB commented 2 years ago

@r4v3r23 yes, Seraphis allows transaction chaining. The current RingCT protocol could technically do tx chaining with a LOT of code work and protocol changes, but the real spends in chained tx would always be the 'newest' ring member, which is an unpleasant and perhaps not-worthwhile heuristic.

r4v3r23 commented 2 years ago

@r4v3r23 yes, Seraphis allows transaction chaining. The current RingCT protocol could technically do tx chaining with a LOT of code work and protocol changes, but the real spends in chained tx would always be the 'newest' ring member, which is an unpleasant and perhaps not-worthwhile heuristic.

would tx chaining allow for spending unconfirmed outputs and remove the 10-block confirmation lock when receiving funds?

UkoeHB commented 2 years ago

would tx chaining allow for spending unconfirmed outputs and remove the 10-block confirmation lock when receiving funds?

Tx chaining lets you make a partial tx that spends outputs that aren't in the chain. However, the 10-block lock time must remain in place. Here's what you can do (Alice and Bob are friends):

  1. Alice receives output A from Carol in block X.
  2. Alice makes a partial tx spending A, that sends output B to Bob.
  3. Alice gives her partial tx to Bob at height X + 1. The outputs in this tx aren't spendable yet (not until height X + 10).
  4. After height X + 10, Bob can complete Alice's tx and submit it. NOTE: Bob will know that Alice's tx spends output A, so Alice should only do this if she trusts Bob (or doesn't care about leaking A)!
tevador commented 2 years ago

I think TX chaining and spending of outputs younger than 10 blocks could be still done with binning if the youngest bin referenced outputs by hash instead of by index. This would increase output sizes (for example by 128 bytes for num_bin_members = 4), but would make the scheme resistant to reorgs and preserve some privacy when spending such outputs.

In the example given by @UkoeHB Alice could draw some decoys from block X, so Bob will not know which exact output is being spent.

UkoeHB commented 2 years ago

I think TX chaining and spending of outputs younger than 10 blocks could be still done with binning if the youngest bin referenced outputs by hash instead of by index.

This is basically the floating output idea this issue originally proposed. I think it is too flawed to pursue.

r4v3r23 commented 2 years ago

@tevador @UkoeHB from the latest getmonero.org Seraphis write-up:

Ignore 10-block lock time when transacting with a trusted party (i.e. allow them to make your tx's membership proofs and submit the tx to the network on your behalf).

is it possible to remove the 10-block lock time in practice without harming privacy across the board by revealing the real output in "trusted" transactions? can this at least remove the lock time on unconfirmed change since its essentially a self-spend with not other party involved?

just trying to get a feel for how this would change UX when transacting

tevador commented 2 years ago

Publicly revealing the spent output weakens all rings that have used that output as a decoy, so that would be a significant hit to the overall privacy of Monero.

r4v3r23 commented 2 years ago

right so in practice the 10-block limit stays

tevador commented 2 years ago

Have any problems been found with this deterministic ring selection algorithm? @UkoeHB's current Seraphis code seems to encode the bin centers explicitly by index rather than generating them from a seed.

There are several advantages of selecting the bins deterministically:

  1. More compact reference set encoding, which would reduce transaction sizes.
  2. Enforcing a uniform decoy selection algorithm across all wallet implementations. Currently wallets are free to implement their own algorithms, which can lead to privacy leaks.
  3. Preventing malicious rings that leak the real spend by selecting the same decoys for multiple outputs (there are thousands of such transactions in the blockchain).
  4. If the binning_upper_bound was implemented as a blockchain height, this would give us an equivalent of Bitcoin's nLockTime for free. Assuming this field would be signed by the Seraphis ownership proof, it could be used in trustless protocols such as atomic swaps to create a transaction that cannot be submitted to the network for a certain number of blocks. This could entirely replace the current broken timelock feature that itself interferes with deterministic selection.
UkoeHB commented 2 years ago

Disadvantages:

  1. implementation complexity - I predict deterministic bin loci would introduce a lot of edge cases that are difficult to reason about. As it stands, no complete algorithm has even been proposed by anyone.
  2. greatly expanded heuristic surface of the protocol - A deterministic bin loci algorithm would be riddled with heuristics, which increases ecosystem dependence on the core team by inviting more hard forks. We want the protocol to become increasingly timeless and independent, not more contextual and dependent.
  3. unit test headaches - I don't like headaches.

If the binning_upper_bound was implemented as a blockchain height, this would give us an equivalent of Bitcoin's nLockTime for free.

If the bin loci are deterministic, but a sub-range of the selection zone is unknown, then you have to brute force rings that only sit within the known range. Since selection distributions greatly favor recent blocks, it may be prohibitively expensive to find viable rings to get a lock time.

Assuming this field would be signed by the Seraphis ownership proof

It cannot be signed by ownership proofs, because that would greatly weaken tx chaining. For example, I want to make multisig txs where the decoy references are selected moments before submitting each tx (this is deferred membership proofs, which is the precursor to tx chaining), in order to make multisig txs more indistinguishable from regular txs. That timing can't be known in advance (when building the signatures). For tx chaining, if binning_upper_bound is baked into signatures, then you can't chain off an enote if it gets added after binning_upper_bound.

tevador commented 2 years ago

you have to brute force rings that only sit within the known range

No. You have to defer making the membership proof until the lock time has elapsed and all outputs in the specified range are known. This is the main point of a time lock field. Consensus would reject transactions with binning_upper_bound > current_height.

I want to make multisig txs where the decoy references are selected moments before submitting each tx

Valid issue, but not insurmountable. Assuming the multisig participants cooperate, they can estimate the required lock time when the signature will be completed.

I guess it's a matter of deciding if we need cheap time locks that are actually usable or the ability to pre-sign a transaction without locking it.

UkoeHB commented 2 years ago

No. You have to defer making the membership proof until the lock time has elapsed and all outputs in the specified range are known.

Ah yes, my mistake.

Assuming the multisig participants cooperate, they can estimate the required lock time when the signature will be completed.

If you aren't online around the right time, then it becomes a brute force problem again. If we want a cleartext min_mineable_height it would be much simpler to just add one varint to txs for that purpose. A more privacy-oriented solution would use range proofs.

tevador commented 2 years ago

If we want a cleartext min_mineable_height it would be much simpler to just add one varint to txs for that purpose

This has the problem of leaking that the tx was time-locked.

A more privacy-oriented solution would https://github.com/monero-project/research-lab/issues/78#issuecomment-1003195804

More costly to store and verify.

But I digress, this discussion would be more suitable for the time locks issue. I just wanted to point out that ring selection could be used as a proxy time lock.