search

0xPolygonZero / zk_evm

Apache License 2.0
86 stars 38 forks source link

`StarkColumnsView<T>` structs for other STARKs #312

Open gio256 opened 5 months ago

gio256 commented 5 months ago

Currently the CpuStark and KeccakSpongeStark use structs to represent their respective columns, while other starks use raw indices into their columns. Is there a reason for this difference, or would some PRs refactoring other starks to use StarkColumnsView<T> structs be helpful?

The CpuColumnsView struct:

https://github.com/0xPolygonZero/zk_evm/blob/baecefcbaa411c77fb5135c626a954c7d88f3028/evm_arithmetization/src/cpu/columns/mod.rs#L58-L95

compared to the columns defined in the MemoryStark:

https://github.com/0xPolygonZero/zk_evm/blob/baecefcbaa411c77fb5135c626a954c7d88f3028/evm_arithmetization/src/memory/columns.rs#L5-L21

Nashtare commented 5 months ago

That's indeed something that's been bugging me for a while but I never got to get around it. The view approach is cleaner IMO, although it may require some workarounds for clean column index access (typically for range-check) as visible on the KeccakSpongeStark side. There's also a bit of code smell for all the associated unwrap() when converting the views to slices but these are pretty harmless given the sizes are known at compile time.

gio256 commented 5 months ago

Valida uses a derive macro to implement Borrow and BorrowMut for their column views. Would something similar for the boilerplate column view impls be convenient? I have mixed feelings about hiding unsafe code in proc macros, but it could make things a bit cleaner.

gio256 commented 5 months ago

Similar to #311, this would require a standalone sub-crate for proc macros.

Nashtare commented 5 months ago

I have mixed feelings about hiding unsafe code in proc macros

In general I'd also tend to advise against, but in this particular scenario of StarkColumnsView we have safety guarantees when calling transmute() so this seems fine to me. And indeed it may make things cleaner, but no strong opinion, I'm not too bothered by the current way of implementing Borrow manually.

Nashtare commented 4 months ago

Remains:

I haven't had time to handle them yet. Feel free to pick them up, or I'll do them sometime in the coming weeks.