-
UkoeHB_
-
knaccc
sarang the question over Hs(128 bits) as a private key is essentially what I was asking Pieter Wuille about here:
bitcoin.stackexchange.com/questions…-bitcoin-wallets-only-use-a-128-bit
-
knaccc
when I pushed him to clarify in the comments, he said: "I guess the answer is defense in depth: less than 128 bits of entropy definitely hurts security. Less than 256 bits may hurt. More than 512 bits can't help"
-
knaccc
so it's all about the "may"
-
knaccc
UkoeHB_ nice idea with the hidden txprivkey
-
knaccc
how do you handle >=3 out txs? a dummy txpubkey, and then you use your own hidden txpubkey instead?
-
knaccc
it would seem cleaner to go back to the idea of using a symmetric key and no DH for the change output
-
knaccc
so change output one-time key = Hs(a||key_image)G+B or something like that
-
knaccc
or change output one-time pubkey = Hs(a || lexicographically sorted key_images)G+B so only one mult with G req'd per tx, although that limits you to one change output per tx
-
knaccc
oh wait i keep forgetting about view tags. so yeah you could just do Hs(a||key_image)G+B
-
knaccc
it sits well with me philosophically that DH is only for establishing keys with strangers, and symmetric keys are for talking to yourself
-
knaccc
and i'd argue that what i've just written is much cleaner from an implementation perspective than hidden txpubkeys based on encrypted txprivkeys on other outputs
-
knaccc
and it also means there is no janus issue on change outputs
-
sgp_
sarang: did you send the response for the alt-coin paper?
-
knaccc
i've also kept thinking about the consequences of a compromised shared secret. no funds can be stolen if it is. and if it ever becomes possible to compromise it, then most bitcoin wallets are also compromised because they use seeds with 128 bits of entropy. so i'd vote for 128-bit tx private keys
-
knaccc
but it's not a strong vote. it hangs somewhat in the balance
-
-
kenshamir[m]
I guess it also depends on what the hash function is as well; if it’s quite new then the extra padded security would likely be something I’d add.
-
kenshamir[m]
^ Also not an expert in hash functions haha
-
sarang
sgp_: yes
-
knaccc
kenshamir interesting, thanks for your thoughts. i must imagine that a lot of people have thought a lot about this, given that bitcoin wallets have 128-bit private keys
-
knaccc
it's easy to say "more is better", but there must have serious thought with bitcoin.
-
knaccc
must have been*
-
kenshamir[m]
<knaccc "it's easy to say "more is better"> Yep I agree, if you find out the exact reason, I would be really interested to hear why also
-
sarang
Interesting knaccc
-
knaccc
one interesting article (what was about AES256, not EC) is this
blog.1password.com/guess-why-were-moving-to-256-bit-aes-keys where they cite 2 reasons for moving to 256 keys as "NSA insists that TOP SECRET material be encrypted using 256-bit keys" "for defense against quantum computing"
-
sarang
o_0
-
knaccc
an argument for 256-bit keys with Monero would be that if quantum computing advancements do start to make 128-bit bitcoin seeds look shaky, then people can easily move their BTC funds to a new 256-bit seed wallet with plenty of warning. but loss of privacy in Monero is forever
-
cjd
I think that monero relies on enough DL math that quantum computers are just catastrophic, at 128 or 256 bits
-
cjd
But someone feel free to correct me if I'm wrong
-
knaccc
heh all EC crypto is dead in 10 years. let's disband and enjoy the summer :)
-
sgp_
Is there an easy way to scrape all BTC peg-in and peg-out addresses for Liquid? I want to see the histories of coins that people are pegging in
-
sarang
^ Isthmus etc.
-
sgp_
I wonder if it will act like a rebranded mixer
-
Isthmus
Potentially, what do the pegging transactions look like? If they have a distinguishing characteristics that can be searched for in BigQuery, then it should be pretty easy
-
Isthmus
And yea, to echo knaccc, you can play the escalating key size game if your only concern is *security*, but that approach is paradigmatically wrong for *privacy* given retroactive deanonymization
-
sarang
FYI UkoeHB_: I have timing numbers for view tags :D
-
sarang
also knaccc ^
-
sarang
Meeting here at 17:00 UTC
-
sarang
.time
-
monerobux
2020-05-27 - 16:27:28
-
sarang
about half an hour from now
-
sarang
good bot
-
knaccc
view tags are just so good. wish i'd thought of that.
-
sarang
Wasn't there a similar-in-spirit idea for such a scan speedup a long while ago? I don't really remember
-
sarang
Anyway, I'll share the numbers at the meeting
-
sarang
The only real downside is that sending wallets don't have to include them honestly
-
sarang
so you could trick a recipient into missing the output on a fast scan
-
sarang
But that seems to be a "just want to watch the world burn" kind of thing
-
knaccc
can you envision a scenario where that could actually be used to burn anyone?
-
knaccc
i guess it's a way of concealing incoming funds from an auditor
-
sarang
Well, presumably an auditor with a view key would do a full scan
-
sarang
So the way the idea of fast scanning is presented would need to be carefully considered
-
Isthmus
" Wasn't there a similar-in-spirit idea for such a scan speedup a long while ago? I don't really remember" < I had some silly idea for partial stealth address collisions for this purpose a while ago
-
Isthmus
But it's not something I would seriously suggest implementing
-
knaccc
heh i still kinda like the idea of brute-forcing the choice of tx private key until the last 8 bits of the txpubkey are the same as the necessary view tag :)
-
Isthmus
^^
-
knaccc
it's not actually that absurd an idea
-
knaccc
given how many EC ops the brute force would take in context with all of the other EC ops being done to create a tx or scan the blockchain
-
sarang
Eh, wait until you see the view key speed up numbers
-
sarang
Maybe you'll think "meh, good enough already..."
-
knaccc
heh i'm on the edge of my seat :)
-
sarang
OK, it's time for the meeting!
-
sarang
As usual, begin with GREETINGS
-
Isthmus
GREETINGS
-
ArticMine
Hi
-
sarang
hello
-
» sarang will wait a couple of minutes for others
-
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:
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
-
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?
-
» binaryFate taking chair at the back of the room
-
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
-
» Isthmus is referring to data from the last week
-
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
^^
-
sarang
-
sarang
This is a plot of the average scan time per output as a function of tag size (assuming large numbers of outputs scanned)
-
sarang
^ UkoeHB_
-
sarang
Oh, the x-units are bytes (not bits)
-
sarang
-
sarang
Even a very small tag (like 8 bits) gives essentially optimal results
-
knaccc
makes perfect sense
-
knaccc
it'd be really interesting to know how view tags affect overall wallet scan times
-
knaccc
since there will be overhead in other areas that aren't captured in your test
-
sarang
I was surprised how quickly the average time drops
-
sarang
I figured it would take more than just a few bits to see so much of the total possible improvement
-
knaccc
why?
-
sarang
No particular reason; just a poor initial guess, I suppose
-
knaccc
it's like shaving seconds off the distance you park your car from your front door after a long journey
-
knaccc
heh you're a genius mathematician, i'm guessing you were just distracted at the time :)
-
sarang
I'm no genius
-
sarang
!
-
sarang
So as an example
-
knaccc
yeah tell it to the white papers you demolish.
-
sarang
Say we have 6 million view tags
-
sarang
reducing from 8 bits to 4 bits is only 3 MB
-
sarang
so such changes are pretty trivial
-
knaccc
yeah it's an awesome realization
-
sarang
At any rate, it tells us that anything over a byte is absolute overkill
-
sarang
And anything under a byte saves you basically nothing in terms of long-term size
-
knaccc
it just be child's play to you to have known the savings would have a logarthimic dropoff
-
sarang
Well, the constants are what really tell you where the benefits become only marginal
-
sarang
It's nice to have data to give real numbers for it
-
knaccc
yeah
-
sarang
and those constants depend entirely on the relative timing between operations
-
sarang
But hey, that's what performance tests are for
-
knaccc
one perf test we never did when we discovered multbase was .15 and multvarbase was .25 was what the frombytesvartime is
-
knaccc
that might be the reason for the discrepancy between 62.5% and 75%
-
sarang
Relying on scaling estimates only gets you so far!
-
sarang
Relying on scaling estimates only gets you so far!
-
sarang
Yeah, byte conversions are easy to miss
-
sarang
Especially when looking at things like large-anon-set tx protocols where you need to do a lot of them
-
sarang
Fortunately a fair number of recent speedups come from removing unnecessary conversions
-
UkoeHB_
Increasing number of outputs also implies more Janus bytes, currently 32 per output if implemented
-
sarang
yep
-
UkoeHB_
I was hoping for around 50% speed up lol, but this is why real analysis is great. Thanks sarang :)
-
sarang
Added the plot to the GitHub issue(s) as well
-
UkoeHB_
I'm a bit hesitant to start enforcing behaviors that aren't already ubiquitous. We enforced 2-out tx since 1-outs were super rare. We enforce 10-block lock time since sub-10 was super rare. Starting to enforce 3-out or 4-out in the name of features that don't even exist yet, and whose prevalence we can't evaluate, seems risky.
-
sarang
Well, in this case it's not so much existing ubiquity as a hesitance for responsible services to start doing this because of the obvious uniformity challenges
-
sarang
I'm also not a fan of this, given the cost
-
UkoeHB_
Btw knaccc I agree with you about multisig arbitration fees. That seems the most reliable mechanism to power an escrow service, with minimized conflict of interest.
-
knaccc
the only problem with escrow is that the escrow services will probably rely on qualitative reputation
-
UkoeHB_
The accumulation of bloat is unfortunate but I don't see a good alternative atm
-
knaccc
and so lead to centralization
-
UkoeHB_
That isn't really a problem for me since as long as they are providing a quality service then customers aren't affected. And competition is fairly trivial
-
UkoeHB_
Plus if designed well then an escrow service won't learn much about transactions being made, other than ones they arbitrate
-
knaccc
i'm thinking more along the lines of a centralized service that needs to inspect evidence of shipping/etc
-
knaccc
one big player with access to sensitive information
-
knaccc
yeah it's the arbitrated cases i'd worry about centralization for
-
knaccc
and what a great way to unmask a vendor. compromise the arbitrator, cause the delivery to fail, vendor provides privacy-sensitive info to the arbitraror
-
knaccc
arbitrator*
-
unseddd[m]
how are atomic-swap dexes handling arbitration (is there any)?
-
knaccc
the point of real atomic-swap is that no arbitrator is required
-
sarang
The "atomic" part, eh? :D
-
UkoeHB_
Yeah I think using escrow in the first place implies such risks. Can't really involve a third party without.. involving them :p
-
unseddd[m]
right, seems the best solution
-
unseddd[m]
:)
-
unseddd[m]
atomic-swaps seem the best solution* for exchanges still requiring arbitration, sounds like a hard problem to solve
-
unseddd[m]
maybe something like Bisq using an internal currency to deal with arbitration, or some other way to break the links between addresses involved in trades
-
sunnuc[m]
how realistic is it for something like this to come
monero-project/monero-gui #2925
-
UkoeHB_
knaccc re: change outputs and >2-out tx. Since we'd already be including tx pub keys for each output it seems straightforward to treat change outs like normal outs. In the first place 2-out tx would be a 'special case' with a special logic branch. Trying to also have change outs in >2-out tx be special invites more logic branches imo.
-
UkoeHB_
sunnuc[m]: maybe try #monero-gui channel
-
sunnuc[m]
ty
-
knaccc
i was weighing the special branches for a symmetric shared secret with the special branches of alternate shared secrets based on encrypted txprivkeys for other outputs
-
knaccc
or for that output
-
UkoeHB_
I think it's a lot easier to identify and keep track of change outs in 2-out tx since you just say 'if 2-out, generate and store the hidden tx pub key'. And the rest of the code base remains unchanged.
-
UkoeHB_
Or actually, I'm not really sure what wallets store..
-
UkoeHB_
Ah I believe 2-out tx may get a bigger reduction in scan times from view tags, since they only (in practice) have 1 tx pub key so you normally only compute `generate_key_derivation()` once, then the `if (is_owned)` stuff twice for each output. If current reduction is to 75%, then 75/(100+25) = 60%. Tx with >2 outputs are only 5% of current tx, so aren't too meaningful for this granularity of analysis.
-
sarang
Hooray, got the tracing preprint's code to run
-
sarang
Now to wait for... a long time
-
UkoeHB_
Of course, as Monero changes and grows tx with >2-outs may begin to dominate, so it's good to keep that scenario in mind
-
UkoeHB_
It sounded like their code might be pretty useful
-
sarang
It's just very time-consuming for it to pull all the chain data into formats it likes
-
sarang
Fortunately, I can fake-parallelize parts of it by running multiple instances on different block ranges
-
sarang
What I really want is to get specific information on tracing they identified
-
sarang
Their datasets use git lfs, but github complained they used up their data quota
-
UkoeHB_
My guess is they were referring to pre-ringct output spends
-
sarang
and FWIW it's probably best to run the data myself as a separate check
-
sarang
UkoeHB_: that is also my guess, but it'll be nice to verify
-
UkoeHB_
To test the spend distribution they should have generated a fake database where each ring is selected from the gamma with no real spends, then quantized the two db (real and fake) and subtracted them. Oh well
-
sarang
oh well indeed
-
sarang
I did point out that flaw in their analysis in my email to them, should they choose to revise
-
UkoeHB_
the semester is already over, so maybe they have moved on
-
sarang
Could be; but hopefully the information is useful should they do similar research in the future
-
sarang
I was disappointed they didn't have tooling to handle Zcash Sapling transactions, which would have been fascinating to see results on