Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

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`.
}