Table of Contents

Introduction
Problem Statement
General Notes
Proof of Recency
Including the OTS data in the PGP signature
Interpreting the results

Introduction

I want better PGP signature timestamping for Nullian Verification, git commits, investigative evidence, and even e-mail.

In the short to medium term, I intend to write code for this; but I have no spare development cycles right now. At this point, as I develop a specification for what I want to implement, I wish to solicit feedback from persons who have an expert-level technical understanding of both OpenTimestamps and OpenPGP.

This thread will be narrowly moderated. Please keep discussion strictly on-topic, and at a high technical level. Although I would love to help newbies learn OpenTimestamps, the purpose of this thread is development discussion; thus, I have deliberately made this post opaque for anybody who does not have deep technical knowledge of the subject matter. If you have non-expert questions or comments, please PM me. At some point, I intend to open an appropriate thread in Beginners & Help; but I think that is premature, when I am seeking to write new software to cover my intended use cases.

My apologies if this post is a bit of a coredump. At this point, I am essentially whiteboarding a large amount of information in haste. Literary, it is not; the technical content is here.

I may soon be gone for a few days here and t here. If so, I will catch up when I return; don’t worry, I do not intend to disappear again!

Problem Statement

My objective is to solve the following problems:

0. OTS only provides proof of past existence. When used with digital signatures, it thus provides a limited protection against the backdating of a signature, but no evidence that a signature has not been forward-dated at the time of its actual creation.

Although no single tool can prevent all deception, an integrated system with proof of both existence and recency would provide evidence preventing many possible deceptions hinged on the time at which a digital signature is made. An expert in the problem domain could interpret this evidence intelligently, in case of any dispute.
1. The existing integration of OTS with git is too specific to that use case. A generalized solution is needed, to cover other uses cases for the timestamping of PGP signatures.
2. The format of the OTS git integration is clunky and ad hoc. The OpenPGP standard specifies a binary format designed for extensibility. OTS data should be integrated into the OpenPGP signature itself!

General Notes

In the following, it is important to distinguish between signed and unsigned data. In OpenPGP terms, the signed data must be included in hashed subpackets within the signature packet; and the unsigned data must be included in unhashed subpackets. References: RFC 4880, §§ 5.2.3 and 5.2.3.2.

Some parts of my proposal could slightly more elegant, if I were to apply for new packet types from IANA. The registration procedure is “IETF Review”, i.e. red tape; and the OpenPGP Working Group is currently embroiled in what may be reasonably described as a flamewar over the direction of RFC4880bis. Thus instead, I plan to use § 5.2.3.16 Notation Data in the “user namespace” (signature subpacket type 20 (0x14) per § 5.2.3.1).

All OTS-related subpackets SHOULD NOT be marked critical (bit 7 of the subpacket type (§ 5.2.3.1)), unless it is desired to prevent a signature from being verified by software that does not understand my PGP-OTS subpackets.

Proof of Recency

My general proposal is to include a list of the most recent Bitcoin block hashes in hashed subpackets (thus, within the signed data). I am currently thinking of optimal ways to pack Notation Data subpackets with the binary hash, plus alleged block height and timestamp (which are a useful record for some use cases, if not incorrectly trusted for verification). Any verifier running a Bitcoin node could trustlessly verify that the signature’s Creation Time subpacket (§ 5.2.3.4) is soon after the referenced blocks, for a somewhat handwavy definition of “soon” which may depend on the specific use case.

I hereby seek feedback on the number of block hashes which should be included. With much handwaving, I feel like about ten blockhashes will provide adequately secure evidence for most any use case; but I do not want to base technical decisions on my own feelings and handwaving!

Question for Bitcoin experts: Realistically, how many block hashes need to be included to cover the case of a reorg? I have heard of a 7-block reorg, but that was a long time ago. In case of a large-scale malicious miner attack on the network, it is not inconceivable that we may get such a long reorg again.

Validation logic in the OTS-PGP verifier MUST include appropriate logic for handling cases in which the most recent referenced block(s) are unknown to the verifier’s node, but older referenced blocks still exist in the blockchain. Future work may include an interface for verification that blocks provided by the signer are valid orphans. Interpreting such subtle evidence SHOULD NOT be done by n00bs; but it may be useful for interpretation by an expert witness, in case the time of a high-value signature is ever disputed in some way that this could be relevant.

