provable.gno
5.52 Kb · 170 lines
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/nym-moultest123/x/merkle/v0 and gno.land/p/nym-moultest123/x/mmr/v0.
31package provable
32
33import (
34 "strconv"
35 "strings"
36
37 "gno.land/p/nym-moultest123/x/merkle/v0"
38 "gno.land/p/nym-moultest123/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}
