diff --git a/services/syncbase/common/access_util.go b/services/syncbase/common/access_util.go
index a76806d..2b8cf96 100644
--- a/services/syncbase/common/access_util.go
+++ b/services/syncbase/common/access_util.go
@@ -6,6 +6,7 @@
 
 import (
 	"sort"
+	"strings"
 
 	"v.io/v23/context"
 	"v.io/v23/rpc"
@@ -13,6 +14,7 @@
 	"v.io/v23/security/access"
 	wire "v.io/v23/services/syncbase"
 	"v.io/v23/verror"
+	"v.io/x/ref/services/syncbase/store"
 )
 
 // ValidatePerms does basic sanity checking on the provided perms:
@@ -49,6 +51,33 @@
 	return nil
 }
 
+// AnyOfTagsAuthorizer provides an authorizer that allows blessings matching any
+// pattern in perms corresponding to any of the provided tags.
+func AnyOfTagsAuthorizer(tags []access.Tag, perms access.Permissions) *anyOfTagsAuthorizer {
+	return &anyOfTagsAuthorizer{
+		tags:  tags,
+		perms: perms,
+	}
+}
+
+type anyOfTagsAuthorizer struct {
+	tags  []access.Tag
+	perms access.Permissions
+}
+
+func (a *anyOfTagsAuthorizer) Authorize(ctx *context.T, call security.Call) error {
+	blessings, invalid := security.RemoteBlessingNames(ctx, call)
+	for _, tag := range a.tags {
+		if acl, exists := a.perms[string(tag)]; exists && acl.Includes(blessings...) {
+			// At least one tag in the set had a matching pattern.
+			return nil
+		}
+	}
+	// None of the tags had a matching pattern. Deny access.
+	return verror.New(verror.ErrNoAccess, ctx,
+		access.NewErrNoPermissions(ctx, blessings, invalid, strings.Join(access.TagStrings(a.tags...), " ∨ ")))
+}
+
 // CheckImplicitPerms performs an authorization check against the implicit
 // permissions derived from the blessing pattern in the Id. It returns the
 // generated implicit perms or an authorization error.
