Skip to content

Instantly share code, notes, and snippets.

@afk11
Last active September 6, 2017 15:55
Show Gist options
  • Save afk11/ab3b303f46f3707b308a6c2dd57ac52c to your computer and use it in GitHub Desktop.
Save afk11/ab3b303f46f3707b308a6c2dd57ac52c to your computer and use it in GitHub Desktop.
BitcoinJS transaction signing internals - update, enhancements, to the moon

It starts with a Signer..

s = Signer(tx)

The signer lets you peek at InputSigners.

iS = s.input(nIn, txOut, [rs], [ws])

this step involves classification of
* bare scriptPubKey: txOut
* p2sh: txOut -> rs
* p2wsh: txOut -> ws
* p2sh|p2wsh: txOut -> rs -> ws

(calls new InputSigner(tx, nIn, txOut, [rs], [ws]))

It is at this moment we know whether bitcoinjs supports signing the script.
These scripts are subset of scripts we can validate (with this data & an interpreter)
If we have this data, we can safely decode signatures, keys, tell if the input
is fully signed, etc. The results of this step inform every decision later. 

We could encapsulate [rs], [ws] in an options object, because they (unlike
the txOut) are optional - the transaction may be fully/partially signed
meaning the details arent _required_ but can be checked against, or, the 
transaction may be unsigned and the [rs]/[ws] _would be required_.

Basic properties

iS.nIn          = nIn
iS.tx           = tx
is.txOut        = meh. could just be `inputValue`, since spk is below.
iS.scriptPubKey = property w/ object containing the scriptPubKey, it's type, and 
                  the hashes/public keys embedded in the script
iS.redeemScript = property w/ object containing the redeemScript, it's type, and 
                  the hashes/public keys embedded in the script
                  (only set if scriptPubKey.type = p2sh)
iS.witnessScript= property w/ object containing the witness, it's type, and 
                  the hashes/public keys embedded in the script
                  (only set if scriptPubKey.type = p2wsh | redeemScriptType = p2wsh)
iS.signScript   = points to iS.scriptPubKey, or iS.redeemScript, or iS.witnessScript.

ScriptData

Suggest we make an object for the iS.ScriptPubKey/redeemScript/witnessScript fields with the properties:

  • type
  • script
  • values
    • if P2SH, it's the scriptHash
    • if P2PKH, it's the pubKeyHash
    • if P2PK, it's the publicKey
    • if Multisig, it's the publicKeys
    • if P2WPKH, it's the pubKeyHash
    • if P2WSH, it's the scriptHash.

Maintained during signing/extraction of a CHECKSIG op

