vladf

How would such a thing like this exist in practice? Who would watch this watchman?

When your goal is to "discover truth" as Chief Truth Discoverer of the DOJ the only way to audit you is with grander truth discoery.

Surely the hiring issue is a market inefficiency, then, no? There's got to be plenty of engineers out there, but maybe not for typical startup cash/equity structures.

> Sure, you could crank up the difficulty until it makes the cost of the attack too high, but then all your users will get mad - that's basically what CloudFlare does and it attracts non-stop criticism.

This is interesting, where can I read more about both sides?

I do think you hit the nail on the head here, with resource symmetry being the center of the give-get here and making the botnet run warmer is the win (because it requires larger botnets, because it's more detectable, etc.). I think that this might make me upset as a client, but if it's economically advantageous for the server, then I'd still tolerate it to get the server's content.

I think that's why you need auth to be first-class in such a protocol. Yes, auth might be painful and annoying and require that your browser essentially mines hashes for a while on connection setup, but then after that presumably your website would be as fast as usual, and perhaps there might be a way to safely cache such authentication with a lease for valid users. Perhaps this kind of approach is too anti-internet, though, since it basically says that to do any useful backend work you need to be a registered user for some backend service.

On your somewhat off-topic meta-comment about my lack of due diligence: lucky for me I don't need to break out Coq to validate an RFC draft to post a comment on HN, which despite my mushy-gushy feelings has resulted in a productive, curious, and educational discussion, at least for me!

On the point of stolen resources, true, the attacker doesn't care, but I think if we get to the level of resource symmetry in a protocol we've effectively throttled a class of attacks. There are only so many grannies whom a given attacker can pwn. Symmetry is relevant because it makes it that much harder and that much more demanding of your botnet. Besides, like you mention at the end of your comment demanding some kind of additional Byzantine DOS-tolerance is likely too hard of an ask.

You do bring a good point. Maybe outlandish, but see my sibling comment (https://news.ycombinator.com/item?id=28578832) where the server overhead for rejecting invalid packets which the attacker made for free goes down to performing a hash.

Hrm, I don't think you're engaging with the spirit of my proposal, which does require resource-symmetry to establish auth in the protocol.

I admit I haven't specified a full counterfactual protocol here, but see my edit for a rough outline of how you wouldn't just be able to generate garbage.

Right, under the previously unspecified constraint that you need a response in one round trip I agree there's a natural resource asymmetry.

I guess the problem is "simply" the use of these resource-asymmetric protocols. As a server-owner, if there was a robust alternative protocol which ensured resource symmetry, wouldn't you be naturally incentivized to adopt it and reject all asymmetric ones?

It still feels like there's a way of specifying a protocol (which of course would need to be adopted) where (1) authentication is a first-class entity (2) all non-authenticated requests enforce resource symmetry at the protocol level, while still allowing asymmetric work to be done (after a resource-symmetric auth).

Edit: augmenting the rough outline of what I originally proposed you can essentially require an arbitrary amount of proof-of-work, however useless, on the requester side (e.g., literally request a nonce such that the hash of the packet is below some value). Since only auth needs to be symmetric the overhead doesn't seem too bad.

Why is this resource asymmetry unavoidable? It seems reasonable that a new protocol could solve it.

Consider augmenting TCP with a "pre-SYN" and "pre-SYNACK". Suppose you have to send a pre-SYN which declares your identity ip X. Then the server sends to X a "pre-SYNACK" encrypted message containing (X, t = timestamp()) based on a server-only key.

Afterwards, X may send the server a SYN for real. But then the server only allows a timeout of length, say, timestamp() - t, as of receiving the SYN back to maintain bookkeeping.

As benevolent cooperating clients, we may want to ourselves wait an exponentially-backed-off amount between receiving the pre-SYNACK from the server and sending our SYN back (such that in log-many rounds we establish our conn).

Then any malevolent actor must then keep a resource on X alive for at least half long as the server does (since the server requires zero bookkeeping after firing off the pre-SYNACK).

Edit: this is simplified, you could just own a machine at X which is far away from the ddos'd server and then have your botnet spoof requests from X; by augmenting this procedure with even more preamble rounds you could verify how long communication takes between the server and client X and subtract that out.

> Hackable is the default for any test imposed by an authority. The reason the tests you're given are so consistently bad — so consistently far from measuring what they're supposed to measure — is simply that the people creating them haven't made much effort to prevent them from being hacked.

In proof-based math classes in college, there really was no hacking them. You had to build up an intuitive understanding of the concepts and think on the fly to come up with a proof for a test.

Sure, you could try to seek out "all relevant questions" and memorize the proofs but there's such a large universe of possible problems to ask you'd never have enough time to study this way.

Hrm, is it really that easy? If you only have a placeholder in one of your arrays that points to the moved object in the other, then you need to do the actual move back if you have a sequence of pops/pushes which force you to delloc the moved-to array (say you have a grow sequence which gets you almost ready to make the 64 array the small one and then a series of pops back)

Thought maybe in principle there’s yet another “amortization process“ which can be layered on top of what you already described that tries to keep the proportion of placeholders in both small and big arrays equal.

Ah, I was in a rust/c++ frame of mind here—it seems you deeply rely on a copy operation being available, but unless you use indirection and weak pointers it might not be.

I think with copy available this certainly works

I challenge you to try to implement it this way and test that (1) an arbitrary sequence of push/pop is valid and (2) doesn’t use more than linear space.

One thing I’ve always been curious about, can you guarantee worst case linear memory use with this setup while supporting pop() at the same time?

Often, especially when analyzing production logs, you might be interested in questions like "how many users were active in the last hour?" or "how many active connections in the past hour for each of my servers during high load?". It's nice when you know this up-front and instrumented Prometheus accordingly, but often these questions are retrospective.

If your log lines look like

    010.100.111.132 - - [30/Jun/2021:15:30:11 +0000] "GET /rest/... HTTP/1.1" 200 0 "-" "User Agent" "-" 212.031.212.003
    010.100.111.132 - - [30/Jun/2021:15:30:10 +0000] "GET /rest/... HTTP/1.1" 200 0 "-" "User Agent" "-" 212.031.212.004
    010.100.111.132 - - [30/Jun/2021:15:30:09 +0000] "GET /rest/... HTTP/1.1" 200 0 "-" "User Agent" "-" 212.031.212.003
    010.100.111.131 - - [30/Jun/2021:15:30:08 +0000] "GET /rest/... HTTP/1.1" 200 0 "-" "User Agent" "-" 212.031.212.006

Then you may be tempted to just use some `awk '{print $1 " " $15}' | sort -u | cut -d" " -f1 | uniq -c ` to back out unique IPs per server over the last hour for a rough estimate.

By using sketches, we can scale this solution to cases where the number of log lines would make `sort` fail due to OOM or take forever. Here, you'd run `dsrs --key`.

Why would a publisher narrow its target purchasing demographic preemptively?

At the end of the day, the point is book sales, not to actually make you successful (even if that’s the effect for some small slice of the people who actually buy it).

I do quite a bit of data munging on multiprocessor Unix systems, and found (some remarkably lightweight) homemade Rust/py tools invaluable for getting stuff done.

A low-memory Unix map-reduce combinator - https://github.com/vlad17/slb

A sparse matrix parser (cpython equivalents are not parallel) - https://github.com/vlad17/svm2csr

A personal task planner when doing high-risk work which minimizes time to failure - https://github.com/vlad17/fdd

Perhaps my info on these are out of date. Why would you say those are successful examples?

Is this really true? To be able to build a track you need to have government-level authority (e.g., in GP's example, to build something on its own lane in the road, or to displace people in homes in the way of the track). However, the entities funding SDCs are private.

I solved a similar problem recently: given a stream of data, how should you choose packet size in an online way to minimize regret (a linear combination of spare capacity of last packet and total packets used).

Turns out doubling isn’t the best strategy. The optimal solution is actually to add a constant increment to packet size. How much depends on relative cost of the terms in the regret function.

Tutorial and git repo: https://github.com/vlad17/slb

I think the problem with observing interventions is it will result in impractically large sample complexity to derive the same causal conclusion as causal calculus armed with assumptions of DAG structure.

I think metaphysically speaking the approaches (observing interventions vs causal calc) aren’t meaningfully different in terms of inferences you can make with infinite data, see my similar observations to yours: https://vladfeinberg.com/2019/12/01/metaphysics-of-causality...

But if you can presume a fixed DAG you can get away with fewer observations bc then you can derive some minimal/cheap set of vars to randomize over such that the resulting experiment measures a causal effect. All causal calc does is give you a framework for clarifying assumptions necessary to derive such a set.

In high dims performing randomization is exponentially costly.

I think parent’s construction works just fine if you disallow removes, so it grows monotonically, regardless of how dramatic the increase in keys, so long as you move over 2 keys for every update to your map.

My comment was a description of a precise “drastic change” where incrementality becomes sophisticated. (Though in part I was hoping for a response which identifies an elegant approach without the complication I mentioned.)

What happens if you have a sequence of puts that triggers an expansion and some keys get migrated, but all of a sudden you get a series of removes, such that you need to perform a shrink to keep memory usage linear?

Do you now end up with three live arrays? You can probably make things even more pathological...

Alternatively, one could get rid of the memory used by optimizers entirely by switching to vanilla SGD.

I haven’t tried this on transformers and maybe that’s what breaks down here but in “classic” supervised settings I’ve found SGD with schedule tuning just as fast as Adam.

I can't wait to see the vector DBs we're going to have 5 years from now when everyone needs to serve their embeddings. It's clearly early but frothy right now.

Also check out this similar co I ran into: https://www.pinecone.io/ (the CEO, EL, has some classic sketches and feature hashing papers).

I agree, I was really only proposing PRESS for the "parameter efficiency" part of your comment. It'd be interesting to see some modern takes on IRLS. I think generally this goes against the grain of the Cheap Gradient Principle which is why you see less of it (edit: eh, I think Fisher scoring can be cast in this light).

For instance, on modern modelling problems with non-linearities and change points, it's a lot less easy to do something like IRLS in an end-to-end system, but interesting as a research direction.

> they do not quite care about parameter efficiency.

Google Research is pretty big, I used to think like you did but I think it's mostly b/c DeepMind just hogs all the spotlight.

Check out PRESS [0] for example.

[0]: https://research.google/pubs/pub46141

See also my note on reddit refering to the generalization: https://www.reddit.com/r/MachineLearning/comments/hm25mv/com...

What about drone-based delivery instead?