Novice to Coin Part 2 - Transactions

We left off with an immutable data structure storing arbitrary data, you can read about that in part one, or you can view the introduction to this series here. As always, the companion code for this post can be found on GitHub.

In this post, we'll introduce transactions which are the primary feature needed to convert that data into a currency. Although a transaction simply needs to subtract coins from one account and add them to another, the way this is implemented in a blockchain is a little unusual. We'll cover all these details and more during this article before implementing them in the LynxCoin project.

This is what we'll be working towards today.

The first thing you need to understand about currencies stored on a blockchain is that there is no concept of a balance. Instead, you hold rights to transactions. Specifically, if you received a transaction for 50 LynxCoins, you now have the right to spend them.

Our updated block looks like this.

A transaction may have one or more inputs and one or more outputs. During the transaction all coins from each of the inputs will be spent, they are divided up amongst the outputs. Each output can be given to a different individual, who may then use it as an input in one of their future transactions. Let's take a look at a few examples.

Example Transactions

Suppose that Alice was given an output in Transaction-A and received 50 LynxCoins. If she wanted to give those coins to Bob, she would use her output in Transaction-A as an input while creating a new transaction.  Bob would then be given an output to receive coins from that transaction.

As long as you want to give away the entire output this works fine, but what if Alice only wanted to give 10 of those coins to Bob? There is actually no way to give away part of a transaction, all of the coins from Transaction-A Output 1 will be spent following the alternative Transaction-B regardless of whether she gives Bob 10 coins or 50. The way we deal with this is the idea of "change". Since Bob should only receive 10 coins, Alice will name herself as a recipient for the remaining 40 coins. At this point, Alice's coins in Transaction-A are considered spent. If Alice needed to give Bob another 15 coins, she could now reference her output from Transaction-B while creating Transaction-C

In one final example, let's suppose Bob wanted to send 20 coins to Carol. He has 10 coins from the Transaction-B and 15 coins in Transaction-C, so he needs to use both of those in order to give Carol all 20 coins. So when making Transaction-D, Bob specifies Transaction-B and Transaction-C as the inputs, for a total of 25. He then names Carol as a recipient for 20 of those coins and himself as a recipient of the change, which is 5 coins.

Where Coins Come From

The previous examples assume that the coins were already somehow in the system but we haven't talked about where they come from originally. With the basic knowledge of how a transaction works, we can talk about a special transaction referred to as a Coinbase which is used to add coins to the system.

As we saw in the first diagram, a new block can contain more than one transaction. For most blocks, there will indeed be multiple transactions and the first of these is special. It has no inputs, instead, there is a Reward built into the system which acts as a default input. Therefore only outputs should be defined to indicate where that reward should go. In this example, we'll give it to Alice. The Coinbase transaction provides an incentive for people to create new blocks on the blockchain. It also prevents giving the power to "print" money to a central authority, in contrast, it actually acts as a way to distributes new coins across many different users which further reduces the influence that individual users have over the system. We'll talk later about why an incentive is needed for creating new blocks.

These properties are very important to a category of research called Cryptoeconomics, which studies the economics of a distributed currency like LynxCoin, Bitcoin, and Ethereum. There are many feedback mechanisms like the Coinbase reward, and they are designed to encourage people for doing the right thing and punish them for doing the wrong thing. Details of Cryptoeconomics are beyond the scope of this series (For now).

Signing Transactions

So we have a way to transfer coins between parties, the transactions are immutable thanks to the blockchain, and there is an audit trail that anyone with the blockchain can validate. These are all critical properties of our currency, but how do we ensure that the person named in an Output is the only one who can spend it? It is finally time to introduce some cryptography.

We need a way to verify that data came from Alice, Bob, or Carol in a way that nobody else could spoof. Fortunately, we can leverage Public-Key Cryptography to do just this. Like Cryptoeconomics, many details about the inner workings of Public-Key Cryptography will be left outside the scope of this series (For now). At a high level, algorithms like RSA or ECDSA work by generating Public and Private keys. Like their names suggest, the Public key is used to unlock data generated using the Private key. The locking mechanism works in two ways.

Encryption and Decryption

