g10: Cache the effective policy. Recompute it when required.

* g10/tofu.c (initdb): Add column effective_policy to the bindings
table.
(record_binding): New parameters effective_policy and set_conflict.
Save the effective policy.  If SET_CONFLICT is set, then set conflict
according to CONFLICT.  Otherwise, preserve the current value of
conflict.  Update callers.
(get_trust): Don't compute the effective policy here...
(get_policy): ... do it here, if it was not cached.  Take new
parameters, PK, the public key, and NOW, the time that the operation
started.  Update callers.
(show_statistics): New parameter PK.  Pass it to get_policy.  Update
callers.
(tofu_notice_key_changed): New function.
* g10/gpgv.c (tofu_notice_key_changed): New stub.
* g10/import.c (import_revoke_cert): Take additional argument CTRL.
Pass it to keydb_update_keyblock.
* g10/keydb.c (keydb_update_keyblock): Take additional argument CTRL.
Update callers.
[USE_TOFU]: Call tofu_notice_key_changed.
* g10/test-stubs.c (tofu_notice_key_changed): New stub.
* tests/openpgp/tofu.scm: Assume that manually setting a binding's
policy to auto does not cause the tofu engine to forget about any
conflict.

--
Signed-off-by: Neal H. Walfield <neal@g10code.com>

We now store the computed policy in the tofu DB (in the
effective_policy column of the bindings table) to avoid computing it
every time, which is expensive.  Further, policy is never overridden
in case of a conflict.  Instead, we detect a conflict if CONFLICT is
not empty.

This change is backwards compatible to existing DBs.  The only minor
incompatibility is that unresolved conflicts won't be automatically
resolved in case we import a direct signature, or cross signatures.

8 files changed, 527 insertions, 351 deletions

diff --git a/g10/gpgv.c b/g10/gpgv.c
index d9f2898d7..da07989ea 100644
--- a/g10/gpgv.c
+++ b/g10/gpgv.c
@@ -713,3 +713,12 @@ tofu_end_batch_update (ctrl_t ctrl)
 {
   (void)ctrl;
 }
+
+gpg_error_t
+tofu_notice_key_changed (ctrl_t ctrl, kbnode_t kb)
+{
+  (void) ctrl;
+  (void) kb;
+
+  return 0;
+}
diff --git a/g10/import.c b/g10/import.c
index 590959d25..1ed11bf38 100644
--- a/g10/import.c
+++ b/g10/import.c
@@ -111,7 +111,8 @@ static int import_secret_one (ctrl_t ctrl, kbnode_t keyblock,
                               struct import_stats_s *stats, int batch,
                               unsigned int options, int for_migration,
                               import_screener_t screener, void *screener_arg);
-static int import_revoke_cert (kbnode_t node, struct import_stats_s *stats);
+static int import_revoke_cert (ctrl_t ctrl,
+                               kbnode_t node, struct import_stats_s *stats);
 static int chk_self_sigs (kbnode_t keyblock, u32 *keyid, int *non_self);
 static int delete_inv_parts (kbnode_t keyblock,
                              u32 *keyid, unsigned int options);
@@ -562,7 +563,7 @@ import (ctrl_t ctrl, IOBUF inp, const char* fname,struct import_stats_s *stats,
                                 screener, screener_arg);
       else if (keyblock->pkt->pkttype == PKT_SIGNATURE
                && keyblock->pkt->pkt.signature->sig_class == 0x20 )
