-
sarang
Brief reminder that there is a research meeting today at 17:00 UTC (a little over two hours from now)
-
sarang
Feel free to comment on the agenda issue in the channel topic for anything specific that should be discussed (but this is not required!)
-
sarang
Anyone is welcome to participate and share research of interest
-
sarang
I also want to remind everyone that since I'll be stepping back from research at the end of this month, there will be only one additional meeting (aside from this one) that I'll be leading
-
sarang
Someone else will have to take on that responsibility if they wish
-
UkoeHB_
Are you planning to make some kind of announcement?
-
sarang
Outside of this group? Not particularly
-
sarang
I don't see a need for any kind of fanfare
-
sarang
Workgroups are flexible for a reason; people come and go, contribute as they see fit, and so on
-
sarang
All of my work is available on GitHub as always
-
UkoeHB_
gotcha
-
sarang
Fortunately there's a much more robust research ecosystem now than when I first started contributing, and that's great to see
-
sarang
Lots of great data science, post-quantum research, increased academic work, atomic swaps, etc.
-
kenshamir[m]
<sarang "I also want to remind everyone t"> Oh I missed the initial announcement, is your time off indefinite?
-
sarang
I'm not totally sure what my plans are yet; but I think it's best to step away due to burnout
-
sarang
I haven't made any kind of big, reddit-style announcement, and I don't plan to
-
kenshamir[m]
<sarang "I'm not totally sure what my pla"> Ah, good luck!
-
needmoney90
Will you still hang out with us
-
sarang
You mean be on IRC a lot? Likely not
-
needmoney90
:(
-
midipoet
sarang: are you going to work for someone else?
-
sarang
I'll probably do unrelated dev work to pay the bills etc.
-
midipoet
you know actually on post-quantum research, the European Commission as part of their new funding programme (Horizon Europe) have a topic (and related subtopics) dedicated to the "quantum internet"
-
sarang
sounds fancy =p
-
midipoet
sarang: you gonna become a CCS/HTML dev?
-
sarang
Heh
-
sarang
I'm no designer
-
Isthmus
Ooh quantum internet needs quantum money :)
-
midipoet
Isthmus: the EC have enough money!
-
sarang
OK, let's get started with our research meeting
-
sarang
First, greetings!
-
sarang
Hi
-
midipoet
Seriously though if anyone is interested in looking at the call, let me know.
-
n3ptune
Hello
-
» Isthmus waves
-
midipoet
Horizon Europe wants consortiums built with emphasis on extra-european knowledge/partnerships. Usual budget for these things is 4-12 million.
-
TheCharlatan
hi
-
» midipoet shuts up as meeting
-
ArticMine
hi
-
sarang
A brief reminder that next week's meeting will be the last that I will be leading; if anyone else wishes to take over meetings at that point, feel free to do so
-
sarang
Let's move to roundtable
-
sarang
Where anyone can share research of interest with the group
-
sarang
Does anyone wish to share anything?
-
n3ptune
I'd like to share two big SQL projects that I've just finished
-
n3ptune
The first is a tx_extra parser for PostgreSQL:
github.com/neptuneresearch/tx-extra-parse
-
n3ptune
The point is to parse a transaction's tx_extra data (which is all packed together into one byte string) into separate database records for each sub-field tag and data, so it can be further queried on.
-
n3ptune
Here are some queries we ran about tag usage and statistics, and their results:
github.com/neptuneresearch/monero-tx-extra-statistics-report
-
n3ptune
We presented some of this before in a Feb 2020 MRL meeting, and some various MRL github issues. There were some questions from then that are answered in here, sorry that took me so long!
-
n3ptune
The biggest result to me is that there are no unknown tx_extra tags being used: no one is storing any other kind of data in Monero transactions, besides the known kinds.
-
sarang
Huh, interesting
-
sarang
Do you take this to mean that a deprecation of `tx_extra` in favor of enforcing standard fields like encrypted pID would be unlikely to break existing unknown use cases?
-
n3ptune
Yes, regarding current usage
-
n3ptune
It would still break future possibilities
-
sarang
Sure, but that's a different problem
-
Isthmus
The answer to UkoeHB_ 's question is very interesting
-
Isthmus
Also, the single transaction that contains 1000 payment IDs, lol
-
Isthmus
Los of interesting stuff to unpack here
-
Isthmus
s/os/ots
-
monerobux
Isthmus meant to say: Lots of interesting stuff to unpack here
-
n3ptune
There are also multiple ways to write the same data, and a transaction's choice there is a fingerprint
-
sarang
Yep, that's certainly come up before
-
n3ptune
For instance, do you write "public key" and then "encrypted payment id", or "encrypted payment id" and then "public key"
-
sarang
Right
-
n3ptune
or do you even do something unique like you add "additional public keys, 0" to every transaction
-
sarang
The "best" option (for some definition of "best") is to enforce a standard ordering and set of data
-
sarang
thereby removing the option for fingerprinting
-
sarang
or at least making it more difficult :)
-
n3ptune
Oh and also, full deprecation would stop unencrypted PID usage.
-
sarang
Yep
-
Isthmus
Yep, upvote for TLV ordering
-
sarang
It's nice to have some data backing this up
-
sarang
Anything else you'd like to share on this, n3ptune?
-
sarang
Or Isthmus?
-
n3ptune
Not on tx_extra
-
n3ptune
any questions welcome
-
n3ptune
-
n3ptune
This provides a way from within PostgreSQL to build the transaction output index, and to decode a transaction's key_offsets, which together let you list a transaction's ring members.
-
n3ptune
This is a building block for writing more complicated queries regarding ring members, like decoy selection analysis.
-
sarang
Cool, so similar to what the block explorer interface does?
-
n3ptune
Exactly
-
sarang
neat
-
sarang
Anything interesting pop up so far when looking at that?
-
sarang
Or is it still a bit early for that analysis
-
n3ptune
This is pretty fresh yeah, we don't have any use cases yet
-
Isthmus
Haha we have a ton of use cases, they just haven't been coded up yet :- p
-
Isthmus
This will be a fun one to mess around with
-
sarang
Oh totally
-
sarang
Since decoy selection is totally up to the client
-
Isthmus
Especially once I add on the layer for tracking chainlets with fungibility defects
-
sarang
This is great!
-
sarang
Any questions for n3ptune and/or Isthmus?
-
sarang
All righty
-
sarang
I have a few things to share
-
sarang
I presented Triptych to an ESORICS workshop, which went well
-
sarang
I'm giving a talk on privacy at MCCVR this weekend, and participating in a panel on Bitcoin privacy
-
dEBRUYNE
To be clear, the talk will be separate? Because I only saw an announcement regarding the panel
-
sarang
I made some updates to Arcturus for a tiny efficiency bump that simplifies things a bit, as well as updated its Python proof-of-concept code to better indicate how to do efficient verification
-
sarang
Yes, the talk is separate and occurs just before the panel
-
sarang
They separately asked me to give the talk after I agreed to do the panel
-
sarang
I'm also updating some transaction statistics for general use
-
sarang
An intriguing idea came from cargodog[m] recently
-
cargodog[m]
Where will those be shared? I have been looking for TX stats :D
-
sarang
They worked up a Rust implementation of Arcturus:
github.com/cargodog/arcturus
-
cargodog[m]
:wave:
-
dEBRUYNE
Thanks for clarifying
-
sarang
cargodog[m]: I'll make them available after my scripts finish up
-
sarang
The scripts are in the `tracing` branch of my `skunkworks` repo
-
cargodog[m]
Great, thanks!
-
sarang
cargodog[m] had an idea to use generalized Gray codes to speed up Triptych/Arcturus/etc. operations that's intriguing
-
sarang
I've been doing more digging to determine the extent of such efficiency gains, the conditions under which they apply significantly, as well as to what extent they're affected by underlying crypto plumbing
-
sarang
cargodog[m]: you're welcome to share this work yourself, if you like!
-
sarang
I didn't know if you were around for this meeting
-
cargodog[m]
Thanks sarang: I am currently writing up a paper to formally describe the improved technique
-
cargodog[m]
Sorry, I was running a few minutes late :)
-
sarang
One thing I noticed about your one-of-many binary Gray implementation was that it performed the Gray decomposition separately from determining which coefficients to update
-
cargodog[m]
My goal is to have a paper (short but sweet), that can clearly explain the concept, not just as it applies to Arcturus, but Triptych, Lelantus, One-out-of-Many, etc
-
sarang
I am also working on the generalized version and have the Gray code stuff operating, but I want to directly integrate the coefficient changes, to avoid redundancy
-
cargodog[m]
Indeed. My OOM implementation is fairly specific. Most of my work right now is generalizing this stuff to make it more broadly applicable
-
sarang
Fortunately you can iteratively compute the `n`-Gray codes too, meaning there's a lot of room for improving how your binary method works
-
sarang
I implemented the iterative method from a paper; I can link some example code after the meeting
-
cargodog[m]
That would be great
-
sarang
What remains is simply to do the coefficient updating from it, which is not too complicated
-
sarang
I don't think there are necessarily _huge_ gains to be made doing it this way, as opposed to a non-iterated method, but this way is certainly faster
-
sarang
Since you're not computing all the codes from scratch
-
sarang
I also had commented that I had questioned your approach because of the reliance on expensive inversions, but I had totally neglected the effects of batch inversion, which both our code and yours support
-
cargodog[m]
Still, every gain is important
-
cargodog[m]
Ultimately, I hope to attract more eyes to Arcturus, and build confidence on its hardness assumption
-
sarang
Meaning you only have to do a single inversion, and then a nontrivial number of accumulator multiplications
-
sarang
I'm super excited that you implemented this cargodog[m]
-
sarang
:D
-
cargodog[m]
Hopefully I can deliver something useful :D
-
sarang
FWIW each scalar inversion is equivalent to ~200 multiplications
-
cargodog[m]
The paper has been a breeze to work with
-
sarang
and the batch inversion of `k` scalars is one 200-mult inversion and another `3k` multiplications
-
sarang
Thanks!
-
cargodog[m]
^ Ah, I was looking for that number yesterday. Thansk!
-
sarang
I'm glad the paper was clear
-
sarang
So anyway, the use of the Gray method will incur that batch inversion cost
-
sarang
and hence I assume there's some tradeoff that's eventually dominated by the gains from the Gray method at higher anon set sizes
-
sarang
You had also pointed out that in the batch verification case where anon sets are common, the gains improve even more
-
cargodog[m]
more important than anon set size is batch size
-
cargodog[m]
but yes
-
sarang
Of course, the effectiveness there depends on how you batch
-
sarang
For something like Lelantus, they reuse a huge anon set, but have to worry about things like windowing and filling up that set
-
sarang
For an approach more similar to ours, where we care a lot about selection age, you'd have fewer common elements in the batch
-
cargodog[m]
Yeah, I am skeptical how they intend to receive many common TXs to batch
-
cargodog[m]
but the idea is similar
-
sarang
Sure, but I think it means that the Gray gains are very dependent on how you select anon sets, and therefore how you batch
-
cargodog[m]
Yes indeed
-
sarang
At any rate, provided you clear the inversion computational hurdle, you'd start to see benefits
-
cargodog[m]
Im interested to explore ring selection techniques to maximize batching
-
sarang
Yeah, it's very nontrivial
-
cargodog[m]
An obvious approach is to increase ring size :)
-
sarang
Sure, but you can't ignore selection age, which is a big heuristic
-
sarang
and that changes dynamically
-
cargodog[m]
indeed. It is a very complex problem
-
sarang
In theory, the Lelantus-style "everyone uses a big anon set" is great for computation
-
cargodog[m]
Unfortunately I need to sign off earlier than expected. I will check in later, and welcome any questions or suggestions to either of my projects :)
-
sarang
but I fear in practice it's burdensome and could lead to age heuristics
-
sarang
No problem! Thanks for joining in today
-
cargodog[m]
I hope to be present longer in the future!
-
sarang
Hop in the channel any time
-
sarang
I'll link the inversion complexity stuff for you, as well as the `n`-Gray example code, after the meeting
-
sarang
Logs are available in the channel topic
-
sarang
Just search for mentions etc.
-
sarang
or perhaps your client will show mentions too, whatever
-
sarang
I'll get the links :)
-
sarang
OK, any questions on the topics I mentioned?
-
sarang
If not, does anyone else wish to share research topics?
-
Isthmus
I found a figure that is a concrete example of n3ptune's framework in action
-
sarang
Go on!
-
Isthmus
So I picked a random fungibility defect (in this case a particular extra tag) and showed how it's used to link transactions via the chain address
-
Isthmus
-
Isthmus
So the wallet received 3 fresh external outputs, and made 16 transactions
-
Isthmus
But each time, the new transaction consumed a change output with the exact same defect
-
sarang
yikes
-
Isthmus
So doxxing all of the transactions was trivial
-
UkoeHB_
is the tag a payment ID or something?
-
Isthmus
Now the cool thing is that I can automate n3ptune's framework to both 1) automatically sift through data to identify the fungibility defects, and 2) automatically identify every transaction (/chain) from that wallet
-
Isthmus
So we can map out the transaction tree through change addresses for ANY wallet with ANY fungibility defect
-
Isthmus
It's a whole new montser
-
UkoeHB_
really impressive work guys
-
dEBRUYNE
+1
-
n3ptune
Thanks :)
-
Isthmus
I think it was the `n_extra_nonce` tag?
-
dEBRUYNE
I guess standardizing the tx_extra format would help in this regard
-
sarang
yep
-
Isthmus
Standardizing tx_extra would entirely shut down this kind of analysis, if the protocol only allowed keys and an encrypted PID
-
sarang
Well, in theory
-
sarang
You can't actually enforce the encrypted pID properly at the consensus level
-
Isthmus
Well, true, the fungibility defects could also be things like unlock time, unusual fees, etc.
-
sarang
You could use authenticated encryption to avoid the recipient accepting such a txn if you wanted to...
-
sarang
No, I mean you can set "the pID" to be anything you want
-
sarang
all zeros
-
moneromooo
Is that extra valid as per the wallet parsing rules ?
-
sarang
your phone number
-
sarang
whatever
-
n3ptune
I think that was a valid tag
-
moneromooo
There was a claim before of non non standard fields used, so I'm guessing it's vlaid.
-
moneromooo
So it's vlaid but out of order compared to what monerod outputs ?
-
n3ptune
I think it was an extra nonce, in a user transaction
-
n3ptune
Which Monero Core wouldn't ever write?
-
moneromooo
a 32 byte one ?
-
moneromooo
It would not anymore.
-
n3ptune
As in, not any kind of payment id. Neither 020901 or 022100. Just an 02 with a valid size
-
moneromooo
Oh. OK.
-
moneromooo
So our monero code would not write that by itself.
-
dEBRUYNE
<sarang> your phone number <= Wouldn't those still be indistinguishable due to the random element?
-
sarang
?
-
sarang
What random element?
-
sarang
The network can't verify that you encrypted a payment ID
-
dEBRUYNE
Ignore me, I am conflating things
-
sarang
You could arrange it so the _recipient_ could
-
sarang
but not at the consensus level
-
sarang
The best you can do is have the recipient not spend such an output
-
Isthmus
^zcash does this, for example
-
sarang
The recipient? Yes
-
moneromooo
Having the recipient not spend actual money they got ? Fat chance it's gonna happen.
-
sarang
that's entirely possible (but not free from a space perspective)
-
dEBRUYNE
We could add a warning though
-
sarang
Isthmus: FWIW that's all on the client
-
dEBRUYNE
If such an output would be received
-
sarang
You could write a Zcash client that spends it anyway
-
sarang
Network can't tell
-
Isthmus
Yep
-
sarang
dEBRUYNE: we'd have to do an AEAD method and change the way that encryption happens
-
sarang
We'd probably end up including all recipient-encrypted data in that, which is much cleaner from a protocol perspective
-
sarang
and share a single AEAD tag
-
sarang
Anyway
-
sarang
We're coming to the end of the hour
-
sarang
Were there any other points relating to this that ought to be discussed now?
-
Isthmus
gg
-
sarang
If anything, I think this provides further evidence that enforcing standard TLV fields in `tx_extra` would be very useful
-
sarang
and the data indicate that there are no obvious existing use cases for nonstandard fields that would be disrupted
-
sarang
OK, any other research topics to share before the time is up?
-
sarang
If not, we can adjourn!
-
sarang
Thanks to everyone for attending
-
sgp_
missed this but just read through it all :)
-
moneromooo
cargodog[m]: thanks for sharing your work on this :)
-
sarang
-
sarang
You can find the individual scalar inversion from that function, and from there see exactly how the additional ladder works
-
sarang
-
sarang
And here's an example of iterated `n`-Gray codes
-
sarang
(the value on line 9 is hard-coded for convenience)
-
sarang
s/additional/addition
-
monerobux
sarang meant to say: You can find the individual scalar inversion from that function, and from there see exactly how the addition ladder works
-
sarang
good bot