Could you explain what a git trailer is if not appended to the message body? My understanding is that trailers are just key-value pairs in a particular format at the end of the message; there's not an alternative storage mechanism.
Even so, trailers or message body might be moot - rerolling the committed at timestamp should be sufficient!
Even with git-prime reducing the address space by a few orders of magnitude, there's still (effectively) zero chance for collision. The difference between 10^-29 and 10^-27 isn't that great in practice.
Actually there are π(N) ~ N / ln(N) primes less than N per the Prime Number Theorem, so π(2 ^ 160) ~ 2 ^ 153.2 - this only drops 7 bits. So that does increase the odds of collision but much less than what I expected!
I added the trailer syntax, and rewrote git-prime history to ensure all commits are now number theoretic certified.
If you wish to do the same in your own repo I added a script "make-whole.sh" to do this - but I don't recommend it as force pushes and history rewrites could break stuff.
Tangentially, I love how easy it is to add submodules to git. Just put an executable named git-<something> in your $PATH and it will get called by git when invoked like that.
Whenever you amend a commit, the commit time stamp changes; that ought to be enough, so that the nonce is not required. However, I think it has only second precision, so if you stick to honest wall time, it means 100 attempts require 100 seconds.
Just be aware that there are more prime hashes than there are hashes with a specific 2 hex-digit prefix, so even relatively short messages will be much harder to find.
I don't like that. I want time the canonical when something happened, and metadata surfaced explicitly in an appropriate place. Zero fakery, zero bullshit, zero magic. That's what I want.
Wow, that's fast. Do you know if committer's email also goes into calculation of a git hash? If it is, it should be possible to manipulate git hash in a very discrete way through the email address like this: user+<nonce>@example.com
Why? Fun. Now every commit is a certified 160-bit prime number.
- Miller-Rabin primality test (40 rounds, ~10^-24 false positive rate)
- Fuzzes commit messages with nonces until finding a prime hash
- Average ~368 attempts to find a prime (based on prime density at 2^160)
- Actual performance: 30-120 seconds depending on luck
The philosophy: shouldn't the global distributed compute grid be used to forward number theoretic random non-goals like primality?
Every developer running git-prime contributes cycles to finding 160-bit primes hidden in SHA-1 space. Corporate pointless, but math & aesthets satisfying.
Sure hope the first line of that bash script isn’t rm -rf $HOME/*
Please don’t ever suggest to anyone ever to curl a script and pipe it to bash. I’m sure this one is fine (I haven’t looked) but it’s a pretty awful idea. Only way to make it worse is to suggest slapping sudo in front.
I think item IDs here are sequential, including comments, so you could have timed the submission to attempt to get one. More likely to get it when the site's quieter.
> Miller-Rabin primality test (40 rounds, ~10^-24 false positive rate)
It's way better than that. You are using the simplest upper bound for the false positive rate, which is 1/t^4 where t is the number of rounds. More sophisticated analysis can give better bounds.
See the paper "Average Case Error Estimates for the Strong Probable Prime Test" by Ivan Damgård, Peter Landrock and Carl Pomerance, in Mathematics of Computation
Vol. 61, No. 203, Special Issue Dedicated to Derrick Henry Lehmer (Jul., 1993), pp. 177-194. Here's a PDF: https://math.dartmouth.edu/~carlp/PDF/paper88.pdf
Here are the bounds given there for t rounds testing a candidate of k bits. I'll give them as Mathematica function definitions because I happen to have them in a Mathematica notebook.
1. This one is valid for k >= 2.
p1[k_, t_] := k^2 4^(2 - Sqrt[k])
Note this one does not depend on t, and for small k does not give a very useful bound. For 160 the bound is 0.00992742. For large k the story is different. Testing an 8192 bit number this gives a bound of 3.45661 x 10^-46. That's good enough for almost all applications so in most cases if you want an 8192 bit prime one round is good enough.
2. This one is for t = 2, k >= 88 or 3 <= t <= k/9, k >= 21.
For k = 160 this is valid for t >= 18. At 18 it gives 9.75 x 10^-26. At 40 it gives 1.80 x 10^-41.
4. This one is for t >= k/4, k >= 21.
p4[k_, t_] := 1/7 k^(15/4) 2^(-k/2 - 2 t)
For k = 160 this is valid for k >= 40. At 40 it gives the same bound as p3.
So bottom line is that with your current 40 rounds your false positive rate is under 1.80 x 10^-41, considerably better than 10^-24.
If 10^-24 is an acceptable rate for this application, 18 rounds is sufficient giving a rate under 9.7 x 10^-25.
BTW, the larger the k the lower the rate. I've often seen people looking for 1024+ bit primes doing 64 or more rounds. The simplest 1/4^t bound gives 2.9 x 10^-39. OpenSSL for example does 64 for k up to 2048, and 128 for larger k.
For k = 1024 a mere 6 rounds beats that with a bound of 8.8 x 10^-41.
For k = 2048 it only takes 3 rounds to get 4.4 x 10^-41.
For k = 4096 a mere 2 sounds gives 3.8 x 10^-48.
If we had a population of 1 trillion people, each using 1000 things that needed a 4096 bit prime, and that frequently rekeyed so they needed 1000 new primes per second, and every star in the observable universe also had such a civilization consuming 4096 bit primes at that rate, and they were all using 2 rounds of Miller-Rabin, there would be around 24 false positives a year across the whole universe.
If everyone upped it to 3 rounds there would, across the whole universe, be a false positive approximately every 44 billion years.
The P in BPSW is for Carl Pomerance mentioned in the academic paper above. According to the wikipedia article "No composite number below 2^64 (approximately 1.845 * 10^19) passes the strong or standard Baillie–PSW test" which means if git-prime used this algorithm and the nonce was below 2^64 (very likely) then it would be provably prime instead of a probabilistic prime and hence have much more "mathematical rigor".
I also agree with other comments here that git-prime would be much cleaner if it put the nonce in git commit header data instead of the message. Something like this was done Long Ago in a "for fun" git patch by Jeff King: https://lore.kernel.org/git/CACBZZX5PqYa0uWiGgs952rk2cy+QRCU...
Thank you. This is the hn I’m here for. Probabilistic tests for definite primes still being so slimmest definitive is amazing to me. What structure are they approximating?
And would keep the date constant rather than use the time of each attempt (such that the only thing that actually varies is the Nonce)
And just for more fun... Nonces should only be prime numbers. Probably won't run out :)
reply