Wikipedia:Reference desk/Archives/Mathematics/2022 December 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 31

Eliptic curves : how the mimc bug from circomlib was safely exploited in practice ?

Several years ago, there was an unenforced constraint on verification in the cirmcomlib library : a tool for building projects using ZsNarks. The error allowed to forge cryptographic nullifiers/proofs without having a prior commitment.

Tornado Cash, using Groth16 was the most well‑known affected case : the protocol had to be safely exploited in order to avoid loss of funds.

On the blog post, there were : Later, we will release a step by step guide on how to use this exploit to educate interested security professionals.

4 years later, such blog posts still don’t exist. And with the ofac sanctions resulting in contributing to any code related to the project banned to ᴜꜱ citizens or peoples living in the ᴜꜱ, is unlikely to ever exists.

Neverless, instead of potential step by step Zokrates commands, would it be possible to have this question containing the detailed required computations to generate proofs along nullifiers that verify a root despite not having prior commitments to the root hash ? 2A01:E0A:401:A7C0:AD3B:3E05:85A6:E687 (talk) 04:28, 31 December 2022 (UTC)

To even begin to understand the bug, one needs to be able to read circom code. And what are nullifiers? There may a mathematical question hidden in here, but it is cloaked by an impenetrable layer of extramathematical stuff.  --Lambiam 08:15, 31 December 2022 (UTC)

This was the first link. In the groth16 mathematical paper, a nullifier is a non varying number valid for a single commitment, and thus allows to mark a commitment as having been used since mathematical proofs can be negated.

This a computing question but rooted in a deep mathematical/pure cryptographic problem since the hack was done through building fake mathematical proofs that neverless did verify. 2A01:E0A:401:A7C0:C58D:3DC3:C686:22FA (talk) 13:44, 31 December 2022 (UTC)

To understand why the fake proofs were accepted, one needs to understand what the bug means, which I do not. Apparently, the = operator and the <== operator both have meanings in circom, but I don't know circom and am clueless about their semantic difference. For all I know, the effect of the bug may have been that any hash, say 0x000...000, was accepted, for no other reason than that the hash was not checked at all. Then it was just a stupid bug circumventing the required cryptographic computations.  --Lambiam 12:13, 1 January 2023 (UTC)

Please read all the hyperlinks. As I explained, the meaning is explained on the blog post. The meaning difference is about assigning when changing the hash on commitment and assigning and also verifying when checking proofs. In short, it is a plain old school forgotten condition which was added in the code.

And No! It did not accept any hash! It is where deep mathematical knowledge is required as shown by one of the exploit tx https://oko.palkeo.com/0x4f4b7e7ba63a0d836421c4f0447dfedef003dae954b3dddc7d05c412db81fbef. Because a constraint was not checked in the code, it means some specifically crafted hash and mathematical proofs that should had been rejected were accepted, and my point is about understanding how they were computed since they only work for a specific verifying key in order to build them for a different verifying key.

In order to understand the bug, you don t need to understand circom code as the circom code is just for using the plain groth16 algorithm https://eprint.iacr.org/2016/260.pdf through Pedersen hashes which is explained here and here. 2A01:E0A:401:A7C0:DD97:5B64:F0B5:B110 (talk) 12:57, 1 January 2023 (UTC)

I read all the hyperlinks; the one to the blog post on the TornadoCash website merely has, "The fix is simple: instead of using the `=` operator the `<==` operator should be used." That is not an explanation. The exploit page you link to is about as transparent to me as a cuneiform tablet. I still have no idea what the bug is other than that one instance of = should have been <== without knowing how that makes a difference. Therefore I also have no clue how one would exploit the bug, so I give up. Anyone else have an idea?  --Lambiam 15:59, 1 January 2023 (UTC)

I told it to you about the fix, the difference is about assigning when changing the hash on commitment phase and assigning and also verifying when checking proofs on the verification phase. In short, it is a plain old school forgotten condition which was added in the code.

What are all the numbers with distinct digits and no 0 that have more divisors than any smaller number with distinct digits and no 0?

This is a similar question to what I put here, but this time, do not allow numbers containing the digit 0.

https://en.wikipedia.org/wiki/Talk:Highly_composite_number

The smallest highly composite number that contains the digit 0 is 60. The list the same as highly composite numbers for numbers up to 60. After that, the next number is 72, with 12 divisors. From this website, I think the highest number is 769152384, with 768 divisors.

http://www.worldofnumbers.com/ninedig6.htm

Also, please put the line of code you used to compute the full sequence. 66.181.118.116 (talk) 21:20, 31 December 2022 (UTC)

I haven't tried this, but I guess the following modified version of the PARI/GP code should do the job:

r=0;for(n=1,10^9,if((!setsearch(vecsort(digits(n)),0))&&setisset(vecsort(digits(n))),d=numdiv(n);if(d>r,print1(n", ");r=d)))

 --Lambiam 03:42, 2 January 2023 (UTC)

That works. I made the original code and would have modifed it like this:

r=0;for(n=1,10^9,s=vecsort(digits(n));if(s[1]&&setisset(s),d=numdiv(n);if(d>r,print1(n", ");r=d)))

Both versions give this sequence:

1, 2, 4, 6, 12, 24, 36, 48, 72, 168, 396, 432, 576, 672, 1296, 1584, 2184, 3168, 4368, 7392, 14256, 23184, 29568, 52416, 78624, 157248, 248976, 561792, 689472, 746928, 753984, 1493856, 3958416, 6971328, 7584192, 7916832, 23154768, 37621584, 75243168, 283459176, 384576192, 769152384,

It's not in OEIS or a Google search. PrimeHunter (talk) 07:55, 3 January 2023 (UTC)

Not being familiar with PARI/GP and not having it installed to experiment with, I was not sure where assignments were allowed and where semicolons were used instead of commas, so I played it safe and skipped the obvious optimization of not repeating the production of the sorted decimal digits. I should have seen, though, that after sorting the use of setsearch was not needed.  --Lambiam 10:38, 3 January 2023 (UTC)

You can Run PARI/GP in your browser. PrimeHunter (talk) 21:19, 3 January 2023 (UTC)

It's still highly inefficient to run through all numbers to look for the small fraction with distinct digits. More efficient PARI/GP generating them directly:

f(n,m)=local(i);if(m,for(i=1,9,if(!u[i],u[i]=1;f(n*10+i,m-1);u[i]=0)),d=numdiv(n);if(d>r,print1(n", ");r=d))
r=0;u=vectorsmall(9);for(l=1,9,f(0,l))

Runtime 2.5s for me in PARI/GP and 16s online. PrimeHunter (talk) 21:50, 3 January 2023 (UTC)