Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Вопрос-Ответ Новый топик    Ответить
 Proof of Memory  [new]
Иван FXS
Member

Откуда:
Сообщений: 2343
Кто-нибудь может привести пример математической задачи, для решения которой нужно очень много (компьютерной, естественно) памяти, но требования по скорости к этой памяти невысокие (то есть не обязательно это должна быть оперативка),

а для проверки того, что задача решена -- много памяти уже не нужно, да и вообще "ресурсов" нужно намного меньше, чем для решения задачи.
4 май 21, 20:15    [22318476]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
kdv
Member

Откуда: iBase.ru
Сообщений: 29805
Иван FXS,

блокчейн chia? :-)
5 май 21, 11:46    [22318681]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
Иван FXS
Member

Откуда:
Сообщений: 2343
kdv
блокчейн chia
да, только "блокчейн chia" не есть формулировка (изложение) математической задачи...
5 май 21, 12:19    [22318700]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
exp98
Member

Откуда:
Сообщений: 3008
Для уточнения:
- диск - комповая память или нет?
- облако?
- срок решения задачи не интересен? (навроде получения перестановок 100х100)?
5 май 21, 13:04    [22318729]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
Иван FXS
Member

Откуда:
Сообщений: 2343
exp98
- диск - комповая память или нет?
- облако?
обобщенной "памяти" -- мы же про математические задачи говорим, а не про программные -- и тем более не про аппаратные! -- их реализации.
exp98
- срок решения задачи не интересен?
то есть моего уточнения "требования по скорости к этой памяти невысокие" недостаточно? Хорошо, говорю явным образом: интересуют задачи, которые достаточно (или "относительно") легко решаются при задействовании большого объёма памяти.
5 май 21, 14:21    [22318782]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
Иван FXS
Member

Откуда:
Сообщений: 2343
Понятно, что я тут немного кривлю душой: речь идет не об однократном решении отдельной задачи, а о систематическом решении однотипных задач, которые -- как "поток задач" -- должны легко решаться (типа, в пересчете затраты ресурсов на одну задачу в этом потоке), если -- для них, всех и каждой -- задействован большой объём памяти.

Мой ход мысли такой: видимо, должно быть выгодно предварительно (однократно) решить большое количество некоторых "инфраструктурных" (математических) задач и сохранить их результаты -- которые сами занимают большое место в памяти. И тогда -- с использованием этих накопленных "инфраструктурных" результатов -- конкретные задачи в "потоке задач" -- должны легко решаться.

Например, задачи в "потоке" должны использовать (многократно обращаться к) большой список простых чисел. Соответственно, если этот список заранее заготовлен ("на диске"), то задачи решаются легко.

Кстати, вот если бы удалось построить блокчейн, для работы которого именно нужен большой список простых (или каких-то других особых) чисел, то от такого блокчейна была бы и "польза для человечества" -- именно доступ к этом списку чисел.

Сообщение было отредактировано: 5 май 21, 14:30
5 май 21, 14:36    [22318792]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
miksoft
Member

Откуда:
Сообщений: 38827
Иван FXS,

Например, нахождение коллизий хэшей, когда алгоритмический вариант слишком сложен.
Можно построить полную таблицу значений хэша. Но вот только для мало-мальски приличных хэш-функций они будут занимать совсем неприличный объем.
5 май 21, 14:52    [22318808]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
miksoft
Member

Откуда:
Сообщений: 38827
Небольшой пример:
У нас на работе иногда применяется такой метод обезличивания данных как хэширование. Однажды мне попалось оно же применительно к ИНН юрлиц.
Мне не все и не сразу проверили, что это легко проворачивается обратно - достаточно всего лишь взять список всех ИНН, применить к ним хэш-функцию и сложить в табличку. Вариантов максимум миллиард, если генерить полным перебором, это не очень большой объем. На самом деле можно взять список имеющихся ИНН из таблицы клиентов, а это вообще ничтожный объем.
5 май 21, 15:05    [22318821]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
Иван FXS
Member

Откуда:
Сообщений: 2343
miksoft, в принципе, да, только я не понял, почему вы обозначили задачу как "нахождение коллизий хэшей"? Я бы тогда уж сформулировал её просто как "задача, обратная хэшированию".

То есть, если имеем систему хэширования не запредельной мощности... ну не знаю, например, она принимает на вход битовые строки длиной 100 бит и порождает из них хэши тоже длиной 100 бит, и задача состоит в том, чтобы для полученной на входе битовой строки (например, взятой из заголовка блока блокчейна) найти, хэшем какой строки она является (и, например, вписать эту найденную строку в тот самый заголовок блока -- в качестве демонстрации того, что задача решена),

-- тогда единственный способ (гарантированно) решить эту задачу требует наличия полной -- размером 2^100 таблицы хэширования...
5 май 21, 20:48    [22318985]     Ответить | Цитировать Сообщить модератору
 Re: Proof of Memory  [new]
miksoft
Member

Откуда:
Сообщений: 38827
Иван FXS
только я не понял, почему вы обозначили задачу как "нахождение коллизий хэшей"? Я бы тогда уж сформулировал её просто как "задача, обратная хэшированию"
Ну да, пример вышел не про коллизии.
Но коллизии тоже можно находить.
6 май 21, 13:29    [22319204]     Ответить | Цитировать Сообщить модератору
Все форумы / Вопрос-Ответ Ответить