Soundness Error in BrainSTARK (aszepieniec.github.io)

It turns out there is an attack on the BrainSTARK proof system [1]. The tutorial was extended to explain and fix the attack.

[1]: https://aszepieniec.github.io/stark-brainfuck/

Unfortunately this can add some overhead to the memory table though. I wonder if there's a better solution than the one proposed here. Not that it matters for Brainfuck too much, as it's a toy language, but it would be very relevant for bigger STARK VMs.

Worth noting is that this solution does not constrain the memory value of the last execution trace if the execution trace ends with a `>` or a `<`. Since this value cannot be output, you could argue that that's OK.

Building sound and complete STARKs are really an intricate affair! I have no doubt that we'll eventually get there though!