diff --git a/services/syncbase/common/access_util.go b/services/syncbase/common/access_util.go
index 8674303..ba45d55 100644
--- a/services/syncbase/common/access_util.go
+++ b/services/syncbase/common/access_util.go
@@ -188,7 +188,7 @@
 // appropriate; if the caller is not authorized for exist access,
 // ErrNoExistOrNoAccess is always returned.
 func ExistAuthStep(ctx *context.T, call rpc.ServerCall, name string, parentPerms access.Permissions, v PermserData, getErr error) error {
-	if getErr != nil {
+	if getErr != nil || v == nil {
 		if verror.ErrorID(getErr) == verror.ErrNoExist.ID {
 			getErr = verror.New(verror.ErrNoExist, ctx, name)
 		}
diff --git a/services/syncbase/server/collection.go b/services/syncbase/server/collection.go
index 5e27d1f..a4251a4 100644
--- a/services/syncbase/server/collection.go
+++ b/services/syncbase/server/collection.go
@@ -50,6 +50,8 @@
 			return err
 		}
 		// Check for "collection already exists".
+		// Note, since the caller has been verified to have Write perm on database,
+		// they are allowed to know that the collection exists.
 		if err := store.Get(ctx, tx, c.permsKey(), &interfaces.CollectionPerms{}); verror.ErrorID(err) != verror.ErrNoExist.ID {
 			if err != nil {
 				return err
@@ -64,7 +66,7 @@
 		storedPerms := interfaces.CollectionPerms(perms)
 		return store.Put(ctx, tx, c.permsKey(), &storedPerms)
 	}
-	return c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 // TODO(ivanpi): Decouple collection key prefix from collection id to allow
@@ -86,7 +88,9 @@
 		}
 		if authErr != nil {
 			if verror.ErrorID(authErr) == verror.ErrNoExist.ID {
-				return nil // delete is idempotent
+				// Destroy is idempotent. Note, this doesn't leak Collection existence
+				// before the call.
+				return nil
 			}
 			return authErr
 		}
@@ -113,7 +117,7 @@
 		// Delete CollectionPerms.
 		return store.Delete(ctx, tx, c.permsKey())
 	}
-	return c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 func (c *collectionReq) Exists(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (bool, error) {
@@ -121,7 +125,7 @@
 		_, _, err := c.GetDataWithExistAuth(ctx, call, sntx, &interfaces.CollectionPerms{})
 		return err
 	}
-	return common.ErrorToExists(c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl))
+	return common.ErrorToExists(c.d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl))
 }
 
 func (c *collectionReq) GetPermissions(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (access.Permissions, error) {
@@ -132,7 +136,7 @@
 		perms, err = common.GetPermsWithAuth(ctx, call, c, allowGetPermissions, sntx)
 		return err
 	}
-	if err := c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl); err != nil {
+	if err := c.d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl); err != nil {
 		return nil, err
 	}
 	return perms, nil
@@ -154,7 +158,7 @@
 		storedPerms := interfaces.CollectionPerms(newPerms)
 		return store.Put(ctx, tx, c.permsKey(), &storedPerms)
 	}
-	return c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 func (c *collectionReq) DeleteRange(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle, start, limit []byte) error {
@@ -182,7 +186,7 @@
 		}
 		return nil
 	}
-	return c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 func (c *collectionReq) Scan(ctx *context.T, call wire.CollectionScanServerCall, bh wire.BatchHandle, start, limit []byte) error {
@@ -217,7 +221,7 @@
 		}
 		return nil
 	}
-	return c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl)
+	return c.d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl)
 }
 
 func (c *collectionReq) GlobChildren__(ctx *context.T, call rpc.GlobChildrenServerCall, matcher *glob.Element) error {
@@ -230,7 +234,7 @@
 		}
 		return util.GlobChildren(ctx, call, matcher, sntx, common.JoinKeyParts(common.RowPrefix, c.stKeyPart()))
 	}
-	return c.d.runWithNewSnapshot(ctx, impl)
+	return c.d.runWithNewSnapshot(ctx, call, impl)
 }
 
 ////////////////////////////////////////
diff --git a/services/syncbase/server/database.go b/services/syncbase/server/database.go
index b4974dd..4333b76 100644
--- a/services/syncbase/server/database.go
+++ b/services/syncbase/server/database.go
@@ -228,18 +228,12 @@
 // RPC methods
 
 func (d *database) Create(ctx *context.T, call rpc.ServerCall, metadata *wire.SchemaMetadata, perms access.Permissions) error {
-	// Permissions checked in d.s.createDatabase.
-	if d.exists {
-		return verror.New(verror.ErrExist, ctx, d.id)
-	}
-	// This database does not yet exist; d is just an ephemeral handle that holds
-	// {id wire.Id, s *service}. d.s.createDatabase will create a new database
-	// handle and store it in d.s.dbs[d.id].
+	// Permissions and existence checked in d.s.createDatabase.
 	return d.s.createDatabase(ctx, call, d.id, perms, metadata)
 }
 
 func (d *database) Destroy(ctx *context.T, call rpc.ServerCall) error {
-	// Permissions checked in d.s.destroyDatabase.
+	// Permissions and existence checked in d.s.destroyDatabase.
 	return d.s.destroyDatabase(ctx, call, d.id)
 }
 
@@ -248,7 +242,7 @@
 		_, _, err := d.GetDataWithExistAuth(ctx, call, sntx, &DatabaseData{})
 		return err
 	}
-	return common.ErrorToExists(d.runWithNewSnapshot(ctx, impl))
+	return common.ErrorToExists(d.runWithNewSnapshot(ctx, call, impl))
 }
 
 var rng *rand.Rand = rand.New(rand.NewSource(time.Now().UTC().UnixNano()))
