It's extremely common in graph theory to use n and m to mean vertex and edge count respectively. And if you're unfamiliar with graph theory, the notation |V| or |E| is hardly more intuitive, especially if you're not an English speaker.
2,248 karma · joined May 9, 2011
Can you run the program 10 times and show me how much variance there actually is in the first column? Because if all the values lie between (say) 756000 and 757000 that's actually just 10 bits of entropy, not 19.5, and if the same applies to the other values, you're much closer to the original 90 bits.
Case in point:
> The sha256 hash itself is responsible for doing physical things to the chip (heating up some parts unevenly during the hashing computation)
Some CPUs do thermal throttling, others run at a fixed frequency or are so underclocked that thermal throttling doesn't kick in during your 50 iterations. This is exactly the source of randomness that is just not guaranteed to exist across systems.
-----
> You can't just do calls to clock_gettime(), you have do an actual sequential sha256() call between them. Please run this code again and tell me what results you get.
OK, I'll humor you, but to reiterate: it isn't really my point.
After adding hashing in the loop:
Clock resolution: 0.000000001
Hash: a8531a79fc350a3b35b3e82e33b759f6caa97a12efd16a715acb99065b6f3e89
Deltas (ns): 21662 452 335 297 290 288 288 291 289 293 290 289 290 284 287 297 289 289 295 288 287 286 292 291 287 287 301 289 299 290 292 288 291 292 296 294 295 293 290 287 297 292 292 292 288 295 291 289 296
Deltas of deltas: -21210 -117 -38 -7 -2 0 3 -2 4 -3 -1 1 -6 3 10 -8 0 6 -7 -1 -1 6 -1 -4 0 14 -12 10 -9 2 -4 3 1 4 -2 1 -2 -3 -3 10 -5 0 0 -4 7 -4 -2 7
Maximum entropy: 177
It's more obvious if you run it a few times in a row:
Deltas (ns): 21662 452 335 297 290 288 288 291 289 293 290 289 290 284 287 297 289 289 295 288 287 286 292 291 287 287 301 289 299 290 292 288 291 292 296 294 295 293 290 287 297 292 292 292 288 295 291 289 296
Deltas (ns): 22213 486 361 318 290 290 290 289 289 291 289 291 287 289 285 289 294 289 289 287 294 292 293 292 295 295 286 298 288 291 292 295 291 292 291 292 297 294 293 297 289 288 299 288 299 295 292 291 293
Deltas (ns): 23042 475 312 309 290 292 294 291 291 289 290 293 287 291 290 297 299 288 289 294 289 289 297 294 295 295 288 295 291 287 290 287 300 293 289 290 292 287 293 295 292 291 289 292 288 294 290 287 290
Deltas (ns): 22209 478 360 301 295 293 290 291 290 290 293 284 291 290 289 290 294 289 294 293 290 301 288 298 287 295 300 295 292 300 293 296 295 294 294 293 291 289 295 293 291 299 292 299 292 291 295 298 292
If I estimate the entropy as the logarithm of the difference between maximum and minimum I get only 146 bits of entropy in this case. Technically above your standard of 128 bit, but my point was: nothing guarantees you get even this much entropy on a less noisy system.
This also shows the problem with your "just run more iterations" advice: in the above sample, the first five columns provide 24 bit of entropy per column, and the remaing 45 columns only 2.6 bits. So adding more iterations at the tail end wouldn't double the entropy obtained.
The code I used is here: https://pastebin.com/ZrL1UDEg
A compromised kernel doesn't even have to fake any data. It can just read the generated seed directly from user space without the program ever knowing about it.
> Sure an infected system may as well fake time values, but that is much more difficult
clock_gettime() just reads a value that the kernel has set, so that's not particularly difficult to fake.
If you're thinking of using RDTSC instructions directly, that's of course not portable, and at that point you might as well call RDRAND directly, which is at least designed to provide random data.
> it's possible to detect from a userspace program.
There is no detection that is guaranteed to work on a compromised system.
And whatever detection you have in mind to make the algorithm resistant to tampering was _not_ part of the original for-loop. You cannot claim the for-loop is superior to just calling getentropy() because it "can detect" clock tampering, while handwaving away the actual code to detect this clock tampering.
> it's an implementation that is used in a lot of security software (including GPG, not as the sole source of course but as one of many).
It's fine if you use it as a strictly additional source of entropy, but then the whole argument that it is superior because it avoids syscalls goes out of the window, because you're doing strictly _more_ work.
#include <time.h>
#include <stdio.h>
static int estimate_entropy(long l) {
int bits = 1; /* for the sign bit */
if (l < 0) l = -l;
while (l > 0) {
++bits;
l >>= 1;
}
return bits;
}
int main() {
struct timespec ts;
if (clock_getres(CLOCK_REALTIME, &ts) != 0) {
perror("clock_getres");
return 1;
}
printf("Clock resolution: %ld.%09ld\n", (long) ts.tv_sec, (long) ts.tv_nsec);
#define N 50 /* number of samples */
struct timespec samples[N];
for (int i = 0; i < N; ++i) {
clock_gettime(CLOCK_REALTIME, &samples[i]);
}
printf("Deltas (ns):");
long deltas[N - 1];
for (int i = 0; i < N - 1; ++i) {
deltas[i] =
(samples[i + 1].tv_sec - samples[i].tv_sec)*1000000000L
+ (samples[i + 1].tv_nsec - samples[i].tv_nsec);
printf(" %4ld", deltas[i]);
}
printf("\n");
long entropy = 0;
printf("Deltas of deltas: ");
for (int i = 0; i < N - 2; ++i) {
long dd = deltas[i + 1] - deltas[i];
printf(" %4ld", dd);
entropy += estimate_entropy(dd);
}
printf("\n");
printf("Maximum entropy: %lld\n", entropy);
}
Clock resolution: 0.000000001
Deltas (ns): 55 51 23 23 25 24 24 24 24 24 25 25 24 24 24 24 24 25 24 24 24 25 25 24 24 23 25 24 24 25 24 23 25 25 26 23 25 24 24 25 26 24 23 25 25 26 24 25 24
Deltas of deltas: -4 -28 0 2 -1 0 0 0 0 1 0 -1 0 0 0 0 1 -1 0 0 1 0 -1 0 -1 2 -1 0 1 -1 -1 2 0 1 -3 2 -1 0 1 1 -2 -1 2 0 1 -2 1 -1
Maximum entropy: 92
The security of your system depends on time() providing enough entropy, even though that's not what it's designed to do. It's built on top of the wrong primitive from the start.
> The reason I like doing it this way is that it happens entirely in userspace
On Linux this is often true, but there is no portable way to get the current time that is _guaranteed_ not to do any system calls.
> If your time() function has a resolution of nanoseconds, you only need your loop to iterate about 50 times to get a cryptographically secure amount of entropy.
You haven't proven that at all. It's easy to imagine that on a CPU running at a fixed frequency the interval between reads is constant, so if anyone knows (or can guess) the start time the resulting seed is entirely predictable.
This is completely independent of timer resolution. You seem to realize that as you were writing that:
> just look at the number of nanoseconds that elapse at each consecutive call to sha256(current_time()) and verify that there's some statistical variance
Oh yes, because evaluating the quality of a random number generator is such a trivial thing to do, it's not like there is decades of research behind it or anything.
And assuming you are able to verify the statistical variance: are you going to put that logic in the loop, making it significantly more complex?
Or are you going to do this test on your machine and then ship your code on the assumption that if it works on your machine, it will work everywhere else, too?
> if your time() function has a resolution of seconds you need to let it run for more like 5 seconds.
So not only is it insecure, it's agonizingly slow by design. Why do a system call that takes milliseconds at best, when we can run a loop in userspace for 5 seconds?
All this just so you can avoid writing the obviously correct oneliner:
if (getentropy(&seed, sizeof(seed)) != 0) abort();The only legitimate reason to roll your own is when you're developing for an embedded system or a bootloader or something like that where there is no kernel API available.
The POSIX standard function is getentropy(), which internally calls getrandom() on Linux.
> what if there’s a bug in the kernel which causes /dev/(u)ramdom to be less than secure?
It's often the other way around: the Linux kernel contains thousands of workarounds for buggy hardware, while the buggy hardware itself doesn't always get patched. Linux developers take this stuff very seriously. As a result it's often safer to rely on kernel APIs than to access the hardware directly.
The kernel code involving random number generation receives an exceptionally high amount of scrutiny because of its security implications, so I'd trust it to do the right thing over a naked call to RDRAND which nobody knows how exactly it's implemented in proprietary hardware or a handrolled solution to mix the RDRAND output with other entropy sources.
Remember the Debian openssl disaster from 2008? That happened exactly because someone had handrolled their entropy mixing solution, then someone else broke it.
I got some really good results with bzip3 compression Wikipedia XML dumps, and I would like to check if it's actually better or if I was just calling zstd wrong.
https://www.orwellfoundation.com/the-orwell-foundation/orwel...
(I'm guessing Zinsser's comments are from "On Writing Well", which you can also find online even though it is still under copyright.)
It's a bit of a pet peeve when people include quotes on a blog post without linking or otherwise references their source.
atproto.com contains a succinct discription:
> Atproto is a big-world open social protocol. Users publish JSON records into repositories. The changestreams of those records then sync across the network to drive applications.
Still a bit abstract, but OK. Personally I would include that AT protocol stands for Authenticated Transfer Protocol and that it is the protocol powering Bluesky.
> We unknowingly gave particularly high rewards for metaphors with creatures
It was the human feedback that caused the bias, not a change in training data.
I never made that claim. I just said it's way too early to rule it out: there is no logical reason why AIs will (always) need to have a human in the loop, and we don't have enough experience with LLMs to know what their true limits are.
I referenced AlphaGo not because the game of Go is exactly like every other task AI might perform in the future, but because the evolution from AlphaGo (which was trained on human games) to AlphaGo Zero (which was not) shows that at least in certain domains, it's not only possible to take the human out of the loop, it can actually make AI perform better.
I'm not claiming this will definitely be possible in every other domain, but people who state it definitely won't be, are jumping the gun.
> We find that _indiscriminate_ use of model-generated content in training causes irreversible defects in the resulting models
If you view AI training as lossy compression of their training data, then lossily compressing the same data repeatedly will result in data degredation; this is well known from other domains (try repeatedly compressing a JPEG image, for example).
That means it's extremely important that there is some content curation in the loop. But there is no reason to believe this content curation must be done by humans, or that it must exclude all AI-generated content by default.
For example, the recent LLM-generated disproof of the Jacobian conjecture would probably be beneficial to include in the training data, despite being the result of an LLM.
This is asserted without evidence. There is absolutely no proof that AI requires humans in the loop to function or improve itself.
Compare it with Deepmind's go-playing program, AlphaGo, which mainly involved training a neural network on a large database of high-level human games. It defeated one of the top-ranked players in the world, Lee Sedol, but arguably it was drawing from human experience just like you described.
But it didn't stop there. After that, Deepmind developed AlphaGo Zero, a version that was trained exclusively through self-play, with no human feedback in the loop. That's what you would call "AI inputs coming from AI outputs" but it didn't have the result of “resulting in delirium”: instead, it became orders of magnitudes stronger than the original version (which it defeated in a 100 to 0 competition after 3 days of training).
This shows that AI can improve itself without having access to any human knowledge, and indeed transcend human performance by orders of magnitudes. There is absolutely nothing to suggest that general AI cannot improve itself the same way.
People who claim otherwise are engaging in wishful thinking; they just assert their conclusion, but have no rational arguments to back it up.
For example, here is a typical use of a lambda expression to filter a vector of values:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
int threshold = 5;
std::erase_if(v, [&](int i) { return i < threshold; });
// prints 5 9 6 5
for (int i : v) std::cout << i << '\n';
}
...
int threshold = 5;
struct lambda_t {
int &threshold;
bool operator()(int i) {
return i < threshold;
}
};
std::erase_if(v, lambda_t{threshold});
...
The important takeaway is that every lambda expression corresponds with a unique type that is _not_ a function type, but a class type. Consequently, lambda expressions can only be passed to template functions like std::erase_if, which are parameterized with the callback type.
You cannot pass a lambda expression to a function that expects a function pointer (e.g. bool(*)(int) in this example), and that's where they differ from GCC-style nested functions, which actually behave like functions. It also explains why lambda expressions don't need a trampoline.
As an aside, you _can_ pass lambdas to non-generic functions using a type-erasing wrapper like std::function, but std::function is itself a class type too, so that still doesn't allow you to convert it to a plain function pointer.
Finally, you can of course assign a name to a lambda expression value, using this common pattern:
auto greet = [](const char *name) { std::cout << "Hello " << name << "!\n"; }
greet("Alice");
greet("Bob");
This is the closest you can get to a local function definition in C++. Admittedly the syntax is a little odd. You might wonder why there wasn't some additional syntactic sugar to make the definition look more normal. I suspect that wasn't a random decision, but rather intentionally avoiding conflicts with existing language extensions like GCC's local function syntax.
For the capturing case: to access context that is not available through global variables or function arguments, i.e., the same reason why closures are useful in other languages.
Here's an example, where I have a list of points that I want to sort based on distance to a chosen target point. I can use qsort() which takes an arbitrary comparison function, but has no way to provide context to that function beyond the input arguments:
#include <stdio.h>
#include <stdlib.h>
int main() {
struct Point {
int x, y;
} points[3] = {
{ 3, 1 },
{ 2, 2 },
{ 5, 7 } };
struct Point target = { 4, 5 };
long dsq(const struct Point *p) {
long dx = p->x - target.x, dy = p->y - target.y;
return dx*dx + dy*dy;
}
int compare(const void *p, const void *q) {
long a = dsq(p), b = dsq(q);
return (a > b) - (a < b);
}
qsort(points, 3, sizeof(struct Point), compare);
for (int i = 0; i < 3; ++i) {
printf("%d,%d\n", points[i].x, points[i].y);
}
}
The usual workaround in standard C is to pass the necessary context as a function argument. That's why qsort_r() exists, which takes a context argument to be passed to compare(), but that's a non-standard GNU extension.
This practice of passing context pointers around is ubiquitous in C code, and it works, but it can get messy especially if you need access to multiple variables or variables from more than one nested scope. There is also a type safety issue: these context pointers are necessarily passed as void* which means they have to be cast back to the real type before use, which is where bugs can be introduced if the caller and receiver disagree on the actual type.
That being said, SDL isn't actually that bad either. A minimal example is about 40 lines of code [1], not counting comments and blank lines, but including lines with just a curly brace which you could easily remove if you were concerned about size. A slightly more serious implementation of Snake runs about 345 lines of code [2].
And to be fair, DONKEY.BAS is also cheating slightly on the line metric by stuffing lines full of statements, like for example:
A$=INKEY$:IF A$=CHR$(27) THEN 1298 ELSE POKE 106,0:IF LEN(A$)>0 THEN LINE (CX,CY)-(CX+28,CY+44),0,BF:CX=252-CX:PUT (CX,CY),CAR%,PRESET:SOUND 200,1
I agree with you though, it's obnoxious to share paywalled articles on Hacker News.
Note that there is an intrinsic trade-off between minimizing file sizes and making access efficient. Something like delta-encoding is highly efficient but makes efficient access impossible.
Most file formats are designed with the assumption that line number information will only be needed rarely (e.g. when explicitly breaking into a debugger, or annotating a backtrace in case of a crash) so they prioritize simplicity and compactness over efficient access.
Gee whiz what an interesting way of thinking.