checksig.opcode       = the opcode, or the type of script (p2pkh, p2pk, multisig) would do
checksig.isVerify     = stateful value, should cause no value to be pushed to the stack during extraction (relevant for IF scripts)
checksig.isRequired   = relevant for IF scripts, and whether the CHECKSIG operation was _expected_ to fail
checksig.requiredSigs = required number of sigs
checksig.publicKeys   = all the public keys involved in the signing. May not all be
                  known. May not all be valid public keys, so should store the Buffer.
                  (https://www.blocktrail.com/BTC/tx/0000a524025cca89db9743a6ec940d2a987bbb7f19f392adb3912b85c7a9a12f?txinIdx=3)
                  sign can also add the public key if it wasn't known before (unsigned P2PKH)
                  but is required for the scriptSig

checksig.signatures   = all the signatures extracted, or created. This should be indexed the
                  same as the publicKeys. 
                  
* These fields should be indexed using the same keys. This allows numeric lookup
  of each public key, hence we can determine if a key signed, etc.
* Please also note that if we want to sign more advanced scripts (eg, [alice] CHECKSIG [bob] CHECKSIG)
  we need to plan for there being multiple signing opcodes meaning multiple
  arrays of publicKeys/signatures (one for each signing opcode)                    

Main functions

(see ScriptData)

This function is the opposite to buildStack. It takes a stack and works out [requiredSigs, publicKeys, signatures] This is where we could do some pseudo validation (not full script interpreter, but templated extraction + ECDSA verification)

extractSignatures(scriptData, stackValues, sigVersion)
=> {requiredSigs: x, publicKeys = [], signatures = []}

This function can take [rs], [ws] (make this the opt object?), the scriptPubKey, the scriptSig, and the witness. It performs the classification of the input. (not strictly the required params if we track state, but this is what it needs)

This function calls extractSignatures.

solve(optsObject, scriptPubKey, scriptSig, witness)
=> {sigVersion: x ?, signScript = {}}
=> (plus the result of extractSignatures, which 
    is probably saved to the iS state)

I suggest calling this function is done in TransactionBuilder or whereever we are creating the iSigner instance. It's a private detail, we don't return an inputSigner unless all this is successful, otherwise it would imply we don't support the type, or had invalid data.

This function, we already have. It takes []publicKeys, []signatures and the scriptTypes, and knows how to determine which data to pass into buildStack.

buildInput(input, allowIncomplete)
=> {script: '', witness: []}

Signing related functions

This function takes a private key and the hashType, and will attempt to sign the input.

sign(privateKey, hashType)
=> true or false if signing occured

Will sign every position with that key.. I think we can start to expose really specific signing functions to advanced people can do it how they like.

We could consider adding a verify function. It would rely on templating and pubkey/signature extraction, and could do some simple checks before doing a raw ECDSA verification. The burden of a scriptInterpreter is too large right now for us, but this is a reasonable first step (are the signatures I just produced valid)

verify()
=> bool

Introspective functions for input signatures

This function is a pure function (no state change), for calculating a signature hash for the input in an unsafe way (accepts arbitrary user data). Advanced, could be left out/private

  • calculateSigHashUnsafe (scriptcode, sigHashType, sigVersion)

This function is a pure function (no state change), for safely calculating a signature hash, because we have all the state to do this after classification. Therefore, the sighash returned will be correct for the requested hashType.

  • getSighash(sigHashType)

This function returns whether the input is fully signed:

  • isFullySigned()

This function returns the number of signatures required to sign the input.

  • getRequiredSigs()

This function returns an ordered map of [keyIdx => signature|null] for each publicKey. See earlier comment about there being several of these arrays depending on how far we go (one for each {CHECKSIG,CHECKMULTISIG}{,VERIFY} operation)

  • getSignatures

This function returns an ordered map of [keyIdx => keyBuffer] Again, only constrain ourselves to knowing the buffers, because not every public key is valid (see that mastercoin example, where they redeem a 1-of-2 multisig w/ 1 valid key, 1 invalid key)

These functions return the objects containing state about the scriptPubKey, redeemScript, witnessScript, signScript (see above) or we leave them out because they are object properties..

  • getScriptPubKey
  • getRedeemScript
  • getWitnessScript
  • getSignScript

These functions say whether the input was P2SH/P2WSH (it may have been partially signed so the caller didn't know this yet)

  • isP2WSH (scriptPubKey.type == P2WSH && witnessScript != null OR: scriptPubKey.type == P2SH && redeemScript.type == P2WSH && witnessScript != null)
  • isP2SH (scriptPubKey.type == P2SH && redeemScript != null)

Advanced Signing

Opening remarks:

We have maintained the TransactionBuilder API to date, and it works well for library consumers. Internally, I believe there are some really cool logical next steps to consider.

For example, our sign function doesn't deal with two public keys nicely. If you had a 2-of-2, key1=key2, then bitcoinjs doesn't make it possible to sign just a single key index in a multiple-key-signing operation.

signIdx(n, key, hashType)

Go:

NB: our existing code (like the array of publicKeys, array of signatures, mentioned in the inputSigner overview) assumes there is only one signing operation. a CHECKSIG, or a CHECKMULTISIG operation.

If we want to support (A CHECKSIG B CHECKSIG) then again, we need to deal with 'multiple signing opcodes'. Signing seems to be scoped to just one CHECKSIG/CHECKMULTISIG opcode.

Maybe like inputs, we need scoped objects for publicKeys/signatures/requiredSigs etc, and can expose functions for a specific cs/cms OP.

signOp(nOp)
=> signingState{}

signingState.signIdx(n, key, hashType)
signingState.sign(key, hashType) (signs all, like were used to)

To date, we have only had one signingState from our P2PKH/P2PK/Multisig support. Multisig is actually a good, under-exposed case. We don't have the ability to sign w/ certain hashtypes at certain key indexes.

eg: rs: 2 Alice Alice 2 CHECKMULTISIG
   sig: SigAlice[ALL] SigAlice[SINGLE]

[alice] checksig 2 [bob] [carol] 2 checkmultisig

this script has two consecutive signingStates, one with alice's public keys and signatures, the other with bobs.

I believe it is within reason for bitcoinjs to eventually support parsing/extracting/verifying these script types, so long as we can safely constrain the allowed scripts from everything to only those for which a signing strategy can be made.

With this covered, we can look atIF templated() ELSE templated() ENDIF

IF [alice] checksig ELSE [bob] checksig ENDIF

this script has two mutually exclusive signingStates. (meaning, we can enforce signatures for a certain branch by setting that in opts, or we can leave it blank if there are existing signatures and don't care which. or it's unsigned and we can pick either).

we could extend this further:

[templated()]
IF 
    templated()
    NOTIF
         templated()
    ENDIF
ELSE
    templated()
ENDIF
[templated()]

We can ensure that so long as the concatenation of the scripts mutually exclusive sections still turns into a script that is templated() || templated() || templated() we can sign it.

Essentially the process looks is as follows

Take a script: 2-of-2 MULTISIGVERIFY IF [Alice] CHECKSIG ELSE [Bob] CHECKSIG ENDIF Determine the distinct logical pathways: [1] and [0] (respectively) (Logical pathways are the value which is on the stack when logical opcodes are run. after each opcode, the first value is shifted off, and so on, until the script succeessfully finishes - or else the script is invalid)

Determine the execution pathways for each branch: [1] = 2-of-2 MULTISIGVERIFY IF[1 - therefore prev op must=true] [Alice] CHECKSIG ELSE ENDIF [0] = 2-of-2 MULTISIGVERIFY IF[0 - therefore prev op must=false] ELSE [Bob] CHECKSIG ENDIF

By now, we check that the users logicalPath is one of these

[1] - STEPS: [Checksig(2-of-2, required), Conditional(IF, value=true), Checksig(P2PKH, Alice, required)

[0] - STEPS: [Checksig(2-of-2, !required), Conditional(IF, value=false), Checksig(P2PKH, Bob, required)

And also now we can determine the scriptSigs for these:

[1] step0 = 0 [sig1] [sig2]

  • step2 = [sigAlice]

= [sigAlice] 0 [sig1] [sig2]

[0] step0 = 0 0 0

  • step2 = [sigBob]

= [sigBob] 0 0 0

Note, how we the checksig operations are step0 and step2 -

Signing Data (rs, ws, script branches, mast data, etc)

One half of this work is separating the data required for input verification from the step of actually signing the input. The remainder is enabling users to have a lot of control over the precise way they sign a transaction.

We require the redeem script and witness script to be set here if the input has no signatures. The signer is able to parse redeemScripts and witnessScripts if they are provided, and it will cross check against the txOut anyway.

NB: the data here must be considered immutable across the life of the input object.

scripts with IF's

If we are signing a certain scriptBranch, ex,

HASH160 [20-byte-hash] EQUAL
IF
    [Alice] CHECKSIG
ELSE
    [Bob] CHECKSIG
ENDIF

there are two branches:

 scriptSig: SigBob '0'
 opcodes: HASH160 [20bytehash] EQUAL [Bob] CHECKSIG
 
 scriptSig: SigBob 'preimage'
 opcodes: HASH160 [20bytehash] EQUAL [Alice] CHECKSIG

We need to be able to tell the signer which branch it ought to follow when deciding the redemption requirements. It cannot know which set of publicKeys/signatures to extract unless signatures already exist, or the user tells us using the opts before any signatures are added. (A convention for writing branch specifiers exists, details don't matter here)

MAST

With MAST, there are different modes of operation:

  1. We can pass in a partial MAST tree (a single MAST redeem path), which means we only know how to sign that branch, and cannot validate that other solutions are a part of the MAST root.

  2. we can pass the entirity of the scripts that form the MAST tree, which means we can validate ALL solutions, and sign any of them once a branch descriptor is provided.

Both of these would be separate fields on the signing options object, we should enforce that only one can be passed at once, and we like always will be connecting the full MAST root/partial MAST tree is committed to using a V1 witness program.

IF scripts, VERIFY operations, dynamic steps

When we get into signature parsing with multple opcodes, we need to actually mutate the stack when evaluating that a certain steps signatures were provided

We know from the pathData, exactly what the next value consumed by OP_IF and OP_NOTIF would be, therefore we know that the last op (within reason, set sensible limitations as constraints to avoid snakeoil signing & invalid sigs) evaluates to true or false, which informs whether we expect signatures to parse, or whether OP_0's were expected instead..

So, when we have a stack, and run the first opcode on it (first signatures extracted), and the operation is CHECKSIG, we have to push true or false to the stack, because otherwise OP_IF wouldn't find a value there (it would see it in pathData, but extraction is interplay between OP_IF/OP_NOTIF handling and standard templated signing/extraction)

so if we extract a P2PK ([sig]), we must push the resulting boolean value to the stack. If it was P2PKH-Verify, we don't push it. Same with multisig. if it wasn't verify, we push true onto the stack.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment