# Witch Hunts (Not) Considered Harmful, or, A General Algorithm for Trust in a Network

In a distributed system, we quite often want to have some sort of “trust” or “opinion” metric, by which we can tell if a node is good or bad. These come in many forms, and so in here I shall describe a fairly general algorithm with which we can extend (for the cost of a small communication and memory overhead) any distributed system to have trust.

# A Gentle Introduction to Parsec

It seems to me that there aren’t many step-by-step introductions to parsec, where you build up a parser as you go. This is especially the case for applicative parsec, which is a shame as applicative functors are nice. So, I wrote one. Today, we are going to learn how to use applicatives and parsec to parse a CSV file. We’ll start off with a very basic one where there can be no commas or escape characters in the fields, then add support for quoted fields which can contain any character, and then we’ll add support for special escape characters (numeric literals and the like). Finally, I’ll leave two small exercises that you might want to work on, just to check that you managed to get everything.

# Indexing collections in Haskell, or, Abstraction with Typeclasses

A typeclass in Haskell is a family of types, all of which implement some common operations. For example, the Num typeclass implements operations like (+) and (-), the Monad typeclass implements (>>=) and return. We can define typeclasses for pretty much any behaviour we want, and I’m going to use indexable data structures to show how we can go from an initially fairly concrete specification to a more abstract one.

Indexable structures are a good example, I think, as three immediately come to mind, [], Array, and Map, all of which have indexing operations, all of which have different names ((!!), (!), and lookup, respectively). If we could just have one operator to extract a value from a container by index, that would surely be much better, and we could write more generic code.

Just to clarify, we want to go from this mess:

> (!)    :: Ix i => Array a -> i -> a
> (!!)   :: [a] -> Int -> a
> lookup :: Ord k => Map k a -> Maybe a


To this beauty:

> (!!!) :: indexable container -> index -> value


Let’s also add an operator to handle cases where we don’t know if the index is valid:

> (!+!) :: indexable container -> index -> Maybe value


# Coproducts, F-Algebras, and Catamorphisms

A catamorphism is the generalisation of a fold to any recursive data type. The concept comes directly from category theory, and so I’ll first explain the category theoretic underpinnings, and then show some examples in Haskell (which will probably be far more intelligible to most readers).

# Dealing Cards Fairly, or, Verifying Agent Behaviour After the Fact

Card games are fun, everyone likes card games. However, can they be more fun? Well, I find it fun to try and solve nonexistent problems, so (if you’re me), yes! Now, what prevents me from going through the entire deck of cards and picking out only the cards that I want, when it’s my turn to draw? Everyone else watching me, of course. How can we replicate this in a decentralised system? Well, let’s more precisely state what it is we want to do:

1. Shuffle the deck in a way that every player agrees is random, and in such a way that no player knows the order of the cards.
2. Allow players to draw from the deck, in such a way that they do not get to choose the card they draw, and such that no other player knows what they drew.
3. Allow players to discard cards, in such a way that no other player knows what they discarded (optional).

# Allocating Roles in a Game, or, Communally Generating Random Sequences

This post is an indirect follow-on of How to Play Rock-Paper-Scissors Online, or, Committing to Choices in Decentralised Systems, and assumes familiarity with commitment schemes.

Let’s say that a group of people want to play a game, and there are a number of roles that must be played. Some are generally considered better than others, and so everyone simply picking their favourite role won’t work out. If there is some sort of trusted game master, then they can allocate the roles randomly, but such an invigilator is never completely above the influence of the other players. If someone really wants to play the wizard, they could threaten the game master’s family. So, we want a way for the players to randomly allocate the roles, in such a way that everyone agrees the allocation is random.

# How to Play Rock-Paper-Scissors Online, or, Committing to Choices in Decentralised Systems

Let’s say that you and a good friend have some dispute, and you have decided to settle this through the most ancient and noble sport of rock-paper-scissors. If you’re both in the same place, this poses no problems at all, however, if you’re not there is a difficulty. Alice could make her move, email it to Bob (the traditional names of the two participants in cryptography), and then Bob could read that and very quickly email Alice with his (winning) choice. Email can suffer from unpredictable delays, and so it’s not easy to tell whether Bob has cheated in this way, based on a single game at least.