Having outlined the shape of the building block provided by digital signatures, we now face the potential problem of how to attach signatures to the messages they sign. The one hard requirement for any attachment scheme is that the verification function can work, that is, can answer unambiguously whether a signature is valid for a specific message and key. I will explore the space of possible approaches here,(i) then describe the one used in Bitcoin.
The simplest approach is to say: "what problem?" That is, treat the message and signature as separate objects (bitstrings, numbers, files or however you like to think of them) and use some external system to organize them. This is known in the traditional GPG toolset as detached signing. It has its advantages, besides the obvious "less work to implement". The original, unmodified message is directly available to the reader and his tools. New signatures can be added to a collection without duplicating or modifying the message object, and thus without needing further verification that they in fact refer to the same message. These properties are exploited in present manifestations of the V version control concept.
Assuming one does indeed want attached signatures, then, the first option is to package the message and signature together in some container format. Depending on how it's done, this can preserve the advantage that at least a semblance of the original message is readily visible in plain text, as with GPG clearsigning.(ii) New signatures can be added either with support from the container format, producing a single multiply-signed document, or without such support, either by nesting (such that each new signature references the previous stack) or duplication.
A second option, when the message represents a formal data structure, is to embed signatures in that structure itself in an application-specific way. At first sight this appears to be a circular data dependency: how can a signature be computed for a message that includes a representation of that signature?(iii) However, this can be worked around by applying a transformation to clip or whiteout the signature field at both signing and verification time.
The third and final option is to generalize the previous into a flexible or perhaps even universal embedding scheme. For example, signatures can be wrapped in whatever comment delimiters are available in a programming language, as seen in Mircea Popescu's recent proposal.(iv)
Bitcoin transactions, we can now say, use option #2: format-specific embedding, though with some added complications as follows.
The signature on each input is wrapped using the "script" encoding, in a field originally named "scriptSig", and its interpretation is determined by a corresponding script in the linked output being spent, originally "scriptPubKey". If we constrain our interest to transactions in the standard pay-to-pubkey-hash form, these considerations reduce to a formality.
The whiteout procedure is basically to replace the scriptSig on each input with an empty script. This implies the signatures are independent of each other. The twist, though, is that for the input for which a signature is being computed, the scriptSig is replaced instead by the corresponding scriptPubKey. I can't see any security advantage in doing this, since the previous output is already referenced by a unique identifier(v) covered by the signature. The result is that a different message must be signed for each input, and transaction verification takes quadratic time with respect to the number of inputs. This makes for a good reminder that the Bitcoin protocol externalizes much of the cost of transacting onto all node operators, and unless a satisfactory solution to that tough problem is deployed, transaction throughput must be kept a scarce resource.
To be continued.
- I struggled more than usual in writing about these, perhaps indicating I didn't grasp them as well as I'd thought. I don't claim to be equipped to discuss why one choice might be philosophically preferable to others; yet neither can I take a "purely technical" approach since cryptography is necessarily shaped as much from above by its utility to human society as from below by mathematical possibility. Maybe search the logs? [^]
- That format however incurs further complexity from tackling the additional perceived problems of linefeed normalization and in-band bracketing for inclusion in a larger text, with the drawback of having to quote instances of the magical bracket sequence in the signed message. [^]
- Such a message can be conceived as a fixpoint of the hash-sign-attach pipeline, but finding one in practice would seem to constitute a severe break in the cryptographic primitives. [^]
- It's not yet clear to me if or how this can be implemented reliably. For starters, how would you distinguish actual signatures from, say, quoted signatures, without knowing the lexical rules of the target language? How would the "whiteout" work to produce the same hash after addition of new signatures, without knowing same? [^]
- Well, not quite unique but at least identifying its contents including the scriptPubKey in question, to the extent you trust SHA256. And if you don't trust that, the signature hash would seem to be the bigger problem. [^]
Since the logs got converted from the flask logger to the mp-wp logger and Diana deprecated the flask logger on ossasepia, that second, "potential problem" link got broken. It starts here and quoted in full below.
Comment by Robinson Dorion — 2021-11-24 @ 13:41
@Robinson Dorion: well yes, lots of links were broken by that rift, including on your blog. So I don't quite get it, you're going to fix them one at a time as you hit them or what's the plan here?
That's some low-effort irc-to-html formatting too.
Comment by Jacob Welsh — 2021-11-28 @ 00:33
If it's any help, the links for #eulora and #ossasepia can be fixed throughout a whole mp-wp blog with a simple script to assemble and run the correct update command, see the example in footnote 2. As the archive is exhaustive, one can even make the simplest script that just creates and runs the update for each line in the archive since that will replace all links that exist without having any ill effects otherwise.
Comment by Diana Coman — 2021-11-28 @ 08:44
@Jacob Welsh, there wasn't much of a plan and I know I still have broken links. It took me a while to even track it down since even Lobbes' logger is down now too, so I just decided to save it. You're right about the low-effort irc-html conversion, sorry about that.
Comment by Robinson Dorion — 2021-12-01 @ 16:48
If it helps for tracking them down, http://ossasepia.com/available_resources/old_logs.gz can be used to look up messages/dates by ossabot line number, and http://btcbase.org/log-raw/ for assbot/a111 line number (and easy local grep is an added win).
And thanks for bringing it up in any case.
Comment by Jacob Welsh — 2021-12-01 @ 17:37
And re #3, there is http://fixpoint.welshcomputing.com/2021/healing-my-old-ossasepia-log-links/ since apparently pingbacks don't work when linking to comments or something.
Comment by Jacob Welsh — 2021-12-01 @ 17:39