Minimizing unspent outputs in output set.

[ghost]

Did some research on outputs, found there are many old outputs that have never been included in a group signature. Can this be prioritized as part of the decoy selection algorithm? To select those outputs so that there status is more uncertain whether they have been spent or not.

https://yorha-0x.github.io/dormant-aeon/

[iamsmooth]

Reasonable idea, but maybe better as an upstream (Monero) issue. Or does Monero somehow handle it better? I guess the larger ring size would tend to naturally do this somewhat, but not entirely.

[ghost]

Monero things are slightly different with larger signature group sizes and encrypted amounts. All outputs are taken from the same signature pool. Aeon anonymity pool is essentially segregated into different classes by the output amounts. Larger outputs are less likely to be generated and transferred making them more traceable. I can see reducing the number of denominations as being somewhat effective so they share the same pool. (no need for 200,000 300,000 400,000 ... if they all use 100,000). The decoy selection algorithm looks a bit complicated I want to study before I make any conclusion about improvements to that.

[ghost]

Here is one deficiency I observe in decoy selection algorithm:

Same output spent multiple times in one transaction

These 3 inputs are all part of the same transaction and use the same output as part of their group. It would be impossible for someone to spend an output three times so 2 are proven decoys.

So that would be one basic improvement.

↪ Input: 930f78477b02b24514c4198c23f1b9955703e45069368ae15d3b0d7c84cb7978

• id: 930f78477b02b24514c4198c23f1b9955703e45069368ae15d3b0d7c84cb7978
• height: 1,408,266
• tx_id: 8ad667c5d683bffaa4b6da7cdd2bdcff16f6c496b9c10eab1ce1d9d80d8653f8
• amount: 0.700000000000

→ Group signature output set (3) height | output_id | index | coinbase -- | -- | -- | -- 1,407,911 | 778a6fe50a7c2c45823ec8d624929c9372f2e78e54ae1fefb828e886a83ea110 | 388,265 | True 1,408,108 | 13d8101489e706d31a92d581b798f9a57f67a1bd4c4ed5a40843c0d424ef38c8 | 388,470 | True 1,408,179 | f6ed9dd14e40bc842eea57603aab036eee25c93d8c309be7c8f43f7b0b593251 | 388,543 | True

---

↪ Input: d809e09011704abd27638665de4153805fc997907f0bca0b487ad3f5bcbfe32c

• id: d809e09011704abd27638665de4153805fc997907f0bca0b487ad3f5bcbfe32c
• height: 1,408,266
• tx_id: 8ad667c5d683bffaa4b6da7cdd2bdcff16f6c496b9c10eab1ce1d9d80d8653f8
• amount: 0.700000000000

→ Group signature output set (3) height | output_id | index | coinbase -- | -- | -- | -- 1,408,101 | d5291f45c6305e7c5198e2f303b22c0ae1fb59d29a9b6b347d2868131eb363ef | 388,463 | True 1,408,172 | 3bb825f22654b678b7a8c9c59fcada6e3c28965752c5691c9d51e26f9e73fd6d | 388,536 | True 1,408,179 | f6ed9dd14e40bc842eea57603aab036eee25c93d8c309be7c8f43f7b0b593251 | 388,543 | True

---

↪ Input: 7d5d3c3699d7ac9053e79bad65253ae8b9ba9a488ca02e4f03b95fe4a3efdc12

• id: 7d5d3c3699d7ac9053e79bad65253ae8b9ba9a488ca02e4f03b95fe4a3efdc12
• height: 1,408,266
• tx_id: 8ad667c5d683bffaa4b6da7cdd2bdcff16f6c496b9c10eab1ce1d9d80d8653f8
• amount: 0.700000000000

→ Group signature output set (3) height | output_id | index | coinbase -- | -- | -- | -- 1,407,103 | 5230719cccfe2d0b27d42685d40887917dd9d5cc0b417f3e32a253f8afb57a52 | 387,441 | True 1,407,416 | 747f591336abc7a0789d0bffda8e52af9042aac915f9188669658095fae9e6d3 | 387,761 | True 1,408,179 | f6ed9dd14e40bc842eea57603aab036eee25c93d8c309be7c8f43f7b0b593251 | 388,543 | True

iamsmooth commented 3 years ago

I can see reducing the number of denominations as being somewhat effective

Yes this was discussed in Monero before Ring CT. The idea was to switch to some smaller denomination set such as 1s and 5s or 1s, 3s, and 7s.

You have an increase in the number of outputs, but usually not that many:

