[Перевод] Разбираемся с генетическим кодом криптокотиков

… и учимся работать с инструментами разработчиков Ethereum на реальном примере.

Часть нулевая: объект попал в поле зрения


Я только что закончил свои лекции по курсу фулл-стек разработки децентрализованных Ethereum-приложений на Solidity на китайском языке. Я давал его в свободное от работы время с целью повысить уровень знаний о блокчейне и смарт контрактах среди китайского комьюнити разработчиков. За время работы я подружился с парой студентов.

И вот как раз по завершении курса, мы внезапно обнаружили себя в окружении вот таких созданий:

eve-ovga3bt6vx11ichn6jmkufm.png

Изображение с сайта cryptokitties.com

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

Как те или иные криптокошки получают свой набор генов?


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

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

Часть первая: высокоуровневая логика генерации маленьких котят


Для начала мы задались вопросом: как происходит рождение криптокотят?

Для ответа на него мы воспользовались великолепным блокчейн-проводником Etherscan, позволяющим делать гораздо больше чем просто «изучать параметры и содержимое блоков». Так мы обнаружили исходный код контракта CryptoKittiesCore:

coodv1ao8ns32llhof2bhbpp3h8.png

https://etherscan.io/address/0×06012c8cf97bead5deae237070f9587f8e7a266d#code

Обратите внимание, что развернутый контракт на деле несколько отличается от использованного в баунти-программе. Согласно этому коду, малыш-котенок образуется в два шага: 1) кошка-мать оплодотворяется котом; 2) несколько позже, когда период созревания плода подходит к концу, вызывается функция giveBirth. Эту функция как правило вызывается неким процессом-демоном, но, как вы увидите далее, для получения интересных мутаций, вам необходимо будет правильно подобрать блок, в котором родился ваш котенок.

