provable.gno

  1// Package provable is an honest demonstration of what gno.land can and cannot
  2// prove about itself.
  3//
  4// It keeps a small append-only log in a Merkle mountain range and hands out
  5// inclusion proofs against the log's root. That part works, and it is the
  6// useful half: a realm can commit to a set and let anyone verify membership
  7// cheaply, with one native call.
  8//
  9// The other half is the point of the realm. A proof here says "this entry is
 10// consistent with the root this realm published". It cannot say "this root is
 11// the chain's own", because:
 12//
 13//  1. gno.land mounts two stores (gno.land/pkg/gnoland/app.go). The IAVL one
 14//     is merkleized and holds package source and account balances. The other
 15//     is a plain dbadapter whose Commit is documented as
 16//     "Always returns a zero commitID, as dbadapter store doesn't merkleize",
 17//     and THAT is where every realm's objects live. So no realm's state,
 18//     including this log, contributes anything to the app hash. There is no
 19//     state proof to produce.
 20//  2. chain/runtime exposes ChainID, ChainDomain, ChainHeight and
 21//     GetSessionInfo, and nothing else. No app hash, no block hash, no header.
 22//     So even given a Tendermint proof, a realm has no trusted root to check
 23//     it against.
 24//
 25// The one crack in the wall: an ESCAPED object, one referenced across realm
 26// boundaries, does get its hash written into the IAVL store
 27// (gnovm/pkg/gnolang/store.go). Cross-realm objects are therefore partially
 28// provable already. Nothing else is.
 29//
 30// Demo of gno.land/p/moul/x/merkle/v0 and gno.land/p/moul/x/mmr/v0.
 31package provable
 32
 33import (
 34	"strconv"
 35	"strings"
 36
 37	"gno.land/p/moul/x/merkle/v0"
 38	"gno.land/p/moul/x/mmr/v0"
 39)
 40
 41const (
 42	// MaxEntries bounds the log. Unbounded append from an untrusted caller is
 43	// a storage-growth hazard even when the caller pays the deposit, and an
 44	// unbounded Render is a permanently unreadable page: the chain caps a
 45	// query at maxGasQuery, and a reader cannot raise it.
 46	MaxEntries = 512
 47
 48	// MaxEntryLen bounds one entry.
 49	MaxEntryLen = 256
 50
 51	// renderEntries is how many of the most recent entries Render lists, so
 52	// the page stays a fixed size no matter how full the log is.
 53	renderEntries = 10
 54)
 55
 56var (
 57	log     = mmr.New()
 58	entries []string
 59)
 60
 61func init() { seed() }
 62
 63// Append adds an entry to the log and returns its index. The root moves, so
 64// every previously issued proof stops verifying against the new root: that is
 65// the nature of an append-only commitment, not a bug.
 66func Append(cur realm, entry string) int { return appendEntry(entry) }
 67
 68func appendEntry(entry string) int {
 69	entry = strings.TrimSpace(entry)
 70	if entry == "" {
 71		panic("provable: empty entry")
 72	}
 73	if len(entry) > MaxEntryLen {
 74		panic("provable: entry longer than " + strconv.Itoa(MaxEntryLen) + " bytes")
 75	}
 76	if len(entries) >= MaxEntries {
 77		panic("provable: log is full at " + strconv.Itoa(MaxEntries) + " entries")
 78	}
 79	entries = append(entries, entry)
 80	return log.Append([]byte(entry))
 81}
 82
 83// Size returns the number of entries.
 84func Size() int { return log.Size() }
 85
 86// Root returns the current log root, hex-encoded. It is also the Tendermint
 87// simple-tree root over the same entries, so any Tendermint verifier accepts
 88// it.
 89func Root() string { return log.RootHex() }
 90
 91// Entry returns the entry at index.
 92func Entry(index int) string {
 93	mustRange(index)
 94	return entries[index]
 95}
 96
 97// ProofOf returns the inclusion proof for index, as the three comma-separated
 98// hex lists Verify expects.
 99func ProofOf(index int) (path, before, after string) {
100	mustRange(index)
101	p, err := log.Proof(index)
102	if err != nil {
103		panic("provable: " + err.Error())
104	}
105	return p.Hex()
106}
107
108// Verify checks a proof against a root the caller supplies, which is the
109// honest signature: the realm is a verifier, not an oracle. Pass Root() to
110// check against the live log.
111func Verify(root string, index, total int, entry, path, before, after string) bool {
112	rb, err := hexHash(root)
113	if err != nil {
114		return false
115	}
116	p, err := mmr.ParseProof(index, total, path, before, after)
117	if err != nil {
118		return false
119	}
120	return mmr.Verify(rb, []byte(entry), p)
121}
122
123// VerifyFixed checks a Tendermint simple-tree proof, the fixed-leaf-set
124// encoding, against a root the caller supplies. Same tree as the log, a
125// different proof shape: siblings are one flat list, leaf first.
126//
127// Both encodings verify against the same root, because the Tendermint tree and
128// a right-bagged mountain range are the same structure.
129func VerifyFixed(root string, index, total int, leaf, siblings string) bool {
130	rb, err := hexHash(root)
131	if err != nil {
132		return false
133	}
134	p, err := merkle.ParseProof(index, total, siblings)
135	if err != nil {
136		return false
137	}
138	return p.Verify(rb, []byte(leaf))
139}
140
141func mustRange(index int) {
142	if index < 0 || index >= len(entries) {
143		panic("provable: index out of range")
144	}
145}
146
147func hexHash(s string) ([]byte, error) {
148	p, err := merkle.ParseProof(0, 1, strings.TrimSpace(s))
149	if err != nil {
150		return nil, err
151	}
152	if len(p.Siblings) != 1 {
153		return nil, merkle.ErrBadHashSize
154	}
155	return p.Siblings[0], nil
156}
157
158// seed returns the realm to its deployed state: an empty log plus the three
159// demo entries, so a fresh deployment renders something and so the example
160// tests have a fixed starting point.
161//
162// Realm globals persist across a whole test binary and examples run after
163// every Test, so a pinned Render must call this first.
164func seed() {
165	log = mmr.New()
166	entries = nil
167	appendEntry("genesis of this log")
168	appendEntry("a second commitment")
169	appendEntry("a third commitment")
170}