Comment by lioeters | Hacker News Reader

Comment by lioeters | Hacker News Reader

Parent Full thread

I don't understand fully what it means for a language or piece of code to be "totally deterministic", but it reminds me of a couple topics that arise in discussions about JavaScript: about an advantage of TypeScript, that a strongly typed language allows more strict error checking at compile time, because the compiler can map the behaviors of functions (which sounds "deterministic"?); and an advantage of functional programming, that each function should be "pure", without side effects or dependency on global state - which, if I remember right, is sometimes called "deterministic". I wonder if these topics are related to what you mean by "untrusted code to be totally deterministic, so that it cannot exploit Spectre or any other side channel attack".

This is an intriguing idea: "a JS engine where any given Javascript event handler and all the synchronous APIs it can call are deterministic, so that all interaction with the nondeterministic outside world is through events".

It seems like that would be a significant re-think/re-organizing at a fundamental architectural level, that it would almost be a new language. Maybe Web Assembly could achieve this?

Determinism is related to purity ("functional programming"), but is a weaker notion. For example, this function

    var c = 0
    function deterministic_not_pure() {
        return c++
    }

is not pure, and you can't reason over it equationally. But it is deterministic: if I make a series of calls to this function in my browser, and you make the same series of calls in your browser, and someone else emulates the code using a Turing machine made of rocks in the desert [1] we will all see the same results. (And consequently, there is nothing that such code can do to learn about its environment!)

As far as I know everything in Javascript-the-language has this property! [2] (Equally, so does WebAssembly). And most of the browser's APIs do as well, though the sheer size of that surface means that any attempt to fix the rare cracks will still be daunting. The vast majority of information that browser JS gets is either through events (i.e. function arguments) and I think most of the rest could be safely forced to be deterministic during the execution of a JS function.

It's still obviously possible for these events to leak timing information about the execution of JS, but I think that can be fought. For example, you could delay the delivery of every event by the number of nanoseconds that JS has executed on the page so far, though of course that naive approach will gradually degrade in performance. But I think for example doing that until you have 10ms of delay and then resetting would probably make timing attacks totally impractical.

All of this needs way more thought, and I'm not at all suggesting that it's easy. But browser JS is closer to an actually-securable-against-side-channels state than almost any other widely deployed platform, and I think it's sad for the people that control the platform (which is, let's face it, basically the Chrome team) to throw it away because they love performance.now() and SharedArrayBuffer.

[1] https://xkcd.com/505/

[2] Well, ECMAScript probably doesn't specify a random number generator, for example. But it could.

Thank you, I was hoping to learn something by posting a comment, and was richly rewarded by your reply. Hadn't seen the "computer of rocks", brilliant.

Yes, I'm starting to see the difference between pure and deterministic. It seems like the latter is a description of a particular type of predictable/repeatable "program flow".

I found a related Wikipedia topic [1], "What makes algorithms non-deterministic?" Quote:

- If it uses external state other than the input, such as user input, a global variable, a hardware timer value, a random value, or stored disk data.

- If it operates in a way that is timing-sensitive, for example if it has multiple processors writing to the same data at the same time. In this case, the precise order in which each processor writes its data will affect the result.

- If a hardware error causes its state to change in an unexpected way.

Although real programs are rarely purely deterministic, it is easier for humans as well as other programs to reason about programs that are. For this reason, most programming languages and especially functional programming languages make an effort to prevent the above events from happening except under controlled conditions.

The prevalence of multi-core processors has resulted in a surge of interest in determinism in parallel programming.

---

The above includes a number of topics you raised, about events and timing information, and the possibility of making a language deterministic with some exceptions "under controlled conditions".

This part feels relevant too: "easier for humans as well as other programs to reason about".

[1] https://en.wikipedia.org/wiki/Deterministic_algorithm#What_m...?

Reply on news.ycombinator.com