Fixpoint

2020-03-04

Bitcoin transactions and their signing, 2: attachment

Filed under: Bitcoin, Software — Jacob Welsh @ 20:10

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.

  1. 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? [^]
  2. 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. [^]
  3. 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. [^]
  4. 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? [^]
  5. 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. [^]

3 Comments »

  1. 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.

    mircea_popescu: ie, if "selection doesn't work for me" "why not ?" "because what i want to select recurs", give some thought whether indeed "selection is broken and should be fixed". WHY do you want to select something THAT RECURS, and recurs so much it actually doesn't allow you to extend the context slightly, one character at a time, resolving your problem ?
    mircea_popescu: maybe what you're trying to select isn't something you should be selecting as part of what you're trying to do because what you;re trying to do is actually broken upstream. ODDS ARE.
    mircea_popescu: god put ~exactly no clues~ permitting one to bootstrap out of the ~necessary~ [http://trilema.com/2015/recursive-dunning-kruger/][d-k recursion]. god put no such clues in ~deliberately~, and god also made it necessary in the first place. because god's an asshole.
    mircea_popescu: the only available support for such bootstrap is this kind of indicia, "why are my self-perceived needs conflict with my betters' designs". it could, [http://trilema.com/2017/dupa-dealuri/?b=The%20secret&e=altogether#select][surely], be the case they're fucked in the head. i'm sure they often are.
    mircea_popescu: nevertheless -- not all problems one can persuade himself into perceiving are actually worth solving.
    mircea_popescu: there's exactly no need to "stop rape", for instance. "being special" (defined as, "never being raped") is not some kind of "universal right of womanhood". no woman's born entitled to be special, she's born to be used, like any other blade of grass on this here GREEN earth. that specialdom may arise, as a mist, RETROSPECTIVELY, is one thing. but the problem needs no "solving" -- you don't wanna take the cock, don't. see ho
    mircea_popescu: w far that gets you and bother whoever cares about it.
    mircea_popescu: "oh but mp, surprise sex is inconvenient" "yes, i'm sure it is"
    mircea_popescu: "i thought this was uncontroversial" "yes, that's how it usually goes."
    mircea_popescu: the persuasive universe is actually very much like a fungal infection of the mind : it grows nicely, i'm sure, but in so doing it misuses a fundamental other thing, that actually has a function independent of ever-growing fungal blather.
    mircea_popescu: the dichotomy between the subjective life of the subject and the demands of the outside structure ~is creative~. this is specifically the mechanism through which it is creative : "i wonder why it is i want something that these idiots didn't put in". one possible outcome of a correct such evaluation is, indeed, "jesus fuck they're idiots". however, ANOTHER possible outcome is the ~EXTREMELY~ valuble bootstrap out of d-k rec
    mircea_popescu: ursion.
    mircea_popescu: it's valuable because it is rare, and because it is, quite pointedly, going against god's own plans with you.
    mircea_popescu: if one just goes by the persuasion tradewinds, this lever's permanently stuck to position one ; and ridiculous nonsense flows downstream, superficially visible as "[http://trilema.com/2015/the-squares-and-the-holes/?b=Powerful&e=badly#select][old men in power have been behaving badly]" or w/e currently fashionable cri de guerre of the retard camp.
    mircea_popescu: this isn't actually the problem though ; as well documented on trilema, the effect on powerful old men an' their behaviour of the tavern wench consensus is still the nil it's ever been.
    mircea_popescu: the subjective paralysis is actually the problem. participating in the tavern wench chorus as to how bad your owner is prevents you from fucking thinking, or growing the fuck up (the two being related).
    mircea_popescu: and participation ~doesn't take all that much~. that's why it exists, after all, because it's easy, because it is in fact even easier than the [http://trilema.com/2014/the-gui-the-twerk-and-the-most-valuable-resource/][very little] use them powerful old men behaving badly might put a dumb wench towards.
    mircea_popescu: in fact, all it really takes is this conviction that a problem once perceived's thereby an' therefore also a problem that needs solving. NOT SO.
    mircea_popescu: it could be, of fucking course, there's no denying that. but there's another step in there, and not to be skipped over.
    mircea_popescu: and it can not even be explained JUST HOW!!! creative that thing that's creative actually is. let's look at one example : mp is, as a factual matter, the one who needs most things not put in. mp apparently needs to walk his bitches on a leash downtown, which romania doesn't even have words for, every newspaper in the country must drop whatever it was doing, selling cheap chinesiums, to talk about mp's weird needs now, and
    mircea_popescu: how it all relates to the system.
    mircea_popescu: erryone's happy with a girl to worship at home, just put her into this one shrineroom and worship there now and again ; mp apparently needs multiple (what! how!) and ~somehow even manages this~, for years, decades, it's not a wish-perceived fantasy, he lives like this ?!
    mircea_popescu: yet mp is also the ~least~ angry at "the system". how the fuck could this be ? is mp insane ? if everyone's so fucking pissed off over epsilon, "they gave us 9000 things but we're missing like... three. burn it all down", what the fuck's mp supposed to say, he has to have his fucking food flown in / slave made, and clothes flown in across the world and everything else.
    mircea_popescu: yet strangely mp doesn't mind nearly as much as the bottom centile of the "red pill" crowd. how the fuck ?! is it because he's a jew that he doesn't suspect jews are in charge ? what the fuck's going on here ?!
    mircea_popescu: ~the dichotomy is creative~. we don't have many (in the sense of : not any) alternative leverage points available. gotta use what's there.
    mircea_popescu: in fact, the reason i take the time to explain how various shits work, unpopular as they may be, is because i put the time in to actually understand how they do in fact work ; and i did that not because i was bored, or because i was desperate to find something to pour some of this time into, i have like a well of time at home and it's overflowing so you gotta put some in all availavble receptacles or else it floods the hou
    mircea_popescu: se, so i have 500 gallon jugs with time lying about.
    mircea_popescu: no, tis outta respect. i will take the time to type something out, an old poem, whatever, for similar reasons : some things are worth it. and they get worth it through occasionally, ever so occasionally, doing you that rare and radiant wonder of a favour, where "it turns out" aka you finally deign to fucking notice you were doing something stupid.
    diana_coman: this thread will be mandatory reading for #o residents

    Comment by Robinson Dorion — 2021-11-24 @ 13:41

  2. @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

  3. 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

RSS feed for comments on this post. TrackBack URL

Leave a comment

Powered by MP-WP. Copyright Jacob Welsh.