microledger: UTxO

A few months/years ago, I was interviewing for IOG, the company behind the Cardano distributed blockchain.

At some point, I reached the last technical round; I had 10 days to get ready, including 2 weekends.

I went through the documentation, tutorials, conferences, 6 research papers, 4 toy smart contracts, and 7 pages in roughly 30 hours.

I did not land the position, so it is time to increase my return on time invested!

Following the feedback of microgpt, we will build a functional distributed blockchain from scratch.

It will be a mix-up of my memories of plutus and the information about Cardano I was able to find.

By no means does it aim to be a replica of Cardano; I will cut corners and assume things will go well.

We will call it microledger, and I have hesitated to call it Cardino, ino meaning small in Italian.

At the time of writing, I have 10 versions of the ledger (in charge of transactions), which I will split in 8 logs.

I also have 2 time-sensitive logs scheduled, which means that we will have logs until January 2027.

Beyond this, there is the script virtual machine, consensus and networking layers, and CLI, so between 6 and 10 logs.

A blockchain is an ecosystem based around blocks.

Each block contains a set of transactions, which is the support of unspent transaction output (UTxO).

The basic idea behind it is that each unit of currency (in Cardano, the currency is called Ada, and each one could be divided into 1.000.000 of lovelace) is distinct and traced.

Meaning that a set of lovelaces belongs to someone only because they can “spend” them, usually with a cryptographic key; we also call that unlocking.

Transactions maintain the causality between spending, and the history.

We can start by drafting the following types:

-- TxOut simply locks a value (Ada) to an Address. It doesn't know about wallets.
data TxOut = TxOut
  { address :: Address Wallet,
    value :: Ada
  }
  deriving (Eq, Show)

-- An output reference uniquely identifies a specific unspent output.
data TxOutRef = TxOutRef
  { txId :: TxId,
    txOutIdx :: TxOutIdx
  }
  deriving (Eq, Ord, Show)

-- Will be the hash of the transaction
newtype TxId
  = TxId {unTxId :: Word64}
  deriving newtype (Eq, Ord, Show)

-- The index of the output of a transaction
newtype TxOutIdx
  = TxOutIdx {unTxOutIdx :: Int}
  deriving newtype (Eq, Ord, Show, Num, Enum)

newtype Ada
  = Ada {unAda :: Fixed E6}
  deriving newtype (Eq, Ord, Show)
  deriving (Semigroup, Monoid) via (Sum (Fixed E6))

-- TxIn points to the TxOutRef and provides the signature (Redeem) to unlock it.
data TxIn = TxIn
  { txOutRef :: TxOutRef,
    pubKey :: PublicKey,
    redeem :: Signature
  }
  deriving (Eq, Show)

-- A Transaction is simply a list of inputs being consumed and new outputs being created.
data Transaction = Transaction
  { txId :: TxId, -- Will be the hash of this transaction
    txInputs :: [TxIn],
    txOutputs :: [TxOut]
  }
  deriving stock (Eq, Show, Generic)

data Wallet = Wallet
  { key :: PublicKey,
    balance :: Ada
  }
  deriving stock (Eq, Show, Generic)

newtype Address a
  = Address {unAddress :: Hash.Hash}
  deriving newtype (Eq, Ord, Show)

newtype PublicKey
  = PublicKey {unPublicKey :: Sign.PublicKey}
  deriving newtype (Eq)

instance Show PublicKey where
  show _ = "<PublicKey>"

-- A basic cryptographic signature
newtype Signature
  = Signature {unSignaure :: Sign.SignedMessage}
  deriving newtype (Eq)

instance Show Signature where
  show _ = "<Signature>"

newtype SecretKey
  = SecretKey {unSecretKey :: Sign.SecretKey}
  deriving newtype (Eq)

instance Show SecretKey where
  show _ = "<SecretKey>"

-- | Generates a new Ed25519 key pair using Sel.
generateKeyPair :: IO (PublicKey, SecretKey)
generateKeyPair = bimap PublicKey SecretKey <$> Sign.generateKeyPair

