Bitcoin Forum
November 07, 2024, 07:53:07 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 2 [3]  All
  Print  
Author Topic: Selfish Mining Simulation  (Read 14059 times)
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 09, 2013, 02:56:32 AM
 #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?

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 11, 2013, 12:02:24 AM
 #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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1026



View Profile
December 11, 2013, 04:06:04 AM
 #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?

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 11, 2013, 04:33:29 AM
 #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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1026



View Profile
December 11, 2013, 04:40:26 AM
 #45

How much does Amazon charge?  Like how much did it cost you to make those graphs, as an example data point.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 11, 2013, 04:48:05 AM
 #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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
David Rabahy
Hero Member
*****
Offline Offline

Activity: 709
Merit: 503



View Profile
December 11, 2013, 04:36:37 PM
 #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?
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1026



View Profile
December 11, 2013, 05: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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 11, 2013, 10: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.


"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 12, 2013, 12:14:05 AM
 #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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
eb3full (OP)
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
December 12, 2013, 01:05:13 AM
Last edit: December 12, 2013, 04:32:32 PM by eb3full
 #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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
Michael_S
Sr. Member
****
Offline Offline

Activity: 278
Merit: 251


Bitcoin-Note-and-Voucher-Printing-Empowerer


View Profile
May 31, 2014, 03:05:40 PM
 #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 <press Enter>
%
% 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<NOPTS>
Percentage_mining_power_selfish_miner = power_attack*100 %#ok<NOPTS>
Percentage_blocks_won_by_selfish_miner = sum(blocks_won)/length(blocks_won)*100 %#ok<NOPTS>
Percentage_of_mainchain_blocks_orphaned_by_selfish_miner = sum(Nb_of_blocks_orphaned_by_attacker)/kn*100 %#ok<NOPTS>

% 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

Skycraft
Newbie
*
Offline Offline

Activity: 28
Merit: 0


View Profile
June 06, 2014, 01:05:12 AM
 #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
green king
Newbie
*
Offline Offline

Activity: 28
Merit: 0


View Profile
September 14, 2014, 07: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...
iron man
Newbie
*
Offline Offline

Activity: 28
Merit: 0


View Profile
September 17, 2014, 08: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?
Pages: « 1 2 [3]  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!