search

oasisprotocol / oasis-core

Performant and Confidentiality-Preserving Smart Contracts + Blockchains
https://oasisprotocol.org
Apache License 2.0
338 stars 113 forks source link

Zero polynomial representation inconsistent with no trimming; no unique representation #5828

Open bennetyee opened 3 months ago

bennetyee commented 3 months ago

https://github.com/oasisprotocol/oasis-core/blob/18da8bc49d92a543795246b8bb7fb574df070eec/secret-sharing/src/poly/univariate.rs#L19

Since there is no trimming, adding two polynomials together can result in a zero polynomial that is represented by a vector of zero coefficients the length of which is not one.

Without trimming, we no longer have unique representation, so polynomial comparisons need to be done by ignoring leading zero coefficients, or there should be a warning that this is not "generic" non-binary finite field polynomials that work the way most people would expect.

peternose commented 3 months ago

Since there is no trimming, adding two polynomials together can result in a zero polynomial that is represented by a vector of zero coefficients the length of which is not one.

True. The comment should be fixed here. What I wanted to say is that the zero polynomial with zero degree is represented with a vector [0] and not with [].

Without trimming, we no longer have unique representation

True. But in our case, the representation is unique as we are always dealing with polynomials of the same size. So the zero polynomial will always be represented with a vector of zeros.

If we use trimming, we don't have constant time operations. Therefore, trimming is ignored and was removed from the code.

So polynomial comparisons need to be done by ignoring leading zero coefficients

Currently, we never compare polynomials, so this is not needed. But if we did, we would need to state that zero polynomials of different sizes are not the same (or are the same, whatever we want to choose).

bennetyee commented 3 months ago

It'd be nice if there were comments/docstrings that explain the limitations and that this was not intended to be general purpose. Or the Polynomial could have more limited visibility (pub (crate)?) This is a minor nit.

It looks like p384 is supposed to be constant time but has not been independently audited yet. This is probably fine (for now), but that the expectation that types here are instantiated with PrimeField implementations that are constant time should be documented, since the algorithms do not try to do randomized blinding to allow the use of non-constant time arithmetic at the cost of putting in / removing blinding factors.