oconnor663

> There's no way for Rust to prevent you from marking an array index as free and later using it.

I 2/3rds disagree with this. There are three different cases:

- Plain Vec<T>. In this case you just can't remove elements. (At least not without screwing up the indexes of other elements, so not in the cases we're talking about here.)

- Vec<Option<T>>. In this case you can make index reuse mistakes. However, this is less efficient and less convenient than...

- SlotMap<T> or similar. This uses generational indexes to solve the reuse problem, and it provides other nice conveniences. The only real downside is that you need to know about it and take a dependency.

Yeah if you go with Vec, you have to accept that you can't delete anything until you're done with the whole collection. A lot of programs (including basically anything that isn't long running) can accept that. The rest need to use SlotMap or similar, which is an easy transition that you can make as needed.

Sort of. But you still get guaranteed-unaliased references when you need them. And generational indexes (SlotMap etc) let you ask "has this pointer been freed" instead of just hoping you never get it wrong.

You could look at it that way. But C++ programs often use similar strategies, even though they don't have to. Array/Vec based layouts like this give you the option of doing some very fancy high-performance stuff, and they also happen to play nicely with the borrow checker.

Yes, Slab and SlotMap are the next stop on this train, and ECS is the last stop. But a simple Vec can get you surprisingly far. Most small programs never really need to delete anything.

My recommendation is that you do whatever you feel like with ownership when you first write the code, but then if something forces you to come back and change how ownership works, seriously consider switching to https://jacko.io/object_soup.html.

In my experience there are two versions of "fighting the borrow checker". The first is where the language has tools it needs you to use that you might not've seen before, like enums, Option::take, Arc/Mutex, channels, etc. The second is where you need to stop using references/lifetimes and start using indexes: https://jacko.io/object_soup.html

> the maintainer of X rust package didn't setup cargo correctly and it's impossible to include in my project

That basically never happens, which is the point.

More important than whether you use a little unsafe or a lot, is whether you can find a clean boundary above which everything can be safe. Something like a hash function or a block cipher can be piles and piles of assembly under the covers, but since the API is bytes-in-bytes-out, the safety concerns are minimal. On the other hand, memory-mapping a file is just one FFI function call, but the uncontrollable mutability of the whole thing tends to poison everything above it with unsafety.

> the SHA3 standard, FIPS 202 and the special publication NIST SP.800-185 define ~20 different functions

The most promising of all the SHA3 derivatives is KangarooTwelve. I think it's sandbagged by its kind of silly name and by (as this article mentioned) the long list of less promising derivatives that came before it. It might take off if they rebrand it "K12" and plaster a message like "you should actually be using K12" at the top of every SHA3 related document out there.

> arguing with the compiler when I know the code is correct just because the compiler can't prove it

I don't want to assume too much about your specific use case, but in a lot of situations that people describe this way, the truth is that the code would've been correct if it was C but -- because it violates the no-mutable-aliasing rule -- it's genuinely broken under the Rust memory model and will trigger UB if you use unsafe code to work around the compiler errors. https://youtu.be/DG-VLezRkYQ

I assume you could just give the computer a large set of 1300 rated games and train it to predict moves from that set :)

You can take as many bytes from the output stream as you want, and they should all be indistinguishable from random to someone who can't guess the input. (Similar to how each of the bytes of a SHA-256 hash should appear independently random. I don't think that's a formal design goal in the SHA-2 spec, but in practice we'd be very surprised and worried if that property didn't hold.) But for example in the catastrophic case where someone found a collision in the default 256-bit BLAKE3 output, they would probably be able to construct colliding outputs of unlimited length with little additional effort.

Fwiw, increasing the BLAKE3 output size beyond 256 bits doesn't add security, because the internal "chaining values" are still 256 bits regardless of the final output length. But 256 bits of security should be enough for any practical purpose.

> Then you can have dangling pointers that point to the wrong place.

Generational indexes in a SlotMap or similar should rule this out.

> Race conditions become possible.

How so?

> You need an allocator for the indices.

Yes, this usually becomes a central point of synchronization. (If you just have a SlotMap, you might not think of it as an "ID allocator", but that is half of what it is.) It doesn't have to be fully synchronous, though, and you can do fancy things with atomics.

> On rare occasions, it crashes with an invalid index.

Indexes become a sort of Weak pointer, and you get an Option when you dereference them, so you can certainly crash if you .unwrap() it or similar. You can use a Vec with "infallible" indexes if you don't want to support deletion, but if you do want to support deletion, the deleted case can bite you one way or another, no?

> It just feels wrong to go around hiding everything that's going on from the borrow checker and moving the errors to runtime. But maybe that's what you need to do to prototype things in Rust without a lot of pain?

There's some truth to that, but I think the real problem is when some part of the state of your program looks like a graph with loops and cycles (not a tree). It's possible that it only looks that way during prototyping, but I think it's more likely that once it starts looking that way, it's gonna stay that way. In that case, "hiding" your lifetimes from the borrow checker is really about making your borrows shorter, which is how you can manage a graph without violating the no-mutable-aliasing rule.

https://jacko.io/object_soup.html

I don't love Rc as a cure for borrow checker woes. When Rust programs need cyclic, graph-y things like back references, I almost always suggest moving to indexes: https://jacko.io/object_soup.html. You can get fancy and reach for a SlotMap or a whole ECS, but a lot of simple cases can get away with just Vec. (And even complex cases can use HashMap if performance isn't critical.)

:-D The styling is adapted from https://edwardtufte.github.io/tufte-css/

> Rust join is actually optional.