function giveBirth(uint256 _matronId)
        external
        whenNotPaused
        returns(uint256)
    {
        Kitty storage matron = kitties[_matronId];
// Проверить, что мать-кошка настоящая.
        require(matron.birthTime != 0);
// Проверить, что она беременна и время родов пришло!
        require(_isReadyToGiveBirth(matron));
// Взять из хранилища ссылку на кота-отца.
        uint256 sireId = matron.siringWithId;
        Kitty storage sire = kitties[sireId];
// Определить, кто из родителей принадлежит к более старшему поколению
        uint16 parentGen = matron.generation;
        if (sire.generation > matron.generation) {
            parentGen = sire.generation;
        }
// Вызвать сверхсекретную операцию смешивания генов.
        uint256 childGenes = geneScience.mixGenes(matron.genes, sire.genes, matron.cooldownEndBlock - 1);


В приведенном выше коде вы можете четко видеть, что гены новорожденного котенка определяются прямо в момент рождения, путем вызова функции mixGenes из внешнего смарт-контракта geneScience. Эта функция принимает три параметра: ген матери, ген отца и номер блока, в котором кошка будет готова родить.

У вас вероятно возникнет закономерный вопрос, почему гены определяются не в момент зачатия, как это происходит в реальном мире? Как вы увидите в ходе дальнейшего повествования, это позволяет довольно изящно защититься от попыток предугадать и расшифровать гены. Такой подход исключает возможность 100% точного предсказания генов котенка до того, сам факт беременности кошки-матери фиксируется в блокчейне. И даже если бы вы могли узнать точный код, отвечающий за смешивание генов, это не дало бы Вам никакого преимущества.

Как бы то ни было, в начале мы этого еще не знали, поэтому давайте продолжим. Теперь нам надо узнать адрес контракта geneScience. Для этого воспользуемся MyEtherWallet:

nffaylnytgmybdkavya0so0ugmi.png

Адрес контракта geneScience

Так выглядит байткод контракта:

0x60606040526004361061006c5763ffffffff7c01000000000000000000000000000000000000000000000000000000006000350416630d9f5aed81146100715780631597ee441461009f57806354c15b82146100ee57806361a769001461011557806377a74a201461017e575b600080fd5b341561007c57600080fd5b61008d6004356024356044356101cd565b604051908152602001604051809........


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

Часть вторая: крах простой гипотезы


Итак, чего же мы хотим добиться в итоге? Надо понимать, что мы не ставим перед собой цель на все 100% задекомпилить байткод, превратив его в человекочитаемый solidity-код. Нам нужен дешевый (без необходимости платить за транзакции в боевом блокчейне) способ определения генов котенка при условии, что мы знаем, кто его родители. Вот этим и займемся.

Для начала давайте воспользуемся опкод-инструментом Etherscan для беглого анализа. Выглядит это так:

m6nt72740bwhn4qz6dlkz0pc6qi.png

Гораздо понятнее

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

  1. Используются ли в нем временные метки? Нет, поскольку отсутствует опкод TIMESTAMP. Если в нем и есть какая-либо простая случайность, то ее источником точно является другой опкод.
  2. Используется ли хэш блока? Да, BLOCKHASH встречается два раза. Поэтому случайность, если она есть, может возникать из их этих опкодов, но мы в этом пока не уверены.
  3. Используются ли какие-либо хэши вообще? Да, встречается SHA3. Не ясно, впрочем, что он делает.
  4. Используется ли msg.sender? Нет, поскольку отсутствует опкод CALLER. Поэтому к контракту не применяется какой-либо контроль доступа.
  5. Используется ли какой-либо внешний контракт? Нет, отсутсвует опкод CALL.
  6. Используется ли COINBASE? Нет, и таким образом мы исключаем еще один возможный источник случайности.


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

Для проверки этого предположения мы вызываем функцию mixGene в основной сети с тремя случайными параметрами: 1111115, 80, 40 и получаем некий результат X. Далее, деплоим этот байткод с помощью truffle и testrpc. Так наша лень привела к несколько нестандартному способу применения truffle.

contract GeneScienceSkeleton {
    function mixGenes(uint256 genes1, uint256 genes2, uint256 targetBlock) public returns (uint256) {}
}


Начинаем со скелета контракта, кладем его в структуру папок фреймворка truffle и выполняем truffle compile. Однако вместо прямой миграции этого пустого контракта в testrpc, мы заменяем байткод контракта в папке build на реальный развернутый байткод и рантайм байткод контракта geneScience. Это нетипичный, но быстрый способ если вы хотите развернуть контракт с одним только байткодом и некоторым ограниченным открытым интерфейсом для локального тестирования. После этого мы напрямую вызываем Mixgenes с параметрами 1111115, 80, 40, и к нашему сожалению получаем в ответ ошибку с ответом revert. Хорошо, смотрим глубже. Как мы знаем, сигнатура функций mixGene — 0×0d9f5aed, поэтому берем ручку и бумагу и отслеживаем выполнение байткода, начиная с точки входа этой функции для учета изменений в стеке и хранилище. После нескольких JUMP«ов мы оказываемся здесь:

[497] DUP1 
[498] NUMBER 
[499] DUP14 
[500] SWAP1 
[501] GT 
[504] PUSH2 0x01fe 
[505] JUMPI 
[507] PUSH1 0x00 
[508] DUP1 
[509] 'fd'(Unknown Opcode)


Судя по содержимому этих строк, если номер текущего блока меньше третьего параметра, то вызывается revert (). Хорошо, это вполне резонное поведение: вызов реальной функции в игре с указанием номера блока из будущего невозможен и этого логично.

Такую проверку входных данных легко обойти: мы просто майним немного блоков на testrpc и вызываем функцию повторно. В этот раз функция успешно возвращает значение Y.

Но, к сожалению, X!= Y

Жаль. Это значит, что результат выполнения функции зависит не только от входных параметров, но также и от состояния блокчейна основной сети, которое, разумеется, отличается от состояния ненастоящего блокчейна testrpc.

Часть третья: закатываем рукава и копаемся в стеке


Ладно. Значит, пришло время засучить рукава. Бумага больше не годится для отслеживания состояния стека. Значит для проведения более серьезных работ запустим весьма полезный EVM дизассемблер под названием evmdis.

По сравнению с бумагой и ручкой это ощутимый шаг вперед. Продолжим с того, на чем остановились в прошлой главе. Далее приводим воодушевляющий вывод с evmdis:

.............
:label22
# Stack: [@0x70E @0x70E @0x70E 0x0 0x0 0x0 @0x88 @0x85 @0x82 :label3 @0x34]
0x1EB PUSH(0x0)
0x1ED DUP1
0x1EE DUP1
0x1EF DUP1
0x1F0 DUP1
0x1F1 DUP1
0x1F3 DUP13
0x1F9 JUMPI(:label23, NUMBER() > POP())
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 0x0 0x0 @0x88 @0x85 @0x82 :label3 @0x34]
0x1FA PUSH(0x0)
0x1FC DUP1
0x1FD REVERT()
:label23
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 0x0 0x0 @0x88 @0x85 @0x82 :label3 @0x34]
0x1FF DUP13
0x200 PUSH(BLOCKHASH(POP()))
0x201 SWAP11
0x202 POP()
0x203 DUP11
0x209 JUMPI(:label25, !!POP())
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 @0x200 0x0 @0x88 @0x85 @0x82 :label3 @0x34]
0x20C DUP13
0x213 PUSH((NUMBER() & ~0xFF) + (POP() & 0xFF))
0x214 SWAP13
0x215 POP()
0x217 DUP13
0x21E JUMPI(:label24, !!(POP() < NUMBER()))
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 @0x200 0x0 @0x213 @0x85 @0x82 :label3 @0x34]
0x222 DUP13
0x223 PUSH(POP() - 0x100)
0x224 SWAP13
0x225 POP()
:label24
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 @0x200 0x0 [@0x223 | @0x213] @0x85 @0x82 :label3 @0x34]
0x227 DUP13
0x228 PUSH(BLOCKHASH(POP()))
0x229 SWAP11
0x22A POP()
:label25
# Stack: [0x0 0x0 0x0 0x0 0x0 0x0 @0x70E @0x70E @0x70E 0x0 [@0x200 | @0x228] 0x0 [@0x88 | @0x223 | @0x213] @0x85 @0x82 :label3 @0x34]
0x22C DUP11
0x22D DUP16
0x22E DUP16
...........


