The Real Blockchain
CSC 597: Blockchain and Ethereum
by: burt rosenberg
at: university of miami
Authentication in Bitcoin
The authorization to spend the UTXO's (unspent transaction outputs) is provided by
the mathematical technology of a digital signature. A digsig is a form of
public key cryptography that can provide proof that a owner of the bitcoin has
authorized the transaction involving the bitcoin.
A digital signature consists of three procedures,
- A key generation procedure GEN.
- A signing procedure SIGN.
- A verification procedure VERIFY.
The subject, the entity that can own bitcoin, runs GEN with input a string of
random bits to provide two outputs, sk, the secret or signing key, and
pk, the public of verification key.
(sk, pk) := GEN(ω ∈ Ω)
The key sk must remain secret and the key pk will be associate with
a TxOut, and forms the identity of the owner of the Bitcoin.
A proposed transaction tr is hashed to a value H(tr). The sign procedure
input that hash, the signing key sk and perhaps randomness to produce σ the
signature,
σ := SIGN(sk,H(tr),ω ∈ Ω)
The verification procedure has the correctness guarantee that, with this notation,
VERIY(pk, σ, H(tr)) → True autentic σ
and has the security guarantee that for any s that the adversary can effectively
compute, even after having witnessed man signatures on many messages, even suggested messages
for the signer to sign, with over whelming probability,
VERIFY(pk, s, H(tr)) → False forged s
Transaction Verification
Bitcoin as several different ways to do the verification.
We will detail Pay-to-PubkeyHash verification.
The TxOut has a scriptPubKey, a standardized script that includes a
hash of pk, the public key of the owner of the TxOut.
The TxIn has a scriptSig, a standardized script that includes
the public key pk and the signature σ. The signature is
on a hash of transaction reformatted.
In the case of a simple SIGHASH_ALL verification, verify each TxIn individually
as,
- Remove from all TxIn's the scriptSig.
- For the given TxIn we are verifying place scriptPubKey of the referenced TxOut.
- Hash this to H
- Check that the pk in this TxIn's scriptSig matches the hash in
the referenced scriptPubKey. So we know we have the corrected signer.
- Check that VERIFY(pk,&sigma,H) is True, so we know the owner of authorized the
transaction.
This verification (for each TxIn) includes,
- That the owner of this TxIn agrees with the source of funds for the transaction, as provided
by the TxIn's in the transaction.
- That the owner of this TxIn agrees with outputs of the transaction, including amounts
and the hash of a public key, as provided by the TxOut's in the transaction.
- The the owner of this TxIn agrees with the condition of spending of this TxIn, by
the inclusion in the hash of the TxOut scriptPubKey associated with this TxIn.
Other Possible Verifications
The scriptSig can ask for these sorts of verifications,
- SIGHASH_ALL, as described. All outputs are included in the hash of the transaction,
for this TxIn's verification.
- SIGHASH_NONE. Remove all TxOuts from the transaction then hash. The signer does not
care where the Bitcoins go.
- SIGHASH_ONE. Remove all but TxOut from the transaction then hash. The signer only
cares about one TXOut.
- SIGHASH_ANYONECANPAY. Remove all TxIn's except this one from the transaction
and hash. The signer does not care who else is the source of funds. This can be combined
with the three TxOut sorts of verification.
Transaction Malleability and SegWit
There is a question of how to identify a transaction, for instance, to prevent a transaction
once mined being mined again, as it has not be chased from some mempools. Bitcoin solved
the piece of the problem it cared about. The transaction will not be included
again in the block chain not because it is a duplicate, but because
as a duplicate it would double spend.
However this does not identify the transaction. It may be a different transaction
identical in its TxIn's and TxOut's. The paper describes a situation where the lack
of a clear identification of the transaction can lead to problems.
We have described how the transaction is stripped of the scriptSig before hashed.
The signatures are on this stripped version of the transaction.
That means that two transaction differing in unimportant ways in their scriptSig's
are both signed with the given signatures. However they will hash differently for
purposes of the identity of the transaction (say in TxIn references to TxOut's).
If the mempool contains both variants, one gets mined and the other will later be
rejected for double spending. This can be exploited.
See
Bitcoin Transaction Malleability and MtGox,
Christian Decker and Roger Wattenhofer, ESORICS 2014.
Signature Details
Pay-to-PubkeyHash
The TxOut has a scriptPubKey script. The TxIn has a scriptSig script.
The script is in a stack-based non-Turing equivalent programing language invented for BitCoin.
The TxOut can be called the locking script and the TxIn can be called the unlocking script.
Both scripts are brought together, lock with the unlock, and run. See the diagram
to the right.
- In this order: sig and PubKey are pushed onto the stack.
- The opcode DUP duplicated the PubKey, because it is top of stack.
- The opcode HASH160 applied to the PubKey on the top of the stack to yield a hashed public key.
- The PubKHash is pushed on the stack; the opcode EQUALVERIFY checks the two two stack elements are equal.
- The script fails if they are not equal. If it succeeds the two elements are popped of the stack and the
script continues.
- The opcode CHECKSIG hashes the transaction and verifies that sig on the top of stack is
valid signature on that hash.
- If not, the transaction is not signed and honest miners will not include it in a block.
