doc: Update the record description of the trustdb.
authorWerner Koch <wk@gnupg.org>
Mon, 15 Jun 2015 13:37:30 +0000 (15:37 +0200)
committerWerner Koch <wk@gnupg.org>
Mon, 15 Jun 2015 13:37:30 +0000 (15:37 +0200)
--

This now reflects the used version of the trustdb.  However, it still
missed a detailed description on how it works.

doc/DETAILS

index db01baa..d1f7394 100644 (file)
@@ -924,212 +924,131 @@ pkd:0:1024:B665B1435F4C2 .... FF26ABB:
 
   The TrustDB is built from fixed length records, where the first byte
   describes the record type.  All numeric values are stored in network
-  byte order. The length of each record is 40 bytes. The first record
-  of the DB is always of type 1 and this is the only record of this
-  type.
-
-  FIXME:  The layout changed, document it here.
-#+begin_example
-  Record type 0:
-  --------------
-    Unused record, can be reused for any purpose.
-
-  Record type 1:
-  --------------
-    Version information for this TrustDB.  This is always the first
-    record of the DB and the only one with type 1.
-     1 byte value 1
-     3 bytes 'gpg'  magic value
-     1 byte Version of the TrustDB (2)
-     1 byte marginals needed
-     1 byte completes needed
-     1 byte max_cert_depth
-           The three items are used to check whether the cached
-           validity value from the dir record can be used.
-     1 u32  locked flags [not used]
-     1 u32  timestamp of trustdb creation
-     1 u32  timestamp of last modification which may affect the validity
-           of keys in the trustdb.  This value is checked against the
-           validity timestamp in the dir records.
-     1 u32  timestamp of last validation [currently not used]
-           (Used to keep track of the time, when this TrustDB was checked
-            against the pubring)
-     1 u32  record number of keyhashtable [currently not used]
-     1 u32  first free record
-     1 u32  record number of shadow directory hash table [currently not used]
-           It does not make sense to combine this table with the key table
-           because the keyid is not in every case a part of the fingerprint.
-     1 u32  record number of the trusthashtbale
-
-
-  Record type 2: (directory record)
-  --------------
-    Informations about a public key certificate.
-    These are static values which are never changed without user interaction.
-
-     1 byte value 2
-     1 byte  reserved
-     1 u32   LID     . (This is simply the record number of this record.)
-     1 u32   List of key-records (the first one is the primary key)
-     1 u32   List of uid-records
-     1 u32   cache record
-     1 byte  ownertrust
-     1 byte  dirflag
-     1 byte  maximum validity of all the user ids
-     1 u32   time of last validity check.
-     1 u32   Must check when this time has been reached.
-            (0 = no check required)
-
-
-  Record type 3:  (key record)
-  --------------
-    Informations about a primary public key.
-    (This is mainly used to lookup a trust record)
-
-     1 byte value 3
-     1 byte  reserved
-     1 u32   LID
-     1 u32   next   - next key record
-     7 bytes reserved
-     1 byte  keyflags
-     1 byte  pubkey algorithm
-     1 byte  length of the fingerprint (in bytes)
-     20 bytes fingerprint of the public key
-             (This is the value we use to identify a key)
-
-  Record type 4: (uid record)
-  --------------
-    Informations about a userid
-    We do not store the userid but the hash value of the userid because that
-    is sufficient.
-
-     1 byte value 4
-     1 byte reserved
-     1 u32  LID  points to the directory record.
-     1 u32  next   next userid
-     1 u32  pointer to preference record
-     1 u32  siglist  list of valid signatures
-     1 byte uidflags
-     1 byte validity of the key calculated over this user id
-     20 bytes ripemd160 hash of the username.
-
-
-  Record type 5: (pref record)
-  --------------
-    This record type is not anymore used.
-
-     1 byte value 5
-     1 byte   reserved
-     1 u32  LID; points to the directory record (and not to the uid record!).
-           (or 0 for standard preference record)
-     1 u32  next
-     30 byte preference data
-
-  Record type 6  (sigrec)
-  -------------
-    Used to keep track of key signatures. Self-signatures are not
-    stored.  If a public key is not in the DB, the signature points to
-    a shadow dir record, which in turn has a list of records which
-    might be interested in this key (and the signature record here
-    is one).
-
-     1 byte   value 6
-     1 byte   reserved
-     1 u32    LID          points back to the dir record
-     1 u32    next   next sigrec of this uid or 0 to indicate the
-                    last sigrec.
-     6 times
-       1 u32  Local_id of signatures dir or shadow dir record
-       1 byte Flag: Bit 0 = checked: Bit 1 is valid (we have a real
-                            directory record for this)
-                        1 = valid is set (but may be revoked)
-
-
-
-  Record type 8: (shadow directory record)
-  --------------
-    This record is used to reserve a LID for a public key.  We
-    need this to create the sig records of other keys, even if we
-    do not yet have the public key of the signature.
-    This record (the record number to be more precise) will be reused
-    as the dir record when we import the real public key.
-
-     1 byte value 8
-     1 byte  reserved
-     1 u32   LID      (This is simply the record number of this record.)
-     2 u32   keyid
-     1 byte  pubkey algorithm
-     3 byte reserved
-     1 u32   hintlist  A list of records which have references to
-                       this key.  This is used for fast access to
-                       signature records which are not yet checked.
-                       Note, that this is only a hint and the actual records
-                       may not anymore hold signature records for that key
-                       but that the code cares about this.
-    18 byte reserved
-
-
-
-  Record Type 10 (hash table)
-  --------------
-    Due to the fact that we use fingerprints to lookup keys, we can
-    implement quick access by some simple hash methods, and avoid
-    the overhead of gdbm.  A property of fingerprints is that they can be
-    used directly as hash values.  (They can be considered as strong
-    random numbers.)
-      What we use is a dynamic multilevel architecture, which combines
-    hashtables, record lists, and linked lists.
-
-    This record is a hashtable of 256 entries; a special property
-    is that all these records are stored consecutively to make one
-    big table. The hash value is simple the 1st, 2nd, ... byte of
-    the fingerprint (depending on the indirection level).
-
-    When used to hash shadow directory records, a different table is used
-    and indexed by the keyid.
-
-     1 byte value 10
-     1 byte reserved
-     n u32  recnum; n depends on the record length:
-           n = (reclen-2)/4  which yields 9 for the current record length
-           of 40 bytes.
-
-    the total number of such record which makes up the table is:
-        m = (256+n-1) / n
-    which is 29 for a record length of 40.
-
-    To look up a key we use the first byte of the fingerprint to get
-    the recnum from this hashtable and look up the addressed record:
-       - If this record is another hashtable, we use 2nd byte
-        to index this hash table and so on.
-       - if this record is a hashlist, we walk all entries
-        until we found one a matching one.
-       - if this record is a key record, we compare the
-        fingerprint and to decide whether it is the requested key;
-
-
-  Record type 11 (hash list)
-  --------------
-    see hash table for an explanation.
-    This is also used for other purposes.
-
-    1 byte value 11
-    1 byte reserved
-    1 u32  next         next hash list record
-    n times             n = (reclen-5)/5
-       1 u32  recnum
-
-    For the current record length of 40, n is 7
-
-
-
-  Record type 254 (free record)
-  ---------------
-    All these records form a linked list of unused records.
-     1 byte  value 254
-     1 byte  reserved (0)
-     1 u32   next_free
-#+end_example
+  byte order.  The length of each record is 40 bytes.  The first
+  record of the DB is always of type 1 and this is the only record of
+  this type.
+
+  The record types: directory(2), key(3), uid(4), pref(5), sigrec(6),
+  and shadow directory(8) are not anymore used by version 2 of the
+  TrustDB.
+
+** Record type 0
+
+   Unused record or deleted, can be reused for any purpose.  Such
+   records should in general not exist because deleted records are of
+   type 254 and kept in a linked list.
+
+** Version info (RECTYPE_VER, 1)
+
+   Version information for this TrustDB.  This is always the first
+   record of the DB and the only one of this type.
+
+   - 1 u8 :: Record type (value: 1).
+   - 3 byte :: Magic value ("gpg")
+   - 1 u8 :: TrustDB version (value: 2).
+   - 1 u8 :: =marginals=. How many marginal trusted keys are required.
+   - 1 u8 :: =completes=. How many completely trusted keys are
+             required.
+   - 1 u8 :: =max_cert_depth=.  How deep is the WoT evaluated.  Along
+             with =marginals= and =completes=, this value is used to
+             check whether the cached validity value from a [FIXME
+             dir] record can be used.
+   - 1 u8 :: =trust_model=
+   - 1 u8 :: =min_cert_level=
+   - 2 byte :: Not used
+   - 1 u32 :: =created=. Timestamp of trustdb creation.
+   - 1 u32 :: =nextcheck=. Timestamp of last modification which may
+              affect the validity of keys in the trustdb.  This value
+              is checked against the validity timestamp in the dir
+              records.
+   - 1 u32 :: =reserved=.  Not used.
+   - 1 u32 :: =reserved2=. Not used.
+   - 1 u32 :: =firstfree=. Number of the record with the head record
+              of the RECTYPE_FREE linked list.
+   - 1 u32 :: =reserved3=. Not used.
+   - 1 u32 :: =trusthashtbl=. Record number of the trusthashtable.
+
+
+** Hash table (RECTYPE_HTBL, 10)
+
+   Due to the fact that we use fingerprints to lookup keys, we can
+   implement quick access by some simple hash methods, and avoid the
+   overhead of gdbm.  A property of fingerprints is that they can be
+   used directly as hash values.  What we use is a dynamic multilevel
+   architecture, which combines hash tables, record lists, and linked
+   lists.
+
+   This record is a hash table of 256 entries with the property that
+   all these records are stored consecutively to make one big
+   table. The hash value is simple the 1st, 2nd, ... byte of the
+   fingerprint (depending on the indirection level).
+
+   - 1 u8 :: Record type (value: 10).
+   - 1 u8 :: Reserved
+   - n u32 :: =recnum=.  A table with the hash table items fitting into
+              this record.  =n= depends on the record length:
+              $n=(reclen-2)/4$ which yields 9 for oure current record
+              length of 40 bytes.
+
+   The total number of hash table records to form the table is:
+   $m=(256+n-1)/n$.  This is 29 for our record length of 40.
+
+   To look up a key we use the first byte of the fingerprint to get
+   the recnum from this hash table and then look up the addressed
+   record:
+
+   - If that record is another hash table, we use 2nd byte to index
+     that hash table and so on;
+   - if that record is a hash list, we walk all entries until we find
+     a matching one; or
+   - if that record is a key record, we compare the fingerprint to
+     decide whether it is the requested key;
+
+
+** Hash list (RECTYPE_HLST, 11)
+
+   See hash table above on how it is used.  It may also be used for
+   other purposes.
+
+   - 1 u8 :: Record type (value: 11).
+   - 1 u8 :: Reserved.
+   - 1 u32 :: =next=.  Record number of the next hash list record or 0
+              if none.
+   - n u32 :: =rnum=.  Array with record numbers to values.  With
+              $n=(reclen-5)/5$ and our record length of 40, n is 7.
+
+** Trust record (RECTYPE_TRUST, 12)
+
+   - 1 u8 :: Record type (value: 12).
+   - 1 u8 :: Reserved.
+   - 20 byte :: =fingerprint=.
+   - 1 u8 :: =ownertrust=.
+   - 1 u8 :: =depth=.
+   - 1 u8 :: =min_ownertrust=.
+   - 1 byte :: Not used.
+   - 1 u32 :: =validlist=.
+   - 10 byte :: Not used.
+
+** Validity record (RECTYPE_VALID, 13)
+
+   - 1 u8 :: Record type (value: 13).
+   - 1 u8 :: Reserved.
+   - 20 byte :: =namehash=.
+   - 1 u8 :: =validity=
+   - 1 u32 :: =next=.
+   - 1 u8 :: =full_count=.
+   - 1 u8 :: =marginal_count=.
+   - 11 byte :: Not used.
+
+** Free record (RECTYPE_FREE, 254)
+
+   All these records form a linked list of unused records in the TrustDB.
+
+   - 1 u8 :: Record type (value: 254)
+   - 1 u8 :: Reserved.
+   - 1 u32 :: =next=.  Record number of the next rcord of this type.
+              The record number to the head of this linked list is
+              stored in the version info record.
 
 
 * GNU extensions to the S2K algorithm