0
\$\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.