Pull to refresh

Bitcoin & AI. Победа неизбежна

Reading time 5 min
Views 7.8K
О некоторых свойствах кривой secp256k1 и попытке предсказать ее поведение.

Как известно, задача дискретного логарифмирования является очень сложной и люди не знают способа вычислять его быстро. Более того, зная точку на кривой P = n*G очень трудно сделать суждение о величине n. Даже о приблизительной величине. Попробуем еще проще: попробуем делать суждения о последовательности $P(i) = i*G$, вернее о значениях $i$ зная значения $P(i)$.

Попробуем определить, насколько эта последовательность отличается от случайной последовательности. Если последовательность $P(i)$ сложная и ее трудно предугадать, то она не будет отличаться от случайной последовательности. А если будет отличаться, то это означает, что последовательность точек кривой secp256k1 не так уж и сложна.
Построим нейронную сеть, которую обучим на тренировочной последовательности отличать последовательности.

Если мы сможем различать случайную последовательность и последовательность точек, то это будет означать, что существует некий достаточно быстро вычисляемый алгоритм позволяющий делать суждения о логарифме.

Напомню, что вычисление дискретного логарифма на эллиптической кривой очень трудная задача.
Возьмем заранее вычисленную случайную последовательность для повторяемости эксперимента. Качество этой последовательности можно проверить

dieharder -f PM_rand_600.bin -g 201 -a

можно и nist проверить, но результат будет почти тот же.

Составим программу, которая будем смешивать координату y последовательности точек кривой и случайную последовательность в соотношении 1:8 и записывать в файл x600_btc_32_LH.bin и одновременно записывая в y600_btc_32_LH.bin указатель на источник — кривая или случайная.

data_preparation.cpp
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <openssl/bn.h>
#include <openssl/ec.h>
#include <openssl/err.h>
#include <openssl/symhacks.h>

using namespace std;

int main() {
	int bits = 256;

	unsigned char buf[32];

	char *pr;

	EC_GROUP *group;
	EC_KEY *eckey = EC_KEY_new();
	EC_POINT *P;

	BN_CTX *ctx = BN_CTX_new();
	BIGNUM *x = BN_new();
	BIGNUM *n = BN_new();  // начало последовательности точек кривой
	BIGNUM *y = BN_new();

	char e_buf[256];

	FILE * xFile;
	FILE * yFile;
	FILE * rFile;
	xFile = fopen("x600_btc_32_LH.bin", "wb");
	yFile = fopen("y600_btc_32_LH.bin", "wb");

	rFile = fopen("PM_rand_600_t.bin", "rb");
	if (rFile==NULL)
	{ cout<<" PM_rand.bin NOT FOUND"; return -1; }

	srand(time(NULL));
// nid 714. curve secp256k1
	int nid = 714;
	if ((group = EC_GROUP_new_by_curve_name(nid)) == NULL) {
		fprintf(stdout, "\nEC_GROUP_new_curve_name() failed with"
				" curve %s\n  nid %x", nid);
	}
	if (eckey == NULL) {
		cout << "ABORT2 ";
		ERR_error_string(ERR_get_error(), e_buf);
		cout << "E_BUF " << e_buf << endl;
	}

	if (!EC_KEY_set_group(eckey, group)) {
		cout << "ABORT3 ";
		ERR_error_string(ERR_get_error(), e_buf);
		cout << "E_BUF " << e_buf << endl;
	}

	EC_GROUP_precompute_mult(group, ctx);


	P = EC_POINT_new(group);

	BN_rand(n, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY);
	// n - начало выборки
	int NN = 60000;

	for (int i = 0; i < NN; i++) {

		if ((rand() % 128) < 16) {
			pr = (char *) "1";

			if (!EC_POINT_mul(group, P, n, NULL, NULL, ctx)) {
				cout << "ABORT_10 ";
				ERR_error_string(ERR_get_error(), e_buf);
				cout << "E_BUF " << e_buf << endl;
			}
			if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) {
				cout << "ABORT_11 ";
				ERR_error_string(ERR_get_error(), e_buf);
				cout << "E_BUF " << e_buf << endl;
			}
			BN_bn2bin(y, buf);
		} else {
			pr = (char *) "0";
			int cind = fread(buf, 32, 1, rFile); // read 32 byte = 256 bit
		}
		fwrite(buf, 32, 1, xFile);
		BN_add_word(n, 1L);  // in P new point n+i
		fwrite(pr, 1, 1, yFile);

	}

	fclose(xFile);
	fclose (yFile);

	BN_CTX_free(ctx);
	EC_GROUP_free(group);
	BN_free(x);
	BN_free(y);

}


И два полученных файла x600_btc_32_LH.bin и y600_btc_32_LH.bin скормим сети.

