Pages:
Author

Topic: Selfish Mining Simulation (Read 14057 times)

newbie
Activity: 28
Merit: 0
September 17, 2014, 03:16:24 AM
#55
It would be interesting use the simulation to see what marginal benefit, if any, can be attained for a Block Discard attacker at 49.9%-50% hashing share. Could it help to give the attacker a leg-up into majority hashing?

agree, but i wonder if the simulation would be attacked by real attacker?
newbie
Activity: 28
Merit: 0
September 14, 2014, 02:12:13 AM
#54
It would be interesting use the simulation to see what marginal benefit, if any, can be attained for a Block Discard attacker at 49.9%-50% hashing share. Could it help to give the attacker a leg-up into majority hashing?

it will be helpful, i can do the simulation before jumping into the ocean.
aha...
newbie
Activity: 28
Merit: 0
June 05, 2014, 08:05:12 PM
#53
This is really cool.  I've been watching it run on a couple of computers here.

I'm getting consistent results here, showing that the selfish mining strategy is a really good way to lose 20-30% of your mining revenue.  I'll note that this is roughly what I was expecting.  In every other context, the whole world considers it obvious that getting your blocks out as fast as possible is a good thing.  Still, science is the art of not fooling yourself, and getting the result you expect is not the same as showing that a model has skill.

As fun as this is, it needs to be much faster to be really useful.  We need hundreds or thousands of runs, covering hundreds or thousands of blocks.  We also need to verify that model parameters are realistic, and that the simulation isn't adding or causing un-real effects.  We should also invite the authors to verify that the attack behavior is implemented correctly.*

* To the limited extent possible.



+1   Super agree man.. Still u'll need to check your data if they are real or not in a network os the same size and conditions... or your experiment will be a total fail ;p
sr. member
Activity: 278
Merit: 251
Bitcoin-Note-and-Voucher-Printing-Empowerer
May 31, 2014, 10:05:40 AM
#52
I wrote an educational simulator (ca. 500 lines of code incl. many comments) that simulates and visualizes the selfish mining.

It runs under Matlab (commercial - nicest graphics) and Octave (freeware open source Linux/Windows, also works nicely).
"FreeMat" (open source freeware for Windows) is also supported,  but the nice graphical illustration does not work (yet).


The simulator displays the chain of blocks that are mined, dynamically, like a film. You can have it run automatically (e.g. every 0.1 seconds one new block is displayed) or interactively (keypress after each block). The tool visualizes both the "public" blockchain, as well as the "secret" chain that the selfish miner is working on.

Blocks get different colors, depending on whether they have been mined by the honest miners or the selfish miner, and whether they caused any orphans. So you can also see how often selfish miners create orphans on the public blockchain, and how long they are. Sometimes they are really long!

At the end of the simulation, you get some statistics concerning the orphans created on the public blockchain (histogram about how often orphans of different lengths have been created).

