search

ethereum / c-kzg-4844

A minimal implementation of the Polynomial Commitments API for EIP-4844 and EIP-7594, written in C.
Apache License 2.0
118 stars 109 forks source link

Fix edge case in expand_root_of_unity #375

Closed jtraglia closed 1 year ago

jtraglia commented 1 year ago

Valgrind pointed out usage of an uninitialized value in our tests. Since this is part of the trusted setup initialization, I expect this would never happen, but good to fix nevertheless.

==501666== Conditional jump or move depends on uninitialised value(s)
==501666==    at 0x40A5A6: fr_is_one (in /home/devops/jtraglia/c-kzg-4844/src/test_c_kzg_4844)
==501666==    by 0x40A556: expand_root_of_unity (in /home/devops/jtraglia/c-kzg-4844/src/test_c_kzg_4844)
==501666==    by 0x40952E: test_expand_root_of_unity__fails_wrong_root_of_unity (in /home/devops/jtraglia/c-kzg-4844/src/test_c_kzg_4844)
==501666==    by 0x4031C1: tt_execute (in /home/devops/jtraglia/c-kzg-4844/src/test_c_kzg_4844)
==501666==    by 0x403AA3: main (in /home/devops/jtraglia/c-kzg-4844/src/test_c_kzg_4844)

In the following test, we provide the wrong root of unity, which causes the loop in expand_root_of_unity to break early. Here, the width is 256 but the look will break at 128 (because it encountered a value of one).

https://github.com/ethereum/c-kzg-4844/blob/b2e41491ad1859f1792964a2432a419b64dc6fb2/src/test_c_kzg_4844.c#L1719-L1727

In expand_root_of_unity, if the loop breaks early, the final check will occur on an uninitialized value:

https://github.com/ethereum/c-kzg-4844/blob/b2e41491ad1859f1792964a2432a419b64dc6fb2/src/c_kzg_4844.c#L1563-L1567

I also added CHECK(width >= 2) as a sanity check and changed the loop to be more "natural" IMO.

asn-d6 commented 1 year ago

Can we just add the check CHECK(i == width); without changing the loop logic?

I feel like this is a non-trivial loop logic and the less we change it the better.

jtraglia commented 1 year ago

IIRC you'd have to compare i to width - 1. It's not as pretty. I think this way is safer.

ppopth commented 1 year ago

Even though, it changes the loop logic, I think the latter is a lot easier to understand (like you can know the maximum number of iterations immediately)