gno.land/p/moul/x/mmr/v0⧉

1package mmr23import (4	"encoding/hex"5	"strings"67	"gno.land/p/moul/x/merkle/v0"8)910// peakHeights returns the mountain heights of a log of total leaves, left to11// right. They are the set bits of total, high to low: 11 leaves is 8 + 2 + 1,12// so heights 3, 1, 0.13func peakHeights(total int) []int {14	var out []int15	for h := 62; h >= 0; h-- {16		if total&(1<<uint(h)) != 0 {17			out = append(out, h)18		}19	}20	return out21}2223// locate returns which mountain holds the leaf at index, and the leaf's index24// within that mountain. It returns -1 when index is out of range.25func locate(total, index int) (int, int) {26	offset := 027	for j, h := range peakHeights(total) {28		size := 1 << uint(h)29		if index < offset+size {30			return j, index - offset31		}32		offset += size33	}34	return -1, 035}3637// Verify reports whether leaf really sits at p.Index of a log that held38// p.Total leaves and whose root is root.39//40// Every dimension of the proof is checked against p.Total rather than trusted:41// the peak count, which mountain holds the leaf, the local index, the path42// length and both peak-list lengths are all recomputed. A proof that does not43// have exactly the shape p.Total implies is rejected before any hashing.44//45// Failures are false, never a panic, so a realm chooses whether a bad proof46// aborts or branches.47func Verify(root, leaf []byte, p Proof) bool {48	if len(root) != HashSize || p.Total <= 0 || p.Index < 0 || p.Index >= p.Total {49		return false50	}51	heights := peakHeights(p.Total)52	if len(heights) > MaxPeaks {53		return false54	}55	j, local := locate(p.Total, p.Index)56	if j < 0 {57		return false58	}59	if len(p.Path) != heights[j] || len(p.Before) != j || len(p.After) != len(heights)-1-j {60		return false61	}62	if !allHashes(p.Path) || !allHashes(p.Before) || !allHashes(p.After) {63		return false64	}6566	node := merkle.LeafHash(leaf)67	for d, sib := range p.Path {68		if (local>>uint(d))&1 == 1 {69			node = merkle.InnerHash(sib, node)70		} else {71			node = merkle.InnerHash(node, sib)72		}73	}7475	peaks := make([][]byte, 0, len(heights))76	peaks = append(peaks, p.Before...)77	peaks = append(peaks, node)78	peaks = append(peaks, p.After...)79	return equal(bag(peaks), root)80}8182func allHashes(hs [][]byte) bool {83	for _, h := range hs {84		if len(h) != HashSize {85			return false86		}87	}88	return true89}9091func equal(a, b []byte) bool {92	if len(a) != len(b) || len(a) == 0 {93		return false94	}95	for i := range a {96		if a[i] != b[i] {97			return false98		}99	}100	return true101}102103// Hex renders the three hash lists as comma-separated hex, in the order104// path|before|after, which is what a realm call takes as arguments.105func (p Proof) Hex() (path, before, after string) {106	return joinHex(p.Path), joinHex(p.Before), joinHex(p.After)107}108109func joinHex(hs [][]byte) string {110	parts := make([]string, len(hs))111	for i, h := range hs {112		parts[i] = hex.EncodeToString(h)113	}114	return strings.Join(parts, ",")115}116117// ParseProof rebuilds a Proof from realm-call arguments. Each of path, before118// and after is a comma-separated hex list, possibly empty.119func ParseProof(index, total int, path, before, after string) (Proof, error) {120	ph, err := splitHex(path)121	if err != nil {122		return Proof{}, err123	}124	bh, err := splitHex(before)125	if err != nil {126		return Proof{}, err127	}128	ah, err := splitHex(after)129	if err != nil {130		return Proof{}, err131	}132	if len(bh)+len(ah)+1 > MaxPeaks {133		return Proof{}, ErrTooManyPeaks134	}135	return Proof{Index: index, Total: total, Path: ph, Before: bh, After: ah}, nil136}137138func splitHex(s string) ([][]byte, error) {139	s = strings.TrimSpace(s)140	if s == "" {141		return nil, nil142	}143	var out [][]byte144	for _, raw := range strings.Split(s, ",") {145		raw = strings.TrimSpace(raw)146		if raw == "" {147			continue148		}149		b, err := hex.DecodeString(raw)150		if err != nil {151			return nil, ErrBadHex152		}153		if len(b) != HashSize {154			return nil, ErrBadSize155		}156		out = append(out, b)157	}158	return out, nil159}160