Можна обчислювати биткоины швидше, простіше чи легше?


Все почалося з того, що я вирішив ближче познайомитися з биткоинами. Хотілося зрозуміти, як їх видобувають. Статті про биткоины і блокчейны останнім часом зустрічаються часто, але таких, щоб з усіма технічними подробицями, таких не дуже багато.

Найпростіший спосіб розібратися у всіх деталях — вивчити відкриті вихідні коди. Я взявся вивчати Verilog код FPGA майнера: https://github.com/progranism/Open-Source-FPGA-Bitcoin-Miner.git. Це не єдиний такий проект, є ще кілька прикладів на github, і всі вони, хоч і різних авторів, схоже працюють приблизно за однією схемою. Цілком можливо, що автор то у них усіх спочатку був один, просто різні розробники адаптують один і той же код під різні чіпи і різні плати… принаймні мені так здалося…

Ось і я, повивчавши исходники Verilog, адаптував проект з github до плати Марсоход3 на основі ПЛІС Altera MAX 10, 50 тис. логічних елементів. Я зміг запустити свій майнер і навіть зміг запустити процес обчислення биткоинов, але кинув цю справу через пів години через безперспективність. Занадто повільно по теперішній час працює мій FPGA майнер. Ну і нехай.

Чесно кажучи, мене в усьому цьому проекті зацікавили не самі биткоины (ну їх, ці грошові сурогати ))), але швидше математична сторона алгоритму SHA256. Ось про це я і хотів би поговорити. Я провів декілька експериментів з алгоритмом SHA256, може бути результати цих експериментів здадуться вам цікавими.

Перше, що мені потрібно було зробити для моїх експериментів — це написати «чисту» реалізацію SHA256 на Verilog.

Насправді реалізацій алгоритму SHA256 в Verilog багато, хоч на тому ж opencores.org, хоч на github.com. Однак, мені такі не підходять для експериментів. Наявні модулі завжди мають конвеєрну структуру, pipeline. Здавалося б — це правильно. Тільки при наявності pipeline можна отримати високу швидкість роботи алгоритму. Алгоритм SHA256 складається з 64 етапів обробки, так званих «раундів». Якщо обсяг ПЛІС дозволяє, то можна розгорнути всі 64 раунду в єдиний ланцюжок операцій: всі етапи обчислення проводяться паралельно за один такт робочої частоти. Приблизно ось так:

На вході алгоритму вісім 32-х бітних слів стану машини SHA256. Це регістри A, B, C, D, E, F, G, H. Самі вхідні дані, 512 біт, преобразутся в коефіцієнти W, які домішуються на кожному раунді. Поки в регістри першого раунду завантажуються нові слова дані, другий раунд продовжує вважати дані завантажені на попередньому такті, третій раунд продовжує вважати, те, що було завантажено на перед-попередньому такті і так далі. Підсумкова latency, тобто затримка результату обчислень як раз і буде 64 такти, але в цілому конвеєр/pipeline дозволяє вважати весь алгоритм за 1 такт. Якщо обсяг ПЛІС малий і не дозволяє розгорнути всю ланцюжок раундів, то її вкорочують вдвічі. Так виходить вмістити проект в яку ПЛІС, але і швидкість обчислень природно падає вдвічі. Можна взяти ще менш ємну ПЛІС і вмістити туди, але доведеться ще укоротити pipeline і знову постраждає продуктивність. Як я зрозумів, на весь Bitcoin майнер, в якому два поспіль SHA256-transform потрібно близько 80-ти тисяч логічних елементів в ПЛІС Altera/Intel. Але це я відволікся…

Отже, я хочу зробити абсолютно абсурдну річ — написати на Verilog «чисту» функцію алгоритму SHA256 без проміжних регістрів, залишити її без конвеєра. Мета у цього дивного дії проста — визначити реальну кількість логіки, необхідну для обчислення алгоритму SHA256. Мені потрібна проста комбинацинная схема, яку подаєш на вхід 512 біт даних (ну і 256 біт вихідного стану) і вона видає 256 біт результату.

