I always assume that one of us is secretly a 3 letter agency, and somebody else is probably a Fortune 500 company that is still in stealth mode about cryptocurrency adoption. :- P

Anyways, what do y'all think about extra decoy outputs for the sake of artificially increasing the anonymity set?

I don't agree with 100% of the statements in that GitHub issue, but I do find the idea thought provoking

Kind of depends on ratios between transaction volume, output volume, and ring size

s/GitHub issue/Sietch writeup on GitHub

This has been brought up several times over the years

The previous context was mainly about the idea of reducing the effects of entities colluding with known outputs to reduce the effective anonymity set

<[keybase] unseddd>: sarang: agree that increasing the anonymity set is a good idea, along with removing the ability of malicious actors to collude in a way that reduces the anonymity set for all users. am advocating for not using an algorithm that is too greedy, rejecting legitimate auxilliary input(s), claiming they are malicious

You can't prevent entities from colluding

Nor can you reliably detect what outputs belong to such entities without significant external information

<[keybase] unseddd>: what i mean, is removing user control over vulnerable aspects of the protocol as much as possible, e.g. deterministic tx-building to defeat Janus attacks

FWIW the percentage of outputs that need to be controlled by colluding entities (or otherwise suspected/known to be non-signers) to destroy a ring signature is nontrivial

and keep in mind that this is very time-based

since decoy selection by default is not uniform over time

unseddd: decoy selection is not protocol enfoced

*enforced

There have been proposals to do so, but they do not play nicely with accurate spend distribution estimates

<[keybase] unseddd>: great! that should make implementing/integrating hardening changes there won't require any consensus changes / hard-forks, right?

What kind of change

Changes to non-enforced decoy selection are, by definition, not enforced =p

<[keybase] unseddd>: still don't fully understand the idea of non-uniform distribution, if spend distributions can't be analyzed on Monero

They can't directly

But some early transactions can be

and this distribution can be compared to transparent chains

They turn out to be similar

<[keybase] unseddd>: the distribution algo from stdlib also causes clang builds to fail for Monero, so replacing it with a uniform random distribution would fix two things

This is assumed to be a reasonable approximation

A uniform random selection from the chain is not suitable

<[keybase] unseddd>: maybe Monero used uniform random distribution before, and it caused issues?

because outputs are not equally likely to be spent as a function of their age on chain

Newer outputs are _much_ more likely to be spent

If the selection algorithm differs significantly from the expected spend age distribution, you can build a heuristic for the most likely signer based on this

So while moving to a simple distribution is useful for protocol-enforced decoy selection, it is terrible for adversarial heuristics

If there are problems with the current distribution, it might be possible to rewrite a custom version that builds properly with other tools

(I have not run into this problem personally)

<[keybase] unseddd>: try building Monero with clang, you'll run into the issue

I want R = fxn[seed, height]

seed is any integer, height is a block height

<[keybase] unseddd>: also advocating for enforcing decoy selection, at least in some of the ways mentioned for Janus mitigation, i.e. making tx-building verifiable, even if optional

Isthmus: ?

And the output R is a set of ring members [technically, a list of output indices] that satisfy our decoy selection algorithm

Oh you mean deterministic ring selection

Yes, this method exists

but in general requires inverse transform sampling

Oooh, tell me more

<[keybase] unseddd>: Isthmus: you want fxn? ;p

Oh, having to generate sets of R's to find one that includes your output?

fxn, yes plz

For simple distributions it's efficient

(I have simple code that shows examples of this)

For more complex distributions, not so much

<[keybase] unseddd>: _gib Isthmus fxn_

Because the verifier needs to use the seed data to reconstruct the output set

The paper shows it for uniform sampling and the old triangular sampling

O rly?

yes

but our distribution is not nearly so straightforward as lines

It relies on keyed hash functions

Here's a weird, maybe heretical question

How closely does our decoy selection algorithm need to match the real spend time distribution

If we ask "what is the ideal decoy selection algorithm" the trivial answer is "our best approximation of the spend time"

<[keybase] unseddd>: not familiar, will check it out. perhaps uniform-random is naive, as am still familiarizing myself with Monero attach surface / design choices. however, continuing a heuristic based only on information exposed by the earliest txes seems a large technical debt

But is this the *only* possible approach that would provide adequate cover?

<[keybase] unseddd>: *attack

Miller et al. look at this difference

Well, it's important to note that there is (ideally) no way to check the validity of age-based guesses

So on their own, they provide no particular provable data

and it's not at all clear what a quantifiable definition of "plausible deniability" for a ring signature looks like in practice

unseddd: how does the selection algorithm imply technical debt?

We have no particular reason to think that Monero spend age distributions differ from the combination of known Monero spend data and Bitcoin spend data, which show the same trends

