merkle.gno

  1// Package merkle verifies sorted-pair SHA-256 Merkle proofs with domain-separated leaves.
  2package merkle
  3
  4import (
  5	"bytes"
  6	"crypto/sha256"
  7	"encoding/hex"
  8	"errors"
  9	"strings"
 10)
 11
 12const MaxDepth = 32
 13
 14type Hash = [32]byte
 15
 16var ErrHash = errors.New("launchpad/merkle: hash must be 64 hex characters")
 17
 18func Leaf(data []byte) Hash {
 19	buf := make([]byte, 0, len(data)+1)
 20	buf = append(buf, 0x00)
 21	buf = append(buf, data...)
 22	return sha256.Sum256(buf)
 23}
 24
 25func node(a, b Hash) Hash {
 26	if bytes.Compare(a[:], b[:]) > 0 {
 27		a, b = b, a
 28	}
 29	buf := make([]byte, 0, 65)
 30	buf = append(buf, 0x01)
 31	buf = append(buf, a[:]...)
 32	buf = append(buf, b[:]...)
 33	return sha256.Sum256(buf)
 34}
 35
 36func Root(leaves []Hash) Hash {
 37	if len(leaves) == 0 {
 38		panic("launchpad/merkle: no leaves")
 39	}
 40	level := append([]Hash{}, leaves...)
 41	for len(level) > 1 {
 42		next := make([]Hash, 0, (len(level)+1)/2)
 43		for i := 0; i < len(level); i += 2 {
 44			if i+1 == len(level) {
 45				next = append(next, level[i])
 46			} else {
 47				next = append(next, node(level[i], level[i+1]))
 48			}
 49		}
 50		level = next
 51	}
 52	return level[0]
 53}
 54
 55func Proof(leaves []Hash, index int) []Hash {
 56	if index < 0 || index >= len(leaves) {
 57		panic("launchpad/merkle: index out of range")
 58	}
 59	level := append([]Hash{}, leaves...)
 60	proof := []Hash{}
 61	for len(level) > 1 {
 62		next := make([]Hash, 0, (len(level)+1)/2)
 63		for i := 0; i < len(level); i += 2 {
 64			if i+1 == len(level) {
 65				next = append(next, level[i])
 66				continue
 67			}
 68			if i == index {
 69				proof = append(proof, level[i+1])
 70			} else if i+1 == index {
 71				proof = append(proof, level[i])
 72			}
 73			next = append(next, node(level[i], level[i+1]))
 74		}
 75		index /= 2
 76		level = next
 77	}
 78	return proof
 79}
 80
 81func Verify(root, leaf Hash, proof []Hash) bool {
 82	if len(proof) > MaxDepth {
 83		return false
 84	}
 85	h := leaf
 86	for _, p := range proof {
 87		h = node(h, p)
 88	}
 89	return h == root
 90}
 91
 92func ParseHash(s string) (Hash, error) {
 93	var h Hash
 94	if len(s) != 64 {
 95		return h, ErrHash
 96	}
 97	b, err := hex.DecodeString(s)
 98	if err != nil {
 99		return h, ErrHash
100	}
101	copy(h[:], b)
102	return h, nil
103}
104
105func ParseProof(s string) ([]Hash, error) {
106	if s == "" {
107		return []Hash{}, nil
108	}
109	parts := strings.Split(s, ",")
110	if len(parts) > MaxDepth {
111		return nil, errors.New("launchpad/merkle: proof too long")
112	}
113	out := make([]Hash, len(parts))
114	for i, p := range parts {
115		h, err := ParseHash(p)
116		if err != nil {
117			return nil, err
118		}
119		out[i] = h
120	}
121	return out, nil
122}
123
124func FormatHash(h Hash) string { return hex.EncodeToString(h[:]) }