Another question for Bitcoin experts: Realistically, how many block hashes are needed to prevent a malicious party with significant mining hardware from somehow faking or manipulating the evidence? If you can think of any practical attacks, please post them with your estimation of how much hashpower would be required, and how many block hashes need to be listed in the signed data to provide sound evidence that your attack was not used by the signer!

Question for OpenPGP experts: Is it allowed to use multiple Notation Data subpackets with the same Notation Name in a signature? The standard only says, “There may be more than one notation in a signature.” If nobody here knows the answer, then I will need to examine some popular implementations to see if they would be confused, and maybe ask on the IETF OpenPGP list.

In concrete terms, for proof of recency, I tentatively plan to use multiple Notation Data hashed subpackets, —each with one blockhash and the corresponding block height and block timestamp. The subpackets must have the “human readable” flag cleared, and a Notation Name of "blockhash@opentimestamps.org" (if I can obtain permission for that—or else, a similar name at another domain). A verifier should interpret these as an array, and sort the subpackets by alleged blockheight.

Alternatively, I may need to invent a sort of sub-subpacket which packs multiple sets of block hash data into a single Notation Data subpacket.

Including the OTS data in the PGP signature

I plan to pack OTS data into a single unhashed Notation Data subpacket with Notation Name similar to "pgp-timestamp@opentimestamps.org" (or a similar name at another domain).

This way, the timestamp is carried with the PGP signature—where necessary, within OpenPGP’s own ASCII armour—without the type of kludge currently used by the OpenTimestamps git integration. This would Just Work for git commits, e-mail, software package distribution, PGP-signed business contracts, my Nullian Verification thread, or any other use case.

Unhashed subpackets are explicitly outside the signed data, and thus can be added, removed, or modified without invalidating the signature. Although I do not yet have experience performing such surgery on a signature, it looks trivial.

Signers SHOULD include a “complete” OTS timestamp, so that the signature contains all data necessary to verify the timestamp trustlessly—even if all of the calendar servers go bad or disappear.

Verifiers SHOULD tolerate an incomplete timestamp, to support use cases in which a signer reasonably cannot wait for blockchain confirmations before issuing the timestamp. (However, I do not want to make this a MUST; a verifier coded for a specific use case should be allowed to demand a complete timestamp.)

Verifiers SHOULD allow graceful upgrade of a PGP signature that is initially received with an incomplete timestamp, with an interface similar to the `ots upgrade` command.

Verifiers MUST gracefully tolerate edge cases in which different timestamps may exist for the same signature.

I don’t really have any questions about this, unless anybody can see problems that I do not see.

Interpreting the results

The OTS timestamp on a signature with signed proof of recency provides strong evidence that a signature was created within a time window delimited by two Bitcoin blocks X and Y. In practice, X and Y will probably not be sequential in most cases; but they should usually be within about 2–3 blocks of each other.

My scheme does NOT provide strong evidence of an explicit wall-clock time. Due to the way that Bitcoin block timestamps work, it is even possible that block timestamp of X may be later than the block timestamp of Y.

Question for Bitcoin experts: What is a reasonable heuristic for software interpreting an OpenPGP signature Creation Time subpacket relative to Bitcoin blocks? I think that verification should immediately fail with an error if the signature’s self-alleged time is more than 7200 seconds before X, or more than 7200 seconds after Y. Is there any better way to do this? To set a floor for the PGP timestamp for all possible edge cases, do I need to ask a Bitcoin node for the timestamps of the 11 blocks before X, and calculate the median?

I am willing to specify that a signer MUST have a reasonably accurate clock. Hate unauthenticated NTP? Good! Buy an inexpensive GPS device, and hook your ntpd up to gpsd. There is no excuse for running with a wildly inaccurate clock.

Anybody wishing better to understand timestamping issues is encouraged to start with the discussion in Peter Todd’s OTS announcement blog post, “What Can and Can’t Timestamps Prove?”