Note: we rely on this contribution to sel to support cryptographic operations.

One of the cornerstones of blockchains is cryptography, which allows for having both computationally expensive functions (reverting a hash of a ciphered text).

For instance, hashing is used as a way to ensure information is known, as follows:

-- | Hashes a public key to produce a standard Wallet Address.
deriveAddress :: PublicKey -> Address a
deriveAddress pub = Address $ Hash.hashByteString (Sign.publicKeyToBinary pub.unPublicKey)

-- | Signs a payload (the TxId) using the sender's Ed25519 SecretKey.
signTx :: SecretKey -> TxId -> IO Signature
signTx sek txid = Signature <$> Sign.signMessage (bsTxId txid) sek.unSecretKey

-- | Verifies an Ed25519 signature against a PublicKey and the expected TxId payload.
verifySignature :: PublicKey -> Signature -> TxId -> Bool
verifySignature pub sig txid = Sign.openMessage sig.unSignaure pub.unPublicKey == Just (bsTxId txid)

-- | Checks if a given PublicKey mathematically hashes to the provided Address.
verifyAddress :: PublicKey -> Address a -> Bool
verifyAddress pub addr = deriveAddress pub == addr

bsTxId :: TxId -> BS.StrictByteString
bsTxId = BSL.toStrict . BSB.toLazyByteString . BSB.word64Hex . (.unTxId)

For example, in the code above, we sign a transaction with the TxId and the signer's SecretKey, known by one person.

Verifying the signature consists only of opening the Signature again, the signer's PublicKey, known by everyone, and checking that it is effectively TxId.

One thing worth mentioning is that UTxO are tracked so they can be unlocked in upcoming transactions, as follows:

-- The UTxO set maps these references to the actual locked outputs.
newtype UTxO = UTxO
  {unUTxO :: Map.Map TxOutRef TxOut}
  deriving newtype (Eq, Show)

The main function is applying a transaction on the current UTxO, enforcing input existence, unlocking permissions, and integrity, and finally producing the updated UTxO, as follows:

applyTx :: Transaction -> UTxO -> Maybe UTxO
applyTx tx (UTxO utxo) = do
  -- 1. Lookup all consumed outputs and pair them with their inputs
  consumed <- mapM (\txIn -> (txIn,) <$> utxo Map.!? txIn.txOutRef) tx.txInputs

  -- 2. Verify authorization
  guard $ all (\(txIn, txOut) -> verifySignatureRedeem txOut.address txIn.pubKey txIn.redeem tx.txId) consumed

  -- 3. Verify conservation of value
  let inputsValue = foldMap ((.value) . snd) consumed
      outputsValue = foldMap (.value) tx.txOutputs
  guard $ inputsValue == outputsValue

  -- 4. Update the UTxO map
  let utxoMinusInputs = foldl' (flip Map.delete) utxo ((.txOutRef) <$> tx.txInputs)
  return $
    UTxO $
      foldl'
        (\u (idx, out) -> Map.insert (TxOutRef tx.txId idx) out u)
        utxoMinusInputs
        (zip [0 ..] tx.txOutputs)

-- | Verifies that the provided PublicKey matches the locking Address,
-- and that the Signature is valid for the TxId.
verifySignatureRedeem :: Address Wallet -> PublicKey -> Signature -> TxId -> Bool
verifySignatureRedeem addr pubKey sig txId =
  verifyAddress pubKey addr && verifySignature pubKey sig txId

As a bonus, we can represent blocks as follows:

data Block = Block
  { blId :: BlockId,
    blTxs :: [Transaction]
  }
  deriving stock (Eq, Show, Generic)

newtype BlockId
  = BlockId {unBlockId :: Int}
  deriving newtype (Eq, Ord, Show)

applyBlock :: Block -> UTxO -> Maybe UTxO
applyBlock block utxo = foldM (flip applyTx) utxo block.blTxs

Note: applying blocks is simply chaining of applyTx.You can find the full source and tests here.