Поиск двойников среди 5 млн. лиц за 0.8 секунды

В статье описан метод, при помощи которого осуществляется поиск клонов в Dcoin.
Также Вы узнаете, во сколько обойдется изменение внешности, которое позволит обмануть алгоритм.
Зачем вообще в криптовалюте нужна привязка к лицам.
Новый метод p2p оффлайн проверки.
Зачем в Dcoin админ и как от него избавиться.
И многое другое.

Для начала отвечу на главный вопрос: Зачем вообще в криптовалюте нужна привязка к живым людям?
У bitcoin используется PoW (Proof-of-Work). Кто быстрее может перебирать хэши с целью найти тот самый заветный, который примут все биткоин-клиенты, тот правит балом. И может решать, чьи транзакции принять в блок, а чьи нет. Сейчас эта власть находится в руках 3-х владельцев пулов.
Некоторые криптовалюты используют PoS (Proof-of-stake). У кого больше всего монет, тот и главный, т.е. с большей вероятностью может сгенерировать и подписать блок.
В Dcoin нет ни PoW, ни PoS, а есть одноранговые пользователи, прошедшие проверку на уникальность (майнеры), каждый из которых может сгенерировать и подписать блок. Таким образом достигается децентрализация, недостижимая при PoW и PoS. Но чтобы всё это работало, необходима защита от массовых регистраций.

Как я искал решение проблемы идентификации

К тому, что нужно снимать фото и видео лица и ставить на них точки, я пришел не сразу.
В процессе поиска был вариант с отпечатками пальцев. Экспериментировал с замазыванием пальцев чернилами ручки и оставлении отпечатка на бумаге. Но рисунок было слабо видно на телефонной камере. К тому же, рисунок легко подделать надеванием перчаток, облегащих кожу и дающих новые отпечатки.
Прорабатывал идею сравнения рисунков ушных раковин, которые, оказывается, у всех уникальные. Кстати, забегу вперед и скажу, что благодаря разным рисункам ушных раковин, в будущем будет добавлена возможноть становиться майнерами двойникам и близнецам.
В итоге остановился на сравнении лиц. А чтобы нельзя было сделать подделку в фотошопе, к фото должно прилагаться видео. Начал изучать технологии распознавания лиц, OpenCV, задача еще усложнялась тем, что всё делалось на php, в итоге добился только поиска лица и глаз на нем. Ситуация казалась тупиковой. Пока неожиданно меня не озарило, ведь на фото люди сами могут наносить точки, по которым можно делать сравнение.

Подделка видео

А что если взять да сгенерировать в каком-нибудь софте видео-ролики, затем зарегать 100500 майнерких аккаунтов, уничтожив Dcoin на корню? Или нанять гримеров, которые будут создавать тысячи новых лиц в сутки?
За небольшие деньги такое возможно только в научной фантастике. Чтобы не быть голословным, я буду приводить пруф-линки.

Компьютерная подделка

Минимальная цена создания одного такого видео будет от 2000$, хотя некоторые специалисты утверждают, что для достижения более-менее приемлемого уровня реалистичности нужно от 1 млн$ за каждый ролик. Пруф

Профессиональный грим

Если взять, например, одного человека и 50 раз его загримировать и разгримировать?
Звучит довольно просто, но на деле такое удовольствие обойдется от 100k$ до 285k$ за 50 гримов. Пруф
В студии Петра Горшенина, где мне озвучили сумму в 285k$, процесс описали вот так:
«Нужно снять форму с человека, отлить модель его лица. Потом изготовить модели частей лица столько, сколько будет разных деталей, примерно 5(отдельно лоб, нос, подбородок и две скулы). Далее на них делаются скульптуры изменений из пластилина. Потом с этого опять снимаются формы, в которых будут отливаться сами детали из силикона. И все это 50 раз за исключением первого снятия формы с человека.»

Про возможность возникновения «ферм»

Скорее всего, рано или поздно, возникнут «Фермы», где ушлые дельцы будут платить по 10-20$ за полную регистрацию аккаунта с добавленной обещанной суммой и оффлайн проверкой. Но если такие хитрецы появятся, значит прибыль, которую они будут получать с каждого такого аккаунта, будет не менее нескольких сотен долларов. Если кто-то отправит на такой серый аккаунт запрос на обмен Dcoin на указанную там обещанную сумму, то владельцу такой фермы будет совершенно не выгодно получить заморозку роста монет по его обещанным суммам. Ведь полученные Dcoin можно без проблем продать на бирже. И ему придется отдать обещанную сумму в обмен на такое же кол-во Dcoin. Т.е. такая ферма, по сути не будет отличаться от группы простых майнеров, единственное, что все сливки будет получать один человек.
Но больших объемов у таких ферм не будет. Т.к. при выявлении первой такой схемы будет добавлено правило записи первого ролика, в котором будет говориться, что нужно на камеру показать лист бумаги, на котором написано «с правилами на сайте democratic-coin.com согласен». Большинство из любопытства зайдут на сайт, чтобы узнать, с чем таким они согласны. А на сайте будет написано, что продавать аккаунт за 10-20$ крайне не выгодно, гораздо выгоднее этот аккаунт использовать самому.

А что если поехать в глухую провинцию Индии, где у 85% населения нет интернета, и снимать там людей в студии?
Опять же, получится ферма, которая не будет оказывать серьезного негатива, т.к. владельцу фермы будет невыгодно игнорировать запросы на его обещанные суммы.
Но не спалить такую ферму будет гораздо сложнее, т.к. пройти оффлайн проверку и затеряться в крупном городе не получится, а значит придется притворяться жителем каких-то мелких городов, где еще не набралось 25 майнеров. А все такие города будут тщательно проверяться админом. Останется найти схожие элементы на видео и отправить запросы с просьбой снять новое видео.

Само существование ферм предполагает, что Dcoin уже развился и каждый майнерский аккаунт является источником постоянной прибыли. А владельцы таких ферм получают сверхприбыли, пользуясь неосведомленностью обывателей. Этот факт не сможет долго оставаться незамеченным и рано или поздно попадет в СМИ. И все эти неосведомленные очень быстро станут осведомлены, что выгоднее самому стать майнером, тем более, для этого к тому времени, возможно, не нужен будет даже компьютер, достаточно один раз зарегистрироваться в каком-нибудь интернет-кафе и дальше использовать мобильный телефон как у 37coins.

Песочина для новых майнеров

Просто так взять и заполонить DС-сеть ботами-майнерами невозможно, потому что новый майнер может зарегистрировать новых юзеров не раньше, чем через один месяц. И в месяц можно регистрировать не более 2-х юзеров. Голосование и обмен на наличные новым майнерам также становятся доступны только через месяц.

Сутки на проверку

А что если где-то достать 10 аккаунтов и ставить по 10 плюсиков своим ботам?
Из этого ничего не получится. Т.к. голосование не может быть завершено ранее, чем через 24 часа от появления транзакции в DC-сети. И если за это время претендент соберет 10 минусов, то майнером он не станет. А чтобы у всех майнеров была мотивация проверять других майнеров, существуют баллы, недобор которых приводит к снижению % роста обещанных сумм.

Офф-лайн проверка

(В процессе внедрения)
Если в радиусе 25км от пользователя, который хочет стать майнером, есть минимум 25 других майнеров, то из них будет выбран 1 псевдо-случайный.

/**  * @param int $user_id - user_id претендента на майнера.  * @param int $size - кол-во элементов в массиве майнеров, которые находятся в пределах 25км.  * @return int  */ function get_checking_miner_id ($user_id, $size) {   $hi = $user_id / 127773;   $lo = $user_id % 127773;   $x = 16807 * $lo - 2836 * $hi;   if ($x <= 0)      $x += 0x7fffffff;   $key = ( ($user_id = $x) % ($size + 1));   return $key; } 

