Use memory-efficient Merkle tree computation when generating proofs

[noahfigueras]

When trying to compute proofs, for the beacon state validators array, it brakes with the following error:

memory allocation of 35184372088800 bytes failed
Aborted (core dumped)

I assume this is cause due to the following line allocating the full node_count space. But, this can cause problems with bigger size lists especially if they are not full. For example if we try to proof that a validator in the BeaconState is active or exists, on computing that proof it will brake due to allocating too many slots on the buffer for empty nodes as it will try to allocate slots for the full list up to VALIDATOR_REGISTRY_LIMIT.

You can reproduce it with the following code:

    const VALIDATOR_REGISTRY_LIMIT: usize = 1099511627776;

    let vec = vec![100u64, 1000u64];

    let h = List::<u64, VALIDATOR_REGISTRY_LIMIT>::try_from(vec).unwrap();
    let p = h.prove(&[1.into()]);

[ralexstokes]

hi @noahfigueras thanks for this!

I think your assessment is correct and basically I used a more naive version of Merkle tree computation for proving as for the initial implementation I focused on getting the APIs right and everything else around the proof generation/verification

Instead, the line you linked should use this implementation which is memory-efficient and I think will resolve this problem

I haven't had time to update the implementation but PRs are very welcome!

[ralexstokes]

I think a nice way forward would be to adjust Tree so that it can handle "virtual" nodes (subtrees that are instances of a "zero" tree) and then refactor merkleize_chunks_with_virtual_padding so that it uses this updated Tree (so just returning the root node in this function), and then during proving the Tree can just be walked (via generalized indices) to compute the necessary internal nodes in a memory-efficient way

[ralexstokes]

ah, this is referenced in #141 btw

[noahfigueras]

hi @ralexstokes! I think that's good approach, I'll try to get this working. Is it ok moving merkleize_chunks_with_virtual_padding inside Tree?