1 -> 1 2 -> 1+1 3 -> 3 4 -> 3+1 5 -> 3+1+1 6 -> 3+3 7 -> 7 8 -> 7+1 9 -> 7+2

9 denominations reduced to 3 with:

3x 1 output 5x 2 outputs 1x 3 outputs

There could be better ways.

iamsmooth commented 3 years ago

Monero things are slightly different with larger signature group sizes and encrypted amounts

True, but the basic issue of favoring uniformity (maybe?) and spending every output at least once would still tend to apply, albeit less likely. At one point I do recall an analysis in Monero of some percentage of outputs never being spent. It may be much less now that the ring size is larger.

stoffu commented 3 years ago

I don't see this as much of a problem at all; some outputs remain unused in any ring signatures, so they are definitely known to be unspent. So what? How can this be harmful?

ghost commented 3 years ago

That makes them distinct from other outputs thereby reducing the uniformity and making them more traceable. Also unused outputs can increase the anonymity pool.

Yes there is always some outputs unspent that is just a fact. But imagine using the same output multiple times in one transaction when there are countless unspent outputs.

ghost commented 3 years ago

Let me rephrase that,

Being unspent makes them distinct from other outputs thereby reducing the uniformity and making them more traceable. Also using unused outputs in group signatures can increase the anonymity pool.

ghost commented 3 years ago

@stoffu, if you have time, can you see if this is correct? (code and logic) https://github.com/monero-project/monero/pull/8047

stoffu commented 3 years ago

@yorha-0x

That makes them distinct from other outputs thereby reducing the uniformity and making them more traceable.

Explain how outputs known to be definitely unspent contribute to increased traceability.

The issue (of using the same output in multiple inputs in the same tx) addressed in Monero PR8047 is a different matter, and I can agree that avoiding this can be beneficial.

ghost commented 3 years ago

I would say the most important thing about "unspent outputs" is that it reduces the uniformity of the output pool. Known unspent outputs can be separated from the total output pool in a trace analysis when paired with other external information. It provides meaningful information about the state of outputs and any meaningful information can be used in trace analysis.

Also, more fundamentally, I consider the meaning of "right to privacy" to include that "it is not publicly known whether or not I have spent my funds". No one should be able to know if my funds are spent. That includes the opposite: no one should be able to know if my funds are unspent. That is an equally private matter that should only be known to an individual who possess their keys.

Now I am not suggesting removing unspent outputs because I don't know how that would be feasible. But can they be minimized in a statistically unbiased way? Such as why are outputs spent many times in one transaction when there are many outputs which have never been included in a group signature? Also why are there so many denominations for obscure output amounts?

I am just brainstorming here and I appreciate your challenge to explain myself clearly. I hope I have accomplished that but I can't say whether what I write is really true, it is just my understanding. Do you agree that these "unspent outputs" increase traceability or at least infringe on aeon users' right to privacy?

PS Thank you for reviewing that. There is always places to make mistakes so your peer review is very much appreciated!

iamsmooth commented 3 years ago

@yorha-0x

I consider the meaning of "right to privacy" to include that "it is not publicly known whether or not I have spent my funds"

You can address this yourself with one round of churn after receiving the funds. The sender then doesn't know (others already don't know because they don't know who's funds those were anyway).

I do think it is ideal that all outputs be included in rings if there is a way to do that without causing other problems. If nothing else it increases the anonymity set (using the term broadly), since unspent are clearly not included.

ghost commented 3 years ago

Yeah, the sad thing is most people don't know about this. Also I have read many times over the year discouraging churning. I hope we can alleviate the situation so that it is not a burden put onto users and is "by default" a protected right like what is promised by most of these cryptonote coins.

Definitely increasing the ring size even slightly would help but I understand the careful work that has been put into this coin to make it lightweight and efficient. So let's not swamp that with one fell swoop before we consider some smaller targets. I am looking at these two small issues which I believe would help improve the situation:

No duplicate group member in transactions.

Combining less used denominations.

ghost commented 3 years ago

Not seeing much progress on monero PR. Waiting on that before continuing.

ghost commented 3 years ago

https://www.reddit.com/r/Monero/comments/r3p2kr/privacy_question/

iamsmooth commented 3 years ago

Without CT, there is a different privacy issue with denominations (related to above reddit). If you use a 100 output to send 1 (w/99 change) the receiver knows you had 100. Can't really be solved without CT or some form of churn or output breaking.

• © Githubissues.
• Githubissues is a development platform for aggregating issues.