Suppose that Alice would like to send a message which can only Bob can read. By using Bob's Public key, she can encrypt the data. That encrypted data can then be sent over an unsecured network, now even though Eve can see the message only Bob has the Private key needed to decrypt the data:

Signing and Verifying

Encryption isn't useful for our Transactions, because rather than preventing others from seeing our message we need a way for everyone to verify that we created the message. To accomplish this we'll use a Sign and Verify routine with our Public and Private keys. The steps are similar, but by Signing our message with the Private key, all users of the system can read those messages using the Public key. Alice's Public key is the only way to unlock messages signed by her Private key, and because only Alice has access to her Private we can verify that Alice sent the message:

Signing Transactions

Using this tool, let's examine how we can secure the input to one of Alice's transactions. We now require that Alice has a Public key, available to everyone who uses the blockchain, and a secret Private key used to Sign.

To start, rather than assign an output to Alice, we'll assign it to her Public key. In fact, this key is used in the blockchain as the destination when Alice receives a transaction. This can be considered Alice's Wallet. We'll use her Private key to sign inputs, this signature is added as a new property to the input. While we're at it, let's also introduce a unique-id to identify input/output pairs. With this input/output ID we no longer need to store the value in both places, so we will also remove the value from the input. A simple transaction now looks like this:

Let's take a closer look at that signature. As we showed earlier we can sign a message, in this diagram we call that operation sig and indicate an output to be signed. The message is only half of the equation though, we also need the Private key. Looking at the input-output pair with id=2 we see that it is assigned to Alice's Public key, so the signature must be made with her Private key. Creating an input which uses output-2 now requires the following steps:

1. Lookup output 2.
2. Serialize output 2 into a message.
3. Sign the message using Alice's Private key.

Any user of our currency can now verify the input:

1. Lookup the input and output with id=2.
2. Serialize output 2 into a message.
3. Use Alice's Public key from the input to read the signature.
4. Verify that the serialized message from step 2 equals the signature from step 3.

Anonymity

You may have noticed that the final form of our transactions doesn't have any personally identifying information. The only thing linking a given transaction to an individual is the Public key. As it turns out, it is trivial to make new keys, so many Cryptocurrency users opt to generate a new pair of keys for every transaction. This way if someone were able to link some Public key to the user, they would only be able to see one of their transactions. It is a very curious property that all transactions are public, yet we still only have part of the story regarding who is making these transactions.

The concept of Zero Knowledge Proofs may change this one day, but I'm not currently planning to implementing that in LynxCoin.

Transaction rules

In addition to everything already talked about, there are a number of more obvious rules that our implementation must take into consideration:

1. Double Spending: An output may only be spent once.
2. Insufficient Inputs: The sum of inputs must be greater than or equal to the sum of outputs.
3. Unique Transaction IDs: There must be no duplicate Transaction IDs.

LynxCoin Implementation

Continuing with our implementation of LynxCoin, there are four important pieces to add: Transaction objects, Encryption utilities, Transaction creation, and Block validation. Unlike our blockchain implementation which was only a small handful of code which could be quickly verified by reading and running the code, there are many new edge cases so testing is no longer optional. So we'll introduce unit testing.

Transaction Object

Kotlin makes this easy, we'll define a few data classes. Note that the full implementation includes serialize methods, but they are omitted here for clarity.

data class Input(
    val id: Long,
    val signature: String)
data class Output(
    val id: Long,
    val value: Double,
    val destination: PublicKey)
data class Transaction(
    val inputs: List<Input>,
    val outputs: List<Output>
)

Integrating these into LynxBlock is a simple matter:

 data class LynxBlock(
     val lastHash: String,
-    val data: Any
+    val data: List<Transaction>
 )

Encryption utilities

Java includes robust implementations for encrypt/decrypt and sign/verify routines. The details are a bit cryptic, so we make some simple helper methods to perform the operations according to our needs:

fun sign(text: String, privateKey: PrivateKey): String {
  val privateSignature = Signature.getInstance("SHA256withRSA")
  privateSignature.initSign(privateKey)
  privateSignature.update(text.toByteArray(UTF_8))

  val signature = privateSignature.sign()

  return Base64.getEncoder().encodeToString(signature)
}

