<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Robert Grosse on Medium]]></title>
        <description><![CDATA[Stories by Robert Grosse on Medium]]></description>
        <link>https://medium.com/@robertgrosse?source=rss-8963dc385f1f------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*B-x_DvC-Xf4GTx8k.</url>
            <title>Stories by Robert Grosse on Medium</title>
            <link>https://medium.com/@robertgrosse?source=rss-8963dc385f1f------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 21:31:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@robertgrosse/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[1SubML: Plan vs Reality]]></title>
            <link>https://medium.com/@robertgrosse/1subml-plan-vs-reality-899c17183afc?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/899c17183afc</guid>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Sun, 05 Apr 2026 00:08:06 GMT</pubDate>
            <atom:updated>2026-04-13T00:15:57.428Z</atom:updated>
            <content:encoded><![CDATA[<p>Last August, I wrote <a href="https://blog.polybdenum.com/2025/08/19/x-design-notes-unifying-ocaml-modules-and-values.html">a series of posts</a> outlining my ideas and plans for my then-upcoming programming language 1SubML. Now that <a href="https://github.com/Storyyeller/1subml">I’ve finally released 1SubML</a>, I decided to look back at how my original plans compare to what I actually ended up implementing.</p><p>Overall, I was successfully able to fulfill the original vision for 1SubML, but there were lots of under-the-hood changes and lots of minor features that I ended up not doing or doing differently, as well as new features that I didn’t originally plan.</p><p>This post will go through all the ways that the final version of 1SubML differs from the original plan, in the approximate order of the original posts.</p><h3>I. Spine constructors</h3><p>The single biggest change was abandoning <a href="https://github.com/Storyyeller/polysubml-demo">PolySubML</a>-style structural polymorphism for <em>spine constructors</em> (i.e. nominal typing).</p><p>PolySubML was my previous language, and I naturally planned to build 1SubML on top of it, as an extension of PolySubML adding features like modules and higher kinded types that didn’t make it into PolySubML.</p><p>As the name suggests, PolySubML’s biggest feature was the addition of polymorphic types. In PolySubML, polymorphic types use <em>structural subtyping</em>. For example, [T]. T -&gt; (T, T) is a subtype of [T]. T -&gt; (T, any).</p><p>Unfortunately, once I started work on my new language, I discovered that <a href="https://blog.polybdenum.com/2025/11/13/polysubml-is-broken.html">PolySubML is broken</a>. Specifically, in certain complex pathological cases, it violated the writeable types property.</p><p>Once I finally realized that fully structural polymorphic types were impossible, I was forced to switch to the next best thing, <em>spine constructors</em>. Effectively, this means that the <em>non-polymorphic</em> parts of polymorphic types are still subject to subtyping, but the <em>polymorphic</em> parts of the type have to match <em>exactly</em>.</p><p>For example, [T]. T -&gt; (T, int) is still a subtype of [T]. T -&gt; (T, any), but [T]. T -&gt; (T, T) is now an incompatible type, unlike in PolySubML. You can still use the :&gt; operator to <em>explicitly</em> convert between different polymorphic types that are structurally compatible, but there are no longer any <em>subtyping</em> relationships between them.</p><p><a href="https://github.com/Storyyeller/1subml/blob/master/docs/guide_ch4.md#spine-constructors"><em>See here for the technical details on spine constructors</em></a><em>.</em></p><p>While switching to spine constructors by itself might not seem like such a big deal, it had huge ramifications for the rest of the language design, because many of the originally planned features only made sense with PolySubML-style polymorphism. For example…</p><h3>II. Existential destructuring</h3><p>In PolySubML, generic functions and existential records are symmetric, in the sense that there is special syntax for creating values of generic functions (function definition syntax) and special syntax for <em>consuming</em> existential record values (pattern matching syntax).</p><p>Specifically, you can include <em>type</em> fields in record patterns, which makes the pattern match against an existential record type (and then pin the type). For example:</p><pre>let foo: {type t; zero: t; add: (t, t) -&gt; t} = <br>    if whatever then <br>        {zero=0; add: fun (a, b) -&gt; a + b}<br>    else <br>        {zero=0.0; add: fun (a, b) -&gt; a +. b}<br>;</pre><p>The original plan was to have this PolySubML-style existential destructuring syntax exist side-by-side in 1SubML with a newly introduced let mod syntax that pins an existential type <em>without</em> also destructuring the fields.</p><p>However, since I had to throw out PolySubML-style polymorphism completely, existential destructuring is no longer a thing. In 1SubML, the only way to pin existential types is to use a mod binding (a slightly simplified version of the originally proposed let mod syntax).</p><p>Furthermore, the switch to spine constructors meant that the only way to <em>create</em> existential record values is using the newly introduced subsumption operator (:&gt;). The subsumption operator was not part of the original plan either, because with PolySubML-style types, subsumption is baked into the <em>subtype relation</em>, and there&#39;s no need for explicit conversions like there is with spine constructors.</p><h3>III. Struct syntax</h3><p>OCaml has basic record syntax ({}) for ordinary values and module syntax ( struct .. end) for module values.</p><p>As 1SubML unifies values and modules, you can just use the normal record syntax for both. The original plan though was to <em>also</em> support OCaml-style struct syntax, and just have it be <a href="https://en.wikipedia.org/wiki/Syntactic_sugar">syntactic sugar</a> for ordinary record syntax wrapped in a block:</p><pre>let M = struct <br>    type t = int;<br>    let x = 2;<br>    let z = 3;<br>end;<br>// is shorthand for<br>let M = (<br>    type t = int;<br>    let x = 2;<br>    let z = 3;<br>    {alias t=t; x; z}<br>);</pre><p>However, this ended up being another indirect casualty of the switch to spine constructors. The problem is that switching to spine constructors changes the exact point in the code where the ordinary record -&gt; existential record coercion occurs. Specifically it happens in the new (:&gt;) expression (i.e. the outer scope) rather than the scope of the original record value (the inner scope).</p><p>This in turn means that it is easy to run into confusing scoping issues with struct syntax, making it into a giant footgun which isn&#39;t worth the cost of including. For example,</p><pre>mod M = (struct<br>    type foo = int;<br>    wrap=foo;<br>    unwrap=foo$;<br>end :&gt; sig <br>    type t;<br>    val wrap: int -&gt; t;<br>    val unwrap: t -&gt; int;<br>end);</pre><p>desugars into</p><pre>mod M = ((<br>    type foo = int;<br>    let wrap=foo;<br>    let unwrap=$foo;<br><br>    {alias foo=foo; foo; foo$; wrap; unwrap}<br>) :&gt; { <br>    type t;<br>    wrap: int -&gt; t;<br>    unwrap: t -&gt; int;<br>} with [t=_]);</pre><p>The problem here is that the type foo goes out of scope after the inner () that struct desugars to, meaning that it is no longer in scope when t is inferred:</p><pre>mod M = ((<br>    type foo = int;<br>    let wrap=foo;<br>    let unwrap=$foo;<br><br>    {alias foo=foo; foo; foo$; wrap; unwrap}<br>    // type foo goes out of scope here<br>) :&gt; { <br>    type t;<br>    wrap: int -&gt; t;<br>    unwrap: t -&gt; int;<br>} <br>    with [t=_] // but we need to infer foo here!<br>);</pre><p>Due to the scoping issues, this code example results in a type error, even though users might expect this code to compile.</p><p>Since struct syntax would be confusing and not that useful anyway, I decided to just leave it out of 1SubML entirely.</p><p>In addition to struct syntax, there were lots of other features originally planned ( sig syntax, record extension, module includes, etc.) that I only originally proposed for the sake of emulating OCaml-style module syntax. With struct removed from the language, 1SubML wasn&#39;t going to be emulating OCaml syntax <em>anyway</em>, so there was no point in including any of that other stuff either.</p><h3>IV. Early type propagation</h3><p>One issue I endlessly struggled with in the design of 1SubML was the question of how much and what kind of <em>early type propagation</em> to do.</p><p>Conceptually, 1SubML’s type checker works in two phases. First, the input source code is parsed and converted into type constraints and inference variables, and then type inference solves all the constraints (or reports a type error if there is a conflict).</p><p>In the actual implementation, both steps are intertwined, but they behave as if they are independent, a separation which is important for making it easier to reason about the correctness of the type checker. Most importantly, this means that <em>the compiler is not allowed to observe the results of type inference</em>.</p><p>1SubML is carefully designed to make as many things inferable as possible. With the exception of polymorphic type parameters (which, strictly speaking, are not actually types and hence can’t be inferred), there are only a handful of cases where explicit type annotations are required.</p><p>The only times when type annotations may be required are when type constraints depend on <em>types</em>, meaning that the types have to be known <em>before type inference</em>. These are mod bindings, subsumption expressions (:&gt;), file exports (which are just a subsumption expression + mod binding under the hood), implicit coercion declarations, and newtype definitions (only if you want to use implicit coercions). Everything else is fully inferable.</p><h4>Mod type annotations</h4><p>This is mostly relevant to mod bindings, so I&#39;ll use that as an example.</p><p>mod bindings can <em>generate new types</em>, which has to be done before type inference runs. Therefore, a mod binding has to know the type of the input value, and that type has to be known before type inference runs, so that the compiler knows which new types, if any, to generate. (And similarly for new type aliases.)</p><p>Normally, this means that an explicit type annotation is required, e.g. mod &lt;name&gt;: &lt;type&gt; = &lt;expr&gt;;. However, requiring a type annotation on <em>every</em> mod binding would be a huge pain, especially when the type is already obvious from the right hand side.</p><p>This is especially important because in order to use abstract types in a module, you need to convert the record to an existential type, which requires a subsumption expression ( mod M = (r :&gt; &lt;type&gt;);). This means that the user will nearly always be specifying the type on the right hand side (in the subsumption expression) <em>anyway</em>, so it would be a huge pain to have to repeat it on the left hand side as well. To handle such cases, we need <em>early type propagation</em> to propagate type information <em>before</em> type inference.</p><p>In the final version of 1SubML, mod type annotations can (roughly speaking) be omitted in the following cases:</p><ul><li>Record literals: mod M = {x=4; y=6};</li><li>Typed expressions: mod M = (r: &lt;type&gt;);</li><li>Subsumption expressions: mod M = (r :&gt; &lt;type&gt;);</li><li>Variables with known types: let r: &lt;type&gt; = ...; mod M = r;</li></ul><p>I think this strikes a good balance, allowing type annotations to be omitted in cases that are a) easy for the user to understand and b) simple to implement in the type checker. However, the original plan included much more aggressive early type propagation.</p><h4>Abandoned type propagation</h4><p>In the original post, <a href="https://blog.polybdenum.com/2025/08/19/x-design-notes-unifying-ocaml-modules-and-values.html#forward-type-propagation">I proposed</a> additionally propagating types through field access expressions, function call expressions, and conditional expressions, among others.</p><p>The original motivation for this was to more closely emulate the behavior of OCaml functors. In OCaml, functors do propagate types, and this would correspond to function calls and field accesses in 1SubML.</p><p>I ended up deciding not to do this for several reasons.</p><p>First off, with appropriate code design, I think the additional annotation burden would be minimal, so there’s little benefit.</p><p>Second, this greatly increases the complexity of the type checker as there now needs to be two completely independent implementations of type checking for each of these expressions, one for type propagation and one for the normal type inference case.</p><p>Finally, I think it would also be confusing for users. For type inference errors, the 1SubML compiler will help you find the issue, but there is no way to do this for early type propagation. If the user expects early type propagation to apply in their code but it doesn’t for whatever reason, they’ll just get an error with no explanation and no way to troubleshoot it or find out <em>why</em> early type propagation didn’t apply. Allowing type propagation across large distances through complex expressions in the code makes this much worse.</p><h3>V. Newtypes and coercions</h3><p>Unlike the original post on handling modules, <a href="https://blog.polybdenum.com/2025/08/25/x-design-notes-nominal-types-newtypes-and-implicit-coercions.html">the post on newtypes</a> made it to implementation with only minor changes, mostly cosmetic syntax changes.</p><p>First off, the original proposal used type for type aliases and newtype for newtype definitions (e.g. newtype foo = int;). The final version of 1SubML instead uses alias for type aliases and type for newtype definitions, as I thought this would be clearer and more intuitive.</p><p>The syntax for pure identity function types also changed, with the originally proposed a :&gt; b becoming a =&gt; b in the final language.</p><p>The syntax for registering custom implicit coercions is completely different. The original proposal was to allow adding an implicit prefix to any let binding:</p><pre>newtype foo = {x: int};<br>(* foo$ implicitly marked as a coercion for foo *)<br><br>(* Create a module wrapping foo as a new type named bar *)<br>let mod M: sig <br>    type bar;<br>    val bar: _ -&gt; bar;<br>    val bar$: bar -&gt; _;<br>end = {bar=foo; bar$=foo$};<br><br>(* There are no coercions for M.bar, but we can add one like this *)<br>let implicit bar$ = M.bar$;<br>(* Any binding in a pattern can be marked implicit. It could have also been done like this: *)<br>let {implicit bar$} = M;</pre><p>However, doing things this way adds a lot of complexity for no real benefit, so I eventually settled on a simpler approach, where implicit coercions are registered using dedicated implicit{} declaration syntax. The new implicit syntax is specified at the point where the custom types are introduced, either a function definition, module binding, or export declaration.</p><p>Here’s the above example translated into the final 1SubML syntax:</p><pre>type foo = {x: int};<br><br>mod M <br>    implicit{bar: bar$ bar} // implicit coercions registered here<br>    = (<br>    {<br>        bar=foo; <br>        bar$=foo$<br>    }<br>    :&gt; <br>    {<br>        type bar; <br>        bar: {x: int} =&gt; bar; <br>        bar$: bar =&gt; {x: int}<br>    }<br>);</pre><p>Finally, there was also a syntax change for coercion annotations in patterns. The original proposal prefixed the pattern with the coercion value <em>expression</em>, followed by #:</p><pre>let foo$#{x=q} = v;</pre><p>In the final version, you prefix the pattern with the <em>type</em>, and there is no # separator:</p><pre>let foo {x=q} = v;</pre><p>Doing things this way greatly simplifies the internal implementation <em>and</em> simplifies the user-visible syntax as well.</p><p>The motivation for the original # syntax was that I also wanted to be able to add inline coercion annotations to field access expressions. For example, v.x could be annotated explicitly as v.foo$#x. However, I eventually decided that this doesn&#39;t make sense and isn&#39;t necessary. In the final version of 1SubML, there is no special syntax for annotating field access expressions like this. If you want to add an annotation, you need to use a normal typed expression, e.g. (v: foo).x.</p><h3>VI. Higher-kinded types and subkinding</h3><p>One design aspect that I struggled with for a long time was how exactly to handle higher-kinded types, and in particular, “subkinding”. As 1SubML has sub <em>typing</em>, it seemed only natural to apply the same approach to <em>kinds</em> as well, but it was hard to figure out the details.</p><p>Eventually, I decided on a much simpler approach: no subkinding. In 1SubML, every type has exactly one kind, and kinds must match exactly when comparing types. This also resulted in having to tweak a number of other aspects of the type system compared to what I originally wrote.</p><h4>Type/constructor unification</h4><p><a href="https://blog.polybdenum.com/2025/09/02/x-design-notes-parameterized-types-and-higher-kinded-type-inference.html#viii-namespaces">I originally proposed</a> having separate namespaces for types and type constructors. In fact, even when I originally started implementing 1SubML, I still had a strict separation between types and type constructors planned, and duplicated all the type checker code to handle this. However, it quickly became unwieldy, and I realized it didn’t make any sense to do things this way anyway.</p><p>The issue is that “type” vs “type constructor” is not the only distinction that matters. What you really care about is compatibility, i.e. kinds. Distinguishing type constructors with different kinds is just as important. Therefore, there is no point in having separate namespaces for types and type constructors, unless you’re going to have a separate namespace for every <em>kind</em> of type constructor, and this didn’t exactly seem like a good idea to me.</p><p>I eventually came up with a much simpler approach. In 1SubML, type constructors are also called “types”. Everything is a “type”, just with different kinds. foo and foo[int] are <em>both</em> &quot;types&quot;, and there is a single namespace for all types, regardless of kind.</p><h3>VII. Variance annotations</h3><p>First off, a cosmetic change: 1SubML uses ^ for annotating invariant type parameters, rather than the originally proposed +-.</p><p>Second, my original posts envisioned variance annotations on newtype parameters being optional, as they are in OCaml. When no explicit variances were specified, they would just be inferred from how the parameter is used on the righthand side of the newtype definition.</p><p>There are several reasons why I decided to make variance annotations mandatory after all. First off, I realized that it would not generally be feasible to infer variances for <em>recursive</em> newtype definitions (e.g. type rec foo[T] = T -&gt; foo[T];)</p><p>Since type rec definitions were going to require explicit variance annotations anyway, I thought that it would be confusing to users if variance annotations were mandatory for recursive definitions but optional for non recursive definitions. Better to just always require them. This of course also saves a massive amount of complexity required for global kind/variance inference. And of course, having mandatory annotations also reduces the scope for errors to propagate when the user makes a mistake.</p><h3>VIII. Parameter naming</h3><p>In PolySubML (and also 1SubML), the type parameters of polymorphic function and record types are distinguished <em>by name</em>. This means that [A]. A -&gt; A and [B]. B -&gt; B are distinct function types (though you can convert between them with an explicit subsumption expression) while [A; B]. (A, B) -&gt; (B, A) and [B; A]. (A, B) -&gt; (B, A) are considered the <em>same</em> type.</p><p>Naturally, I planned to make newtype parameters work the same way. In the original plan, newtype parameters were nominal, with positional parameters just being syntactic sugar. For example, if you had type map[K; V] = ..., then map[str; int] is just shorthand for map[K=str; V=int], and you could also specify parameters by name explicitly if you wanted to (e.g. map[V=int; K=str]). However, in the final version of 1SubML, newtype parameters are purely positional and can&#39;t be specified by name.</p><p>One advantage of specifying parameters by name rather than position is that it allows you to specify only a subset of the parameters or provide <em>extra</em> parameters that will be ignored. However, with the removal of subkinding, that is now irrelevant — the parameters always have to exactly match anyway.</p><p>The <em>main</em> reason I decided on purely positional parameters was the introduction of spine constructors. Spine constructors are implicitly generated by the compiler, and thus have no explicit names for the parameters. I considered giving the parameters implicitly generated names _0, _1, _2, ... like I do for tuples, but decided that there was no point. Without subkinding, there&#39;s no real benefit to named parameters, and with spine constructors, there&#39;s a real cost in confusion and complexity to having named parameters. Therefore, it was better to just switch to purely positional parameters.</p><h3>IX. Kind annotations</h3><p>With a type constructor application, we need to know how to interpret the parameters. For a normal type like foo[int; str] where foo is an ordinary type constructor, we can just look at the declaration of foo to find its kind, and hence the variance and kind of its parameters, and then use those when parsing the parameter list (the [int; str] part).</p><p>However, what happens when the type constructor is a <em>type inference variable</em>? (e.g. _[int; str])</p><p>In the original plan, <a href="https://blog.polybdenum.com/2025/09/02/x-design-notes-parameterized-types-and-higher-kinded-type-inference.html#unknown-declarations">I proposed</a> putting annotations on the <em>parameters</em>.</p><pre>let f = fun M -&gt; (<br>    let x: M.t[+-a=int] = M.make 42;<br>    M.get x<br>);</pre><p>In this example, M.t was a type inference variable, so annotations on the parameter are required: +-a=int indicating that the int was for the parameter named a with variance +-.</p><p>However, in the actual implementation of 1SubML, I decided to flip it and require annotations on the <em>constructor</em>. In 1SubML, the constructor must always have a known type in a type constructor application, and you can annotate it with as &lt;kind&gt; if necessary.</p><p>For example</p><pre>type pair[+A; +B] = (A, B);<br><br>let p: _ as [+;+] [str; int] = pair (&quot;&quot;, 3);</pre><p>Here, _ as [+;+] annotates the inference variable _ with kind [+;+], so the compiler knows that the parameters are both covariant with kind [] (i.e. ordinary types like int or str).</p><pre>let p: any as [+;+] [str; int] = pair (&quot;&quot;, 3);</pre><p>The kind annotation and kind inference system in 1SubML is relatively simple, because I figured that realistically, users will almost never actually run into the cases where it would be necessary, and thus it doesn’t need to be polished and it is better to prioritize implementation simplicity.</p><h3>X. GADTs</h3><p>1SubML does support an OCaml-like shorthand syntax for generating wrapper functions for variant types. For example,</p><pre>type opt[+T] = | Some T | None;</pre><p>is just syntactic sugar for</p><pre>type opt[+T] = [`Some T | `None];<br>let Some = fun[T]. x: T :: opt[T] -&gt; opt `Some x;<br>let None: opt[never] = opt `None ();</pre><p>In addition to the basic variant type syntax, OCaml also supports an extended variant syntax referred to as Generalized Algebraic Data Types (GADTs). In OCaml, GADTs provide access to type equality witnesses, existential types, and altered match exhaustiveness checking behavior, among other things.</p><p>My original goal was to replicate as much of OCaml-style GADTs as possible in 1SubML. 1SubML already has native support for type witnesses and existential types, so that part would just be syntactic sugar. Just like how the ordinary variant syntax is syntactic sugar for implicitly generating a bunch of wrapper functions, the GADT syntax would be the same, except with implicitly generated witness values, existential types, etc. as applicable.</p><p>In the final version of 1SubML, I did not include any GADT shorthand syntax at all. You can still emulate GADTs by <a href="https://github.com/Storyyeller/1subml/blob/master/tests/gadt2.test">writing explicit wrapper functions</a>, but there’s no syntactic sugar for it.</p><p>One reason for this is that I realized that my original plan to mechanically generate type witnesses based on the type parameters of the GADT would not actually be useful because the functions that people actually want would normally be different from what my proposal would have generated.</p><p>Another factor is that a major goal of 1SubML is to have high quality error messages for compiler errors during type checking. Part of how 1SubML ensures good error messages is by carefully tracking the origin of everything and pointing to exactly where in the code the relevant type originated.</p><p>In cases where a type error involves implicitly generated code, this doesn’t work as well. The error message has to point to something less clear, like the newtype definition as a whole, rather than being able to show exactly where the problematic type appeared in the source code (since it never did appear in the source code for generated code).</p><p>This isn’t an absolute barrier, as 1SubML does include a number of other features (newtype definitions, mod bindings, match expressions, etc.) that are offenders here, but it’s still best to keep it to a minimum where possible. More importantly, the generated code for GADTs would be very complex, so there’s more potential for confusing type errors and explicitness is more important than in simpler cases.</p><h3>XI. The magic dot</h3><p>As mentioned previously, in addition to type witnesses and existential types, GADTs in OCaml also change the way that match exhaustiveness checking works. This means that in some cases when using GADTs, you are allowed (and in fact required) to omit some of the variants when pattern matching. In other cases, you have to include the variant in the match, but you can just put . on the right hand side instead of supplying a body for the match arm.</p><pre>type _ foo = <br>  | Foo : int foo<br>  | Bar : string foo<br><br>let f (x: int foo) =<br>  match x with<br>  | Foo -&gt; 1<br>  (* No Bar case listed at all! *)</pre><p>However, there are numerous issues with this feature.</p><p>However, with OCaml-style GADTs, that goes out the window. In the case of an unhandled match case, there is no way to know whether a) the user left it out by mistake or b) deliberately omitted it under the assumption that it is considered unreachable due to GADTs. Therefore, instead of just directly telling the user what they did wrong, the compiler has to cover both possibilities in every possible error message, even though only one will ever actually be relevant to the user.</p><p>Second, it’s a bad experience for the user. If the user expects a variant to be considered unreachable but the compiler disagrees, there’s no way to figure out <em>why</em>. The reachability logic is just a big black box and there’s no way to understand why it didn’t trigger in any particular case. Or if the compiler error messages <em>were</em> augmented to include the full reasoning of why it didn’t trigger, that would turn every single match error message into a massive wall of text, which would be just as bad.</p><p>Third, it introduces <strong>negative reasoning</strong> into the type system. The correctness of the match expression relies on the assumption that certain types <em>aren’t</em> compatible or <em>aren’t</em> inhabitable. Negative reasoning like this is not <em>inherently</em> unsound (after all, OCaml does it!) but it is very <em>risky</em>. The problem is that suddenly the soundness of your type system depends on <em>global</em> assumptions about the absence of other behavior. It’s very easy to accidentally add a type system feature or even just a library which violates this assumption.</p><p>Negative reasoning is also very <em>fragile</em>. Even in OCaml, wrapping your code in a module with abstract types will make the GADT-based match pruning no longer work because the compiler has no way to know what the underlying types of two abstract types are, and thus is forced to assume they may be compatible. Meanwhile, 1SubML has <em>subtyping</em>, meaning that many types which would be considered incompatible in OCaml <em>are</em> compatible in 1SubML.</p><p>In light of these issues, even the “magic dot” feature that I originally proposed for 1SubML was a <em>very</em> watered down version of what OCaml allows. However, that didn’t really solve the issue. Watering it down just meant that the proposed feature offered almost no <em>benefit</em> while still incurring all the <em>costs</em>. Therefore, I decided it was best to just leave it out entirely.</p><h3>XII. Pattern matching algorithms</h3><p>The algorithms <a href="https://blog.polybdenum.com/2025/09/15/x-design-notes-pattern-matching-i.html">I originally proposed</a> for pattern matching were a bit of a mess. The problem is that I was trying to come up with a <em>single</em> algorithm to do three different things — exhaustiveness checking, reachability checking, <em>and</em> code generation.</p><p>I later realized that it was possible to simplify the algorithms and make them more accurate by using different algorithms for each task.</p><p>For example, the <em>order</em> of match arms is significant for reachability checking and for code generation, but it doesn’t matter at all for exhaustiveness checking. For exhaustiveness checking, all you care about is that every possible case is handled by <em>at least one</em> match case. The order of the match arms determines which arm will be taken during execution, but that doesn’t matter at all for exhaustiveness checking.</p><h3>XIII. Or patterns</h3><p>I originally envisioned handling or patterns as actual patterns, similar to OCaml. Since nested patterns can lead to exponential type checking, my original proposal was to just limit or patterns to a single instance per match arm. In my research, every <em>example</em> of or patterns in OCaml that I was able to find used only a single or pattern anyway, so this is unlikely to be a problem in practice.</p><p>However, an ad hoc “one instance per match arm” restriction is arbitrary and complicated to enforce and implement, so I later devised a more elegant approach: instead of | being a <em>pattern</em>, I just allowed multiple match cases to <em>share</em> a match arm body.</p><p>For example:</p><pre>let f = fun x -&gt; match x with <br>    | `A (x, y)<br>    | `B y          -&gt; y<br>;</pre><p>In OCaml, this would be interpreted as a single giant or pattern (`A (x, y) | `B y). In 1SubML however, this is interpreted as <em>two different match cases</em> (`A (x, y) and `B y) which happen to share the same <em>body</em> (the -&gt; y).</p><p>I especially like this solution because OCaml <em>already</em> uses | to separate match arms <em>anyway</em>. Allowing multiple match cases to share a body achieves the same effect with <em>less syntax</em> than the OCaml equivalent.</p><p>Since | is not actually a pattern in 1SubML, there&#39;s no way to nest them in the first place, and it automatically means they can&#39;t be used outside of match expressions (e.g. in function argument patterns or destructuring assignment patterns).</p><p>Another consequence is that in 1SubML, the “or”ed together patterns can each contain individual <em>guard expressions</em>, something that is impossible in OCaml:</p><pre>let f = fun x -&gt; match x with <br>    | `A y when y == 2<br>    | `A   when 1 == 5<br>    | _                -&gt; x<br>;</pre><h3>XIV. Other patterns</h3><p>1SubML does support alias patterns, e.g. the as p in let (x, y) as p = (1, 2);. However, unlike the original plan, they are only allowed after record or tuple patterns, since it was unclear what the semantics should be for variant patterns, and it seemed like record patterns are the only case where alias patterns are actually useful anyway.</p><p>Lastly, I originally planned to add a Rust-style if let feature, but that didn&#39;t make it in. To be honest, I just completely forgot about it.</p><h3>XV. Constructor of</h3><p>Apart from the differences discussed above, there were some unplanned features that I had to add due to the switch to spine constructors.</p><p>The first was constructor-of!(). One of the major guarantees of 1SubML is the <em>writeable types property</em>, which requires that any inferred types can always also be written explicitly. Since there is normally no way to explicitly refer to the type constructors generated for polymorphic types, I added constructor-of!() as a quick hack to enable that:</p><pre>alias foo = constructor-of!([T]. (T, any) -&gt; (T, any));<br><br>let f: foo[str; str] = fun[T] x: (T, str) :: (T, str) -&gt; x;<br>let f: foo[any; int] = fun[T] x: (T, _) :: (T, _) -&gt; (x._0, 12213);</pre><p>The second extra feature was invariant pair shorthand syntax, which will require some background explanation.</p><h3>XVI. Invariant pairs</h3><p>1SubML, like PolySubML and Cubiml before it, is based on <a href="https://www.cs.tufts.edu/~nr/cs257/archive/stephen-dolan/thesis.pdf">Algebraic Subtyping</a>, and thus the underlying type system is <em>polarized</em>, and types are always in covariant or contravariant position, never <em>in</em>variant. To make things convenient, the <em>user-facing</em> syntax however does support invariant types, with invariant types being represented as a (covariant, contravariant) <em>pair</em> under the hood.</p><p>For example, a mutable record field {mut x: R &lt;- W} has a pair of types, R &lt;- W, where R is the type that can be read from the field and W is the type that can be written to the field. For convenience, there is the shorthand syntax {mut x: int}, which is equivalent to {mut x: int &lt;- int} except without the need to write the int twice.</p><p>In PolySubML, this shorthand is pure syntactic sugar, but thanks to the introduction of spine constructors, that is no longer the case in 1SubML. With spine constructors, the polymorphic parts of a type have to match <em>exactly</em>, which means that [T]. T -&gt; {mut x: T} and [T]. T -&gt; {mut x: T &lt;- T} are <em>distinct types</em>.</p><p>By itself, this isn’t a problem. The issue arises from the way that newtype definitions are desugared.</p><h4>Newtypes with invariant parameters</h4><p>When a newtype definition contains an <em>invariant</em> parameter (specified by ^), that parameter actually represents a <em>pair</em> of parameters under the hood. A parameter T becomes the pair T and T$, where T is used in covariant contexts and T$ is used in contravariant contexts.</p><p>For example, type foo[^T] = T -&gt; T; is roughly equivalent to type foo[+T;-T$] = T$ -&gt; T;.</p><p>Although they represent a pair of parameters under the hood, invariant parameters are still specified as a single parameter in the syntax. As with the mutable field example, you can pass either a single type ( int) or a pair of types (int &lt;- int). For example:</p><pre>type foo[^T] = T -&gt; T;<br>type bar[+V; -U] = U -&gt; V;<br><br>let a: foo[int] = foo (fun x -&gt; x);<br>let b: foo[int &lt;- int] = foo (fun x -&gt; x);<br>let c: foo[str &lt;- bool] = foo (fun (x: bool) -&gt; &quot;Hello&quot;);<br><br>// bar has two parameters, so types are passed separately:<br>let d: bar[str; bool] = bar (fun (x: bool) -&gt; &quot;Hello&quot;);</pre><p>Newtype definitions also implicitly generate functions to create and unwrap the new type:</p><pre>type foo[^T] = T -&gt; T;<br><br>// Wrap function has type [T; T$]. (T -&gt; T$) =&gt; foo[T$ &lt;- T] <br>let _: [T; T$]. (T -&gt; T$) =&gt; foo[T$ &lt;- T] = foo;<br><br>// Unwrap function has type [T; T$]. foo[T &lt;- T$] =&gt; (T$ -&gt; T)<br>let _: [T; T$]. foo[T &lt;- T$] =&gt; (T$ -&gt; T) = foo$;</pre><h4>Slash pair syntax</h4><p>Now comes the problem. What are the types for the functions generated by a newtype definition like type [^T] = {mut x: T};?</p><p>The source level T parameter is replaced by the underlying covariant T parameter when used in covariant contexts, and T$ in contravariant contexts. The problem is that here, those occur in the same location! If the newtype were instead defined as {mut x: T &lt;- T}, there would be no problem, because one half would be replaced by T and the other half by T$. But with the shorthand syntax, this is impossible.</p><p>Therefore, 1SubML supports a special slash pair syntax A/B in polymorphic function types. A/B represents the type A when used covariantly and the type B when used contravariantly. This syntax essentially only exists so that the functions generated by newtype definitions can have writable types, but users can also use it on their own if they want to for some reason.</p><p>With the slash pair syntax, it is now possible to write the above function types:</p><pre>type foo[^T] = {mut x: T};<br><br>// Wrap function has type [T; T$]. {mut x: T/T$} =&gt; foo[T$ &lt;- T]<br>let _: [T; T$]. {mut x: T/T$} =&gt; foo[T$ &lt;- T] = foo;<br><br>// Unwrap function has type [T; T$]. foo[T &lt;- T$] =&gt; {mut x: T/T$}<br>let _: [T; T$]. foo[T &lt;- T$] =&gt; {mut x: T/T$} = foo$;</pre><p>Incidentally, this was another problem that caused many issues during development. Even after implementing the initial version of it, I wasn’t happy and completely redesigned and rewrote it. <strong>Twice</strong>.</p><p>It’s amazing how much trouble and complexity can be caused by an obscure feature that is never even actually meant to be used and just exists to fill a gap in the type system. (To be fair, the same was true of the type union/intersection feature in PolySubML as well.)</p><h3>Conclusion</h3><p>Even after spending weeks writing the original plans for 1SubML, there were a number of unresolved issues, and many more changes required by issues I ran into during development. On the one hand, it’s an illustration of “no plan survives contact with the enemy”, but on the other hand, the final version of 1SubML is still <em>basically</em> the same as the original vision, and I managed to fulfill all the original goals I had for the language.</p><p>Anyway, I hope this post proved informative. Usually you only get to see the finished product and don’t know anything about how things changed during development or <em>why</em> they ended up the way they did.</p><p><em>Originally published at </em><a href="https://blog.polybdenum.com/2026/04/05/1subml-plan-vs-reality.html"><em>https://blog.polybdenum.com</em></a><em> on April 5, 2026.</em></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=899c17183afc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[My blog has moved off Medium]]></title>
            <link>https://medium.com/@robertgrosse/my-blog-has-moved-off-medium-e901e336a1d5?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/e901e336a1d5</guid>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Fri, 06 Feb 2026 17:23:55 GMT</pubDate>
            <atom:updated>2026-02-06T17:23:55.166Z</atom:updated>
            <content:encoded><![CDATA[<p>In mid-2020, I moved off of Medium to <a href="https://blog.polybdenum.com/">a custom site</a> in order to offer a better experience to readers (no ads or popups or other Medium crap).</p><p>Here are some of the most popular posts I’ve written since then, in case people still following me on Medium might be interested:</p><ul><li><a href="https://blog.polybdenum.com/2020/07/04/subtype-inference-by-example-part-1-introducing-cubiml.html"><strong>Subtype Inference by Example Part 1: Introducing CubiML</strong></a><strong>: </strong><em>A detailed tutorial about how to implement global type inference based on Algebraic Subtyping, with code examples.</em></li><li><a href="https://blog.polybdenum.com/2021/05/05/how-i-hacked-google-app-engine-anatomy-of-a-java-bytecode-exploit.html"><strong>How I Hacked Google App Engine: Anatomy of a Java Bytecode Exploit</strong></a></li><li><a href="https://blog.polybdenum.com/2022/04/25/when-type-annotations-are-code-too.html"><strong>When Type Annotations Are Code Too</strong></a></li><li><a href="https://blog.polybdenum.com/2023/03/05/fixing-the-next-10-000-aliasing-bugs.html"><strong>Fixing the Next 10,000 Aliasing Bugs</strong></a>: Why even garbage collected languages need a borrow checker.</li><li><a href="https://blog.polybdenum.com/2023/08/01/how-i-came-second-out-of-999-in-the-salem-center-prediction-market-tournament-without-knowing-anything-about-prediction-markets-and-what-i-learned-along-the-way-part-1.html"><strong>How I came second out of 999 in the Salem Center prediction market tournament without knowing anything about prediction markets, and what I learned along the way</strong></a></li><li><a href="https://blog.polybdenum.com/2024/06/07/the-inconceivable-types-of-rust-how-to-make-self-borrows-safe.html"><strong>The Inconceivable Types of Rust: How to Make Self-Borrows Safe</strong></a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e901e336a1d5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Improving compile speed: the dark arts]]></title>
            <link>https://medium.com/@robertgrosse/improving-compile-speed-the-dark-arts-c4d2a276197a?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/c4d2a276197a</guid>
            <category><![CDATA[complexity]]></category>
            <category><![CDATA[programming-languages]]></category>
            <category><![CDATA[compiler-optimization]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Wed, 01 Apr 2020 12:29:21 GMT</pubDate>
            <atom:updated>2026-02-06T16:55:51.558Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2020/04/01/improving-compile-speed-the-dark-arts.html"><em>here</em></a><em> for the updated post.</em></p><p>So you’re designing a statically typed programming language. You recognize the importance of fast compilation to adoption of your language and have slaved over your compiler, optimizing it every way you can think of, but it’s still not as fast as you’d like. Luckily, I’m here to reveal some common pitfalls and underappreciated techniques for improving compilation speed.</p><h4>Problem #1 — deeply nested scope resolution</h4><p>Most programming languages have <em>scopes</em> which determine which points in the program can access a given variable, and allow scopes to be nested, so that an inner scope can automatically access anything in the enclosing scope without specifically mentioning it.</p><p>In order to compile this code, the compiler must figure out which identifiers in the source code refer to which variables in which scopes. The typical implementation strategy is to maintain a dictionary/hash table for each scope with the variables defined in that scope. When scopes are nested, there are two common approaches — either eagerly copy all the items from the outer scope dictionary into the dictionary for the inner scope, or chain lookups so that any variable resolution that isn’t found in the inner scope dictionary falls back to checking the dictionary for the outer scope.</p><p>Unfortunately, both these approaches suffer from poor O(n²) performance in the presence of deeply nested scopes. The more scopes you have, the more time the compiler spends copying the same variables down into each successive layer or alternatively, the more time it spends walking back up the chain for each failed variable lookup. This means that even small amounts of code can take forever to compile if they use a lot of nesting.</p><p>One possibility is to use <a href="https://en.wikipedia.org/wiki/Persistent_data_structure#Trees">a persistent balanced tree data structure</a> to ensure worst case O(nlogn) performance. However, this decreases performance considerably in the common case and is more work to implement and maintain. Luckily, there is a much simpler solution:</p><h4>Solution: require indentation for nested scopes</h4><p>Although Python is not a statically compiled language, it has lessons for anyone seeking to make their language fast to compile. Specifically, it solves the O(n²) scope resolution problem by requiring indentation for nested scopes.</p><pre><strong>def</strong> favourite_colour(colour):<br>    <strong>def</strong> decorator(func):<br>        <strong>def</strong> wrapper():<br>            print(colour)<br>            func()<br>        <strong>return</strong> wrapper<br>    <strong>return</strong> decorator</pre><p>To understand how this works, consider how compilation speed is measured. The most common figures quoted are in lines of code/second, but this is not a fair unit of measurement because lines of code can have varying lengths. A more reasonable metric for compilation speed is bytes/second, since every byte in the source code has to be processed at least once. This distinction can also be obviated by imposing a maximum line length, in which case the two measures would match up to a constant factor.</p><p>The n in the O(n²) figures given above is shorthand for the number of scopes and variable definitions and references. However, the actual numerator for compilation speed is not the number of scopes, but the number of bytes of source code. Thanks to the fact that each nested scope is required to be indented to a higher level than the previous, each line of code has length at least linear in the number of previous scopes, which means that the size of the source code is also ~O(n²) in the number of scopes, which means that the actual compilation speed in bytes/second is linear, no matter how many scopes you use.</p><p>The majority of mainstream programming languages fare poorly on this front due to a slavish adherence to C-style syntax with few restrictions on the placement and quantity of whitespace. However, there are efforts underway to improve this state of affairs. Even if your programming language syntax is already set in stone, you can change the de-facto syntax by promulgating an official source code formatter which inserts the appropriate indentation, thus making your compiler perform well on typical, i.e. properly formatted code.</p><h4>Problem #2 — generics</h4><p>Most performance oriented languages cannot escape the siren song of supporting convenient code reuse via some sort of “template” or “generics” feature that allows programmers to use the same code with different types in a type safe and runtime-efficient manner.</p><p>Unfortunately, this is also one of the most notorious killers of compilation speed in languages that support them, because what looks like a single innocuous block of code in the source must be duplicated by the compiler under the hood for each distinct usage. In cases where one generic function calls another generic function, this can lead to exponential increases in the effective size of the code, and consequent compilation time, compared to what is actually present in the source code.</p><p><a href="https://github.com/Storyyeller/IntercalScript">IntercalScript</a> pioneered an approach to solve this problem syntactically. In IntercalScript, each generic leaf function must be prefixed by a $. Each generic function which calls other generic functions must be prefixed by a number of $s equal to the total among generic functions it calls. This has the result that the number of $s, and hence source code size, increases exponentially with the nesting depth of generic functions, and thus the time required for compilation is polynomial in the size of the source code.</p><pre>{-# language rank1-types #-}<br><br>f = $funct(x) x(x) end;<br>f2 = $$funct(x) f(f(x)) end;<br>f3 = $$$$funct(x) f2(f2(x)) end;<br>f4 = $$$$$$$$funct(x) f3(f3(x)) end;<br>f5 = $$$$$$$$$$$$$$$$funct(x) f4(f4(x)) end;</pre><p>The $ rule is simple and easy to understand, but not all that attractive from a code aesthetics perspective. However, there are alternatives that can achieve the same effect while being more in line with traditional programming language syntax. For example, you could require type signatures for generic functions that include the complete type signatures for nested function calls with no affordances for type aliasing, inference, or otherwise compressing the signatures.</p><h4>Problem #3 — macros</h4><p>Macros are a less common feature, but absolutely kill performance in the languages that implement them. It might seem like a good idea to let users customize the language arbitrarily, but it is one of the worst things you can do for compilation speed. You should be building a compiler, not an ad-hoc ill-considered scripting language interpreter for whatever garbage your users see fit to execute on every single compilation.</p><p>Instead of integrating compile time code generation into your language, you should strive for your language to be a platform which can be targeted by third party code generation tools and transpilers, as it is the <em>output</em> of those tools that will serve as input to your compiler, and thus be the metric that your compilation speed is measured against.</p><p>To facilitate this, you should keep your language as simple as possible. Simplicity has a lot of benefits — it saves you time in developing the language, and it saves your users time in learning the language and it saves them time when developing tools to work with your language.</p><p>If a feature that users like is absent from your language, they can always use third party code generation tools to work around this. Not all features are created equal. When deciding what to include and what to leave out, you should strongly consider avoiding performance pitfall features such as generics entirely. In general, you want your language to be powerful enough that code generation tools can express anything necessary in your language, but not so powerful that they can express it <em>concisely</em>.</p><p>If you do intend for your language to become a platform, be extra careful with the design, as the kinds of code you are asked to compile may not be what you expect. For example, a human would be unlikely to write code with deeply nested scopes (see #1), but code generators may not be so considerate. If it is possible in your language, you should expect to see it and be able to handle it efficiently in the compiler.</p><h4>But isn’t this cheating?</h4><p>If you are not accustomed to these techniques, they may strike you as “dishonest” or “underhanded”. However, they have precedent in other design philosophies that pass largely without objection.</p><p>To wit: some languages forbid user defined operator overloading under the rational that it can negatively effect runtime performance in ways that are not readily apparent from the source code. It is considered desirable that runtime performance be predictable from the source code syntax, with things that could be slow correspondingly conspicuous in the source code. Even in the case of C++, which does have operator overloading, there have been <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2137r0.html">suggestions</a> that it adopt predictability of runtime performance as an explicit goal.</p><p>While runtime performance of the compiled code is of course important, there has also been increasing appreciation for the importance of compilation speed as well. Excessive compilation times are highly disruptive to developer flow and productivity. Therefore, if it is worth warping the syntax of a language to make runtime performance more predictable, then it is only logical to make predictability of compilation speed a consideration in the design of the language syntax as well.</p><h4>Conclusion</h4><p>I hope that this article has been helpful. As you can see, some of these techniques have already been employed by popular existing programming languages, but there is obviously a lot of room for improvement. I can’t wait to see what the collective ingenuity of the programming language community can come up with.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c4d2a276197a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solution to the besquare crypto challenge]]></title>
            <link>https://medium.com/@robertgrosse/solution-to-the-besquare-crypto-challenge-c5d8b7eab6ce?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/c5d8b7eab6ce</guid>
            <category><![CDATA[security]]></category>
            <category><![CDATA[number-theory]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Mon, 17 Dec 2018 16:42:48 GMT</pubDate>
            <atom:updated>2026-02-06T16:54:42.336Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2018/12/17/solution-to-the-besquare-crypto-challenge.html"><em>here</em></a><em> for the updated post.</em></p><p>In 2014, I wrote a bunch of cryptography challenges for a competition at my college, and also posted them online in case anyone else was interested in trying to solve them. Recently, someone contacted me asking for help with one challenge, named besquare. I realized that I never posted solutions for most of the problems, so I decided to write a post explaining how to solve this challenge. (If you want to try it yourself before reading the answer, you can find the code <a href="https://github.com/nickbjohnson4224/greyhat-crypto-ctf-2014/blob/master/challenges/besquare/besquare.py">here</a>)</p><p>The besquare challenge was unique in that rather than being written from scratch, it was inspired by a mishap during the 2013 CSAW qualifiers. CSAW (Computer Security Awareness Week) is an annual information security competition for college students held by NYU Poly. The competition includes various categories of hacking related challenges, including cryptography. As my team’s cryptography expert, I naturally tackled the crypto challenges, but there was one problem that I couldn’t solve no matter how hard I tried, due to a foolish misunderstanding of the problem. In the process, I came up with a potential attack for what I thought the problem was, so when it came time to write my own crypto challenges, I decided to take advantage of my mistake and use a modified version of the CSAW problem.</p><p>Before I get into my version of the problem, I will first explain the solution to the original problem from CSAW (written by Ben Agre). The basic idea is that there is a server which spies can log into using a special cryptographic protocol, and you have to find a weakness in the protocol. The code provided for the challenge is as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e11a806dedfd7670fd8996c9c45c91b2/href">https://medium.com/media/e11a806dedfd7670fd8996c9c45c91b2/href</a></iframe><p>This is an implementation of a custom password-authenticated key exchange (PAKE) protocol. The server and the client (spy) have a shared secret — the spy’s password. Using this shared secret, they can exchange messages to agree on a temporary secret key in a way that is not vulnerable to eavesdroppers.</p><p>The particular protocol in this challenge is presumably intended to function as follows. Note that only the code for the server is provided in the challenge. I inferred the client portion of the protocol here, though it doesn’t actually matter for the purposes of the challenge.</p><p>Setup: Client and server agree on a shared secret (the password) and a public shared prime modulus, N.</p><p>Client:<br>Chooses an integer i and generate a secure random number a. Compute the client ephemeral key c = iᵃ mod N and then send i and c to the server.</p><p>Server:<br>Verify that 1 &lt; i &lt; N/2 and c ≠ 0 mod N.<br>Compute salt = hash(i)<br>Compute salted password hash h = hash(salt, password)<br>Generate a secure random number b<br>Compute server ephemeral key s = 3iʰ + iᵇ mod N<br>Send salt and s to the client.<br>(Sending the salt is not actually necessary here, since it is based only on information available to the client. Presumably, it was designed this way so that the salt algorithm could be changed without needing to update the client.)</p><p>Client:<br>Compute h = hash(salt, password)<br>Compute j = s − 3iʰ mod N<br>(This is just temporary value to split the computation up for clarity. Here, j is just iᵇ mod N. Note that the client does <strong>not</strong> know the value of b, only iᵇ)<br>Compute temporary value e = a + h × hash(c, s)<br>Compute agreed key k = jᵉ mod N<br>Compute “genned key” g = hash(hash(N) ^ hash(i), hash(i), salt, c, s, a)<br>(Note that every component of g is visible to an eavesdropper with the exception of a, so a and g are roughly equivalent in terms of security)<br>Send g to the server</p><p>Server:<br>Compute temporary value m = b × h × hash(c, s)<br>Compute agreed key k = cʳ + iᵐ mod N<br>Compute “genned key” g = hash(hash(N) ^ hash(i), hash(i), salt, c, s, a)<br>Verify that the computed value of g matches that received from the client</p><p>For the purpose of the challenge, the goal is to successfully impersonate the client without knowing the password. We also do not have any recorded legitimate sessions available, so the only tool at our disposal is the ability to send different values of i and c to the server and see what values of s we get back.</p><p>First off, we can send c=1 to simplify the calculations. A legitimate client needs to choose c to be a random power of i in order to maximize security, but we are under no such constraints, and using c=1 means there is one less step we have to worry about at the end. So I will assume that c=1.</p><p>Next, the security of the system rests on us not being able to determine iᵇ from s without knowing the password. If we have a way to figure out the value of iᵇ, we can easily calculate the agreed key and hence break the system.</p><p>If we were able to set i = 1, then we would of course know iᵇ because it would always be 1. Unfortunately for us, the server requires that i ≥ 2. Likewise, if we were able to set i = N-1 (and hence i=-1 mod N), we would know that iᵇ is either 1 or -1 (mod N), and could just keep trying until we win the coin flip. Unfortunately, this possibility is also blocked by the check that i &lt; N/2.</p><p>So our goal is to find a value of i such that 1 &lt; i &lt; N/2 and iᵇ mod N has only a small number of possible values. Luckily, we can do this with a bit of number theory.</p><p>The key is that N is a) prime and b) one more than a multiple of 4. As the actual value of N is 617 digits long, I’ll demonstrate with a smaller prime, 13, instead. For example, here are the powers of 2 mod 13.</p><p>1 2 4 8 3 6 12 11 9 5 10 7 1</p><p>We have 2 ** 12 = 1 mod 13, and hence the cycle repeats. 2 ** 14 = 2, 2 ** 15 = 4, etc. (I am using ** for exponents since Medium doesn’t allow proper math notation.) You might wonder whether this is a coincidence, but in fact, raising any (nonzero) number to different powers modulo a prime will eventually yield 1. The smallest nonzero power k such that xᵏ = 1 mod p is known as the order of x (in the multiplicative group of integers modulo p). So ord(2) = 12. Since there are only p−1 possible nonzero numbers mod p, the highest possible order is p−1. A number x with ord(x) = p − 1 will generate every possible number mod p as a power of x and hence is known as a generator. So 2 is a generator in the group of integers mod 13.</p><p>In the previous example, all the powers of 2 were shown between 0 and 12. However, when working with modular arithmetic, the choice of range is arbitrary. Instead of using the range 0 to p-1, using the range -(p-1)/2, p-1/2 makes the patterns clearer. So for example, here are the same powers of 2 mod 13 as before, but now shown in the range -6 to 6.</p><p>1 2 4 -5 3 6 -1 -2 -4 5 -3 -6 1</p><p>You can see that the middle number is -1, which makes sense, since we know that 2 ** 12 = 1, and hence (2 ** 6)² = 1 mod 13. We know that -1 must appear as some power of 2, and this is the only place it can appear. Since 2 ** 6 = -1, this also means that the second half must be the same as the first half with the signs flipped, as 2 ** 7 = (2 ** 6) × (2 ** 1), 2 ** 8 = (2 ** 6) × (2 ** 2) etc.</p><p>This will be true regardless of the original number. For example, if we choose a different generator, 6, the same pattern emerges.</p><p>1 6 -3 -5 -4 2 -1 -6 3 5 4 -2 1</p><p>Now what happens if we choose a number that is not a generator? For example, take the powers of 4 mod 13.</p><p>1 4 3 -1 -4 -3 1 4 3 -1 -4 -3 1</p><p>As you can see, this repeats every 6 steps instead of every 12. You may also notice that this is just the same as the powers of 2, except with every other number skipped, which makes sense since 4 = 2², so the kth power of 4 is the 2k-th power of 2. This means that the powers of 4 repeat every 12/2 = 6 steps.</p><p>At this point, you may object — isn’t every number a power of 2? How can 6 be a generator then? The answer is that 6 = 2 ** 5, and 5 does not share any factors with 12, so if you take every 5th power of 2, you’ll skip past the end and wrap around instead of hitting it cleanly. The end result is that you get a full 12 powers of 6. But if you raise 2 to any multiple of 2 or 3, you will get a non-generator with order at most 12/2=6 or 12/3=4 respectively.</p><p>This also implies that the number of generators mod p is equal to the number of numbers mod <em>p−1</em> which are coprime to p−1 (i.e share no common factors with p−1). 12 has an unusually large amount of factors relative to its size, so there aren’t many generators mod 13, but most numbers don’t have so many factors, which means that generators are plentiful and easy to find by chance. For example, consider the numbers modulo the prime 311. p−1 = 310 has the factorization 2 × 5 × 31, which means that there are (2−1) × (5−1) × (31−1) = 120 generators. If you tried numbers randomly, you’d find a generator after only 2.6 tries on average.</p><p>At any rate, all this number theory lets us find a number modulo N with a very <em>low</em> order, and in particular, a “fourth root” of 1 modulo N. The crucial fact is that not only is N prime, but N = 1 mod 4. Let N = 1 + 4k. Then any generator g mod N will have ord(g) = N−1 = 4k. This implies that ord(gᵏ) = 4k/k = 4. So we just found a number gᵏ which is not 1, not -1, and has only 4 possible powers mod N. If the number gᵏ ends up &gt; N/2, we can just use -gᵏ instead, which will also be a fourth root of 1.</p><p>For example, consider the process with N=13 and suppose we chose g=2. Then we have k=3 and gᵏ = 8 mod 13. 8 &gt; 13/2, so it will be rejected by the 2 &lt; i &lt; N/2 check in the original server code. However, -8 = 5 mod 13 works just as well and is within the range. Sure enough, if we check the powers of 5 mod 13, there are only 4 possible values.</p><p>1 5 -1 -5 1</p><p>So now we have our method to crack the original problem — choose a number x arbitrarily, and calculate xᵏ mod N, where N = 4k + 1. If we get 1 or -1, try again. Then use that value as i and submit it to the server. We will get back s, and then guess a value for iᵇ. Since there are only 4 possible values, we will have a 25% success rate guessing randomly, and log in successfully after an average of four tries.</p><p>Overall, it’s a simple problem if you’ve studied number theory. So what went wrong? I saw that N used the variable name “N” instead of “P” and assumed that that meant that it must be composite, rather than prime. All the information I could find online and all the attacks I could think of involved the case of a prime modulus, but it still never occurred to me to simply check whether N was prime or not. Eventually, I came up with an offline dictionary attack which works even when N is composite, but since the CSAW problem was designed assuming a full break, it used a strong password, and hence, my dictionary attack failed. But when it came time to write my own crypto challenges, I decided not to let the attack I came up with go to waste, which brings us to the besquare challenge.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/393c20497562178c08da7ab21ad5e2e6/href">https://medium.com/media/393c20497562178c08da7ab21ad5e2e6/href</a></iframe><p>The besquare code is functionally identical to the original CSAW challenge except for the value of N, which I obviously changed to be composite. The attack described in the previous section doesn’t work for the besquare challenge because there is no known way to efficiently find low order elements modulo a composite number (without knowing its factorization). Instead, we’ll have to try something different.</p><p>To provide a hint, I also changed the welcome message when you connect to the server. The new message says “Note: passwords must contain at least one uppercase, one lowercase, and one digit. Sorry for the inconvienence but we’ve had problems with weak passwords lately.” This was intended as a hint that the password for the besquare challenge (unlike the CSAW challenge) is weak, i.e. guessable.</p><p>However, trying to brute force the password will quickly run into the issue that the server uses proof of work and rate limiting (carried over unchanged from the CSAW challenge). This means that there is a limit of how quickly you can test guesses against the live server. The challenge is to find a way to test password guesses quickly without touching the server each time. This is known as an offline dictionary attack.</p><p>The only piece of information we can get back from the server is s = 3iʰ + iᵇ mod N, where h is the hash of the password and b is a secret random number. If we knew the value of b for a given s, we could easily test candidate passwords by hashing them and seeing whether iʰ matches up to the expected value. However, the whole point of the protocol is that b is a number which is known only to the server.</p><p>Although b is a perfectly random number, iᵇ is not completely random — we know it is some power of i, which is chosen by us. It is impossible to find a low order value to use for i as in the previous attack, so no matter what we do, iᵇ will have a very large number of possible values. But what if we had some way of distinguishing values that were some power of i from values that weren’t?</p><p>For example, suppose we had a function that could determine whether any given number was a square mod N. This isn’t as trivial as it sounds, since the modulus means you can’t just take the square root and see if it is an integer. For a given value x, you are trying to determine whether there exists some r and k such that r² = x + kN. If there is, x is a <em>quadratic residue</em> mod N, otherwise it is called a <em>quadratic nonresidue</em>.</p><p>Armed with a quadratic residue testing function, we could conduct an offline dictionary attack. We would just choose a square number for i. Since any power of a square is still a square, iᵇ is guaranteed to be a quadratic residue, regardless of the value of b. This means that we can test candidate passwords by computing s − 3iʰ and checking if it is a quadratic residue or not. If our guess is correct, it will always be a quadratic residue. If our guess is incorrect, s − 3iʰ will effectively be a random number, so it may or may not be a quadratic residue. Therefore, we can just collect a bunch of (i, s) pairs from the server, and test each candidate password by seeing if any of the remainders are quadratic nonresidues. The name of the problem (besquare) itself was even intended as a hint that square numbers are involved in the solution.</p><p>So are we done? Not quite. As it turns out, there is no known way to test quadratic residues modulo a composite (of unknown factorization). In fact, there are cryptosystems which rely on the hardness of this problem for their security. However, number theory once again comes our rescue with a slight workaround.</p><p>Since “function that checks for quadratic residues” is a bit of a mouthful, mathematicians introduced a function called <a href="https://en.wikipedia.org/wiki/Legendre_symbol">the Legendre symbol</a> for this purpose. It is typically written vertically like a fraction, but since Medium forbids mathematical notation and the normal notation is confusing anyway, I will write it as Leg(x, n) instead. This function is defined by the rules</p><p>Leg(x, n) = 1 if x is a quadratic residue mod n<br>Leg(x, n) = -1 if x is a quadratic nonresidue mod n<br>Leg(x, n) = 0 if x shares a factor with n</p><p>One obvious property is that the Legendre symbol is multiplicative — that is Leg(a × b, n) = Leg(a, n) × Leg(b, n) for any a and b. Furthermore, it is always 1 or -1 for numbers coprime to n. (We will ignore the case of numbers not coprime to n, because in the unlikely event that we ever stumble on one, it means we have found the factorization of N anyway and can thus solve the problem through the previous attack).</p><p>As mentioned above, the Legendre symbol can’t be computed for composite n without knowing the factorization of n. However, it is easy to compute for prime n. In fact, since we know that prime moduli always have a generator, we know that the quadratic residues modulo a prime are exactly the even powers of a generator, and the nonresidues are the odd powers of that generator. Furthermore, we know that a quadratic residue must always have order at most (p-1)/2 and hence x ** (p-1)/2 = 1 mod p for any residue x. Likewise, x ** (p-1)/2 = -1 mod p for any non residue x. So we can compute the Legendre symbol for prime moduli with a single modular exponent.</p><p>What about the composite case? Any modular equation must also hold modulo any factor of the modulus. For example, suppose n = pq where p and q are different prime factors. Then x is a quadratic residue mod n if there is some y such that y² = x mod n. However, if this is true, then it is also true that y² = x mod p and y² = x mod q, since any multiple of n is also a multiple of p and of q. Therefore, Leg(x, pq) = 1 if and only if Leg(x, p) = 1 and Leg(x, q) = 1. If we knew the factors of n, we could easily calculate this, but we don’t so we can’t.</p><p>Another mathematician, Jacobi, introduced <a href="https://en.wikipedia.org/wiki/Jacobi_symbol">the Jacobi symbol</a> (here written Jac(a, n)), as a slight modification of the Legendre symbol. The Jacobi symbol is defined the same way as the Legendre symbol for prime moduli:</p><p>Jac(x, p) = 1 if x is a quadratic residue mod p<br>Jac(x, p) = -1 if x is a quadratic nonresidue mod p<br>Jac(x, p) = 0 if x is a multiple of p</p><p>However, the Jacobi symbol differs in its treatment of composite moduli. For a composite n with factorization n = pq where p and q are primes, it is defined as Jac(x, pq) = Jac(x, p) × Jac(x, q). (It is defined for composite numbers with more factors in a similar manner.)</p><p>This is almost the same as the Legendre symbol, but with one crucial difference. Recall that Leg(x, pq) = 1 if and only if Leg(x, p) = 1 <strong>and</strong> Leg(x, q) = 1. However, Jac(x, pq) = Jac(x, p) × Jac(x, q), which means that Jac(x, pq) = 1 if Jac(x, p) = 1 and Jac(x, q) = 1 <strong>or</strong> if Jac(x, p) = -1 and Jac(x, q) = -1.</p><p>In the later case, x is not a quadratic residue mod n, despite the fact that Jax(x, n) = 1. Therefore, if Jac(x, n) = -1, x is guaranteed to be a nonresidue, but if Jac(x, n) = 1, there is no way to know whether x is a residue or not.</p><p>Another implication is that for any n, half the numbers coprime to n will have Jac(x, n) = 1 and half will have Jac(x, n) = -1. In the prime case, this is easy to see, since these are just the even and odd powers of a generator respectively. In the composite case, this follows from induction.</p><p>This means that if we have a way to calculate the Jacobi symbol, we can use it in place of the Legendre symbol in our original offline password guessing attack. If i is a square number, then Jac(iᵇ, n) = 1 for any b. But if we guess wrong, the calculated remainder s − 3iʰ will effectively be a randomly chosen number mod n and therefore a 50–50 chance of Jac(x, n) = 1 or -1. Therefore, we have a way to distinguish our password guesses as before. (I’m not sure if there is any way to actually prove that the remainder is effectively randomly distributed, but it works this way in practice so ¯\_(ツ)_/¯ ).</p><p>It may not seem like we’ve gotten anywhere, since the definition of the Jacobi symbol still requires the factorization of n to calculate. However, a famous result in number theory, <a href="https://en.wikipedia.org/wiki/Quadratic_reciprocity">The Law of Quadratic Reciprocity</a>, provides a method to efficiently calculate the Jacobi symbol, even without knowing the factorization of the modulus. It’s a bit complicated, but you can find the formulas on <a href="https://en.wikipedia.org/wiki/Jacobi_symbol">Wikipedia</a>. Or you can see the implementation I wrote when solving the problem below (I made sure I could solve every challenge myself before posting them).</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e5795999a2411ce01326097d70667b56/href">https://medium.com/media/e5795999a2411ce01326097d70667b56/href</a></iframe><p>This means that we now have a way to test password guesses without hitting the server, so we can start with a list of common passwords and go until we find one that works. As hinted in the welcome message, the password in this case is very weak. In fact, it is “Trustno1”, a password that is sure to appear on any list of commonly used passwords.</p><p>And that’s the solution for the “besquare” crypto challenge. Or at least, it is the solution I came up with. If you find any other methods to solve the problem, please tell me.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c5d8b7eab6ce" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Ref patterns, destructuring, and invisible borrows]]></title>
            <link>https://medium.com/@robertgrosse/ref-patterns-destructuring-and-invisible-borrows-2f8ae6902656?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/2f8ae6902656</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Wed, 17 Jan 2018 05:07:16 GMT</pubDate>
            <atom:updated>2026-02-06T16:53:50.950Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2018/01/17/ref-patterns-destructuring-and-invisible-borrows.html"><em>here</em></a><em> for the updated post.</em></p><p><em>Note: The behavior of match patterns in Rust has been changed since this post was written, making it largely obsolete.</em></p><p>Recently, I was puzzled when I came across some Rust code that looked like it couldn’t possibly compile, and yet it did. Here’s a short snippet that demonstrates the same problem as the original code I was reading:</p><pre>let opt = Some(&quot;Hello&quot;.to_string());</pre><pre>match opt {<br>    Some(_) =&gt; println!(&quot;We have a string&quot;),<br>    None =&gt; println!(&quot;We have None&quot;),<br>}</pre><pre>match opt {<br>    Some(mut s) =&gt; {<br>        s.push_str(&quot; world!&quot;);<br>        println!(&quot;{}&quot;, s);<br>    }<br>    None =&gt; {}<br>}</pre><p>The usual rule in Rust is that if you see a variable without a &amp; in front of it, that means that the value is being moved or copied. Here, opt appears twice, but it is not a copyable type. The first match expression should move opt, leading to an error in the second match expression, but this code compiles without errors. How is this possible?</p><p>After some experimentation, I discovered that replacing the Some(_) in the first match clause above with Some(s) does cause a “use of partially moved value” error as expected. Furthermore, the ever helpful compiler suggests changing it to Some(ref s), which does compile without errors. Clearly, the _ is getting implicitly replaced by ref s rather than s, and this somehow causes the match expression to borrow opt rather than moving it.</p><p>However, this still leaves the question of why the match expression is borrowing opt when there is no &amp;. If like me, you think of ref as something to sprinkle into all your match clauses until the compiler stops complaining, this may seem a bit magical, but it turns out to be a logical consequence of the way pattern matching works in Rust.</p><p>Like many languages, Rust offers destructuring, a shorthand syntax to split up complicated values. The simplest case is using destructing assignment to split up a tuple at the same time you assign new variables as shown below.</p><pre>let (a, (b, c)) = (1, (2, 4));<br>// a = 1, b = 2, c = 4</pre><p>In a language without destructuring assignment, you would have to access every part of the tuple separately, like this, which is much more verbose.</p><pre>let temp = (1, (2, 4));<br>let a = temp.0;<br>let b = temp.1.0;<br>let c = temp.1.1;</pre><p>The basic idea behind destructuring syntax is that the left hand side of the assignment looks the same as the right hand side you are trying to match against, which means that each bit of syntax on the left of the assignment does the opposite of what it would do in a normal expression. For example, adding parenthesis causes a tuple to be broken apart rather than creating a tuple like normal. The same applies for structs.</p><pre>struct Foo {<br>    size: u32,<br>    name: &amp;&#39;static str,<br>}</pre><pre>let Foo{size: a, name: b} = Foo{size: 42, name: &quot;Bob&quot;};<br>// a = 42, b = &quot;Bob&quot;</pre><p>However, Rust’s destructuring syntax is not limited to tuples and structs. You can also use it with references:</p><pre>let &amp;&amp;&amp;x = &amp;&amp;&amp;42;<br>// x = 42</pre><p>And of course, you don’t have to undo every level of references in the pattern. If you don’t, the resulting variable will be a reference.</p><pre>let &amp;&amp;y = &amp;&amp;&amp;42;<br>// y = &amp;42</pre><p>This syntax can also be combined with tuples and structs</p><pre>let (x, &amp;y) = (&amp;32, &amp;8);<br>// x = &amp;32, y = 8</pre><p>However, what if you had an existing reference to a tuple and you wanted to get references to the individual members of the tuple? Using &amp; in a destructuring pattern will “undo” a reference but it can’t create one.</p><pre>// What goes here ???<br>let &amp;(???x, ???y) = &amp;(4, 7);</pre><p>The answer is ref. In a pattern, ref does the opposite of &amp; — it creates a reference. This allows us to undo the original reference to the tuple, split it apart, and then take a reference to each individual member, all in one pattern:</p><pre>let &amp;(ref x, ref y) = &amp;(4, 7);</pre><p>You don’t have to use ref inside a tuple. You can also use it on a bare variable and combine it with &amp;, although there’s no real reason to do so. Since &amp; and ref are opposites, the following are equivalent:</p><pre>let x       = &amp;42;<br>let &amp;ref y  = &amp;42;<br>// x = &amp;42, y = &amp;42</pre><p>However, we can also remove the &amp; from both sides, meaning that the following must also be equivalent:</p><pre>let ref z = 42;<br>// z = &amp;42</pre><p>But wait! We just borrowed a variable without using a &amp; ! (Well, we actually borrowed a literal here for the sake of example, but you could just as easily put a variable in place of 42).</p><p>Far from being weird magic, borrowing the right hand side is the only logical way for a ref pattern to work! In the examples above, we’ve been doing the destructing inside an assignment, but it works the same way if you do it in the arms of a match expression instead:</p><pre>match opt {<br>    // opt is borrowed because of the ref pattern<br>    // on the &quot;left hand side&quot; here<br>    Some(ref s) =&gt; println!(&quot;We have a string&quot;),<br>    None =&gt; println!(&quot;We have None&quot;),<br>}</pre><p>So the lesson is that when destructuring is involved, it’s not enough to look for &amp; to find the borrows of a given variable. You need to check whether the destructuring pattern contains ref, (and if so, whether there are more levels of &amp; then refs.)</p><p>As for why _ turned into ref s rather than s, this is presumably just the Rust compiler being helpful and choosing the least restrictive form of reference, much like it does for closures. Since the string isn’t actually used in the first match expression, we might as well just borrow it, which places the fewest restrictions on the surrounding code.</p><p><strong>Update</strong>: mutabah pointed out in the comments that _ doesn’t actually get turned into a ref pattern. It acts like it did in terms of the fact that opt doesn’t get moved, but it is actually even weaker because it doesn’t borrow opt either. You can see the difference if you try something like this:</p><pre>match opt {<br>    Some(_) =&gt; drop(opt),<br>    None =&gt; println!(&quot;We have None&quot;),<br>}</pre><p>The match opt part doesn’t hold on to opt at all, meaning we are free to move it within the match statement (in this case, passing it to drop). If the _ were replaced by ref s, this would be invalid because we would be trying to drop the string while simultaneously borrowing it.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2f8ae6902656" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How ES6 classes really work and how to build your own]]></title>
            <link>https://medium.com/@robertgrosse/how-es6-classes-really-work-and-how-to-build-your-own-fd6085eb326a?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/fd6085eb326a</guid>
            <category><![CDATA[ecmascript]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[es6]]></category>
            <category><![CDATA[es6-in-depth]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Fri, 29 Dec 2017 07:17:06 GMT</pubDate>
            <atom:updated>2026-02-06T16:53:07.855Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2017/12/29/how-es6-classes-really-work-and-how-to-build-your-own.html"><em>here</em></a><em> for the updated post.</em></p><p>The 6th edition of ECMAScript (or ES6 for short) revolutionized the language, adding many new features, including classes and class based inheritance. The new syntax is easy to use without understanding the details and mostly does what you’d expect, but if you’re like me, that isn’t quite satisfying. How does the seemingly magical syntax actually work under the hood? How does it interact with other features in the language? Is it possible to emulate classes without using the class syntax? Here, I will answer these questions in gratuitous detail.</p><p>But first, in order to understand classes, you must understand what came before them, and Javascript’s underlying object model.</p><h4><strong>Object model</strong></h4><p>The Javascript object model is fairly simple. Each object is just a mapping of strings and symbols to property descriptors. Each property descriptor in turn holds either a getter/setter pair for computed properties or a data value for ordinary data properties.</p><p>When you execute the code foo[bar] , it converts bar to a string if it isn’t already a string or symbol, then looks up that key among foo’s properties and returns the value of the corresponding property (or calls its getter function as applicable). For literal string keys that are valid identifiers, there is the shorthand syntax foo.bar which is equivalent to foo[&quot;bar&quot;] . So far, so simple.</p><h4><strong>Prototypal inheritance</strong></h4><p>Javascript has what is called prototypal inheritance, which sounds scary, but is actually simpler than traditional class based inheritance once you get the hang of it. Each object may have an implicit pointer to another object, referred to as its prototype. When you try to access a property on an object where no property exists with that key, it instead looks up the key on the prototype object, and returns the prototype’s property for that key if it exists. If it doesn’t exist on the prototype, it recursively checks the prototype’s prototype and so on, all the way up the chain until a property is found or an object without a prototype is reached.</p><p>If you have used Python before, the attribute lookup process is similar. In Python, each attribute is first looked up in the instance dictionary. If it is not present there, the runtime then checks the class dictionary, then the super class dictionary, and so on, all the way up the inheritance hierarchy. In Javascript, the process is similar except that there is no distinction between type objects and instance objects — any object can be the prototype of any other object. Of course, in the real world, people rarely use this fact and instead organize their code into class-like hierarchies, because it is easier to manage that way, which is why Javascript added class syntax in the first place.</p><h4><strong>Internal slots</strong></h4><p>If all an object consists of is a mapping of keys to properties, where is the prototype stored? The answer is that in addition to properties, objects also have <em>internal methods</em> and <em>internal slots </em>which are used to implement special language level semantics. Internal slots cannot be directly accessed from Javascript code in any way, but in some cases, there are ways to indirectly access them. For example, object prototypes are represented by the [[Prototype]] slot which can be read and written using Object.getPrototypeOf() and Object.setPrototypeOf() respectively. By convention, internal slots and methods are written in [[double square brackets]] to distinguish them from ordinary properties.</p><h4>Old style classes</h4><p>In early versions of Javascript, it was common to simulate classes using code like the following.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2b8fae5923c89983c9b049fecb258ab9/href">https://medium.com/media/2b8fae5923c89983c9b049fecb258ab9/href</a></iframe><p>Where did this come from? Where did prototype come from? What does new do? As it turns out, even the earliest versions of Javascript didn’t want to be too unconventional, so they included some syntax that let you code things that were kinda-sorta like classes.</p><p>In technical terms, functions in Javascript are defined by the two internal methods [[Call]] and [[Construct]] . Any object with a [[Call]] method is called a function, and any function that additionally has a [[Construct]] method is called a constructor¹. The [[Call]] method determines what happens when you invoke an object as a function, e.g. foo(args) , while [[Construct]] determines what happens when you invoke it as a new expression, i.e. new foo or new foo(args) .</p><p>For ordinary function definitions², calling [[Construct]] will implicitly create a new object whose [[Prototype]] is the prototype property of the constructor function if that property exists and is object valued, or Object.prototype otherwise. The newly created object is bound to the this value inside the function’s local environment. If the function returns an object, the new expression will evaluate to that object, otherwise, the new expression evaluates to the implicitly created this value.</p><p>As for the prototype property, that is implicitly created whenever you define an ordinary function. Each newly defined function has a property named “prototype” defined upon it with a newly created object as its value. That object in turn has a constructor property which points back to the original function. Note that this prototype property is <strong>not</strong> the same as the [[Prototype]] slot. In the previous code example, Foo is still just a function, so its [[Prototype]] is the predefined object Function.prototype .</p><p>Here is a diagram to illustrate the previous code sample with [[Prototype]] relationships in black and property relationships in green and blue.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*l4G8UjP-fAz13prd3TDr9g.png" /><figcaption>diagram of prototype hierarchy for previous code sample</figcaption></figure><p>[1] You could conceivably have objects with a [[Construct]] method and no [[Call]] method, but the ECMAScript specification does not define any such objects. Therefore, all constructors are also functions.</p><p>[2] By ordinary function definitions, I mean functions defined using the regular function keyword and nothing else, rather than =&gt; functions, generator functions, async functions, methods, etc. Of course, prior to ES6, this was the only kind of function definition.</p><h4>New style classes</h4><p>With that background out of the way, it’s time to examine ES6 class syntax. The previous code sample translates directly to the new syntax as follows:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f78e34a905a74eacea2aef8b45ca6f70/href">https://medium.com/media/f78e34a905a74eacea2aef8b45ca6f70/href</a></iframe><p>As before, each class consists of a constructor function and a prototype object which refer to each other via the prototype and constructor properties. However, the order of definition of the two is reversed. With an old style class, you define the constructor function, and the prototype object is created for you. With a new style class, the body of the class definition becomes the contents of the prototype object (except for static methods), and among them, you define a constructor. The end result is the same either way.</p><p>So if the ES6 class syntax is just sugar for old style “classes”, what’s the point? Apart from looking a lot nicer and adding safety checks, the new class syntax also has functionality that was impossible pre-ES6, specifically, class based inheritance. When you define a class with the new syntax, you can optionally provide a super class for the class to inherit from as demonstrated below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/eb76ae98469b16c736d97ef553bfcfb9/href">https://medium.com/media/eb76ae98469b16c736d97ef553bfcfb9/href</a></iframe><p>This example by itself can still be emulated without class syntax, although the code required is a lot uglier.</p><p>With class based inheritance, the rule is simple — each part of the pair has as its prototype the corresponding part of the superclass. So the constructor of the superclass is the [[Prototype]] of the subclass constructor and the prototype object of the superclass is the [[Prototype]] of the subclass prototype object. Here’s a diagram to illustrate (only the [[Prototypes]] are shown; properties are omitted for clarity).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/614/1*bIRH65fDxTXALv63yQvbVg.png" /></figure><p>There is no direct and convenient way to set up these [[Prototype]] relationships without using class syntax, but you can set them manually using Object.setPrototypeOf(), introduced in ES5.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/2444c677df98e9d51d706da74fe3c529/href">https://medium.com/media/2444c677df98e9d51d706da74fe3c529/href</a></iframe><p>However, the example above notably avoids doing anything in the constructors. In particular, it avoids super, a new piece of syntax that allows subclasses to access the properties and constructor of the superclass. This is much more complicated, and is in fact impossible to fully emulate in ES5, although it can be emulated in ES6 without using class syntax or super through use of Reflect.</p><h4>Superclass property access</h4><p>There are two uses for super — calling a superclass constructor, or accessing properties of the superclass. The second case is simpler, so we’ll cover it first.</p><p>The way that super works is that each function has an internal slot called [[HomeObject]] , which holds the object that the function was originally defined within if it was originally defined as a method. For a class definition, this object will be the prototype object of the class, i.e. Foo.prototype . When you access a property via super.foo or super[&quot;foo&quot;], it is equivalent to [[HomeObject]].[[Prototype]].foo .</p><p>With this understanding of how super works behind the scenes, you can predict how it will behave even under complicated and unusual circumstances. For example, a function’s [[HomeObject]] is fixed at definition time and will not change even if you later assign the function to other objects as shown below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/63527e220643d9e98e5ee4c935589702/href">https://medium.com/media/63527e220643d9e98e5ee4c935589702/href</a></iframe><p>In the above example, we took a function originally defined in D.prototype and copied it over to B.prototype. Since the [[HomeObject]] still points to D.prototype, the super access looks in the [[Prototype]] of D.prototype, which is C.prototype. The result is that C&#39;s copy of foo is called even though C is nowhere in b&#39;s prototype chain.</p><p>Likewise, the fact that [[HomeObject]].[[Prototype]] is looked up on every evaluation of the super expression means that it will see changes to the [[Prototype]] and return new results, as shown below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b66324638beb70d3992944ffdbf2dafb/href">https://medium.com/media/b66324638beb70d3992944ffdbf2dafb/href</a></iframe><p>As a side note, super is not limited to class definitions. It can also be used from any function defined within an object literal using the new method shorthand syntax, in which case [[HomeObject]] will be the enclosing object literal. Of course, the [[Prototype]] of an object literal will always be Object.prototype so this isn’t terribly useful unless you manually reassign the prototype as is done below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/134a5ddcb94122822bcae423898afeb2/href">https://medium.com/media/134a5ddcb94122822bcae423898afeb2/href</a></iframe><h4>Emulating super properties</h4><p>There is no way to manually set [[HomeObject]] on our methods, but we can emulate it by just saving the value and doing the resolution manually as shown below. It’s not as convenient as just writing super, but at least it works.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/64309c9e89afc70715540b4660efd559/href">https://medium.com/media/64309c9e89afc70715540b4660efd559/href</a></iframe><p>Note that we need to use .call(this) to ensure that the super method gets called with the right this value. If the method has a property which shadows Function.prototype.call for some reason, we could instead use Function.prototype.call.call(foo, this) or Reflect.apply(foo, this) , which are more reliable but verbose.</p><h4>Super in static methods</h4><p>You can also use super from static methods. Static methods are the same as regular methods, except that they are defined as properties on the constructor function instead of on the prototype object.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f7a246946746485c8ecbc3d237725376/href">https://medium.com/media/f7a246946746485c8ecbc3d237725376/href</a></iframe><p>super can be emulated within static methods in the same way as with normal methods. The only difference is that [[HomeObject]] is now the constructor function rather than the prototype object.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/594b51d108c65bbd098606874ce0c719/href">https://medium.com/media/594b51d108c65bbd098606874ce0c719/href</a></iframe><h4>Super constructors</h4><p>When the [[Construct]] method of an ordinary constructor function is invoked, a new object is implicitly created and bound to the this value inside the function. However, subclass constructors follow different rules. There is no automatically created this value and attempting to access this results in an error. Instead, you must call the constructor of the superclass via super(args) . The result of the superclass constructor is then bound to the local this value, after which you can access it in the subclass constructor as normal.</p><p>This of course presents problems if you want to create an old style class that can properly interoperate with new style classes. There is no problem when subclassing an old style class with a new style class, since the base class constructor is just an ordinary constructor function either way. However, subclassing a new style class with an old style class will not work properly, since old style constructors are always base constructors and don’t have the special subclass constructor behavior.</p><p>To make the challenge concrete, suppose we have a new style class Base whose definition is unknown and cannot be changed, and we wish to subclass it without using class syntax, while remaining compatible with whatever code in Base is expecting a true subclass.</p><p>First off, we will assume that Base is not using proxies, or nondeterministic computed properties, or anything else weird like that, since our solution will likely access the properties of Base a different number of times or in a different order than a real subclass would, and there’s nothing we can do about that.</p><p>After that, the question becomes how to set up the constructor call chain. As with regular super properties, we can easily get the superclass constructor using Object.getPrototypeOf(homeObject).constructor. But how to invoke it? Luckily, we can use Reflect.construct() to manually invoke the internal [[Construct]] method of any constructor function.</p><p>There’s no way to emulate the special behavior of the this binding, but we can just ignore this and use a local variable to store the “real” this value, named $this in the example below.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ecbdef498d3b4b589e4051bab8189fd7/href">https://medium.com/media/ecbdef498d3b4b589e4051bab8189fd7/href</a></iframe><p>Note the return $this; line above. Recall that if a constructor function returns an object, that object will be used as the value of the new expression instead of the implicitly created this value.</p><p>So, mission accomplished? Not quite. The obj value in the above example is not actually an instance of Child, i.e. it does not have Child.prototype in its prototype chain. This is because Base‘s constructor didn’t know anything about Child and hence returned an object that was just a plain instance of Base (its [[Prototype]] is Base.prototype).</p><p>So how is this problem solved for real classes? [[Construct]], and by extension, Reflect.construct, actually take three parameters. The third parameter, newTarget, is a reference to the constructor that was originally invoked in the new expression, and hence the constructor of the bottom-most (most derived) class in the inheritance hierarchy. Once control flow reaches the constructor of the base class, the implicitly created this object will have newTarget as its [[Prototype]].</p><p>Therefore, we can make Base construct an instance of Child by invoking the constructor via Reflect.construct(constructor, args, Child). However, this still isn’t quite right, because it will break whenever someone else subclasses Child. Instead of hardcoding the child class, we need to pass through newTarget unchanged. Luckily, it can be accessed within constructors using the special new.target syntax. This leads to the final solution below:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ab96320cbfcd844cf89b4bc147f75551/href">https://medium.com/media/ab96320cbfcd844cf89b4bc147f75551/href</a></iframe><h4>Final touches</h4><p>This covers all the major functionality of classes, but there are a few other minor differences, mostly safety checks added to the new class syntax. For example, the prototype property automatically added to function definitions is writeable by default, but the prototype property of class constructors is not writeable. We can easily make ours non-writeable as well by calling Object.defineProperty() . Alternatively, you could just call Object.freeze() if you want the whole thing to be immutable.</p><p>Another new protection is that class constructors will throw a TypeError if you try to [[Call]] them instead of constructing them with new. Our constructor above happens to throw a TypeError as well, but only indirectly, because new.target is undefined when the function is [[Call]]ed and Reflect.construct() throws a TypeError if you explicitly pass undefined as the last argument. Since the TypeError is coincidental here, the resulting error message is rather confusing. It might be useful to add an explicit check for new.target that throws an error with a more helpful error message.</p><p>Anyway, I hope you enjoyed this post and learned as much as I did in the process of researching it. The above techniques are rarely useful in real world code, but it is still important to understand how things work under the hood in case you have an unusual use case which requires reaching for the black magic, or more likely, you’re stuck having to debug somebody else’s black magic.</p><p><strong>P.S.</strong> If, like me, you are annoyed by Medium’s giant uncloseable banner on the bottom of the screen urging you to sign up, or the general quest of websites to make reading their content as difficult and annoying as possible, I would highly recommend checking out <a href="https://alisdair.mcdiarmid.org/kill-sticky-headers/">Kill Sticky</a>. It is a simple Javascript snippet you can bookmark that deletes any “sticky” elements on the page. It sounds simple, but browsing with Kill Sticky is life changing. And since it’s just a bookmarklet, you don’t have to worry about accidentally killing important page elements for good like you would with a uBlock filter. At worst, you can always just refresh the page.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=fd6085eb326a" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Solving the Traveling Pacman Problem]]></title>
            <link>https://medium.com/@robertgrosse/solving-the-traveling-pacman-problem-39c0872428bc?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/39c0872428bc</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Wed, 26 Jul 2017 16:29:26 GMT</pubDate>
            <atom:updated>2026-02-06T16:52:22.130Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2017/07/26/solving-the-traveling-pacman-problem.html"><em>here</em></a><em> for the updated post.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/939/1*iv3FBxte8htes9UUyIVPaw.png" /></figure><p>When I was in college, one class assignment gave us a set of Pacman mazes and asked us to write an A* search heuristic that would find the shortest path which visits every food pellet at least once. This is obviously similar to the famously NP-Hard Traveling Salesman Problem, but the mazes we were required to solve were small enough that even an exponential solution would work. However, there was also a much larger maze included which the assignment instructions said was impossible to solve, and if our code did terminate in a reasonable amount of time on it, it meant there was a bug in our code. Naturally, I couldn’t turn down a challenge like that, and this is the story of how I solved it.</p><h4>A* Search</h4><p>The assignment provided the game engine and A* implementation, with the only part of the code that we were supposed to change being the heuristic function. There are several obvious heuristics one could use for this problem, such as the number of uneaten food, or the maximum distance to a food, or even the length of the minimum spanning tree of the food. But this is a trap. To see why, consider how A* search is supposed to work.</p><p>The most classic application of A* search is to 2d pathfinding, as depicted below. The red, green, and blue nodes show the nodes expanded during search when using the null heuristic, euclidean distance (a good but not perfect heuristic) and manhattan distance (a perfect heuristic in this case) respectively. The null heuristic expands every single node within distance 4 of the origin, while the euclidean heuristic only expands a few extra nodes and the manhattan heuristic goes straight to the goal without expanding any extra nodes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/657/1*QIS-CpHQQHL58fQM3I_Mcw.png" /><figcaption>illustration of 2d A* search with various heuristics</figcaption></figure><p>Obviously, the better the heuristic, the fewer nodes are expanded. However, even with the null heuristic, where A* devolves into a simple breadth first search, only quadratically many nodes are expanded. This is because in a sense, the search space is quadratically big. For any given node, there are at most O(k²) nodes that are k steps away. This means that if your heuristic differs from the optimal heuristic by k, the search will expand at most O(nk²) incorrect nodes.</p><p>For the Pacman problem by contrast, the search space is exponentially large. Even though the maze itself is small, each possible subset of eaten food represents a different state in the search space. Unlike with the pathfinding example, moving up and then left will not result in the same state as moving left and then up, because a different set of food will have been eaten.</p><p>This means that there are up to O(3ᵏ) nodes that are k steps away from any given node, and any heuristic that is short of perfection is likely to lead to an exponential search complexity. This makes A* search unsuitable for the problem, no matter how clever you try to be with the heuristic function.</p><p>However, there is one out: a perfect heuristic function. The optimal solution is only linearly long (in fact, it will visit every edge at most twice), so if the A* search never takes a single wrong step, then the overall search time will be linear as well (ignoring the complexity of the heuristic function itself).</p><p>Note: There could be exponentially many optimal paths of the same length, but this is easily solved by making the A* search break ties in favor of the longest path.</p><p>This of course leads to the question of how to find an efficient perfect heuristic function. However we are now at least freed from the confines of A*: We can use any algorithm we want to calculate the length of the optimal path and then feed the results back to the A* search as a “heuristic”.</p><h4>The exponential algorithm</h4><p>The mazes required to be solved for the assignment were all sparse — most of the maze was empty, with only a handful of food pellets, meaning we can speed things up by only considering the food. Instead of trying to find the shortest path in a large maze of n nodes, where we only care about m of them (the number of food), we can instead pretend to solve a problem in a maze of m nodes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*thPOUBad8-6nNk-4Qk_F-Q.png" /><figcaption>One of the homework mazes: note all the empty spaces.</figcaption></figure><p>To do this, just precompute the shortest distance between every pair of food, and find the shortest path in the complete graph Kₘ where the edge weights are equal to said distances. Note that you also have to add the distance from Pacman’s current location to the food in addition to the distances between the food themselves, but this is easily done with standard distance finding algorithms.</p><p>The naive brute force approach is O(m!), but this can be reduced to O(m²2ᵐ) using simple dynamic programming (memoize on the subset of uneaten food and the starting food). For the homework mazes, m was small enough that this was sufficient. However, the “impossible” maze was much larger, and every square had food in it. In order to solve it, I would need a more sophisticated approach.</p><h4>Biconnected components</h4><p>I was of course not foolish enough to think that I could prove P=NP. The reason I was confident I could solve it is because the mazes weren’t just arbitrary graphs. In fact, they were poorly connected. If you look closely at the maze below, you’ll notice that there are many points where removing a single square cuts the maze in two.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/939/1*FKnFcRSIYWA-J3vd3UkwNA.png" /><figcaption>mediumSearch with cut nodes and large biconnected components marked</figcaption></figure><p>This makes solving much easier, because such a <em>cut vertex</em>, is the “interface” between the components. Each component doesn’t care at all what happens in the other. If you have an optimal path that visits every food in the left component, and an optimal path that visits every food in the right component, you can join them together into a solution for the entire maze.</p><p>The only information required to ensure they can be joined is to make sure the parity of the number of edges going out of the cut vertex matches up. So in order to find a solution to the entire maze, you can find the optimal odd and even solutions to the left component, and <em>independently</em> find the optimal odd and even solutions to the right component, and then join them together and pick the best result.</p><p>This effectively reduces the complexity of solving the maze to be exponential in the size of the largest biconnected component. Unfortunately for the mediumSearch maze, the largest component (highlighted in green above) had 26 nodes, which was still too large to be solved, or at least solved quickly in Python on an old laptop. Therefore, I needed to find further improvements.</p><h4>Carving decomposition</h4><p>The next step was to consider cuts of 2 vertices in addition to cuts of a single vertex. The biconnected components all have large “tunnels”, so a 2-cut would be sufficient to reduce them to a manageable size. However, it is much more complicated than the single vertex case because you have to consider the connectivity as well.</p><p>After some research, I came across the notion of a <a href="https://en.wikipedia.org/wiki/Branch-decomposition#Carving_width">carving decomposition</a>, and its use in fixed parameter tractable algorithms for similar problems. The trick is to generalize not just to cuts of 2 vertices, but to arbitrary numbers of vertices.</p><p>In the case of multiple vertex cuts, there are several complications that don’t apply in the single vertex case. First off, you have to keep track of which set of vertices in the cut each sub-solution visits. In the single vertex case, both sub-solutions must visit the vertex, but in the multiple vertex case, it is ok to visit only a subset, as long as every vertex in the cut is visited from at least one side, and there is at least one vertex of overlap so the sub-solutions can be joined together.</p><p>Additionally you have to keep track of which cut vertices are connected by each sub-solution. This is necessary to ensure that the sub-solutions can be joined together into a single path, rather than a bunch of disconnected loops. An illustration of such joining is shown below. Note that this “solution” is not optimal, it was just chosen to depict the process.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*R_7L0PQnEHQXQ4W-22QXHg.png" /><figcaption>diagram showing path merging</figcaption></figure><p>Given any specific tuple of (visited nodes, connectivity, parity), the rest of the sub-solution is irrelevant to determining whether it can be joined into a larger solution, so the usual dynamic programming techniques still apply.</p><p>The idea behind a carving decomposition is to split the entire graph up with such cuts, leaving only single nodes as the base case for the recursion. The size of the largest cut required is known as the <strong>carving width</strong> of the graph, and it is this which determines the complexity of the overall algorithm.</p><p>Since for each cut, the number of (visited nodes, connectivity, parity) cases to consider is exponential in the number of vertices in the cut, the algorithm is exponential in the carving width of the graph. However, if you hold width constant, the algorithm is otherwise polynomial in the size of the graph, making it what is known as a <a href="https://en.wikipedia.org/wiki/Parameterized_complexity">fixed parameter tractable algorithm</a>.</p><p>As an aside, carving width is unbounded, even for planar grid graphs. For example, an n x n grid has a carving width of n, since there is no way to split the graph completely without cutting at least one vertex from every row or column. In this case, the fixed parameter tractable algorithm would have exponential complexity. Luckily, we are dealing with poorly connected graphs, rather than giant grids.</p><p>The last question is how to actually find the carving decomposition. There are algorithms to find an optimal carving decomposition of planar graphs in polynomial time, but I found them too difficult to understand and implement, so I decided to just use the greedy algorithm to find a non-optimal decomposition, which worked well enough for the mazes in question. Once all this was implemented and optimized, my code was able to solve mediumSearch in under 5 seconds on my laptop, thus conquering the impossible challenge.</p><h4>bigSearch</h4><p>In addition to mediumSearch, the assignment also comes with a much larger maze known as bigSearch. Although our class did not use it, many versions of this assignment at other colleges include <a href="https://www.cs.utexas.edu/~pstone/Courses/343spring10/assignments/search/search.html">a contest</a> where students compete to find the best (non-optimal) solution in under 30 seconds. This maze can be solved optimally using the same algorithm as before, although the higher carving width means it takes longer. Since my final code can solve this optimally in under 30 seconds, I like to think I won those contests in spirit.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/934/1*AksaWYwhXxpDXwgdvkfghQ.png" /><figcaption>The big maze</figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=39c0872428bc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Rust is self driving C++]]></title>
            <link>https://medium.com/@robertgrosse/rust-is-self-driving-c-9171c54c79f5?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/9171c54c79f5</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Sat, 22 Jul 2017 07:21:57 GMT</pubDate>
            <atom:updated>2026-02-06T16:51:17.558Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2017/07/22/rust-is-self-driving-c.html"><em>here</em></a><em> for the updated post.</em></p><p><em>Warning: Opinion piece without code</em></p><p>Rust is often mocked for the relentless evangelism of Rust programmers and its perceived overhyping. For people who aren’t already familiar with Rust, it is hard to understand what the big deal about it is, and hence all the talk about Rust just seems like a crazy fad. I think the best way to explain it is by analogy to the work on driverless cars.</p><p>The most striking thing when reading stories about people working on driverless cars is their passion. Humans are really bad at driving cars. They get tired, or distracted, or drunk, and kill over 35,000 people a year. For a long time, this was tolerated because there was no alternative, but now that there is, people are understandably excited. Driverless cars are a really, really, big deal.</p><p>I think the same situation is playing out in the realm of systems programming, minus the horrible deaths. C and C++ are incredibly bad languages for programming. Among other issues, they make it nearly impossible to write correct code, leading to countless bugs and security vulnerabilities.</p><p>At this point, some C++ programmers will object that if you are just smart enough, you won’t write bugs. But that simply isn’t borne out by reality. Consider Google Chrome, a modern C++ codebase supported by sophisticated tooling and a world-class security team. A quick check of cvedetails.com shows 5 critical vulnerabilities in just the last year. Or as another example, consider Android, which had 523 vulnerabilities reported last year.</p><p>I’m not trying to pick on Google here, I just highlighted it because they have a bug bounty program that paid out $3 million last year. C++ is costing people serious money. And that’s just the tip of the iceberg, since most companies don’t have security teams or bug bounties and have orders of magnitude more vulnerabilities lurking in their code. As it turns out, human programmers also get tired and distracted (and frequently drunk too). Even with the best coding practices possible, you can’t keep every detail of the code in working memory. Expecting perfection from a million line codebase is simply unworkable.</p><p>For a long time this was tolerated, because there was no alternative to C/C++ when it came to systems programming, but Rust is changing that, and that is what makes it so exciting. This isn’t to say that it will catch every possible vulnerability, any more than a driverless car won’t eventually get into a crash somewhere, but even eliminating say, 95% of vulnerabilities would bring immense benefits. Just because many fads get overhyped doesn’t mean that the hype isn’t justified this time. It is high time that systems programming be brought into the 21st century.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9171c54c79f5" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Generating 64 bit hash collisions to DOS Python]]></title>
            <link>https://medium.com/@robertgrosse/generating-64-bit-hash-collisions-to-dos-python-5b21404a5306?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/5b21404a5306</guid>
            <category><![CDATA[security]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[python]]></category>
            <category><![CDATA[cryptography]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Thu, 02 Mar 2017 01:36:11 GMT</pubDate>
            <atom:updated>2026-02-06T16:50:37.674Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2017/03/02/generating-64-bit-hash-collisions-to-dos-python.html"><em>here</em></a><em> for the updated post.</em></p><p>Hash tables are one of the most commonly used data structures in computer science, due to their O(1) access time. However, this assumes a perfect hash function — the complexity can increase to O(n) when there are a lot of hash collisions. Historically, most libraries used weak, non cryptographic hashes for efficiency. These worked well for random strings, but the simplicity of the hash functions used makes it possible to generate multiple strings with the same hash value, leading to a denial of service vulnerability.</p><p>Although this problem has been theoretically known for decades, it didn’t receive much attention until 2003, when <a href="http://static.usenix.org/event/sec03/tech/full_papers/crosby/crosby_html/">a USENIX paper</a> pointed out that Perl and the Squid proxy were vulnerable to this attack. <a href="https://mail.python.org/pipermail/python-dev/2003-May/035874.html">They also reported it on the Python mailing list</a>, but no action was taken and the issue was once again forgotten until December 2011, when <a href="https://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html">a talk at the Chaos Communication Congress</a> pointed out that nearly every framework and language in use is also vulnerable and finally brought widespread attention to the issue.</p><p>At the time, Python used a non-cryptographic multiply/xor hash algorithm similar to <a href="https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function">FNV</a> for string hashing. <a href="https://mail.python.org/pipermail/python-dev/2011-December/115116.html">After</a> <a href="https://mail.python.org/pipermail/python-dev/2012-January/115690.html">much</a> <a href="http://bugs.python.org/issue13703">deliberation</a>, the Python developers decided to simply modify the hash function to xor a random value to the beginning and end. In Python 2.7, hash randomization can be enabled by passing -R to Python. In Python 3.3, it was turned on by default.</p><p>It didn’t take long for someone to <a href="https://bugs.python.org/issue14621">point out</a> that Python’s hash randomization added negligible collision resistance. In version 3.4, Python switched the default string hash algorithm to <a href="https://131002.net/siphash/">SipHash</a>, a cryptographic keyed hash function recently created specifically for use in hash tables, thus solving the problem for real. However, anyone using Python 2.x is stuck with an insecure hash function.</p><p>As the author of a Python 2 application which deals with untrusted inputs and as an amateur cryptographer, I was curious to see if I could perform the DOS attack first hand. Unfortunately, there’s often a gap between crypto that is theoretically broken and crypto that is easily breakable by the average person. I couldn’t find any public information about how to generate 64 bit FNV collisions, so I had to figure it out myself. It turned out to be a lot harder than I expected, but I eventually managed it, and here is how I did it.</p><h3>Background</h3><p>There are several different ways to attack a hash table. When you insert or look up a string in a hash table, the string is first hashed to a 32 bit or 64 bit value, and then this hash value is reduced modulo the size of the table to get the actual bucket to search.</p><p>If the size of the hash table is small and predictable, and the hash function is deterministic, then it is possible to find strings that map to the same bucket by brute force, regardless of the strength of the underlying hash function. Therefore, it is necessary to use a keyed hash function, where the output hash depends not only on the string, but on a secret key. Typically the key is randomly generated at startup, or when creating a new hashtable.</p><p>However, if the hash function is weak, then it may be possible to find strings which map not only to the same bucket, but to the same raw 64 bit value. This means that such strings will be in the same bucket regardless of the hashtable size, or even if it is resized, making the attack much more powerful. Additionally, if the hash function is sufficiently weak, it is possible to find strings that map to the same hash value <em>regardless of the secret key</em>. This is the type of attack I’ll be focusing on.</p><p>Additionally, there is the question of interactive vs noninteractive attacks. In some scenarios, such as a web server, the attacker can query the server multiple times, which potentially leaks information about the secret key. However, if you can perform the attack without any knowledge of the secret key at all, that is strictly more powerful.</p><p>The target I chose is the <a href="https://github.com/Storyyeller/Krakatau">Krakatau assembler</a> that I wrote, which is designed to have worst case linear performance in the size of the input file (ignoring time spent printing error messages anyway). However, pathological hash collisions would increase this to quadratic time, making it take unreasonably long, even with a small input file. Naturally, this is a non-interactive attack.</p><p>Additionally, I decided to inject the strings via Krakatau’s symbolic references feature, which limits the strings to lowercase alphanumerics and underscore, a total of 37 characters. The more characters you have to choose from, the shorter your colliding strings can be, but I figure that alphanumerics is a superset of any plausible character restrictions, meaning that the strings I use to attack Krakatau would also be useful for testing other programs.</p><h3>Universal collisions</h3><p>A universal hash collision is a collision where two strings hash to the same value, regardless of the secret key. The first step is to show that such collisions exist, even theoretically. To make things easier to understand, I’ll first explain using a simplified version of Python’s actual hash function.</p><p>Consider the following simple hash function pseudocode where x is a 64 bit int.</p><pre>P = 1000003</pre><pre>def hash(s):<br>x = random key 1<br>for byte in s:<br>    x = (x * P) + byte<br>x ^= random key 2<br>return x</pre><p>All the hash function does is start with a random 64 bit state, loops through each byte in the string, multiplying the state by a constant and then adding the byte, and then adds another random value at the end.</p><p>Note: This is defined for byte strings. If you hash unicode, you need to utf8 encode it first. However, since I am only using ASCII here, I’ll use the terms “byte” and “character” interchangeably.</p><p>Each step in the hash function can be thought of as a function that maps from the old state to the new state. In fact, this function can be written out explicitly.</p><pre>step(oldstate, byte) = oldstate * P + byte</pre><p>Or giving the variables shorter names,</p><pre>step(x, b) = x * P + b</pre><p>This can also be curried. Any particular byte defines a function from one state to another. We’ll call this the action of the byte on the state.</p><pre>act(b)(x) = x * P + b</pre><p>Just like individual bytes, substrings also act on the state of the hash function, and the action is just the application of the action for each byte in turn.</p><pre>act(&#39;a&#39; + &#39;b&#39;)(x) = act(&#39;b&#39;)(act(&#39;a&#39;)(x)) </pre><p>The trick is that the action of each byte is a linear function, i.e. of the form f(x) = a*x + b . Since the composition of linear functions is also linear, this means that the action of every possible string is also a linear function.</p><pre>let act(s1) = a*x + b<br>let act(s2) = c*x + d<br>act(s1 + s2) = c*(a*x + b) + d = (a*c)*x + (b*c + d)</pre><p>That means that the action of any possible string is completely defined by just two numbers. Since we’re assuming 64 bit math, each of those numbers is at most 64 bits, meaning that there are only 2¹²⁸ distinct possible actions. If you have a set of at least 2¹²⁸+1 strings, two of them are guaranteed to have the same action.</p><p>If two strings have the same action, that means that given the same input state, they’ll have the same output state. This means that they’ll collide, regardless of what happens before or afterwards. Such strings will produce the same hash value, regardless of the secret keys. The actual hash value obviously does depend on the key, but whatever it is, it will be the same between the two strings.</p><p>This puts an upper bound on the length of the shortest collision. If you are using an alphabet of W bytes, then there is a collision of length at most floor(1 + 128/log(W)) . In fact, the bound is half this because the multiplier coefficient depends only on the length of the string (it is P to the nth power mod 2⁶⁴). This means that for any fixed length, only the additive constant matters and there are 2⁶⁴ possible actions.</p><p>Naturally, the actual hash function used by Python is slightly more complicated. Here it is in pseudocode.</p><pre>P = 1000003</pre><pre>def hash(s):<br>if len(s) == 0: <br>    return 0</pre><pre>x = random key 1<br>x ^= s[0] &lt;&lt; 7<br>for byte in s:<br>    x = (x * P) ^ byte<br>x ^= len(s)<br>x ^= random key 2<br>if x == -1:<br>    return -2<br>return x</pre><p>Most of the extra details don’t matter for our purposes. For example, the empty string is special cased to always hash to 0, but we don’t care about that. Likewise, the -1 check strictly increases the number of collisions and can be ignored. Also, the length addition doesn’t matter if we always used strings of equal length, and the special handling of the first byte doesn’t matter if we prefix all our strings with an arbitrary fixed byte.</p><p>One other thing to note is that x is either 32 or 64 bits depending on the platform and how Python was compiled. However, any 64 bit collision is also a 32 bit collision and I’m using 64 bit Python, so I focused on the 64 bit case. If you only care about 32 bit collisions, you can generate them very quickly with just brute force anyway.</p><p>Once these details are removed, the hash function simplifies to this.</p><pre>def hash(s):<br>x = random key 1<br>for byte in s:<br>    x = (x * P) ^ byte<br>x ^= random key 2<br>return x</pre><p>This is identical to the previous hash algorithm except for the use of xor rather than addition. However, this one tweak makes it much more difficult to break. The problem is that the step function is no longer a simple mathematical equation. Bitwise xor is a nonlinear operation when viewed in the ring of integers mod 2⁶⁴.</p><p>Fortunately, xor is only slightly nonlinear. In particular, it is addition without carry, which means that the nonlinearity is limited to the size of the smaller operand, in this case a byte. Therefore, for any fixed least significant byte in the input state, the new state is a linear function of the old state. This means that the action of any string can be expressed as a table of 256 ints, where you look up and add the appropriate value from the table based on the low byte of the input. This puts a bound, albeit a much larger one, on the size of the smallest universal collision.</p><p>Unfortunately, simply knowing a collision exists doesn’t help you find it, unless the bound is small enough to brute force. Therefore, I needed to come up with an algorithm to find collisions.</p><h3>First try: concatenate and filter</h3><p>The first idea I came up with is a relatively simple algorithm. On each step, you start with a set of n strings, which are all the same length and which collide in the lowest k bits. Then you form a set of n² strings that are twice as long by concatenation. Since each of the individual strings collides in the lowest k bits, the concatenated strings will as well. There are a fixed number of values for the next highest bit, and by the pigeonhole principle, you can take the largest subset that have the same value. This gives you a set that collides in the lowest k+1 bits and you can repeat.</p><p>There are a few more subtleties than that. I started with a set of strings that leave the lowest byte unchanged, so that the actions don’t “mix” between the 256 possible input bytes. This lets you collide them one at a time, meaning that you only divide your set by 2 at each step, rather than 2²⁵⁶. It is fairly easy to generate short strings that leave the lowest byte unchanged by searching combinations of 2 or 4 characters for permutations of low order and then repeating them until they reach the identity. For example, “08080808080808080808080808080808” is one such string, while “000h000h000h000h000h000h000h000h” is another.</p><p>Another note is that rather than concatenating the strings explicitly, you can <a href="https://blog.polybdenum.com/2017/02/11/optimizing-rc-memory-usage-in-rust.html">represent them as a tree, with pointers to two other strings</a>, which makes things much more efficient, especially as the strings tend to grow exponentially long. In fact, using this method, the colliding strings ended up at least 2²⁴ bytes long, no matter what I tried. It’s nice for a proof of concept, but not terribly practical in actually demonstrating an attack.</p><p>At that point, I gave up on generating fully universal hash collisions, and decided to try creating 256 sets of semi-universal collisions, which would hopefully be much smaller.</p><p>One of the flaws of Python’s hash randomization scheme is that only 8 bits of the key actually mix with the hash in a nontrivial way. This means that if you fix the value of the lowest byte of the key, you can easily generate collisions, and such collisions will collide for 2¹²⁰ out of the possible 2¹²⁸ keys. However, it’s easier to pretend that the key is only 8 bits to begin with and treat these like normal hash collisions, which is what I’ll do from now on.</p><p>Anyway, this means that you don’t need a set of fully universal colliding strings to ensure hash collisions. Instead, you can just prepare 256 different sets of strings, one which collides for each possible key byte. You don’t know which set will collide, but if you include all of them in the input, one of the sets is guaranteed to cause a lot of collisions, and hence a slowdown.</p><p>Anyway, I modified the code to start with individual characters and maintain 256 colliding sets. My initial try produced 128 byte strings, which was already much shorter. After a lot of optimization and tweaks, and combining results from multiple runs with different parameters, etc. I managed to produce minimal collisions of 48–64 bytes.</p><p>Since a single pair of colliding strings isn’t that useful, my plan was to produce a larger number of colliding strings by repeatedly concatenating the smaller sets. I decided that I needed 10,000 strings to produce a noticeable slowdown. Even using A* search to choose the optimal sets to concatenate, this increased the size to 328 bytes for 10,000 strings. (It is roughly logarithmic in the number of strings you want). At that point, the files I was generating containing the colliding strings were nearly a gigabyte, and I decided that the method was impractical.</p><h3>Second try: near optimal collisions</h3><p>I decided that in order to have a practical file size, I needed colliding strings of near optimal length. Unfortunately, brute force is infeasible, so I wasn’t even sure if this was possible. Eventually, I figured out a way to do it, which relied on several key observations.</p><h4>Lossy and lossless pruning</h4><p>Since it’s not feasible to actually calculate 2⁶⁴+ strings, it is necessary to prune the search space. Doing so can either be lossy or lossless.</p><p>For example, suppose your initial search space is all 10 byte strings, or 2⁸⁰ strings. Since there are only 2⁶⁴ possible hash values, there is guaranteed to be at least a 2¹⁶ way collision. Now suppose you restrict your search space to strings whose hash ends in the most popular lowest 16 bits. By the pigeonhole principle, there are at least 2⁶⁴ of these. However, there are now only 2⁴⁸ possible hash values. Therefore, you are still guaranteed to have a 2¹⁶ way collision. I call this type of pruning lossless, because it doesn’t reduce the worst case collision size.</p><p>Note that lossless doesn’t mean you aren’t throwing away collisions. Although improbable, there could have been a 2⁶⁴ way collision among the strings you threw out. All it means is that the ratio of search space to output space is maintained or increased, and therefore the worst case collision size is maintained.</p><p>By contrast, lossy pruning does not preserve this ratio. For example, suppose you restricted your search space to all strings whose state after 5 characters ends in the most popular lowest 16 bits. In this case, you have once again restricted your search space to (at least) 2⁶⁴ strings. However, the hash of all 10 characters mostly doesn’t care what the internal state was after 5 characters, so the output space is still 2⁶⁴ possible values. Therefore, you have thrown away the guaranteed collisions.</p><p>The reason the repeated concatenation algorithm performs so poorly is that <em>every step but the last is lossy</em>. Suppose the final output size is 2048 bytes, and these strings collide with all 64 bits. The construction of the algorithm means that these 2048 byte strings are concatenated from 1024 byte strings, where the internal state after 1024 bytes is a partial collision (up to 63 bits). This means it is a lossy way to prune the search space.</p><p>Anyway, this means that I needed to find a way to do only lossless pruning.</p><h4>Counting the most popular lower bits</h4><p>It might seem like it is impossible to actually perform this lossless pruning. After all, how can you determine which lower bit values are most popular without actually generating the strings? It turns out that this is possible.</p><p>To count the number of strings of length n whose hash has a given lowest k bits, you can create two tables of size 2^k. At each step, you iterate through the table, calculate the new state for each character in your alphabet, and then increment the corresponding entry in the other table. Essentially, you are performing a sparse matrix multiplication n-1 times. This works because in order to know the number of strings of length n with given low bits, all you need to know is the number of strings of length n-1 that have each possible low bit value.</p><p>The main limitation of this is memory usage. With 32gb of RAM, it is effectively limited to k=31, but even with unlimited memory, the time would increase exponentially with k.</p><p>Anyway, this was the code that resulted in <a href="https://blog.polybdenum.com/2017/02/19/how-copying-an-int-made-my-code-11-times-faster.html">my previous optimization post</a>. However, I later realized that this step isn’t actually necessary for generating large multi-collisions. The reason is because FNV is approximately uniformly distributed for large enough inputs. If you’re trying to find a small number of collisions among a small set of strings, it is necessary to take the most common hash value (the extreme case of this is the birthday attack). However, for larger numbers of strings this evens out. For example, if you are searching 2⁸⁰ strings, then each of the possible hash values will have roughly 2¹⁶ strings that hash to that value, with a small amount of random variation. Therefore, you can take any arbitrary end state and get almost the same number of strings. In my final version, I just find strings that hash to the value 0.</p><p>Although I didn’t end up using it in the final version, I included the code anyway, as the function get_common_lowest(), since people were curious after my last post.</p><h4>Meet in the middle</h4><p>Even once you’ve decided to restrict your search to strings which hash to 0, it’s not immediately obvious how that helps, since you can’t determine which strings hash to 0 without generating and hashing them all.</p><p>Suppose you have two lists of N ints, and you want to find all pairs that are equal mod 2^k. The naive approach of looping through all pairs is O(N²), but as it turns out, there is a much faster approach. Just sort the lists (using the low bits as sort key), and iterate through them both in order. This lets you find all the matching pairs in O(N) time, or more accurately, O(N+M) time where M is the number of output pairs. (In the degenerate case, all the ints are equal mod 2^k and M = N²).</p><p>Now suppose that the two lists are of the hashes of strings of length n, and you want to find the strings of length 2n whose hash is equal to e mod 2^k. The action/hash of concatenated strings can be expressed as a simple equation.</p><pre>act(lhs + rhs)(i) = (act(lhs)(i)-j)*P^len(rhs) + act(rhs)(j) <br>where j = act(lhs)(i) mod 256</pre><p>Assuming you’ve dealt with the nonlinearity in the lowest bits (I’ll explain how below), the equation is just</p><pre>act(lhs+rhs) = act(lhs)*Pn + act(rhs)</pre><p>where Pn is the appropriate power of P. If you let a = act(lhs) and b = act(rhs), then you’re essentially trying to find pairs which satisify the equation</p><pre>a*Pn + b = e mod 2^k</pre><p>If you multiply every number in the first list by Pn and subtract from e, you get</p><pre>a&#39; = e - a * Pn<br>a&#39; = b mod 2^k</pre><p>But that’s just the pair matching problem described earlier, and hence can be solved in linear time.</p><p>This meet in the middle step means that you can effectively search N² strings in time O(N + M) where M is the number of output strings. Without any pruning, M would just be N² and there is no speedup. However, the lossless pruning lets us reduce M, giving a potentially quadratic speedup.</p><p>Without further improvements, this still takes an impractically large amount of memory. For example, if you want a 2¹⁶ way collision, you need to search 2⁸⁰ strings, meaning that the two lists of half-strings must have 2⁴⁰ entries each, which is obviously not possible in 32GB of ram. Additionally, I skated over the issue of how to ensure the lowest bytes match up.</p><h4>Recursive meet in the middle</h4><p>Say for example, that you are trying to search strings of length 24, so your lists of half-strings contain strings of length 12 (or more accurately, their hash/action values, since there is no need to explicitly construct the strings at this step).</p><p>Instead of generating all 12 character strings, you choose some number s ≤ k and a target s bit value, mid. For the left hand strings, you find all 12 character strings where the lowest s bits of the hash are mid, and for the right hand side, you find all strings where starting from an initial state of mid, the lowest s bits of the hash are your goal. For s ≥ 8, this also solves the problem of making sure the nonlinearity in the lowest byte matches up.</p><p>This means that instead of lists of size N, you only need to store lists of size N/2^s, reducing the memory requirement. By itself, this is a lossy restriction. However, instead of choosing just one value of mid, you can repeat this process for all 2^s possible values of mid, meaning there is no loss.</p><p>That seems like it would multiply the time required by 2^s, but there is a further trick — apply the meet in the middle step recursively. If you choose the parameters right, the time complexity of the substeps are linear in their output size (the O(M) part above). Increasing s doubles the number of iterations in the top level function, but each of the substeps takes half as long, meaning the time is unchanged overall. Theoretically, the optimal value for s is proportional to log(N), but I found that setting it a bit lower makings things faster in practice.</p><p>Optimization note: Once the recursive splitting is added, the bottleneck is the sorting step. I tried writing several different radix sort implementations, as well as the <a href="https://crates.io/crates/quickersort">quickersort</a> and <a href="https://crates.io/crates/pdqsort">pdqsort</a> libraries. Surprisingly, the only one that was faster than Rust’s native stable sort was pdqsort, which was about 25–30% faster in my tests. This is notable mainly due to being a rare situation where a) sorting performance is the bottleneck, b) sort stability is observable, and c) unstable sort performs measurably better than stable sort. It’s also interesting that radix sort was slower than a generic comparison sort, though I may just suck at implementing fast sorts.</p><h4>Reducing nonlinearity</h4><p>Previously, I assumed that the lowest 8 bits of the state participate in nonlinearity, but I realized that that wasn’t quite true. It’s only nonlinear if some byte in the string actually has a set bit in that position or higher, since otherwise it is just being xored against 0 all the time. In particular, this means that if you are using only ascii characters like I was, you only need to worry about the lowest 7 bits.</p><p>The corollary is that using smaller character values reduces the number of states you have to consider. I restricted myself to the digits (0–9), which are all below 64, meaning that I only had 6 bits of nonlinearity to contend with. Reducing the alphabet size from 37 to 10 increases the minimum collision length, but having half as many colliding sets to generate more than makes up for it.</p><p>If the target of the DOS accepts arbitrary bytes, then you can make collisions much more effective by using only low bytes. In the extreme case, if you only use the bytes 0x00 and 0x01, there is only one bit of nonlinearity. At that point you could generate two sets of colliding strings, or just generate universal collisions, which is almost as easy with only 1 bit.</p><p>In my case, I couldn’t go below 64, since I had already decided to restrict myself to alphanumerics. There are other parts of the Krakatau assembler which accept arbitrary bytes, but I didn’t feel like attacking that, even though it’s much easier. Besides, generating colliding digit strings means the resulting strings could be used practically anywhere.</p><h4>String recovery</h4><p>At first, I tried computing the strings directly through the recursive meet in the middle method, but this turned out to be infeasibly slow. I figured this is probably due to all the intermediate strings being created, concatenated, and thrown away. Therefore, I came up with a different approach — run meet in the middle only on the hash values, and record which pair of hashes was composed to create the larger hash. Then perform this recursively until you get to short enough strings, at which point you find the strings and build it back up. This avoids creating any intermediate strings that will be thrown away, making things much faster. There are also a couple other optimizations I did which you can see in the code, such as avoiding sorting at this step.</p><h4>Putting it together</h4><p>With all this done, I was ready to generate large multicollisions in 64 bit FNV. I decided to go with 24 character strings, mainly due to memory constraints. Since the time taken to generate the strings is roughly proportional to the number of strings generated, I deliberately added a lossy partition to speed things up, which I then relaxed to generate more and more strings.</p><p>The initial four runs took a cumulative 71 hours on an i7–4790K running 8 threads, which resulted in 64 sets of colliding strings with 3206–3538 strings each.</p><p>To test Krakatau, I created one assembly file with the collided strings, and another with equal lengths of randomly generated digits as a control. That way, I could tell how much of the time was parsing overhead and how much was the hashtable slowdown.</p><p>With the 3000 strings, the difference was 6.4 seconds vs 6.8 seconds, a measureable slowdown, but a bit disappointing. Keep in mind though that this is with 64 sets of strings, only one of which collides, which effectively divides the slowdown by 64. If you only include the colliding set of strings (possible if hash randomization is not enabled, or if you’re making 64 different requests to a web server), then the difference is 0.10 seconds vs 0.62 seconds, a much more dramatic slowdown.</p><p>At that point, I realized that there is no need to generate 64 independent sets of colliding strings. If you have say, a set of strings that collides when the input state is 0 (mod 64) and a fixed prefix string that maps state i to state 0, then preprending that prefix gives you a set of strings that collides when the state is i. This means that at the cost of adding a single character, I could just generate one set of colliding strings and reuse it 64 times.</p><p>With the collision search now effectively 64 times faster, it became practical to generate many more collisions. In an additional 8 hours, I generated another 50k strings, bringing the total to 54091.</p><p>Using all 54k strings, the time difference became 114 seconds vs 414 seconds, a much more dramatic slowdown (although the filesize also grew to 229mb with this many strings). Keep in mind that if you only include one set of strings instead of 64, the difference is 1.7 seconds vs 304 seconds, and the filesize is only 3.6mb.</p><p>Anyway, all the code is <a href="https://github.com/Storyyeller/fnv-collider">available on Github</a>, as well as the collided strings I found and the script to generate the Krakatau files. If you have a Python application you are concerned about, you can use these strings to test how it responds to hash based DOS.</p><h3>XML parsing</h3><p>While reading through the discussions surrounding the original decision to add randomized hashing to Python in the python-dev archives, I noticed one comment that Python’s string hashing function is duplicated in the xml parser. Out of curiosity, I checked the source, and even in the latest Python 3.6, it is <a href="https://github.com/python/cpython/blob/227e42754059806e37aab276baa9d251059aaba6/Modules/expat/xmlparse.c#L111">still there</a>, still using the insecure FNV hash.</p><p>Presumably, it wasn’t considered important since XML parsers can be trivially DOSed through other means, such as repeated entity expansion, the “billion laughs” attack. However, this is worth noting if you are parsing untrusted XML with a “safe” library like <a href="https://pypi.python.org/pypi/defusedexpat">defusedexpat</a> which limits entity expansion but does nothing to protect against hash collisions.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5b21404a5306" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[How copying an int made my code 11 times faster]]></title>
            <link>https://medium.com/@robertgrosse/how-copying-an-int-made-my-code-11-times-faster-f76c66312e0f?source=rss-8963dc385f1f------2</link>
            <guid isPermaLink="false">https://medium.com/p/f76c66312e0f</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[Robert Grosse]]></dc:creator>
            <pubDate>Sun, 19 Feb 2017 01:33:38 GMT</pubDate>
            <atom:updated>2026-02-06T16:48:13.304Z</atom:updated>
            <content:encoded><![CDATA[<p><em>I have moved off Medium to a personal blog. Click </em><a href="https://blog.polybdenum.com/2017/02/19/how-copying-an-int-made-my-code-11-times-faster.html"><em>here</em></a><em> for the updated post.</em></p><p>Recently, after refactoring some Rust code, I noticed that it had suddenly become four times slower. However, the strange part is that I didn’t even touch the part of the code that became slower. Furthermore, it was still slower after commenting out the changes. Curious, I decided to investigate further.</p><p>The first step was to use git diff to display all changes since the previous commit, which was normal speed. Then I started removing them one by one, no matter how inconsequential, and testing to see if it was still slow after the change.</p><p>Eventually, I was left with a diff of just one print statement, added for unrelated debugging purposes, and sure enough, commenting out the print statement made the code fast again. Note that this print statement only executes once, and it isn’t even part of the code that was slow. The only thing I could think of was that it was somehow breaking the compiler’s optimizations, so I decided to try to reduce it down to a minimal example, in order to report it as a bug.</p><p>Eventually, I reduced the code down to the following:</p><pre>fn main() {<br>    let size = 1usize &lt;&lt; 25;</pre><pre>    // Adding this line causes program to go from 0.16 seconds to 1.7 seconds<br>    println!(&quot;{}&quot;, size);</pre><pre>    let mut ints = vec![0u32; size];<br>    for i in 0..size {<br>        for c in 0..8usize {<br>            ints[(i ^ c) % size] += 1;<br>        }<br>    }<br>}</pre><p>Adding the print statement causes the code to go from 0.16 seconds to 1.7 seconds, an 11x slowdown (in release mode). Then, I posted it in the rustc IRC channel, where eddyb and bluss suggested a workaround and explained what was going on.</p><p>The fix was to the change the print line to the following, which does indeed fix the slowdown.</p><pre>println!(&quot;{}&quot;, {size});</pre><p>{x} declares a statement block which evaluates to the last expression, in this case x. This means that {x} is the same as x with an extra move/copy. Normally, this is only useful for <a href="https://bluss.github.io/rust/fun/2015/10/11/stuff-the-identity-function-does/">bypassing the implicit reborrow when passing mutable references</a>. However, here there are no borrows involved. All it is doing is copying a plain int, which seems useless.</p><p>The trick is that like all generic interfaces in Rust, printing takes arguments by reference, regardless of whether they are Copy or not. The println! macro hides this from you by implicitly borrowing the arguments, which you can see by having rustc print out the macro expansions (note the (&amp;size,). In case you were wondering, this is why you can print non-copyable values without explicitly borrowing them, in seeming violation of the ownership system.</p><pre>#![feature(prelude_import)]<br>#![no_std]<br>#[prelude_import]<br>use std::prelude::v1::*;<br>#[macro_use]<br>extern crate std as std;<br>fn main() {<br>    let size = 1usize &lt;&lt; 25;<br>    <br>    // Adding this line causes program to go from 0.16 seconds to 1.7 seconds<br>    <br>    ::io::_print(::std::fmt::Arguments::new_v1({<br>                                                   static __STATIC_FMTSTR:<br>                                                          &amp;&#39;static [&amp;&#39;static str]<br>                                                          =<br>                                                       &amp;[&quot;&quot;, &quot;\n&quot;];<br>                                                   __STATIC_FMTSTR<br>                                               },<br>                                               &amp;match (&amp;size,) {<br>                                                    (__arg0,) =&gt;<br>                                                    [::std::fmt::ArgumentV1::new(__arg0,<br>                                                                                 ::std::fmt::Display::fmt)],<br>                                                }));<br>    let mut ints = ::vec::from_elem(0u32, size);<br>    for i in 0..size { for c in 0..8usize { ints[(i ^ c) % size] += 1; } }<br>}</pre><p>Passing {size} instead of size prevents println! from borrowing size . Instead, it borrows a temporary copy. However, that still doesn’t explain how the borrow causes such a huge slowdown. The other half of the story is that while Rust knows that the borrow is immutable, this information is sadly not passed to LLVM. This means that the LLVM optimizer sees that a pointer to size is being passed to some function and just gives up, leaving the following code to assume that size holds an arbitrary value. Borrowing a copy instead allows the optimizer to do its job.</p><p>You can also see this by explicitly resetting the value of size after the print call returns. This makes the code fast again, because the optimizer sees the constant value of size .</p><pre>fn main() {<br>    let mut size = 1usize &lt;&lt; 25;<br>    println!(&quot;{}&quot;, size);<br>    size = 1usize &lt;&lt; 25;</pre><pre>    let mut ints = vec![0u32; size];<br>    for i in 0..size {<br>        for c in 0..8usize {<br>            ints[(i ^ c) % size] += 1;<br>        }<br>    }<br>}</pre><p>At that point, the mystery was solved, but I was curious to see what the actual differences in code generation were that were causing the speed difference. It turns out that you can ask rustc to print out assembly as well.</p><pre>rustc -O --emit asm src/main.rs -C llvm-args=-x86-asm-syntax=intel</pre><p>It’s pretty easy to identify the inner loop in the assembly, especially since the code in this example is so small. For the optimized {size} version, the inner loop looks like this.</p><pre>.LBB0_3:<br> mov r14d, dword ptr [rbx + 4*rax + 4]<br> inc rax<br>.LBB0_2:<br> inc r14d<br> mov dword ptr [rbx + 4*rax], r14d<br> mov rcx, rax<br> xor rcx, 1<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 2<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 3<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 4<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 5<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 6<br> inc dword ptr [rbx + 4*rcx]<br> mov rcx, rax<br> xor rcx, 7<br> inc dword ptr [rbx + 4*rcx]<br> cmp rax, 33554431<br> jne .LBB0_3</pre><p>The code is pretty much as optimal as you can get, short of removing memory accesses (the optimizer could theoretically figure out that ints is just set to 8 in this toy example, but luckily, it doesn’t). In particular, the % size operation and the bounds checks in the inner loop are completely optimized away, and the outer loop condition just compares against a constant. This is possible because the optimizer realizes that the size is a) constant and b) a power of two, and thus xoring by a small value won’t go out of bounds.</p><p>By contrast, the corresponding code for the size version is unoptimized apart from the loop unrolling. It does the modulo and bounds checking on every single access, since it doesn’t know what size is.</p><pre>.LBB0_6:<br> xor edx, edx<br> mov rax, rsi<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 1<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 2<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 3<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 4<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 5<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 6<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc dword ptr [r14 + 4*rdx]<br> mov rax, rsi<br> xor rax, 7<br> xor edx, edx<br> div rbx<br> cmp rcx, rdx<br> jbe .LBB0_7<br> inc rsi<br> inc dword ptr [r14 + 4*rdx]<br> cmp rsi, rbx<br> jb .LBB0_6</pre><h4>Bonus: nonconstant size</h4><p>After seeing the above code, I was curious if the optimizations would still work when size is an unknown power of two. After all, in real world code, the size is often variable. I couldn’t figure out how to get rustc to print the nice assembly when using an external crate dependency, so I simulated the opaque parameter with an extern function instead. It obviously won’t link, but that doesn’t matter for assembly generation.</p><pre>extern {<br>    fn opaque() -&gt; usize;<br>}</pre><pre>fn main() {<br>    let bits = 14 + (unsafe{opaque()} &amp; 15);<br>    let size = 1usize &lt;&lt; bits;<br>    println!(&quot;{}&quot;, {size});</pre><pre>    let mut ints = vec![0u32; size];<br>    for i in 0..size {<br>        for c in 0..8usize {<br>            ints[(i ^ c) % size] += 1;<br>        }<br>    }<br>}</pre><p>Anyway, it turns out that the resulting code is mostly unoptimized, though still better than the previous case where the optimizer thought size was unknown.</p><pre>.LBB0_2:<br> mov rsi, rbx<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 1<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 2<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 3<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 4<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 5<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 6<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc dword ptr [r15 + 4*rsi]<br> mov rsi, rbx<br> xor rsi, 7<br> and rsi, r13<br> cmp r12, rsi<br> jbe .LBB0_3<br> inc rbx<br> inc dword ptr [r15 + 4*rsi]<br> cmp rbx, r12<br> jb .LBB0_2</pre><p>In particular, it still does the bounds checking, and it still does the % size part. However, it is at least smart enough to do the modulo via bitwise and instead of a full division operation. On the other hand, the bounds checking is far from ideal. It makes me wonder whether it would be worth it to hand monomorphize performance critical code like this and duplicate it for every possible power of two and then switch on size to call one of these functions at runtime, to get the full optimization potential.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f76c66312e0f" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>