Hi,
this is a question that I hope is convered in the literature on transparency logs, but what meaning do we assign to a single, isolated, cosignature?
If we have a *sequence* of cosigned tree heads (signed by a particular witness, ordered by increasing tree size), then each cosignature says that all tree leafs in previous cosigned trees are present in later trees. But a sigsum client only sees a single cosigned tree head, not the sequence. In particular, consider the case of the first cosignature of a particular witness, with no history.
So what exactly does that signature mean?
I suspect there are maybe some underlying assumptions or policys that should be spelled out somewhere.
Is this an reasonably accurate description? When I see a leaf node accompanied by a cosigned treehead and an inclusion proof leading up to that head, then I expect that the witness will raise some alarm if, sometime in the future, the log attempts to publish a tree head where the leaf no longer is present?
In this case, a single cosignature doesn't make any claim about the state of the log, it just states that the witness has observed this state, and hence that the witness has the information needed to detect future inconsistencies. More concisely: An isolated cosignature (without history) does not make a claim about the state of the log, it makes a claim about the state of the witness.
Does that make sense?
Regards, /Niels
On Thu, Nov 17, 2022 at 03:21:12PM +0100, Sigsum General wrote:
Hi,
this is a question that I hope is convered in the literature on transparency logs, but what meaning do we assign to a single, isolated, cosignature?
If we have a *sequence* of cosigned tree heads (signed by a particular witness, ordered by increasing tree size), then each cosignature says that all tree leafs in previous cosigned trees are present in later trees. But a sigsum client only sees a single cosigned tree head, not the sequence. In particular, consider the case of the first cosignature of a particular witness, with no history.
So what exactly does that signature mean?
"From my local vantage point, the log's state is append-only". This is a trivial claim when fetching the first tree head as there's no prior state, but after that the witness must require valid consistency proofs.
Note that a cosignature doesn't say there are no split-views, just that none has been presented to the witness. What convinces an end-user of global consistency is cosignatures from several independent witnesses.
I suspect there are maybe some underlying assumptions or policys that should be spelled out somewhere.
Is this an reasonably accurate description? When I see a leaf node accompanied by a cosigned treehead and an inclusion proof leading up to that head, then I expect that the witness will raise some alarm if, sometime in the future, the log attempts to publish a tree head where the leaf no longer is present?
Yep, alarm and of course not cosign that future inconsistent state.
In this case, a single cosignature doesn't make any claim about the state of the log, it just states that the witness has observed this state,
s/state/append-only state locally/
and hence that the witness has the information needed to detect future inconsistencies. More concisely: An isolated cosignature (without history) does not make a claim about the state of the log, it makes a claim about the state of the witness.
Does that make sense?
I disagree that there's no claim about the log's state. I agree that the central part is what (local append-only state) the witness is in.
-Rasmus
Rasmus Dahlberg rgdd@glasklarteknik.se writes:
On Thu, Nov 17, 2022 at 03:21:12PM +0100, Sigsum General wrote:
More concisely: An isolated cosignature (without history) does not make a claim about the state of the log, it makes a claim about the state of the witness.
Does that make sense?
I disagree that there's no claim about the log's state. I agree that the central part is what (local append-only state) the witness is in.
I think my argument is that a *pair* of cosignatures makes a claim about log state: It says that all leaves in the tree corresponding to the smaller cosigned tree are still present in the larger cosigned tree. Since the witness has either verified a consistency proof directly connecting the two trees, or a chain of such consistency proofs via some other tree heads that it has cosigned.
But a *single* cosignature doesn't: if there's no additional evidence, the verifier has to assume that this is the witness' very first cosignature.
I think I'd also like to argue that history of the log is not that interesting to a verifier about to decide whether or not to accept a logged signature. What's relevant is to establish that the signature of interest is observed by the witness, and hence, that future attempts by the log to erase it from history will be noticed.
To me, there appears to be an important link between witnesses and monitors. Consider the attack case, that an unauthorised signature is added to the log (e.g., to accompany a doctored software update). That can be detected, if the signature appears on the *monitor*'s view of the log. Does the witness cosignature imply that the signature will be observed also by the monitor? That seems a bit subtle, but I think it should, *if* the client and the monitor share witnesses. And on the other hand, in the somewhat pathologic case client and monitor trust disjoint sets of witnesses, there's no connection, and the log could let the two sets of witnesses see completely different trees, with no one noticing.
BTW, this might add an interesting requirement for log-witness protocol. It will make it harder for the log to sustain a split view if in the protocol, it has to commit to a tree head, *before* learning the identity of the witness asking for it. So it's desirable to enable the witness to be anonymous to the log up to the point where it provides a cosignature and reveals its key hash.
Regards, /Niels
Niels Möller via Sigsum-general sigsum-general@lists.sigsum.org writes:
But a *single* cosignature doesn't: if there's no additional evidence, the verifier has to assume that this is the witness' very first cosignature.
I think I'd also like to argue that history of the log is not that interesting to a verifier about to decide whether or not to accept a logged signature. What's relevant is to establish that the signature of interest is observed by the witness, and hence, that future attempts by the log to erase it from history will be noticed.
Let me try to wrap this up, after pondering the question for some more time. I'm approaching the question from the point of view of a client verifier about to decide whether to accept an update (or some other requested action) based on a "sigsum proof", including a relevant logged checksum, an inclusion proof binding it to some tree head, and cosignatures on that tree head.
I think I stand by "history of the log is not that interesting". Maybe a better angle is to say that the point of the cosignature is to evidence that the supposedly public log actually has published the item, in a way that is hard to "un-publish".
So the cosignature means that the item has been inserted into the sigsum machinery, promising that if other sigsum participants (in particular monitors and selected witnesses) act honestly and reliably, then an unauthorized signature will be detected in a timely manner. Which is a lot more complex than trying to understand the signature as the witness making a meaningful statement about the log's state.
Regards, /Niels
Niels Möller via Sigsum-general sigsum-general@lists.sigsum.org writes:
this is a question that I hope is convered in the literature on transparency logs, but what meaning do we assign to a single, isolated, cosignature?
I've pondered this question a bit more. And in the mean time, we have also changed the sigsum cosignatures to include a timestamp. For a start, I think it makes things clearer to think about the cosignature as the signature on a tree (rather than, as a signature on a published tree head), i.e., think about it as a signature on a set of leaves; that its a signature on a merkle tree root hash is an implementation detail.
In the current protocol, the cosignature covers the log's key hash (KH) (acting as the identity of a log), a root hash (TREE), and a timestamp (T). I think it can be understood as the witness making the following three claims:
1. I have observed TREE published by KH.
2. As of time T, it's the most recent publication I've seen from KH.
3. TREE includes all leaves from KH that I have ever cosigned.
For a proof verifier, claim (1) is the interesting one, since it's proof of logging in a known (and usually public) log. The benefit of this to the verifier is indirect, thanks to other actors in the sigsum system.
Claim (3) is related to monitoring, since it implies that when a monitor retrieves all leaves of TREE, it gets everything the witness has cosigned.
The relevance of claim (2) is a bit fuzzy to me, but it is related to the monitor's need to have a fresh view of the log.
From this view, the append-only property, and the witness' use of consistency proofs, is merely a means to make it practical and efficient for the witness to make claim (3). But it would in principle work just as fine if the witness signs and makes available the signed leaf sets by any other means.
I tink it's just confusing to think that the witness make some claim about the log being append-only or consistent. The witness makes a claim about an observation of a published tree, and a claim about that tree's relation to other trees that the witness itself has cosigned previously.
Regards, /Niels
sigsum-general@lists.sigsum.org
-
Niels Möller -
Rasmus Dahlberg