permbook.gno
17.78 Kb · 535 lines
1// Package permbook is a bounded, authorization-carrying facade over
2// gno.land/p/nt/groups/v0. It lets a realm define named permissions, grant
3// them to addresses, revoke them, and ask "does this address currently hold
4// this permission" without iterating anything.
5//
6// It holds no coins, imports no banker, stores no callbacks, and owns no
7// package-level state. The importing realm allocates a *Book and keeps it
8// private.
9//
10// # What this package adds, and what it does not
11//
12// It adds exactly four things to groups, and deliberately nothing else:
13//
14// 1. an ADMIN bound to the book, with a two-step handoff;
15// 2. BOUNDS on permission count, holders per permission, and name shape;
16// 3. permission semantics instead of membership semantics — no base set, no
17// metadata slot, and an empty permission is pruned rather than kept;
18// 4. a cross-realm surface that is safe by CONSTRUCTION — the *groups.Group
19// is unexported and no method returns a mutable handle to it.
20//
21// Everything else — the B+-tree registry, the member sets, ordered
22// iteration, the readonly views — comes from groups. This package writes no
23// data-structure code.
24//
25// # The query
26//
27// if !book.Has("withdraw", who) {
28// panic("not authorized")
29// }
30//
31// Has costs two independent B+-tree descents: O(log P) to find the
32// permission, O(log H) to find the holder. It is NOT a function of how many
33// permissions `who` already holds. That matters: every other named-permission
34// implementation surveyed answers this by iterating the subject's
35// permissions, which makes the most-privileged address the most expensive to
36// check — the wrong asymptotic for an authorization check on a hot path.
37//
38// # Authorization
39//
40// Mutators take (_ int, rlm realm) and identify the principal as
41// rlm.Previous().Address(), after asserting rlm.IsCurrent(). The consuming
42// realm threads its own cur:
43//
44// func Grant(cur realm, perm string, addr address) {
45// if err := book.Grant(0, cur, perm, addr); err != nil {
46// panic(err)
47// }
48// }
49//
50// IsCurrent() rejects a stale or stashed realm value, so a hostile realm
51// cannot replay an old cur to impersonate the admin. This is the same shape
52// as p/nt/ownable/v0 and p/nt/ownable/v0/exts/authorizable.
53//
54// # Lifecycle of a permission
55//
56// A permission comes into existence on its first grant and ceases to exist
57// when its last holder is revoked. There is no create step and no reserved
58// name. Has returns false either way, so the distinction is invisible to a
59// caller and the book does not accumulate empty buckets.
60//
61// (absent) ──Grant──> held by 1..MaxHoldersPerPermission ──Revoke last──> (absent)
62// │
63// └── DropPermission ──> (absent)
64//
65// # Admin handoff is two-step
66//
67// NominateAdmin records a nominee; only AcceptAdmin, called by that nominee,
68// moves the admin. A one-step transfer to a well-formed-but-unowned address
69// is permanently fatal — address.IsValid only checks bech32 form, so a
70// mistyped address passes validation and leaves a book nobody can ever grant
71// or revoke on again. This is the Y4 finding from the audit of Cosmic Bull's
72// own r/permission_registry, carried forward.
73//
74// # Consumer contract — the parts this package CANNOT enforce
75//
76// 1. THREAD A LIVE cur. rlm.IsCurrent() proves the realm value came from a
77// live crossing frame, and rlm.Previous().Address() is then the principal
78// that crossed into your realm. A consumer that wraps a permbook mutator
79// in a NON-crossing exported helper resolves its importer's caller
80// instead of its importer — Class-2 designation forgery, in the consumer.
81// Call permbook mutators from your own crossing entrypoints, passing that
82// entrypoint's own cur.
83//
84// 2. DO NOT LEAK THE *Book. No method here returns a mutable handle, but a
85// consumer that exports its *Book — or returns it from a function
86// reachable by another realm — hands out every mutator on it, and
87// borrow rule #2 commits those writes under YOUR realm's authority. Keep
88// it in an unexported package-level variable.
89//
90// 3. Has ANSWERS ABOUT AN ADDRESS, NOT ABOUT YOUR CALLER. It performs no
91// authentication. Derive the address from your own crossing entrypoint's
92// cur.Previous().Address() and pass it in.
93//
94// 4. CHOOSE LIMITS DELIBERATELY. They are fixed for the life of a Book. A
95// consumer that needs different bounds later must allocate a second Book;
96// nothing here migrates state between them.
97//
98// # Note on the groups base set
99//
100// A groups.Group carries a base address set alongside its named roles. This
101// package never writes to it, so it is provably empty for any Book, and
102// "in the base set" can never mean "holds a permission".
103package permbook
104
105import (
106 "errors"
107
108 "gno.land/p/nt/groups/v0"
109)
110
111// Ceilings on what Limits may be configured to. They bound worst-case gas
112// and storage for any Book, however the consumer configures it.
113//
114// MaxPermissionsCeiling is the one that bounds GAS rather than merely
115// storage. Three operations walk every permission in the book at O(P log H)
116// — Permissions, HasAny, and RevokeAll — and this ceiling is what bounds
117// them. Everything else is logarithmic or paginated; see each method's own
118// doc for its cost, which is authoritative.
119//
120// In particular HasAny is NOT a cheap variant of Has. Has is two tree
121// descents; HasAny is a full walk of the registry. Do not put HasAny on a
122// hot authorization path or inside a per-item render loop.
123//
124// These ceilings are not the objection this package raises against a shared
125// registry. A shared registry's caps are rivalrous and unraisable because
126// one immutable realm holds every tenant's state; here a consumer that needs
127// more simply allocates another Book in its own realm, at no cost to anyone
128// else.
129const (
130 MaxPermissionsCeiling = 256
131 MaxHoldersCeiling = 10000
132 MaxNameLenCeiling = 64
133)
134
135// Default limits, used by NewDefault.
136const (
137 DefaultMaxPermissions = 64
138 DefaultMaxHoldersPerPermission = 1024
139 DefaultMaxNameLen = 32
140)
141
142var (
143 ErrUnauthorized = errors.New("permbook: caller is not the admin")
144 ErrNotLiveRealm = errors.New("permbook: rlm is not the caller's live cur")
145 ErrInvalidAddress = errors.New("permbook: invalid address")
146 ErrInvalidName = errors.New("permbook: permission name must be 1..MaxNameLen chars, lowercase alphanumeric and underscore only")
147 ErrInvalidLimits = errors.New("permbook: limits must be positive and within the package ceilings")
148 ErrAlreadyGranted = errors.New("permbook: address already holds this permission")
149 ErrNotGranted = errors.New("permbook: address does not hold this permission")
150 ErrPermissionLimit = errors.New("permbook: permission limit reached for this book")
151 ErrHolderLimit = errors.New("permbook: holder limit reached for this permission")
152 ErrNoPendingAdmin = errors.New("permbook: no pending admin nomination")
153 ErrNotPendingAdmin = errors.New("permbook: caller is not the pending admin")
154 ErrSameAdmin = errors.New("permbook: nominee is already the admin")
155 ErrUnknownPermission = errors.New("permbook: no such permission")
156)
157
158// Limits are fixed at construction and never change for the life of a Book.
159type Limits struct {
160 // MaxPermissions bounds how many distinct permission names may exist at
161 // once. Because Permissions and RevokeAll walk all of them, this bounds
162 // gas, not just storage.
163 MaxPermissions int
164
165 // MaxHoldersPerPermission bounds how many addresses may hold any one
166 // permission. No operation iterates holders unpaginated, so this bounds
167 // storage rather than gas.
168 MaxHoldersPerPermission int
169
170 // MaxNameLen bounds permission-name length.
171 MaxNameLen int
172}
173
174// DefaultLimits returns the limits used by NewDefault.
175func DefaultLimits() Limits {
176 return Limits{
177 MaxPermissions: DefaultMaxPermissions,
178 MaxHoldersPerPermission: DefaultMaxHoldersPerPermission,
179 MaxNameLen: DefaultMaxNameLen,
180 }
181}
182
183func (l Limits) valid() bool {
184 return l.MaxPermissions > 0 && l.MaxPermissions <= MaxPermissionsCeiling &&
185 l.MaxHoldersPerPermission > 0 && l.MaxHoldersPerPermission <= MaxHoldersCeiling &&
186 l.MaxNameLen > 0 && l.MaxNameLen <= MaxNameLenCeiling
187}
188
189// Book is a bounded set of named permissions with an admin. The zero value
190// is not usable; construct with New or NewDefault.
191//
192// SECURITY: keep a *Book in an unexported variable. It is the capability.
193// Every mutator on it is gated on the admin, but a realm that receives the
194// pointer itself can invoke those mutators, and borrow rule #2 commits the
195// writes under the ALLOCATING realm's authority.
196type Book struct {
197 g *groups.Group
198 admin address
199 pendingAdmin address
200 lim Limits
201}
202
203// New constructs an empty Book owned by admin, with explicit limits.
204func New(admin address, lim Limits) (*Book, error) {
205 if !admin.IsValid() {
206 return nil, ErrInvalidAddress
207 }
208 if !lim.valid() {
209 return nil, ErrInvalidLimits
210 }
211 return &Book{
212 g: groups.NewGroup(),
213 admin: admin,
214 lim: lim,
215 }, nil
216}
217
218// NewDefault constructs an empty Book owned by admin, with DefaultLimits.
219func NewDefault(admin address) (*Book, error) {
220 return New(admin, DefaultLimits())
221}
222
223// --- authorization ---
224
225// principal returns the address that crossed into the caller's realm, after
226// proving rlm is a live crossing frame rather than a stashed value.
227func principal(_ int, rlm realm) (address, error) {
228 if !rlm.IsCurrent() {
229 return address(""), ErrNotLiveRealm
230 }
231 return rlm.Previous().Address(), nil
232}
233
234// assertAdmin resolves the principal from rlm and requires it to be the
235// book's admin.
236func (b *Book) assertAdmin(_ int, rlm realm) error {
237 who, err := principal(0, rlm)
238 if err != nil {
239 return err
240 }
241 if who != b.admin {
242 return ErrUnauthorized
243 }
244 return nil
245}
246
247// --- grant and revoke ---
248
249// Grant gives addr the named permission. Admin only.
250//
251// The permission is created if it does not exist. Granting a permission the
252// address already holds returns ErrAlreadyGranted rather than silently
253// succeeding, so a consumer cannot mistake a no-op for a state change.
254func (b *Book) Grant(_ int, rlm realm, perm string, addr address) error {
255 if err := b.assertAdmin(0, rlm); err != nil {
256 return err
257 }
258 if !b.validName(perm) {
259 return ErrInvalidName
260 }
261 if !addr.IsValid() {
262 return ErrInvalidAddress
263 }
264
265 r, found := b.g.GetRole(perm)
266 if !found {
267 if b.g.RoleCount() >= b.lim.MaxPermissions {
268 return ErrPermissionLimit
269 }
270 var err error
271 r, err = b.g.AddRole(perm)
272 if err != nil {
273 return err
274 }
275 }
276
277 members := r.Members()
278 if members.Has(addr) {
279 return ErrAlreadyGranted
280 }
281 if members.Size() >= b.lim.MaxHoldersPerPermission {
282 // No rollback is needed here, and adding one would be dead code.
283 //
284 // Reaching this branch requires Size() >= MaxHoldersPerPermission,
285 // and Limits.valid guarantees MaxHoldersPerPermission >= 1, so
286 // Size() >= 1. A permission created moments ago above has Size() 0
287 // and therefore cannot reach this branch at all. So the permission
288 // this rejects always pre-existed with holders, and returning leaves
289 // no orphan empty bucket occupying a MaxPermissions slot.
290 //
291 // That argument depends on Limits.valid rejecting a zero holder
292 // limit. If that ever changes, this branch needs an undo.
293 return ErrHolderLimit
294 }
295
296 members.Add(addr)
297 return nil
298}
299
300// Revoke removes the named permission from addr. Admin only.
301//
302// Revoking the last holder removes the permission itself, freeing its slot
303// against MaxPermissions. Has reports false either way, so this is invisible
304// to a caller and keeps the book from accumulating empty buckets.
305func (b *Book) Revoke(_ int, rlm realm, perm string, addr address) error {
306 if err := b.assertAdmin(0, rlm); err != nil {
307 return err
308 }
309 if !b.revokeOne(perm, addr) {
310 return ErrNotGranted
311 }
312 return nil
313}
314
315// revokeOne removes addr from perm and prunes the permission if it is left
316// empty. Reports whether addr actually held it. No authorization: every
317// caller is inside this package and has already gated on the admin.
318func (b *Book) revokeOne(perm string, addr address) bool {
319 r, found := b.g.GetRole(perm)
320 if !found {
321 return false
322 }
323 members := r.Members()
324 if !members.Remove(addr) {
325 return false
326 }
327 if members.Size() == 0 {
328 b.g.RemoveRole(perm)
329 }
330 return true
331}
332
333// RevokeAll removes addr from every permission in the book and reports how
334// many were removed. Admin only.
335//
336// Cost is O(P log H) in the book's permission count — bounded by
337// MaxPermissions, which is why that limit has a ceiling.
338//
339// Implementation note: the permission names are collected FIRST, into a
340// value slice, and the registry is mutated only after that walk returns.
341// groups documents that mutating the role registry mid-iteration can panic
342// and abort the transaction.
343func (b *Book) RevokeAll(_ int, rlm realm, addr address) (int, error) {
344 if err := b.assertAdmin(0, rlm); err != nil {
345 return 0, err
346 }
347 names := b.g.RolesContaining(addr)
348 n := 0
349 for _, perm := range names {
350 if b.revokeOne(perm, addr) {
351 n++
352 }
353 }
354 return n, nil
355}
356
357// DropPermission removes a permission and every grant of it. Admin only.
358//
359// Cost is O(log P): groups discards the whole member set with the role and
360// does not walk it, so this is safe for a permission with many holders.
361func (b *Book) DropPermission(_ int, rlm realm, perm string) error {
362 if err := b.assertAdmin(0, rlm); err != nil {
363 return err
364 }
365 if !b.g.RemoveRole(perm) {
366 return ErrUnknownPermission
367 }
368 return nil
369}
370
371// --- admin handoff ---
372
373// NominateAdmin records a nominee for the admin role. Admin only. The
374// handoff does NOT take effect until the nominee calls AcceptAdmin, and a
375// nomination may be withdrawn with CancelNomination until then.
376func (b *Book) NominateAdmin(_ int, rlm realm, nominee address) error {
377 if err := b.assertAdmin(0, rlm); err != nil {
378 return err
379 }
380 if !nominee.IsValid() {
381 return ErrInvalidAddress
382 }
383 if nominee == b.admin {
384 return ErrSameAdmin
385 }
386 b.pendingAdmin = nominee
387 return nil
388}
389
390// CancelNomination withdraws a pending nomination. Admin only.
391func (b *Book) CancelNomination(_ int, rlm realm) error {
392 if err := b.assertAdmin(0, rlm); err != nil {
393 return err
394 }
395 if b.pendingAdmin == address("") {
396 return ErrNoPendingAdmin
397 }
398 b.pendingAdmin = address("")
399 return nil
400}
401
402// AcceptAdmin completes a pending handoff. Only the nominee may call it.
403func (b *Book) AcceptAdmin(_ int, rlm realm) error {
404 who, err := principal(0, rlm)
405 if err != nil {
406 return err
407 }
408 if b.pendingAdmin == address("") {
409 return ErrNoPendingAdmin
410 }
411 if who != b.pendingAdmin {
412 return ErrNotPendingAdmin
413 }
414 b.admin = who
415 b.pendingAdmin = address("")
416 return nil
417}
418
419// --- queries ---
420//
421// Queries perform NO caller authentication. They answer questions about an
422// address, not about your caller. See consumer-contract clause 3.
423
424// Has reports whether addr currently holds the named permission.
425//
426// Two B+-tree descents, O(log P + log H). Independent of how many other
427// permissions addr holds. Never panics; unknown permissions report false.
428func (b *Book) Has(perm string, addr address) bool {
429 r, found := b.g.GetRole(perm)
430 if !found {
431 return false
432 }
433 return r.Members().Has(addr)
434}
435
436// HasAny reports whether addr holds any permission at all. O(P log H).
437func (b *Book) HasAny(addr address) bool {
438 return b.g.HasAny(addr)
439}
440
441// Permissions returns the names addr holds, in lexicographic order, or nil.
442// O(P log H) — bounded by MaxPermissions.
443func (b *Book) Permissions(addr address) []string {
444 return b.g.RolesContaining(addr)
445}
446
447// PermissionCount returns how many distinct permissions currently exist.
448func (b *Book) PermissionCount() int {
449 return b.g.RoleCount()
450}
451
452// PermissionNames returns up to count permission names in lexicographic
453// order, starting at offset. Paginated so the caller, not the book, chooses
454// how much work a single call does.
455func (b *Book) PermissionNames(offset, count int) []string {
456 if count <= 0 {
457 return nil
458 }
459 var out []string
460 b.g.IterateRoles(offset, count, func(rr *groups.ReadonlyRole) bool {
461 out = append(out, rr.Name())
462 return false
463 })
464 return out
465}
466
467// HolderCount returns how many addresses hold the named permission, or 0 if
468// it does not exist.
469func (b *Book) HolderCount(perm string) int {
470 r, found := b.g.GetRole(perm)
471 if !found {
472 return 0
473 }
474 return r.Members().Size()
475}
476
477// Holders returns up to count holders of the named permission, in sorted
478// order, starting at offset. Paginated for the same reason as
479// PermissionNames. Returns nil for an unknown permission.
480func (b *Book) Holders(perm string, offset, count int) []address {
481 if count <= 0 {
482 return nil
483 }
484 r, found := b.g.GetRole(perm)
485 if !found {
486 return nil
487 }
488 var out []address
489 r.Members().IterateByOffset(offset, count, func(a address) bool {
490 out = append(out, a)
491 return false
492 })
493 return out
494}
495
496// Admin returns the book's current admin.
497func (b *Book) Admin() address {
498 return b.admin
499}
500
501// PendingAdmin returns the nominated-but-not-yet-accepted admin, or the
502// empty address if there is no pending nomination.
503func (b *Book) PendingAdmin() address {
504 return b.pendingAdmin
505}
506
507// IsAdmin reports whether addr is the book's admin.
508func (b *Book) IsAdmin(addr address) bool {
509 return addr == b.admin
510}
511
512// Limits returns the book's fixed limits.
513func (b *Book) Limits() Limits {
514 return b.lim
515}
516
517// --- names ---
518
519// validName restricts permission names to lowercase alphanumerics and
520// underscores, within the book's MaxNameLen.
521//
522// Beyond hygiene this is a security property: permission names end up in
523// composite trust decisions and in rendered output, so no delimiter,
524// whitespace, or markdown character may enter one.
525func (b *Book) validName(name string) bool {
526 if name == "" || len(name) > b.lim.MaxNameLen {
527 return false
528 }
529 for _, c := range name {
530 if !((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || c == '_') {
531 return false
532 }
533 }
534 return true
535}
