search

pluto / ronkathon

Cryptography Educational Foundations
https://pluto.xyz/blog/ronkathon-learn-cryptography-from-first-principles
Apache License 2.0
191 stars 23 forks source link

Migrate binary field from struct to enum. #126

Closed jtriley-eth closed 4 months ago

jtriley-eth commented 4 months ago

Refactors BinaryField from being a usize container to a sum type of Zero and One.

Also adjusts tests and binary field extensions.

supragya commented 4 months ago

Curious if this is the best way for representation here. Would you create an enum for ternary field too with three elements inside?

Generally, goes for any F_p if p is known btw.

I guess for consistency's sake this is not the best possible thing.? But I may be wrong.

jtriley-eth commented 4 months ago

it's tricky

enshrined numeric data types tend to emerge from the underlying processor, $2^8, 2^{16}, 2^{32}, 2^{64}, ...$, the usize wrapper makes sense from a hardware perspective, and would likely be more performant since it's corresponding to XOR and AND cpu instructions rather than pattern matching branches.

but from a type theoretic perspective, a sum type is the cleanest well-constrained representation of a binary field element. it uses the type checker to signal to the compiler the valid states of the type. the existing implementation enforces two states in its construction, but not its implementation. that is to say while you can't construct an invalid field element via BinaryField::new, it is possible to construct or mutate one through other functions as, by definition, its cardinality depends on usize.

a ternary field and, by extension, all prime fields, would ideally be defined in this way. using product types wouldn't work for prime fields bc the cardinality of a product type is definitionally not prime. however, obviously this doesn't scale in rust. recursive types are poorly handled and a prime field sum type with literally 115792089237316195423570985008687907853269984665640564039457584007908834671663 elements is ofc impossible.

so there's a balance to be struck. personally, i'd write a ternary field in the same way (sum type), but anything beyond single or low double digit primes is off the table imo. however, i do think the prime field type should be generalized in a way that accepts arbitrary internal field element types to generalize. ie PrimeField<BinaryField>, PrimeField<U256>, etcetc. ofc there's no way to really constrain the huge primes the same way, but i think where it's feasible we should constrain it to a sum type.

(or we could just do BinaryField(bool) lol)