merged documentation improvements from ln5/rgdd

1 files changed, 141 insertions, 115 deletions

diff --git a/doc/design.md b/doc/design.md
index 535685b..4f7c06a 100644
--- a/doc/design.md
+++ b/doc/design.md
@@ -33,11 +33,11 @@ sigsum logging as pre-hashed digital signing with transparency.
 The signing party is called a _signer_.
 The user of the signed data is called a _verifier_.
 
-The problem with _just digital signing_ is that it is difficult to determine
-whether the signed data is _actually the data that should have been signed_.
-How would we detect if a secret signing key got compromised?
-How would we detect if something was signed by mistake, or even worse,
-if the signing party was forced to sign malicious data against their will?
+The problem with _digital signing on its own_ is that it is difficult to
+determine whether the signed data is _actually the data that should have been
+signed_.  How would we detect if a secret signing key got compromised?  How
+would we detect if something was signed by mistake, or even worse, if the
+signing party was forced to sign malicious data against their will?
 
 Sigsum logs make it possible to answers these types of questions.  The basic
 idea is to make a signer's _key-usage_ transparent.  This is a powerful building
@@ -46,7 +46,7 @@ block that can be used to facilitate verification of falsifiable claims.
 Examples include:
 - Everyone gets the same executable binaries
 	[\[BT\]](https://wiki.mozilla.org/Security/Binary_Transparency)
-- A domain does not serve malicious javascript
+- A web server does not serve malicious javascript
 	[\[SRI\]](https://developer.mozilla.org/en-US/docs/Web/Security/Subresource_Integrity)
 - A list of key-value pairs is maintained with a certain policy.
 
@@ -107,10 +107,6 @@ that a verifier is required to support.  Signers, monitors, and witnesses
 additionally need to interact with a sigsum log's line-terminated ASCII HTTP(S)
         [API](https://git.sigsum.org/sigsum/tree/doc/api.md).
 
-### 1.3 - Roadmap
-First we describe our threat model.  Then we give a bird's view of the design.
-Finally, we wrap up with an incomplete frequently asked questions section.
-
 ## 2 - Threat model
 We consider a powerful attacker that gained control of a signer's signing and
 release infrastructure.  This covers a weaker form of attacker that is able to
@@ -121,17 +117,18 @@ The fact that signing keys and related infrastructure components get
 compromised should not be controversial these days
 	[\[SolarWinds\]](https://www.zdnet.com/article/third-malware-strain-discovered-in-solarwinds-supply-chain-attack/).
 
-The attacker can also gain control of the log's signing key and infrastructure.
-This covers a weaker form of attacker that is able to sign log data and
-distribute it to a subset of isolated verifiers.  For example, this could have
-been the case when a remote code execution was found for a Certificate
-Transparency Log
+The same attacker also gained control of the signing key and infrastructure of a
+sigsum log that is used for transparency.  This covers a weaker form of attacker
+that is able to sign log data and distribute it to a subset of isolated
+verifiers.  For example, this could have been the case when a remote code
+execution was found for a Certificate Transparency Log
 	[\[DigiCert\]](https://groups.google.com/a/chromium.org/g/ct-policy/c/aKNbZuJzwfM).
 
-The overall system is said to be secure if a monitor can discover every signed
-checksum that a verifier would accept.  A log can misbehave by not presenting
-the same append-only Merkle tree to everyone because it is attacker-controlled.
-However, a log operator would only do that if it is likely to go unnoticed.
+The overall system is said to be secure if a log monitor can discover every
+signed checksum that a verifier would accept.
+A log can misbehave by not presenting the same append-only Merkle tree to
+everyone because it is attacker-controlled.
+The attacker would only do that if it is likely to go unnoticed, however.
 
 For security we need a collision resistant hash function and an unforgeable
 signature scheme.  We also assume that at most a threshold of independent
@@ -140,7 +137,7 @@ attempts
 	[split-view](https://datatracker.ietf.org/doc/html/draft-ietf-trans-gossip-05)
 and
 	[slow-down](https://git.sigsum.org/sigsum/tree/archive/2021-08-24-checkpoint-timestamp)
-attacks.   A log operator can at best deny service with these assumptions.
+attacks.   An attacker can at best deny service with these assumptions.
 
 ## 3 - Design
 An overview of sigsum logging is shown in Figure 1.  Before going into detail
@@ -160,7 +157,7 @@ we give a brief primer below.
                  |  +---------->| Monitor |<-------+  |proof
                  v              +---------+           v
                +---------+           |             +----------+
-               | witness |           | false       | Verifier |
+               | Witness |           | false       | Verifier |
                +---------+           | claim       +----------+
                                      v
                                 investigate
@@ -194,78 +191,63 @@ verify that this tree is fresh and append-only before cosigning it to achieve a
 distributed form of trust.  A tree leaf contains four fields:
 - **shard_hint**: a number that binds the leaf to a particular _shard interval_.
 Sharding means that the log has a predefined time during which logging requests
-are accepted.  Once elapsed, the log can be shut down.
+are accepted.  Once elapsed, the log can be shut down or be made read-only.
 - **checksum**: most likely a hash of some data.  The log is not aware of data;
 just checksums.
 - **signature**: a digital signature that is computed by a signer over the
-leaf's shard hint and checksum.
+selected shard hint and checksum.
 - **key_hash**: a cryptographic hash of the signer's verification key that can
 be used to verify the signature.
 
-A shard hint is included in the signed statement to prevent replays in a
-non-overlapping shard.  See details in Section 4.2.
-
 Any additional metadata that is use-case specific can be stored as part of the
 data that a checksum represents.  Where data is located is use-case specific.
 
 Note that a key hash is logged rather than the public key itself.  This reduces
 the likelihood that an untrusted key is discovered and used by mistake.  In
-other words, verifiers and monitors must locate keys and trust them explicitly.
+other words, verifiers and monitors must locate signer verification keys
+independently of logs, and trust them explicitly.
 
 ### 3.2 - Usage pattern
 #### 3.2.1 - Prepare a request
-A signer selects a shard hint and a checksum that should be logged.  The
-selected shard hint represents an abstract statement like "sigsum logs that are
-active during 2021".  The selected checksum is most likely the output of a
-hash function.  For example, it could be the hash of an executable binary.
+A signer selects a checksum that should be logged.  For example, it could be the
+hash of an executable binary or something else.
+
+The signer also selects a shard hint representing an abstract statement like
+"sigsum logs that are active during 2021".  Shard hints ensure that a log's
+leaves cannot be replayed in a non-overlapping shard.
 
-The selected shard hint and checksum are signed by the signer.  A shard hint is
-incorporated into the signed statement to ensure that a log's leaves cannot be
-replayed in a non-overlapping shard by a good Samaritan.
+The signer signs the selected shard hint and checksum.
 
 The signer also has to do a one-time DNS setup.  As outlined below, logs will
 check that _some domain_ is aware of the signer's verification key.  This is
-part of a defense mechanism that helps us combat log spam.
+part of a defense mechanism that helps log operators to deal with log spam.
+Once present in DNS, a verification key can be used in subsequent log requests.
 
 #### 3.2.2 - Submit request
 Sigsum logs implement an HTTP(S) API.  Input and output is human-readable and
-uses a simple ASCII format.  A more complex parser like JSON is not needed
-because the exchanged data structures are primitive enough.
-
-A signer submits their shard hint, checksum, signature, and public verification
-key as key-value pairs.  The log uses the public verification key to check that
-the signature is valid, then hashes it to construct the leaf's key hash.
-
-The signer also submits a _domain hint_.  The log will download a DNS TXT
-resource record based on the provided domain name.  The downloaded result must
-match the public verification key hash.  By verifying that all signers control a
-domain that is aware of their verification key, rate limits can be applied per
-second-level domain.  You would need a large number of domain names to spam the
-log in any significant way if rate limits are not too loose.
-
-Using DNS to combat spam is convenient because many signers already have a
-domain name.  A single domain name is also relatively cheap.  Another benefit is
-that the same anti-spam mechanism can be used across several independent logs
-without coordination.  This is important because a healthy log ecosystem needs
-more than one log to be reliable in case of downtime or unexpected events like
-        [cosmic rays](https://groups.google.com/a/chromium.org/g/ct-policy/c/PCkKU357M2Q/).
+use a simple ASCII format.  A more complex parser like JSON is not needed
+since the data structures being exchanged are primitive enough.
 
-A signer's domain hint is not part of the logged leaf because key management is
-more complex than that.  A separate project should focus on transparent key
-management.  Our work is about transparent _key-usage_.
+The signer submits their shard hint, checksum, signature, public verification
+key and domain hint as ASCII key-value pairs.  The log verifies that the public
+verification key is present in DNS and uses it to check that the signature is
+valid, then hashes it to construct the Merkle tree leaf as described in
+Section 3.1.
 
-A sigsum log _tries_ to incorporate a leaf into its Merkle tree if a logging
-request is accepted.  There are however no _promises of public logging_ as in
-Certificate Transparency.  Therefore, sigsum logs do not provide low-latency.  A
-signer has to wait for an inclusion proof and a cosigned tree head.
+When a submitted logging request is accepted, the log _tries_ to incorporate the
+submitted leaf into its Merkle tree.  There are however no _promises of public
+logging_ as in Certificate Transparency.  Therefore, sigsum logs do not provide
+low latency---the signer has to wait for an inclusion proof and a cosigned tree
+head.
 
 #### 3.2.3 - Wait for witness cosigning
-Sigsum logs freeze a tree head every five minutes.  Cosigning witnesses poll the
-logs for so-called _to-sign_ tree heads, verifying that they are fresh and
-append-only before doing a cosignature operation.  Cosignatures are posted back
-to the logs so that signers can easily fetch the finalized cosigned tree heads.
+Sigsum logs periodically freeze the most current tree head, typically every five
+minutes.  Cosigning witnesses poll logs for so-called _to-sign_ tree heads and
+verify that they are fresh and append-only before doing a cosignature operation.
+Cosignatures are posted back to logs so that signers can easily fetch finalized
+cosigned tree heads.
 
-It takes five to ten minutes before a signer's distribution phase can start.
+It thus takes five to ten minutes before a signer's distribution phase can start.
 The added latency is a trade-off that simplifies sigsum logging by removing the
 need for reactive gossip-audit protocols
 	[\[G1,](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7346853)
@@ -276,78 +258,83 @@ need for reactive gossip-audit protocols
 Use-cases like instant certificate issuance are not supported by design.
 
 #### 3.2.4 - Distribution
-After a signer collected proofs of public logging the distribution phase can
+Once a signer has collected proofs of public logging the distribution phase can
 start.  Distribution happens using the same mechanism that is normally used for
 the data.  For example, on a website, in a git repository, etc.
+Signers distribute at least the following pieces:
 
 **Data:**
-the signer's data.  It can be used to reproduce a logged checksum.
+the signer's data, for example an executable binary.  It can be used to
+reproduce a logged checksum.
 
 **Metadata:**
-a signer's shard hint, signature, and verification key hash.  Note that the
-combination of data and metadata can be used to reconstruct the logged leaf.
+the shard hint, the signature over shard hint and checksum, and the verification
+key hash used in the log request.  Note that the combination of data and
+metadata can be used to reconstruct the logged leaf.
 
 **Proof:**
-an inclusion proof that leads up to a cosigned tree head.
+an inclusion proof that leads up to a cosigned tree head.  Note that _proof_
+refers to the collection of an inclusion proof and a cosigned tree head.
 
 #### 3.2.5 - Verification
-A verifier should only accept the distributed data if these criteria hold:
-1. The signer's checksum is correct for the distributed data.
-2. The signer's signed statement is valid for the specified public key.
-3. The provided tree head can be reconstructed from the logged leaf and 
+A verifier should only accept the distributed data if the following criteria hold:
+1. The data's checksum and shard hint are signed using the specified public key.
+2. The provided tree head can be reconstructed from the logged leaf and
 its inclusion proof.
-4. The provided tree head is from a known log with enough valid cosignatures.
+3. The provided tree head is from a known log with enough valid cosignatures.
 
 Notice that there are no new outbound network connections for a verifier.
-Therefore, a proof of public logging is only as convincing as the tree head that
-an inclusion proof leads up to.  Sigsum logs have trustworthy tree heads due to
-using a variant of witness cosigning.  In other words, a verifier cannot be
-tricked into accepting some data whose checksum have yet to be publicly logged
-unless the attacker controls more than a threshold of witnesses.
+Therefore, a verifier will not be affected by future log downtime since the
+signer already collected relevant proofs of public logging.  Log downtime may be
+caused by temporary operational issues or simply because a shard is done.
 
-#### 3.2.6 - Monitoring
-An often overlooked step is that transparency logging falls short if no-one keeps
-track of what appears in the public logs.  Monitoring is necessarily use-case
-specific in sigsum.  At minimum, you need to locate relevant public keys.  You
-may also need to be aware of how to locate the data that a checksum represents.
+The lack of external communication means that a proof of public logging cannot
+be more convincing than the tree head an inclusion proof leads up to.  Sigsum
+logs have trustworthy tree heads thanks to using a variant of witness cosigning.
+A verifier cannot be tricked into accepting data whose checksum have not been
+publicly logged unless the attacker controls more than a threshold of witnesses.
 
-It should also be noted that sigsum logging can facilitate detection of attacks
-even if a verifier fails open by enforcing the third and fourth criteria partially
-in Section 3.2.5.  For example, the fact that a distribution mechanism does not
-serve proofs of public logging could indicate that there is an ongoing attack
-against a signer's distributed infrastructure.  A monitor may detect that.
+#### 3.2.6 - Monitoring
+An often overlooked step is that transparency logging falls short if no-one
+keeps track of what appears in the public logs.  Monitoring is necessarily
+use-case specific in sigsum.  At a minimum, monitors need to locate relevant
+public keys.  They may also need to be aware of how to locate the data that
+logged checksums represent.
 
 ### 3.3 - Summary
 Sigsum logs are sharded and shut down at predefined times.  A sigsum log can
 shut down _safely_ because verification on the verifier-side is not interactive.
+
 The difficulty of bypassing public logging is based on the difficulty of
 controlling enough independent witnesses.  A witness checks that a log's tree
-head is correct before cosigning.  Correct refers to fresh and append-only.
+head is correct before cosigning.  Correctness includes freshness and the
+append-only property.
 
 Signers, monitors, and witnesses interact with the logs using an ASCII HTTP(S)
-API.  A signer must prove that they own a domain name as an anti-spam mechanism.
-No data and rich metadata is logged to protect the log operator from poisoning.
-It also keeps log operations simpler because there are fewer bytes to manage.
+API.  A signer must prove that they control a DNS domain name as an anti-spam
+mechanism.  No data or rich metadata is being logged, to protect the log
+operator from poisoning.  This also keeps log operations simpler because there
+are less data to manage.
 
-Verifiers interact with the logs indirectly through their signer's existing
+Verifiers interact with logs indirectly through their signer's existing
 distribution mechanism.  Signers are responsible for logging signed checksums
-and distributing necessary proofs of public logging.  Monitor discover signed
-checksums in the logs, generating alerts if any key-usage is inappropriate.
+and distributing necessary proofs of public logging.  Monitors discover signed
+checksums in the logs and generate alerts if any key-usage is inappropriate.
 
 ### 4 - Frequently Asked Questions
-#### 4.1 - What parts of the design are we still thinking about?
+#### 4.1 - What parts of the design are up for debate?
 A brief summary appeared in our archive on
 	[2021-10-05](https://git.sigsum.org/sigsum/tree/archive/2021-10-05-open-design-thoughts?id=5c02770b5bd7d43b9327623d3de9adeda2468e84).
 It may be incomplete, but covers some details that are worth thinking more
-about.  We are still open to remove, add, or change things if it is motivated.
+about.  We are still open to remove, add, or change things.
 
 #### 4.2 - What is the point of having a shard hint?
 Unlike TLS certificates which already have validity ranges, a checksum does not
 carry any such information.  Therefore, we require that the signer selects a
-shard hint.  The selected shard hint must be in a log's shard interval.  A shard
-interval is defined by a start time and an end time.  Both ends of the shard
-interval are inclusive and expressed as the number of seconds since the UNIX
-epoch (January 1, 1970 00:00 UTC).
+shard hint.  The selected shard hint must be within a log's shard interval.  A
+shard interval is defined by a start time and an end time.  Both ends of the
+shard interval are inclusive and expressed as the number of seconds since the
+UNIX epoch (January 1, 1970 00:00 UTC).
 
 Without sharding, a good Samaritan can add all leaves from an old log into a
 newer one that just started its operations.  This makes log operations
@@ -360,13 +347,52 @@ set it as large as possible.  If a verified timestamp is needed to reason about
 the time of logging, you may use a cosigned tree head instead
 	[\[TS\]](https://git.sigsum.org/sigsum/commit/?id=fef460586e847e378a197381ef1ae3a64e6ea38b).
 
-#### 4.3 - XXX
-- Why not store data in the log?  XXX: answered enough already?
-- Why not store rich metadata in the log? XXX: answered enough already?
-- What (de)serialization parsers are needed and why?
-- What cryptographic primitives are supported and why?
-- What thought went into witness cosigning?  Compare with other approaches, and
-should include `get-tree-head-*` endpoints in more detail.
-- Are there any privacy concerns?
-- How does it work with more than one log?
-- What policy should a verifier use?
+A log operator that shuts down a completed shard will not affect verifiers.  In
+other words, a signer can continue to distribute proofs that were once
+collected.  This is important because a checksum does not necessarily expire.
+
+#### 4.3 - What is the point of having a domain hint?
+Domain hints help log operators combat spam.  By verifying that every signer
+controls a domain name that is aware of their public key, rate limits can be
+applied per second-level domain.  You would need a large number of domain names
+to spam a log in any significant way if rate limits are not set too loose.
+
+Notice that the effect of spam is not only about storage.  It is also about
+merge latencies.  Too many submissions from a single party may render a log
+unusable for others.  This kind of incident happened in the real world already
+	[\[Aviator\]](https://groups.google.com/a/chromium.org/g/ct-policy/c/ZZf3iryLgCo/m/rdTAHWcdBgAJ).
+
+Using DNS as an anti-spam mechanism is not a perfect solution.  It is however
+better than not having any anti-spam mechanism at all.  We picked DNS because
+many signers have a domain.  A single domain name is also relatively cheap.
+
+A signer's domain hint is not part of the logged leaf because key management is
+more complex than that.  A separate project should focus on transparent key
+management.  Our work is about transparent _key-usage_.
+
+We are considering if additional anti-spam mechanisms should be supported.
+
+#### 4.4 - What parts of witness cosigning are not done?
+There are interesting policy aspects that relate to witness cosigning.  For
+example, what witnessing policy should a verifier use and how are trustworthy
+witnesses discovered.  This is somewhat analogous to a related policy question
+that all log ecosystems must address.  Which logs should be considered known?
+
+We do however think that witness cosigning could be done _from the perspective
+of a log and its operator_.  The
+	[sigsum/v0 API](https://git.sigsum.org/sigsum/tree/doc/api.md)
+supports witness cosigning.  Policy aspects for a log operator are easy because
+it is relatively cheap to allow a witness to be a cosigner.  It is not a log
+operator's job to determine if any real-world entity is trustworthy.  It is not
+even a log operator's job to help signers and verifiers discover witness keys.
+
+Given a permissive policy for which witnesses are allowed to cosign, a signer
+may not care for all retrieved cosignatures.  Unwanted ones can simply be
+removed before distribution to a verifier takes place.  This is in contrast to
+the original proposal by
+	[Syta et al.](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7546521),
+which puts an authority right in the middle of a slowly evolving witnessing policy.
+
+#### 4.5 - More questions
+- What are the privacy concerns?
+- Add more questions here!