(and we can't check this anyway)

<[keybase] unseddd>: unfortunately don't think practical knowledge of plausible deniability will be know until it's used in a court case or similar

and FWIW the distribution is not that complicated

it just doesn't play as nicely with sampling that would make deterministic selection reasonable

<[keybase] unseddd>: since the effect of uniform random selection on deniable plausibility is unknown, and the effects of non-deterministic selection is known (Janus), would favor mitigating the latter given more research on the former

I don't really think much about "plausible deniability," since it's an artificial construct that will vary by every jurisdiction and decade. My only interest is in statistical obfuscation.

Janus is about subaddress faking, not decoy selection

And uniform selection is a terrible option

<[keybase] unseddd>: basically, if we can measure the effects of uniform random distribution on selection, and it is found to not break anything, lets use uniform random

Under all but the simplest risk assumptions

Uniform selection doesn't break anything except statistical expectations of spend ages

<[keybase] unseddd>: why terrible?

Because it basically gives away the likely signer

And an adversary can use that to weight the likely true tx graph

<[keybase] unseddd>: statistics that cannot be verified, or even measured, on the current chain?

No but they can be used as part of broader graph techniques

And they're a really good heuristic

<[keybase] unseddd>: giving away the likely signer is disasterous, if that really is the effect, definitely no uniform random

<[keybase] unseddd>: good heuristic based only on unspent early txes right? am misunderstanding something? create a turnstyle-like protocol, and remove the ability to perform those heuristics. problem solved, no?

That's not really the point

The point is that we know how users tend to spend outputs based on other chains and early Monero data

<[keybase] unseddd>: thought removing heuristics was the point, where have gone wrong?

Selecting decoys according to expected spend patterns is the mitigation to this heuristic

That's exactly why we use the algorithm we do

And continue to iterate on it

<[keybase] unseddd>: right, just trying to think of a more permanent solution, so you do not have the technical debt going forward

How is it technical debt

I don't really follow

<[keybase] unseddd>: having to continually update a selection algo based on best-guesses and heuristics sounds like technical debt to me

yeah, the output selection doesn't create technical debt afaict.

its more like a technical burden

a lot of aspects of security are continually moving targets

<[keybase] unseddd>: burden == debt ...

It's not ideal, but it is a consequence of ring signatures

well yeah, semantics

you can't really pick a single algorithm and carve it into stone. it'd be like the maginot line, someone will walk around it.

simple answer is ringsize a bajillion

The goal is transaction uniformity, which depends in part on usage patterns

We need to adapt to them as best we can

This is part of it

<[keybase] unseddd>: hyc: get that security, and the fight for privacy is ever-moving, just tring to think of things that will make Monero have to move less in this particular direction. totally understand that i do not comprehend the full picture yet

those are good thoughts to have. less human hands the better

There are techniques like binning that can apply better at larger ring size

These have the added advantage of reducing communication complexity

<[keybase] unseddd>: sarang: are those ring sizes practical?

That's the current goal

We're getting there

<[keybase] unseddd>: ok awesome! then will direct my attention there :)

I assure you it is not an easy problem to solve

nonsense! just put it on a blockchain!

Brilliant

<[keybase] unseddd>: no, wouldn't think it is, but at willing to throw some braincells at it

Please do

Nobody has totally solved it yet

<[keybase] unseddd>: is there a tracking issue for ongoing efforts?

the current effort is in CLSAG isn't it?

Clsag is more of a stopgap

<[keybase] unseddd>: oh, so CLSAG and it's successors would enable large enough ring sizes for binning?

Other efforts include Ommiring, Triptych, Lelantus, RCT 3, Arcturus

Clsag would not

Some are externally developed, others are in house

<[keybase] unseddd>: sarang: is there a paper(s) or description of the binning technique you mentioned?

unsedd, eprint.iacr.org/2019/186.pdf

i think thats the reference

woops

<[keybase] unseddd>: gingeropolous, sarang: many thanks :)

<[keybase] unseddd>: yeah, that paper makes it obvious that uniform distribution is terrible for input selection. sorry for wasting time suggesting it

<[keybase] unseddd>: would be interesting to re-run the POPETS18 analysis using most current chain data, see if their results still hold. still need to read the IACR paper

<[keybase] unseddd>: by re-running the analysis, only mean using the current 11-mixin with Gaussian distribution, and compare with say 11-mixin, (3,4)-bin binning strategy

<[keybase] unseddd>: the 7-mixin, 4-bin gives 4.0 min-untraceability in the POPETS18 paper, so curious to see if the 11-mixin, 4-bin strategy gets close to ideal 1/11 chance of 100% traceability