search

starkware-libs / veedo

Other
75 stars 19 forks source link

(documentation) STARK proof soundness #2

Open JustinDrake opened 3 years ago

JustinDrake commented 3 years ago

What is the soundness (ideally provable soundness) of the VeeDo STARK proof being produced?

elibensasson commented 3 years ago

It's 80 bits of security: 30 bits PoW grinding + 50 bits from 10 sets of FRI queries using a rate of 2^{-5}.

JustinDrake commented 3 years ago

80 bits of security

Is that 80 bits of provable soundness or 80 bits of conjectured soundness using conjecture 7.3 in BCIKS20? I'm also curious what DeversiFi has in terms of soundness :)

elibensasson commented 3 years ago

It's the latter, which is also what we use for Deversifi. There, for a 1K size batch of trades we use 32 bits PoW grinding and 48 bits from 12 FRI queries at a rate of 2^{-4}. BTW, calling either case "soundness" is misleading, and "provable soundness" is even more problematic because once you use a hash function for a commitment scheme there's no more soundness (certainly not provable). Soundness should be reserved to the IOP model (which, alas, is unrealistic).

Best Eli

On Sun, Aug 9, 2020 at 11:35 AM Justin notifications@github.com wrote:

80 bits of security

Is that 80 bits of provable soundness or 80 bits of conjectured soundness using BCIKS20? I'm also curious what DeversiFi has in terms of soundness :)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/starkware-libs/veedo/issues/2#issuecomment-671024381, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABYCHABE23GHI7N4UKEOJLLR7ZNULANCNFSM4PX73IRA .