Introduction
This is Part 2 of my F# blockchain implementation. Previous parts:
Code
This time I am tackling transactions. The code is based on a JavaScript blockchain implementation called naivecoin. The source code for naivecoin transactions can be found here.
namespace Blockchain.Core
open System.Security.Cryptography
open System.Text
open System
open System.Text.RegularExpressions
open Helpers
type TransactionOutput =
{ address: string; amount: float }
override this.ToString() = [this.address; this.amount.ToString()] |> String.Concat
type UnspentTransactionOutput =
{ transactionId: string; outputIndex: int; address: string; amount: float }
override this.ToString() = [this.transactionId; this.outputIndex.ToString(); this.address; this.amount.ToString()] |> String.Concat
type TransactionInput =
{ sourceOutputTransactionId: string; sourceOutputIndex: int; signature: string }
override this.ToString() = [this.sourceOutputTransactionId; this.sourceOutputIndex.ToString()] |> String.Concat
type Transaction =
{ id: string; inputs: TransactionInput array; outputs: TransactionOutput array }
override this.ToString() =
let inputContent =
this.inputs
|> Seq.map (fun x -> x.ToString())
|> Seq.fold (+) ""
let outputContent =
this.outputs
|> Seq.map (fun x -> x.ToString())
|> Seq.fold (+) ""
[this.id; inputContent; outputContent] |> String.Concat
type TransactionProcessor() =
let coinbaseAmount = 50.0
member private this.GetTransactionId(transactionInputs: TransactionInput seq, transactionOutputs: TransactionOutput seq) =
let inputContent =
transactionInputs
|> Seq.map (fun x -> x.ToString())
|> Seq.fold (+) ""
let outputContent =
transactionOutputs
|> Seq.map (fun x -> x.ToString())
|> Seq.fold (+) ""
use algorithm = SHA256.Create()
let byteId =
inputContent + outputContent
|> Encoding.UTF8.GetBytes
|> algorithm.ComputeHash
byteId.ToHex()
member private this.FindUnspentOutput(outputTransactionId: string, outputIndex: int, unspentOutputs: UnspentTransactionOutput seq) =
Seq.tryFind (fun x -> x.transactionId = outputTransactionId && x.outputIndex = outputIndex) unspentOutputs
member private this.SignTransactionInput(transaction: Transaction, inputIndex: int, key: CngKey, unspentOutputs: UnspentTransactionOutput seq) =
let input = transaction.inputs.[inputIndex]
let referencedUnspentOutput =
match this.FindUnspentOutput(input.sourceOutputTransactionId, input.sourceOutputIndex, unspentOutputs) with
| Some(output) -> output
| None -> failwith "Could not find referenced output."
if key.Export(CngKeyBlobFormat.EccPublicBlob).ToHex() <> referencedUnspentOutput.address then
failwith "Key does not match the address referenced in the input."
let dataToSign = Encoding.UTF8.GetBytes transaction.id
use dsa = new ECDsaCng(key, HashAlgorithm = CngAlgorithm.Sha256)
(dsa.SignData dataToSign).ToHex()
member private this.UpdateUnspentOutputs(newTransactions: Transaction seq, unspentOutputs: UnspentTransactionOutput seq) =
let newUnspentOutputs =
newTransactions
|> Seq.map (fun t -> t.outputs |> Seq.mapi (fun i o -> { transactionId = t.id; outputIndex = i; address = o.address; amount = o.amount }))
|> Seq.concat
let consumedUnspentOutputs =
newTransactions
|> Seq.map (fun x -> x.inputs)
|> Seq.concat
|> Seq.map (fun x -> { transactionId = x.sourceOutputTransactionId; outputIndex = x.sourceOutputIndex; address = ""; amount = 0.0 })
unspentOutputs
|> Seq.filter (fun x -> not (Seq.contains x consumedUnspentOutputs))
|> Seq.append newUnspentOutputs
member private this.GetInputAmount(input: TransactionInput, unspentOutputs: UnspentTransactionOutput seq) =
match this.FindUnspentOutput(input.sourceOutputTransactionId, input.sourceOutputIndex, unspentOutputs) with
| Some(output) -> output.amount
| None -> failwith "No matching unspent output found."
member private this.AddressIsValid(address: string) =
// Valid address is a valid ECDSA public key in the '04' + 'X-coordinate' + 'Y-coordinate' format.
address.Length = 130 && Regex.IsMatch(address, "^04[a-fA-F0-9]+$")
member private this.InputIsValid(input: TransactionInput, transaction: Transaction, unspentOutputs: UnspentTransactionOutput seq) =
match this.FindUnspentOutput(input.sourceOutputTransactionId, input.sourceOutputIndex, unspentOutputs) with
| Some referencedOutput ->
let key = CngKey.Import(hexToByteArray referencedOutput.address, CngKeyBlobFormat.EccPublicBlob)
use dsa = new ECDsaCng(key)
dsa.VerifyData(hexToByteArray transaction.id, hexToByteArray input.signature)
| None -> false
member private this.CoinbaseTransactionIsValid(transaction: Transaction, blockIndex: int) =
this.GetTransactionId(transaction.inputs, transaction.outputs) = transaction.id &&
transaction.inputs |> Seq.length = 1 &&
(transaction.inputs |> Seq.head).sourceOutputIndex = blockIndex &&
transaction.outputs |> Seq.length = 1 &&
(transaction.outputs |> Seq.head).amount = coinbaseAmount
member private this.TransactionIsValid(transaction: Transaction, unspentOutputs: UnspentTransactionOutput seq) =
imperative {
if this.GetTransactionId(transaction.inputs, transaction.outputs) <> transaction.id then return false
let inputsAreValid =
transaction.inputs
|> Seq.map (fun x -> this.InputIsValid(x, transaction, unspentOutputs))
|> Seq.fold (&&) true
if (not inputsAreValid) then return false
let outputsAreValid = transaction.outputs |> Seq.forall (fun x -> this.AddressIsValid x.address)
if (not outputsAreValid) then return false
let inputValues = Seq.map (fun x -> this.GetInputAmount(x, unspentOutputs)) transaction.inputs
let totalInputValues = Seq.fold (+) 0.0 inputValues
let totalOutputValues =
transaction.outputs
|> Seq.map (fun x -> x.amount)
|> Seq.fold (+) 0.0
if totalInputValues <> totalOutputValues then return false
return true
}
member private this.BlockTransactionsAreValid(transactions: Transaction seq, unspentOutputs: UnspentTransactionOutput seq, blockIndex: int) =
imperative {
if Seq.isEmpty transactions then return false
if not (this.CoinbaseTransactionIsValid(transactions |> Seq.head, blockIndex)) then return false
let inputs = transactions |> Seq.map (fun x -> x.inputs) |> Seq.concat
let inputsAreUnique =
(
inputs
|> Seq.map (fun x -> (x.sourceOutputTransactionId, x.sourceOutputIndex))
|> Seq.distinct
) |> Seq.length = (inputs |> Seq.length)
if not inputsAreUnique then return false
return transactions |> Seq.skip 1 |> Seq.forall (fun x -> this.TransactionIsValid(x, unspentOutputs))
}
member this.ProcessTransactions(transactions: Transaction seq, unspentOutputs: UnspentTransactionOutput seq, blockIndex: int) =
if this.BlockTransactionsAreValid(transactions, unspentOutputs, blockIndex) then
None
else
Some(this.UpdateUnspentOutputs(transactions, unspentOutputs))
member private this.GetCoinbaseTransaction(address: string, blockIndex: int) =
if not (this.AddressIsValid address) then
None
else
let transactionInputs = [| { sourceOutputTransactionId = ""; sourceOutputIndex = blockIndex; signature = "" } |]
let transactionOutputs = [| { address = address; amount = coinbaseAmount } |]
Some({ id = this.GetTransactionId(transactionInputs, transactionOutputs); inputs = transactionInputs; outputs = transactionOutputs })
Notes
Byte array's ToHex method:
[<Extension>]
type ByteArrayExtensions =
[<Extension>]
static member inline ToHex(xs: byte[]) =
String.Join("", xs.Select(fun b -> b.ToHex()))
let hexToByteArray(hex: string) =
let pairs s =
s
|> Seq.pairwise
|> Seq.mapi (fun i x -> (i % 2 = 0, x))
|> Seq.filter fst
|> Seq.map snd
hex
|> pairs
|> Seq.map (fun x -> Convert.ToByte(new String([|fst x; snd x|]), 16))
|> Array.ofSeq
The imperative computation expression is taken from this blog post.
