Checks
Some of the validation checks are cheap and some are expensive to perform. A block or a transaction passes if it passes all the checks. For performance reasons, it's better to fail fast, i.e if the block fails a cheap test and an expensive one, it is better to check the fast one first and avoid doing the expensive check. But alas, it is not always possible to do so. Checks are of several categories:
- parsing checks. If the block got here, it already passed these.
- single metadata checks. For instance, the hash must be below the target. It's a check that doesn't involve other blocks
- multi metadata checks. These checks are more expensive because more than one block participate. For example, the previous block hash must match, or the timestamp must be no sooner than the median of the previous 11 blocks
- the most expensive of all are the checks that require analyzing the content of a block: double spends, signature checks, scripts, merkle tree root hash, etc.
1:
|
module Checks |
Misc functions
Create a lazy sequence of block headers backwards from the one given to the genesis block. Because it is lazily evaluated, it is very rarely read all the way.
1: 2: 3: 4: 5: 6: 7: 8: 9: |
let chainFromTip (tip: BlockHeader): seq<BlockHeader> = Seq.unfold ( fun (header: BlockHeader) -> if header.Hash = zeroHash then None else let prevHeader = Db.readHeader(header.PrevHash) Some(header, prevHeader)) (tip) |
Convert between bits compact representation and target difficulty
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: |
let target (bits: int) = let b = BitConverter.GetBytes(bits) let exp = int b.[3] let mantissa = b.[0..2] (bigint mantissa) <<< (8*(exp-3)) let bits (target: bigint) = let targetBytes = target.ToByteArray() let mantissa = targetBytes.TakeLast 4 |> Seq.toArray let exp = targetBytes.Length let p1 = BitConverter.ToInt32(mantissa, 0) (p1 >>> 8) ||| (exp <<< 24) let maxTarget = target 0x207fFFFF // This is the max target on the main net |
The reward halving schedule
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: |
let reward (height: int) = let range = height / 210000 let era = min range 33 5000000000L / (1L <<< era) let maxHash = 1I <<< 256 let getWork (fork: BlockHeader seq) = fork |> Seq.map (fun bh -> maxHash / target bh.Bits) |> Seq.sum // The coinbase follow a particular format let isCoinBase (tx: Tx) = tx.TxIns.Length = 1 && hashCompare.Equals(tx.TxIns.[0].PrevOutPoint.Hash, zeroHash) && tx.TxIns.[0].PrevOutPoint.Index = -1 |
Compute the merkle root of a bunch of hashes
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: |
let rec computeMerkleRoot (hashes: byte[][]) = if hashes.Length = 1 then hashes.[0] else let hs = if hashes.Length % 2 = 0 then hashes else [hashes; [|hashes.Last()|]] |> Array.concat computeMerkleRoot (hs.Batch(2) |> Seq.map(fun x -> let h = x |> Array.concat dsha h ) |> Seq.toArray) |
Calculate the sum of satoshis in and out of a transaction. If there is a problem, the function returns None
.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: |
let totalIn (tx: Tx) = seq { for txIn in tx.TxIns do let utxo = utxoAccessor.GetUTXO txIn.PrevOutPoint yield utxo |> Option.map(fun utxo -> utxo.TxOut.Value) } |> Seq.toList |> Option.sequence |> Option.map Seq.sum let totalOut (tx: Tx) = seq { for txOut in tx.TxOuts do yield txOut.Value } |> Seq.sum |
Check that the timestamp of the block is in the proper range
1: 2: 3: 4: 5: 6: 7: 8: 9: |
let checkTimestamp (header: BlockHeader) = maybe { let prevBlockTimestamps = chainFromTip header |> Seq.skip 1 |> Seq.truncate minTimestampBlocks |> Seq.toArray |> Array.sortBy (fun h -> h.Timestamp) let median = prevBlockTimestamps.[prevBlockTimestamps.Length / 2] do! (prevBlockTimestamps.Length < minTimestampBlocks || header.Timestamp > median.Timestamp) |> errorIfFalse "timestamp is too far back" do! Instant.FromDateTimeUtc(DateTime.UtcNow.AddHours 2.0) >= Instant.FromSecondsSinceUnixEpoch(int64 header.Timestamp) |> errorIfFalse "timestamp is too far ahead" } let between x min max = if x < min then min elif x > max then max else x |
Check that the difficulty/target is correct. Either it's the same as the previous block or if it's time to readjust then it must be so that the previous 2016 blocks would have taken 10 minutes in average to produce.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: |
let checkBits (header: BlockHeader) = let testResult = if header.Height > 0 && header.Height % difficultyReadjustmentInterval = 0 then let chain = chainFromTip header let prevBlock = chain |> Seq.skip 1 |> Seq.head let blockIntervalAgo = chain |> Seq.skip (difficultyReadjustmentInterval) |> Seq.head let timeElapsed = (prevBlock.Timestamp - blockIntervalAgo.Timestamp) let boundedTimeElapsed = between timeElapsed (targetElapsed/4u) (targetElapsed*4u) // don't readjust by too much let prevTarget = target prevBlock.Bits let readjustedTarget = (prevTarget*bigint boundedTimeElapsed)/(bigint targetElapsed) let newBits = bits readjustedTarget newBits = header.Bits else let prevBlock = chainFromTip header |> Seq.skip 1 |> Seq.head prevBlock.Bits = header.Bits testResult |> errorIfFalse "difficulty is invalid" |
Check that the content of the blockheader is valid
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: |
let checkBlockHeader (header: BlockHeader) = logger.InfoF "Checking block header #%d" (header.Height) let hashInt = header.Hash |> fun x -> bigint (Array.append x [|0uy|]) // append 0 to make sure the result is > 0 maybe { let t = target header.Bits do! (t <= maxTarget && t >= 0I) |> errorIfFalse "target is out of range" do! checkBits header do! hashInt < (target header.Bits) |> errorIfFalse "hash is above target difficulty" do! checkTimestamp header } |
Check that the transaction is final
1: 2: 3: 4: |
let checkLocktime (height: int) (timestamp: uint32) (tx: Tx) = let sequenceFinal = tx.TxIns |> Seq.map (fun txIn -> txIn.Sequence = 0xFFFFFFFF) |> Seq.exists id let lockTime = tx.LockTime (sequenceFinal || lockTime = 0u || (lockTime < 500000000u && (uint32)height >= lockTime) || (lockTime >= 500000000u && timestamp >= lockTime)) |
Check the transactions from a block. These are expensive but they still aren't the worst because they don't access the database or require script evaluation.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: |
let checkBlockTxs (utxoAccessor: IUTXOAccessor) (block: Block) = let bh = block.Header logger.InfoF "Checking block tx #%d %A" (bh.Height) (bh) maybe { // checkdup do! block.Txs.Any() |> errorIfFalse "Must have at least one transaction" do! block.Txs |> Seq.mapi (fun i tx -> if i = 0 then isCoinBase tx else not (isCoinBase tx)) |> Seq.forall id |> errorIfFalse "coinbase must be the first transaction" do! block.Txs |> Seq.map (fun tx -> (utxoAccessor.GetCount tx.Hash) = 0) |> Seq.forall id |> errorIfFalse "duplicate tx" do! block.Txs |> Seq.map (checkLocktime bh.Height bh.Timestamp) |> Seq.forall id |> errorIfFalse "has non final tx" let coinBaseScriptlen = block.Txs.[0].TxIns.[0].Script.Length do! (coinBaseScriptlen >= 2 && coinBaseScriptlen <= 100) |> errorIfFalse "coinbase script must be between 2 and 100 bytes" let scriptRuntime = new Script.ScriptRuntime(fun a _ -> a) let checkSigOpsCount = block.Txs |> Seq.mapi (fun i tx -> let inputScripts = if i <> 0 then tx.TxIns |> Seq.map (fun txIn -> let utxo = utxoAccessor.GetUTXO txIn.PrevOutPoint utxo |> Option.bind(fun utxo -> let pubScript = utxo.TxOut.Script if Script.isP2SH pubScript // For P2SH, also count the signature checks from the redeem script then Some(scriptRuntime.RedeemScript pubScript) else None ) |?| txIn.Script ) |> Seq.toArray else Array.empty let outputScripts = tx.TxOuts |> Array.map (fun x -> x.Script) [inputScripts; outputScripts] |> Array.concat |> Seq.map (fun script -> scriptRuntime.CheckSigCount script) |> Seq.sum ) |> Seq.sum logger.DebugF "CheckSig count %d" checkSigOpsCount do! checkSigOpsCount <= maxCheckSigOpsCount |> errorIfFalse (sprintf "checkSig ops cannot occur more than %d times" maxCheckSigOpsCount) let merkleRoot = block.Txs |> Array.map (fun tx -> tx.Hash) |> computeMerkleRoot do! block.Header.MerkleRoot = merkleRoot |> errorIfFalse "merkle root does not match with header" } |
Check the tx and update the UTXO set. These are the worst and also the very last checks.
I must use a temporary UTXO accessor for this because if any transaction of the block fails then the entire block is rejected and all the modification of the UTXO set must be rolled back.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: |
let updateBlockUTXO (utxoAccessor: IUTXOAccessor) (block: Block) = logger.InfoF "Processing block #%d" block.Header.Height use undoWriter = storeUndoBlock block maybe { let processUTXO = processUTXO utxoAccessor undoWriter let! fees = block.Txs |> Array.mapi (fun i tx -> if i <> 0 then checkScript utxoAccessor tx else Some() |> Option.bind(fun _ -> processUTXO (i=0) block.Header.Height tx) ) |> Seq.toList |> Option.sequence |> Option.map Seq.sum let coinbase = totalOut block.Txs.[0] let totalReward = fees + reward block.Header.Height do! coinbase <= totalReward |> errorIfFalse "coinbase payout exceeds fees + reward" } |
Canonical Signature / PubKey
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: |
let checkDERInt (signature: byte[]) (offset: int) (len: int) = maybe { do! (signature.[offset-2] = 0x02uy) |> errorIfFalse "Non-canonical signature: value type mismatch" do! (len <> 0) |> errorIfFalse "Non-canonical signature: length is zero" do! ((signature.[offset] &&& 0x80uy) = 0uy) |> errorIfFalse "Non-canonical signature: value negative" do! (len <= 1 || (signature.[offset] <> 0x00uy) || ((signature.[offset+1] &&& 0x80uy) <> 0uy)) |> errorIfFalse "Non-canonical signature: value negative" } let checkLowS (sBytes: byte[]) = let s = bigint (sBytes |> Array.rev) (s >= 0I && s < Script.halfN) |> errorIfFalse "Non-canonical signature: S value is unnecessarily high" let checkCanonicalSignature (signature: byte[]) = maybe { do! (signature.Length >= 9) |> errorIfFalse "Non-canonical signature: too short" do! (signature.Length <= 73) |> errorIfFalse "Non-canonical signature: too long" let hashType = signature.Last() &&& ~~~0x80uy do! (hashType >= 1uy && hashType <= 3uy) |> errorIfFalse "unknown hashtype byte" do! (signature.[0] = 0x30uy) |> errorIfFalse "Non-canonical signature: wrong type" do! (signature.[1] = byte(signature.Length-3)) |> errorIfFalse "Non-canonical signature: wrong length marker" let rLen = int signature.[3] do! (rLen+5 < signature.Length) |> errorIfFalse "Non-canonical signature: S length misplaced" let sLen = int signature.[rLen+5] do! (rLen+sLen+7 = signature.Length) |> errorIfFalse "Non-canonical signature: R+S length mismatch" do! checkDERInt signature 4 rLen do! checkDERInt signature (6+rLen) sLen do! checkLowS signature.[6+rLen..5+rLen+sLen] } |
namespace System.Linq
--------------------
namespace Microsoft.FSharp.Linq
from Microsoft.FSharp.Control
namespace System.Collections
--------------------
namespace Microsoft.FSharp.Collections
type Choice<'T1,'T2> =
| Choice1Of2 of 'T1
| Choice2Of2 of 'T2
Full name: Microsoft.FSharp.Core.Choice<_,_>
--------------------
type Choice<'T1,'T2,'T3> =
| Choice1Of3 of 'T1
| Choice2Of3 of 'T2
| Choice3Of3 of 'T3
Full name: Microsoft.FSharp.Core.Choice<_,_,_>
--------------------
type Choice<'T1,'T2,'T3,'T4> =
| Choice1Of4 of 'T1
| Choice2Of4 of 'T2
| Choice3Of4 of 'T3
| Choice4Of4 of 'T4
Full name: Microsoft.FSharp.Core.Choice<_,_,_,_>
--------------------
type Choice<'T1,'T2,'T3,'T4,'T5> =
| Choice1Of5 of 'T1
| Choice2Of5 of 'T2
| Choice3Of5 of 'T3
| Choice4Of5 of 'T4
| Choice5Of5 of 'T5
Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_>
--------------------
type Choice<'T1,'T2,'T3,'T4,'T5,'T6> =
| Choice1Of6 of 'T1
| Choice2Of6 of 'T2
| Choice3Of6 of 'T3
| Choice4Of6 of 'T4
| Choice5Of6 of 'T5
| Choice6Of6 of 'T6
Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_,_>
--------------------
type Choice<'T1,'T2,'T3,'T4,'T5,'T6,'T7> =
| Choice1Of7 of 'T1
| Choice2Of7 of 'T2
| Choice3Of7 of 'T3
| Choice4Of7 of 'T4
| Choice5Of7 of 'T5
| Choice6Of7 of 'T6
| Choice7Of7 of 'T7
Full name: Microsoft.FSharp.Core.Choice<_,_,_,_,_,_,_>
from Microsoft.FSharp.Core
Full name: Checks.BlockHeaderList
Full name: Microsoft.FSharp.Collections.list<_>
Full name: Checks.BlockChainFragment
Full name: Checks.minTimestampBlocks
Full name: Checks.difficultyReadjustmentInterval
Full name: Checks.targetElapsed
val uint32 : value:'T -> uint32 (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.uint32
--------------------
type uint32 = UInt32
Full name: Microsoft.FSharp.Core.uint32
Full name: Checks.maxCheckSigOpsCount
Full name: Checks.chainFromTip
val seq : sequence:seq<'T> -> seq<'T>
Full name: Microsoft.FSharp.Core.Operators.seq
--------------------
type seq<'T> = IEnumerable<'T>
Full name: Microsoft.FSharp.Collections.seq<_>
from Microsoft.FSharp.Collections
Full name: Microsoft.FSharp.Collections.Seq.unfold
Full name: Checks.target
val int : value:'T -> int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int
--------------------
type int = int32
Full name: Microsoft.FSharp.Core.int
--------------------
type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
static val IsLittleEndian : bool
static member DoubleToInt64Bits : value:float -> int64
static member GetBytes : value:bool -> byte[] + 9 overloads
static member Int64BitsToDouble : value:int64 -> float
static member ToBoolean : value:byte[] * startIndex:int -> bool
static member ToChar : value:byte[] * startIndex:int -> char
static member ToDouble : value:byte[] * startIndex:int -> float
static member ToInt16 : value:byte[] * startIndex:int -> int16
static member ToInt32 : value:byte[] * startIndex:int -> int
static member ToInt64 : value:byte[] * startIndex:int -> int64
...
Full name: System.BitConverter
BitConverter.GetBytes(value: float32) : byte []
BitConverter.GetBytes(value: uint64) : byte []
BitConverter.GetBytes(value: uint32) : byte []
BitConverter.GetBytes(value: uint16) : byte []
BitConverter.GetBytes(value: int64) : byte []
BitConverter.GetBytes(value: int) : byte []
BitConverter.GetBytes(value: int16) : byte []
BitConverter.GetBytes(value: char) : byte []
BitConverter.GetBytes(value: bool) : byte []
Full name: Microsoft.FSharp.Core.bigint
Full name: Checks.bits
Full name: Microsoft.FSharp.Collections.Seq.toArray
Full name: Checks.maxTarget
Full name: Checks.reward
Full name: Microsoft.FSharp.Core.Operators.min
Full name: Checks.maxHash
Full name: Checks.getWork
Full name: Microsoft.FSharp.Collections.Seq.map
Full name: Microsoft.FSharp.Collections.Seq.sum
Full name: Checks.isCoinBase
Full name: Checks.computeMerkleRoot
val byte : value:'T -> byte (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.byte
--------------------
type byte = Byte
Full name: Microsoft.FSharp.Core.byte
(extension) IEnumerable.Last<'TSource>(predicate: Func<'TSource,bool>) : 'TSource
member Clone : unit -> obj
member CopyTo : array:Array * index:int -> unit + 1 overload
member GetEnumerator : unit -> IEnumerator
member GetLength : dimension:int -> int
member GetLongLength : dimension:int -> int64
member GetLowerBound : dimension:int -> int
member GetUpperBound : dimension:int -> int
member GetValue : params indices:int[] -> obj + 7 overloads
member Initialize : unit -> unit
member IsFixedSize : bool
...
Full name: System.Array
Full name: Microsoft.FSharp.Collections.Array.concat
Full name: Checks.totalIn
Full name: Microsoft.FSharp.Core.Option.map
Full name: Microsoft.FSharp.Collections.Seq.toList
Full name: Checks.totalOut
Full name: Checks.checkTimestamp
Full name: Microsoft.FSharp.Collections.Seq.skip
Full name: Microsoft.FSharp.Collections.Seq.truncate
Full name: Microsoft.FSharp.Collections.Array.sortBy
type DateTime =
struct
new : ticks:int64 -> DateTime + 10 overloads
member Add : value:TimeSpan -> DateTime
member AddDays : value:float -> DateTime
member AddHours : value:float -> DateTime
member AddMilliseconds : value:float -> DateTime
member AddMinutes : value:float -> DateTime
member AddMonths : months:int -> DateTime
member AddSeconds : value:float -> DateTime
member AddTicks : value:int64 -> DateTime
member AddYears : value:int -> DateTime
...
end
Full name: System.DateTime
--------------------
DateTime()
(+0 other overloads)
DateTime(ticks: int64) : unit
(+0 other overloads)
DateTime(ticks: int64, kind: DateTimeKind) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, calendar: Globalization.Calendar) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, kind: DateTimeKind) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, calendar: Globalization.Calendar) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int) : unit
(+0 other overloads)
DateTime(year: int, month: int, day: int, hour: int, minute: int, second: int, millisecond: int, kind: DateTimeKind) : unit
(+0 other overloads)
val int64 : value:'T -> int64 (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int64
--------------------
type int64 = Int64
Full name: Microsoft.FSharp.Core.int64
--------------------
type int64<'Measure> = int64
Full name: Microsoft.FSharp.Core.int64<_>
Full name: Checks.between
Full name: Checks.checkBits
Full name: Microsoft.FSharp.Collections.Seq.head
Full name: Checks.checkBlockHeader
Full name: Microsoft.FSharp.Collections.Array.append
Full name: Checks.checkLocktime
Full name: Microsoft.FSharp.Collections.Seq.exists
Full name: Microsoft.FSharp.Core.Operators.id
Full name: Checks.checkBlockTxs
Full name: Microsoft.FSharp.Collections.Seq.mapi
Full name: Microsoft.FSharp.Core.Operators.not
Full name: Microsoft.FSharp.Collections.Seq.forall
Full name: Microsoft.FSharp.Core.Option.bind
Full name: Microsoft.FSharp.Collections.Array.empty
Full name: Microsoft.FSharp.Collections.Array.map
Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
Full name: Checks.updateBlockUTXO
Full name: Microsoft.FSharp.Collections.Array.mapi
Full name: Checks.checkDERInt
Full name: Checks.checkLowS
Full name: Microsoft.FSharp.Collections.Array.rev
Full name: Checks.checkCanonicalSignature