3 ms·
Soundness Error in BrainSTARK
- aszepieniec 4y agoIt 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/ https://aszepieniec.github.io/stark-brainfuck/
- sword_smith 4y agoUnfortunately 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.
- sword_smith 4y agoWorth 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!