func subtreeDefinition(c CacheReader, p Position) (root, firstLeaf Position, width uint64, err error) {
	width, err = c.GetLayerReader(p.Height).Width()
	if err != nil {
		return Position{}, Position{}, 0, err
	}
	maxRootHeight := RootHeightFromWidth(width)
	for root = p.parent(); root.Height < maxRootHeight; root = root.parent() {
		if layer := c.GetLayerReader(root.Height); layer != nil {
			break
		}
	}
	subtreeHeight := root.Height - p.Height
	firstLeaf = Position{
		Index:  root.Index << subtreeHeight,
		Height: p.Height,
	}
	return root, firstLeaf, 1 << subtreeHeight, err
}
subtreeDefinition returns the definition (firstLeaf and root positions, width) for the minimal subtree whose
base layer includes p and where the root is on a cached layer. If no cached layer exists above the base layer, the
subtree will reach the root of the original tree.
package merkle
import (
	"errors"
	"fmt"
	"io"
)
var ErrMissingValueAtBaseLayer = errors.New("reader for base layer must be included")
func GenerateProof(
	provenLeafIndices map[uint64]bool,
	treeCache CacheReader,
) (sortedProvenLeafIndices []uint64, provenLeaves, proofNodes [][]byte, err error) {
	provenLeafIndexIt := NewPositionsIterator(provenLeafIndices)
	skipPositions := &positionsStack{}
	width, err := treeCache.GetLayerReader(0).Width()
	if err != nil {
		return nil, nil, nil, err
	}
	rootHeight := RootHeightFromWidth(width)
	for {  
		nextProvenLeafPos, found := provenLeafIndexIt.peek()
		if !found {
			break
		}
		currentPos, subtreeStart, width, err := subtreeDefinition(treeCache, nextProvenLeafPos)
		if err != nil {
			return nil, nil, nil, err
		}
		leavesToProve := provenLeafIndexIt.batchPop(subtreeStart.Index + width)
		additionalProof, additionalLeaves, err := calcSubtreeProof(treeCache, leavesToProve, subtreeStart, width)
		if err != nil {
			return nil, nil, nil, err
		}
		proofNodes = append(proofNodes, additionalProof...)
		provenLeaves = append(provenLeaves, additionalLeaves...)
		for ; currentPos.Height < rootHeight; currentPos = currentPos.parent() {  
			found := skipPositions.PopIfEqual(currentPos)
			if found {
				continue
			}
			if p, found := provenLeafIndexIt.peek(); found && currentPos.sibling().isAncestorOf(p) {
				skipPositions.Push(currentPos.sibling())
				break
			}
			currentVal, err := GetNode(treeCache, currentPos.sibling())
			if err != nil {
				return nil, nil, nil, err
			}
			proofNodes = append(proofNodes, currentVal)
		}
	}
	return Set(provenLeafIndices).AsSortedSlice(), provenLeaves, proofNodes, nil
}
func calcSubtreeProof(c CacheReader, leavesToProve Set, subtreeStart Position, width uint64) (
	additionalProof, additionalLeaves [][]byte, err error) {
	relativeLeavesToProve := make(Set)
	for leafIndex, prove := range leavesToProve {
		relativeLeavesToProve[leafIndex-subtreeStart.Index] = prove
	}
	reader := c.GetLayerReader(0)
	err = reader.Seek(subtreeStart.Index)
	if err != nil {
		return nil, nil, errors.New("while preparing to traverse subtree: " + err.Error())
	}
	_, additionalProof, additionalLeaves, err = traverseSubtree(reader, width, c.GetHashFunc(), relativeLeavesToProve, nil)
	if err != nil {
		return nil, nil, errors.New("while traversing subtree: " + err.Error())
	}
	return additionalProof, additionalLeaves, err
}
func traverseSubtree(leafReader LayerReader, width uint64, hash HashFunc, leavesToProve Set,
	externalPadding []byte) (root []byte, proof, provenLeaves [][]byte, err error) {
	shouldUseExternalPadding := externalPadding != nil
	t, err := NewTreeBuilder().
		WithHashFunc(hash).
		WithLeavesToProve(leavesToProve).
		WithMinHeight(RootHeightFromWidth(width)).  
		Build()
	if err != nil {
		return nil, nil, nil, errors.New("while building a tree: " + err.Error())
	}
	for i := uint64(0); i < width; i++ {
		leaf, err := leafReader.ReadNext()
		if err == io.EOF {
			if !shouldUseExternalPadding {
				break
			}
			leaf = externalPadding
			shouldUseExternalPadding = false
		} else if err != nil {
			return nil, nil, nil, errors.New("while reading a leaf: " + err.Error())
		}
		err = t.AddLeaf(leaf)
		if err != nil {
			return nil, nil, nil, errors.New("while adding a leaf: " + err.Error())
		}
		if leavesToProve[i] {
			provenLeaves = append(provenLeaves, leaf)
		}
	}
	root, proof = t.RootAndProof()
	return root, proof, provenLeaves, nil
}
func GetNode(c CacheReader, nodePos Position) ([]byte, error) {
	reader := c.GetLayerReader(nodePos.Height)
	if reader == nil {
		return calcNode(c, nodePos)
	}
	err := reader.Seek(nodePos.Index)
	if err == io.EOF {
		return calcNode(c, nodePos)
	}
	if err != nil {
		return nil, errors.New("while seeking to Position " + nodePos.String() + " in cache: " + err.Error())
	}
	currentVal, err := reader.ReadNext()
	if err != nil {
		return nil, errors.New("while reading from cache: " + err.Error())
	}
	return currentVal, nil
}
func calcNode(c CacheReader, nodePos Position) ([]byte, error) {
	var subtreeStart Position
	var reader LayerReader
	if nodePos.Height == 0 {
		return nil, ErrMissingValueAtBaseLayer
	}
	for subtreeStart = nodePos; reader == nil; {
		subtreeStart = subtreeStart.leftChild()
		reader = c.GetLayerReader(subtreeStart.Height)
	}
	err := reader.Seek(subtreeStart.Index)
	if err == io.EOF {
		return PaddingValue.value, nil
	}
	if err != nil {
		return nil, errors.New("while seeking to Position " + subtreeStart.String() + " in cache: " + err.Error())
	}
	var paddingValue []byte
	width := uint64(1) << (nodePos.Height - subtreeStart.Height)
	readerWidth, err := reader.Width()
	if err != nil {
		return nil, fmt.Errorf("while getting reader width: %v", err)
	}
	if readerWidth < subtreeStart.Index+width {
		paddingPos := Position{
			Index:  readerWidth,
			Height: subtreeStart.Height,
		}
		paddingValue, err = calcNode(c, paddingPos)
		if err == ErrMissingValueAtBaseLayer {
			paddingValue = PaddingValue.value
		} else if err != nil {
			return nil, errors.New("while calculating ephemeral node at Position " + paddingPos.String() + ": " + err.Error())
		}
	}
	currentVal, _, _, err := traverseSubtree(reader, width, c.GetHashFunc(), nil, paddingValue)
	if err != nil {
		return nil, errors.New("while traversing subtree for root: " + err.Error())
	}
	return currentVal, nil
}