| layout |
title |
tags |
author |
| post |
Logs for the MRL Meeting Held on 2020-05-27 |
| dev diaries |
| crypto |
| research |
|
asymptotically / Sarang |
Logs
<sarang> OK, it's time for the meeting!
<sarang> As usual, begin with GREETINGS
<Isthmus> GREETINGS
<ArticMine> Hi
<sarang> hello
<knaccc> yo
<knaccc> very nice :)
<sarang> Subtle!
<sgp_> hello
<sarang> OK, let's move to ROUNDTABLE
<sarang> I'll start with a few things
<sarang> A preprint came out from student researchers at CMU on Monero and Zcash tracing: https://eprint.iacr.org/2020/593
<sarang> It only looked at pre-Sapling Zcash data that was previously examined (independent checking of earlier work is valuable)
<sarang> but did look at much more recent Monero transactions
<sarang> The overall conclusions are that protocol improvements have been very useful
<sarang> I disagree completely with their methodology leading to a conclusion about the effectiveness of the updated output selection algorithm, however
<sarang> and I think they can't reach any conclusions from that
<sarang> I put together some notes and sent them to the authors, along with my thanks for their work
<sarang> They did make their analysis code available on GitHub, so I'm going to see what useful information can be pulled from that as well
<sarang> Separately from this, I'm working on some non-slanderability definition stuff to port from Omniring's security model to that of Arcturus now
<sarang> Worked on address verification proof updates with moneromooo
<sarang> and wrote up some test code for the view tag scanning idea
<knaccc> in what lang?
<sarang> As described by UkoeHB_ earlier, the idea is to include a small truncated hash of the key derivation for each output, and use this for a "fast scanning" mode that avoids some curve operations
<sarang> knaccc: timing code in the C++ codebase
<sarang> It's not an implementation, only for getting timing information
<sarang> Under the assumption that a view tag is a single byte and only 1 out of every 256 tag checks results in a match, here are the numbers
<sarang> On a particular test machine, the total scan cost _without_ view tags for those 256 checks is 43.520 ms
<sarang> The total scan cost _with_ view tags (and a single match in the group) is 32.559 ms
<sarang> That means the fast scan mode operates in 75% of the time as the standard scan mode, in this example
<knaccc> how many txs in total were you scanning?
<sarang> This wasn't an actual scan; it was a simulation that performed all the operations for fake outputs generated by the test code
<knaccc> i just mean, what was the ratio of matching outputs to outputs scanned
<sarang> It built a view tag and output key, and then timed the scanning under various modes
<sarang> This assumed 1/256
<sarang> Purely statistical
<knaccc> when you hit that 1 in 256, are you including the cost of the extra scalamultbase to then properly check?
<sarang> Yes, let me explain a bit
<sarang> The test has 3 modes
<sarang> Mode 1. standard scanning, no view tags
<sarang> Mode 2. view tag, no hit (compute the derivation and view tag, and then abort)
<sarang> Mode 3. view tag, hit (after the derivation and view tag check, recompute the expected spend pubkey)
<sarang> So the "no view tags" total assumes 256 Mode 1 operations
<sarang> The "yes view tags" total assumes 255 Mode 2 operations, and 1 Mode 3 operation
<ArticMine> There is the question also of non standard math
<sarang> ?
<sarang> knaccc: the test code actually always generates a matching view tag and output key (for sanity checking), but the simulation just uses the modes to fake whether or not a match occurred (there's no difference in timing doing it this way)
<knaccc> your findings roughly match up with the back-of-envelope calc that if you almost always save on a scalarmultbase, and if variable-base scalarmult costs 25 and a fixed-base scalarmult costs 15, then you reduce the scanning cost from 100% to 25/(25+15) = 62.5%
<ArticMine> for Arcturus
<sarang> ArticMine: view tags are entirely separate from Arcturus
<ArticMine> sorry
<sarang> They apply generally to the output key construction process
<sarang> which is abstracted away from Arcturus anyway
<sarang> The added risk with view tags is that a sending wallet can generate whatever tag it wants, and the receiver would not detect the output
<sarang> But FWIW the reverse isn't true... you can't DoS a scan with this method
<sarang> Bad view tag implementations could also fingerprint if a wallet did something silly like always set it to a fixed value
<sarang> Of course, compatible recipient wallets wouldn't detect it if they did fast scanning, and this would not look good for the incompatible sending wallet anyway
<sarang> Here's the timing code: 93172f80b2
<sarang> (it does pass build checks, but Windows CI is broken)
<knaccc> i wonder where the difference is between the 75% real-world and 62.5% theoretical
<knaccc> i'll read through your code
<sarang> There is a small cost for each hash computation, and for the few non-scalarmult operations
<sarang> Yeah, let me know if you notice something that I missed
<knaccc> those are usually neglibible compared to .15ms or .25ms for an EC mult
<sarang> aye
<sarang> IIRC the hash stuff is something like 2-3% of the total time
<knaccc> i don't see anywhere in your code actually referencing loop_count
<sarang> That's taken care of by the test runner
<sarang> Which uses the individual results for statistics
<knaccc> ah
<sarang> Each test is set up by a non-timed init()
<sarang> and then timed for test()
<knaccc> makes perfect sense
<sarang> If you build yourself, just run ./performance\_tests --stats --filter=\\*view\_tag\\*
<sarang> the true/false flags correspond to the bools in the test definition
<sarang> Oh, the byte conversions would need to be accounted for
<sarang> They're not huge, but not negligible either
<sarang> I tend to ignore those during back-of-envelope estimates
<sarang> Anyway, that's the stuff I wanted to present here
<sarang> Are there other questions?
<knaccc> code looks good to me
<sarang> OK, does anyone else wish to present any research of interest?
<sarang> knaccc: cool
<Isthmus> Hmmm, I started wondering about something this morning...
<Isthmus> Over the last several years, I’ve had to nix a ton of cool software ideas because repeated 3-output transactions are heuristically linkable, and alternative business models (subscriptions, accounts, etc) have tons of downsides and privacy concessions compared to adding a small service fee to each operation.
<Isthmus> Now I’m wondering if this is stifling Monero adoption and integration by preventing the most straightforward and private method for compensating the developers who want to contribute new stuff to the ecosystem.
<Isthmus> If we want Monero to be used for more than point-to-point transactions, without putting the first adopters at statistical risk, there may be some pros to a 3-output minimum: recipient + change + optional service fee.
<Isthmus> Of course, for many transactions the third output will be an empty dummy. (Or people could get creative and split the return across 2 change addresses for latter flexibility, etc)
<sarang> Ah, increasing the enforced minimum to 3?
<Isthmus> It might make sense to bundle this in with bigger rings, since the ratio of (# outputs) / (# ring signatures) per unit time shouldn’t get too large (since outputs that haven’t ever shown up in a ring signature yet have a known spend state [unspent], and inforrms [with provable certainty] the sender that funds weren’t subsequently moved).
<Isthmus> @sarang yep
<sarang> Splitting change means more likely to pull in multiple change outputs in later transactions
<sarang> which is bad for linking
<sarang> Downside is chain bloat
<Isthmus> Yeah, that's why I've always advocated against people splitting up within their wallet
<ArticMine> What is the additional size per tx?
<Isthmus> 0.22 kB
<Isthmus> I think
<Isthmus> oh wait
<sarang> that seems too big
<Isthmus> That number isn't right
<Isthmus> hold on a sec
<ArticMine> If we go to 4?
<sarang> ArticMine: why 4?
<ArticMine> Is there not efficiency bullet proofs?
<ArticMine> with 4 vs 3 outputs that had to be padded
<sarang> BP padding doesn't imply extra outputs
<Isthmus> Now I'm getting pulled into a side adventure on xmrchain that I can't find any 1/3/e txns but there are lots of 1/3/s (trying to figure out what that means)
<sarang> it's merely an algebra thing
<sarang> ArticMine: it would mean that the corresponding bulletproof is a bit bigger for standard transactions
<sarang> if that's what you meant?
<ArticMine> Yes
<sarang> Ah, a 3-out BP (padded to 4) is 64 bytes larger than a 2-out BP
<sarang> (a 4-out BP is the same size as a 3-out BP)
<ArticMine> That is y point
<ArticMine> my
<sarang> got it
<sarang> Yes, you are correct that this would increase the typical range proof size
<Isthmus> Yep, it makes Monero usable for more applications and businesses, but does increase the transaction size
<Isthmus> Hm, little easter egg:
<Isthmus> There are essentially no 1-in-3-out txns with encrypted PIDs
<Isthmus> There are a few 1-in-3-out transactions with no PID at all
<Isthmus> And a few 1-in-3-out with some unusual tag in xmrchain, not sure what's in tx_extra
<jwinterm> I guess that would make sense considering any PID tx is probably from user to exchange/service, so would likely just be one in two out
<Isthmus> Ugh, stands out as non-standard software
<Isthmus> I feel like we sometimes make things worse when we add a feature "to all transactions" in the wallet, but not the protocol :- (
<sarang> aye
<ArticMine> So is there additional bloat over the 64 bytes?
<sarang> The new output has a pubkey, a commitment, an encrypted amount...
<sarang> those three are 72 bytes total
<ArticMine> and 4
<sarang> 73 bytes if you add a view tag
<sarang> add another pubkey, commitment, amount, view tag for each output you want
<ArticMine> so 82 vs 73 bytes for 4 over 3
<sarang> No
<sarang> In addition to a possible marginal range proof increase, each additional output requires 73 more bytes for pubkey, commitment, hidden amount, [optional view tag]
<sarang> The marginal range proof increase from 2 -> {3 or 4} is another 64 bytes
<ArticMine> So for 3 it is 137 bytes
<sarang> sounds about right
<sarang> This also implies increased scanning time (reduced by view tags)
<ArticMine> and for 4 210 bytes
<sarang> and additional scanning time
<ArticMine> Yes
<sarang> Anyway, in the interest of time, were there other topics that needed to be brought up?
<sarang> (We can always continue discussions afterward)
<knaccc> btw i'd be interested to know some examples of great use-cases for 3-out txs
<knaccc> either now or after
<sarang> Service fees are a big one
<sarang> One output goes to the recipient, one to change, one to service provider
<ArticMine> VAT / GST?
<knaccc> sarang can you be more specific about the service? just one example of something that could be common?
<knaccc> ArticMine you're suggesting paying VAT direct to the gov as part of a tx?
<sarang> knaccc: maybe you're using some kind of hosted wallet service
<sarang> Or maybe your wallet software has an option to donate a small amount to charity with each txn
<knaccc> oh right, fine yes, gotcha.
<sarang> OK, let's finish up with ACTION ITEMS if there aren't any other topics to bring up
<sarang> If/when Windows CI gets fixed up, I'll rebase some new work for PR/review
<sarang> and get Triptych and Arcturus sent off to PoPETs
<sarang> and hopefully be able to reproduce some of the results from that tracing preprint
<moneromooo> Micropayments in every tx is a great way to punch monero into the ground. We don't want to have huge amounts of dust outputs, they take up the same resources as "normal" outputs.
<sarang> moneromooo: that's what I meant by chain bloat and scan increases
<knaccc> service-fee is essential for multisig arbitration insurance fee probably
<ArticMine> but I see a slippery slope
<knaccc> eventually i think the default kind of payment tx should be multisig w/arbitration insurance fee attached
<knaccc> and multisig won't be a different type of wallet, it'll be something created on-the-fly on each payment tx
<sarang> OK, I suppose we can formally adjourn (so I can post logs), but discussion can of course continue
<sarang> Thanks to everyone for attending!
<knaccc> ^^