@@ -57,8 +86,127 @@
 func CheckImplicitPerms(ctx *context.T, call rpc.ServerCall, id wire.Id, allowedTags []access.Tag) (access.Permissions, error) {
 	implicitPerms := access.Permissions{}.Add(security.BlessingPattern(id.Blessing), access.TagStrings(allowedTags...)...)
 	// Note, allowedTags is expected to contain access.Admin.
-	if err := implicitPerms[string(access.Admin)].Authorize(ctx, call.Security()); err != nil {
+	if err := AnyOfTagsAuthorizer([]access.Tag{access.Admin}, implicitPerms).Authorize(ctx, call.Security()); err != nil {
 		return nil, verror.New(wire.ErrUnauthorizedCreateId, ctx, id.Blessing, id.Name, err)
 	}
 	return implicitPerms, nil
 }
+
+// PermserData is persistent metadata about an object, including perms.
+type PermserData interface {
+	// GetPerms returns the perms for the object.
+	GetPerms() access.Permissions
+}
+
+// Permser is an object in the hierarchy that supports retrieving perms and
+// authorizing access to existence checks.
+type Permser interface {
+	// GetDataWithExistAuth must return a nil error only if the object exists and
+	// the caller is authorized to know it (Resolve access up to the parent and
+	// any access tag on self, or Resolve access up to grandparent and Read or
+	// Write on parent). Otherwise, the returned error must not leak existence
+	// data (ErrNoExistOrNoAccess must be returned instead of more specific
+	// errors such as ErrNoExist if the caller is not authorized to know about
+	// an object's existence).
+	// If the error is nil, PermserData must be populated with object metadata
+	// loaded from the store and the method must return perms of the object's
+	// parent and the object itself.
+	// A typical implementation calls GetPermsWithExistAndParentResolveAuth on
+	// the object's parent, followed by GetDataWithExistAuthStep.
+	GetDataWithExistAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, v PermserData) (parentPerms, perms access.Permissions, existErr error)
+
+	// PermserData returns a zero-value PermserData for this object.
+	PermserData() PermserData
+}
+
+// getDataWithExistAndParentResolveAuth is equivalent to
+// GetPermsWithExistAndParentResolveAuth, in addition populating the loaded
+// PermserData into v.
+func getDataWithExistAndParentResolveAuth(ctx *context.T, call rpc.ServerCall, at Permser, st store.StoreReader, v PermserData) (access.Permissions, error) {
+	parentPerms, perms, existErr := at.GetDataWithExistAuth(ctx, call, st, v)
+	if existErr != nil {
+		return nil, existErr
+	}
+	return perms, AnyOfTagsAuthorizer([]access.Tag{access.Resolve}, parentPerms).Authorize(ctx, call.Security())
+}
+
+// GetPermsWithExistAndParentResolveAuth returns a nil error only if the object
+// exists, the client is authorized to know it and has resolve access on all
+// objects up to and including this object's parent.
+func GetPermsWithExistAndParentResolveAuth(ctx *context.T, call rpc.ServerCall, at Permser, st store.StoreReader) (access.Permissions, error) {
+	return getDataWithExistAndParentResolveAuth(ctx, call, at, st, at.PermserData())
+}
+
+// GetDataWithAuth is equivalent to GetPermsWithAuth, in addition populating
+// the loaded PermserData into v.
+func GetDataWithAuth(ctx *context.T, call rpc.ServerCall, at Permser, tags []access.Tag, st store.StoreReader, v PermserData) (access.Permissions, error) {
+	perms, existErr := getDataWithExistAndParentResolveAuth(ctx, call, at, st, v)
+	if existErr != nil {
+		return nil, existErr
+	}
+	return perms, AnyOfTagsAuthorizer(tags, perms).Authorize(ctx, call.Security())
+}
+
+// GetPermsWithAuth returns a nil error only if the client has exist and parent
+// resolve access (see GetPermsWithExistAndParentResolveAuth) as well as at
+// least one of the specified tags on the object itself.
+func GetPermsWithAuth(ctx *context.T, call rpc.ServerCall, at Permser, tags []access.Tag, st store.StoreReader) (access.Permissions, error) {
+	return GetDataWithAuth(ctx, call, at, tags, st, at.PermserData())
+}
+
+// GetDataWithExistAuthStep is a helper intended for use in GetDataWithExistAuth
+// implementations. It assumes Resolve access up to and including the object's
+// grandparent. It loads the object's metadata from the store into v, returning
+// ErrNoExistOrNoAccess, ErrNoExist or other errors when appropriate; if the
+// caller is not authorized for exist access, ErrNoExistOrNoAccess is always
+// returned. If a nil StoreReader is passed in, the object is assumed to not
+// exist.
+func GetDataWithExistAuthStep(ctx *context.T, call rpc.ServerCall, name string, parentPerms access.Permissions, st store.StoreReader, k string, v PermserData) error {
+	if st == nil {
+		return fuzzifyErrorForExists(ctx, call, name, parentPerms, nil, verror.New(verror.ErrNoExist, ctx, name))
+	}
+	if getErr := store.Get(ctx, st, k, v); getErr != nil {
+		if verror.ErrorID(getErr) == verror.ErrNoExist.ID {
+			getErr = verror.New(verror.ErrNoExist, ctx, name)
+		}
+		return fuzzifyErrorForExists(ctx, call, name, parentPerms, nil, getErr)
+	}
+	return fuzzifyErrorForExists(ctx, call, name, parentPerms, v.GetPerms(), nil)
+}
+
+// fuzzifyErrorForExists passes through the original error only if the caller is
+// authorized for exist access. Otherwise, ErrNoExistOrNoAccess is returned
+// instead. It assumes Resolve access up to and including the object's
+// grandparent.
+func fuzzifyErrorForExists(ctx *context.T, call rpc.ServerCall, name string, parentPerms, perms access.Permissions, originalErr error) error {
+	if parentRWErr := AnyOfTagsAuthorizer([]access.Tag{access.Read, access.Write}, parentPerms).Authorize(ctx, call.Security()); parentRWErr == nil {
+		// Read or Write on parent, return original error.
+		return originalErr
+	}
+	fuzzyErr := verror.New(verror.ErrNoExistOrNoAccess, ctx, name)
+	if perms == nil {
+		// Exit early if object does not exist - caller cannot have any perms on it.
+		return fuzzyErr
+	}
+	// No Read or Write on parent, caller must have both Resolve on parent and at
+	// least one tag on the object itself to get the original error.
+	if parentXErr := AnyOfTagsAuthorizer([]access.Tag{access.Resolve}, parentPerms).Authorize(ctx, call.Security()); parentXErr != nil {
+		return fuzzyErr
+	}
+	if selfAnyErr := AnyOfTagsAuthorizer(access.AllTypicalTags(), perms).Authorize(ctx, call.Security()); selfAnyErr != nil {
+		return fuzzyErr
+	}
+	return originalErr
+}
+
+// ErrorToExists converts the error returned from GetDataWithExistAuth into
+// the Exists RPC result, suppressing ErrNoExist.
+func ErrorToExists(err error) (bool, error) {
+	if err == nil {
+		return true, nil
+	}
+	if verror.ErrorID(err) == verror.ErrNoExist.ID {
+		return false, nil
+	}
+	return false, err
+}
diff --git a/services/syncbase/server/collection.go b/services/syncbase/server/collection.go
index 06a2be5..d497c97 100644
--- a/services/syncbase/server/collection.go
+++ b/services/syncbase/server/collection.go
@@ -107,9 +107,10 @@
 
 func (c *collectionReq) Exists(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (bool, error) {
 	impl := func(sntx store.SnapshotOrTransaction) error {
-		return util.GetWithAuth(ctx, call, c.d.st, c.permsKey(), &interfaces.CollectionPerms{})
+		_, _, err := c.GetDataWithExistAuth(ctx, call, sntx, &interfaces.CollectionPerms{})
+		return err
 	}
-	return util.ErrorToExists(c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl))
+	return common.ErrorToExists(c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl))
 }
 
 func (c *collectionReq) GetPermissions(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (perms access.Permissions, err error) {
@@ -207,7 +208,26 @@
 		}
 		return util.GlobChildren(ctx, call, matcher, sntx, common.JoinKeyParts(common.RowPrefix, c.stKeyPart()))
 	}