fun verify(text: String, signature: String, publicKey: PublicKey): Boolean {
  val publicSignature = Signature.getInstance("SHA256withRSA")
  publicSignature.initVerify(publicKey)
  publicSignature.update(text.toByteArray(UTF_8))

  val signatureBytes = Base64.getDecoder().decode(signature)

  return publicSignature.verify(signatureBytes)
}

If you look closely you'll notice that the implementation includes a SHA256 hash. It is a common convention to first take a hash of the message and compare hashes rather than fully encrypt/decrypt the message. Mainly because it is much faster to do this than to sign and verify a large message.

Transaction Creation

Before we were putting arbitrary data into the blocks, things are a bit more complicated now to deal with our transactions. Here is what the genesis block looks like, it includes a specification for the new Coinbase transaction:

-  val chain = LynxChain(LynxBlock("0", "Genesis block"))
+  val key = generateKeyPair()
+  val genesisBlock = LynxBlock("0",
+      listOf(
+          // Coinbase transaction, no inputs.
+          Transaction(
+              listOf(),
+              listOf(Output(0, REWARD, key.public)))))
+  val chain = LynxChain(genesisBlock)

Here is a larger demonstration of multiple transactions, they now include a signature:

  // Create some keys for the demo.
  val key1 = generateKeyPair()
  val key2 = generateKeyPair()
  val key3 = generateKeyPair()

  // Genesis block with coinbase reward for key1.
  val genesisBlock = LynxBlock("0",
      listOf(
          // Coinbase transaction
          Transaction(
              // No inputs.
              listOf(),
              // One output.
              listOf(Output(0, REWARD, key1.public)))))
  
  // Create chain with genesis block.
  val chain = LynxChain(genesisBlock)

  val transaction1 = LynxBlock(chain.last.getHash(),
      listOf(
          // Coinbase transaction.
          Transaction(listOf(), listOf(Output(1, REWARD, key2.public))),
          // Send the initial reward to the owner of key2 and key3.
          Transaction(
              // Sign output using key1's private key.
              listOf(Input(0, chain.getSignature(0, key1.private))),
              // Create outputs for key2 and key3.
              listOf(
                  Output(chain.lastId + 2, 50.0, key2.public),
                  Output(chain.lastId + 3, 50.0, key3.public)
              ))))
  chain.add(transaction1)

  val transaction2 = LynxBlock(chain.last.getHash(),
      listOf(
          // Coinbase transaction.
          Transaction(listOf(), listOf(Output(chain.lastId + 1, REWARD, key2.public))),
          // Multiple outputs
          Transaction(
              // Use coinbase reward from transaction 1.
              listOf(Input(1, chain.getSignature(1, key2.private))),
              // Split up output into multiple pieces to show that we can.
              listOf(
                  Output(chain.lastId + 2, 20.0, key3.public),
                  Output(chain.lastId + 3, 20.0, key3.public),
                  Output(chain.lastId + 4, 20.0, key3.public),
                  Output(chain.lastId + 5, 20.0, key3.public),
                  Output(chain.lastId + 6, 20.0, key3.public)
              ))))
  chain.add(transaction2)

  chain.print()

After reading through the example you'll notice a couple helper methods: getSignature and lastId. These help pull metadata out of the blockchain. lastId takes the last block and iterates over the outputs, then returns the largest. If there is no last block it simply returns -1. getSignature uses our encryption utilities to lookup a specific output, and sign it with the provided private key. Note that although the private key is being passed into a helper method, we only store the signature in the transaction.

Here is the code listing for these methods, it uses the Kotlin stream interface to work with data, see inline comments for operation details:

  /**
   * Return the last ID used for an output, or -1 if there are none.
   */
  val lastId get() = chain.lastOrNull()
      ?.data               // get the transaction list
      ?.map { it.outputs } // get the output list
      ?.flatten()          // flatten to output stream
      ?.map { it.id }      // get the IDs
      ?.max() ?: -1L       // return the largest ID, or -1.

  /**
   * Create a signature of the Output.
   */
  fun getSignature(id: Long, key: PrivateKey) : String {
    // Find the given output and serialize it to a string.
    return sign(find(id).serialize(), key)
  }

  /**
   * Lookup a specific transaction, throw an exception if missing.
   */
  fun find(id: Long) : Output {
    return unspentOutputCache[id] // Cache to speed up most lookups.
        ?: chain.asSequence()     // Stop processing when a match is found.
            .map { it.data }      // Get transaction list.
            .flatten()            // Get transactions.
            .map { it.outputs }   // Get output list.
            .flatten()            // Get outputs.
            .find { it.id == id } // Look for output with given ID.
        ?: throw NoSuchElementException("Not found: $id")
  }

