1

The following is taken from BIP-330 (aka Erlay):

A short ID sketch with capacity c consists of a sequence of c field elements. The first is the sum of all short IDs in the set, the second is the sum of the 3rd powers of all short IDs, the third is the sum of the 5th powers etc., up to the last element with is the sum of the (2c-1)th powers.

Why is it that the first c odd powers are picked instead of the first c? How is it that we can reconstruct those c elements from their first c odd power sums? It is more or less straightforward using Newton's identities if we had their first c, but it is not obvious to me how to do so with just the odd ones.

1 Answer 1

2

You can reconstruct the elements whenever you have 2c consecutive power sums for k=a until k=a+2c-1 (power sum Sk is x1k + x2k + ... xnk) of the elements, regardless of which a you start at.

However, since PinSketch works in a characterstic-2 field, it holds that (a + b)2 = a2 + b2 (the Freshman's dream). Because of that, it holds that S2k = Sk2, or in other words, we can compute the even power sums by squaring the half power sum. Thus, having the odd power sums between k=1 and k=2c-1 (i.e., setting a=1) suffices to reconstruct all power sums (including even ones) up to k=2c too.

There is a more elaborate description in the Miniscript code documentation.

4
  • Thanks! That's a very clever trick :-) Commented Feb 8 at 17:10
  • Just one more extra question: doesn't it suffice with the first c power sums? Given c elements x_1, ..., x_c, one can reconstruct the c elementary symmetric polynomials evaluated in x_1, ..., x_c with the first c power sums. The polynomial prod (x-xi) has those elementary symmetric polynomials as coefficients, and since it has integral simple roots those can be found by bisection. Am I missing some detail here? Commented Feb 8 at 17:24
  • @CosmikDebris If that were true, you'd be able to communicate c elements by only sending c/2 powersums - that's information theoretically not possible, so there must be something wrong in your reasoning. Commented Feb 8 at 17:58
  • 1
    Yup, you're absolutely right. What I meant by a bisection argument above referred to checking signs and using the mean value theorem but that obviously works for polynomials over Z, not for polynomials over a finite field. Thanks again. Commented Feb 9 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.