Я написав цей Verilog модуль, де-то что-то сам писав, щось запозичив з інших відкритих джерел. Мій проект «sha256-test».
Ось чистий комбінаційна SHA256, жодного проміжного регістру
module e0 (x, y);
input [31:0] x;
output [31:0] y;
assign y = {x[1:0],x[31:2]} ^ {x[12:0],x[31:13]} ^ {x[21:0],x[31:22]};
endmodule

module e1 (x, y);
input [31:0] x;
output [31:0] y;
assign y = {x[5:0],x[31:6]} ^ {x[10:0],x[31:11]} ^ {x[24:0],x[31:25]};
endmodule

module ch (x, y, z, o);
input [31:0] x, y, z;
output [31:0] o;
assign o = z ^ (x & (y ^ z));
endmodule

module maj (x, y, z, o);
input [31:0] x, y, z;
output [31:0] o;
assign o = (x & y) | (z & (x | y));
endmodule

module s0 (x, y);
input [31:0] x;
output [31:0] y;
assign y[31:29] = x[6:4] ^ x[17:15];
assign y[28:0] = {x[3:0], x[31:7]} ^ {x[14:0],x[31:18]} ^ x[31:3];
endmodule

module s1 (x, y);
input [31:0] x;
output [31:0] y;
assign y[31:22] = x[16:7] ^ x[18:9];
assign y[21:0] = {x[6:0],x[31:17]} ^ {x[8:0],x[31:19]} ^ x[31:10];
endmodule

module round (idx, in, k, w, out);
input [7:0]idx;
input [255:0]in;
input [ 31:0]k;
input [ 31:0]w;
output [255:0]out;

завжди @(w)
$display("i=%d k=%8x w=%8x",idx,k,w);

wire [31:0]a; assign a = in[ 31: 0];
wire [31:0]b; assign b = in[ 63: 32];
wire [31:0]c; assign c = in[ 95: 64];
wire [31:0]d; assign d = in[127: 96];
wire [31:0]e; assign e = in[159:128];
wire [31:0]f; assign f = in[191:160];
wire [31:0]g; assign g = in[223:192];
wire [31:0]h; assign h = in[255:224];

wire [31:0]e0_w; e0 e0_(a,e0_w);
wire [31:0]e1_w; e1 e1_(e,e1_w);
wire [31:0]ch_w; ch ch_(e,f,g,ch_w);
wire [31:0]mj_w; maj maj_(a,b,c,mj_w);

wire [31:0]t1; assign t1 = h+w+k+ch_w+e1_w;
wire [31:0]t2; assign t2 = mj_w+e0_w;
wire [31:0]a_; assign a_ = t1+t2;
wire [31:0]d_; assign d_ = d+t1;
assign out = { g,f,e,d_,c,b,a,a_ };
endmodule

module sha256_transform(
input wire [255:0]state_in,
input wire [511:0]data_in,
output wire [255:0]state_out
);
localparam Ks = {
32'h428a2f98, 32'h71374491, 32'hb5c0fbcf, 32'he9b5dba5,
32'h3956c25b, 32'h59f111f1, 32'h923f82a4, 32'hab1c5ed5,
32'hd807aa98, 32'h12835b01, 32'h243185be, 32'h550c7dc3,
32'h72be5d74, 32'h80deb1fe, 32'h9bdc06a7, 32'hc19bf174,
32'he49b69c1, 32'hefbe4786, 32'h0fc19dc6, 32'h240ca1cc,
32'h2de92c6f, 32'h4a7484aa, 32'h5cb0a9dc, 32'h76f988da,
32'h983e5152, 32'ha831c66d, 32'hb00327c8, 32'hbf597fc7,
32'hc6e00bf3, 32'hd5a79147, 32'h06ca6351, 32'h14292967,
32'h27b70a85, 32'h2e1b2138, 32'h4d2c6dfc, 32'h53380d13,
32'h650a7354, 32'h766a0abb, 32'h81c2c92e, 32'h92722c85,
32'ha2bfe8a1, 32'ha81a664b, 32'hc24b8b70, 32'hc76c51a3,
32'hd192e819, 32'hd6990624, 32'hf40e3585, 32'h106aa070,
32'h19a4c116, 32'h1e376c08, 32'h2748774c, 32'h34b0bcb5,
32'h391c0cb3, 32'h4ed8aa4a, 32'h5b9cca4f, 32'h682e6ff3,
32'h748f82ee, 32'h78a5636f, 32'h84c87814, 32'h8cc70208,
32'h90befffa, 32'ha4506ceb, 32'hbef9a3f7, 32'hc67178f2};

genvar i;
generate
for(i=0; i<64; i=i+1)
begin : RND
wire [255:0] state;
wire [31:0]W;

if(i<16)
begin
assign W = data_in[i*32+31:i*32];
end
else
begin
wire [31:0]s0_w; s0 so_(RND[i-15].W,s0_w);
wire [31:0]s1_w; s1 s1_(RND[i-2].W,s1_w);
assign W = s1_w + RND[i - 7].W + s0_w + RND[i - 16].W;
end

if(i == 0)
round R (
.idx(i[7:0]),
.in(state_in),
.k( Ks[32*(63-i)+31:32*(63-i)] ),
.w(W),
.out(state) );
else
round R (
.idx(i[7:0]),
.in(RND[i-1].state),
.k( Ks[32*(63-i)+31:32*(63-i)] ),
.w(W),
.out(state) );
end
endgenerate

wire [31:0]a; assign a = state_in[ 31: 0];
wire [31:0]b; assign b = state_in[ 63: 32];
wire [31:0]c; assign c = state_in[ 95: 64];
wire [31:0]d; assign d = state_in[127: 96];
wire [31:0]e; assign e = state_in[159:128];
wire [31:0]f; assign f = state_in[191:160];
wire [31:0]g; assign g = state_in[223:192];
wire [31:0]h; assign h = state_in[255:224];

wire [31:0]a1; assign a1 = RND[63].state[ 31: 0];
wire [31:0]b1; assign b1 = RND[63].state[ 63: 32];
wire [31:0]c1; assign c1 = RND[63].state[ 95: 64];
wire [31:0]d1; assign d1 = RND[63].state[127: 96];
wire [31:0]e1; assign e1 = RND[63].state[159:128];
wire [31:0]f1; assign f1 = RND[63].state[191:160];
wire [31:0]g1; assign g1 = RND[63].state[223:192];
wire [31:0]h1; assign h1 = RND[63].state[255:224]; 

wire [31:0]a2; assign a2 = a+a1;
wire [31:0]b2; assign b2 = b+b1;
wire [31:0]c2; assign c2 = c+c1;
wire [31:0]d2; assign d2 = d+d1;
wire [31:0]e2; assign e2 = e+e1;
wire [31:0]f2; assign f2 = f+f1;
wire [31:0]g2; assign g2 = g+g1;
wire [31:0]h2; assign h2 = h+h1;

assign state_out = {h2,g2,f2,e2,b2,c2,b2,a2};
endmodule

