accumulator/batchproof: Remove the numTargets max check in deserialize

[kcalvinalvin]

In mainnet, the check for 1<<16 numTargets doesn't work because there's a mainnet block that crashes with this but doesn't with 1<<31. Not sure which block and exactly how many inputs it's referencing.

utreexo/accumulator/batchproof.go

Lines 108 to 111 in 71712c4

	if numTargets > 1<<16 {
	err = fmt.Errorf("%d targets - too many\n", numTargets)
	return
	}

But this is just a check to see if the proof was serialized correctly right? We should remove the whole check completely and replace it with some tests.

[adiabat]

It's weird because the numbers seem close to 65K, not like millions / billions, suggesting that numTargets might actually be correct.

But it can't be; numTargets should be at most the number of inputs in a block (less the skipped 0-conf inputs), and there can't be 65K inputs in a bitcoin block. They all have at least 36 byte (32 byte txid, 4 byte index) outpoints, meaning there can be at most 27777 targets in a block. And realistically much fewer.

So something else weird is going on, like too many targets being added, duplicate targets, or targets that don't correspond to inputs or something...

[kcalvinalvin]

It's weird because the numbers seem close to 65K, not like millions / billions, suggesting that numTargets might actually be correct.

But it can't be; numTargets should be at most the number of inputs in a block (less the skipped 0-conf inputs), and there can't be 65K inputs in a bitcoin block. They all have at least 36 byte (32 byte txid, 4 byte index) outpoints, meaning there can be at most 27777 targets in a block. And realistically much fewer.

So something else weird is going on, like too many targets being added, duplicate targets, or targets that don't correspond to inputs or something...

Might also just be the utcd code ugh...

[kcalvinalvin]

 func (bp *BatchProof) Serialize(w io.Writer) (err error) {
+       if len(bp.Proof) > 1<<16 {
+               err = fmt.Errorf("%d targets - too many\n", len(bp.Proof))
+               panic(err)
+       }

Panics when doing this (tested on commit 71712c452df5e77f9f593261ad0229765995dcac). We're likely re-adding targets or something.. :/

EDIT:

So in the code snippet below, we're adding extra data besides the proofs so it's possible to be greater than 1<<16. It's proof + sorted targets that we're putting in the proofs.

utreexo/accumulator/forestproofs.go

Lines 172 to 189 in deb3c4c

	// targets need to be sorted because the proof hashes are sorted
	// NOTE that this is a big deal -- we lose in-block positional information
	// because of this sorting. Does that hurt locality or performance? My
	// guess is no, but that's untested.
	sortedTargets := make([]uint64, len(bp.Targets))
	copy(sortedTargets, bp.Targets)
	sortUint64s(sortedTargets)
	positionList := NewPositionList()
	defer positionList.Free()
	ProofPositions(sortedTargets, f.numLeaves, f.rows, &positionList.list)
	targetsAndProof := mergeSortedSlices(positionList.list, sortedTargets)
	bp.Proof = make([]Hash, len(targetsAndProof))
	for i, proofPos := range targetsAndProof {
	bp.Proof[i] = f.data.read(proofPos)
	}