An Erlang simulator of the effectiveness of bitmap attacks on RandomX scratchpad entropy, given various parameters. It also simulates these attacks against RandomXSquared; a new algorithm that optimizes the resilience of RandomX entropy generation by mixing entropy (optionally across multiple parallel RX instances) periodically.

rx_bitmap_sim.erl

-module(rx_bitmap_sim).
-compile(export_all).

%%% A simple simulator for the RX and RX2 scratchpad bitmap attacks.
%%% run `rx_bitmap_sim:create_report(ProgCount, Divisions)` to see the sizes of bitmaps
%%% that would be needed in order to reconstruct the scratchpad from the
%%% bitmap for N RandomX programs, with D divisions of the programs.

% The number of RX memory cells in the scratchpad.
-define(SCRATCHPAD_CELLS, 262144).

-define(BOOKKEEPING_ISTORES, 16).
-define(PROG_SIZE, (256 + ?BOOKKEEPING_ISTORES)).
-define(BASE_ISTORE_FREQ, 16).
-define(ISTORE_FREQ, (?BASE_ISTORE_FREQ + ?BOOKKEEPING_ISTORES)).
-define(INST_FREQ_TOTAL, 256).
-define(INT_MAX, (2 bsl 64)).
-define(WORD_SIZE, 8).
-define(PROG_COUNT, 10).
-define(PROG_ITER, 2048).

% Whether to use random values for the instruction argument. The 'destination'
% argument is always random.
-define(SIM_RANDOM_ARG, false).

% Whether the 'istore' instruction should only store _that_ the cell was written
% to (bitmap mode), the number of times it was written to (count mode), or store
% the value written to the cell (write mode).
-define(SIM_ISTORE_MODE, bitmap).

create_report() -> create_report(10, 4).
create_report(Progs, Divisions) ->
  report(rx:experiment(rx_vs_rx2, {Progs, Divisions})).

%% @doc Run an experiment to see the size of the bitmap needed to reconstruct
%% the scratchpad after running N RandomX programs, relative to the size of the
%% scratchpad in bytes.
experiment(rx_bitmap_size, MaxProgs) ->
	lists:map(
		fun(N) ->
			{N,
				?MODULE:size(rx_bitmap_attack(1, N, ?PROG_ITER, ?SCRATCHPAD_CELLS)) /
					(?SCRATCHPAD_CELLS * 8) % Calculate scratchpad size in bytes
			}
		end,
		lists:seq(1, MaxProgs)
	);
%% Show the sizes for bitmaps needed to reconstruct the scratchpad for RX and RX2
%% after running N RandomX programs.
experiment(rx_vs_rx2, {MaxProgs, MixDivisor}) ->
	RXFun = fun rx_bitmap_attack/4,
	RX2Fun = fun rx2_bitmap_attack/4,
	lists:map(
		fun(Progs) ->
			{Progs,
				?MODULE:size(RXFun(1, Progs, ?PROG_ITER, ?SCRATCHPAD_CELLS)) /
					(?SCRATCHPAD_CELLS * 8),
				lists:map(
					fun(LogDivMix) ->
						MixEveryNIts = ?PROG_ITER div (1 bsl LogDivMix),
						io:format("Progs: ~p. Mixing every: ~p iterations.~n", [Progs, MixEveryNIts]),
						{MixEveryNIts,
							?MODULE:size(RX2Fun(MixEveryNIts, Progs, ?PROG_ITER, ?SCRATCHPAD_CELLS)) /
								(?SCRATCHPAD_CELLS * 8)
						}
					end,
					lists:seq(1, MixDivisor)
				)
			}
		end,
		lists:seq(1, MaxProgs)
	).

report(Experiment) ->
	io:format("~s~n", [csv(table(Experiment))]).

%% @doc Turn the experiment results into a table.
table(Results = [{_, _, FirstRowResults} | _]) ->
	[["-", "Base"] ++ [ Label || {Label, _} <- FirstRowResults ] ] ++
	lists:map(
		fun({Progs, Baseline, LabeledResults}) ->
			[Progs, Baseline | [ Result || {_Label, Result} <- LabeledResults ] ]
		end,
		Results
	).

%% @doc Turn the table into a CSV string.
csv([]) -> [];
csv([Row | Rows]) ->
	lists:join(",", lists:map(
		fun(Cell) ->
			case Cell of
				X when is_float(X) -> io_lib:format("~f", [X]);
				X when is_integer(X) -> integer_to_list(X);
				X when is_binary(X) -> binary_to_list(X);
				X when is_atom(X) -> atom_to_list(X);
				_ -> "-"
			end
		end,
		Row
	)) ++ "\n" ++
	csv(Rows).

gen_scratchpad() ->
	gen_scratchpad(?SCRATCHPAD_CELLS).