Природно, потрібно переконатися, що модуль працює. Для цього потрібен простий тестбенч, щоб подати на вхід якийсь блок даних і подивитися результат.
Ось testbench Verilog
`timescale 1ns/1ps

module tb;

initial
begin
$dumpfile("tb.vcd");
$dumpvars(0, tb);
#100;
$finish;
end

wire [511:0]data;

assign data = 512'h66656463626139383736353433323130666564636261393837363534333231306665646362613938373635343332313066656463626139383736353433323130;

wire [255:0]result;
sha256_transform s(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in(data),
.state_out(result)
);
endmodule

Порівнювати буду з відповіддю, який мені видає функція sha256_transform, написана на мові C (можна я не буду приводити код на C? цих реалізацій на C/C++ повним повно). Головне результат:

Програмують на C/C++ в середовищі Visual Studio, а Verilog програму тестую з допомогою icarus verilog і gtkwave. Переконався, що відповіді збігаються, значить можна рухатися далі.

Тепер можна вставити модуль в ПЛІС і подивитися скільки ж логічних елементів може займати така функція.
Робимо такий проект для ПЛІС:
module sha256_test(
input wire clk,
input wire data,
output wire [255:0]result
);

reg [511:0]d;
завжди @(posedge clk)
d <= { d[510:0],data };

sha256_transform s0(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in( d ),
.state_out(result)
);
endmodule

Тут передбачається, що вхідні дані ховаються в один довгий регістр 512 біт, який подається в якості вхідних даних на мою «чисту» SHA256_transform. Всі 256 вихідних біт виводяться назовні мікросхеми на вивідні піни ПЛІС.

Компилирую, для FPGA Cyclone IV і бачу, що ця штука займе 30,103 логічних елементів.
Добре запам'ятаємо це число: 30103

Зробимо другий експеримент.
Проект «sha256-eliminated».
module sha256_test(
input wire clk,
input wire data,
output wire [255:0]result
);

sha256_transform s0(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in( 512'h66656463626139383736353433323130666564636261393837363534333231306665646362613938373635343332313066656463626139383736353433323130 ),
.state_out(result)
);

endmodule

Тут вхідні дані я не подаю у ПЛІС ззовні, а просто ставлю константою, постійним вхідним сигналом для модуля sha256_transform.

Компілюємо в ПЛІС. Знаєте скільки буде задіяно логічних елементів в цьому випадку: НУЛЬ.

Середа Altera (або вже Intel? як правильно називати?) Quartus Prime оптимізує всю логіку пристрою і оскільки немає ніяких регістрів і немає вхідних сигналів, від яких залежав результат, то вся комбінаційна функція вироджується, з вхідних параметрів модуля SHA256 обчислюється відповідь прямо під час компіляції. Ви можете подивитися вихідні сигнали на пинах ПЛІС. Компілятор відразу пише, що деякі сигнали будуть навішені на землю, а деякі до VCC, до напруги живлення. Так на виходах з'явиться обчислений самим компілятором результат: 0x56, 0x70,… точно як у моєму першому тестовому прикладі.

Звідси виникає така думка. Раз компілятор такий розумний і може настільки добре оптимізувати логіку, то чому би не вважати лише один вихідний біт від sha256? Скільки логіки потрібно, щоб порахувати тільки один результуючий біт?

У самому справі. Биткоины вважаються так: є блок даних. У блоці даних є змінне поле, яке можна змінювати — це поле nonce, 32 біта. Решта дані в блоці зафіксовані. Ми повинні міняти, перебирати поле " nonce таким чином, щоб результат sha256 вийшов «спеціальним», а саме, щоб старші біти результату sha256-transform опинилися в нулі.

Ось вважаємо sha256 один раз, потім збільшуємо nonce на одиницю, знову вважаємо хеш, потім знову і знову. Сотні, тисячі разів один і той же блок даних, але трохи інше поле nonce. При цьому обчислюються всі біти результату sha256, тобто всі вихідні 256 біт. А вигідно це енергетично? Вигідно це по кількості задіяних логічних елементів?

А якщо порахувати лише один із старших біт результату. Він думаю рівноймовірно буде або нуль або одиниця. Якщо він виявиться одиницею, так інші біти і рахувати не потрібно. Навіщо на них витрачати дорогоцінну енергію?

Зробивши це припущення, я для себе чомусь відразу вирішив, що число логічних елементів для обчислення тільки одного біта хеша повинно бути в 256 разів менше, ніж для обчислення всіх біт результату. Але я помилявся.

Щоб перевірити цю гіпотезу я вирішив зробити проект для квартуса з топ модулем, який виглядає ось так:
module sha256_test(
input wire clk,
input wire data,
output wire result
);

reg [511:0]d;
завжди @(posedge clk)
d <= { d[510:0],data };

wire [255:0]r;
sha256_transform s0(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in( d ),
.state_out®
);

assign result = r[187]; //номер біт, який нас цікавить
endmodule

Зверніть увагу, що начебто sta256_transform буде обчислювати весь хеш і відповідь буде в сигналі wire [255:0]r, однак, вихід модуля Verilog — це тільки один біт, який assign result = r[187]; Це дозволить компілятору ефективно залишити тільки ту логіку, яка потрібна для обчислення потрібного біта. Решта буде оптимізовано і вилучено з проекту.

Щоб провести мій експеримент мені потрібно всього навсього виправляти передостанню сходинку і перекомпілювати проект 256 разів. Щоб полегшити таку роботу напишу скрипт для квартуса:
#!/usr/bin/tclsh

proc read_rpt { i frpt } {
set fp [open "output_files/xxx.map.summary" r]
set file_data [read $fp]
close $fp
set data [split $file_data "\n"]
foreach line $data {
set half [split $line ":"]
set a [lindex $half 0]
set b [lindex $half 1]
if { $a == " Total combinational functions " } {
puts [format "%d %s" $i $b]
puts $frpt [format "%d %s" $i $b]
}
}
}

proc gen_sha256_src { i } {
set fo [open "sha256_test.v" "w"] 
puts $f "module sha256_test("
puts $f " input wire clk,"
puts $f " input wire data,"
puts $f " output wire result"
puts $f ");"
puts $f ""
puts $f "reg \[511:0]d;"
puts $f "завжди @(posedge clk)"
puts $f " d <= { d\[510:0],data };"
puts $f ""
puts $f "wire \[255:0]r;"
puts $f "sha256_transform s0("
puts $f " .state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),"
puts $f " .data_in( d ),"
puts $f " .state_out®"
puts $f " );"
puts $f ""
puts $f "assign result = r\[$i];"
puts $f ""
puts $f "endmodule"
close $fo
}

set frpt [open "rpt.txt" "w"] 
for {set i 0} {$i < 256} {incr i} {
gen_sha256_src $i
exec x.bat
read_rpt $i $frpt
}
close $frpt
exit

Цей скрипт в циклі заново створює модуль sha256_test.v і кожен раз виводить на вихідний пін ПЛІС черговий біт результату sha256.

Запускаю скрипт на пару годин і вуаля. Є таблиця значень. Тепер ми точно знаємо, який біт з SHA256 найпростіше обчислити. Ось графік залежності необхідної кількості логічних елементів від порядкового номера обчислюваного біта SHA256:

Звідси стає ясно, що простіше всього обчислити біт номер 224. Для нього потрібно 27204 логічних елемента. Це взагалі-то майже на 10% менше, ніж при обчисленні всіх 256 вихідних біт.

Графік у вигляді пилки пояснюється тим, що в алгоритмі SHA256 багато суматорів. У суматорі кожен наступний старший біт обчислити важче, ніж попередній молодший. Це через схеми переносу, адже суматори складаються з багатьох блоків full-adder.

Ось вже здалася примарна економія енергії. Я вважаю, що кожна логічна функція їсть енергію. Чим менше число задіяних логічних елементів LE у проекті ПЛІС, тим менше споживання енергії. Передбачуваний алгоритм такий: вважаємо один найпростіший біт, якщо він нуль, то вважаємо наступний. Якщо він одиниця, то не витрачаємо енергію і сили і час на інші біти в цьому ж хэше.

Тепер інша думка, так само пов'язана з можливостями компілятора оптимізувати логіку.

Оскільки при переборі поля nonce основні дані блоку залишаються однаковими, то, логічно і очевидно, що від циклу до циклу деякі обчислення просто повторюються і вважають одне і те ж. Питання: як оцінити скільки там втрачається енергії на повторних обчисленнях?

Експеримент простий. Поставимо, наприклад, два модуля sha256_transform поруч і подамо на них однакові вхідні дані, ну за винятком одного біта. Вважаємо, що ці два модуля вважають сусідні nonce відрізняються одним бітом.
module sha256_test(
input wire clk,
input wire data,
output wire [1:0]result
);

reg [511:0]d;
завжди @(posedge clk)
d <= { d[510:0],data };

wire [255:0]r0;
sha256_transform s0(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in( { 1'b0, d[510:0] } ),
.state_out(r0)
);

wire [255:0]r1;
sha256_transform s1(
.state_in( 256'h5be0cd191f83d9ab9b05688c510e527fa54ff53a3c6ef372bb67ae856a09e667 ),
.data_in( { 1'b1, d[510:0] } ),
.state_out(r1)
);

assign result = { r0[224], r1[224] };
endmodule


Кожен з модулів s0 і s1 вважають свій хеш від однакових вхідних даних, відрізняються на один біт nonce. З кожного забираю тільки самий «легкий» біт результату, біт номер 224.
Скільки триватиме така логіка в ПЛІС? 47,805 логічних елементів. Оскільки модулів два, то один займає 47805 / 2 = 23902. Виходить, що починати рахувати відразу два хеш-набагато вигідніше, ніж вважати їх по черзі за рахунок того, що є загальні обчислення.

А якщо починати рахувати відразу 4 хеша і тільки 2 біти різних на полі nonce?
Вийде 89009LE / 4 = 22252 LE/SHA256

А якщо рахувати 8 хешей?
Вийде 171418LE / 8 = 21427 LE/SHA256

Ось можна порівняти початкове число 30103 логічних елементів на повний SHA256_transform з висновком 256 біт результату і 21427 логічних елемента на SHA256_transfrom з висновком одного біта результату (які можна використовувати для прогнозування доцільності подальших розрахунків). Мені здається, що такими методами можна скоротити споживання енергії майнера десь майже на третину. Ну на чверть… Не знаю наскільки це суттєво, але здається, що це суттєво.

Є ще одна думка. Основні дані у блоці для обчислення залишаються зафикированными і під час обчислення хеша змінюється лише поле " nonce. Якщо б можна було швидко здійснювати компіляцію для ПЛІС, то значна частина предвычислений могла б бути виконана на етапі компіляції. Адже вище я показав, як ефективно компілятор обчислює все, що можна завчасно вирахувати. Оптимізована логіка з передобчисленням буде за обсягом набагато або значно менше, ніж потрібно для повного обчислювача, отже і енергії вона буде споживати менше.

Ну от якось так.
Насправді я й сам до кінця не впевнений у своєму дослідженні. Можливо я чогось не враховую або не розумію. Пропоновані методи, звичайно, не дають глобального прориву, але дещо що дозволяють заощадити. Поки це все швидше теоретичні міркування. Для практичної реалізації «чиста» SHA256 не годиться — у неї буде занадто маленька робоча частота. Вводити pipeline обов'язково доведеться.

Є ще один фактор. У реальному житті для биткоина вважаються два поспіль SHA256_transform. В цьому випадку мій очікуваний виграш за кількістю логічних елементів і споживаної енергії можливо виявиться не таким значним.

Вихідні коди проекту bitcon майнера для плати Марсоход3 з ПЛІС Altera MAX 10, 50K LE тут: https://github.com/marsohod4you/btc-fpga-miner
Тут же в папці research є всі вихідні коди моїх експериментів з алгоритмом SHA256.

Опис проекту майнера для ПЛІС тут.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.