Breaking RSA with a Quantum Computer

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.

Meeting 1.25hr

Hello.

meeting time monero-project/meta #776

1. greetings

hello

Hi

Hi

hi

Hi

2. updates, what's everyone working on?

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).

More data analysis of p2pool outputs. Also looking at tx confirmation latency. And writing responses to isthmus's comments on OSPEAD.

I've been working on Jamtis URI schemes: gist.github.com/tevador/500d5d32d5ecc73b56997e12a9d2b20e

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

also @vtnerd all the seraphis PRs have been updated based on your comments if you want to review again :)

yeah will circle back through that list again

thanks

vtnerd: where can I find the C code?

vtnerd: Do you have a reference for that C version?

Thanks

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)

it's a pretty huge diff for a proof, BP and BP+ are only 1k lines

Thanks. Much more readable than haskell.

I've just been working on a project to analyze rings that differ by only one ring member github.com/Mitchellpkt/ringxor

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.

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

I guess this one is 1k lines src/modules/bulletproofs/bulletproofs_pp_rangeproof_impl.h

3. discussion

anything to discuss today?

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.

makes sense

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.

X is...something that someone could tell me

Nowadays, every tx input has 2-3 p2pool decoys, which stick out like a sore thumb.

should be 640 bytes per input

Would it be possible to get a rough estimate how much those consolidations will add to the blockchain?

They seem to be much, much heaver at first sight.

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.

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

with seraphis binned ref sets you need to select from a contiguous integer range, you'd need to segregate coinbase from normal enotes

With this idea, you would spend coinbase enotes with rings that only consist of coinbase stuff?

with "a no-coinbase decoy selection algorithm"

you could implement a coinbase consolidation tx type that only allows coinbase inputs without ring signatures and only range proofs on outputs

Yes, somehow you must be able to spend coinbase enotes :)

coinbase ownership is largely public information, so consolidating without ring signatures wouldn't necessarily be terrible

<isthmus> "That implementation runs in ~O(N..." <- That's quite interesting. Can you elaborate if that's okay?

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.

Coinbase consolidations without ring signatures sounds like a reasonable solution.

Sure @ghostway[m] happy to elaborate, here's what I have in mind:

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”).

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.

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.

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.

According to this total blockchain growth in those 3 months was between 4 and 5 Gigabytes: localmonero.co/blocks/stats/blockchain-growth

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.

Right. 10% only to "digest" those enotes. Hmmm.

rbrunner: I have 4,302,893,381 bytes in my data

sgp_: iirc you have been advocating about coinbase enote issues for years

sgp[

sgp[m]: ^

sgp:

would this be wallet or consensus enforcement?

Coinbase consolidations without ring signatures will also help reduce fees for consolidations which is a problem for small miners

Cool trick isthmus,, had to guess that it's about ordering :)

that github comment neglects the fact that real p2pool spends are easily recognized in practice

Agreed

But the problem may come back with the binned approach of Seraphis, if we are not careful, do I understand that correctly?

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.

ty ghostway[m] ^_^

rbrunner: no, if you want coinbase consolidations then coinbase enotes should be completely segregated from normal enotes (only spendable by consolidating)

lower p2pool consolidation fees would be a big plus for mining decentralization

Right. It would also decrease the tx fee that p2pool miners pay for consolidations :)

isthmus: I thought you had to compare it as a set of the people in the ring though?

"with seraphis binned ref sets you need to select from a contiguous integer range": So you number the two types of enotes independently, somehow?

yes, just dump them into two different lists

That could possibly have some repercussions in the codebase ... but yeah.

yeah it causes some wallet-side headaches especially

because there is a segregated balance

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)

s/DBO/"differ-by-one"

That doesn't sound O(N) though...

So would probably good to know early if we really start to march into this direction with Monero transactions

ghostway[m]: it should be O(kN)

We probably should, wishing for p2pool becoming the largest pool.

Sure, ok

Will probably be the horror to put this into `wallet2` still.

rbrunner: probably better to wait until seraphis

So maybe wallet3 specification should be there (and also wait for seraphis)

it's also easier with seraphis because membership proofs are separate from ownership proofs

Yea koe said it

Well, yes, dev time going into this with the "old" codebase would probably delay Seraphis

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.

Decoy selection for non-mining users can be changed before Seraphis. Doesn't require a hard fork.

Is it hard to exclude coinbase outputs in the old codebase? There is no binning, so you can avoid those issues.

And what then for miners? I am a bit confused

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)

They don't select coinbase outputs as decoys either. They use the coinbase outputs as the real spend :D

So coinbase consolidations would be even more obvious than they are now.

Ah, ok.

Hard now than coinbases have more than one output. Otherwise, not hard.

So that's no contribution against any size saving, just the "nonsense" decoys get avoided, right?

Right. To address the privacy issue

Ok. I think now I get it.

But now the rings that do have coinbase enotes become somewhat nonsensical :)

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.

<UkoeHB> "sgp_ (New Account: @sgp:..." <- medium.com/@JEhrenhofer/lets-stop-using-coinbase-outputs-da672ca75d43

Well, and now, any volunteers to code that ... :)

ok made an MRL issue for comments monero-project/research-lab #108

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

I will let it marinate for 1-2 weeks then implement it in the seraphis lib if there seems to be consensus

Thanks UkoeHB , will review

I guess it's less than trivial to put that into the library, for some newcomers?

*more

adding coinbase tx type only took around 15hrs I think, this may take a bit more due to balance segregation

For you as the author.

Can they use the current decoy selection algorithm code and reroll on coinbase enotes? Or does that introduce second order effects?

yes a newcomer would take quite a while, since you need to learn how the library is put together

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.

🤔

(it'd be OK to re-roll the whole ring. I just mean you can't throw out and re-roll one output)

isthmus: shouldn't be constant since p2pool is a minority of blocks

Yea that's probably not the right approach then

ok we are approaching the end of the hour, are there any final comments or questions to address?

I'll call it here, thanks for attending everyone

<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.

Rucknium[m]: I think you should make a new issue for that

Ok

Added monero-project/research-lab #108#issuecomment-1371265587

one of the most interesting things that I like to think about is what to do with the coinbase ring :)

Remove it

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

Are there any downsides to excluding Coinbase from rings?

downsides are 1) forcing a churn, and 2) implementation complexity

sgp[m]: it would be better not to add protocol rules in response to particular use-cases like p2pool; the goal is generic solutions

p2pool only highlights a weakness of the current approach

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?

xmrack: yeah but it'll cost them more money so why would they do it

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

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?

If that's possible people could consolidate their coinbase enotes in batches of 16 ...

(current consensus so no need for a hardfork)

rbrunner: It’s possible to spend 2 inputs in same ring ?

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

Optimistically seen many a good idea started with a pretty dumb question :)

Issue for "Avoid selecting coinbase outputs as decoys": monero-project/research-lab #109

rbrunner: I guess, but what's the point?

Saving fees, and saving blockchain space, if people who mine a lot have an easier way to consolidate, in batches of 16 coinbase enotes

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.

All within current consensus of course, because if we need a hardfork, we can do it "properly" of course

That would not actually save anything. Current consensus would still require 16 (useless) ring signatures.