The result from our transactions looks like the following when we print the chain object:

Size: 3

Block 0
hash: 0cf19c40407e59beb4132284e776f4f8759237ca41de14c8dd1150f89fd129e0
last hash: 0
transactions:
  Transaction: 0 (coinbase)
Disconnected from the target VM, address: '127.0.0.1:54115', transport: 'socket'
  | inputs: 0
  | outputs: 1
  |   tx: 0, value: 100.0, key: 06b80bee761...

Block 1
hash: bfdb9b282322ff4fc630f2c53ae531ead0a4f3353aac2f4f4b751266482591f9
last hash: 0cf19c40407e59beb4132284e776f4f8759237ca41de14c8dd1150f89fd129e0
transactions:
  Transaction: 0 (coinbase)
  | inputs: 0
  | outputs: 1
  |   tx: 1, value: 100.0, key: aa453d1992d...

  Transaction: 1
  | inputs: 1
  |   tx: 0, sig: NQ7IAZhyq9c...
  | outputs: 2
  |   tx: 2, value: 50.0, key: aa453d1992d...
  |   tx: 3, value: 50.0, key: caa0ff040e4...

Block 2
hash: 426ca1b9bf96171dec56d0d0f3c435c810c1145835f96ec1797fd16d1c6ecf30
last hash: bfdb9b282322ff4fc630f2c53ae531ead0a4f3353aac2f4f4b751266482591f9
transactions:
  Transaction: 0 (coinbase)
  | inputs: 0
  | outputs: 1
  |   tx: 4, value: 100.0, key: aa453d1992d...

  Transaction: 1
  | inputs: 1
  |   tx: 1, sig: eVOcNO4ozmV...
  | outputs: 5
  |   tx: 5, value: 20.0, key: caa0ff040e4...
  |   tx: 6, value: 20.0, key: caa0ff040e4...
  |   tx: 7, value: 20.0, key: caa0ff040e4...
  |   tx: 8, value: 20.0, key: caa0ff040e4...
  |   tx: 9, value: 20.0, key: caa0ff040e4...

Block Validation

Although validation is significantly more complex than before, it can be encapsulated as a single method which gets called right before adding a new block. One detail to notice is that the unspentOutputCache which was used by our find method is updated each time a block is added.

  /**
   * Add and validate a new block.
   */
  fun add(block: LynxBlock) {
    val state = validate(block)
    when (state) {
      is Valid -> chain.add(block)
      else      -> throw state
    }

    this.unspentOutputCache = unspentOutputs()
  }

To help organize the code errors are coded into a sealed class, the return type for validate is ValidationState which may either be Valid or one of the error states. This isn't strictly necessary but may come in handy later on as we build out our coin.

// Validation types
sealed class ValidationState: RuntimeException()
object Valid: ValidationState()
data class InvalidLastHash(private val expected: String, private val actual: String) : ValidationState()
data class InsufficientInputValue(val transactions: List<Transaction>) : ValidationState()
data class TransactionDoubleSpend(val transactionIds: List<Long>) : ValidationState()
data class PreviouslySpentTransactions(val transactionIds: List<Long>) : ValidationState()
data class CoinbaseRewardTooLarge(val rewardSize: Double) : ValidationState()
data class InvalidTransactionIds(val transactionIds: List<Long>) : ValidationState()
data class BadSignatures(val inputs: List<Input>) : ValidationState()