I was recently surprised to learn that returning from main() with background threads still running is more or less UB in C++, because those threads can race against static destructors: https://www.reddit.com/r/cpp/comments/1fu0y6n/when_a_backgro.... C doesn't have this issue, though, as far as I know?

It's harder to ignore the problem in Python, because reference counting turns every read into a write, incrementing and then decrementing the recount of the object you read. For example, calling "my_mutex.lock()" has already messed with the recount on my_mutex before any locking happens. If races between threads could corrupt those refcounts, there's no way you could code around that. Right now the GIL protects those refcounts, so without a GIL you need a big change to make them all atomic.

> Debian effectively does this. It doesn't actually implement the crates.io API, but when building a Rust package they tell cargo "look in this directory for dependencies, don't talk to the network".

That sounds close to what I had in mind, but I assume you run into problems with the finer points of Rust's dependency model. Like if I depend on libfoo v1, and you depend on libfoo v2, there are a lot of situations (not all) where Cargo will happily link in both versions of libfoo, and applications that depend on both of us will Just Work. But if libfoo needs to be its own Debian package, does that mean every major version is a different package?

That's the first question that comes to mind, but I'm sure there are others like it. (Optional features? Build vs test dependencies?) In short, dependency models (like Cargo's and Debian/APT's) are actually pretty complicated, and ideally you want to find a way to avoid forcing one to represent all the features of the other. Not that I have any great ideas though :p

I think it would be pretty natural for a distro to run it's own crates.io/PyPI/NPM mirror to build packages against, and have a unified set of library versions for the entire OS that way. Maybe not even a server, maybe just a giant Git repo or whatever, filtered down to the set of packages they actually use. Have any of them tried this?

> most individuals in the world were much worse off 200 years ago than they were 200 years before that

Is there like a particular graph or chart that puts numbers on this?

> Does a ref counted arg transfer the ref or does it take its own ref?

This sort of thing also comes up a lot when you write Python extensions in C. You have to know the "calling convention" when you pass object refs in and out of functions. This entire category of problems goes away when you write extensions in Rust with PyO3, and the barrier to entry for new folks is much lower. C++ can do similar things (std::shared_ptr), but it tends to introduce new footguns in a way that Rust really doesn't.

This is confusing two different questions, "How do we hash multiple things at once without breaking the collision property?" and "How do we MAC messages in a way an attacker can't forge?" Length suffixes are answering the first question, not the second.

> I’m explicitly talking about cases where you UTF-8-encode right where you’re hashing.

Totally, I get that. I think what you're pointing out is that in a language like Python for example, the scenario I'm trying to describe is meaningless. You can't make an "invalid string" in Python (as far as I know, without resorting to FFI), because it checks things like that during string decoding, and it'll just crash.

But languages like C/C++/Rust/Go work differently. As these languages are commonly used, the string -> UTF-8 step is actually a no-op, because the assumption is that strings are already UTF-8 in memory. (In C or C++ this is usually in the programmer's head rather than in the types, but it's a common choice.) In these languages it's possible for the result of that no-op "encoding" to be invalid, if the input string was invalid somehow. This is a pretty weird edge case and almost certainly a bug that the application needs to fix fix anyway, but if we're noodling about cryptography best practices, it might be nice to limit the "blast radius" of a bug like that.

I agree that this approach works in the use case you're describing, but there are a couple reasons I wouldn't want to teach it broadly. Mainly, a caveat like "remember to only use this with UTF-8 strings and not with arbitrary bytes" is exactly the sort of thing applications routinely get wrong in the wild. Also, focusing on wacky edge cases, do we really know that our UTF-8 strings are valid UTF-8? Maybe we're comfortable staking our security on that in a language like Rust, where invalid strings are literally undefined behavior anyway. But what about in Go for example, where this snippet writes 0xff to stdout with no warnings whatsoever?

    func main() {
        s := string([]byte{0xff})
        fmt.Println(s)
    }

It's not a random suffix, but a length suffix. So for example putting "hello" and "world!" together looks like "hello" | 5 | "world!" | 6. Concretely, you probably represent 5 and 6 as eight little-endian bytes, i.e. `n.to_bytes(8, 'little')` in Python. If you want to stop attackers from guessing/constructing hashes, you need to get a secret key involved, which is what the "YoloMAC" section of the post is about.

I usually recommend an 8-byte length suffix for each piece instead of a separator.* That way you don't need to make any assumptions about what bytes are legal. Putting the length in suffix position means you can still stream input into your hash state without knowing how long it's going to be in advance, and 2^64 bytes is enough for any practical application. (The maximum input size of SHA-256 is less than this.)

I'm less sanguine than the authors about using Protobuf or CBOR for "canonical" serialization like this. I think it tends to "work until it doesn't". It's not what these formats were designed for, and you have to ask awkward questions like "is the order of struct fields guaranteed?" and "do integers always use the smallest possible representation?". This is more obvious for JSON, as the post points out, but every common serialization format I'm aware of has problems like this. I think we need a dedicated standard to do a good job of this, but I'm not aware of anything widespread. It's a surprisingly hard problem.

* Technically you only need the suffix for each variable-length piece, and you can omit the first one. But it's more complicated if the number of pieces is variable. (If you have two adjacent fixed-length pieces, and then you combine them, does the hash change?) This sort of penny-pinching is interesting to think about in a design that's going to come with a giant set of test vectors, but it's asking for trouble in an application doing something custom. This is another reason I'd like to have a standard here.

I'm sure that's part of the story, but there's tons of boring old company/government equipment out there in the world that wants secure boot too.