[iamsmooth]

I can see reducing the number of denominations as being somewhat effective

Yes this was discussed in Monero before Ring CT. The idea was to switch to some smaller denomination set such as 1s and 5s or 1s, 3s, and 7s.

You have an increase in the number of outputs, but usually not that many:

1 -> 1 2 -> 1+1 3 -> 3 4 -> 3+1 5 -> 3+1+1 6 -> 3+3 7 -> 7 8 -> 7+1 9 -> 7+2

9 denominations reduced to 3 with:

3x 1 output 5x 2 outputs 1x 3 outputs

There could be better ways.

[iamsmooth]

Monero things are slightly different with larger signature group sizes and encrypted amounts

True, but the basic issue of favoring uniformity (maybe?) and spending every output at least once would still tend to apply, albeit less likely. At one point I do recall an analysis in Monero of some percentage of outputs never being spent. It may be much less now that the ring size is larger.

[stoffu]

I don't see this as much of a problem at all; some outputs remain unused in any ring signatures, so they are definitely known to be unspent. So what? How can this be harmful?

[ghost]

That makes them distinct from other outputs thereby reducing the uniformity and making them more traceable. Also unused outputs can increase the anonymity pool.

Yes there is always some outputs unspent that is just a fact. But imagine using the same output multiple times in one transaction when there are countless unspent outputs.

[ghost]

Let me rephrase that,

Being unspent makes them distinct from other outputs thereby reducing the uniformity and making them more traceable. Also using unused outputs in group signatures can increase the anonymity pool.

[ghost]

@stoffu, if you have time, can you see if this is correct? (code and logic) https://github.com/monero-project/monero/pull/8047

[stoffu]

@yorha-0x

That makes them distinct from other outputs thereby reducing the uniformity and making them more traceable.

Explain how outputs known to be definitely unspent contribute to increased traceability.

The issue (of using the same output in multiple inputs in the same tx) addressed in Monero PR8047 is a different matter, and I can agree that avoiding this can be beneficial.

[ghost]

I would say the most important thing about "unspent outputs" is that it reduces the uniformity of the output pool. Known unspent outputs can be separated from the total output pool in a trace analysis when paired with other external information. It provides meaningful information about the state of outputs and any meaningful information can be used in trace analysis.

Also, more fundamentally, I consider the meaning of "right to privacy" to include that "it is not publicly known whether or not I have spent my funds". No one should be able to know if my funds are spent. That includes the opposite: no one should be able to know if my funds are unspent. That is an equally private matter that should only be known to an individual who possess their keys.

Now I am not suggesting removing unspent outputs because I don't know how that would be feasible. But can they be minimized in a statistically unbiased way? Such as why are outputs spent many times in one transaction when there are many outputs which have never been included in a group signature? Also why are there so many denominations for obscure output amounts?

I am just brainstorming here and I appreciate your challenge to explain myself clearly. I hope I have accomplished that but I can't say whether what I write is really true, it is just my understanding. Do you agree that these "unspent outputs" increase traceability or at least infringe on aeon users' right to privacy?

PS Thank you for reviewing that. There is always places to make mistakes so your peer review is very much appreciated!

[iamsmooth]

@yorha-0x

I consider the meaning of "right to privacy" to include that "it is not publicly known whether or not I have spent my funds"

You can address this yourself with one round of churn after receiving the funds. The sender then doesn't know (others already don't know because they don't know who's funds those were anyway).

I do think it is ideal that all outputs be included in rings if there is a way to do that without causing other problems. If nothing else it increases the anonymity set (using the term broadly), since unspent are clearly not included.

[ghost]

Yeah, the sad thing is most people don't know about this. Also I have read many times over the year discouraging churning. I hope we can alleviate the situation so that it is not a burden put onto users and is "by default" a protected right like what is promised by most of these cryptonote coins.

Definitely increasing the ring size even slightly would help but I understand the careful work that has been put into this coin to make it lightweight and efficient. So let's not swamp that with one fell swoop before we consider some smaller targets. I am looking at these two small issues which I believe would help improve the situation:

No duplicate group member in transactions.

Combining less used denominations.

[ghost]

Not seeing much progress on monero PR. Waiting on that before continuing.

[ghost]

https://www.reddit.com/r/Monero/comments/r3p2kr/privacy_question/

[iamsmooth]

Without CT, there is a different privacy issue with denominations (related to above reddit). If you use a 100 output to send 1 (w/99 change) the receiver knows you had 100. Can't really be solved without CT or some form of churn or output breaking.