search

0xPolygonZero / plonky2

Apache License 2.0
763 stars 285 forks source link

Add Support for Batch STARKs with Proving, Verification, and Recursion #1600

Closed sai-deng closed 2 months ago

sai-deng commented 3 months ago

The method used in this PR can be found in Section 3.2 in the paper.

Nashtare commented 3 months ago

Hey @sai-deng! Thank you for the PR! As this is quite dense, could you write some explanation about the approach taken, and any specific parts that may help reviewers? Also could you explain how this impacts STARK recursive verification now that they're batched together? Thanks!

sai-deng commented 3 months ago

Hey @sai-deng! Thank you for the PR! As this is quite dense, could you write some explanation about the approach taken, and any specific parts that may help reviewers? Also could you explain how this impacts STARK recursive verification now that they're batched together? Thanks!

The paper is still WIP, the method used in this PR can be found in Section 3.2

sai-deng commented 3 months ago

Still in the middle of reviewing. Looks really nice!

I have a random question: from what I'm seeing you can only open leaves from the bottom layer, and you open all intermediary leaves you encounter on your way to the top. If for some reason you want to open only a leaf from one of the smaller trees, can't you have a shorter proof starting at the smaller tree's height?

Thanks for reviewing! In this case, you'd better not use a field Merkle tree since it will not reduce the Merkle proof size.

sai-deng commented 3 months ago

Fairly minor comments as well for now, will do another pass at FRI later.

Thanks for the careful reviews! Comments are addressed in 59d637f.

hratoanina commented 3 months ago

I have a question with regards to STARK batching in general. From section 3.3 of the paper, I understand that for each individual STARK you pad it to the maximum length it can have given a normal execution (determined via testing with a bunch of different inputs) to have a fixed length you can build a recursion circuit from. In our zkEVM, we have very wide discrepancies between best and worst case scenarios for individual trace lengths, which can range e.g. from 16 to 2^20. Does that mean we would be forced to make a circuit accommodating a 2^20-length trace, and pad the trace to this length for every single execution?

sai-deng commented 3 months ago

I have a question with regards to STARK batching in general. From section 3.3 of the paper, I understand that for each individual STARK you pad it to the maximum length it can have given a normal execution (determined via testing with a bunch of different inputs) to have a fixed length you can build a recursion circuit from. In our zkEVM, we have very wide discrepancies between best and worst case scenarios for individual trace lengths, which can range e.g. from 16 to 2^20. Does that mean we would be forced to make a circuit accommodating a 2^20-length trace, and pad the trace to this length for every single execution?

Yes, we have to pad the trace to a length of 2^20. Alternatively, we can use a Merkle tree to save all the valid recursion circuits hash and treat the Merkle root hash as the public parameters.

hratoanina commented 3 months ago

Hi @sai-deng, sorry for the wait! I'm currently implementing STARK batching on our zkEVM alongside the review, which I treat as another layer of testing. I should be done by the end of the week; if there's no issue I'll approve the PR then!

sai-deng commented 3 months ago

Hi @sai-deng, sorry for the wait! I'm currently implementing STARK batching on our zkEVM alongside the review, which I treat as another layer of testing. I should be done by the end of the week; if there's no issue I'll approve the PR then!

Batch STARKs are already implemented in our zkVM; unfortunately, the code is not open-sourced yet. Let me know if you need any help during the implementation.