Как видно из алгоритма, сделать так, чтобы проверку делал какой-то определенный майнер, невозможно. Выбранному майнеру отправляются контакты претендента на майнера, он должен ему позвонить и назначить место встречи. В течение 2-х суток они должны встретиться, выбранный майнер должен сделать их совместное фото, выложить на свою ноду и отправить транзакцию в DC-сеть.

За это он получит 1000 баллов. Также он может отправить транзакцию, в которой отказывается делать проверку. Если прошло 2 суток или была отправлена транзакция с отказом, претендент получает право отправить новый запрос следующему случайному майнеру.
Если в радиусе 25км менее 25 майнеров, то проверка происходит без личной встречи. В радиусе 50,100,500,1000,10000,100000км ищется 25 майнеров, выбирается псевдо-случайный, ему шлется запрос. Он должен по скайпу позвонить претенденту, посмотреть на него через камеру, сделать фото, выложить на свою ноду, отправить транзакцию в DC-Сеть.
После того, как транзакция с фото отправлена, претендент получает право отправить в DC-сеть транзакцию, в которой укажет ссылку на свое видео, хэши своих фото, точки на фото. Далее идет проверка майнерами и голосование.

Таким образом «ферма» не сможет затеряться в толпе в крупном городе, а все майнеры, которые будут появляться в местах, где еще нет 25-и других майнеров, будут дополнительно проверяться админом.

Про баллы

Чтобы получать майнерский %, нужно каждый месяц набирать кол-во баллов, не менее, чем:
Сумма баллов всех майнеров за месяц / кол-во майнеров * Коэффициент.
Коэффициент в данный момент равен 0.3
Если баллов меньше, то в следующем месяце будет юзерский процент.

Отправка данных в DC-сеть и проверка нодами

После успешного прохождения оффлайн проверки, пользователь, который хочет стать майнером, заливает на свою ноду 2 фото, отмечает на них точки, указывает url к видео и отправляет в DC-сеть транзакцию. В этой же транзакции указаны хэши от фото.
Ноды получают эту транзакцию в одном из блоков и если находят себя среди тех, кто должен скачать эти фото к себе, то автоматически качают их.
Ноды, которые должны сохранить фото у себя, определяются вот таким алгоритмом:

/**  * @param int $block_id номер блока, в котором транзакция была принята.  * @param int $max_miner_id - максимальный id майнера на момент, когда тр-я попала в блок.  * @param int $miners_keepers - сколько нодов должны сохранить фото у себя. сейчас это 10.  * @return array  */ function get_miners_keepers ($block_id, $max_miner_id, $miners_keepers) {   for ($i=0; $i < $miners_keepers; $i++) {     $hi = $block_id / 127773;     $lo = $block_id % 127773;     $x = 16807 * $lo - 2836 * $hi;     if ($x <= 0)         $x += 0x7fffffff;     $miner_id = ( ($block_id = $x) % ($max_miner_id + 1));     $miner_id = ($miner_id==0)?1:$miner_id;     $array[] = $miner_id;   }   return $array; } 

Т.е. сделать так, чтобы фото сохранили какие-то конкретные ноды, невозможно.
Каждая нода, которая сохранила фото у себя, сравнивает их хэши с хэшами, указанными в транзакции. Если они сходятся, то отправляет в DC-сеть транзакцию, в которой сообщает о том, что проверка пройдена. Если >=50% нодов подтвердили, что успешно скачали к себе фото, то начинается проверка майнерами. Проверка нодами происходит в автоматическом режиме, без участия майнера.

Проверка майнерами

На первом шаге нужно проверить, верно ли нанесены точки на фото.
Далее, нужно сравнить фото и видео, действительно ли там одно и то же лицо. А также фото, полученное от майнера, который делал проверку в оффлайн.
После этого выдается страница, где показаны фото похожих людей. Нужно визуально проверить, нет ли на них подозрительно похожих лиц. Предусмотрен выбор расы, т.к. для европейцев все азиаты на одно лицо, а для азиатов все европейцы одинаковые.

