14:43:24 <sarang> Brief reminder that there is a research meeting today at 17:00 UTC (a little over two hours from now)
14:43:59 <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!)
14:44:15 <sarang> Anyone is welcome to participate and share research of interest
14:45:21 <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
14:45:35 <sarang> Someone else will have to take on that responsibility if they wish
14:54:39 <UkoeHB_> Are you planning to make some kind of announcement?
14:57:18 <sarang> Outside of this group? Not particularly
14:57:36 <sarang> I don't see a need for any kind of fanfare
14:59:23 <sarang> Workgroups are flexible for a reason; people come and go, contribute as they see fit, and so on
14:59:50 <sarang> All of my work is available on GitHub as always
15:07:32 <UkoeHB_> gotcha
15:08:12 <sarang> Fortunately there's a much more robust research ecosystem now than when I first started contributing, and that's great to see
15:08:43 <sarang> Lots of great data science, post-quantum research, increased academic work, atomic swaps, etc.
15:44:05 <kenshamir[m]> <sarang "I also want to remind everyone t"> Oh I missed the initial announcement, is your time off indefinite?
15:47:48 <sarang> I'm not totally sure what my plans are yet; but I think it's best to step away due to burnout
15:49:01 <sarang> I haven't made any kind of big, reddit-style announcement, and I don't plan to
16:18:27 <kenshamir[m]> <sarang "I'm not totally sure what my pla"> Ah, good luck!
16:39:23 <needmoney90> Will you still hang out with us
16:39:48 <sarang> You mean be on IRC a lot? Likely not
16:40:18 <needmoney90> :(
16:57:55 <midipoet> sarang: are you going to work for someone else?
16:59:33 <sarang> I'll probably do unrelated dev work to pay the bills etc.
16:59:58 <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"
17:00:16 <sarang> sounds fancy =p
17:00:24 <midipoet> sarang: you gonna become a CCS/HTML dev?
17:00:29 <sarang> Heh
17:00:32 <sarang> I'm no designer
17:00:49 <Isthmus> Ooh quantum internet needs quantum money :)
17:01:04 <midipoet> Isthmus: the EC have enough money!
17:01:23 <sarang> OK, let's get started with our research meeting
17:01:28 <sarang> First, greetings!
17:01:29 <sarang> Hi
17:01:31 <midipoet> Seriously though if anyone is interested in looking at the call, let me know.
17:01:36 <n3ptune> Hello
17:01:40 * Isthmus waves
17:02:16 <midipoet> Horizon Europe wants consortiums built with emphasis on extra-european knowledge/partnerships. Usual budget for these things is 4-12 million.
17:02:30 <TheCharlatan> hi
17:02:45 * midipoet shuts up as meeting
17:03:06 <ArticMine> hi
17:03:45 <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
17:03:49 <sarang> Let's move to roundtable
17:03:56 <sarang> Where anyone can share research of interest with the group
17:04:00 <sarang> Does anyone wish to share anything?
17:04:08 <n3ptune> I'd like to share two big SQL projects that I've just finished
17:04:24 <n3ptune> The first is a tx_extra parser for PostgreSQL: http://github.com/neptuneresearch/tx-extra-parse
17:04:32 <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.
17:04:40 <n3ptune> Here are some queries we ran about tag usage and statistics, and their results: http://github.com/neptuneresearch/monero-tx-extra-statistics-report
17:05:05 <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!
17:05:23 <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.
17:05:59 <sarang> Huh, interesting
17:06:34 <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?
17:06:59 <n3ptune> Yes, regarding current usage
17:07:17 <n3ptune> It would still break future possibilities
17:07:25 <sarang> Sure, but that's a different problem
17:07:45 <Isthmus> The answer to UkoeHB_ 's question is very interesting
17:08:04 <Isthmus> Also, the single transaction that contains 1000 payment IDs, lol
17:08:19 <Isthmus> Los of interesting stuff to unpack here
17:08:24 <Isthmus> s/os/ots
17:08:25 <monerobux> Isthmus meant to say: Lots of interesting stuff to unpack here
17:08:28 <n3ptune> There are also multiple ways to write the same data, and a transaction's choice there is a fingerprint
17:08:37 <sarang> Yep, that's certainly come up before
17:08:41 <n3ptune> For instance, do you write "public key" and then "encrypted payment id",  or "encrypted payment id" and then "public key"
17:08:52 <sarang> Right
17:08:57 <n3ptune> or do you even do something unique like you add "additional public keys, 0" to every transaction
17:09:19 <sarang> The "best" option (for some definition of "best") is to enforce a standard ordering and set of data
17:09:27 <sarang> thereby removing the option for fingerprinting
17:09:34 <sarang> or at least making it more difficult :)
17:10:16 <n3ptune> Oh and also, full deprecation would stop unencrypted PID usage.
17:10:40 <sarang> Yep
17:10:44 <Isthmus> Yep, upvote for TLV ordering
17:11:02 <sarang> It's nice to have some data backing this up
17:12:33 <sarang> Anything else you'd like to share on this, n3ptune?
17:12:36 <sarang> Or Isthmus?
17:12:46 <n3ptune> Not on tx_extra
17:12:48 <n3ptune> any questions welcome
17:12:49 <n3ptune> The other SQL project I'd like to share is: http://github.com/neptuneresearch/ring-membership-sql
17:12:55 <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.
17:13:01 <n3ptune> This is a building block for writing more complicated queries regarding ring members, like decoy selection analysis.
17:13:24 <sarang> Cool, so similar to what the block explorer interface does?
17:13:32 <n3ptune> Exactly
17:13:35 <sarang> neat
17:14:30 <sarang> Anything interesting pop up so far when looking at that?
17:14:39 <sarang> Or is it still a bit early for that analysis
17:14:59 <n3ptune> This is pretty fresh yeah, we don't have any use cases yet
17:15:18 <Isthmus> Haha we have a ton of use cases, they just haven't been coded up yet :- p
17:15:29 <Isthmus> This will be a fun one to mess around with
17:15:45 <sarang> Oh totally
17:15:53 <sarang> Since decoy selection is totally up to the client
17:15:53 <Isthmus> Especially once I add on the layer for tracking chainlets with fungibility defects
17:17:23 <sarang> This is great!
17:17:41 <sarang> Any questions for n3ptune and/or Isthmus?
17:18:47 <sarang> All righty
17:18:50 <sarang> I have a few things to share
17:19:09 <sarang> I presented Triptych to an ESORICS workshop, which went well
17:19:25 <sarang> I'm giving a talk on privacy at MCCVR this weekend, and participating in a panel on Bitcoin privacy
17:20:05 <dEBRUYNE> To be clear, the talk will be separate? Because I only saw an announcement regarding the panel
17:20:12 <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
17:20:19 <sarang> Yes, the talk is separate and occurs just before the panel
17:20:34 <sarang> They separately asked me to give the talk after I agreed to do the panel
17:20:51 <sarang> I'm also updating some transaction statistics for general use
17:21:01 <sarang> An intriguing idea came from cargodog[m] recently
17:21:16 <cargodog[m]> Where will those be shared? I have been looking for TX stats :D
17:21:17 <sarang> They worked up a Rust implementation of Arcturus: https://github.com/cargodog/arcturus/
17:21:23 <cargodog[m]> :wave:
17:21:25 <dEBRUYNE> Thanks for clarifying
17:21:30 <sarang> cargodog[m]: I'll make them available after my scripts finish up
17:21:47 <sarang> The scripts are in the `tracing` branch of my `skunkworks` repo
17:22:06 <cargodog[m]> Great, thanks!
17:22:08 <sarang> cargodog[m] had an idea to use generalized Gray codes to speed up Triptych/Arcturus/etc. operations that's intriguing
17:22:44 <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
17:22:56 <sarang> cargodog[m]: you're welcome to share this work yourself, if you like!
17:23:20 <sarang> I didn't know if you were around for this meeting
17:23:33 <cargodog[m]> Thanks sarang: I am currently writing up a paper to formally describe the improved technique
17:23:49 <cargodog[m]> Sorry, I was running a few minutes late :)
17:24:26 <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
17:24:30 <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
17:24:49 <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
17:25:31 <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
17:25:37 <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
17:26:26 <sarang> I implemented the iterative method from a paper; I can link some example code after the meeting
17:26:42 <cargodog[m]> That would be great
17:26:45 <sarang> What remains is simply to do the coefficient updating from it, which is not too complicated
17:27:18 <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
17:27:31 <sarang> Since you're not computing all the codes from scratch
17:28:07 <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
17:28:08 <cargodog[m]> Still, every gain is important
17:28:12 <cargodog[m]> Ultimately, I hope to attract more eyes to Arcturus, and build confidence on its hardness assumption
17:28:26 <sarang> Meaning you only have to do a single inversion, and then a nontrivial number of accumulator multiplications
17:28:36 <sarang> I'm super excited that you implemented this cargodog[m]
17:28:38 <sarang> :D
17:29:05 <cargodog[m]> Hopefully I can deliver something useful :D
17:29:07 <sarang> FWIW each scalar inversion is equivalent to ~200 multiplications
17:29:13 <cargodog[m]> The paper has been a breeze to work with
17:29:26 <sarang> and the batch inversion of `k` scalars is one 200-mult inversion and another `3k` multiplications
17:29:29 <sarang> Thanks!
17:29:30 <cargodog[m]> ^ Ah, I was looking for that number yesterday. Thansk!
17:29:33 <sarang> I'm glad the paper was clear
17:30:04 <sarang> So anyway, the use of the Gray method will incur that batch inversion cost
17:30:22 <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
17:30:40 <sarang> You had also pointed out that in the batch verification case where anon sets are common, the gains improve even more
17:30:43 <cargodog[m]> more important than anon set size is batch size
17:30:47 <cargodog[m]> but yes
17:30:48 <sarang> Of course, the effectiveness there depends on how you batch
17:31:08 <sarang> For something like Lelantus, they reuse a huge anon set, but have to worry about things like windowing and filling up that set
17:31:30 <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
17:31:49 <cargodog[m]> Yeah, I am skeptical how they intend to receive many common TXs to batch
17:31:53 <cargodog[m]> but the idea is similar
17:32:13 <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
17:32:33 <cargodog[m]> Yes indeed
17:32:38 <sarang> At any rate, provided you clear the inversion computational hurdle, you'd start to see benefits
17:32:56 <cargodog[m]> Im interested to explore ring selection techniques to maximize batching
17:33:11 <sarang> Yeah, it's very nontrivial
17:33:13 <cargodog[m]> An obvious approach is to increase ring size :)
17:33:24 <sarang> Sure, but you can't ignore selection age, which is a big heuristic
17:33:30 <sarang> and that changes dynamically
17:33:42 <cargodog[m]> indeed. It is a very complex problem
17:33:59 <sarang> In theory, the Lelantus-style "everyone uses a big anon set" is great for computation
17:34:03 <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 :)
17:34:10 <sarang> but I fear in practice it's burdensome and could lead to age heuristics
17:34:20 <sarang> No problem! Thanks for joining in today
17:34:33 <cargodog[m]> I hope to be present longer in the future!
17:34:42 <sarang> Hop in the channel any time
17:35:15 <sarang> I'll link the inversion complexity stuff for you, as well as the `n`-Gray example code, after the meeting
17:35:23 <sarang> Logs are available in the channel topic
17:35:34 <sarang> Just search for mentions etc.
17:35:41 <sarang> or perhaps your client will show mentions too, whatever
17:35:46 <sarang> I'll get the links :)
17:36:18 <sarang> OK, any questions on the topics I mentioned?
17:37:50 <sarang> If not, does anyone else wish to share research topics?
17:38:16 <Isthmus> I found a figure that is a concrete example of n3ptune's framework in action
17:38:23 <sarang> Go on!
17:39:03 <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
17:39:04 <Isthmus> https://usercontent.irccloud-cdn.com/file/1F4ccO3H/image.png
17:39:20 <Isthmus> So the wallet received 3 fresh external outputs, and made 16 transactions
17:39:39 <Isthmus> But each time, the new transaction consumed a change output with the exact same defect
17:40:14 <sarang> yikes
17:40:16 <Isthmus> So doxxing all of the transactions was trivial
17:40:39 <UkoeHB_> is the tag a payment ID or something?
17:41:04 <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
17:41:24 <Isthmus> So we can map out the transaction tree through change addresses for ANY wallet with ANY fungibility defect
17:41:29 <Isthmus> It's a whole new montser
17:42:27 <UkoeHB_> really impressive work guys
17:42:32 <dEBRUYNE> +1
17:42:34 <n3ptune> Thanks :)
17:42:43 <Isthmus> I think it was the `n_extra_nonce` tag?
17:42:46 <dEBRUYNE> I guess standardizing the tx_extra format would help in this regard
17:42:49 <sarang> yep
17:43:34 <Isthmus> Standardizing tx_extra would entirely shut down this kind of analysis, if the protocol only allowed keys and an encrypted PID
17:44:07 <sarang> Well, in theory
17:44:19 <sarang> You can't actually enforce the encrypted pID properly at the consensus level
17:44:36 <Isthmus> Well, true, the fungibility defects could also be things like unlock time, unusual fees, etc.
17:44:48 <sarang> You could use authenticated encryption to avoid the recipient accepting such a txn if you wanted to...
17:44:58 <sarang> No, I mean you can set "the pID" to be anything you want
17:45:00 <sarang> all zeros
17:45:03 <moneromooo> Is that extra valid as per the wallet parsing rules ?
17:45:04 <sarang> your phone number
17:45:06 <sarang> whatever
17:45:20 <n3ptune> I think that was a valid tag
17:45:23 <moneromooo> There was a claim before of non non standard fields used, so I'm guessing it's vlaid.
17:45:37 <moneromooo> So it's vlaid but out of order compared to what monerod outputs ?
17:45:50 <n3ptune> I think it was an extra nonce, in a user transaction
17:46:03 <n3ptune> Which Monero Core wouldn't ever write?
17:46:23 <moneromooo> a 32 byte one ?
17:46:31 <moneromooo> It would not anymore.
17:47:04 <n3ptune> As in, not any kind of payment id. Neither 020901 or 022100.  Just an 02 with a valid size
17:47:15 <moneromooo> Oh. OK.
17:47:44 <moneromooo> So our monero code would not write that by itself.
17:47:45 <dEBRUYNE> <sarang> your phone number <= Wouldn't those still be indistinguishable due to the random element?
17:47:56 <sarang> ?
17:48:06 <sarang> What random element?
17:48:16 <sarang> The network can't verify that you encrypted a payment ID
17:48:27 <dEBRUYNE> Ignore me, I am conflating things
17:48:30 <sarang> You could arrange it so the _recipient_ could
17:48:34 <sarang> but not at the consensus level
17:48:42 <sarang> The best you can do is have the recipient not spend such an output
17:48:43 <Isthmus> ^zcash does this, for example
17:48:51 <sarang> The recipient? Yes
17:49:28 <moneromooo> Having the recipient not spend actual money they got ? Fat chance it's gonna happen.
17:49:30 <sarang> that's entirely possible (but not free from a space perspective)
17:50:18 <dEBRUYNE> We could add a warning though
17:50:18 <sarang> Isthmus: FWIW that's all on the client
17:50:22 <dEBRUYNE> If such an output would be received
17:50:24 <sarang> You could write a Zcash client that spends it anyway
17:50:29 <sarang> Network can't tell
17:50:38 <Isthmus> Yep
17:51:22 <sarang> dEBRUYNE: we'd have to do an AEAD method and change the way that encryption happens
17:51:46 <sarang> We'd probably end up including all recipient-encrypted data in that, which is much cleaner from a protocol perspective
17:51:58 <sarang> and share a single AEAD tag
17:52:56 <sarang> Anyway
17:53:02 <sarang> We're coming to the end of the hour
17:53:13 <sarang> Were there any other points relating to this that ought to be discussed now?
17:53:57 <Isthmus> gg
17:54:25 <sarang> If anything, I think this provides further evidence that enforcing standard TLV fields in `tx_extra` would be very useful
17:54:42 <sarang> and the data indicate that there are no obvious existing use cases for nonstandard fields that would be disrupted
17:55:37 <sarang> OK, any other research topics to share before the time is up?
17:57:06 <sarang> If not, we can adjourn!
17:57:10 <sarang> Thanks to everyone for attending
17:57:53 <sgp_> missed this but just read through it all :)
17:58:34 <moneromooo> cargodog[m]: thanks for sharing your work on this :)
17:59:58 <sarang> cargodog[m]: here's the batch inversion your library uses https://github.com/dalek-cryptography/curve25519-dalek/blob/master/src/scalar.rs#L723
18:00:16 <sarang> You can find the individual scalar inversion from that function, and from there see exactly how the additional ladder works
18:01:16 <sarang> https://www.irccloud.com/pastebin/B3jfb60h/gray-example
18:01:28 <sarang> And here's an example of iterated `n`-Gray codes
18:01:39 <sarang> (the value on line 9 is hard-coded for convenience)
18:01:57 <sarang> s/additional/addition
18:01:57 <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
18:02:06 <sarang> good bot