# Write up - EPF Progress (0625)

## Introduce new function: `ProofByFieldIndex`

> You can see a draft PR in [this link](https://github.com/OffchainLabs/prysm/pull/15443).

As I mentioned at the [last dev update](https://hackmd.io/@junsong/S1gNy3INgx), there are some redundant code that can be simplified (e.g. `CurrentSyncCommitteeProof`, `NextSyncCommitteeProof` and `FinalizedRootProof`). `ProofByFieldIndex` is introduced to 1) make logic common and 2) generalize the proof generation in the level of the fields in `BeaconState`.

// ProofByFieldIndex constructs proofs for given field index with lock acquisition.
func (b *BeaconState) ProofByFieldIndex(ctx context.Context, f types.FieldIndex) ([][]byte, error) {
	b.lock.Lock()
	defer b.lock.Unlock()

	return b.proofByFieldIndex(ctx, f)
}

// proofByFieldIndex constructs proofs for given field index.
// Important: it is assumed that beacon state mutex is locked when calling this method.
func (b *BeaconState) proofByFieldIndex(ctx context.Context, f types.FieldIndex) ([][]byte, error) {
	err := b.validateFieldIndex(f)
	if err != nil {
		return nil, err
	}

	if err := b.initializeMerkleLayers(ctx); err != nil {
		return nil, err
	}
	if err := b.recomputeDirtyFields(ctx); err != nil {
		return nil, err
	}
	return trie.ProofFromMerkleLayers(b.merkleLayers, f.RealPosition()), nil
}

One notable thing is about the **race condition**. In case of `FinalizedRootProof`, we need to access to `epoch` in `Checkpoint` container. So the critical section protected by the mutex should also cover this access. There's a comment for `proofByFieldIndex`: _it is assumed that beacon state mutex is locked when calling this method_.

## More fine-grained proof generation

Although `ProofByFieldIndex` is introduced, this cannot cover all proof generation. For example, what if we want to prove the 42nd validator in the validator registry? Or `FinalizedRootProof` is also a great example to explain this issue. More generally speaking, we should find a way to prove for an item with generalized index more than `128`. `BeaconState` now has 37 fields, so the first field (which is `genesis_time`) has `64` as the generalized index.

After thinking an hour, I'd like to suggest to divide the proof generation into two subproblems.

1. Proof generation using `ProofByFieldIndex`: This step will cover the field that can **directly** access from the `BeaconState`. For example, in case of `FinalizedRootProof`, this will cover `finalized_checkpoint`.
- This logic relies on `merkleLayers` that `BeaconState` holds during its lifetime. It is quite well-optimized by only computing dirty fields, so we can enjoy this optimization.
2. Proof generation of more deeper item: In this case, we need to reconstruct a merkle tree to generate the proof. I think reconstruction is okay in terms of performance as it can be further optimized by caching if we really need a proof for specific item often.

Here's the pseudocode for this strategy. Some functions like `calculateGeneralizedIndex` should be implemented.

func (b *BeaconState) ProofByPath(ctx context.Context, path []types.PathElement) ([][]byte, error) {
	gIndex, err := calculateGeneralizedIndex(path)
	if err != nil {
		return nil, err
	}
	return ProofByGeneralizedIndex(ctx, gIndex)
}

func (b *BeaconState) ProofByGeneralizedIndex(ctx context.Context, gIndex types.GeneralizedIndex) ([][]byte, error) {
	b.lock.Lock()
	defer b.lock.Unlock()

	fieldIndex := getFieldIndexFromGeneralizedIndex(gIndex)

	branchProof, err := b.proofByFieldIndex(ctx, fieldIndex)
	if err != nil {
		return nil, err
	}

	tree, err := reconstructMerkleTree(gIndex)
	if err != nil {
		return nil, err
	}

	leafProof, err := tree.MerkleProof(index)
	if err != nil {
		return nil, err
	}

	proof := make([][]byte, 0)
	proof = append(proof, leafProof...)
	proof = append(proof, branchProof...)
	return proof, nil
}

Let's come back to the first question. What if we want to prove the 42nd validator in the validator registry? User can call `ProofByPath` with the path: `["validators", 42]`.

## Other resources

- [`fastssz`](https://github.com/ferranbt/fastssz) (which Prysm also depends on) provides more general way to generate a proof like following:

// Prove returns a list of sibling values and hashes needed
// to compute the root hash for a given general index.
func (n *Node) Prove(index int) (*Proof, error) {
	pathLen := getPathLength(index)
	proof := &Proof{Index: index}
	hashes := make([][]byte, 0, pathLen)

	cur := n
	for i := pathLen - 1; i >= 0; i-- {
		var siblingHash []byte
		if isRight := getPosAtLevel(index, i); isRight {
			siblingHash = hashNode(cur.left)
			cur = cur.right
		} else {
			siblingHash = hashNode(cur.right)
			cur = cur.left
		}
		hashes = append([][]byte{siblingHash}, hashes...)
		if cur == nil {
			return nil, errors.New("Node not found in tree")
		}
	}

	proof.Hashes = hashes
	if cur.value == nil {
		// This is an intermediate node without a value; add the hash to it so that we're providing a suitable leaf value.
		cur.value = hashNode(cur)
	}
	proof.Leaf = cur.value

	return proof, nil
}