Soundness Error in BrainSTARK(aszepieniec.github.io)

7 pointsby aszepieniec4 ปีที่แล้ว3 comments

aszepieniec.github.io

https://aszepieniec.github.io/stark-brainfuck/attack.html

3 comments

sword_smith4 ปีที่แล้ว

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!

sword_smith4 ปีที่แล้ว

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.

aszepieniec4 ปีที่แล้ว

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/