It may be interesting to read the following code, but more important is that you understand the different cases being validated. All of the cases have been described above. The code is organized with private methods performing each of the validation algorithms at the top, and a simple check which leverages these methods to generate an error when necessary.

  /**
   * Logic for validating the content of new block.
   */
  fun validate(block: LynxBlock) : ValidationState {
    /**
     * Last hash must equal previous block's hash.
     */
    fun badLastHash() = chain.isNotEmpty() && (chain.last().getHash() != block.lastHash)

    /**
     * Find inputs referencing spent transaction-ids.
     */
    fun previouslySpentTransactions() : List<Input> {
      return block.data
          // Get all the input transactions.
          .map {it.inputs }.flatten()
          // Get inputs which are NOT identified in the unspent cache.
          .filter { !unspentOutputCache.containsKey(it.id) }
    }

    /**
     * Look for duplicate transactionIds in the current transaction list.
     */
    fun doubleSpendsInCurrentTransaction() : Map<Long,Int> {
      return block.data
          // Get all the input transactions.
          .map { it.inputs }.flatten()
          // Group them by transaction ID, count occurrences.
          .groupingBy{ it.id }.eachCount()
          // Filter out the valid cases (spent 0 or 1 times).
          .filter { it.value > 1 }
    }

    /**
     * Make sure the sum of Inputs is >= the sum of Outputs
     */
    fun inputsGreaterThanOutputs() : List<Transaction> {
      // Lookup inputs and tally their values.
      fun getInputsValue(transaction: Transaction) : Double =
          transaction.inputs
              .map { this.unspentOutputCache[it.id]?.value ?: 0.0 }
              .sum()

      return block.data
          // skip coinbase transaction
          .drop(1)
          .filter { getInputsValue(it) < it.value() }
    }

    /**
     * Compute the coinbase transaction size.
     */
    fun coinbaseTransactionSize() : Double {
      return block.data[0].outputs.map { it.value }.sum()
    }

    /**
     * Transaction IDs should all be greater than the largest ID in the last block,
     * and unique in the current transaction list.
     */
    fun invalidTransactionIds() : Map<Long, Int> {
      return block.data
          // Get all the input transactions.
          .map { it.outputs }.flatten()
          // Group them by transaction ID, count occurrences.
          .groupingBy{ it.id }.eachCount()
          // Look for duplicate transaction IDs.
          .filter { it.value > 1 || it.key <= lastId }
    }

    /**
     * Verify that the signatures match.
     */
    fun badSignatures() : List<Input> {
      return block.data
          .map { it.inputs }
          .flatten()
          .filter { !verifySignature(it) }
    }

    //
    //
    // Do the checks.
    //
    //

    if (badLastHash()) {
      return InvalidLastHash(chain.last().getHash(), block.lastHash)
    }

    // Inputs must not be spent.
    previouslySpentTransactions().let {
      if (it.isNotEmpty()) {
        return PreviouslySpentTransactions(it.map { it.id }.toList())
      }
    }

    // A transaction must not be used in multiple Inputs.
    doubleSpendsInCurrentTransaction().let {
      if (it.isNotEmpty()) {
        return TransactionDoubleSpend(it.map { it.key }.toList() )
      }
    }

    // Transaction inputs > outputs.
    inputsGreaterThanOutputs().let {
      if (it.isNotEmpty()) {
        return InsufficientInputValue(it)
      }
    }

    // Coinbase reward transaction is not too large.
    coinbaseTransactionSize().let {
      if (it > REWARD) {
        return CoinbaseRewardTooLarge(it)
      }
    }

    // Validate transaction IDs are unique and increase in size.
    invalidTransactionIds().let {
      if (it.isNotEmpty()) {
        return InvalidTransactionIds(it.map { it.key }.toList())
      }
    }

    badSignatures().let {
      if (it.isNotEmpty()) {
        return BadSignatures(it)
      }
    }

    // Verify transaction signatures.
    return Valid
  }

Tests

I won't be covering the tests. They can be explored in the full source listing on GitHub. I happen to be using JUnit5, which uses the @Test annotation preceding each test method. One of the tests also uses @ParameterizedTest which is a new feature for JUnit5 allowing dynamic test inputs.

Next time

Things are really ramping up now. The blockchain concept was simple, and even though the idea of Transactions is pretty simple as well, as we found, there are a lot of small details that need to be just right. We'll continue adding on details next time as we start to look into what it takes to make LynxCoin decentralized. We'll discuss Mining, the Byzantine Generals' Problem and some of the solutions. We'll implement Proof of Work and enable some simple endpoints to allow LynxCoin to go distributed!