Add More Test Coverage for Longer, Dynamic SSZ Lists

[rauljordan]

TL;DR - SSZ tests are not exhaustive for dynamic lists with many elements in them.

Context

Our Go-SSZ library is currently up-to-date with v0.8 and passing all latest spec tests, both minimal and mainnet. However, we encountered something quite interesting in slot/block sanity tests when it came to SSZ. Our hash tree root for the beacon state in all the slot/block sanity tests was failing and returning a different root than what the spec wants. We were confused as we were indeed passing all types of spec tests. We noticed, however, that the SSZ spec tests do not cover cases where dynamic lists have a lot of elements (the slot sanity tests had 512 validators in the registry of the state).

We found a discrepancy between Python and Go in mixInLength when converting the length of an object into a 256-bit number. In Python, following code returns:

>>> balances = [32 for _ in range(512)}
>>> print(f"0x{len(balances).to_bytes(32, 'little').hex()}")

0x0002000000000000000000000000000000000000000000000000000000000000

The same code in Go, however, returns:

balances := make([]uint64, 512)
buf := make([]byte, 32)
binary.PutUvarint(buf, uint64(len(balances)))
fmt.Printf("%x\n", buf)

// Prints...
0x8004000000000000000000000000000000000000000000000000000000000000

It turns out we had to use a different method of putting the length into a buffer than binary.PutUvarint, however, we expected SSZ spec tests to have covered these cases. It turns out that if there were a single SSZ spec test case that had lists with lengths as big as the ones in the sanity tests, we could have caught this bug earlier.

[protolambda]

Yes, the SSZ spec doesn't include Var-ints. Var-ints are simply not the same as uint256, they encode numbers in 7 bits per byte, with the last bit signifying an extended number (reading the next 7 bits from the next byte). It's used in a few places in Eth1, but nowhere in Eth 2 (yes, bitlists are encoded similar, but not the same), so I am quite surprised that you even encode it like that.

But fair enough, we can put higher list sizes in some spec tests. Good for the extension of the ssz-generic test suite later.

For now I recommend copying the ssz tests in https://github.com/ethereum/eth2.0-specs/blob/dev/test_libs/pyspec/eth2spec/utils/ssz/test_ssz_impl.py

(We will change them to vectorized tests later, but 0.8 updates + more tooling first)

[rauljordan]

Hi @protolambda totally - we shouldn't have been encoding it that way but it was just a bit tricky that no SSZ spec tests failed due to that. Our wrong approach/bug could have been caught through better coverage from the spec tests, however.

[protolambda]

It was an off-by-28 :sweat_smile: And coverage didn't catch it, as branch/line coverage is the same for different lengths mix ins. Current limit is at 100 items to put in a dynamic list, but your bug only triggered after 127 (more than 7 bits). Sure is a fun one.