Чем evmdis действительно хорош, так это его полезностью для анализа JUMPDEST в нужные лейблы, которую невозможно переоценить.

Итак, после того, как мы передаем первоначальный require, мы оказываемся на label 23. Видим DUP13 и, вспоминаем по предыдущей главе, что номер 13 в стеке — это наш третий параметр. Значит мы пытаемся получить BLOCKHASH нашего третьего параметра. Однако действие BLOCKHASH ограничено 256 блоками. Вот почему за ним следует JUMPI (это if-конструкция). Если перевести логику опкодов на язык псевдокода, получим нечто подобное:

func blockhash(p) {
    if (currentBlockNumber - p < 256) 
        return hash(p);
    return 0;
}

var bhash = blockhash(thrid);
if (bhash == 0) {
    thirdProjection = (currentBlockNumber & ~0xff) + (thridParam & 0xff);
    if (thirdProjection > currentBlockNumber) {
        thirdProjection -= 256;
    }
    thirdParam = thirdProjection;
    bhash = blockhash(thirdProjection);
}
label 25 and beyond
..... some more stuff related to thirdParam and bhash


some more stuff related to thirdParam and bhash — другой код связанный с thirdParam и хэшем блока

Теперь мы полагаем, что нашли причину, по которой наши результаты отличаются от тех, что мы наблюдаем в основной сети. Что более важно, нам, судя по всему, удалось обнаружить источник случайности. А именно: хэш блока вычисляется на основе третьего параметра, или прогноза третьего параметра. Важно отметить, что в стеке третий параметр также заменяется на этот прогнозируемый номер блока.

Очевидно, что во время локального выполнения вне основной сети, у нас нет простого варианта навязать возвращение BLOCKHASH, совпадающего со значениями основной сети. Как бы то ни было, поскольку нам известны все три параметра, мы можем с легкостью наблюдать за основной сетью и получить хэш блока H для третьего параметра, равно как и хэш прогнозируемого блока.

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

Но есть одна загвоздка: DUP13 и BLOCKHASH — это всего 2 байта в коде, и если мы просто заменим их на 33 байтный PUSH32 0x*хэш*, счетчик программы полностью изменится и нам придется исправлять каждый JUMP и JUMPI. Или же нам придется сделать JUMP в конец кода и заменить инструкции развернутого кода и так далее.