The simulator can be configured in that the selfish miner self-restricts itself to not create any orphans longer than a pre-defined maximum. This of course reduces the income that the selfish miner can generate. Also various other configuration variables exist (e.g. the selfish miner's share of max. hash rate, of course).

Network propagation times are NOT modeled, the focus is to investigate, illustrate and understand the basic principles of selfish mining.

Also long simulations can be performed and graphic outputs disabled, thereby simulation of 1 Million blocks takes only a few seconds on Matlab on a >7 years old PC (FreeMat and Octave is by a factor 10 to 100 slower as it seems).

Here are some screenshots:







Enjoy! (and donate whatever you consider reasonable)

Here's the source code - copy-paste to text editor and save as file "selfish.m":

Code:
function selfish(Nsim, PercentSelfish, MaxOrphanLen, PlotFlag, PauseValue, RndState)
% ------------------------------------------------------------------------------------------------------------
% function selfish()
% function selfish(Nsim, PercentSelfish, MaxOrphanLen, PlotFlag, PauseValue, RndState)
%
% This function simulates and ilustrates the selfish bitcoin mining.
%
% As we see, selfish mining works if the mining power of the selfish miner is more than one 3rd of the total
% mining power.
%
% Network propagation times are not modelled and are assumed to be zero (best case from selfish miner's
% perspective)
%
% Optional arguments:
% * Nsim (def.=100): Length of simulation time in terms of number of blocks on the public main blockchain
% * PercentSelfish (def.=40.586): Percent of the selfish miner's overall network hashing power
% * MaxOrphanLen (def.=5): Selfish miner will avoid creating orphans on main chain longer than this nb of blocks.
% * PlotFlag (def.=1=true): If set to =false or =0, no illustratetive plot will be made -> set =false for long simulations!
% * PauseValue (def.=inf): When plotting is active, this many seconds of waiting time is added after each block.
%                          Set =inf to require keypress after each block.
%                          For Non-Matlab, default = 0.1 [sec] and =inf is not supported.
% * RndState (def.=sum(100*clock)): set to a certain value (e.g. integer number) to set random seed.
%
% Example function calls:
%    > selfish % run with default settings - good for learning and demonstration purposes                                           <-- good for educational purposes
%    > selfish(40, 48, 3, true, inf, 8) % short interactive simulation with limitation of the orphan lengths in the main chain      <-- very good for educational purposes
%    > selfish(200, 41, inf, true, 0.01, 1) % self-running simulation, watch while running. Certain random seed for reproducibility <-- very good for educational purposes
%    > selfish(200, 41, inf, true, 0.01) % self-running simulation, watch while running. Random seed is different each time
%    > selfish(1e4, 45, inf, false, false, 4) % run a long simulation without plotting during simulation time
% ------------------------------------------------------------------------------------------------------------
% Tested with Matlab R2007b, Octave 3.0.0 (Linux) and FreeMat 4.1.1 (Windows).
% Restriction for FreeMat: only works for PlotFlag=false
%
% Octave is open-source freeware, available for Windows and Linux.
% FreeMat is open-source freeware, available for Windows.
%
% If you start Octave (or Matlab or FreeMat), you see a command window (console).
% There you simply enter (where ">" denotes the console's command prompt):
%    > cd the_path/where/this_file/is_located
%    > selfish
%
% Note: In the comments of this file, the terms "selfish miner" and "attacker" are used interchangeably,
%       they refer to the same thing.
% ------------------------------------------------------------------------------------------------------------
%
% License:
% --------
% * Use is permitted as long as the user has donated an amount that he/she considers reasonable, or if the
%   user truly thinks that a donation is not required.
%
% * Reuse/modify/extend as you like, commercially or non-commercially.
%
% * The only condition is that you include this license condition in the source code, and include a reference
%   to the original author and the bitcoin donation address both in the source code and being displayed
%   by the running program.
%
% Bitcoin Donations to the author: 1MichaS16UMKFgNjanKrtfD51HpBkqPAwD (Michael_S at bitcointalk.org)
% ------------------------------------------------------------------------------------------------------------

global power_attack % selfish miner's hasing power share
global THR_orphanes_publish % max number of orpans that the selfish miner will create on the public main chain
global Pause_value % pause in seconds after each block, when plotting is active

ismatlab = false;
v=version;% typical Matlab version string: "7.5.0.338 (R2007b)"; typical Octave version string: "3.0.0"
if ~isempty(strfind(v,'R2')), % Matlab version string contains "R2" in it.
    ismatlab = true;
end

%% 0 - Parameters (adjust to your liking)

% - - - - - Parameters that can be overruled by function arguments: - - - - -

% 0.1 - Change as desired: (may be overruled by function arguments)
%power_attack = 0.17; % between 0 and 1 (0.40586 yields 50% of the blocks, 0.5 yields 100%)
power_attack = 0.40586; % between 0 and 1 (0.40586 yields 50% of the blocks, 0.5% yields 100%)
%power_attack = 0.44; % between 0 and 1 (0.40586 yields 50% of the blocks, 0.5 yields 100%)
%power_attack = 0.51; % between 0 and 1 (0.40586 yields 50% of the blocks, 0.5 yields 100%)

% 0.2 - Change as desired: (may be overruled by function arguments)
% The selfish miner gets the highest yield when setting the following parameter to "inf", but this might be "impractical".
% Setting this to e.g. =5 or =10 gives a yield close to theoretical maximum while avoiding creation of too long orphans in the main chain.
% Hence, e.g. setting it to =5 might be a reasonable choice, to ensure that blocks of depth=6 in the public main chain are never orphaned by the selfish miner.
THR_orphanes_publish = 5; % (>=1) [best is =inf] If the attacker creates so many orphans in the main chain, he publishes before even more orphans are created.
%THR_orphanes_publish = inf; % (>=1) [best is =inf] If the attacker creates so many orphans in the main chain, he publishes before even more orphans are created.

% 0.3 - Change as desired: (may be overruled by function arguments)
N = 1e6; % number of blocks to be simulated
N = 1e5; % number of blocks to be simulated
N = 100; % number of blocks to be simulated

% 0.4 - Change as desired: (may be overruled by function arguments)
plot_flag = 1;% =1 for plotting illustrative block chain and interactive keypress; =0 for not plotting (faster).

% 0.5 - Change as desired: (may be overruled by function arguments)
try
    rand('state', 1);% set random generator seed
    rand('state', sum(100*clock));% set random generator seed
catch
    % Freemat does understand the above format, but instead this:
    seed(1,1);% set random generator seed
    seed(sum(100*clock),sum(100*clock));% set random generator seed
end

% - - - - - Parameters that can NOT be overruled by function arguments: - - - - -

% 0.6 - Normally keep the "best" values!
THR_attack_give_up = 1; % (>=1) [best is =1] If main chain is so much longer than the own "secret" chain, then attacker gives up and adopts the main chain's blocks.
THR_attack_publish = inf; % (>=2) [best is =inf] If the attacker has so many secret blocks, he will publish them (e.g. to avoid loosing them due to checkpointing).


% ------------------------------------------------------------------------------------------------------------
% ------------------------------------------------------------------------------------------------------------

%% 1.1 - Overruling pre-set parameters with function arguments:
if exist('Nsim', 'var'),
    N = Nsim;
end
if exist('PercentSelfish', 'var'),
    power_attack = PercentSelfish/100;
end
if exist('MaxOrphanLen', 'var'),
    THR_orphanes_publish = MaxOrphanLen;
end
if exist('PlotFlag', 'var'),
    plot_flag = PlotFlag;
end
if ~exist('PauseValue', 'var'),
    Pause_value = inf;
else
    Pause_value = PauseValue;
end
if exist('RndState', 'var'),
    try
        rand('state', RndState);
    catch
        seed(RndState,RndState);
    end
end

%% 1.2 - Pre-Processing
power_normal = 1-power_attack;% mining power (share of the total) of the normal (=honest) miners

gen_time_attack = 10/power_attack;% average time needed to generate a block, in minutes, by attacker
gen_time_normal = 10/power_normal;% average time needed to generate a block, in minutes, by normal (=honest) miners

N_force_terminate = ceil(1.1*N);% ceil(1.1*N) by default

%% 2 - Simulate
% Pre-allocate memory - this is important for simulation time:
blocks_won = NaN*ones(1,ceil(N_force_terminate)); % vector indicating which block was won by the selfish mining attacker
chn = blocks_won;% vector showing the normal (public) chain
cha = blocks_won;% vector showing the chain that the attacker works on
Nb_of_blocks_orphaned_by_attacker = NaN*ones(1,ceil(N_force_terminate));

cnt_event_orphaned = 0;% counter for the *nb of events* that a selfish miner published his secretly mined blocks and thereby orphans honestly mined coins.

kn = 0;% kn is the length of the "official" blockchain that the normal (=honest) miners work on
ka = 0;% ka is the number of mined blocks that the attacker's chain has in common with the official chain.
sa = 0;% sa is the number of blocks already mined secretly by the attacker

Time.Total = 0;% To output timestamps during the simulation, whenever a new block is found

time_next_attack = -gen_time_attack*log(rand());% time until attacker finds the next block
time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block

cnt_blocks.found_normal    = 0;% counts nb of blocks found by honest miners
cnt_blocks.orphaned_normal = 0;% ...of which so many got orphaned (replaced) by blocks found by the selfish miner.
cnt_blocks.found_attack    = 0;% counts nb of blocks found by selfish miner
cnt_blocks.orphaned_attack = 0;% ...of which so many got orphaned (replaced) by blocks found by the honest miners.
cnt_blocks.in_main_chain   = 0;% counts the number of blocks in the (public) main chain.

if plot_flag, [hdn, hda] = plot_chain([0], [0]); end;% pro forma plot
while 1;

    % --- Finding new block, depending on whether normal (=honest) miners or attacker find the next block:
    if time_next_normal < time_next_attack,% the next block is found by the normal (=honest) miners
        cnt_blocks.found_normal = cnt_blocks.found_normal + 1;
        cnt_blocks.in_main_chain = cnt_blocks.in_main_chain + 1;
        Time.Delta = time_next_normal;
        Time.Total = Time.Total + Time.Delta;
        kn = kn + 1;% official block chain grows by one block
        blocks_won(kn) = 0;% block nb. kn found by the normal (=honest) miners [not final, might still be reverted later on]
        chn(kn) = 0;
        if sa == 0, % attacker has no secret blocks
            cha(ka+1:kn) = 0;
            ka = kn;% attacker stays at the official chain
            sa = 0;% attacker stays at the official chain
            time_next_attack = -gen_time_attack*log(rand());% time until attacker finds the next block
            time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block
        elseif kn >= ka + sa + THR_attack_give_up, % normal (=honest) miners have too many blocks, attacker gives up
            cha(ka+1:kn-THR_attack_give_up) = 0.1;% attacker replaces his secret blocks by the official blocks
            chn(ka+1:kn-THR_attack_give_up) = 0.1;% attacker replaces his secret blocks by the official blocks
            cha(kn-THR_attack_give_up+1:kn) = 0;% attacker takes latest official block to his own chain
            cnt_blocks.orphaned_attack = cnt_blocks.orphaned_attack + (kn-THR_attack_give_up-ka);
            ka = kn;% attacker switches to the official chain
            sa = 0;% attacker switches to the official chain
            time_next_attack = -gen_time_attack*log(rand());% time until attacker finds the next block
            time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block
        else % attacker remains on his own chain
            time_next_attack = time_next_attack - time_next_normal;% time until attacker finds the next block
            time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block
        end

    else % the next block is found by the attacker
        cnt_blocks.found_attack = cnt_blocks.found_attack + 1;
        Time.Delta = time_next_attack;
        Time.Total = Time.Total + Time.Delta;
        sa = sa + 1;% attacker does not publish the block (yet), so the number of secret blocks is incremented
        cha(ka+sa) = 2;
        time_next_normal = time_next_normal - time_next_attack;% time until normal (=honest) miners find the next block
        time_next_attack = -gen_time_attack*log(rand());% time until attacker finds the next block
    end
    if plot_flag, [hdn, hda] = plot_chain(chn(1:kn), cha(1:ka+sa), hdn, hda, Time, cnt_blocks, 'pause'); end % illustrate state of block chains
   
    % --- Check out if the attacker publishes his secret blocks:
    if sa >= THR_attack_publish || (sa >= 2 && ka+sa == kn+1),% 2nd condition means: normal (=honest) miners get too close, so publish before it is too late.
        blocks_won(ka+1:ka+sa) = 1;% These blocks are (re-)credited to the attacker now
        chn(ka+1:kn) = 1;% orphaned
        chn(kn+1:ka+sa) = -1;% not orphaned
        cha(ka+1:ka+sa) = chn(ka+1:ka+sa);
        cnt_event_orphaned = cnt_event_orphaned + 1;
        Nb_of_blocks_orphaned_by_attacker(cnt_event_orphaned) = kn-ka;
        cnt_blocks.orphaned_normal = cnt_blocks.orphaned_normal + (kn-ka);
        cnt_blocks.in_main_chain = cnt_blocks.in_main_chain + (ka+sa-kn);
        kn = ka+sa; % attacker's secretly mined blocks become published and accepted by the normal (=honest) miners
        ka = kn;% all blocks of the attacker are now in common with the normal chain.
        sa = 0;% attacker has no secret blocks any more now.
        time_next_attack = -gen_time_attack*log(rand());% time until attacker finds the next block
        time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block
        Time.Delta = 0;
        if plot_flag, [hdn, hda] = plot_chain(chn(1:kn), cha(1:ka+sa), hdn, hda, Time, cnt_blocks, 'pause'); end % illustrate state of block chains
    elseif sa >= 2 && kn-ka >= THR_orphanes_publish,% attacker publishes some blocks to avoid that even more orphans are created on the main chain
        blocks_won(ka+1:ka+THR_orphanes_publish+1) = 1;% These blocks are published and (re-)credited to the attacker now
        chn(ka+1:ka+THR_orphanes_publish) = 1;% selfishly mined blocks replacing honest blocks
        chn(ka+THR_orphanes_publish+1) = -1;% another selfishly mined block, but not causing orphanes on the main chain
        cha(ka+1:ka+THR_orphanes_publish+1) = chn(ka+1:ka+THR_orphanes_publish+1);
        cnt_event_orphaned = cnt_event_orphaned + 1;
        cnt_blocks.in_main_chain = cnt_blocks.in_main_chain + (ka+THR_orphanes_publish+1-kn);
        Nb_of_blocks_orphaned_by_attacker(cnt_event_orphaned) = THR_orphanes_publish;
        cnt_blocks.orphaned_normal = cnt_blocks.orphaned_normal + THR_orphanes_publish;
        kn = ka + THR_orphanes_publish + 1;% attacker's secretly mined blocks become published and accepted by the normal (=honest) miners
        ka = ka + THR_orphanes_publish + 1;% all blocks of the attacker are now in common with the normal chain.
        sa = sa - THR_orphanes_publish - 1;% attacker has no secret blocks any more now.
        time_next_normal = -gen_time_normal*log(rand());% time until normal (=honest) miners find the next block
        Time.Delta = 0;
        if plot_flag, [hdn, hda] = plot_chain(chn(1:kn), cha(1:ka+sa), hdn, hda, Time, cnt_blocks, 'pause'); end % illustrate state of block chains
    end

    % --- Termination condition(s) of the simulation:
    if kn > N && sa == 0,% terminate if enough blocks were simulated and the attacker has no more secret blocks
        break;
    end
   
    if ka+sa > N_force_terminate, % Force termination of the simulation. If attacker has more blocks than the normal (=honest) miners,
        % publish them now to get the blocks credited, and then terminate the simulation.
        if ka+sa > kn,
            blocks_won(ka+1:ka+sa) = 1;% These blocks are credited to the attacker
            chn(ka+1:kn) = 1;% orphaned
            chn(kn+1:ka+sa) = -1;% not orphaned
            cha(ka+1:ka+sa) = chn(ka+1:ka+sa);
            cnt_event_orphaned = cnt_event_orphaned + 1;
            Nb_of_blocks_orphaned_by_attacker(cnt_event_orphaned) = kn-ka;
            kn = ka+sa; % attacker's secretly mined blocks become published and accepted by the normal (=honest) miners
            Time.Delta = 0;
            if plot_flag, [hdn, hda] = plot_chain(chn(1:kn), cha(1:ka+sa), hdn, hda, Time, cnt_blocks); end % illustrate state of block chains
        end
        break;
    end
   
end% while 1

% Cut of the NaN entries from the results vector
blocks_won = blocks_won(1:kn);
Nb_of_blocks_orphaned_by_attacker = Nb_of_blocks_orphaned_by_attacker(1:cnt_event_orphaned);

%% 3 - Show results:
Number_of_blocks_simulated = kn %#ok
Percentage_mining_power_selfish_miner = power_attack*100 %#ok
Percentage_blocks_won_by_selfish_miner = sum(blocks_won)/length(blocks_won)*100 %#ok
Percentage_of_mainchain_blocks_orphaned_by_selfish_miner = sum(Nb_of_blocks_orphaned_by_attacker)/kn*100 %#ok

% Finally the histogram:
hfig=figure;
hist(Nb_of_blocks_orphaned_by_attacker,[1:max(2,max(Nb_of_blocks_orphaned_by_attacker))]); title('Lengths of Consecutive Blocks Orphaned on the Main Chain by the Selfish Miner'); xlabel('Event that this number of consecutive blocks were orphaned on the Main Chain'); ylabel('How often the rexpective event happened');
if ismatlab,% Octave does not understand the following formating
    set(0,'units','pixels');
    Pix_SS = get(0,'screensize');% info about the screen resolution in 'pixel'
    set(hfig, 'position', [0.25*Pix_SS(3), 1, 0.5*Pix_SS(3), 0.45*Pix_SS(4)]);% [x, y, width, height]
end


%% -----------------------------------------------------------------------------------------------------------
%% ---------------------------------------------- SUB-FUNCTION -----------------------------------------------
%% -----------------------------------------------------------------------------------------------------------

function [hdn, hda] = plot_chain(chn, cha, hdn, hda, Time, cnt_blocks, pause_flag)
% chn = the normal chain, row vector
% cha = the chain of the attacker
% The elements of the vector have the following meaning:
%       0 = block was mined by normal (=honest) miners
%     0.1 = block was mined by normal (=honest) miners and overruled a block from the selfish miner
%       1 = block was mined by attacker and caused an orphan of the normal (=honest) miners
%      -1 = block was mined by attacker and did not cause an orphan of the normal (=honest) miners
%       2 = (only in the attacker chain): secret block

global power_attack % selfish miner's hasing power share
global THR_orphanes_publish % max number of orpans that the selfish miner will create on the public main chain
global Pause_value % pause in seconds after each block, when plotting is active

ismatlab = false;
v=version;% typical Matlab version string: "7.5.0.338 (R2007b)"; typical Octave version string: "3.0.0"
if ~isempty(strfind(v,'R2')), % Matlab version string contains "R2" in it.
    ismatlab = true;
end

if nargin > 2,
    try
        delete(hdn.n);
    catch
        disp('ERROR with this software! (maybe you are using FreeMat?)');
        disp('Try running the function "selfish" with PlotFlag=false, or use Matlab or Octave for full plot support.');
        disp(' ');
        pause
        return;
    end
    delete(hdn.d);
    delete(hdn.o);
    delete(hdn.m);
   
    delete(hda.n);
    delete(hda.d);
    delete(hda.o);
    delete(hda.m);
    delete(hda.z);

    delete(hdn.ti);
    delete(hdn.dt);
   
    delete(hdn.t1);
    delete(hdn.t2);
    delete(hdn.t3);
    delete(hdn.t4);
    delete(hdn.t5);
    delete(hdn.t6);
    delete(hdn.t7);
    delete(hdn.t8);
   
    delete(hdn.t9);
    delete(hdn.t10);
    delete(hdn.t11);
   
else % initial call
    if ismatlab,% Octave does not understand the following formating
        hfig = figure;
        set(0,'units','pixels');
        Pix_SS = get(0,'screensize');% info about the screen resolution in 'pixel'
        set(hfig, 'position', [0, Pix_SS(4), Pix_SS(3), 0.3*Pix_SS(4)]);% [x, y, width, height]
    else
        disp(' ')
        disp('*** Please manually change the width of the figure that will now appear, ***')
        disp('*** to take the full screen width for best visual results!               ***')
        disp(' ')
        disp('--> Press any key to continue <--')
        pause
        hfig = figure;
    end
end

% Only display a window of 100 blocks:
len = max(length(chn), length(cha));
if len > 100,
    chn = chn(len-99:end);
    cha = cha(len-99:end);
end

chn_0 = chn; chn_0(chn_0==1)=999; chn_0(chn_0==-1)=999; chn_0(chn_0==0.1)=999;%  0: green
chn_d = chn; chn_d(chn_d==1)=999; chn_d(chn_d==-1)=999; chn_d(chn_d==0)=999;  %  0: green
chn_1 = chn; chn_1(chn_1==0)=999; chn_1(chn_1==-1)=999; chn_1(chn_1==0.1)=999;%  1: red
chn_m = chn; chn_m(chn_m==1)=999; chn_m(chn_m== 0)=999; chn_m(chn_m==0.1)=999;% -1: pink

cha_0 = cha; cha_0(cha_0==1)=999; cha_0(cha_0==-1)=999; cha_0(cha_0==2)=999; cha_0(cha_0==0.1)=999;%  0: green
cha_d = cha; cha_d(cha_d==1)=999; cha_d(cha_d==-1)=999; cha_d(cha_d==2)=999; cha_d(cha_d==0)=999;  %  0: green
cha_1 = cha; cha_1(cha_1==0)=999; cha_1(cha_1==-1)=999; cha_1(cha_1==2)=999; cha_1(cha_1==0.1)=999;%  1: red
cha_m = cha; cha_m(cha_m==1)=999; cha_m(cha_m== 0)=999; cha_m(cha_m==2)=999; cha_m(cha_m==0.1)=999;% -1: pink
cha_z = cha; cha_z(cha_z==0)=999; cha_z(cha_z==-1)=999; cha_z(cha_z==1)=999; cha_z(cha_z==0.1)=999;%  2: black

chn_0(chn_0==0) = 1;
chn_d(chn_d==0.1) = 1;
chn_m(chn_m==-1) = 1;

cha_0(cha_0==0) = 1;
cha_d(cha_d==0.1) = 1;
cha_m(cha_m==-1) = 1;
cha_z(cha_z==2) = 1;

if nargin > 2, % normal section
    if ismatlab,
        hdn.n = plot(2*chn_0,'gs', 'MarkerFaceColor','g'); hold on;
        hdn.d = plot(2*chn_d,'cs', 'MarkerFaceColor','c'); hold on;
        hdn.o = plot(2*chn_1,'rs', 'MarkerFaceColor','r'); hold on;
        hdn.m = plot(2*chn_m,'ms', 'MarkerFaceColor','m'); hold on;
       
        hda.n = plot(1*cha_0,'gs', 'MarkerFaceColor','g'); hold on;
        hda.d = plot(1*cha_d,'cs', 'MarkerFaceColor','c'); hold on;
        hda.o = plot(1*cha_1,'rs', 'MarkerFaceColor','r'); hold on;
        hda.m = plot(1*cha_m,'ms', 'MarkerFaceColor','m'); hold on;
        hda.z = plot(1*cha_z,'ks', 'MarkerFaceColor','k'); hold on;
    else
        hdn.n = plot(2*chn_0,'gs'); hold on;
        hdn.d = plot(2*chn_d,'cs'); hold on;
        hdn.o = plot(2*chn_1,'rs'); hold on;
        hdn.m = plot(2*chn_m,'ms'); hold on;
       
        hda.n = plot(1*cha_0,'gs'); hold on;
        hda.d = plot(1*cha_d,'cs'); hold on;
        hda.o = plot(1*cha_1,'rs'); hold on;
        hda.m = plot(1*cha_m,'ms'); hold on;
        hda.z = plot(1*cha_z,'ks'); hold on;
    end
    cnt_blk_tot = cnt_blocks.found_normal + cnt_blocks.found_attack;
    hdn.ti = text(50,2.55,['Time = ',num2str(Time.Total),' min (Total blocks calculated = ', ...
        num2str(cnt_blk_tot),' --> 1 block per ',num2str(Time.Total/cnt_blk_tot),' min)']);
    hdn.dt = text(50,2.35,['Delta = ',num2str(Time.Delta),' min (Blocks on Main Chain = ', ...
        num2str(cnt_blocks.in_main_chain),' --> 1 block per ',num2str(Time.Total/cnt_blocks.in_main_chain),' min)']);
   
    hdn.t1 = text(50,1.80, 'Blocks calculated by...');
    hdn.t2 = text(50,1.60, ['...honest miners: ', num2str(cnt_blocks.found_normal), ' (',num2str(cnt_blocks.found_normal/cnt_blk_tot*100),'%)']);
    hdn.t3 = text(50,1.40, ['...selfish miner: ', num2str(cnt_blocks.found_attack), ' (',num2str(cnt_blocks.found_attack/cnt_blk_tot*100),'%)']);
    hdn.t4 = text(50,1.20, ['...Total number:  ', num2str(cnt_blk_tot),' (100%)']);
   
    hdn.t5 = text(68,1.80, ['--> of which orphaned (i.e. mined in vain):']);
    hdn.t6 = text(68,1.60, ['--> ',num2str(cnt_blocks.orphaned_normal),' (',num2str(cnt_blocks.orphaned_normal/cnt_blocks.found_normal*100),'%)']);
    hdn.t7 = text(68,1.40, ['--> ',num2str(cnt_blocks.orphaned_attack),' (',num2str(cnt_blocks.orphaned_attack/cnt_blocks.found_attack*100),'%)']);
    hdn.t8 = text(68,1.20, ['--> ',num2str(cnt_blocks.orphaned_normal+cnt_blocks.orphaned_attack), ...
        ' (',num2str((cnt_blocks.orphaned_normal+cnt_blocks.orphaned_attack)/cnt_blk_tot*100),'%)']);

    hdn.t9  = text(50,0.67, ['Number of blocks that were found in current Main Chain by...']);
    tmp_cnt_hon = cnt_blocks.found_normal - cnt_blocks.orphaned_normal;
    tmp_cnt_sel = cnt_blocks.in_main_chain - tmp_cnt_hon;
    hdn.t10 = text(50,0.47, ['...honest miners:  ',num2str(tmp_cnt_hon),' (',num2str(tmp_cnt_hon/(tmp_cnt_hon+tmp_cnt_sel)*100),'%)']);
    hdn.t11 = text(50,0.27, ['...selfish miners: ',num2str(tmp_cnt_sel),' (',num2str(tmp_cnt_sel/(tmp_cnt_hon+tmp_cnt_sel)*100),'%)']);

   
else % initialization section
    if ismatlab,
        hdn.n = plot(2*chn_0,'ws', 'MarkerFaceColor','w'); hold on;
        hdn.d = plot(2*chn_d,'ws', 'MarkerFaceColor','w'); hold on;
        hdn.o = plot(2*chn_1,'ws', 'MarkerFaceColor','w'); hold on;
        hdn.m = plot(2*chn_m,'ws', 'MarkerFaceColor','w'); hold on;

        hda.n = plot(1*cha_0,'ws', 'MarkerFaceColor','w'); hold on;
        hda.d = plot(1*cha_d,'ws', 'MarkerFaceColor','w'); hold on;
        hda.o = plot(1*cha_1,'ws', 'MarkerFaceColor','w'); hold on;
        hda.m = plot(1*cha_m,'ws', 'MarkerFaceColor','w'); hold on;
        hda.z = plot(1*cha_z,'ws', 'MarkerFaceColor','w'); hold on;
    else
        hdn.n = plot(2,'ws'); hold on;
        hdn.d = plot(2,'ws'); hold on;
        hdn.o = plot(2,'ws'); hold on;
        hdn.m = plot(2,'ws'); hold on;

        hda.n = plot(1,'ws'); hold on;
        hda.d = plot(1,'ws'); hold on;
        hda.o = plot(1,'ws'); hold on;
        hda.m = plot(1,'ws'); hold on;
        hda.z = plot(1,'ws'); hold on;
    end
    hdn.ti = text(50,2.35,[' ']);
    hdn.dt = text(50,2.35,[' ']);
    hdn.t1 = text(50,2.35,[' ']);
    hdn.t2 = text(50,2.35,[' ']);
    hdn.t3 = text(50,2.35,[' ']);
    hdn.t4 = text(50,2.35,[' ']);
    hdn.t5 = text(50,2.35,[' ']);
    hdn.t6 = text(50,2.35,[' ']);
    hdn.t7 = text(50,2.35,[' ']);
    hdn.t8 = text(50,2.35,[' ']);
    hdn.t9 = text(50,2.35,[' ']);
    hdn.t10 = text(50,2.35,[' ']);
    hdn.t11 = text(50,2.35,[' ']);

    xlabel('block number');
    ylabel('attacker''s chain (bottom)    |    public chain (top)');
    title(['Selfish Miner''s Hashing Power = ',num2str(power_attack*100),'% of Total Network; Max. Length of Orphans Caused by Selfish Miner = ',num2str(THR_orphanes_publish),]);
    text(5,1.80, 'Blockchain that the honest miners are working on (public Main Chain)');
    text(5,1.13, 'Blockchain that the attacker (selfish miner) is working on (secret chain)');

    text(75,0.37, 'by Michael\_S at bitcointalk.org');
    text(75,0.17, '1MichaS16UMKFgNjanKrtfD51HpBkqPAwD');
   
    axis([1 100 0 3]);
   
    plot(5, 2.55, 'gs', 'MarkerFaceColor','g'); text(6,2.52,'Block mined by honest miner');
    plot(5, 2.35, 'cs', 'MarkerFaceColor','c'); text(6,2.32,'Block first mined by selfish miner, then replaced by honest miner');
    plot(5, 0.70, 'ms', 'MarkerFaceColor','m'); text(6,0.67,'Block mined by selfish miner (without replacement)');
    plot(5, 0.50, 'rs', 'MarkerFaceColor','r'); text(6,0.47,'Block first mined by honest miner, then replaced by selfish miner');
    plot(5, 0.30, 'ks', 'MarkerFaceColor','k'); text(6,0.27,'Block mined secretly by selfish miner, not yet published');

end

if nargin > 6,
    if Pause_value==inf,
        if ~ismatlab,
            disp('--> Press any key to see next block (focus must be on console when you press the key) <--')
        end
        pause;
    else
        pause(Pause_value);
    end
end
vip
Activity: 198
Merit: 101
December 11, 2013, 08:05:13 PM
#51
Quote
this.ptotal += p; // the probability of an event occuring increases
is still there.

What probability increases? The probability of finding a block is the same no matter how long you've been trying.

(I'm probably just misreading this, though. So my apologies in advance.)

You're looking at a pooled event object, all mining nodes are registered to the pool. When the event is emitted, the ptotal is used as a ceiling to randomly identify the node which has mined the block proportional to each's individual probability of mining the block during that msec. The ptotal is then used to find when the next block will be mined.

Code:
this.delay = Math.floor((Math.log(1-Math.random())/-1) * (1 / (this.ptotal)));

It's possible for two blocks to be mined at once, if the new delay is 0, then it will fire immediately after.

edit: ptotal is only changed when the probability of mining a block changes, like right at the beginning of the simulation or after a node adjusts difficulty.

edit2: the pooling of events into a single object is also a remnant of a previous version where adding events to a binary heap was expensive; now that I compute the delays in advance I can separate probabilistic tick events into their own objects. I can even create heap buckets to make insertion faster. Which I've just done.
vip
Activity: 198
Merit: 101
December 11, 2013, 07:14:05 PM
#50
That's residual code from how I used to handle discrete time events in an older version. I just removed it so thank you for reminding me.

And yes, selfish attack at 35% requires over 50 days to be profitable, assuming the network hashrate stays the same. And assuming the block reward is the only thing that matters, which is true for now.
vip
Activity: 198
Merit: 101
December 11, 2013, 05:44:17 PM
#49
I think there's something wrong. Difficulty doesn't change for 2016 blocks, so attackers shouldn't be seeing more revenue per hour in less than 2016 blocks. (Attackers can't do more hashes per second, so they shouldn't have an increased number of blocks per hour at least until difficulty changes.)

But I don't have time to investigate this right now. Maybe next week.

In the 40% results, for example:

normal/sybil:
sim45-18067092:(h=2016) difficulty adjustment 1.0116679056880324x
sim45-2210925:(h=2016) difficulty adjustment 1.0411968218665215x
sim45-23586774:(h=2016) difficulty adjustment 0.9990748637793512x
sim45-26354243:(h=2016) difficulty adjustment 0.9823499433113184x
sim45-64896747:(h=2016) difficulty adjustment 0.984449367266411x
sim45-87844436:(h=2016) difficulty adjustment 1.0116418448848656x

attack/attack+sybil:
sim45-21082244:(h=2016) difficulty adjustment 0.623596869023641x   ( 539.54 h)
sim45-22962843:(h=2016) difficulty adjustment 0.6104684972955473x ( 549.30 h)
sim45-46100699:(h=2016) difficulty adjustment 0.6466402958243354x ( 517.50 h)
sim45-63334992:(h=2016) difficulty adjustment 0.6079748180529679x ( 552.14 h)
sim45-74353382:(h=2016) difficulty adjustment 0.5940874807871993x ( 565.13 h)
sim45-82186196:(h=2016) difficulty adjustment 0.6131612492096951x ( 547.88 h)

The difficulty adjustment is allowing the attacker to take the lead quicker.

kjj
legendary
Activity: 1302
Merit: 1026
December 11, 2013, 12:01:51 PM
#48
There would be an unusual number of orphans,  But it would be hard to see because we don't relay orphans, so no single node would necessarily see enough of them to notice.
hero member
Activity: 709
Merit: 503
December 11, 2013, 11:36:37 AM
#47
So, how would we detect such attacks?  What should our response be?  Or are we thinking we're ok as is?  Maybe the default behavior could be configured to be selfish and that way a selfish attack wouldn't be able to gain.  Hmm, then the non-selfish algorithm would look like an attack.  Ah, the mining software should detect the current situation and adjust the algorithm to selfish or non-selfish to maximize earnings.

Or, have I completely missed the point and need to pay closer attention?
vip
Activity: 198
Merit: 101
December 10, 2013, 11:48:05 PM
#46
$66.12 to run the simulation above, 6 hours with 19 servers. (simulating up to 10000 blocks with 1000 nodes each for every percentage of hashrate three times is an unusually demanding task so far) But if you use spot instances, and carefully pick the availability zones/regions, you could probably at least halve that cost.
kjj
legendary
Activity: 1302
Merit: 1026
December 10, 2013, 11:40:26 PM
#45
How much does Amazon charge?  Like how much did it cost you to make those graphs, as an example data point.
vip
Activity: 198
Merit: 101
December 10, 2013, 11:33:29 PM
#44
Excellent.  A decent launcher is a critical piece for doing useful (aka large scale) simulations.  Do you have any experience with other launchers for big clusters?  As in, can you set it up so that an academic researcher with access to an existing supercomputer array could launch your simulator on their equipment?

I created a launcher here: https://github.com/ebfull/ebfull.github.io/blob/master/hub.js

It just uses SSH to provision servers and dispatch tasks, and you can define the concurrency for each server. I have an instance-backed AMI set up on my AWS account which Node/NPM installed for quickly deploying slave servers. I think a similar architecture could be used for many academic compute environments, but I have no experience with them.

But to answer your question, yes I will be making it much more useful for large-scale simulations for researchers. I think it's great that the codebase can be flexible enough for both browser simulations (testing/sharing/prototyping/visualizing) and large-scale analysis, I won't neglect either. It's still under development though.
kjj
legendary
Activity: 1302
Merit: 1026
December 10, 2013, 11:06:04 PM
#43
I'm currently generating the graphs by running the simulation on an ec2 cluster, all of the scripts I'm using to render them are on my github repo. It's still a bit shabby.

Excellent.  A decent launcher is a critical piece for doing useful (aka large scale) simulations.  Do you have any experience with other launchers for big clusters?  As in, can you set it up so that an academic researcher with access to an existing supercomputer array could launch your simulator on their equipment?
vip
Activity: 198
Merit: 101
December 10, 2013, 07:02:24 PM
#42
I decided to run a comprehensive simulation with my framework. I simulated every strategy three times, at every percentage of hashrate between 0 and 49 inclusive. Each simulation evaluated 10000 blocks, with 1000 nodes. Each node had between 8 and 37 connections with other peers, forming an interesting and realistic network topology. The difficulty adjustment targetted 10 minute block times like bitcoin.

The result after ~10000 blocks:



I've plotted the revenue over time of each strategy at various network hashrate percentages:

30%:

35%:

40%:

45%:


Very interesting to see the time/revenue investment necessary to profit from the attack.

How did you make those graphs, anyway? I have a bunch more questions (I'd like to see if, as I suspect, the supposed "fix" actually makes things worse), but I don't want to put the burden on you to keep running all my hypotheticals.

I'm currently generating the graphs by running the simulation on an ec2 cluster, all of the scripts I'm using to render them are on my github repo. It's still a bit shabby.

Ask your hypotheticals, I'd love to take a look at some/all of them. I'd rather make it easier for others to prototype their own ideas and so I'll be pursuing that.
vip
Activity: 198
Merit: 101
December 08, 2013, 09:56:32 PM
#41
Here's your graph!



I'll work on the revenue time graph tomorrow. Any percentages of hashrate you'd like to see plotted over time?
vip
Activity: 198
Merit: 101
December 08, 2013, 03:29:19 PM
#40
Percentage of revenue is irrelevant. BTC per hour is the important number.

Would you mind explaining why the distinction is so critical? Those two numbers are trivially mathematically related. Never mind, I know why you're asking this. I'll start plotting this instead.
vip
Activity: 198
Merit: 101
December 08, 2013, 01:49:28 PM
#39
Update:

I have now published a much better version of the simulator at the original URL.

http://ebfull.github.io/

This simulator performs much better than before, but is also much more accurate. (Still runs best on Chrome.)

Here's just a few of the changes:
  • discrete probabilistic events (mining) now more accurately model Poisson distribution
  • inter-node latency more accurate
  • full blown inventory system, modeled by a network-wide state machine for efficiency
  • peer manager more accurately models TCP (especially the sequence of messages)
  • new modular "middleware" architecture of the simulator
  • events use the closure library's priority queue
  • difficulty adjustment added
  • blockchain branches are compared by work not just height
  • much more memory efficient

The page now just runs several trials of every network percent between 10% and 49%, for every combination of sybil attack and selfish mining attack toggle. 200 nodes are simulated for ~5000 blocks each trial.

I left this running and had the following results:





Disclaimer: This simulation does not accurately reflect the bitcoin network.
  • The topology of the simulation, as well as inter-node latency, is dissimilar from the real bitcoin network although I've made it more accurate. Does anyone know what the average latency between nodes should be? How much variance? Packet loss characteristics?
  • Block validation is assumed to be instantaneous because no transactions are occurring. (Yet!)
  • There are only 200 nodes being simulated. Hopefully in the future the simulation can support thousands of nodes.
  • Nodes just grab whatever peers they can get and don't optimize for latency.



More details:

Is it done? No.

I'll finish it and publish it as an independent project with better documentation soon.

Is this simulator general enough? Yes!

You can cook up any type of p2p simulation with this. It took me a few minutes to build a p2p (trustful) time syncing protocol simulation. (Demo here.) The code is pretty fun and easy to work with.

TODO:

  • Is my implementation of the selfish mining attack correct? See miner.js's .attack()
  • (de)registering events in NodeProbablisticTickEvent needs to update delay retroactively
  • Thoroughly test UTXO system.
  • Integrate mempool with blockchain.
  • mapOrphans (transactions and blocks)
  • getheaders, relay set
  • Document and release as standalone project
  • Use WebWorkers for something, anything.
  • Play with node.js, maybe throw this on EC2 and see what I can do.
vip
Activity: 198
Merit: 101
December 06, 2013, 06:55:11 PM
#38
Well, no, I wouldn't expect that. Yes, the hashrate does not change, but because a large portion of the hashrate is wasted on orphaned blocks, the difficulty should go down.

Sorry, I was speaking of the simulator in general, not the attack.

You will not see an effect from the difficulty adjustments in the current simulator, because the attacker will never retain a large enough lead coinciding during a difficulty adjustment for it to matter. If you want to see the effects, change target_avg_between_blocks from 2.5 minutes (litecoin) to something like 10 seconds, so the attacker will have an extremely large lead on the network. I haven't investigated the effects of the difficulty adjustment yet, but it could be interesting.
vip
Activity: 198
Merit: 101
December 06, 2013, 03:58:35 PM
#37
You say "25% chance of mining a block = 25% hashrate". 25% chance of mining a block over what time period? If you have a 25% chance of mining a block every 10 minutes, and this doesn't change, then your revenue doesn't change. There's no need for a simulator to measure that. So obviously there must be something more going on. As I understand it, what goes on is that the difficulty decreases over time (because everyone is forced to waste time mining orphans), and therefore the chance of mining a block every 10 minutes increases. Obviously this is going to take many blocks to happen, though. For the first 2016 blocks, the non-orphaned blocks per minute found by everyone, including the attacker, will decrease. For the next 2016 blocks... I don't know for sure. That's why I'm interested in seeing the simulator. On the one hand, the attacker will be wasting time on orphans. On the other hand, the difficulty has decreased.

When I say "25% chance of mining a block" I speak in terms of every 100msec. The difficulty dilutes this probability on a per-node basis. At a difficulty of 1000, a node with 31% chance of mining a block will have 0.00031 chance of mining a block each 100msec.

Let me make clear that the average time between blocks is an emergent phenomena in the simulation. Often, just as in the real network, blocks are solved within moments of each other even though (on average) they occur every ten minutes if the difficulty adjustments are allowed to take their course. You can witness the difficulty adjustments in the javascript console, but that page will be slow at reaching 2016-multiple heights because it is also simulating a UTXO/polling/propagation system for other purposes.

Code:
(height = 2016) Difficulty adjustment: from 1000 to 1441.9452528101006 (1.4419452528101004x)

Here's the way the simulator currently handles mining: when a node calls its own .mine() method with an argument of network percentage, that network percentage is allocated to the node. What remains in the network can be claimed by other miners, or nodes could simply call .mine(true) and receive an evenly distributed portion of the unallocated hashrate. Here's how you can simulate bitcoin-like mining pools:

Code:
btc.init(function(self) {
switch(self.id) {
case 0:
self.mine(0.31) // btcguild
break;
case 1:
self.mine(0.22)
break;
case 2:
self.mine(0.13)
break;
case 3:
self.mine(0.06)
break;
case 4:
self.mine(0.05)
break;
case 5:
self.mine(0.03)
break;
case 6:
self.mine(0.02)
break;
case 7:
self.mine(0.02)
break;
default:
if (self.id < 100)
self.mine(true);
else
self.mine(false);
break;
}
});

The above code results in the following (default difficulty is 1000):



pnothing is the probability of nothing happening each time the event fires (currently 100msec), mprob is the node's claimed hashrate.

An emergent phenomena of the simulation is that (because the hashrate does not change) the difficulty will settle at a certain point as you'd expect.

To put it another way, one thing I'd really like to know is how long it takes for the attacker to break even, let alone gain from this attack. I don't see anything like that in this simulator.

As I say above, another consideration is that the network is actually dynamic, and not static, but if we can start with something simple like "how long does it take to break even if everything stays static", I think that can give us a better feel for how much the dynamic nature of reality is going to matter. It also gives us an idea of how long we as a community have to respond and try to punish anyone performing this attack. If it's only 2016 blocks or so, okay, that's one thing to deal with. If it's 20,160 blocks, then it's going to be much harder to successfully pull this off in the real world.

Currently it is more useful to approach the simulator as such: run it normally, witness an accurate revenue relative to hashrate, run it with the attack, witness the revenue over time larger than normal.

I hope to have a more accurate answer to your questions (so that the actual thresholds of the attack can be witnessed and graphed) soon.
vip
Activity: 198
Merit: 101
December 06, 2013, 03:11:38 AM
#36
Any chance we can get a readout on hashes per second and difficulty? The probability of solving a hash during any particular second changes over time as the difficulty changes.

Note: It would be pointless to simulate actual hash functions or authentication. The simulator instead simulates probabilistic events over time (say 25% chance of mining a block = 25% hashrate). As you'd expect, two nodes may solve two different blocks at the exact microsecond, or no block may appear for quite a while.

I have indeed added difficulty adjustments (to http://ebfull.github.io/test.html) and those adjustments do affect the probability of a node (which has adopted the new difficulty) solving a block. It shows their network percentage there as well.
Pages:
Jump to: