gno.land/p/samcrew/launchpad/merkle/v1⧉

1// Package merkle verifies sorted-pair SHA-256 Merkle proofs with domain-separated leaves.2package merkle34import (5	"bytes"6	"crypto/sha256"7	"encoding/hex"8	"errors"9	"strings"10)1112const MaxDepth = 321314type Hash = [32]byte1516var ErrHash = errors.New("launchpad/merkle: hash must be 64 hex characters")1718func 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}2425func node(a, b Hash) Hash {26	if bytes.Compare(a[:], b[:]) > 0 {27		a, b = b, a28	}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}3536func 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 = next51	}52	return level[0]53}5455func 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				continue67			}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 /= 276		level = next77	}78	return proof79}8081func Verify(root, leaf Hash, proof []Hash) bool {82	if len(proof) > MaxDepth {83		return false84	}85	h := leaf86	for _, p := range proof {87		h = node(h, p)88	}89	return h == root90}9192func ParseHash(s string) (Hash, error) {93	var h Hash94	if len(s) != 64 {95		return h, ErrHash96	}97	b, err := hex.DecodeString(s)98	if err != nil {99		return h, ErrHash100	}101	copy(h[:], b)102	return h, nil103}104105func ParseProof(s string) ([]Hash, error) {106	if s == "" {107		return []Hash{}, nil108	}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, err118		}119		out[i] = h120	}121	return out, nil122}123124func FormatHash(h Hash) string { return hex.EncodeToString(h[:]) }125