Что ж, раз мы уж мы зашли так далеко, похакаем еще немного. Поскольку мы пушим 32-байтовый ненулевой хэш в if-ветку, условие всегда будет справедливо и следовательно, все, что записано в else части можно просто выкинуть, чтобы освободить место для нашего 32-байтового хэша. Ну в общем так мы и сделали:

n1xx-xl6ew1nlx-xjwzkgtk90cs.png

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

Это к тому, что если вы пытаетесь получить результат операции
mixGene (X, Y, Z), где currentBlockNumber — Z < 256, вам нужно только заменить PUSH32-хэш на хэш блока Z.
Однако если вы намерены сделать следующее
mixGene (X, Y, Z), где currentBlockNumber — Z ≥ 256, вам надо будет заменить PUSH32-хэш на хэш блока proj_Z, где proj_Z определяется следующим образом:

proj_Z = (currentBlockNumber & ~0xff) + (Z & 0xff);
    if (proj_Z > currentBlockNumber) {
        proj_Z -= 256;
    }

И вам придется заменить Z на proj_Z при вызове функции, то есть mixGene(X, Y, proj_Z).


Обратите внимание, что proj_Z будет оставаться неизменным в определенном диапазоне блоков. К примеру, если Z&0xff = 128, то proj_Z изменяется только на каждом нулевом и 128-м блоках.

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

eyd5cxlyauklees28j70widdisg.png

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

Usage: hevm exec --code TEXT [--calldata TEXT] [--address ADDR] [--caller ADDR]
                 [--origin ADDR] [--coinbase ADDR] [--value W256] [--gas W256]
                 [--number W256] [--timestamp W256] [--gaslimit W256]
                 [--gasprice W256] [--difficulty W256] [--debug]
                 [--state STRING]
Available options:
  -h,--help


Выше приведены опции запуска. Утилита позволяет указывать самые разные параметры. Среди них есть --debug, который и дает вам возможность дебага в интерактивном режиме.

Итак, вот мы сделали несколько обращений к развернутому на блокчейне основной сети контракту geneScience и записали результаты. Далее воспользовались hevm для запуска нашего ломанного байткода с данными, подготовленными с учетом описанных выше правил и…

Результаты совпали!

Глава последняя: заключение и продолжение работы (?)


Итак, чего нам удалось добиться?

Используя наш хак-софт, вы можете со 100% вероятность предсказать 256-битный ген новорожденного котенка, если он рождается в диапазоне блоков [coolDownEndBlock (когда малыш готов появиться), текущий блок+256 (примерно)]. Вы можете рассуждать об этом следующим образом: когда малыш находится в утробе кошки-матери, его гены со временем подвергаются мутации, из-за источника энтропии в виде хэша прогнозируемого блока coolDownEndBlock, который также меняется с течением времени. Поэтому вы можете воспользоваться этой программой для проверки того, как будет выглядеть ген малыша, если бы он родился прямо сейчас. И если этот ген вам не нравится, вы можете подождать еще примерно 256 блоков (в среднем), и проверить новый ген.

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

Что можно улучшить и какие здесь есть нюансы?

Мы быстро пробежались по изменениям, которые происходят в стеке в реальной логической части смарт контракта (label 25 и все, что после него) и мы полагаем, что эта предсказуемая часть кода mixGene вполне подлежит разбору и изучению. Мы надеемся, что хэш блока как фактор мутации также несет в себе некоторое физическое значение, помогая, например, определить, какой ген следует подвергать мутации. Если нам удастся с этим разобраться, мы получим исходный ген, без мутаций. Это полезно, поскольку если у вас нет хорошего исходного гена, то даже самой хорошей мутации может оказаться недостаточно.

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

И в целом нам вполне понятно намерение команды разработчиков CryptoKitties стабилизировать мутацию на протяжении короткого временного промежутка. Но обратная сторона такого подхода заключается в возможности произвести анализ наподобие сделанного нами.

Также мы бы хотели поблагодарить замечательное ethereum-комьюнити за разработку таких инструментов, как Etherscan, hevm, evmdis, truffle, testrpc, myetherwallet и Solidity. Это очень классное сообщество и мы рады быть его частью.

И, наконец, измененный код https://github.com/modong/GeneScienceCracked/

Не забудьте изменить $CONSTBLOCKHASH$ на хэш прогнозируемого блока.

image

© Geektimes