<p>You can reconstruct the elements whenever you have <em>2c</em> consecutive power sums for <em>k=a</em> until <em>k=a+2c-1</em> (power sum <em>S<sub>k</sub></em> is <em>x<sub>1</sub><sup>k</sup> + x<sub>2</sub><sup>k</sup> + ... x<sub>n</sub><sup>k</sup></em>) of the elements, regardless of which <em>a</em> you start at.</p>
<p>However, since PinSketch works in a <a href="https://en.wikipedia.org/wiki/Characteristic_(algebra)" rel="nofollow noreferrer">characterstic</a>-2 field, it holds that <em>(a + b)<sup>2</sup> = a<sup>2</sup> + b<sup>2</sup></em> (the <a href="https://en.wikipedia.org/wiki/Freshman%27s_dream" rel="nofollow noreferrer">Freshman's dream</a>). Because of that, it holds that <em>S<sub>2k</sub> = S<sub>k</sub><sup>2</sup></em>, or in other words, we can compute the even power sums by squaring the half power sum. Thus, having the odd power sums between <em>k=1</em> and <em>k=2c-1</em> (i.e., setting <em>a=1</em>) suffices to reconstruct all power sums (including even ones) up to <em>k=2c</em> too.</p>
<p>There is a more elaborate description in the Miniscript code <a href="https://github.com/sipa/minisketch/blob/master/doc/math.md" rel="nofollow noreferrer">documentation</a>.</p>

CC BY-SA 4.0
2024-02-08T17:10:35.410Z
Thanks! That's a very clever trick :-)
Cosmik Debris
CC BY-SA 4.0
2024-02-08T17:24:18.160Z
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?
Cosmik Debris
CC BY-SA 4.0
2024-02-08T17:58:12.583Z
@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.
Pieter Wuille
CC BY-SA 4.0
2024-02-09T13:12:24.317Z
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.
Cosmik Debris
CC BY-SA 4.0
2024-02-08T16:55:56.577Z
2024-02-08T16:55:56.577Z
Pieter Wuille
<p>The following is taken from <a href="https://github.com/bitcoin/bips/blob/master/bip-0330.mediawiki#user-content-Short_transaction_ID_sketches" rel="nofollow noreferrer">BIP-330</a> (aka Erlay):</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>Why is it that the first c <em>odd</em> 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 <a href="https://en.wikipedia.org/wiki/Newton%27s_identities" rel="nofollow noreferrer">Newton's identities</a> if we had their first c, but it is not obvious to me how to do so with just the odd ones.</p>

<bitcoin-core-development><p2p><relay>
Why do PinSketch sketches consist of the sum of odd powers?
Cosmik Debris
# Why do PinSketch sketches consist of the sum of odd powers?

(Asked by: username_0 on 2024-02-08)

The following is taken from [BIP-330](https://github.com/bitcoin/bips/blob/master/bip-0330.mediawiki#user-content-Short_transaction_ID_sketches) (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](https://en.wikipedia.org/wiki/Newton%27s_identities) if we had their first c, but it is not obvious to me how to do so with just the odd ones.

**Tags:** bitcoin-core-development, p2p, relay


---

## 1 answers

### Answer by username_1 on 2024-02-08. Score: 2 | Accepted answer

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](https://en.wikipedia.org/wiki/Characteristic_(algebra))-2 field, it holds that *(a + b)2 = a2 + b2* (the [Freshman's dream](https://en.wikipedia.org/wiki/Freshman%27s_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](https://github.com/sipa/minisketch/blob/master/doc/math.md).

> **Comments:**
> **username_0**: Thanks! That's a very clever trick :-)  
> **username_0**: 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?  
> **username_1**: @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.  
> **username_0**: 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.  

---