-	return store.RunWithSnapshot(c.d.st, impl)
+	return c.d.runWithNewSnapshot(ctx, impl)
+}
+
+////////////////////////////////////////
+// Authorization hooks
+
+var _ common.Permser = (*collectionReq)(nil)
+
+func (c *collectionReq) GetDataWithExistAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, v common.PermserData) (parentPerms, perms access.Permissions, _ error) {
+	cp := v.(*interfaces.CollectionPerms)
+	parentPerms, err := common.GetPermsWithExistAndParentResolveAuth(ctx, call, c.d, st)
+	if err != nil {
+		return nil, nil, err
+	}
+	err = common.GetDataWithExistAuthStep(ctx, call, c.id.String(), parentPerms, st, c.permsKey(), cp)
+	return parentPerms, cp.GetPerms(), err
+}
+
+func (c *collectionReq) PermserData() common.PermserData {
+	return &interfaces.CollectionPerms{}
 }
 
 ////////////////////////////////////////
@@ -231,6 +251,7 @@
 // TODO(rogulenko): Revisit this behavior. Eventually we'll want the
 // collection-level access check to be a check for "Resolve", i.e. also check
 // access to service and database.
+// TODO(ivanpi): Remove once all callers are ported to explicit auth.
 func (c *collectionReq) checkAccess(ctx *context.T, call rpc.ServerCall, sntx store.SnapshotOrTransaction) (access.Permissions, error) {
 	collectionPerms := &interfaces.CollectionPerms{}
 	if err := util.GetWithAuth(ctx, call, sntx, c.permsKey(), collectionPerms); err != nil {
diff --git a/services/syncbase/server/database.go b/services/syncbase/server/database.go
index bf0b800..16ec31c 100644
--- a/services/syncbase/server/database.go
+++ b/services/syncbase/server/database.go
@@ -242,10 +242,11 @@
 }
 
 func (d *database) Exists(ctx *context.T, call rpc.ServerCall) (bool, error) {
-	if !d.exists {
-		return false, nil
+	impl := func(sntx store.SnapshotOrTransaction) error {
+		_, _, err := d.GetDataWithExistAuth(ctx, call, sntx, &DatabaseData{})
+		return err
 	}
-	return util.ErrorToExists(util.GetWithAuth(ctx, call, d.st, d.stKey(), &DatabaseData{}))
+	return common.ErrorToExists(d.runWithNewSnapshot(ctx, impl))
 }
 
 var rng *rand.Rand = rand.New(rand.NewSource(time.Now().UTC().UnixNano()))
@@ -737,16 +738,44 @@
 }
 
 ////////////////////////////////////////
+// Authorization hooks
+
+var _ common.Permser = (*service)(nil)
+
+func (d *database) GetDataWithExistAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, v common.PermserData) (parentPerms, perms access.Permissions, _ error) {
+	dd := v.(*DatabaseData)
+	parentPerms, err := common.GetPermsWithExistAndParentResolveAuth(ctx, call, d.s, d.s.st)
+	if err != nil {
+		return nil, nil, err
+	}
+	err = common.GetDataWithExistAuthStep(ctx, call, d.id.String(), parentPerms, st, d.stKey(), dd)
+	return parentPerms, dd.GetPerms(), err
+}
+
+func (d *database) PermserData() common.PermserData {
+	return &DatabaseData{}
+}
+
+////////////////////////////////////////
 // Internal helpers
 
 func (d *database) stKey() string {
 	return common.DatabasePrefix
 }
 