-        rc = import_revoke_cert (keyblock, stats);
+        rc = import_revoke_cert (ctrl, keyblock, stats);
       else
         {
           log_info (_("skipping block of type %d\n"), keyblock->pkt->pkttype);
@@ -1642,7 +1643,7 @@ import_one (ctrl_t ctrl,
         {
           mod_key = 1;
           /* KEYBLOCK_ORIG has been updated; write */
-          rc = keydb_update_keyblock (hd, keyblock_orig);
+          rc = keydb_update_keyblock (ctrl, hd, keyblock_orig);
           if (rc)
             log_error (_("error writing keyring '%s': %s\n"),
                        keydb_get_resource_name (hd), gpg_strerror (rc) );
@@ -2288,7 +2289,7 @@ import_secret_one (ctrl_t ctrl, kbnode_t keyblock,
  * Import a revocation certificate; this is a single signature packet.
  */
 static int
-import_revoke_cert (kbnode_t node, struct import_stats_s *stats)
+import_revoke_cert (ctrl_t ctrl, kbnode_t node, struct import_stats_s *stats)
 {
   PKT_public_key *pk = NULL;
   kbnode_t onode;
@@ -2379,7 +2380,7 @@ import_revoke_cert (kbnode_t node, struct import_stats_s *stats)
   insert_kbnode( keyblock, clone_kbnode(node), 0 );
 
   /* and write the keyblock back */
-  rc = keydb_update_keyblock (hd, keyblock );
+  rc = keydb_update_keyblock (ctrl, hd, keyblock );
   if (rc)
     log_error (_("error writing keyring '%s': %s\n"),
                keydb_get_resource_name (hd), gpg_strerror (rc) );
diff --git a/g10/keydb.c b/g10/keydb.c
index 1467b2d53..aab90e380 100644
--- a/g10/keydb.c
+++ b/g10/keydb.c
@@ -1518,7 +1518,7 @@ build_keyblock_image (kbnode_t keyblock, iobuf_t *r_iobuf, u32 **r_sigstatus)
  * you should use keydb_push_found_state and keydb_pop_found_state to
  * save and restore it.  */
 gpg_error_t
-keydb_update_keyblock (KEYDB_HANDLE hd, kbnode_t kb)
+keydb_update_keyblock (ctrl_t ctrl, KEYDB_HANDLE hd, kbnode_t kb)
 {
   gpg_error_t err;
   PKT_public_key *pk;
@@ -1542,6 +1542,10 @@ keydb_update_keyblock (KEYDB_HANDLE hd, kbnode_t kb)
   if (err)
     return err;
 
+#ifdef USE_TOFU
+  tofu_notice_key_changed (ctrl, kb);
+#endif
+
   memset (&desc, 0, sizeof (desc));
   fingerprint_from_pk (pk, desc.u.fpr, &len);
   if (len == 20)
diff --git a/g10/keydb.h b/g10/keydb.h
index e4fbe274f..8daa9ee0f 100644
--- a/g10/keydb.h
+++ b/g10/keydb.h
@@ -181,7 +181,7 @@ const char *keydb_get_resource_name (KEYDB_HANDLE hd);
 gpg_error_t keydb_get_keyblock (KEYDB_HANDLE hd, KBNODE *ret_kb);
 
 /* Update the keyblock KB.  */
-gpg_error_t keydb_update_keyblock (KEYDB_HANDLE hd, kbnode_t kb);
+gpg_error_t keydb_update_keyblock (ctrl_t ctrl, KEYDB_HANDLE hd, kbnode_t kb);
 
 /* Insert a keyblock into one of the underlying keyrings or keyboxes.  */
 gpg_error_t keydb_insert_keyblock (KEYDB_HANDLE hd, kbnode_t kb);
diff --git a/g10/keyedit.c b/g10/keyedit.c
index 795be052d..5b77ee747 100644
--- a/g10/keyedit.c
+++ b/g10/keyedit.c
@@ -2782,7 +2782,7 @@ keyedit_menu (ctrl_t ctrl, const char *username, strlist_t locusr,
 	case cmdSAVE:
 	  if (modified)
 	    {
-              err = keydb_update_keyblock (kdbhd, keyblock);
+              err = keydb_update_keyblock (ctrl, kdbhd, keyblock);
               if (err)
                 {
                   log_error (_("update failed: %s\n"), gpg_strerror (err));
@@ -2936,7 +2936,7 @@ keyedit_quick_adduid (ctrl_t ctrl, const char *username, const char *newuid)
 
   if (menu_adduid (ctrl, keyblock, 0, NULL, uidstring))
     {
-      err = keydb_update_keyblock (kdbhd, keyblock);
+      err = keydb_update_keyblock (ctrl, kdbhd, keyblock);
       if (err)
         {
           log_error (_("update failed: %s\n"), gpg_strerror (err));
@@ -3039,7 +3039,7 @@ keyedit_quick_revuid (ctrl_t ctrl, const char *username, const char *uidtorev)
                          gpg_strerror (err));
               goto leave;
             }
-          err = keydb_update_keyblock (kdbhd, keyblock);
+          err = keydb_update_keyblock (ctrl, kdbhd, keyblock);
           if (err)
             {
               log_error (_("update failed: %s\n"), gpg_strerror (err));
@@ -3261,7 +3261,7 @@ keyedit_quick_sign (ctrl_t ctrl, const char *fpr, strlist_t uids,
 
   if (modified)
     {
-      err = keydb_update_keyblock (kdbhd, keyblock);
+      err = keydb_update_keyblock (ctrl, kdbhd, keyblock);
       if (err)
         {
           log_error (_("update failed: %s\n"), gpg_strerror (err));
@@ -3326,7 +3326,7 @@ keyedit_quick_addkey (ctrl_t ctrl, const char *fpr, const char *algostr,
   /* Store.  */
   if (modified)
     {
-      err = keydb_update_keyblock (kdbhd, keyblock);
+      err = keydb_update_keyblock (ctrl, kdbhd, keyblock);
       if (err)
         {
           log_error (_("update failed: %s\n"), gpg_strerror (err));
diff --git a/g10/test-stubs.c b/g10/test-stubs.c
index 8560f9d22..2dc65ab4d 100644
--- a/g10/test-stubs.c
+++ b/g10/test-stubs.c
@@ -517,3 +517,12 @@ tofu_end_batch_update (ctrl_t ctrl)
 {
   (void)ctrl;
 }
+
+gpg_error_t
+tofu_notice_key_changed (ctrl_t ctrl, kbnode_t kb)
+{
+  (void) ctrl;
+  (void) kb;
+
+  return 0;
+}
diff --git a/g10/tofu.c b/g10/tofu.c
index 696cfc368..96938931f 100644
--- a/g10/tofu.c
+++ b/g10/tofu.c
@@ -682,13 +682,49 @@ initdb (sqlite3 *db)
     {
       /* Early version of the v1 format did not include the encryption
          table.  Add it.  */
-      sqlite3_exec (db,
-                    "create table if not exists encryptions"
-                    " (binding INTEGER NOT NULL,"
-                    "  time INTEGER);"
-                    "create index if not exists encryptions_binding"
-                    " on encryptions (binding);\n",
-                    NULL, NULL, &err);
+      rc = sqlite3_exec (db,
+                         "create table if not exists encryptions"
+                         " (binding INTEGER NOT NULL,"
+                         "  time INTEGER);"
+                         "create index if not exists encryptions_binding"
+                         " on encryptions (binding);\n",
+                         NULL, NULL, &err);
+      if (rc)
+        {
+	  log_error (_("error creating 'encryptions' TOFU table: %s\n"),
+		     err);
+          sqlite3_free (err);
+        }
+    }
+  if (! rc)
+    {
+      /* The effective policy for a binding.  If a key is ultimately
+       * trusted, then the effective policy of all of its bindings is
+       * good.  Likewise if a key is signed by an ultimately trusted
+       * key, etc.  If the effective policy is NONE, then we need to
+       * recompute the effective policy.  Otherwise, the effective
+       * policy is considered to be up to date, i.e., effective_policy
+       * is a cache of the computed policy.  */
+      rc = gpgsql_exec_printf
+        (db, NULL, NULL, &err,
+         "alter table bindings"
+         " add column effective_policy INTEGER"
+         " DEFAULT %d"
+         " CHECK (effective_policy in (%d, %d, %d, %d, %d, %d));",
+         TOFU_POLICY_NONE,
+         TOFU_POLICY_NONE, TOFU_POLICY_AUTO, TOFU_POLICY_GOOD,
+         TOFU_POLICY_UNKNOWN, TOFU_POLICY_BAD, TOFU_POLICY_ASK);
+      if (rc)
+	{
+          if (rc == SQLITE_ERROR)
+            /* Almost certainly "duplicate column name", which we can
+             * safely ignore.  */
+            rc = 0;
+          else
+            log_error (_("adding column effective_policy to bindings DB: %s\n"),
+                       err);
+	  sqlite3_free (err);
+	}
     }
 
   if (rc)
@@ -858,8 +894,9 @@ get_single_long_cb2 (void *cookie, int argc, char **argv, char **azColName,
    If SHOW_OLD is set, the binding's old policy is displayed.  */
 static gpg_error_t
 record_binding (tofu_dbs_t dbs, const char *fingerprint, const char *email,
-		const char *user_id, enum tofu_policy policy,
-                const char *conflict,
+		const char *user_id,
+                enum tofu_policy policy, enum tofu_policy effective_policy,
+                const char *conflict, int set_conflict,
                 int show_old, time_t now)
 {
   char *fingerprint_pp = format_hexfingerprint (fingerprint, NULL, 0);
@@ -924,19 +961,33 @@ record_binding (tofu_dbs_t dbs, const char *fingerprint, const char *email,
   rc = gpgsql_stepx
     (dbs->db, &dbs->s.record_binding_update, NULL, NULL, &err,
      "insert or replace into bindings\n"
-     " (oid, fingerprint, email, user_id, time, policy, conflict)\n"
+     " (oid, fingerprint, email, user_id, time,"
+     "  policy, conflict, effective_policy)\n"
      " values (\n"
      /* If we don't explicitly reuse the OID, then SQLite will
-	reallocate a new one.  We just need to search for the OID
-	based on the fingerprint and email since they are unique.  */
+      * reallocate a new one.  We just need to search for the OID
+      * based on the fingerprint and email since they are unique.  */
      "  (select oid from bindings where fingerprint = ? and email = ?),\n"
-     "  ?, ?, ?, ?, ?, ?);",
+     "  ?, ?, ?, ?, ?,"
+     /* If SET_CONFLICT is 0, then preserve conflict's current value.  */
+     "  case ?"
+     "    when 0 then"
+     "      (select conflict from bindings where fingerprint = ? and email = ?)"
+     "    else ?"
+     "  end,"
+     "  ?);",
+     /* oid subquery.  */
      GPGSQL_ARG_STRING, fingerprint, GPGSQL_ARG_STRING, email,
+     /* values 2 through 6.  */
      GPGSQL_ARG_STRING, fingerprint, GPGSQL_ARG_STRING, email,
      GPGSQL_ARG_STRING, user_id,
      GPGSQL_ARG_LONG_LONG, (long long) now,
      GPGSQL_ARG_INT, (int) policy,
+     /* conflict subquery.  */
+     GPGSQL_ARG_INT, set_conflict ? 1 : 0,
+     GPGSQL_ARG_STRING, fingerprint, GPGSQL_ARG_STRING, email,
      GPGSQL_ARG_STRING, conflict ? conflict : "",
+     GPGSQL_ARG_INT, (int) effective_policy,
      GPGSQL_ARG_END);
   if (rc)
     {
@@ -1113,108 +1164,6 @@ time_ago_scale (signed long t)
 }
 
 
-/* Return the policy for the binding <FINGERPRINT, EMAIL> (email has
-   already been normalized) and any conflict information in *CONFLICT
-   if CONFLICT is not NULL.  Returns _tofu_GET_POLICY_ERROR if an error
-   occurs.  */
-static enum tofu_policy
-get_policy (tofu_dbs_t dbs, const char *fingerprint, const char *email,
-	    char **conflict)
-{
-  int rc;
-  char *err = NULL;
-  strlist_t strlist = NULL;
-  enum tofu_policy policy = _tofu_GET_POLICY_ERROR;
-  long along;
-
-  /* Check if the <FINGERPRINT, EMAIL> binding is known
-     (TOFU_POLICY_NONE cannot appear in the DB.  Thus, if POLICY is
-     still TOFU_POLICY_NONE after executing the query, then the
-     result set was empty.)  */
-  rc = gpgsql_stepx (dbs->db, &dbs->s.get_policy_select_policy_and_conflict,
-                      strings_collect_cb2, &strlist, &err,
-                      "select policy, conflict from bindings\n"
-                      " where fingerprint = ? and email = ?",
-                      GPGSQL_ARG_STRING, fingerprint,
-                      GPGSQL_ARG_STRING, email,
-                      GPGSQL_ARG_END);
-  if (rc)
-    {
-      log_error (_("error reading TOFU database: %s\n"), err);
-      print_further_info ("checking for existing bad bindings");
-      sqlite3_free (err);
-      rc = gpg_error (GPG_ERR_GENERAL);
-      goto out;
-    }
-
-  if (strlist_length (strlist) == 0)
-    /* No results.  */
-    {
-      policy = TOFU_POLICY_NONE;
-      goto out;
-    }
-  else if (strlist_length (strlist) != 2)
-    /* The result has the wrong form.  */
-    {
-      log_error (_("error reading TOFU database: %s\n"),
-                 gpg_strerror (GPG_ERR_BAD_DATA));
-      print_further_info ("checking for existing bad bindings:"
-                          " expected 2 results, got %d\n",
-                          strlist_length (strlist));
-      goto out;
-    }
-
-  /* The result has the right form.  */
-
-  if (string_to_long (&along, strlist->d, 0, __LINE__))
-    {
-      log_error (_("error reading TOFU database: %s\n"),
-                 gpg_strerror (GPG_ERR_BAD_DATA));
-      print_further_info ("bad value for policy: %s", strlist->d);
-      goto out;
-    }
-  policy = along;
-
-  if (! (policy == TOFU_POLICY_AUTO
-	 || policy == TOFU_POLICY_GOOD
-	 || policy == TOFU_POLICY_UNKNOWN
-	 || policy == TOFU_POLICY_BAD
-	 || policy == TOFU_POLICY_ASK))
-    {
-      log_error (_("error reading TOFU database: %s\n"),
-                 gpg_strerror (GPG_ERR_DB_CORRUPTED));
-      print_further_info ("invalid value for policy (%d)", policy);
-      policy = _tofu_GET_POLICY_ERROR;
-      goto out;
-    }
-
-
-  /* If CONFLICT is set, then policy should be TOFU_POLICY_ASK.  But,
-     just in case, we do the check again here and ignore the conflict
-     if POLICY is not TOFU_POLICY_ASK.  */
-  if (conflict)
-    {
-      if (policy == TOFU_POLICY_ASK && *strlist->next->d)
-	*conflict = xstrdup (strlist->next->d);
-      else
-	*conflict = NULL;
-    }
-
- out:
-  log_assert (policy == _tofu_GET_POLICY_ERROR
-              || policy == TOFU_POLICY_NONE
-              || policy == TOFU_POLICY_AUTO
-              || policy == TOFU_POLICY_GOOD
-              || policy == TOFU_POLICY_UNKNOWN
-              || policy == TOFU_POLICY_BAD
-              || policy == TOFU_POLICY_ASK);
-
-  free_strlist (strlist);
-
-  return policy;
-}
-
-
 /* Format the first part of a conflict message and return that as a
  * malloced string.  */
 static char *
@@ -1862,7 +1811,7 @@ ask_about_binding (ctrl_t ctrl,
                 }
 
               if (record_binding (dbs, fingerprint, email, user_id,
-                                  *policy, NULL, 0, now))
+                                  *policy, TOFU_POLICY_NONE, NULL, 0, 0, now))
                 {
                   /* If there's an error registering the
                    * binding, don't save the signature.  */
@@ -2150,6 +2099,328 @@ build_conflict_set (tofu_dbs_t dbs,
 }
 
 
+/* Return the effective policy for the binding <FINGERPRINT, EMAIL>
+ * (email has already been normalized) and any conflict information in
+ * *CONFLICT_SETP, if CONFLICT_SETP is not NULL.  Returns
+ * _tofu_GET_POLICY_ERROR if an error occurs.  */
+static enum tofu_policy
+get_policy (tofu_dbs_t dbs, PKT_public_key *pk,
+            const char *fingerprint, const char *user_id, const char *email,
+	    strlist_t *conflict_setp, time_t now)
+{
+  int rc;
+  char *err = NULL;
+  strlist_t results = NULL;
+  enum tofu_policy policy = _tofu_GET_POLICY_ERROR;
+  enum tofu_policy effective_policy_orig = TOFU_POLICY_NONE;
+  enum tofu_policy effective_policy = _tofu_GET_POLICY_ERROR;
+  long along;
+  char *conflict_orig = NULL;
+  char *conflict = NULL;
+  strlist_t conflict_set = NULL;
+  int conflict_set_count;
+
+  /* Check if the <FINGERPRINT, EMAIL> binding is known
+     (TOFU_POLICY_NONE cannot appear in the DB.  Thus, if POLICY is
+     still TOFU_POLICY_NONE after executing the query, then the
+     result set was empty.)  */
+  rc = gpgsql_stepx (dbs->db, &dbs->s.get_policy_select_policy_and_conflict,
+                      strings_collect_cb2, &results, &err,
+                      "select policy, conflict, effective_policy from bindings\n"
+                      " where fingerprint = ? and email = ?",
+                      GPGSQL_ARG_STRING, fingerprint,
+                      GPGSQL_ARG_STRING, email,
+                      GPGSQL_ARG_END);
+  if (rc)
+    {
+      log_error (_("error reading TOFU database: %s\n"), err);
+      print_further_info ("reading the policy");
+      sqlite3_free (err);
+      rc = gpg_error (GPG_ERR_GENERAL);
+      goto out;
+    }
+
+  if (strlist_length (results) == 0)
+    {
+      /* No results.  Use the defaults.  */
+      policy = TOFU_POLICY_NONE;
+      effective_policy = TOFU_POLICY_NONE;
+    }
+  else if (strlist_length (results) == 3)
+    {
+      /* Parse and sanity check the results.  */
+
+      if (string_to_long (&along, results->d, 0, __LINE__))
+        {
+          log_error (_("error reading TOFU database: %s\n"),
+                     gpg_strerror (GPG_ERR_BAD_DATA));
+          print_further_info ("bad value for policy: %s", results->d);
+          goto out;
+        }
+      policy = along;
+
+      if (! (policy == TOFU_POLICY_AUTO
+             || policy == TOFU_POLICY_GOOD
+             || policy == TOFU_POLICY_UNKNOWN
+             || policy == TOFU_POLICY_BAD
+             || policy == TOFU_POLICY_ASK))
+        {
+          log_error (_("error reading TOFU database: %s\n"),
+                     gpg_strerror (GPG_ERR_DB_CORRUPTED));
+          print_further_info ("invalid value for policy (%d)", policy);
+          effective_policy = _tofu_GET_POLICY_ERROR;
+          goto out;
+        }
+
+      if (*results->next->d)
+        conflict = xstrdup (results->next->d);
+
+      if (string_to_long (&along, results->next->next->d, 0, __LINE__))
+        {
+          log_error (_("error reading TOFU database: %s\n"),
+                     gpg_strerror (GPG_ERR_BAD_DATA));
+          print_further_info ("bad value for effective policy: %s",
+                              results->next->next->d);
+          goto out;
+        }
+      effective_policy = along;
+
+      if (! (effective_policy == TOFU_POLICY_NONE
+             || effective_policy == TOFU_POLICY_AUTO
+             || effective_policy == TOFU_POLICY_GOOD
+             || effective_policy == TOFU_POLICY_UNKNOWN
+             || effective_policy == TOFU_POLICY_BAD
+             || effective_policy == TOFU_POLICY_ASK))
+        {
+          log_error (_("error reading TOFU database: %s\n"),
+                     gpg_strerror (GPG_ERR_DB_CORRUPTED));
+          print_further_info ("invalid value for effective_policy (%d)",
+                              effective_policy);
+          effective_policy = _tofu_GET_POLICY_ERROR;
+          goto out;
+        }
+    }
+  else
+    {
+      /* The result has the wrong form.  */
+
+      log_error (_("error reading TOFU database: %s\n"),
+                 gpg_strerror (GPG_ERR_BAD_DATA));
+      print_further_info ("reading policy: expected 3 columns, got %d\n",
+                          strlist_length (results));
+      goto out;
+    }
+
+  /* Save the effective policy and conflict so we know if we changed
+   * them.  */
+  effective_policy_orig = effective_policy;
+  conflict_orig = conflict;
+
+  /* Unless there is a conflict, if the effective policy is cached,
+   * just return it.  The reason we don't do this when there is a
+   * conflict is because of the following scenario: assume A and B
+   * conflict and B has signed A's key.  Now, later we import A's
+   * signature on B.  We need to recheck A, but the signature was on
+   * B, i.e., when B changes, we invalidate B's effective policy, but
+   * we also need to invalidate A's effective policy.  Instead, we
+   * assume that conflicts are rare and don't optimize for them, which
+   * would complicate the code.  */
+  if (effective_policy != TOFU_POLICY_NONE && !conflict)
+    goto out;
+
+  /* If the user explicitly set the policy, then respect that.  */
+  if (policy != TOFU_POLICY_AUTO && policy != TOFU_POLICY_NONE)
+    {
+      effective_policy = policy;
+      goto out;
+    }
+
+  /* Unless proven wrong, assume the effective policy is 'auto'.  */
+  effective_policy = TOFU_POLICY_AUTO;
+
+  /* See if the key is ultimately trusted.  */
+  {
+    u32 kid[2];
+
+    keyid_from_pk (pk, kid);
+    if (tdb_keyid_is_utk (kid))
+      {
+        effective_policy = TOFU_POLICY_GOOD;
+        goto out;
+      }
+  }
+
+  /* See if the key is signed by an ultimately trusted key.  */
+  {
+    int fingerprint_raw_len = strlen (fingerprint) / 2;
+    char fingerprint_raw[fingerprint_raw_len];
+    int len = 0;
+
+    if (fingerprint_raw_len != 20
+        || ((len = hex2bin (fingerprint,
+                            fingerprint_raw, fingerprint_raw_len))
+            != strlen (fingerprint)))
+      {
+        if (DBG_TRUST)
+          log_debug ("TOFU: Bad fingerprint: %s (len: %zd, parsed: %d)\n",
+                     fingerprint, strlen (fingerprint), len);
+      }
+    else
+      {
+        int lookup_err;
+        kbnode_t kb;
+
+        lookup_err = get_pubkey_byfprint (NULL, &kb,
+                                          fingerprint_raw,
+                                          fingerprint_raw_len);
+        if (lookup_err)
+          {
+            if (DBG_TRUST)
+              log_debug ("TOFU: Looking up %s: %s\n",
+                         fingerprint, gpg_strerror (lookup_err));
+          }
+        else
+          {
+            int is_signed_by_utk = signed_by_utk (email, kb);
+            release_kbnode (kb);
+            if (is_signed_by_utk)
+              {
+                effective_policy = TOFU_POLICY_GOOD;
+                goto out;
+              }
+          }
+      }
+  }
+
+  /* Check for any conflicts / see if a previously discovered conflict
+   * disappeared.  The latter can happen if the conflicting bindings
+   * are now cross signed, for instance.  */
+
+  conflict_set = build_conflict_set (dbs, pk, fingerprint, email);
+  conflict_set_count = strlist_length (conflict_set);
+  if (conflict_set_count == 0)
+    {
+      /* build_conflict_set should always at least return the current
+         binding.  Something went wrong.  */
+      effective_policy = _tofu_GET_POLICY_ERROR;
+      goto out;
+    }
+
+  if (conflict_set_count == 1
+      && (conflict_set->flags & BINDING_NEW))
+    {
+      /* We've never observed a binding with this email address and we
+       * have a default policy, which is not to ask the user.  */
+
+      /* If we've seen this binding, then we've seen this email and
+       * policy couldn't possibly be TOFU_POLICY_NONE.  */
+      log_assert (policy == TOFU_POLICY_NONE);
+
+      if (DBG_TRUST)
+	log_debug ("TOFU: New binding <key: %s, user id: %s>, no conflict.\n",
+		   fingerprint, email);
+
+      effective_policy = TOFU_POLICY_AUTO;
+      goto out;
+    }
+
+  if (conflict_set_count == 1
+      && (conflict_set->flags & BINDING_CONFLICT))
+    {
+      /* No known conflicts now, but there was a conflict.  That is,
+       * at somepoint there was a conflict, but it went away.  A
+       * conflict can go away if there is now a cross sig between the
+       * two keys.  In this case, we just silently clear the
+       * conflict.  */
+
+      if (DBG_TRUST)
+        log_debug ("TOFU: binding <key: %s, user id: %s> had a conflict, but it's been resolved (probably via  cross sig).\n",
+                   fingerprint, email);
+
+      effective_policy = TOFU_POLICY_AUTO;
+      conflict = NULL;
+
+      goto out;
+    }
+
+  if (conflict_set_count == 1)
+    {
+      /* No conflicts and never marked as conflicting.  */
+
+      log_assert (!conflict);
+
+      effective_policy = TOFU_POLICY_AUTO;
+
+      goto out;
+    }
+
+  /* There is a conflicting key.  */
+  log_assert (conflict_set_count > 1);
+  effective_policy = TOFU_POLICY_ASK;
+  conflict = xstrdup (conflict_set->next->d);
+
+ out:
+  log_assert (policy == _tofu_GET_POLICY_ERROR
+              || policy == TOFU_POLICY_NONE
+              || policy == TOFU_POLICY_AUTO
+              || policy == TOFU_POLICY_GOOD
+              || policy == TOFU_POLICY_UNKNOWN
+              || policy == TOFU_POLICY_BAD
+              || policy == TOFU_POLICY_ASK);
+  /* Everything but NONE.  */
+  log_assert (effective_policy == _tofu_GET_POLICY_ERROR
+              || effective_policy == TOFU_POLICY_AUTO
+              || effective_policy == TOFU_POLICY_GOOD
+              || effective_policy == TOFU_POLICY_UNKNOWN
+              || effective_policy == TOFU_POLICY_BAD
+              || effective_policy == TOFU_POLICY_ASK);
+
+  if (effective_policy != TOFU_POLICY_ASK && conflict)
+    conflict = NULL;
+
+  /* If we don't have a record of this binding, its effective policy
+   * changed, or conflict changed, update the DB.  */
+  if (effective_policy != _tofu_GET_POLICY_ERROR
+      && (/* New binding.  */
+          policy == TOFU_POLICY_NONE
+          /* effective_policy changed.  */
+          || effective_policy != effective_policy_orig
+          /* conflict changed.  */
+          || (conflict != conflict_orig
+              && (!conflict || !conflict_orig
+                  || strcmp (conflict, conflict_orig) != 0))))
+    {
+      if (record_binding (dbs, fingerprint, email, user_id,
+                          policy == TOFU_POLICY_NONE ? TOFU_POLICY_AUTO : policy,
+                          effective_policy, conflict, 1, 0, now) != 0)
+        log_error (_("error setting TOFU binding's policy"
+                     " to %s\n"), tofu_policy_str (policy));
+    }
+
+  /* If the caller wants the set of conflicts, return it.  */
+  if (effective_policy == TOFU_POLICY_ASK && conflict_setp)
+    {
+      if (! conflict_set)
+        conflict_set = build_conflict_set (dbs, pk, fingerprint, email);
+      *conflict_setp = conflict_set;
+    }
+  else
+    {
+      free_strlist (conflict_set);
+
+      if (conflict_setp)
+        *conflict_setp = NULL;
+    }
+
+  xfree (conflict_orig);
+  if (conflict != conflict_orig)
+    xfree (conflict);
+  free_strlist (results);
+
+  return effective_policy;
+}
+
+
 /* Return the trust level (TRUST_NEVER, etc.) for the binding
  * <FINGERPRINT, EMAIL> (email is already normalized).  If no policy
  * is registered, returns TOFU_POLICY_NONE.  If an error occurs,
@@ -2175,9 +2446,7 @@ get_trust (ctrl_t ctrl, PKT_public_key *pk,
   enum tofu_policy policy;
   int rc;
   char *sqerr = NULL;
-  int change_conflicting_to_ask = 0;
   strlist_t conflict_set = NULL;
-  int conflict_set_count;
   int trust_level = TRUST_UNKNOWN;
   strlist_t iter;
 
@@ -2201,36 +2470,22 @@ get_trust (ctrl_t ctrl, PKT_public_key *pk,
               && _tofu_GET_TRUST_ERROR != TRUST_FULLY
               && _tofu_GET_TRUST_ERROR != TRUST_ULTIMATE);
 
-  begin_transaction (ctrl, 0);
-  in_transaction = 1;
-
-  policy = get_policy (dbs, fingerprint, email, NULL);
+  /* If the key is ultimately trusted, there is nothing to do.  */
   {
-    /* See if the key is ultimately trusted.  If so, we're done.  */
     u32 kid[2];
 
     keyid_from_pk (pk, kid);
-
     if (tdb_keyid_is_utk (kid))
       {
-        if (policy == TOFU_POLICY_NONE)
-          /* New binding.  */
-          {
-            if (record_binding (dbs, fingerprint, email, user_id,
-                                TOFU_POLICY_GOOD, NULL, 0, now) != 0)
-              {
-                log_error (_("error setting TOFU binding's trust level"
-                             " to %s\n"), "good");
-                trust_level = _tofu_GET_TRUST_ERROR;
-                goto out;
-              }
-          }
-
         trust_level = TRUST_ULTIMATE;
         goto out;
       }
   }
 
+  begin_transaction (ctrl, 0);
+  in_transaction = 1;
+
+  policy = get_policy (dbs, pk, fingerprint, user_id, email, &conflict_set, now);
   if (policy == TOFU_POLICY_AUTO)
     {
       policy = opt.tofu_default_policy;
@@ -2255,12 +2510,7 @@ get_trust (ctrl_t ctrl, PKT_public_key *pk,
       goto out;
 
     case TOFU_POLICY_ASK:
-      /* We need to ask the user what to do.  Case #1 or #2 below.  */
-      break;
-
-    case TOFU_POLICY_NONE:
-      /* The binding is new, we need to check for conflicts.  Case #3
-       * below.  */
+      /* We need to ask the user what to do.  */
       break;
 
     case _tofu_GET_POLICY_ERROR:
@@ -2281,211 +2531,68 @@ get_trust (ctrl_t ctrl, PKT_public_key *pk,
    *   2. The saved policy is ask (either last time the user selected
    *      accept once or reject once or there was a conflict and this
    *      binding's policy was changed from auto to ask)
-   *      (policy == TOFU_POLICY_ASK), or,
-   *
-   *   3. We don't have a saved policy (policy == TOFU_POLICY_NONE)
-   *      (need to check for a conflict).
-   *
-   * In summary: POLICY is ask or none.
+   *      (policy == TOFU_POLICY_ASK).
    */
+  log_assert (policy == TOFU_POLICY_ASK);
 
-  /* Before continuing, see if the key is signed by an ultimately
-   * trusted key.  */
-  {
-    int fingerprint_raw_len = strlen (fingerprint) / 2;
-    char fingerprint_raw[fingerprint_raw_len];
-    int len = 0;
-    int is_signed_by_utk = 0;
-
-    if (fingerprint_raw_len != 20
-        || ((len = hex2bin (fingerprint,
-                            fingerprint_raw, fingerprint_raw_len))
-            != strlen (fingerprint)))
-      {
-        if (DBG_TRUST)
-          log_debug ("TOFU: Bad fingerprint: %s (len: %zd, parsed: %d)\n",
-                     fingerprint, strlen (fingerprint), len);
-      }
-    else
-      {
-        int lookup_err;
-        kbnode_t kb;
-
-        lookup_err = get_pubkey_byfprint (NULL, &kb,
-                                          fingerprint_raw,
-                                          fingerprint_raw_len);
-        if (lookup_err)
-          {
-            if (DBG_TRUST)
-              log_debug ("TOFU: Looking up %s: %s\n",
-                         fingerprint, gpg_strerror (lookup_err));
-          }
-        else
-          {
-            is_signed_by_utk = signed_by_utk (email, kb);
-            release_kbnode (kb);
-          }
-      }
-
-    if (is_signed_by_utk)
-      {
-        if (record_binding (dbs, fingerprint, email, user_id,
-                            TOFU_POLICY_GOOD, NULL, 0, now) != 0)
-          {
-            log_error (_("error setting TOFU binding's trust level"
-                         " to %s\n"), "good");
-            trust_level = _tofu_GET_TRUST_ERROR;
-          }
-        else
-          trust_level = TRUST_FULLY;
-
-        goto out;
-      }
-  }
-
-
-  /* Look for conflicts.  This is needed in all 3 cases.  */
-  conflict_set = build_conflict_set (dbs, pk, fingerprint, email);
-  conflict_set_count = strlist_length (conflict_set);
-  if (conflict_set_count == 0)
-    {
-      /* We should always at least have the current binding.  */
-      trust_level = _tofu_GET_TRUST_ERROR;
-      goto out;
-    }
-
-  if (conflict_set_count == 1
-      && (conflict_set->flags & BINDING_NEW)
-      && opt.tofu_default_policy != TOFU_POLICY_ASK)
+  if (may_ask)
     {
-      /* We've never observed a binding with this email address and we
-       * have a default policy, which is not to ask the user.  */
-
-      /* If we've seen this binding, then we've seen this email and
-       * policy couldn't possibly be TOFU_POLICY_NONE.  */
-      log_assert (policy == TOFU_POLICY_NONE);
-
-      if (DBG_TRUST)
-	log_debug ("TOFU: New binding <key: %s, user id: %s>, no conflict.\n",
-		   fingerprint, email);
-
-      if (record_binding (dbs, fingerprint, email, user_id,
-			  TOFU_POLICY_AUTO, NULL, 0, now) != 0)
-	{
-	  log_error (_("error setting TOFU binding's trust level to %s\n"),
-		       "auto");
-	  trust_level = _tofu_GET_TRUST_ERROR;
-	  goto out;
-	}
+      /* We can't be in a normal transaction in ask_about_binding.  */
+      end_transaction (ctrl, 0);
+      in_transaction = 0;
 
-      trust_level = tofu_policy_to_trust_level (TOFU_POLICY_AUTO);
-      goto out;
+      /* If we get here, we need to ask the user about the binding.  */
+      ask_about_binding (ctrl,
+                         &policy,
+                         &trust_level,
+                         conflict_set,
+                         fingerprint,
+                         email,
+                         user_id,
+                         now);
     }
+  else
+    trust_level = TRUST_UNDEFINED;
 
-  if (conflict_set_count == 1
-      && (conflict_set->flags & BINDING_CONFLICT))
+  /* Mark any conflicting bindings that have an automatic policy as
+   * now requiring confirmation.  Note: we do this after we ask for
+   * confirmation so that when the current policy is printed, it is
+   * correct.  */
+  if (! in_transaction)
     {
-      /* No known conflicts now, but there was a conflict.  This means
-       * at somepoint, there was a conflict and we changed this
-       * binding's policy to ask and set the conflicting key.  The
-       * conflict can go away if there is not a cross sig between the
-       * two keys.  In this case, just silently clear the conflict and
-       * reset the policy to auto.  */
-
-      log_assert (policy == TOFU_POLICY_ASK);
-
-      if (DBG_TRUST)
-        log_debug ("TOFU: binding <key: %s, user id: %s> had a conflict, but it's been resolved (probably via  cross sig).\n",
-                   fingerprint, email);
-
-      if (record_binding (dbs, fingerprint, email, user_id,
-			  TOFU_POLICY_AUTO, NULL, 0, now) != 0)
-	log_error (_("error setting TOFU binding's trust level to %s\n"),
-		   "auto");
-
-      trust_level = tofu_policy_to_trust_level (TOFU_POLICY_AUTO);
-      goto out;
+      begin_transaction (ctrl, 0);
+      in_transaction = 1;
     }
 
-  /* We have a conflict.  Mark any conflicting bindings that have an
-   * automatic policy as now requiring confirmation.  Note: we delay
-   * this until after we ask for confirmation so that when the current
-   * policy is printed, it is correct.  */
-  change_conflicting_to_ask = 1;
+  /* The conflict set should always contain at least one element:
+   * the current key.  */
+  log_assert (conflict_set);
 
-  if (! may_ask)
+  for (iter = conflict_set->next; iter; iter = iter->next)
     {
-      log_assert (policy == TOFU_POLICY_NONE || policy == TOFU_POLICY_ASK);
-      if (policy == TOFU_POLICY_NONE)
+      /* We don't immediately set the effective policy to 'ask,
+         because  */
+      rc = gpgsql_exec_printf
+        (dbs->db, NULL, NULL, &sqerr,
+         "update bindings set effective_policy = %d, conflict = %Q"
+         " where email = %Q and fingerprint = %Q and effective_policy != %d;",
+         TOFU_POLICY_NONE, fingerprint,
+         email, iter->d, TOFU_POLICY_ASK);
+      if (rc)
         {
-          /* We get here in the third case (no saved policy) and if
-           * there is a conflict.  */
-          if (record_binding (dbs, fingerprint, email, user_id,
-                              TOFU_POLICY_ASK,
-                              conflict_set && conflict_set->next
-                              ? conflict_set->next->d : NULL,
-                              0, now) != 0)
-            log_error (_("error setting TOFU binding's trust level to %s\n"),
-                       "ask");
+          log_error (_("error changing TOFU policy: %s\n"), sqerr);
+          print_further_info ("binding: <key: %s, user id: %s>",
+                              fingerprint, user_id);
+          sqlite3_free (sqerr);
+          sqerr = NULL;
+          rc = gpg_error (GPG_ERR_GENERAL);
         }
-
-      trust_level = TRUST_UNDEFINED;
-      goto out;
+      else if (DBG_TRUST)
+        log_debug ("Set %s to conflict with %s\n",
+                   iter->d, fingerprint);
     }
 
-  /* We can't be in a normal transaction in ask_about_binding.  */
-  end_transaction (ctrl, 0);
-  in_transaction = 0;
-
-  /* If we get here, we need to ask the user about the binding.  */
-  ask_about_binding (ctrl,
-                     &policy,
-                     &trust_level,
-                     conflict_set,
-                     fingerprint,
-                     email,
-                     user_id,
-                     now);
-
  out:
-
-  if (change_conflicting_to_ask)
-    {
-      /* Mark any conflicting bindings that have an automatic policy as
-       * now requiring confirmation.  */
-
-      if (! in_transaction)
-        {
-          begin_transaction (ctrl, 0);
-          in_transaction = 1;
-        }
-
-      /* If we weren't allowed to ask, also update this key as
-       * conflicting with itself.  */
-      for (iter = may_ask ? conflict_set->next : conflict_set;
-           iter; iter = iter->next)
-        {
-          rc = gpgsql_exec_printf
-            (dbs->db, NULL, NULL, &sqerr,
-             "update bindings set policy = %d, conflict = %Q"
-             " where email = %Q and fingerprint = %Q and policy = %d;",
-             TOFU_POLICY_ASK, fingerprint,
-             email, iter->d, TOFU_POLICY_AUTO);
-          if (rc)
-            {
-              log_error (_("error changing TOFU policy: %s\n"), sqerr);
-              print_further_info ("binding: <key: %s, user id: %s>",
-                                  fingerprint, user_id);
-              sqlite3_free (sqerr);
-              sqerr = NULL;
-              rc = gpg_error (GPG_ERR_GENERAL);
-            }
-          else if (DBG_TRUST)
-            log_debug ("Set %s to conflict with %s\n",
-                       iter->d, fingerprint);
-        }
-    }
-
   if (in_transaction)
     end_transaction (ctrl, 0);
 
@@ -2684,17 +2791,18 @@ write_stats_status (estream_t fp,
 }
 
 /* Note: If OUTFP is not NULL, this function merely prints a "tfs" record
- * to OUTFP.  In this case USER_ID is not required.
+ * to OUTFP.
  *
  * Returns whether the caller should call show_warning after iterating
  * over all user ids.
  */
 static int
-show_statistics (tofu_dbs_t dbs, const char *fingerprint,
+show_statistics (tofu_dbs_t dbs, PKT_public_key *pk, const char *fingerprint,
 		 const char *email, const char *user_id,
 		 estream_t outfp, time_t now)
 {
-  enum tofu_policy policy = get_policy (dbs, fingerprint, email, NULL);
+  enum tofu_policy policy =
+    get_policy (dbs, pk, fingerprint, user_id, email, NULL, now);
 
   char *fingerprint_pp;
   int rc;
@@ -3336,7 +3444,7 @@ tofu_write_tfs_record (ctrl_t ctrl, estream_t fp,
   fingerprint = hexfingerprint (pk, NULL, 0);
   email = email_from_user_id (user_id);
 
-  show_statistics (dbs, fingerprint, email, user_id, fp, now);
+  show_statistics (dbs, pk, fingerprint, email, user_id, fp, now);
 
   xfree (email);
   xfree (fingerprint);
@@ -3412,7 +3520,7 @@ tofu_get_validity (ctrl_t ctrl, PKT_public_key *pk, strlist_t user_id_list,
 
       if (may_ask && tl != TRUST_ULTIMATE && tl != TRUST_EXPIRED)
         need_warning |=
-          show_statistics (dbs, fingerprint, email, user_id->d, NULL, now);
+          show_statistics (dbs, pk, fingerprint, email, user_id->d, NULL, now);
 
       if (tl == TRUST_NEVER)
         trust_level = TRUST_NEVER;
@@ -3512,7 +3620,7 @@ tofu_set_policy (ctrl_t ctrl, kbnode_t kb, enum tofu_policy policy)
       email = email_from_user_id (user_id->name);
 
       err = record_binding (dbs, fingerprint, email, user_id->name,
-                            policy, NULL, 1, now);
+                            policy, TOFU_POLICY_NONE, NULL, 0, 1, now);
       if (err)
         {
           log_error (_("error setting policy for key %s, user id \"%s\": %s"),
@@ -3561,6 +3669,7 @@ gpg_error_t
 tofu_get_policy (ctrl_t ctrl, PKT_public_key *pk, PKT_user_id *user_id,
 		 enum tofu_policy *policy)
 {
+  time_t now = gnupg_get_time ();
   tofu_dbs_t dbs;
   char *fingerprint;
   char *email;
@@ -3580,7 +3689,7 @@ tofu_get_policy (ctrl_t ctrl, PKT_public_key *pk, PKT_user_id *user_id,
 
   email = email_from_user_id (user_id->name);
 
-  *policy = get_policy (dbs, fingerprint, email, NULL);
+  *policy = get_policy (dbs, pk, fingerprint, user_id->name, email, NULL, now);
 
   xfree (email);
   xfree (fingerprint);
@@ -3588,3 +3697,42 @@ tofu_get_policy (ctrl_t ctrl, PKT_public_key *pk, PKT_user_id *user_id,
     return gpg_error (GPG_ERR_GENERAL);
   return 0;
 }
+
+gpg_error_t
+tofu_notice_key_changed (ctrl_t ctrl, kbnode_t kb)
+{
+  tofu_dbs_t dbs;
+  PKT_public_key *pk;
+  char *fingerprint;
+  char *sqlerr = NULL;
+  int rc;
+
+  /* Make sure PK is a primary key.  */
+  setup_main_keyids (kb);
+  pk = kb->pkt->pkt.public_key;
+  log_assert (pk_is_primary (pk));
+
+  fingerprint = hexfingerprint (pk, NULL, 0);
+
+  dbs = opendbs (ctrl);
+  if (! dbs)
+    {
+      log_error (_("error opening TOFU database: %s\n"),
+                 gpg_strerror (GPG_ERR_GENERAL));
+      return gpg_error (GPG_ERR_GENERAL);
+    }
+
+  fingerprint = hexfingerprint (pk, NULL, 0);
+
+  rc = gpgsql_stepx (dbs->db, NULL, NULL, NULL, &sqlerr,
+                     "update bindings set effective_policy = ?"
+                     " where fingerprint = ?;",
+                     GPGSQL_ARG_INT, (int) TOFU_POLICY_NONE,
+                     GPGSQL_ARG_STRING, fingerprint,
+                     GPGSQL_ARG_END);
+  xfree (fingerprint);
+
+  if (rc == _tofu_GET_POLICY_ERROR)
+    return gpg_error (GPG_ERR_GENERAL);
+  return 0;
+}
diff --git a/g10/tofu.h b/g10/tofu.h
index f114443bc..3ee2f41b4 100644
--- a/g10/tofu.h
+++ b/g10/tofu.h
@@ -139,4 +139,9 @@ void tofu_end_batch_update (ctrl_t ctrl);
 /* Release all of the resources associated with a DB meta-handle.  */
 void tofu_closedbs (ctrl_t ctrl);
 
+/* Whenever a key is modified (e.g., a user id is added or revoked, a
+ * new signature, etc.), this function should be called to cause TOFU
+ * to update its world view.  */
+gpg_error_t tofu_notice_key_changed (ctrl_t ctrl, kbnode_t kb);
+
 #endif /*G10_TOFU_H*/