На данном примере видно, что у претендента был найден точный клон
Если фото не отображено, то нужно нажать на кнопку «перезагрузить», тогда это фото загрузится с другой ноды. Если ни с одной из 10-и нод фото невозможно загрузить, то есть вероятность, что наш претендент на майнера просто заддосил 10 нодов, где лежит фото от его предыдущего аккаунта. Поэтому нужно отказывать такому майнеру. За выполнение задания по проверке претендента в майнеры начисляется 50 баллов

Будут ли майнеры ответственно относиться к выполнению заданий?

Если у Вас прямо сейчас есть какое-то кол-во btc, то любой негатив в СМИ в сторону bitcoin будет Вам неприятен, т.к. этот негатив может повлиять на курс btc, а следовательно, и на кол-во благ, которые Вы могли бы купить на свои btc. При этом, когда у Вас не было btc, то отношение к новостям о bitcoin у Вас было более нейтральным. Верно?
Представьте, что у Вас куплено Dcoin на какую-то сумму или у Вас добавлена обещанная сумма, которая приносит постоянную прибыль. Только в этом случае судьба Dcoin будет Вам действительно небезразлична. И если от Вас будет зависеть, пройдут ли в DC-сеть чьи-то клоны, которые смогут получить незаслуженные монеты, то отнесетесь ли Вы ответственно к процедуре их проверки? При этом, запрещать всех подряд нельзя, ведь Dcoin должен проникать в широкие массы, чтобы Ваши монеты можно было без проблем обменять на фиат.

Поиск клонов изнутри

Нам понадобится один отрезок на каждой из 2-х фото, с которым будем сравнивать все остальные отрезки.
Сейчас это расстояние между глаз на фото анфас и расстояние от глаза до края уха на фото в профиль.

В таблице spots_compatibility хранится:
1. Текущая версия.
2. Точки, которые наносятся на 2 фото примера.
3. С какими версиями совместимо.
4. Какие точки с какими будем соединять для получения отрезков.
5. Допустимые расхождения при поиске клонов.

В таблице faces хранится:
1. f1,f2…f20 — соотношения отрезков на лице анфас к расстоянию между глаз.
2. p1,p2…p20 — соотношения отрезков на лице в профиль к расстоянию от глаза до края уха.
3. Версия spots_compatibility, которая была на тот момент.

Если будет найден более эффективный набор точек для поиска клонов, то данные в таблице spots_compatibility обновляются и в таблицу faces будут заносится отрезки на основе нового набора точек.

В первом шаге проверки претендента на майнера мы убедились, что точки на фото нанесены верно, а значит отрезки будут получены тоже верные. Остается просто сделать запрос в базу данных, где будет идти сравнение с f1,f2…f20 и с p1,p2…p20 с учетом допустимых расхождений из spots_compatibility. В итоге получаем id майнеров, которые похожи на претендента.
Тесты:
i7-2600k / centos i386 / стандартные настройки mysql и php

Проверка админом

Возможно, из-за неидеальных значений в spots_compatibility, клоны смогут проскакивать. По-этому у админа есть возможность разжаловать уже прошедших проверку майнеров в пользователи, но не более 1000 за день. В результате этого перевода, средства на аккаунте майнера никуда не денутся, просто будут расти с юзерским %, а обещанные суммы перестанут приносить новые монеты.

Защита от админа

(В процессе внедрения)
Если действия админа будут не устраивать большинство, то майнеры могут проголосовать за передачу функций админа любому пользователю. Если наберется более 50% голосов, то все функции админа полностью перейдут к выбранному пользователю.
Интересно, как бы сейчас выглядел фейсбук, если бы у каждого зарегистрированного там человека была возможность нажать кнопку «Заменить Цукенберга на ….»

Сейчас готовлю еще 4 статьи:
Как определить того, кто будет подписывать блок без PoW и PoS.
Алгоритм обмена внутренней валюты на фиатные деньги.
Добровольная деноминация, если случится гиперинфляция.
Тройная подпись и всё про безопасность.

Предыдущий пост про Dcoin