+func (d *database) runWithNewSnapshot(ctx *context.T, fn func(sntx store.SnapshotOrTransaction) error) error {
+	return d.runWithExistingBatchOrNewSnapshot(ctx, "", fn)
+}
+
 func (d *database) runWithExistingBatchOrNewSnapshot(ctx *context.T, bh wire.BatchHandle, fn func(sntx store.SnapshotOrTransaction) error) error {
+	if !d.exists {
+		// TODO(ivanpi): Return fuzzy error if appropriate.
+		return verror.New(verror.ErrNoExist, ctx, d.id)
+	}
 	if bh != "" {
 		if sntx, err := d.batchReader(ctx, bh); err != nil {
 			// Batch does not exist.
+			// TODO(ivanpi): Return fuzzy error if appropriate.
 			return err
 		} else {
 			return fn(sntx)
@@ -757,9 +786,14 @@
 }
 
 func (d *database) runInExistingBatchOrNewTransaction(ctx *context.T, bh wire.BatchHandle, fn func(ts *transactionState) error) error {
+	if !d.exists {
+		// TODO(ivanpi): Return fuzzy error if appropriate.
+		return verror.New(verror.ErrNoExist, ctx, d.id)
+	}
 	if bh != "" {
 		if batch, err := d.batchTransaction(ctx, bh); err != nil {
 			// Batch does not exist or is readonly (snapshot).
+			// TODO(ivanpi): Return fuzzy error if appropriate.
 			return err
 		} else {
 			return fn(batch)
diff --git a/services/syncbase/server/dispatcher.go b/services/syncbase/server/dispatcher.go
index 4b2648c..cd0f0f2 100644
--- a/services/syncbase/server/dispatcher.go
+++ b/services/syncbase/server/dispatcher.go
@@ -79,13 +79,12 @@
 		}
 	}
 
-	dbExists := false
 	var d *database
 	if dInt, err := disp.s.Database(ctx, nil, dbId); err == nil {
 		d = dInt.(*database) // panics on failure, as desired
-		dbExists = true
 	} else {
 		if verror.ErrorID(err) != verror.ErrNoExist.ID {
+			// TODO(ivanpi): Panic here? Database() seems to never return other errors.
 			return nil, nil, err
 		} else {
 			// Database does not exist. Create a short-lived database object to
@@ -100,17 +99,14 @@
 	// TODO(sadovsky): Is it possible to determine the RPC method from the
 	// context? If so, we can check here that the database exists (unless the
 	// client is calling Database.Create), and avoid the "d.exists" checks in all
-	// the RPC method implementations.
+	// the RPC method implementations. Note, this would also require being able
+	// to authorize the user to return the appropriate error type (ErrNoExist vs
+	// ErrNoExistOrNoAccess), possibly by returning a specialized authorizer.
+
 	if len(parts) == 1 {
 		return wire.DatabaseServer(d), auth, nil
 	}
 
-	// All collection and row methods require the database to exist. If it
-	// doesn't, abort early.
-	if !dbExists {
-		return nil, nil, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
-
 	// Note, it's possible for the database to be deleted concurrently with
 	// downstream handling of this request. Depending on the order in which things
 	// execute, the client may not get an error, but in any case ultimately the
@@ -131,5 +127,6 @@
 		return wire.RowServer(rReq), auth, nil
 	}
 
-	return nil, nil, verror.NewErrNoExist(ctx)
+	// TODO(ivanpi): Panic here? This should never happen since we do SplitN.
+	return nil, nil, verror.New(wire.ErrInvalidName, ctx, suffix, "too many name components")
 }
diff --git a/services/syncbase/server/interfaces/database.go b/services/syncbase/server/interfaces/database.go
index 7b8d8c5..111c6d7 100644
--- a/services/syncbase/server/interfaces/database.go
+++ b/services/syncbase/server/interfaces/database.go
@@ -25,7 +25,7 @@
 
 	// CheckPermsInternal checks whether the given RPC (ctx, call) is allowed per
 	// the database perms.
-	// Designed for use from within Service.DestroyDatabase.
+	// TODO(ivanpi): Remove once all callers are ported to explicit auth.
 	CheckPermsInternal(ctx *context.T, call rpc.ServerCall, st store.StoreReader) error
 
 	// GetSchemaMetadataInternal returns SchemaMetadata stored for this db
diff --git a/services/syncbase/server/interfaces/sync_types.go b/services/syncbase/server/interfaces/sync_types.go
index 5ed2d98..b948b83 100644
--- a/services/syncbase/server/interfaces/sync_types.go
+++ b/services/syncbase/server/interfaces/sync_types.go
@@ -6,7 +6,7 @@
 
 import (
 	"v.io/v23/security/access"
-	"v.io/x/ref/services/syncbase/server/util"
+	"v.io/x/ref/services/syncbase/common"
 )
 
 func (in Knowledge) DeepCopy() Knowledge {
@@ -70,7 +70,7 @@
 }
 
 var (
-	_ util.Permser = (*CollectionPerms)(nil)
+	_ common.PermserData = (*CollectionPerms)(nil)
 )
 
 func (perms *CollectionPerms) GetPerms() access.Permissions {
diff --git a/services/syncbase/server/row.go b/services/syncbase/server/row.go
index 8101289..6a0550c 100644
--- a/services/syncbase/server/row.go
+++ b/services/syncbase/server/row.go
@@ -7,11 +7,10 @@
 import (
 	"v.io/v23/context"
 	"v.io/v23/rpc"
+	"v.io/v23/security/access"
 	wire "v.io/v23/services/syncbase"
-	"v.io/v23/verror"
 	"v.io/v23/vom"
 	"v.io/x/ref/services/syncbase/common"
-	"v.io/x/ref/services/syncbase/server/util"
 	"v.io/x/ref/services/syncbase/store"
 )
 
@@ -29,8 +28,14 @@
 // RPC methods
 
 func (r *rowReq) Exists(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (bool, error) {
-	_, err := r.Get(ctx, call, bh)
-	return util.ErrorToExists(err)
+	allowExists := []access.Tag{access.Read, access.Write}
+	impl := func(sntx store.SnapshotOrTransaction) (err error) {
+		if _, err := common.GetPermsWithAuth(ctx, call, r.c, allowExists, sntx); err != nil {
+			return err
+		}
+		return store.Get(ctx, sntx, r.stKey(), &vom.RawBytes{})
+	}
+	return common.ErrorToExists(r.c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl))
 }
 
 func (r *rowReq) Get(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (*vom.RawBytes, error) {
@@ -76,16 +81,9 @@
 	if _, err := r.c.checkAccess(ctx, call, sntx); err != nil {
 		return nil, err
 	}
-	value, err := sntx.Get([]byte(r.stKey()), nil)
 	var valueAsRawBytes vom.RawBytes
-	if err == nil {
-		err = vom.Decode(value, &valueAsRawBytes)
-	}
-	if err != nil {
-		if verror.ErrorID(err) == store.ErrUnknownKey.ID {
-			return nil, verror.New(verror.ErrNoExist, ctx, r.stKey())
-		}
-		return nil, verror.New(verror.ErrInternal, ctx, err)
+	if err := store.Get(ctx, sntx, r.stKey(), &valueAsRawBytes); err != nil {
+		return nil, err
 	}
 	return &valueAsRawBytes, nil
 }
@@ -93,20 +91,12 @@
 // put writes data to the storage engine.
 // Performs authorization check.
 func (r *rowReq) put(ctx *context.T, call rpc.ServerCall, ts *transactionState, value *vom.RawBytes) error {
-	tx := ts.tx
-	currentPerms, err := r.c.checkAccess(ctx, call, tx)
+	currentPerms, err := r.c.checkAccess(ctx, call, ts.tx)
 	if err != nil {
 		return err
 	}
 	ts.MarkDataChanged(r.c.id, currentPerms)
-	valueAsBytes, err := vom.Encode(value)
-	if err != nil {
-		return err
-	}
-	if err = tx.Put([]byte(r.stKey()), valueAsBytes); err != nil {
-		return verror.New(verror.ErrInternal, ctx, err)
-	}
-	return nil
+	return store.Put(ctx, ts.tx, r.stKey(), value)
 }
 
 // delete deletes data from the storage engine.
@@ -117,8 +107,5 @@
 		return err
 	}
 	ts.MarkDataChanged(r.c.id, currentPerms)
-	if err := ts.tx.Delete([]byte(r.stKey())); err != nil {
-		return verror.New(verror.ErrInternal, ctx, err)
-	}
-	return nil
+	return store.Delete(ctx, ts.tx, r.stKey())
 }
diff --git a/services/syncbase/server/service.go b/services/syncbase/server/service.go
index 87b1e09..2693479 100644
--- a/services/syncbase/server/service.go
+++ b/services/syncbase/server/service.go
@@ -602,6 +602,29 @@
 }
 
 ////////////////////////////////////////
+// Authorization hooks
+
+var _ common.Permser = (*service)(nil)
+
+func (s *service) GetDataWithExistAuth(ctx *context.T, _ rpc.ServerCall, st store.StoreReader, v common.PermserData) (parentPerms, perms access.Permissions, _ error) {
+	sd := v.(*ServiceData)
+	getErr := store.Get(ctx, st, s.stKey(), sd)
+	if verror.ErrorID(getErr) == verror.ErrNoExist.ID {
+		// ServiceData entry should always exist.
+		getErr = verror.New(verror.ErrBadState, ctx, "ServiceData entry missing")
+	}
+	return openAcl(), sd.GetPerms(), getErr
+}
+
+func openAcl() access.Permissions {
+	return access.Permissions{}.Add(security.AllPrincipals, access.TagStrings(access.AllTypicalTags()...)...)
+}
+
+func (s *service) PermserData() common.PermserData {
+	return &ServiceData{}
+}
+
+////////////////////////////////////////
 // Other internal helpers
 
 func (s *service) stKey() string {
diff --git a/services/syncbase/server/types.go b/services/syncbase/server/types.go
index 3120666..b4c4830 100644
--- a/services/syncbase/server/types.go
+++ b/services/syncbase/server/types.go
@@ -6,12 +6,12 @@
 
 import (
 	"v.io/v23/security/access"
-	"v.io/x/ref/services/syncbase/server/util"
+	"v.io/x/ref/services/syncbase/common"
 )
 
 var (
-	_ util.Permser = (*ServiceData)(nil)
-	_ util.Permser = (*DatabaseData)(nil)
+	_ common.PermserData = (*ServiceData)(nil)
+	_ common.PermserData = (*DatabaseData)(nil)
 )
 
 func (data *ServiceData) GetPerms() access.Permissions {
diff --git a/services/syncbase/server/util/store.go b/services/syncbase/server/util/store.go
index e023ac0..f44086f 100644
--- a/services/syncbase/server/util/store.go
+++ b/services/syncbase/server/util/store.go
@@ -11,6 +11,7 @@
 	"v.io/v23/rpc"
 	"v.io/v23/security/access"
 	"v.io/v23/verror"
+	"v.io/x/ref/services/syncbase/common"
 	"v.io/x/ref/services/syncbase/store"
 )
 
@@ -28,13 +29,8 @@
 // TODO(sadovsky): Perhaps these functions should strip key prefixes such as
 // "c:" from the error messages they return.
 
-type Permser interface {
-	// GetPerms returns the Permissions for this Layer.
-	GetPerms() access.Permissions
-}
-
 // GetWithAuth does Get followed by an auth check.
-func GetWithAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, k string, v Permser) error {
+func GetWithAuth(ctx *context.T, call rpc.ServerCall, st store.StoreReader, k string, v common.PermserData) error {
 	if err := store.Get(ctx, st, k, v); err != nil {
 		return err
 	}
@@ -48,7 +44,7 @@
 // UpdateWithAuth performs a read-modify-write.
 // Input v is populated by the "read" step. fn should "modify" v.
 // Performs an auth check as part of the "read" step.
-func UpdateWithAuth(ctx *context.T, call rpc.ServerCall, tx store.Transaction, k string, v Permser, fn func() error) error {
+func UpdateWithAuth(ctx *context.T, call rpc.ServerCall, tx store.Transaction, k string, v common.PermserData, fn func() error) error {
 	if err := GetWithAuth(ctx, call, tx, k, v); err != nil {
 		return err
 	}
@@ -57,22 +53,3 @@
 	}
 	return store.Put(ctx, tx, k, v)
 }
-
-// ErrorToExists wraps a call to Get and returns true if Get found the
-// object, false otherwise, suppressing ErrNoExist. Access errors are
-// suppressed as well because they imply existence in some Get
-// implementations.
-// TODO(ivanpi): Revisit once ACL specification is finalized.
-func ErrorToExists(err error) (bool, error) {
-	if err == nil {
-		return true, nil
-	}
-	switch verror.ErrorID(err) {
-	case verror.ErrNoExist.ID:
-		return false, nil
-	case verror.ErrNoAccess.ID, verror.ErrNoExistOrNoAccess.ID:
-		return false, nil
-	default:
-		return false, err
-	}
-}
diff --git a/services/syncbase/server/watchlog_test.go b/services/syncbase/server/watchlog_test.go
index 8d0bae6..ed5f76c 100644
--- a/services/syncbase/server/watchlog_test.go
+++ b/services/syncbase/server/watchlog_test.go
@@ -55,14 +55,19 @@
 	ctx, shutdown := test.V23Init()
 	defer shutdown()
 	ctx, _ = v23.WithPrincipal(ctx, testutil.NewPrincipal("root"))
-	// Mock the service, store, db, collection.
+	// Mock create the service, db, collection.
 	clk := vclock.NewVClockForTests(nil)
 	st, _ := watchable.Wrap(memstore.New(), clk, &watchable.Options{
 		ManagedPrefixes: []string{common.RowPrefix, common.CollectionPermsPrefix},
 	})
-	db := &database{id: wire.Id{Blessing: "a", Name: "d"}, st: st}
+	store.Put(ctx, st, common.ServicePrefix, &ServiceData{
+		Perms: access.Permissions{}.Add("root", access.TagStrings(access.AllTypicalTags()...)...),
+	})
+	db := &database{id: wire.Id{Blessing: "a", Name: "d"}, exists: true, st: st}
+	store.Put(ctx, st, db.stKey(), &DatabaseData{
+		Perms: access.Permissions{}.Add("root", access.TagStrings(wire.AllDatabaseTags...)...),
+	})
 	c := &collectionReq{id: wire.Id{Blessing: "u", Name: "c"}, d: db}
-	// Mock create the collection.
 	perms := access.Permissions{}.Add("root", access.TagStrings(wire.AllCollectionTags...)...)
 	storedPerms := interfaces.CollectionPerms(perms)
 	store.Put(ctx, st, c.permsKey(), &storedPerms)
diff --git a/services/syncbase/testutil/layer.go b/services/syncbase/testutil/layer.go
index 1092547..1e846b8 100644
--- a/services/syncbase/testutil/layer.go
+++ b/services/syncbase/testutil/layer.go
@@ -39,9 +39,7 @@
 	}
 
 	assertExists(t, ctx, self, "self", false)
-	// TODO(ivanpi): Exists on child when parent does not exist currently fails
-	// with an error instead of returning false.
-	// assertExists(t, ctx, child, "child", false)
+	assertExists(t, ctx, child, "child", false)
 
 	// Create self.
 	if err := self.Create(ctx, nil); err != nil {
@@ -79,9 +77,7 @@
 		t.Errorf("Perms do not match: got %v, want %v", gotPerms, wantPerms)
 	}
 
-	// Even though self2 exists, Exists returns false because Read access is
-	// needed.
-	assertExists(t, ctx, self2, "self2", false)
+	assertExists(t, ctx, self2, "self2", true)
 
 	// Test that create fails if the parent perms disallow access.
 	perms = DefaultPerms(parent.AllowedTags(), "root:o:app:client")
@@ -153,9 +149,7 @@
 	}
 
 	assertExists(t, ctx, self, "self", false)
-	// TODO(ivanpi): Exists on child when parent does not exist currently fails
-	// with an error instead of returning false.
-	// assertExists(t, ctx, child, "child", false)
+	assertExists(t, ctx, child, "child", false)
 
 	// self.Create should succeed, since self was destroyed.
 	if err := self.Create(ctx, nil); err != nil {
@@ -207,9 +201,7 @@
 	}
 
 	assertExists(t, ctx, self, "self", false)
-	// TODO(ivanpi): Reenable when Exists() is fixed to treat nonexistent parent
-	// same as nonexistent self.
-	//assertExists(t, ctx, child, "child", false)
+	assertExists(t, ctx, child, "child", false)
 
 	// Test that destroy is idempotent.
 	if err := self.Destroy(ctx); err != nil {