05:00:16 <Mumuks> Breaking RSA with a Quantum Computer
05:00:17 <Mumuks> A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.
05:00:17 <Mumuks> https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html
13:24:30 <narodnik> https://eprint.iacr.org/2022/1763.pdf
13:24:48 <narodnik> https://github.com/geometryresearch/cq
15:46:23 <UkoeHB> Meeting 1.25hr
16:59:06 <one-horse-wagon[> Hello.
17:00:01 <UkoeHB> meeting time https://github.com/monero-project/meta/issues/776
17:00:02 <UkoeHB> 1. greetings
17:00:02 <UkoeHB> hello
17:00:23 <rbrunner> Hi
17:00:24 <Rucknium[m]> Hi
17:00:42 <vtnerd> hi
17:01:33 <tevador> Hi
17:03:04 <UkoeHB> 2. updates, what's everyone working on?
17:04:10 <UkoeHB> me: continued cleanup/review of the seraphis lib. I am at least 2/3 done, and finding plenty of things to tweak, optimize, and generally clean up. I also reviewed tevador's updates to the jamtis spec, and his new URI spec (both looking good to me).
17:04:32 <Rucknium[m]> More data analysis of p2pool outputs. Also looking at tx confirmation latency. And writing responses to isthmus's comments on OSPEAD.
17:04:52 <tevador> I've been working on Jamtis URI schemes: https://gist.github.com/tevador/500d5d32d5ecc73b56997e12a9d2b20e
17:05:42 <vtnerd> not much to report again :/ there is a c version of bp++ for reference that will definitely help. otherwise its been doing stuff on other projects or vaca time
17:05:59 <UkoeHB> also @vtnerd all the seraphis PRs have been updated based on your comments if you want to review again :)
17:06:31 <vtnerd> yeah will circle back through that list again
17:06:37 <UkoeHB> thanks
17:06:49 <tevador> vtnerd: where can I find the C code?
17:06:59 <one-horse-wagon[> vtnerd: Do you have a reference for that C version?
17:07:17 <vtnerd> https://github.com/ElementsProject/secp256k1-zkp/pull/207/files
17:07:52 <one-horse-wagon[> Thanks
17:08:00 <vtnerd> its written for a different crypto lib so it cant be used directly, but rough numbers can be used and compared against bp (I think)
17:08:14 <UkoeHB> it's a pretty huge diff for a proof, BP and BP+ are only 1k lines
17:08:20 <tevador> Thanks. Much more readable than haskell.
17:08:50 <isthmus> I've just been working on a project to analyze rings that differ by only one ring member https://github.com/Mitchellpkt/ringxor
17:08:50 <isthmus> That implementation runs in ~O(N^2) and based on benchmarks this will take about a month to exhaustively check ring pairs. However, I have a ~O(N) solution in mind which will probably bring it down to sub-day on a decent machine.
17:08:50 <isthmus> h/t @rucknium shared a transaction with me that kicked this whole thing off, @neptune is going to help with the data, and @gingeropolous has been helping me get set up on research infra
17:09:35 <UkoeHB> I guess this one is 1k lines src/modules/bulletproofs/bulletproofs_pp_rangeproof_impl.h
17:10:50 <UkoeHB> 3. discussion
17:13:11 <UkoeHB> anything to discuss today?
17:13:51 <Rucknium[m]> I have number on the bytes added by p2pool coinbase txs. Over Oct-Dec the p2pool coinbases added 23 MB. That's 0.53% of the total bytes added to the blockchain over that period. p2pool found about 7% of blocks.
17:14:25 <UkoeHB> makes sense
17:14:47 <Rucknium[m]> p2pool miners would generally have to consolidate the payouts before making them spendable. That would cause X bytes to be added for each ring signature.
17:15:07 <Rucknium[m]> X is...something that someone could tell me
17:16:01 <tevador> Nowadays, every tx input has 2-3 p2pool decoys, which stick out like a sore thumb.
17:16:34 <UkoeHB> should be 640 bytes per input
17:17:26 <rbrunner> Would it be possible to get a rough estimate how much those consolidations will add to the blockchain?
17:17:36 <rbrunner> They seem to be much, much heaver at first sight.
17:17:58 <Rucknium[m]> IMHO, it would make sense to implement a no-coinbase decoy selection algorithm at the same time as (hopefully) the new decoy selection algorithm from OSPEAD is implemented. For implementation simplicity and so not to cause so many "anonymity puddles" in the ring member distributions.
17:19:13 <Rucknium[m]> rbrunner: Yes. Best way would be to just multiply the number of outputs in each p2pool coinbase tx (which I already have) by 640 bytes. That would be missing the weight of the output side, but that may be ok as  a good approximation
17:19:15 <UkoeHB> with seraphis binned ref sets you need to select from a contiguous integer range, you'd need to segregate coinbase from normal enotes
17:20:51 <rbrunner> With this idea, you would spend coinbase enotes with rings that only consist of coinbase stuff?
17:21:13 <rbrunner> with "a no-coinbase decoy selection algorithm"
17:21:17 <UkoeHB> you could implement a coinbase consolidation tx type that only allows coinbase inputs without ring signatures and only range proofs on outputs
17:21:52 <rbrunner> Yes, somehow you must be able to spend coinbase enotes :)
17:22:19 <UkoeHB> coinbase ownership is largely public information, so consolidating without ring signatures wouldn't necessarily be terrible
17:23:08 <ghostway[m]> <isthmus> "That implementation runs in ~O(N..." <- That's quite interesting. Can you elaborate if that's okay?
17:23:13 <Rucknium[m]> With quick calculations, I am getting 373,068,160 bytes from just the inputs/ring sigs on consolidation txs. p2pool had 582,919 payout outputs during this period.
17:24:21 <tevador> Coinbase consolidations without ring signatures sounds like a reasonable solution.
17:25:20 <isthmus> Sure @ghostway[m] happy to elaborate, here's what I have in mind:
17:25:20 <isthmus> I was thinking of it like this: Each output on the chain is a letter. Each ring signature is a word, with the letters [outputs] in chronological order (“ACBDE” –> “ABCDE”).
17:25:20 <isthmus> We eat the cost once to sort the list of words (rings) lexicographically. Then you make two fast passes over it, one where you compare each ring that starts with the same letter, and then a second pass where you compare against every ring whose first letter is my second letter.
17:25:20 <isthmus> In other words, Let l_{i,j} be the jth letter of the ith word. The "first letter" pass only compares words x and y if L_{x, 0} = L_{y, 0}. And the “second letter” pass only compares words x and y if L_{x, 0} = L_{y, 1}. Because we’re looking specifically for “differ by one” rings, you don’t need to make any further passes! I think this is kind of a pigeonhole principle thing.
17:25:20 <isthmus> And the reason this doesn’t subtly become O(N^2) for checks in the passes is because of the initial lexicographical sort (arguably the real magic here). If you’ve got the dictionary open to words that start with F and you want to check against other words that start with F, you already know where they are! You only need to thumb pages until you hit a word starting with an E or a G.
17:25:42 <rbrunner> According to this total blockchain growth in those 3 months was between 4 and 5 Gigabytes: https://localmonero.co/blocks/stats/blockchain-growth
17:25:46 <Rucknium[m]> Combining that with the 23 MB from the p2pool coinbase txs, that's 9.2% of all bytes added to the blockchain during this period.
17:26:15 <rbrunner> Right. 10% only to "digest" those enotes. Hmmm.
17:26:16 <Rucknium[m]> rbrunner: I have 4,302,893,381 bytes in my data
17:26:31 <UkoeHB> sgp_: iirc you have been advocating about coinbase enote issues for years
17:26:44 <ofrnxmr[m]> https://github.com/monero-project/monero/issues/6688#issuecomment-1190753103
17:26:46 <UkoeHB> sgp[
17:26:55 <UkoeHB> sgp[m]:  ^
17:27:02 <ofrnxmr[m]> sgp: 
17:27:44 <gingeropolous> would this be wallet or consensus enforcement?
17:27:55 <sech1> Coinbase consolidations without ring signatures will also help reduce fees for consolidations which is a problem for small miners
17:28:14 <ghostway[m]> Cool trick isthmus,, had to guess that it's about ordering :)
17:28:26 <tevador> that github comment neglects the fact that real p2pool spends are easily recognized in practice
17:28:53 <ofrnxmr[m]> Agreed
17:28:57 <rbrunner> But the problem may come back with the binned approach of Seraphis, if we are not careful, do I understand that correctly?
17:29:05 <Rucknium[m]> gingeropolous: Changes to decoy selection could happen at the wallet level. Changes to allow coinbase outputs to avoid ring sigs would require consensus changes (hard fork) AFAIK.
17:29:09 <isthmus> ty ghostway[m] ^_^
17:29:54 <UkoeHB> rbrunner: no, if you want coinbase consolidations then coinbase enotes should be completely segregated from normal enotes (only spendable by consolidating)
17:30:22 <tevador> lower p2pool consolidation fees would be a big plus for mining decentralization
17:31:01 <Rucknium[m]> Right. It would also decrease the tx fee that p2pool miners pay for consolidations :)
17:31:08 <ghostway[m]> isthmus: I thought you had to compare it as a set of the people in the ring though?
17:32:48 <rbrunner> "with seraphis binned ref sets you need to select from a contiguous integer range": So you number the two types of enotes independently, somehow?
17:33:05 <UkoeHB> yes, just dump them into two different lists
17:34:11 <rbrunner> That could possibly have some repercussions in the codebase ... but yeah.
17:34:36 <UkoeHB> yeah it causes some wallet-side headaches especially
17:34:57 <UkoeHB> because there is a segregated balance
17:35:04 <isthmus> Yep, @ghostway[m] when it "compares words x and y" in the analogy that corresponds to taking two different rings and comparing their ring members, to see if they overlap by all but one ring member (in which case it gets marked as a DBO ring pair, otherwise it moves on to the next two rings to compare)
17:35:30 <isthmus> s/DBO/"differ-by-one"
17:35:43 <ghostway[m]> That doesn't sound O(N) though...
17:35:48 <rbrunner> So would probably good to know early if we really start to march into this direction with Monero transactions
17:36:25 <UkoeHB> ghostway[m]: it should be O(kN)
17:36:35 <rbrunner> We probably should, wishing for p2pool becoming the largest pool.
17:36:42 <ghostway[m]> Sure, ok
17:37:38 <rbrunner> Will probably be the horror to put this into `wallet2` still.
17:38:01 <UkoeHB> rbrunner: probably better to wait until seraphis
17:38:32 <ghostway[m]> So maybe wallet3 specification should be there (and also wait for seraphis)
17:38:34 <UkoeHB> it's also easier with seraphis because membership proofs are separate from ownership proofs
17:38:34 <ghostway[m]> Yea koe said it
17:40:11 <rbrunner> Well, yes, dev time going into this with the "old" codebase would probably delay Seraphis
17:40:13 <Rucknium[m]> rbrunner: I pretty much agree. If nothing is done, then either we believe that p2pool has little chance of getting larger or that we don't care much about effective ring size shrinking.
17:40:14 <Rucknium[m]> Decoy selection for non-mining users can be changed before Seraphis. Doesn't require a hard fork.
17:41:34 <Rucknium[m]> Is it hard to exclude coinbase outputs in the old codebase? There is no binning, so you can avoid those issues.
17:41:45 <rbrunner> And what then for miners? I am a bit confused
17:42:34 <isthmus> Haha yea +1 @UkoeHB O(kN) better notation than "2 ~O(N) passes". Though to be thorough it is true that *within a given letter* if there are F words starting with the letter 'f' we have to make (F^2-F)/2 checks. It's just that there's a huge number of letters (66921481 at time of writing) and only a handful of words starting with each letter, so those go by very quickly and zooming out it's effectively O(kN)
17:42:35 <Rucknium[m]> They don't select coinbase outputs as decoys either. They use the coinbase outputs as the real spend :D
17:42:58 <Rucknium[m]> So coinbase consolidations would be even more obvious than they are now.
17:43:02 <rbrunner> Ah, ok.
17:43:02 <moneromoooo> Hard now than coinbases have more than one output. Otherwise, not hard.
17:44:12 <rbrunner> So that's no contribution against any size saving, just the "nonsense" decoys get avoided, right?
17:44:41 <Rucknium[m]> Right. To address the privacy issue
17:44:52 <rbrunner> Ok. I think now I get it.
17:45:26 <rbrunner> But now the rings that do have coinbase enotes become somewhat nonsensical :)
17:45:45 <moneromoooo> Actually, probably not too hard, since the node can tell wihch outputs are locked, so it probably has access to the amount, and can thus see which outs are coinbases. 
17:46:14 <sgp[m]> <UkoeHB> "sgp_ (New Account: @sgp:..." <- https://medium.com/@JEhrenhofer/lets-stop-using-coinbase-outputs-da672ca75d43
17:50:01 <rbrunner> Well, and now, any volunteers to code that ... :)
17:50:15 <UkoeHB> ok made an MRL issue for comments https://github.com/monero-project/research-lab/issues/108
17:50:30 <sgp[m]> Initially the focus was that the behavior of users never conceivably spent coinbase outputs, but that's no longer the case. "Normal" people (not just pools) now spend them. It may be tempting to sever these coinbase outputs from the normal decoy set if they grow large, but the benefits are less clear to me
17:50:36 <UkoeHB> I will let it marinate for 1-2 weeks then implement it in the seraphis lib if there seems to be consensus
17:50:37 <sgp[m]> Thanks UkoeHB , will review
17:51:08 <rbrunner> I guess it's less than trivial to put that into the library, for some newcomers?
17:51:19 <rbrunner> *more
17:51:34 <UkoeHB> adding coinbase tx type only took around 15hrs I think, this may take a bit more due to balance segregation
17:51:46 <rbrunner> For you as the author.
17:52:09 <isthmus> Can they use the current decoy selection algorithm code and reroll on coinbase enotes? Or does that introduce second order effects?
17:52:10 <UkoeHB> yes a newcomer would take quite a while, since you need to learn how the library is put together
17:52:36 <isthmus> Ah I think there is a second order effect if the ratio of normal enotes to coinbase enotes is not a constant. And I would NOT assume it to be constant. 
17:52:50 <isthmus> 🤔
17:53:14 <isthmus> (it'd be OK to re-roll the whole ring. I just mean you can't throw out and re-roll one output)
17:53:23 <sgp[m]> isthmus: shouldn't be constant since p2pool is a minority of blocks
17:53:36 * isthmus nods
17:53:51 <isthmus> Yea that's probably not the right approach then
17:54:00 * isthmus walks back the suggestion
17:57:06 <UkoeHB> ok we are approaching the end of the hour, are there any final comments or questions to address?
17:59:30 <UkoeHB> I'll call it here, thanks for attending everyone
18:03:14 <Rucknium[m]> <UkoeHB> "ok made an MRL issue for..." <- Should this issue also be used for discussion of non-miner decoy selection? They are separate but closely related issues.
18:05:06 <UkoeHB> Rucknium[m]: I think you should make a new issue for that
18:07:08 <Rucknium[m]> Ok
18:18:18 <sgp[m]> Added https://github.com/monero-project/research-lab/issues/108#issuecomment-1371265587
18:18:38 <sgp[m]> one of the most interesting things that I like to think about is what to do with the coinbase ring :)
18:24:43 <monerobull[m]1> Remove it
18:24:55 <sgp[m]> imposing granular restrictions on spends of coinbase outputs whether the transaction has 3+ outputs or not could further improve things for p2pool miners with no harm to public pools, and minimal cost to the network
18:24:59 <monerobull[m]1> Are there any downsides to excluding Coinbase from rings?
18:25:27 <sgp[m]> downsides are 1) forcing a churn, and 2) implementation complexity
18:29:13 <UkoeHB> sgp[m]: it would be better not to add protocol rules in response to particular use-cases like p2pool; the goal is generic solutions
18:29:40 <UkoeHB> p2pool only highlights a weakness of the current approach
19:40:22 <xmrack[m]> sgp: I like the idea of incentivizing p2pool. But wouldnt adding a protocol rule such as 3+ outputs be easily bypassed by pools. Couldnt they just use 4 outputs to a bunch of subaddresses?
19:58:13 <sgp[m]> xmrack: yeah but it'll cost them more money so why would they do it
19:59:44 <sgp[m]> the only reason I can think of is for the sake of being malicious. which of course they can do, no way around that. this is a (theoretical at least) option for separating p2pool activity from typical mining pools for a potential benefit
20:19:04 <rbrunner> Maybe stupid idea, but who knows: Is it possible to construct a transaction that spends ALL 16 enotes in its ring AND that passes current consensus rules and checks?
20:19:32 <rbrunner> If that's possible people could consolidate their coinbase enotes in batches of 16 ...
20:20:09 <rbrunner> (current consensus so no need for a hardfork)
20:22:12 <nikg83[m]> rbrunner: It’s possible to spend 2 inputs in same ring ? 
20:22:55 <rbrunner> I guess not, but I think asking the people in the know can't do harm, because if it's possible it would help I think
20:23:52 <rbrunner> Optimistically seen many a good idea started with a pretty dumb question :)
20:24:40 <Rucknium[m]> Issue for "Avoid selecting coinbase outputs as decoys": https://github.com/monero-project/research-lab/issues/109
20:30:11 <UkoeHB> rbrunner: I guess, but what's the point?
20:31:00 <rbrunner> Saving fees, and saving blockchain space, if people who mine a lot have an easier way to consolidate, in batches of 16 coinbase enotes
20:31:41 <rbrunner> Or maybe not the full 16, but a ring with 12 normal enotes and 4 coinbase enotes where all 4 coinbase enotes get spent, with that single ring.
20:32:48 <rbrunner> All within current consensus of course, because if we need a hardfork, we can do it "properly" of course
21:47:36 <tevador> That would not actually save anything. Current consensus would still require 16 (useless) ring signatures.