gen_scratchpad(Size) ->
	lists:foldl(
		fun(N, Acc) ->
			Acc#{ N => 0 } end,
		#{},
		lists:seq(1, Size)
	).

%% Generate a random RX program. Only `istore` and `nop` instructions are used.
gen_prog() ->
	gen_prog(?PROG_SIZE).
gen_prog(Size) ->
	lists:map(
		fun(_N) ->
			case rand:uniform(?INST_FREQ_TOTAL) of
				N when N =< ?ISTORE_FREQ -> fun istore/3;
				_ -> fun nop/3
			end
		end,
		lists:seq(1, Size)
	).

%% @doc Simulate running a program on a scratchpad, with random values for the
%% instruction arguments.
run_prog(M, Prog) ->
	lists:foldl(
		fun(Inst, Acc) ->
			case ?SIM_RANDOM_ARG of
				false -> Inst(Acc, rand:uniform(?INT_MAX), 0);
				true -> Inst(Acc, rand:uniform(?INT_MAX), rand:uniform(?INT_MAX))
			end
		end,
		M,
		Prog
	).

%% @doc Simulate the `istore` instruction. Ignore the value argument, but increment
%% the count of writes to the destination cell.
istore(Pad, Dst, Val) ->
	DstIndex = Dst rem ?SCRATCHPAD_CELLS + 1,
	case ?SIM_ISTORE_MODE of
		bitmap -> Pad#{ DstIndex => 1 };
		count -> Pad#{ DstIndex => maps:get(DstIndex, Pad) + 1 };
		write -> Pad#{ DstIndex => Val }
	end.

%% @doc Simulate the `nop` instruction. Do nothing.
nop(Pad, _Dst, _Val) ->
	Pad.

%% @doc Simulate the RX scratchpad undergoing a series of programs, referenced
%% by the number of instructions to run.
rx() -> rx(?PROG_COUNT).
rx(Instrs) ->
	rx(Instrs, ?SCRATCHPAD_CELLS).
rx(Instrs, Size) when is_integer(Size) ->
	rx(Instrs, gen_scratchpad(Size));
rx(Instrs, Scratchpad) when is_map(Scratchpad) ->
	run_prog(Scratchpad, gen_prog(Instrs)).

%% @doc Simulate the bitmap attack on RX. Returns a bitmap of the scratchpad
%% after running N programs for I iterations each.
rx_bitmap_attack(_Mixes, NumPrograms, Iterations, Size) ->
	bitmap(rx(NumPrograms * Iterations * ?PROG_SIZE, Size)).

%% @doc Simulate the bitmap attack on RX2. Returns a combined bitmap of the
%% scratchpads after running N programs for I iterations each.
rx2_bitmap_attack(MixEveryNIts, Programs, Iterations, Size) ->
	TotalInstrs = Programs * Iterations * ?PROG_SIZE,
	InstrsPerMix = MixEveryNIts * ?PROG_SIZE,
	Mixes = TotalInstrs div InstrsPerMix,
	lists:foldl(
		fun(MixPhase, BitmapAcc) ->
			PhaseScratchpad = rx(InstrsPerMix, Size),
			merge_bitmap(MixPhase, BitmapAcc, bitmap(PhaseScratchpad))
		end,
		#{},
        lists:seq(1, Mixes)
    ).

%% @doc Return a bitmap of the scratchpad, including a key with the size of 
%% the map itself.
bitmap(M) ->
	(maps:filter(fun(_, Count) -> Count > 0 end, M))#{
		map_size => maps:size(M) div 8
	}.

%% Calculate the size of a bitmap or scratchpad in bytes.
size(Bitmap) ->
	lists:sum(maps:values(sizes(Bitmap))).

%% Return a map of the size of each cell in a (combined)bitmap or scratchpad.
sizes(Bitmap) ->
	maps:filtermap(
		fun({_, map_size}, Size) -> {true, Size};
			(map_size, Size) -> {true, Size};
			(_, _) -> {true, ?WORD_SIZE}
		end,
		Bitmap
	).

%% @doc Merge two bitmaps, adding a prefix to the cell keys. The output is what
%% the attacker would need to store in order to reconstruct the scratchpad without
%% executing any programs.
merge_bitmap(Name, Bitmap1, Bitmap2) ->
	maps:merge(Bitmap1,
		maps:from_list(
			lists:map(
				fun({Cell, Count}) ->
					{{Name, Cell}, Count}
				end,
				maps:to_list(Bitmap2)
			)
		)
	).

%% Extract only the cells that have been written to NumWrites times.
cells_with_writes(M, NumWrites) ->
	maps:filter(fun(_, Writes) -> Writes =/= NumWrites end, M).

%% @doc return the frequency of writes to a cell
writes_per_cell(M2, Max) ->
	[ 
		{
			N,
			maps:size(cells_with_writes(M2, N)) / maps:size(M2)
		} || N <- lists:seq(0, Max)
	].