@@ -257,7 +251,7 @@
 	allowBeginBatch := wire.AllDatabaseTags
 
 	if !d.exists {
-		return "", verror.New(verror.ErrNoExist, ctx, d.id)
+		return "", d.fuzzyNoExistError(ctx, call)
 	}
 	if _, err := common.GetPermsWithAuth(ctx, call, d, allowBeginBatch, d.st); err != nil {
 		return "", err
@@ -288,17 +282,17 @@
 func (d *database) Commit(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) error {
 	allowCommit := wire.AllDatabaseTags
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	if bh == "" {
 		return wire.NewErrNotBoundToBatch(ctx)
 	}
-	if _, err := common.GetPermsWithAuth(ctx, call, d, allowCommit, d.st); err != nil {
+	if !d.exists {
+		return d.fuzzyNoExistError(ctx, call)
+	}
+	_, ts, batchId, err := d.batchLookupInternal(ctx, call, bh)
+	if err != nil {
 		return err
 	}
-	_, ts, batchId, err := d.batchLookupInternal(ctx, bh)
-	if err != nil {
+	if _, err := common.GetPermsWithAuth(ctx, call, d, allowCommit, d.st); err != nil {
 		return err
 	}
 	if ts == nil {
@@ -323,17 +317,17 @@
 func (d *database) Abort(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) error {
 	allowAbort := wire.AllDatabaseTags
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	if bh == "" {
 		return wire.NewErrNotBoundToBatch(ctx)
 	}
-	if _, err := common.GetPermsWithAuth(ctx, call, d, allowAbort, d.st); err != nil {
+	if !d.exists {
+		return d.fuzzyNoExistError(ctx, call)
+	}
+	sn, ts, batchId, err := d.batchLookupInternal(ctx, call, bh)
+	if err != nil {
 		return err
 	}
-	sn, ts, batchId, err := d.batchLookupInternal(ctx, bh)
-	if err != nil {
+	if _, err := common.GetPermsWithAuth(ctx, call, d, allowAbort, d.st); err != nil {
 		return err
 	}
 	if ts != nil {
@@ -352,7 +346,7 @@
 }
 
 func (d *database) Exec(ctx *context.T, call wire.DatabaseExecServerCall, bh wire.BatchHandle, q string, params []*vom.RawBytes) error {
-	// Permissions checked in qdb.GetTable.
+	// Permissions and existence checked in qdb.GetTable.
 	// RunInTransaction() cannot be used here because we may or may not be
 	// creating a transaction. qe.Exec must be called and the statement must be
 	// parsed before we know if a snapshot or a transaction should be created. To
@@ -372,9 +366,6 @@
 }
 
 func (d *database) execInternal(ctx *context.T, call wire.DatabaseExecServerCall, bh wire.BatchHandle, q string, params []*vom.RawBytes) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	impl := func() error {
 		db := &queryDb{
 			ctx:  ctx,
@@ -435,21 +426,20 @@
 }
 
 func (d *database) SetPermissions(ctx *context.T, call rpc.ServerCall, perms access.Permissions, version string) error {
-	// Permissions checked in d.setPermsInternal.
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
+	// Permissions checked in d.setPermsInternal, existence in d.s.setDatabasePerms.
 	return d.s.setDatabasePerms(ctx, call, d.id, perms, version)
 }
 
 func (d *database) GetPermissions(ctx *context.T, call rpc.ServerCall) (perms access.Permissions, version string, err error) {
 	allowGetPermissions := []access.Tag{access.Admin}
 
-	if !d.exists {
-		return nil, "", verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	var data DatabaseData
-	if _, err := common.GetDataWithAuth(ctx, call, d, allowGetPermissions, d.st, &data); err != nil {
+	impl := func(sntx store.SnapshotOrTransaction) error {
+		// Check perms.
+		_, err := common.GetDataWithAuth(ctx, call, d, allowGetPermissions, d.st, &data)
+		return err
+	}
+	if err := d.runWithNewSnapshot(ctx, call, impl); err != nil {
 		return nil, "", err
 	}
 	return data.Perms, util.FormatVersion(data.Version), nil
@@ -458,9 +448,6 @@
 func (d *database) GlobChildren__(ctx *context.T, call rpc.GlobChildrenServerCall, matcher *glob.Element) error {
 	allowGlob := []access.Tag{access.Read}
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	impl := func(sntx store.SnapshotOrTransaction) error {
 		// Check perms.
 		if _, err := common.GetPermsWithAuth(ctx, call, d, allowGlob, sntx); err != nil {
@@ -468,7 +455,7 @@
 		}
 		return util.GlobChildren(ctx, call, matcher, sntx, common.CollectionPermsPrefix)
 	}
-	return store.RunWithSnapshot(d.st, impl)
+	return d.runWithNewSnapshot(ctx, call, impl)
 }
 
 // See comment in v.io/v23/services/syncbase/service.vdl for why we can't
@@ -476,9 +463,6 @@
 func (d *database) ListCollections(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) ([]wire.Id, error) {
 	allowListCollections := []access.Tag{access.Read}
 
-	if !d.exists {
-		return nil, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	var res []wire.Id
 	impl := func(sntx store.SnapshotOrTransaction) error {
 		// Check perms.
@@ -501,7 +485,7 @@
 		}
 		return nil
 	}
-	if err := d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl); err != nil {
+	if err := d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl); err != nil {
 		return nil, err
 	}
 	return res, nil
@@ -510,10 +494,7 @@
 func (d *database) PauseSync(ctx *context.T, call rpc.ServerCall) error {
 	allowPauseSync := []access.Tag{access.Admin}
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
-	return d.runInTransaction(func(ts *transactionState) error {
+	return d.runInNewTransaction(ctx, call, func(ts *transactionState) error {
 		// Check perms.
 		if _, err := common.GetPermsWithAuth(ctx, call, d, allowPauseSync, ts.tx); err != nil {
 			return err
@@ -525,10 +506,7 @@
 func (d *database) ResumeSync(ctx *context.T, call rpc.ServerCall) error {
 	allowResumeSync := []access.Tag{access.Admin}
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
-	return d.runInTransaction(func(ts *transactionState) error {
+	return d.runInNewTransaction(ctx, call, func(ts *transactionState) error {
 		// Check perms.
 		if _, err := common.GetPermsWithAuth(ctx, call, d, allowResumeSync, ts.tx); err != nil {
 			return err
@@ -547,6 +525,13 @@
 	return d.st
 }
 
+func (d *database) CheckExists(ctx *context.T, call rpc.ServerCall) error {
+	if !d.exists {
+		return d.fuzzyNoExistError(ctx, call)
+	}
+	return nil
+}
+
 func (d *database) Service() interfaces.Service {
 	return d.s
 }
@@ -624,7 +609,7 @@
 			// We are in a batch (could be snapshot or transaction)
 			// and Write access is required.  Attempt to get a
 			// transaction from the request.
-			qt.qdb.ts, err = qt.qdb.d.batchTransaction(qt.qdb.GetContext(), qt.qdb.bh)
+			qt.qdb.ts, err = qt.qdb.d.batchTransaction(qt.qdb.GetContext(), qt.qdb.call, qt.qdb.bh)
 			if err != nil {
 				if verror.ErrorID(err) == wire.ErrReadOnlyBatch.ID {
 					// We are in a snapshot batch, write access cannot be provided.
@@ -635,7 +620,7 @@
 			}
 			qt.qdb.sntx = qt.qdb.ts.tx
 		} else {
-			qt.qdb.sntx, err = qt.qdb.d.batchReader(qt.qdb.GetContext(), qt.qdb.bh)
+			qt.qdb.sntx, err = qt.qdb.d.batchReader(qt.qdb.GetContext(), qt.qdb.call, qt.qdb.bh)
 			if err != nil {
 				return nil, err
 			}
@@ -643,6 +628,9 @@
 	} else {
 		// Now that we know if write access is required, create a snapshot
 		// or transaction.
+		if !qt.qdb.d.exists {
+			return nil, qt.qdb.d.fuzzyNoExistError(qt.qdb.ctx, qt.qdb.call)
+		}
 		if !writeAccessReq {
 			qt.qdb.sntx = qt.qdb.d.st.NewSnapshot()
 		} else { // writeAccessReq
@@ -811,13 +799,21 @@
 	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) fuzzyNoExistError(ctx *context.T, call rpc.ServerCall) error {
+	_, _, err := d.GetDataWithExistAuth(ctx, call, nil, &DatabaseData{})
+	return err
 }
 
-func (d *database) runWithExistingBatchOrNewSnapshot(ctx *context.T, bh wire.BatchHandle, fn func(sntx store.SnapshotOrTransaction) error) error {
+// Note, the following methods (using batchLookupInternal) handle database
+// existence checks without leaking existence information.
+
+func (d *database) runWithNewSnapshot(ctx *context.T, call rpc.ServerCall, fn func(sntx store.SnapshotOrTransaction) error) error {
+	return d.runWithExistingBatchOrNewSnapshot(ctx, call, "", fn)
+}
+
+func (d *database) runWithExistingBatchOrNewSnapshot(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle, fn func(sntx store.SnapshotOrTransaction) error) error {
 	if bh != "" {
-		if sntx, err := d.batchReader(ctx, bh); err != nil {
+		if sntx, err := d.batchReader(ctx, call, bh); err != nil {
 			// Batch does not exist.
 			return err
 		} else {
@@ -825,16 +821,22 @@
 		}
 	} else {
 		if !d.exists {
-			// TODO(ivanpi): Return fuzzy error if appropriate.
-			return verror.New(verror.ErrNoExist, ctx, d.id)
+			return d.fuzzyNoExistError(ctx, call)
 		}
+		// Note, prevention of errors leaking existence information relies on the
+		// fact that RunWithSnapshot cannot fail before it calls fn (and therefore
+		// checks access) at least once.
 		return store.RunWithSnapshot(d.st, fn)
 	}
 }
 
-func (d *database) runInExistingBatchOrNewTransaction(ctx *context.T, bh wire.BatchHandle, fn func(ts *transactionState) error) error {
+func (d *database) runInNewTransaction(ctx *context.T, call rpc.ServerCall, fn func(ts *transactionState) error) error {
+	return d.runInExistingBatchOrNewTransaction(ctx, call, "", fn)
+}
+
+func (d *database) runInExistingBatchOrNewTransaction(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle, fn func(ts *transactionState) error) error {
 	if bh != "" {
-		if batch, err := d.batchTransaction(ctx, bh); err != nil {
+		if batch, err := d.batchTransaction(ctx, call, bh); err != nil {
 			// Batch does not exist or is readonly (snapshot).
 			return err
 		} else {
@@ -842,15 +844,17 @@
 		}
 	} else {
 		if !d.exists {
-			// TODO(ivanpi): Return fuzzy error if appropriate.
-			return verror.New(verror.ErrNoExist, ctx, d.id)
+			return d.fuzzyNoExistError(ctx, call)
 		}
+		// Note, prevention of errors leaking existence information relies on the
+		// fact that runInTransaction cannot fail before it calls fn (and therefore
+		// checks access) at least once.
 		return d.runInTransaction(fn)
 	}
 }
 
-func (d *database) batchReader(ctx *context.T, bh wire.BatchHandle) (store.SnapshotOrTransaction, error) {
-	sn, ts, _, err := d.batchLookupInternal(ctx, bh)
+func (d *database) batchReader(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (store.SnapshotOrTransaction, error) {
+	sn, ts, _, err := d.batchLookupInternal(ctx, call, bh)
 	if err != nil {
 		return nil, err
 	}
@@ -860,8 +864,8 @@
 	return ts.tx, nil
 }
 
-func (d *database) batchTransaction(ctx *context.T, bh wire.BatchHandle) (*transactionState, error) {
-	sn, ts, _, err := d.batchLookupInternal(ctx, bh)
+func (d *database) batchTransaction(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (*transactionState, error) {
+	sn, ts, _, err := d.batchLookupInternal(ctx, call, bh)
 	if err != nil {
 		return nil, err
 	}
@@ -874,7 +878,9 @@
 // batchLookupInternal parses the batch handle and retrieves the corresponding
 // snapshot or transaction. It returns an error if the handle is malformed or
 // the batch does not exist. Otherwise, exactly one of sn and ts will be != nil.
-func (d *database) batchLookupInternal(ctx *context.T, bh wire.BatchHandle) (sn store.Snapshot, ts *transactionState, batchId uint64, _ error) {
+// If a non-nil error is returned, it will not leak database existence if the
+// caller is not authorized to know it.
+func (d *database) batchLookupInternal(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (sn store.Snapshot, ts *transactionState, batchId uint64, _ error) {
 	if bh == "" {
 		return nil, nil, 0, verror.New(verror.ErrInternal, ctx, "batch lookup for empty handle")
 	}
@@ -883,8 +889,7 @@
 		return nil, nil, 0, err
 	}
 	if !d.exists {
-		// TODO(ivanpi): Return fuzzy error if appropriate.
-		return nil, nil, 0, verror.New(verror.ErrNoExist, ctx, d.id)
+		return nil, nil, 0, d.fuzzyNoExistError(ctx, call)
 	}
 	d.mu.Lock()
 	defer d.mu.Unlock()
@@ -896,7 +901,11 @@
 		ts, found = d.txs[bId]
 	}
 	if !found {
-		return nil, nil, bId, wire.NewErrUnknownBatch(ctx)
+		_, _, err := d.GetDataWithExistAuth(ctx, call, d.st, &DatabaseData{})
+		if err == nil {
+			return nil, nil, bId, wire.NewErrUnknownBatch(ctx)
+		}
+		return nil, nil, bId, err
 	}
 	return sn, ts, bId, nil
 }
diff --git a/services/syncbase/server/database_bm.go b/services/syncbase/server/database_bm.go
index 97338fb..9369d0c 100644
--- a/services/syncbase/server/database_bm.go
+++ b/services/syncbase/server/database_bm.go
@@ -8,92 +8,60 @@
 	"v.io/v23/context"
 	"v.io/v23/rpc"
 	wire "v.io/v23/services/syncbase"
-	"v.io/v23/verror"
 	"v.io/x/ref/services/syncbase/vsync"
 )
 
 ////////////////////////////////////////////////////////////////////////////////
 // RPCs for managing blobs between Syncbase and its clients.
 
-// Note, access authorization is checked in SyncDatabase methods.
-// TODO(ivanpi): Move d.exists checks into SyncDatabase to prevent existence leaks.
+// Note, existence and access authorization is checked in SyncDatabase methods.
 
 func (d *database) CreateBlob(ctx *context.T, call rpc.ServerCall) (wire.BlobRef, error) {
-	if !d.exists {
-		return wire.NullBlobRef, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.CreateBlob(ctx, call)
 }
 
 func (d *database) PutBlob(ctx *context.T, call wire.BlobManagerPutBlobServerCall, br wire.BlobRef) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.PutBlob(ctx, call, br)
 }
 
 func (d *database) CommitBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.CommitBlob(ctx, call, br)
 }
 
 func (d *database) GetBlobSize(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) (int64, error) {
-	if !d.exists {
-		return 0, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.GetBlobSize(ctx, call, br)
 }
 
 func (d *database) DeleteBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.DeleteBlob(ctx, call, br)
 }
 
 func (d *database) GetBlob(ctx *context.T, call wire.BlobManagerGetBlobServerCall, br wire.BlobRef, offset int64) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.GetBlob(ctx, call, br, offset)
 }
 
 func (d *database) FetchBlob(ctx *context.T, call wire.BlobManagerFetchBlobServerCall, br wire.BlobRef, priority uint64) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.FetchBlob(ctx, call, br, priority)
 }
 
 func (d *database) PinBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.PinBlob(ctx, call, br)
 }
 
 func (d *database) UnpinBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.UnpinBlob(ctx, call, br)
 }
 
 func (d *database) KeepBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef, rank uint64) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.KeepBlob(ctx, call, br, rank)
 }
diff --git a/services/syncbase/server/database_crm.go b/services/syncbase/server/database_crm.go
index d3c4d19..a98df8b 100644
--- a/services/syncbase/server/database_crm.go
+++ b/services/syncbase/server/database_crm.go
@@ -8,7 +8,6 @@
 	"v.io/v23/context"
 	"v.io/v23/security/access"
 	wire "v.io/v23/services/syncbase"
-	"v.io/v23/verror"
 	"v.io/x/lib/vlog"
 	"v.io/x/ref/services/syncbase/common"
 )
@@ -20,7 +19,7 @@
 	allowStartConflictResolver := []access.Tag{access.Admin}
 
 	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
+		return d.fuzzyNoExistError(ctx, call)
 	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, d, allowStartConflictResolver, d.st); err != nil {
diff --git a/services/syncbase/server/database_sgm.go b/services/syncbase/server/database_sgm.go
index 07a5ca0..458fb73 100644
--- a/services/syncbase/server/database_sgm.go
+++ b/services/syncbase/server/database_sgm.go
@@ -8,84 +8,55 @@
 	"v.io/v23/context"
 	"v.io/v23/rpc"
 	wire "v.io/v23/services/syncbase"
-	"v.io/v23/verror"
 	"v.io/x/ref/services/syncbase/vsync"
 )
 
 ////////////////////////////////////////
 // Syncgroup RPC methods
 
-// Note, access authorization is checked in SyncDatabase methods.
-// TODO(ivanpi): Move d.exists checks into SyncDatabase to prevent existence leaks.
+// Note, existence and access authorization is checked in SyncDatabase methods.
 
 func (d *database) ListSyncgroups(ctx *context.T, call rpc.ServerCall) ([]wire.Id, error) {
-	if !d.exists {
-		return nil, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.ListSyncgroups(ctx, call)
 }
 
 func (d *database) CreateSyncgroup(ctx *context.T, call rpc.ServerCall, sgId wire.Id, spec wire.SyncgroupSpec, myInfo wire.SyncgroupMemberInfo) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.CreateSyncgroup(ctx, call, sgId, spec, myInfo)
 }
 
 func (d *database) JoinSyncgroup(ctx *context.T, call rpc.ServerCall, remoteSyncbaseName string, expectedSyncbaseBlessings []string, sgId wire.Id, myInfo wire.SyncgroupMemberInfo) (wire.SyncgroupSpec, error) {
-	if !d.exists {
-		return wire.SyncgroupSpec{}, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.JoinSyncgroup(ctx, call, remoteSyncbaseName, expectedSyncbaseBlessings, sgId, myInfo)
 }
 
 func (d *database) LeaveSyncgroup(ctx *context.T, call rpc.ServerCall, sgId wire.Id) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.LeaveSyncgroup(ctx, call, sgId)
 }
 
 func (d *database) DestroySyncgroup(ctx *context.T, call rpc.ServerCall, sgId wire.Id) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.DestroySyncgroup(ctx, call, sgId)
 }
 
 func (d *database) EjectFromSyncgroup(ctx *context.T, call rpc.ServerCall, sgId wire.Id, member string) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.EjectFromSyncgroup(ctx, call, sgId, member)
 }
 
 func (d *database) GetSyncgroupSpec(ctx *context.T, call rpc.ServerCall, sgId wire.Id) (wire.SyncgroupSpec, string, error) {
-	if !d.exists {
-		return wire.SyncgroupSpec{}, "", verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.GetSyncgroupSpec(ctx, call, sgId)
 }
 
 func (d *database) SetSyncgroupSpec(ctx *context.T, call rpc.ServerCall, sgId wire.Id, spec wire.SyncgroupSpec, version string) error {
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.SetSyncgroupSpec(ctx, call, sgId, spec, version)
 }
 
 func (d *database) GetSyncgroupMembers(ctx *context.T, call rpc.ServerCall, sgId wire.Id) (map[string]wire.SyncgroupMemberInfo, error) {
-	if !d.exists {
-		return nil, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	sd := vsync.NewSyncDatabase(d)
 	return sd.GetSyncgroupMembers(ctx, call, sgId)
 }
diff --git a/services/syncbase/server/database_sm.go b/services/syncbase/server/database_sm.go
index 2319680..bb616eb 100644
--- a/services/syncbase/server/database_sm.go
+++ b/services/syncbase/server/database_sm.go
@@ -24,12 +24,13 @@
 func (d *database) GetSchemaMetadata(ctx *context.T, call rpc.ServerCall) (wire.SchemaMetadata, error) {
 	allowGetSchemaMetadata := []access.Tag{access.Read}
 
-	if !d.exists {
-		return wire.SchemaMetadata{}, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	// Check permissions on Database and retrieve schema metadata.
 	var dbData DatabaseData
-	if _, err := common.GetDataWithAuth(ctx, call, d, allowGetSchemaMetadata, d.st, &dbData); err != nil {
+	impl := func(sntx store.SnapshotOrTransaction) error {
+		_, err := common.GetDataWithAuth(ctx, call, d, allowGetSchemaMetadata, d.st, &dbData)
+		return err
+	}
+	if err := d.runWithNewSnapshot(ctx, call, impl); err != nil {
 		return wire.SchemaMetadata{}, err
 	}
 	if dbData.SchemaMetadata == nil {
@@ -41,11 +42,9 @@
 func (d *database) SetSchemaMetadata(ctx *context.T, call rpc.ServerCall, metadata wire.SchemaMetadata) error {
 	allowSetSchemaMetadata := []access.Tag{access.Admin}
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	// Check permissions on Database and store schema metadata.
-	return store.RunInTransaction(d.st, func(tx store.Transaction) error {
+	return d.runInNewTransaction(ctx, call, func(ts *transactionState) error {
+		tx := ts.tx
 		var dbData DatabaseData
 		if _, err := common.GetDataWithAuth(ctx, call, d, allowSetSchemaMetadata, tx, &dbData); err != nil {
 			return err
diff --git a/services/syncbase/server/database_watch.go b/services/syncbase/server/database_watch.go
index b7f88aa..cadf468 100644
--- a/services/syncbase/server/database_watch.go
+++ b/services/syncbase/server/database_watch.go
@@ -27,9 +27,6 @@
 func (d *database) GetResumeMarker(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (watch.ResumeMarker, error) {
 	allowGetResumeMarker := wire.AllDatabaseTags
 
-	if !d.exists {
-		return nil, verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	var res watch.ResumeMarker
 	impl := func(sntx store.SnapshotOrTransaction) (err error) {
 		// Check permissions on Database.
@@ -39,7 +36,7 @@
 		res, err = watchable.GetResumeMarker(sntx)
 		return err
 	}
-	if err := d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl); err != nil {
+	if err := d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl); err != nil {
 		return nil, err
 	}
 	return res, nil
@@ -76,9 +73,6 @@
 func (d *database) watchWithFilter(ctx *context.T, call rpc.ServerCall, sender *watchBatchSender, resumeMarker watch.ResumeMarker, watchFilter filter.CollectionRowFilter) error {
 	allowWatchDbStart := []access.Tag{access.Read}
 
-	if !d.exists {
-		return verror.New(verror.ErrNoExist, ctx, d.id)
-	}
 	initImpl := func(sntx store.SnapshotOrTransaction) error {
 		// Check permissions on Database.
 		if _, err := common.GetPermsWithAuth(ctx, call, d, allowWatchDbStart, sntx); err != nil {
@@ -115,7 +109,7 @@
 		// Finalize initial state or root update batch.
 		return sender.finishBatch(resumeMarker)
 	}
-	if err := store.RunWithSnapshot(d.st, initImpl); err != nil {
+	if err := d.runWithNewSnapshot(ctx, call, initImpl); err != nil {
 		return err
 	}
 	return d.watchUpdates(ctx, call, sender, resumeMarker, watchFilter)
diff --git a/services/syncbase/server/dispatcher.go b/services/syncbase/server/dispatcher.go
index cd0f0f2..7657380 100644
--- a/services/syncbase/server/dispatcher.go
+++ b/services/syncbase/server/dispatcher.go
@@ -89,10 +89,7 @@
 		} else {
 			// Database does not exist. Create a short-lived database object to
 			// service this request.
-			d = &database{
-				id: dbId,
-				s:  disp.s,
-			}
+			d = disp.s.nonexistentDatabaseHandle(dbId)
 		}
 	}
 
diff --git a/services/syncbase/server/interfaces/database.go b/services/syncbase/server/interfaces/database.go
index 69326a4..48c9e44 100644
--- a/services/syncbase/server/interfaces/database.go
+++ b/services/syncbase/server/interfaces/database.go
@@ -6,6 +6,7 @@
 
 import (
 	"v.io/v23/context"
+	"v.io/v23/rpc"
 	"v.io/v23/security/access"
 	wire "v.io/v23/services/syncbase"
 	"v.io/x/ref/services/syncbase/common"
@@ -21,6 +22,10 @@
 	// St returns the storage engine instance for this database.
 	St() *watchable.Store
 
+	// CheckExists returns an error if this database does not exist, transformed
+	// to prevent leaking existence information if the client has no access to it.
+	CheckExists(ctx *context.T, call rpc.ServerCall) error
+
 	// Service returns the service handle for this database.
 	Service() Service
 
diff --git a/services/syncbase/server/row.go b/services/syncbase/server/row.go
index e489673..dad14c8 100644
--- a/services/syncbase/server/row.go
+++ b/services/syncbase/server/row.go
@@ -28,15 +28,16 @@
 // RPC methods
 
 func (r *rowReq) Exists(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (bool, error) {
-	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 {
+		cxPerms, err := common.GetPermsWithExistAndParentResolveAuth(ctx, call, r.c, sntx)
+		if err != nil {
 			return err
 		}
-		return store.Get(ctx, sntx, r.stKey(), &vom.RawBytes{})
+		getErr := store.Get(ctx, sntx, r.stKey(), &vom.RawBytes{})
+		return common.ExistAuthStep(ctx, call, r.key, cxPerms, nil, getErr)
+
 	}
-	return common.ErrorToExists(r.c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl))
+	return common.ErrorToExists(r.c.d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl))
 }
 
 func (r *rowReq) Get(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) (*vom.RawBytes, error) {
@@ -46,7 +47,7 @@
 		res, err = r.get(ctx, call, sntx)
 		return err
 	}
-	if err := r.c.d.runWithExistingBatchOrNewSnapshot(ctx, bh, impl); err != nil {
+	if err := r.c.d.runWithExistingBatchOrNewSnapshot(ctx, call, bh, impl); err != nil {
 		return nil, err
 	}
 	return res, nil
@@ -57,7 +58,7 @@
 	impl := func(ts *transactionState) error {
 		return r.put(ctx, call, ts, value)
 	}
-	return r.c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return r.c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 func (r *rowReq) Delete(ctx *context.T, call rpc.ServerCall, bh wire.BatchHandle) error {
@@ -65,7 +66,7 @@
 	impl := func(ts *transactionState) error {
 		return r.delete(ctx, call, ts)
 	}
-	return r.c.d.runInExistingBatchOrNewTransaction(ctx, bh, impl)
+	return r.c.d.runInExistingBatchOrNewTransaction(ctx, call, bh, impl)
 }
 
 ////////////////////////////////////////
diff --git a/services/syncbase/server/service.go b/services/syncbase/server/service.go
index 8db90a4..7c3a42a 100644
--- a/services/syncbase/server/service.go
+++ b/services/syncbase/server/service.go
@@ -4,10 +4,6 @@
 
 package server
 
-// TODO(sadovsky): Check Resolve access on parent where applicable. Relatedly,
-// convert ErrNoExist and ErrNoAccess to ErrNoExistOrNoAccess where needed to
-// preserve privacy.
-
 import (
 	"bytes"
 	"crypto/rand"
@@ -421,6 +417,7 @@
 	defer s.mu.Unlock()
 	d, ok := s.dbs[dbId]
 	if !ok {
+		// Note, a fuzzy error should be returned to external clients instead.
 		return nil, verror.New(verror.ErrNoExist, ctx, dbId)
 	}
 	return d, nil
@@ -456,10 +453,6 @@
 	// 4. Move dbInfo from GC log into active dbs. <===== CHANGE BECOMES VISIBLE
 	s.mu.Lock()
 	defer s.mu.Unlock()
-	if _, ok := s.dbs[dbId]; ok {
-		// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
-		return verror.New(verror.ErrExist, ctx, dbId)
-	}
 
 	// 1. Check serviceData perms. Also check implicit perms if not service admin.
 	sData := &ServiceData{}
@@ -482,6 +475,13 @@
 		}
 	}
 
+	// Check if the database exists.
+	if _, ok := s.dbs[dbId]; ok {
+		// Note, since the caller has been verified to have Write perm on service,
+		// they are allowed to know that the database exists.
+		return verror.New(verror.ErrExist, ctx, dbId)
+	}
+
 	// 2. Put dbInfo record into garbage collection log, to clean up database if
 	//    remaining steps fail or syncbased crashes.
 	rootDir, err := s.rootDirForDb(ctx, dbId)
@@ -542,7 +542,8 @@
 			if err != nil {
 				return err
 			}
-			// TODO(sadovsky): Should this be ErrExistOrNoAccess, for privacy?
+			// Note, as above, since the caller has been verified to have Write perm
+			// on service, they are allowed to know that the database exists.
 			return verror.New(verror.ErrExist, ctx, dbId)
 		}
 		// Write dbInfo into active databases.
@@ -569,18 +570,37 @@
 	//    syncbased restart.
 	s.mu.Lock()
 	defer s.mu.Unlock()
-	d, ok := s.dbs[dbId]
-	if !ok {
-		return nil // destroy is idempotent
+	d, dExists := s.dbs[dbId]
+	if !dExists {
+		// Database does not exist. Use a short-lived database object for auth.
+		d = s.nonexistentDatabaseHandle(dbId)
 	}
 
 	// 1. Check serviceData and databaseData perms.
+	var authErr error
 	// Check permissions on Service.
-	if _, authErr := common.GetPermsWithAuth(ctx, call, d.s, allowDestroyDatabase, d.s.st); authErr != nil {
+	if _, authErr = common.GetPermsWithAuth(ctx, call, d.s, allowDestroyDatabase, d.s.st); authErr != nil {
 		// Caller has no Admin access on Service. Check databaseData perms.
-		if _, authErr = common.GetPermsWithAuth(ctx, call, d, allowDestroyDatabase, d.st); authErr != nil {
-			return authErr
+		if !dExists {
+			authErr = d.fuzzyNoExistError(ctx, call)
+		} else {
+			_, authErr = common.GetPermsWithAuth(ctx, call, d, allowDestroyDatabase, d.st)
 		}
+	} else {
+		// Caller has Admin access on Service. Check if Database exists.
+		if !dExists {
+			authErr = verror.New(verror.ErrNoExist, ctx, d.id.String())
+		} else {
+			authErr = nil
+		}
+	}
+	if authErr != nil {
+		if verror.ErrorID(authErr) == verror.ErrNoExist.ID {
+			// Destroy is idempotent. Note, this doesn't leak Database existence
+			// before the call.
+			return nil
+		}
+		return authErr
 	}
 
 	// 2. Move dbInfo from active dbs into GC log.
@@ -613,7 +633,9 @@
 	defer s.mu.Unlock()
 	d, ok := s.dbs[dbId]
 	if !ok {
-		return verror.New(verror.ErrNoExist, ctx, dbId)
+		// Database does not exist. Use a short-lived database object to check if
+		// the client is allowed to know it.
+		return s.nonexistentDatabaseHandle(dbId).fuzzyNoExistError(ctx, call)
 	}
 	return d.setPermsInternal(ctx, call, perms, version)
 }
@@ -648,6 +670,13 @@
 	return common.ServicePrefix
 }
 
+func (s *service) nonexistentDatabaseHandle(dbId wire.Id) *database {
+	return &database{
+		id: dbId,
+		s:  s,
+	}
+}
+
 var unsafeDirNameChars *regexp.Regexp = regexp.MustCompile("[^-a-zA-Z0-9_]")
 
 func dirNameFrom(s string) string {
diff --git a/services/syncbase/vsync/blob.go b/services/syncbase/vsync/blob.go
index 844ae53..99cd782 100644
--- a/services/syncbase/vsync/blob.go
+++ b/services/syncbase/vsync/blob.go
@@ -197,6 +197,9 @@
 	vlog.VI(2).Infof("sync: CreateBlob: begin")
 	defer vlog.VI(2).Infof("sync: CreateBlob: end")
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return wire.NullBlobRef, err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowCreateBlob, sd.db.St()); err != nil {
 		return wire.NullBlobRef, err
@@ -223,6 +226,9 @@
 	vlog.VI(2).Infof("sync: PutBlob: begin br %v", br)
 	defer vlog.VI(2).Infof("sync: PutBlob: end br %v", br)
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowPutBlob, sd.db.St()); err != nil {
 		return err
@@ -254,6 +260,9 @@
 	vlog.VI(2).Infof("sync: CommitBlob: begin br %v", br)
 	defer vlog.VI(2).Infof("sync: CommitBlob: end br %v", br)
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowCommitBlob, sd.db.St()); err != nil {
 		return err
@@ -276,6 +285,9 @@
 	vlog.VI(2).Infof("sync: GetBlobSize: begin br %v", br)
 	defer vlog.VI(2).Infof("sync: GetBlobSize: end br %v", br)
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return 0, err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowGetBlobSize, sd.db.St()); err != nil {
 		return 0, err
@@ -297,6 +309,9 @@
 func (sd *syncDatabase) DeleteBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
 	allowDeleteBlob := wire.AllDatabaseTags
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowDeleteBlob, sd.db.St()); err != nil {
 		return err
@@ -311,6 +326,9 @@
 	vlog.VI(2).Infof("sync: GetBlob: begin br %v", br)
 	defer vlog.VI(2).Infof("sync: GetBlob: end br %v", br)
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowGetBlob, sd.db.St()); err != nil {
 		return err
@@ -332,6 +350,9 @@
 	vlog.VI(2).Infof("sync: FetchBlob: begin br %v", br)
 	defer vlog.VI(2).Infof("sync: FetchBlob: end br %v", br)
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowFetchBlob, sd.db.St()); err != nil {
 		return err
@@ -365,6 +386,9 @@
 func (sd *syncDatabase) PinBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
 	allowPinBlob := []access.Tag{access.Write}
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowPinBlob, sd.db.St()); err != nil {
 		return err
@@ -376,6 +400,9 @@
 func (sd *syncDatabase) UnpinBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef) error {
 	allowUnpinBlob := wire.AllDatabaseTags
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowUnpinBlob, sd.db.St()); err != nil {
 		return err
@@ -387,6 +414,9 @@
 func (sd *syncDatabase) KeepBlob(ctx *context.T, call rpc.ServerCall, br wire.BlobRef, rank uint64) error {
 	allowKeepBlob := wire.AllDatabaseTags
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
 	// Check permissions on Database.
 	if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowKeepBlob, sd.db.St()); err != nil {
 		return err
diff --git a/services/syncbase/vsync/responder.go b/services/syncbase/vsync/responder.go
index 8d6bab7..efa6837 100644
--- a/services/syncbase/vsync/responder.go
+++ b/services/syncbase/vsync/responder.go
@@ -105,7 +105,8 @@
 //
 // In the first phase, the initiator is checked against the syncgroup ACLs of
 // all the syncgroups it is requesting, and only those prefixes that belong to
-// allowed syncgroups are carried forward.
+// allowed syncgroups are carried forward. If the database is offline, does not
+// exist, or none of the prefixes are allowed, ErrDbOffline is returned.
 //
 // In the second phase, for a given set of nested prefixes from the initiator,
 // the shortest prefix in that set is extracted. The initiator's genvector for
@@ -144,20 +145,21 @@
 		return interfaces.NewErrDbOffline(ctx, rSt.dbId)
 	}
 
-	// TODO(ivanpi): Ensure that Database and syncgroup existence is not leaked.
-
 	// Phase 1 of sendDeltas: Authorize the initiator and respond to the
 	// caller only for the syncgroups that allow access.
 	err := rSt.authorizeAndFilterSyncgroups(ctx)
 
 	// Check error from phase 1.
 	if err != nil {
-		vlog.VI(4).Infof("sync: sendDeltasPerDatabase: failed authorization, err %v", err)
-		return err
+		// Authorization failed. Return ErrDbOffline to prevent leaking existence.
+		vlog.VI(2).Infof("sync: sendDeltasPerDatabase: failed authorization, err %v", err)
+		return interfaces.NewErrDbOffline(ctx, rSt.dbId)
 	}
 
 	if len(rSt.initVecs) == 0 {
-		return verror.New(verror.ErrInternal, ctx, "empty initiator generation vectors")
+		// No authorized genvecs. Return ErrDbOffline to prevent leaking existence.
+		vlog.VI(2).Infof("sync: sendDeltasPerDatabase: empty initiator generation vectors")
+		return interfaces.NewErrDbOffline(ctx, rSt.dbId)
 	}
 
 	// Phase 2 and 3 of sendDeltas: diff contains the bound on the
diff --git a/services/syncbase/vsync/syncgroup.go b/services/syncbase/vsync/syncgroup.go
index 6bbce3a..ab20f0a 100644
--- a/services/syncbase/vsync/syncgroup.go
+++ b/services/syncbase/vsync/syncgroup.go
@@ -696,6 +696,10 @@
 		Joiners:     map[string]interfaces.SyncgroupMemberState{ss.name: sm},
 	}
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
+
 	err = watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Check permissions on Database.
 		if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowCreateSyncgroupDb, tx); err != nil {
@@ -777,6 +781,11 @@
 	var sg *interfaces.Syncgroup
 	nullSpec := wire.SyncgroupSpec{}
 	gid := SgIdToGid(sd.db.Id(), sgId)
+
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return nullSpec, err
+	}
+
 	err := watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Check permissions on Database.
 		if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowJoinSyncgroupDb, tx); err != nil {
@@ -901,6 +910,10 @@
 func (sd *syncDatabase) LeaveSyncgroup(ctx *context.T, call rpc.ServerCall, sgId wire.Id) error {
 	allowLeaveSyncgroupDb := []access.Tag{access.Write}
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
+
 	err := watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Check permissions on Database.
 		if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowLeaveSyncgroupDb, tx); err != nil {
@@ -918,6 +931,11 @@
 
 	var sg *interfaces.Syncgroup
 	gid := SgIdToGid(sd.db.Id(), sgId)
+
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
+
 	err := watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Check permissions on Database.
 		if _, err := common.GetPermsWithAuth(ctx, call, sd.db, allowDestroySyncgroupDb, tx); err != nil {
@@ -950,6 +968,10 @@
 
 	var sg interfaces.Syncgroup
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
+
 	err := watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Get the syncgroup information with auth check.
 		sgAuth := &syncgroupAuth{
@@ -993,6 +1015,10 @@
 	vlog.VI(2).Infof("sync: ListSyncgroups: begin")
 	defer vlog.VI(2).Infof("sync: ListSyncgroups: end")
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return nil, err
+	}
+
 	sn := sd.db.St().NewSnapshot()
 	defer sn.Abort()
 
@@ -1020,13 +1046,17 @@
 	vlog.VI(2).Infof("sync: GetSyncgroupSpec: begin %v", sgId)
 	defer vlog.VI(2).Infof("sync: GetSyncgroupSpec: end: %v", sgId)
 
+	var spec wire.SyncgroupSpec
+	var sg interfaces.Syncgroup
+
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return spec, "", err
+	}
+
 	sn := sd.db.St().NewSnapshot()
 	defer sn.Abort()
 
-	var spec wire.SyncgroupSpec
-
 	// Get the syncgroup information with auth check.
-	var sg interfaces.Syncgroup
 	sgAuth := &syncgroupAuth{
 		db: sd.db,
 		id: sgId,
@@ -1045,11 +1075,16 @@
 	vlog.VI(2).Infof("sync: GetSyncgroupMembers: begin %v", sgId)
 	defer vlog.VI(2).Infof("sync: GetSyncgroupMembers: end: %v", sgId)
 
+	var sg interfaces.Syncgroup
+
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return nil, err
+	}
+
 	sn := sd.db.St().NewSnapshot()
 	defer sn.Abort()
 
 	// Get the syncgroup information with auth check.
-	var sg interfaces.Syncgroup
 	sgAuth := &syncgroupAuth{
 		db: sd.db,
 		id: sgId,
@@ -1080,6 +1115,10 @@
 	gid := SgIdToGid(sd.db.Id(), sgId)
 	var sg interfaces.Syncgroup
 
+	if err := sd.db.CheckExists(ctx, call); err != nil {
+		return err
+	}
+
 	err := watchable.RunInTransaction(sd.db.St(), func(tx *watchable.Transaction) error {
 		// Get the syncgroup information with auth check.
 		sgAuth := &syncgroupAuth{
@@ -1588,25 +1627,17 @@
 
 	nullSG, nullGV := interfaces.Syncgroup{}, interfaces.GenVector{}
 
-	// TODO(ivanpi): Ensure that Database and syncgroup existence is not leaked.
-
-	// If this admin is offline, it shouldn't accept the join request since it
-	// would be unable to send out the new syncgroup updates. However, it is still
-	// possible that the admin goes offline right after processing the request.
-	if !s.isDbSyncable(ctx, dbId) {
-		return nullSG, "", nullGV, interfaces.NewErrDbOffline(ctx, dbId)
-	}
-
 	// Find the database for this syncgroup.
 	db, err := s.sv.Database(ctx, call, dbId)
 	if err != nil {
-		return nullSG, "", nullGV, verror.New(verror.ErrNoExist, ctx, "Database not found", dbId)
+		vlog.VI(4).Infof("sync: JoinSyncgroupAtAdmin: end: %v from peer %s, err in db retrieve %v", sgId, joinerName, err)
+		return nullSG, "", nullGV, verror.New(verror.ErrNoExistOrNoAccess, ctx, dbId, sgId)
 	}
 
 	gid := SgIdToGid(dbId, sgId)
 	if _, err = getSyncgroupVersion(ctx, db.St(), gid); err != nil {
 		vlog.VI(4).Infof("sync: JoinSyncgroupAtAdmin: end: %v from peer %s, err in sg search %v", sgId, joinerName, err)
-		return nullSG, "", nullGV, verror.New(verror.ErrNoExist, ctx, "Syncgroup not found", sgId)
+		return nullSG, "", nullGV, verror.New(verror.ErrNoExistOrNoAccess, ctx, dbId, sgId)
 	}
 
 	version := s.newSyncgroupVersion()
@@ -1618,7 +1649,13 @@
 		var err error
 		sg, err = getSyncgroupByGid(ctx, tx, gid)
 		if err != nil {
-			return err
+			return verror.New(verror.ErrNoExistOrNoAccess, ctx, dbId, sgId)
+		}
+
+		// Check SG ACL. Caller must have Read access on the syncgroup
+		// ACL to join a syncgroup.
+		if err := common.TagAuthorizer(access.Read, sg.Spec.Perms).Authorize(ctx, call.Security()); err != nil {
+			return verror.New(verror.ErrNoExistOrNoAccess, ctx, dbId, sgId)
 		}
 
 		// Check SG ACL to see if this node is still a valid admin.
@@ -1626,10 +1663,11 @@
 			return interfaces.NewErrNotAdmin(ctx)
 		}
 
-		// Check SG ACL. Caller must have Read access on the syncgroup
-		// ACL to join a syncgroup.
-		if err := common.TagAuthorizer(access.Read, sg.Spec.Perms).Authorize(ctx, call.Security()); err != nil {
-			return err
+		// If this admin is offline, it shouldn't accept the join request since it
+		// would be unable to send out the new syncgroup updates. However, it is still
+		// possible that the admin goes offline right after processing the request.
+		if !s.isDbSyncable(ctx, dbId) {
+			return interfaces.NewErrDbOffline(ctx, dbId)
 		}
 
 		// Check that the SG is not in pending state.
diff --git a/services/syncbase/vsync/testutil_test.go b/services/syncbase/vsync/testutil_test.go
index 442811f..8ab18c5 100644
--- a/services/syncbase/vsync/testutil_test.go
+++ b/services/syncbase/vsync/testutil_test.go
@@ -93,6 +93,10 @@
 	return d.st
 }
 
+func (d *mockDatabase) CheckExists(ctx *context.T, call rpc.ServerCall) error {
+	return nil
+}
+
 func (d *mockDatabase) GetCollectionPerms(ctx *context.T, cxId wire.Id, st store.StoreReader) (access.Permissions, error) {
 	return nil, verror.NewErrNotImplemented(ctx)
 }