from keras.models import Model
from keras.utils import np_utils
from keras.layers import Dense, Input
from keras.layers import Bidirectional, GRU
from keras.models import Model
from keras.optimizers import RMSprop


import numpy as np
import keras as ks

num_classes = 2 

length = 32
length_8 = length<<3
num_train = 50000
num_test = 10000


X_train = np.zeros(shape=(num_train, length_8), dtype='uint8')
y_train = np.zeros(shape=(num_train), dtype='uint8')

X_test = np.zeros(shape=(num_test, length_8), dtype='uint8')
y_test = np.zeros(shape=(num_test), dtype='uint8')

bx_train = np.zeros(shape=(num_train, length), dtype='uint8')
bx_test = np.zeros(shape=(num_test, length), dtype='uint8')

f_x = open("./input/x600_btc_32_LH.bin", 'rb')
for k in xrange(num_train):
    for i in xrange(32):
        bx_train[k, i] = ord(f_x.read(1))

for k in xrange(num_test):
    for i in xrange(32):
        bx_test[k, i] = ord(f_x.read(1))

f_x.close()

f_y = open("./input/y600_btc_32_LH.bin", 'rb')
for i in xrange(num_train):
    y_train[i] = ord(f_y.read(1))

for i in xrange(num_test):
    y_test[i] = ord(f_y.read(1))
    
f_y.close()
y_train -= 48
y_test -= 48

Переведем в формат бит в байт. Т.е. один бит исходной последовательности переносим в байт.

tab = np.zeros((256,8),dtype='int8')
for i in xrange(256):
    mask = 1
    for j in xrange(8):
        if i & mask == 0:
            tab[i,j] = 0
        else:
            tab[i,j] = 1
        mask<<1
for k in xrange(num_train):
    for i in xrange(length):
        for j in xrange(8):
            X_train[k,i*8+j] = tab[bx_train[k,i],j]
            
for k in xrange(num_test):
    for i in xrange(length):
        for j in xrange(8):
            X_test[k,i*8+j] = tab[bx_test[k,i],j]


Переведем в формат float и масштабируем до 0.004 и подготовим Y.

X_train = X_train.astype('float32') 
X_test = X_test.astype('float32')
X_train /= 255.
X_test /= 255.

Y_train = np_utils.to_categorical(y_train, num_classes)
Y_test = np_utils.to_categorical(y_test, num_classes)

Сеть возьмем достаточно простую, только немного изменим функцию активации.

import math
from keras import backend as K
from keras.utils.generic_utils import get_custom_objects
from keras.layers import Activation

def gaussian(x):
    mu = 64.
    sigma = 10.
    xx = -0.5*((x-mu)/sigma)**2 / sigma / math.sqrt(2*math.pi)
    return K.exp(xx)

get_custom_objects().update({'gaussian': Activation(gaussian)})

batch_size = 32
num_epochs = 16
hidden_size_1 = 1024
hidden_size_2 = 1024

X_train = X_train.reshape(num_train,16,16)
X_test = X_test.reshape(num_test,16,16)

inp = Input(shape=(16,16,))
x = Bidirectional(GRU(1024, return_sequences=True))(inp)
x = Bidirectional(GRU(1024, return_sequences=False))(x)
x = Dense(hidden_size_1, activation='sigmoid')(x)
x = Dense(hidden_size_2, activation='gaussian')(x)

out = Dense(num_classes, activation='gaussian')(x) 

model = Model(inputs=inp, outputs=out)
model.compile(loss='binary_crossentropy',
#              optimizer='adam',
              optimizer=RMSprop(lr=0.0001,clipvalue=1, clipnorm=1),
              metrics=['accuracy'])


Результат вполне приемлем, сеть отличает последовательность точек кривой от случайной последовательности, не так точно как хотелось бы, но суждение о логарифме делает.

mod = model.fit(X_train, Y_train, # Train the model using the training set...
          batch_size=batch_size, epochs=2,
          verbose=1, validation_data=(X_test, Y_test))

Train on 50000 samples, validate on 10000 samples
Epoch 1/2
val_loss: 0.3706 - val_acc: 0.8783
Epoch 2/2
val_loss: 0.3703 - val_acc: 0.8783

Мы получили, что простая обычная нейронная сеть может различать случайную последовательность и последовательность точек кривой secp256k1. Это говорит о том, что сеть обнаруживает закономерности в последовательности, которая должна быть очень сложной.

На сегодняшний день, 01.04.18, это самая серьезная уязвимость кривой secp256k1 и рано или поздно победа будет за AI.

Все тексты и файлы выложены на GitHub и можно всё проверить, убедиться и усовершенствовать.
Tags:
Hubs:
+8
Comments 27
Comments Comments 27

Articles