func (t *Tree) RootAndProof() ([]byte, [][]byte) {
	ephemeralProof := t.proof
	var ephemeralNode node
	l := t.baseLayer
	for height := uint(0); height < t.minHeight || l != nil; height++ {
		reachedMinHeight := height >= t.minHeight
		onLastLayer := l != nil && l.next == nil
		parkingIsBalancedTreeRoot := reachedMinHeight && onLastLayer && ephemeralNode.IsEmpty()
		if parkingIsBalancedTreeRoot {
			return l.parking.value, ephemeralProof
		}
		var parking node
		if l != nil {
			parking = l.parking
		}
		parent, lChild, rChild := t.calcEphemeralParent(parking, ephemeralNode)
		if parent.OnProvenPath {
			if !lChild.OnProvenPath {
				ephemeralProof = append(ephemeralProof, lChild.value)
			}
			if !rChild.OnProvenPath {
				ephemeralProof = append(ephemeralProof, rChild.value)
			}
		}
		ephemeralNode = parent
		if l != nil {
			l = l.next
		}
	}
	return ephemeralNode.value, ephemeralProof
}
RootAndProof returns the root of the tree and a partial tree proving the membership of leaves that were passed in
leavesToProve when the tree was initialized. For a single proved leaf this is a standard merkle proof (one sibling
per layer of the tree from the leaves to the root, excluding the proved leaf and root).
If the tree is unbalanced (num. of leaves is not a power of 2) it will perform padding on-the-fly.
package merkle
import (
	"errors"
	"github.com/spacemeshos/merkle-tree/shared"
	"github.com/spacemeshos/sha256-simd"
)
const NodeSize = shared.NodeSize
type (
	HashFunc        = shared.HashFunc
	LayerWriter     = shared.LayerWriter
	LayerReader     = shared.LayerReader
	LayerReadWriter = shared.LayerReadWriter
	CacheWriter     = shared.CacheWriter
	CacheReader     = shared.CacheReader
)
var RootHeightFromWidth = shared.RootHeightFromWidth
var EmptyNode node
var PaddingValue = node{
	value:        make([]byte, NodeSize),  
	OnProvenPath: false,
}
type node struct {
	value        []byte
	OnProvenPath bool  
}
func (n node) IsEmpty() bool {
	return n.value == nil
}
type layer struct {
	height  uint
	parking node  
	next    *layer
	cache   LayerWriter
}
func (l *layer) ensureNextLayerExists(cacheWriter shared.CacheWriter) error {
	if l.next == nil {
		writer, err := cacheWriter.GetLayerWriter(l.height + 1)
		if err != nil {
			return err
		}
		l.next = newLayer(l.height+1, writer)
	}
	return nil
}
func newLayer(height uint, cache LayerWriter) *layer {
	return &layer{height: height, cache: cache}
}
type sparseBoolStack struct {
	sortedTrueIndices []uint64
	currentIndex      uint64
}
func NewSparseBoolStack(trueIndices Set) *sparseBoolStack {
	sorted := trueIndices.AsSortedSlice()
	return &sparseBoolStack{sortedTrueIndices: sorted}
}
func (s *sparseBoolStack) Pop() bool {
	if len(s.sortedTrueIndices) == 0 {
		return false
	}
	ret := s.currentIndex == s.sortedTrueIndices[0]
	if ret {
		s.sortedTrueIndices = s.sortedTrueIndices[1:]
	}
	s.currentIndex++
	return ret
}
type Tree struct {
	baseLayer     *layer  
	hash          HashFunc
	proof         [][]byte
	leavesToProve *sparseBoolStack
	cacheWriter   CacheWriter
	minHeight     uint
}
func (t *Tree) AddLeaf(value []byte) error {
	n := node{
		value:        value,
		OnProvenPath: t.leavesToProve.Pop(),
	}
	l := t.baseLayer
	var parent, lChild, rChild node
	var lastCachingError error
	for {
		if l.cache != nil {
			_, err := l.cache.Append(n.value)
			if err != nil {
				lastCachingError = errors.New("error while caching: " + err.Error())
			}
		}
		if l.parking.IsEmpty() {
			l.parking = n
			break
		} else {
			lChild, rChild = l.parking, n
			parent = t.calcParent(lChild, rChild)
			if parent.OnProvenPath {
				if !lChild.OnProvenPath {
					t.proof = append(t.proof, lChild.value)
				}
				if !rChild.OnProvenPath {
					t.proof = append(t.proof, rChild.value)
				}
			}
			l.parking.value = nil
			n = parent
			err := l.ensureNextLayerExists(t.cacheWriter)
			if err != nil {
				return err
			}
			l = l.next
		}
	}
	return lastCachingError
}
func (t *Tree) Root() []byte {
	root, _ := t.RootAndProof()
	return root
}
func (t *Tree) Proof() [][]byte {
	_, proof := t.RootAndProof()
	return proof
}