Playground
gnomod.toml
module = "gno.land/r/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/provable/v0" gno = "0.9" private = true [addpkg] creator = "g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv" height = 914348 max_deposit = "10000000ugnot"
provable.gno
// Package provable is an honest demonstration of what gno.land can and cannot
// prove about itself.
//
// It keeps a small append-only log in a Merkle mountain range and hands out
// inclusion proofs against the log's root. That part works, and it is the
// useful half: a realm can commit to a set and let anyone verify membership
// cheaply, with one native call.
//
// The other half is the point of the realm. A proof here says "this entry is
// consistent with the root this realm published". It cannot say "this root is
// the chain's own", because:
//
// 1. gno.land mounts two stores (gno.land/pkg/gnoland/app.go). The IAVL one
// is merkleized and holds package source and account balances. The other
// is a plain dbadapter whose Commit is documented as
// "Always returns a zero commitID, as dbadapter store doesn't merkleize",
// and THAT is where every realm's objects live. So no realm's state,
// including this log, contributes anything to the app hash. There is no
// state proof to produce.
// 2. chain/runtime exposes ChainID, ChainDomain, ChainHeight and
// GetSessionInfo, and nothing else. No app hash, no block hash, no header.
// So even given a Tendermint proof, a realm has no trusted root to check
// it against.
//
// The one crack in the wall: an ESCAPED object, one referenced across realm
// boundaries, does get its hash written into the IAVL store
// (gnovm/pkg/gnolang/store.go). Cross-realm objects are therefore partially
// provable already. Nothing else is.
//
// Demo of gno.land/p/moul/x/merkle/v0 and gno.land/p/moul/x/mmr/v0.
package provable
import (
"strconv"
"strings"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/merkle/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/mmr/v0"
)
const (
// MaxEntries bounds the log. Unbounded append from an untrusted caller is
// a storage-growth hazard even when the caller pays the deposit, and an
// unbounded Render is a permanently unreadable page: the chain caps a
// query at maxGasQuery, and a reader cannot raise it.
MaxEntries = 512
// MaxEntryLen bounds one entry.
MaxEntryLen = 256
// renderEntries is how many of the most recent entries Render lists, so
// the page stays a fixed size no matter how full the log is.
renderEntries = 10
)
var (
log = mmr.New()
entries []string
)
func init() { seed() }
// Append adds an entry to the log and returns its index. The root moves, so
// every previously issued proof stops verifying against the new root: that is
// the nature of an append-only commitment, not a bug.
func Append(cur realm, entry string) int { return appendEntry(entry) }
func appendEntry(entry string) int {
entry = strings.TrimSpace(entry)
if entry == "" {
panic("provable: empty entry")
}
if len(entry) > MaxEntryLen {
panic("provable: entry longer than " + strconv.Itoa(MaxEntryLen) + " bytes")
}
if len(entries) >= MaxEntries {
panic("provable: log is full at " + strconv.Itoa(MaxEntries) + " entries")
}
entries = append(entries, entry)
return log.Append([]byte(entry))
}
// Size returns the number of entries.
func Size() int { return log.Size() }
// Root returns the current log root, hex-encoded. It is also the Tendermint
// simple-tree root over the same entries, so any Tendermint verifier accepts
// it.
func Root() string { return log.RootHex() }
// Entry returns the entry at index.
func Entry(index int) string {
mustRange(index)
return entries[index]
}
// ProofOf returns the inclusion proof for index, as the three comma-separated
// hex lists Verify expects.
func ProofOf(index int) (path, before, after string) {
mustRange(index)
p, err := log.Proof(index)
if err != nil {
panic("provable: " + err.Error())
}
return p.Hex()
}
// Verify checks a proof against a root the caller supplies, which is the
// honest signature: the realm is a verifier, not an oracle. Pass Root() to
// check against the live log.
func Verify(root string, index, total int, entry, path, before, after string) bool {
rb, err := hexHash(root)
if err != nil {
return false
}
p, err := mmr.ParseProof(index, total, path, before, after)
if err != nil {
return false
}
return mmr.Verify(rb, []byte(entry), p)
}
// VerifyFixed checks a Tendermint simple-tree proof, the fixed-leaf-set
// encoding, against a root the caller supplies. Same tree as the log, a
// different proof shape: siblings are one flat list, leaf first.
//
// Both encodings verify against the same root, because the Tendermint tree and
// a right-bagged mountain range are the same structure.
func VerifyFixed(root string, index, total int, leaf, siblings string) bool {
rb, err := hexHash(root)
if err != nil {
return false
}
p, err := merkle.ParseProof(index, total, siblings)
if err != nil {
return false
}
return p.Verify(rb, []byte(leaf))
}
func mustRange(index int) {
if index < 0 || index >= len(entries) {
panic("provable: index out of range")
}
}
func hexHash(s string) ([]byte, error) {
p, err := merkle.ParseProof(0, 1, strings.TrimSpace(s))
if err != nil {
return nil, err
}
if len(p.Siblings) != 1 {
return nil, merkle.ErrBadHashSize
}
return p.Siblings[0], nil
}
// seed returns the realm to its deployed state: an empty log plus the three
// demo entries, so a fresh deployment renders something and so the example
// tests have a fixed starting point.
//
// Realm globals persist across a whole test binary and examples run after
// every Test, so a pinned Render must call this first.
func seed() {
log = mmr.New()
entries = nil
appendEntry("genesis of this log")
appendEntry("a second commitment")
appendEntry("a third commitment")
}
provable_test.gno
package provable
import (
"strconv"
"strings"
"testing"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/merkle/v0"
)
func TestAppendAndVerify(cur realm, t *testing.T) {
seed()
i := Append(cross(cur), "a fourth commitment")
if i != 3 || Size() != 4 {
t.Fatalf("Append returned %d with Size %d, want 3 and 4", i, Size())
}
if Entry(i) != "a fourth commitment" {
t.Errorf("Entry(%d) = %q", i, Entry(i))
}
root := Root()
for j := 0; j < Size(); j++ {
path, before, after := ProofOf(j)
if !Verify(root, j, Size(), Entry(j), path, before, after) {
t.Errorf("entry %d: its own proof does not verify", j)
}
}
}
// Append trims, so the proof must be over the trimmed entry.
func TestAppendTrims(cur realm, t *testing.T) {
seed()
i := Append(cross(cur), " padded ")
if Entry(i) != "padded" {
t.Fatalf("Entry = %q, want %q", Entry(i), "padded")
}
path, before, after := ProofOf(i)
if !Verify(Root(), i, Size(), "padded", path, before, after) {
t.Error("trimmed entry does not verify")
}
if Verify(Root(), i, Size(), " padded ", path, before, after) {
t.Error("the untrimmed string verified, so the leaf is not what is stored")
}
}
func TestVerifyRejects(cur realm, t *testing.T) {
seed()
root := Root()
path, before, after := ProofOf(1)
other := "0000000000000000000000000000000000000000000000000000000000000000"
tests := []struct {
name string
root string
index, total int
entry, path, before, after string
}{
{"wrong entry", root, 1, 3, "not in the log", path, before, after},
{"another real entry", root, 1, 3, Entry(0), path, before, after},
{"wrong index", root, 0, 3, Entry(1), path, before, after},
{"wrong total", root, 1, 4, Entry(1), path, before, after},
{"wrong root", other, 1, 3, Entry(1), path, before, after},
{"root not hex", "zz", 1, 3, Entry(1), path, before, after},
{"root wrong length", "abcd", 1, 3, Entry(1), path, before, after},
{"empty path", root, 1, 3, Entry(1), "", before, after},
{"peaks swapped", root, 1, 3, Entry(1), path, after, before},
{"garbage path", root, 1, 3, Entry(1), "zz", before, after},
}
for _, tc := range tests {
if Verify(tc.root, tc.index, tc.total, tc.entry, tc.path, tc.before, tc.after) {
t.Errorf("%s: accepted, must be rejected", tc.name)
}
}
}
// The log root is also the Tendermint simple-tree root over the same entries,
// so the fixed-leaf-set proof encoding verifies against it too. This is the
// claim the realm makes in Render; it is tested, not asserted.
func TestVerifyFixedAcceptsTendermintProof(cur realm, t *testing.T) {
seed()
Append(cross(cur), "a fourth commitment")
Append(cross(cur), "a fifth commitment")
leaves := make([][]byte, Size())
for i := range leaves {
leaves[i] = []byte(Entry(i))
}
tree := merkle.New(leaves)
if tree.RootHex() != Root() {
t.Fatalf("tree root %s, log root %s", tree.RootHex(), Root())
}
for i := 0; i < Size(); i++ {
p, err := tree.Proof(i)
if err != nil {
t.Fatalf("i=%d: %v", i, err)
}
if !VerifyFixed(Root(), i, Size(), Entry(i), p.Hex()) {
t.Errorf("i=%d: Tendermint proof rejected by the realm", i)
}
if VerifyFixed(Root(), i, Size(), "forged", p.Hex()) {
t.Errorf("i=%d: forged leaf accepted", i)
}
}
}
func TestCaps(t *testing.T) {
seed()
tests := []struct {
name string
entry string
}{
{"empty", ""},
{"whitespace only", " "},
{"too long", strings.Repeat("x", MaxEntryLen+1)},
}
for _, tc := range tests {
if got := panicked(func() { appendEntry(tc.entry) }); got == "" {
t.Errorf("%s: accepted, must panic", tc.name)
}
}
// A note of exactly MaxEntryLen is fine.
if got := panicked(func() { appendEntry(strings.Repeat("x", MaxEntryLen)) }); got != "" {
t.Errorf("entry of exactly MaxEntryLen panicked: %s", got)
}
}
func TestLogIsBounded(t *testing.T) {
seed()
for Size() < MaxEntries {
appendEntry("filler-" + strconv.Itoa(Size()))
}
if got := panicked(func() { appendEntry("one too many") }); got == "" {
t.Error("appending past MaxEntries was accepted")
}
seed()
}
func TestEntryRangeChecked(t *testing.T) {
seed()
for _, i := range []int{-1, 3, 999} {
if got := panicked(func() { Entry(i) }); got == "" {
t.Errorf("Entry(%d) did not panic", i)
}
if got := panicked(func() { ProofOf(i) }); got == "" {
t.Errorf("ProofOf(%d) did not panic", i)
}
}
}
// panicked runs f and returns the panic message, or "" if it returned
// normally. Safe here because these calls are in-package and do not cross a
// realm boundary, where a panic would be an unrecoverable abort instead.
func panicked(f func()) (msg string) {
defer func() {
if r := recover(); r != nil {
if s, ok := r.(string); ok {
msg = s
} else {
msg = "panic"
}
}
}()
f()
return ""
}
render.gno
package provable
import (
"strconv"
"strings"
)
// Render serves the overview at "" and one entry with its proof at
// "entry/<index>".
//
// Output is a fixed size: the entry list is capped at renderEntries, so a full
// log still renders. The chain caps a query at maxGasQuery and a reader cannot
// raise it, so an unbounded Render is a permanently unreadable page.
func Render(path string) string {
path = strings.TrimSpace(path)
if strings.HasPrefix(path, "entry/") {
return renderEntry(strings.TrimPrefix(path, "entry/"))
}
return renderIndex()
}
func renderIndex() string {
var b strings.Builder
b.WriteString("# provable\n\n")
b.WriteString("What gno.land can and cannot prove about itself, demonstrated rather than asserted.\n\n")
b.WriteString("## The log\n\n")
b.WriteString("An append-only Merkle mountain range. Appending costs O(log n) hashes and never rebuilds.\n\n")
b.WriteString("| Field | Value |\n|---|---|\n")
b.WriteString("| Entries | " + strconv.Itoa(log.Size()) + " / " + strconv.Itoa(MaxEntries) + " |\n")
b.WriteString("| Stored hashes | " + strconv.Itoa(log.Nodes()) + " |\n")
b.WriteString("| Peaks | " + strconv.Itoa(len(log.PeakHashes())) + " |\n")
b.WriteString("| Root | `" + rootOrDash() + "` |\n\n")
b.WriteString("This root is also the Tendermint simple-tree root over the same entries, so any\n")
b.WriteString("Tendermint verifier accepts it. `Verify` and `VerifyFixed` check the two proof\n")
b.WriteString("encodings against it.\n\n")
b.WriteString("## What the chain can prove\n\n")
b.WriteString("`gno.land/pkg/gnoland/app.go` mounts exactly two stores. One is IAVL and merkleized,\n")
b.WriteString("the other is a plain dbadapter whose `Commit` is documented as *\"Always returns a zero\n")
b.WriteString("commitID, as dbadapter store doesn't merkleize\"*.\n\n")
b.WriteString("| Data | Store | Provable against the app hash |\n|---|---|---|\n")
b.WriteString("| Package source | iavl | yes |\n")
b.WriteString("| Account balances | iavl | yes |\n")
b.WriteString("| Escaped object hashes (cross-realm) | iavl | yes, the hash only |\n")
b.WriteString("| Realm objects, types, realm metadata | base | **no** |\n")
b.WriteString("| **This log** | base | **no** |\n\n")
b.WriteString("## What that means here\n\n")
b.WriteString("A proof from this realm says *this entry is consistent with the root this realm\n")
b.WriteString("published*. It cannot say *this root is the chain's own*, for two independent reasons:\n\n")
b.WriteString("1. Realm state is not merkleized, so there is no state proof to produce.\n")
b.WriteString("2. `chain/runtime` exposes `ChainID`, `ChainDomain`, `ChainHeight` and `GetSessionInfo`\n")
b.WriteString(" and nothing else. No app hash, no block hash, no header. A realm has no trusted\n")
b.WriteString(" root to check anything against.\n\n")
b.WriteString("Anything built on Merkle proofs in a gno realm is trust-minimised relative to a\n")
b.WriteString("committed root, never trustless. Saying otherwise would be the interesting-sounding\n")
b.WriteString("half of a true story.\n\n")
b.WriteString("## Entries\n\n")
if log.Size() == 0 {
b.WriteString("_Empty. Call `Append(\"something\")`._\n")
return b.String()
}
start := 0
if len(entries) > renderEntries {
start = len(entries) - renderEntries
b.WriteString("Showing the last " + strconv.Itoa(renderEntries) + " of " + strconv.Itoa(len(entries)) + ".\n\n")
}
b.WriteString("| # | Entry |\n|---|---|\n")
for i := start; i < len(entries); i++ {
b.WriteString("| [" + strconv.Itoa(i) + "](/r/moul/x/provable/v0:entry/" + strconv.Itoa(i) + ") | " + entries[i] + " |\n")
}
return b.String()
}
func renderEntry(raw string) string {
i, err := strconv.Atoi(raw)
if err != nil || i < 0 || i >= len(entries) {
return "# provable\n\nNo entry `" + raw + "`.\n"
}
path, before, after := ProofOf(i)
var b strings.Builder
b.WriteString("# provable: entry " + strconv.Itoa(i) + "\n\n")
b.WriteString("```\n" + entries[i] + "\n```\n\n")
b.WriteString("## Inclusion proof\n\n")
b.WriteString("| Field | Value |\n|---|---|\n")
b.WriteString("| Index | " + strconv.Itoa(i) + " |\n")
b.WriteString("| Total | " + strconv.Itoa(log.Size()) + " |\n")
b.WriteString("| Path | `" + orDash(path) + "` |\n")
b.WriteString("| Before | `" + orDash(before) + "` |\n")
b.WriteString("| After | `" + orDash(after) + "` |\n")
b.WriteString("| Root | `" + rootOrDash() + "` |\n\n")
b.WriteString("Valid against that root only. The next `Append` moves it.\n")
return b.String()
}
func rootOrDash() string { return orDash(Root()) }
func orDash(s string) string {
if s == "" {
return "-"
}
return s
}
render_example_test.gno
package provable
// ExampleRender pins the realm's Render output as a testable example.
func ExampleRender() {
seed()
print(Render(""))
// Output:
// # provable
//
// What gno.land can and cannot prove about itself, demonstrated rather than asserted.
//
// ## The log
//
// An append-only Merkle mountain range. Appending costs O(log n) hashes and never rebuilds.
//
// | Field | Value |
// |---|---|
// | Entries | 3 / 512 |
// | Stored hashes | 4 |
// | Peaks | 2 |
// | Root | `c9d22dd237c668944fde619edb56cc1bee0e988b03ac08694f6d3aba440c0776` |
//
// This root is also the Tendermint simple-tree root over the same entries, so any
// Tendermint verifier accepts it. `Verify` and `VerifyFixed` check the two proof
// encodings against it.
//
// ## What the chain can prove
//
// `gno.land/pkg/gnoland/app.go` mounts exactly two stores. One is IAVL and merkleized,
// the other is a plain dbadapter whose `Commit` is documented as *"Always returns a zero
// commitID, as dbadapter store doesn't merkleize"*.
//
// | Data | Store | Provable against the app hash |
// |---|---|---|
// | Package source | iavl | yes |
// | Account balances | iavl | yes |
// | Escaped object hashes (cross-realm) | iavl | yes, the hash only |
// | Realm objects, types, realm metadata | base | **no** |
// | **This log** | base | **no** |
//
// ## What that means here
//
// A proof from this realm says *this entry is consistent with the root this realm
// published*. It cannot say *this root is the chain's own*, for two independent reasons:
//
// 1. Realm state is not merkleized, so there is no state proof to produce.
// 2. `chain/runtime` exposes `ChainID`, `ChainDomain`, `ChainHeight` and `GetSessionInfo`
// and nothing else. No app hash, no block hash, no header. A realm has no trusted
// root to check anything against.
//
// Anything built on Merkle proofs in a gno realm is trust-minimised relative to a
// committed root, never trustless. Saying otherwise would be the interesting-sounding
// half of a true story.
//
// ## Entries
//
// | # | Entry |
// |---|---|
// | [0](/r/moul/x/provable/v0:entry/0) | genesis of this log |
// | [1](/r/moul/x/provable/v0:entry/1) | a second commitment |
// | [2](/r/moul/x/provable/v0:entry/2) | a third commitment |
}
// ExampleRenderEntry pins the per-entry page, including a live proof.
func ExampleRenderEntry() {
seed()
print(Render("entry/1"))
// Output:
// # provable: entry 1
//
// ```
// a second commitment
// ```
//
// ## Inclusion proof
//
// | Field | Value |
// |---|---|
// | Index | 1 |
// | Total | 3 |
// | Path | `8f88aaa49b43fc28f266ea6b4f18d865933cad3584b59f162b8ce55edd8263fc` |
// | Before | `-` |
// | After | `495f0f3042890e970ad8344ae78ff490806c2b8403282d518e8112044bc43827` |
// | Root | `c9d22dd237c668944fde619edb56cc1bee0e988b03ac08694f6d3aba440c0776` |
//
// Valid against that root only. The next `Append` moves it.
}
// ExampleRenderMissingEntry pins the not-found page.
func ExampleRenderMissingEntry() {
seed()
print(Render("entry/99"))
// Output:
// # provable
//
// No entry `99`.
}