An example in Erlang of a crytographically fair distributed coin toss. This example also includes totally unnecessary calls to an inefficient recursive definition of the fibonacci function to generate some non-trivial computation in each process so we can better see the parallelism in the system monitors.

coin_toss.erl

%% @author mcphee
%% @doc An example in Erlang of a crytographically fair
%% distributed coin toss. 

% There are a ton of commented out erlang:display/1 calls that illustrate
% a fairly brute force approach to debugging this sort of code. It can be
% really difficult to tell what's going on in a process, and using erlang:display/1
% (which should *only* be used for debugging instead of "real" I/O) can be
% a useful way to see what's happening.

-module(coin_toss).

%% ====================================================================
%% API functions
%% ====================================================================
-export([pair/2, pair_all/1, create_people/1, counter_loop/2, wait/1, wait_for_choice/5, wait_for_outcome/4]).

% Peeps = coin_toss:create_people(100).
% coin_toss:pair_all(Peeps).

create_people(Num_people) ->
	% erlang:display("About to create people"),
	register(counter, spawn(coin_toss, counter_loop, [0, 0])),
	lists:map(fun(N) -> spawn(coin_toss, wait, [N]) end, lists:seq(1, Num_people)).

pair(First_pid, Second_pid) ->
	First_pid ! {start, Second_pid}.

pair_all([]) -> true;
pair_all([A, B | Rest]) ->
	pair(A, B),
	pair_all(Rest).

counter_loop(Heads_wins, Tails_wins) ->
	% erlang:display("Running counter loop"),
	receive
		report ->
			io:format("~w heads wins and ~w tails wins~n", [Heads_wins, Tails_wins]),
			counter_loop(Heads_wins, Tails_wins);
		{heads, won} ->
			io:format("Heads won~n"),
			counter_loop(1 + Heads_wins, Tails_wins);
		{tails, lost} ->
			io:format("Heads won~n"),
			counter_loop(1 + Heads_wins, Tails_wins);
		{heads, lost} ->
			io:format("Tails won~n"),
			counter_loop(Heads_wins, 1 + Tails_wins);
		{tails, won} ->
			io:format("Tails won~n"),
			counter_loop(Heads_wins, 1 + Tails_wins)
	end.

% The starting state, waiting for someone to pair us up with another
% process to do a cryptographic coin toss. One option in this state is
% to receive a start message, which pairs us with another process; we 
% create a hashed flip and send that to them. The other option is to
% receive a choose message from another process that has already created
% a hashed flip and asks us to choose heads or tails and send our choice.
wait(ID) ->
	% erlang:display("About to start up a process.~n"),
	receive
		{start, Partner} ->
			% erlang:display("Received a request to start"),
			Flip = case crypto:rand_uniform(0, 2) of
					   0 -> tails;
					   1 -> heads
				   end,
			% erlang:display("flipped"),
			io:format("Flip was ~w.~n", [Flip]),
			{Salt, Hashed_flip} = hash_flip(Flip),
			% erlang:display("hashed"),
			Partner ! {choose, self(), Hashed_flip},
			% erlang:display("Contacted partner"),
			wait_for_choice(ID, Partner, Flip, Salt, Hashed_flip);
		{choose, Partner, Hashed_flip} ->
			% erlang:display("Received a request to choose"),
			% The fib call is just to put some expensive computation in
			% the system so we can see the parallelism at the system
			% system monitor level. Feel free to remove this, or raise
			% or lower the argument to fib to change the amount of work
			% being done here.
			F = fib(35),
			Choice = case (crypto:rand_uniform(0, 2) + F) rem 2 of
						 0 -> tails;
					     1 -> heads
					 end,
			% erlang:display("Made choice"),
			% io:format("Choice was ~w.~n", [Choice]),
			Partner ! {check_outcome, self(), Choice, Hashed_flip},
			% erlang:display("Asked partner to check outcome"),
			wait_for_outcome(ID, Partner, Choice, Hashed_flip);
		stop ->
			true
	end.

% In this state we've flipped the coin, and sent a hash of the flip
% to our partner. We're now waiting for them to choose heads or tails
% and send us that choice. When we receive that we determine whether 
% they won and send that and the unhashed flip to our partner for 
% confirmation.
wait_for_choice(ID, Partner, Flip, Salt, Hashed_flip) ->
	% erlang:display("Waiting for choice"),
	receive
		{check_outcome, Partner, Choice, Hashed_flip} ->
			% erlang:display("Received choice"),
			Result = case Choice == Flip of
						 true -> won;
						 false -> lost
					 end,
			% erlang:display("Computed result"),
			io:format("Flip was ~w, choice was ~w, results was ~w.~n", [Flip, Choice, Result]),
			Partner ! {confirm_result, self(), Result, Flip, Salt, Hashed_flip}
			% erlang:display("Asked partner to confirm")
	end.

% In this state we've made our choice and sent it to our partner. We're
% now waiting for them to decide if we won and send us that result along with
% the unhashed version of the flip and the salt so we can confirm that they didn't
% cheat.
wait_for_outcome(ID, Partner, Choice, Hashed_flip) ->
	% erlang:display("Waiting for outcome"),
	receive
		{confirm_result, Partner, Result, Flip, Salt, Hashed_flip} ->
			% erlang:display("Received outcome"),
			case (Choice == Flip) == (Result == won) of
				true -> true;
				false -> exit("Partner didn't process toss correctly")
			end,
			% erlang:display("Confirmed outcome"),
			{Salt, Hash_check} = hash_flip(Salt, Flip),
			% erlang:display("Computed hash"),
			case Hash_check of
				Hashed_flip -> true;
				_			-> exit("Partner's hashed flip didn't match")
			end,
			% erlang:display("Checked hash"),
			io:format("Processing choice ~w and result ~w.~n", [Choice, Result]),
			counter ! {Choice, Result}
			% erlang:display("Notified counter")
	end.

%% ====================================================================
%% Internal functions
%% ====================================================================

hash_flip(Flip) ->
	Salt = integer_to_list(crypto:rand_uniform(0, 1000000)),
	hash_flip(Salt, Flip).
hash_flip(Salt, Flip) ->
	{Salt, crypto:md5(string:concat(Salt, atom_to_list(Flip)))}.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

The coin toss algorithm implemented here is similar to, but not exactly the same as, the one described on Wikpedia. The main difference is that here I have the flipper commit first instead of having the caller commit, but I think that's really a cosmetic difference.