halo2 icon indicating copy to clipboard operation
halo2 copied to clipboard

Use smaller extended domains where possible during proving

Open str4d opened this issue 2 years ago • 6 comments

We perform polynomial operations over an extended Lagrange basis that is large enough to contain the results of evaluating expressions on the largest polynomials: https://github.com/zcash/halo2/blob/18e13b1d093113c93387d38e188d7dc85c64e1ec/src/poly/domain.rs#L46-L52

However, not all of the polynomials need the full extended domain. We could instead group the polynomials on the basis size they require, and then evaluate sub-expressions that only involve these polynomials using their respective basis. It is possible to efficiently extract a smaller basis from a larger one, so the cost of generating these multiple bases should be small compared to the efficiency gains from reducing the basis sizes used in many of the circuit operations.

This blocks on #360 because we need to "transpose" how we operate on polynomials (moving parallelization to the start of the call chain instead of the end) for that issue, and once we are applying full expressions to chunks of polynomials, it becomes natural to introduce smaller polynomial bases.

str4d avatar Dec 10 '21 17:12 str4d

I currently believe that addressing this issue would resolve the performance problem noted in https://github.com/zcash/halo2/issues/418#issuecomment-989568648.

str4d avatar Dec 10 '21 17:12 str4d

Actually, having looked more closely at https://github.com/zcash/halo2/issues/418#issuecomment-989568648, I think it's being caused by the fact that we don't cache rotated polynomials, so if the same (polynomial, rotation) pair is used multiple times within an expression, we'll rotate it multiple times. So I think this will actually be addressed by #360, where we'll need to pre-compute all the polynomials used in an expression in order to the parallelize at the top, and in doing so will eliminate duplicate rotations.

str4d avatar Dec 10 '21 17:12 str4d

Sorry for a dumb question, but I don't see which polynomials need an extended domain? I was actually wondering how and whether at all extended domain is needed for custom constraint polynomials because I am having some issues with a high degree for Merkle Patricia Trie circuit which consequently uses quite an extension of the original domain.

miha-stopar avatar Dec 13 '21 08:12 miha-stopar

Sorry for a dumb question, but I don't see which polynomials need an extended domain? I was actually wondering how and whether at all extended domain is needed for custom constraint polynomials because I am having some issues with a high degree for Merkle Patricia Trie circuit which consequently uses quite an extension of the original domain.

Ah, had another look and I think I see it now. There is a poly (like in vanishing/prover.rs, construct method):

h_poly = l^0 + expr_0 + l^1 * expr_1 + ... + l^n * expr_n

where each expr_i is of the form p(a(x), b(x), c(x)) where p is a poly of the degree at most m and a(x), b(x), c(x) describe the columns (let's say we only have three). Polynomials a(x), b(x), c(x) are of the degree at most n, so h_poly is a poly of degree (at most) m*n - and after dividing by vanishing polynomial, we need enough space to interpolate it (which we don't have if the domain is not extended).

miha-stopar avatar Dec 14 '21 08:12 miha-stopar

Yep (though I think it's actually (m-1)*n IIRC - there's an off-by-one in there of which I always forget the origin). The idea for this issue is to break down and combine the various expr_i into sub-expressions involving columns that are only used at common smaller degrees. e.g. if the maximum degree is 7, but a(x) and b(x) are only involved in degree-4 sub-expressions, then we only need to operate on c(x) in the largest extension domain.

str4d avatar Dec 14 '21 12:12 str4d

Off-by-one is probably because of division by vanishing poly x^n - 1 which reduces the degree by n. I was thinking a bit how to implement this optimisation, but I worry it wouldn't be much of a speed up. The beauty of multi-opening is that there is FFT only for one polynomial needed, if there would be k-sub-expressions, FFT interpolation would be needed for each of them to get the final h poly. Do you think it's worth it?

miha-stopar avatar Jan 31 '22 07:01 miha-stopar