verify.gno

  1package mmr
  2
  3import (
  4	"encoding/hex"
  5	"strings"
  6
  7	"gno.land/p/moul/x/merkle/v0"
  8)
  9
 10// peakHeights returns the mountain heights of a log of total leaves, left to
 11// 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 []int
 15	for h := 62; h >= 0; h-- {
 16		if total&(1<<uint(h)) != 0 {
 17			out = append(out, h)
 18		}
 19	}
 20	return out
 21}
 22
 23// locate returns which mountain holds the leaf at index, and the leaf's index
 24// within that mountain. It returns -1 when index is out of range.
 25func locate(total, index int) (int, int) {
 26	offset := 0
 27	for j, h := range peakHeights(total) {
 28		size := 1 << uint(h)
 29		if index < offset+size {
 30			return j, index - offset
 31		}
 32		offset += size
 33	}
 34	return -1, 0
 35}
 36
 37// Verify reports whether leaf really sits at p.Index of a log that held
 38// 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 path
 42// length and both peak-list lengths are all recomputed. A proof that does not
 43// 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 proof
 46// 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 false
 50	}
 51	heights := peakHeights(p.Total)
 52	if len(heights) > MaxPeaks {
 53		return false
 54	}
 55	j, local := locate(p.Total, p.Index)
 56	if j < 0 {
 57		return false
 58	}
 59	if len(p.Path) != heights[j] || len(p.Before) != j || len(p.After) != len(heights)-1-j {
 60		return false
 61	}
 62	if !allHashes(p.Path) || !allHashes(p.Before) || !allHashes(p.After) {
 63		return false
 64	}
 65
 66	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	}
 74
 75	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}
 81
 82func allHashes(hs [][]byte) bool {
 83	for _, h := range hs {
 84		if len(h) != HashSize {
 85			return false
 86		}
 87	}
 88	return true
 89}
 90
 91func equal(a, b []byte) bool {
 92	if len(a) != len(b) || len(a) == 0 {
 93		return false
 94	}
 95	for i := range a {
 96		if a[i] != b[i] {
 97			return false
 98		}
 99	}
100	return true
101}
102
103// Hex renders the three hash lists as comma-separated hex, in the order
104// 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}
108
109func 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}
116
117// ParseProof rebuilds a Proof from realm-call arguments. Each of path, before
118// 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{}, err
123	}
124	bh, err := splitHex(before)
125	if err != nil {
126		return Proof{}, err
127	}
128	ah, err := splitHex(after)
129	if err != nil {
130		return Proof{}, err
131	}
132	if len(bh)+len(ah)+1 > MaxPeaks {
133		return Proof{}, ErrTooManyPeaks
134	}
135	return Proof{Index: index, Total: total, Path: ph, Before: bh, After: ah}, nil
136}
137
138func splitHex(s string) ([][]byte, error) {
139	s = strings.TrimSpace(s)
140	if s == "" {
141		return nil, nil
142	}
143	var out [][]byte
144	for _, raw := range strings.Split(s, ",") {
145		raw = strings.TrimSpace(raw)
146		if raw == "" {
147			continue
148		}
149		b, err := hex.DecodeString(raw)
150		if err != nil {
151			return nil, ErrBadHex
152		}
153		if len(b) != HashSize {
154			return nil, ErrBadSize
155		}
156		out = append(out, b)
157	}
158	return out, nil
159}