eth/tracers/logger: accessList.equal performs extraneous checks that are mathematical contradictions after a length equality check

[odeke-em]

If we look at this code

go-ethereum/eth/tracers/logger/access_list_tracer.go

Lines 61 to 74 in 111a1b7

	// Cross reference the accounts first
	if len(al) != len(other) {
	return false
	}
	for addr := range al {
	if _, ok := other[addr]; !ok {
	return false
	}
	}
	for addr := range other {
	if _, ok := al[addr]; !ok {
	return false
	}
	}

Bug or unnecessary code

There are extraneous checks

Reasoning

Firstly we notice:

1. We have affirmed that len(al) == len(other)
2. al and other are Go maps for which a strong hashing algorithm wyhash; and have unique elements in them hence are technically by composition a "set" mathematically

Mathematically if set A and set B have the same number of elements and each element were unique; checking membership of all elements of A in B is reflexive as checking elements of B in A. If an extra element existed in A that wasn't in B and vice versa, then by definition that would be a contradiction of a set and failed precondition of len(A) == len(B), even if A and B weren't sets

Suggestion

We can remove the 2 extraneous checks that I highlighted and only check once so

func (al accessList) equal(other accessList) bool {
	// Cross reference the accounts first
	if len(al) != len(other) {
		return false
	}
	for addr := range al {
		if _, ok := other[addr]; !ok {
			return false
		}
	}

	// Accounts match, cross reference the storage slots too
	for addr, slots := range al {
		otherslots := other[addr]

		if len(slots) != len(otherslots) {
			return false
		}
		for hash := range slots {
			if _, ok := otherslots[hash]; !ok {
				return false
			}
		}
	}
	return true
}

and that should shave off unnecessary CPU cycle and RAM burn.

[karalabe]

Yes, you're correct. Please open a PR.

Generally these cross check constructs are used in tests where if there's a mismatch, we'd also like to list out each difference. In this case however, it's pointless as you've also noted.

[holiman]

SGTM!

[odeke-em]

Thank you @karalabe and @holiman! I've mailed out a PR #24663 along with benchmarks to exhibit the benefits too.

[karalabe]

Closing this issue to keep the tracker slimmer, please patch up the PR and we'll merge it.