1
\$\begingroup\$

Introduction

This is Part 2 of my F# blockchain implementation. Previous parts:

  1. Block and Blockchain

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.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.