Мы определяем схему кодификации состояний детерминированного конечного автомата (ДКА) [1]. В отличие от обычной практики, сама кодификация является машиночитаемой, то есть с ней связан алгоритм, который может динамически определять состояние машины. Такая кодификация хорошо подходит для распределенной реализации конечного автомата, например реализации блокчейна, описанной в [2, 3]. Купонная облигация будет использоваться в качестве примера использования технологии через бумагу.
Фон
DFA [1] - это математическая модель вычислений, задуманная как абстрактная машина, которая может находиться в одном из конечного набора состояний и может переходить из одного состояния в другое. (переход) при возникновении инициирующего события или условия. Его вычислительные возможности больше, чем у комбинационной логики, но меньше, чем у стековой машины. Кроме того, хотя это и не является существенным для самой структуры, она может выполнять заданный набор действий при переходе из одного состояния в другое.
При обычном подходе к такой машине состояния определяются статически (априори) и представляют некоторую конкретную конфигурацию системы или имеют какое-то конкретное значение, например, им может быть дан набор или имена, они могут быть связаны с набором тегов. , или с набором неизрасходованных выходных транзакций (UTXO), как предложено в [3] для DFA на основе блокчейна. Этого достаточно, чтобы система работала, поскольку само вычисление (выход) определяется тем, как система перемещается между состояниями, пока она принимает цепочку входов.
В этом смысле DFA (т. Е. Наборы состояний, переходов и т. Д.) Не уникальны, и два DFA могут быть эквивалентными, т. Е. Давать одинаковые выходные данные для каждой заданной цепочки входов, даже если возможно, что интерпретация a априори задуманные для состояний очень разные (скажем, они развернуты на разных физических машинах или задуманы для решения разных проблем). Это также естественным образом приводит к концепции минимизации DFA [4].
Хотя статического определения (маркировки) состояний достаточно для абстрактного функционирования самого конечного автомата и достаточно для многих задач, в которых важен только результат вычисления, бывают случаи, в которых значение самих состояний практическое значение и не может быть выведено из тегов состояний, например, потому что он намеренно скрыт по соображениям конфиденциальности или конфиденциальности. Примером этого является система, описанная в [2], в которой вычисления распределяются и выполняются агентами, которые (намеренно) не имеют полной информации о системе. В этом случае необходимо динамическое определение состояния системы.
Основное изобретение в этой статье - схема кодификации, которая позволяет динамическое (на лету) определение состояния DFA, например (но не исключительно) состояний, связанных с (распределенным) исполнением контракта, как описано в [2]. Для описания и иллюстрации схемы кодификации мы будем использовать в качестве примеров купонную облигацию и бессрочный, хотя изобретение никоим образом не ограничивается этими примерами.
Купонная облигация - это долговое обязательство с периодической выплатой процентов (купонов), которое держатель получает с момента выпуска контракта до его погашения, когда в дополнение к последнему купону выплачивается также основная сумма облигации. В последней части статьи мы также рассмотрим бессрочный период, то есть бесконечный поток платежей, то есть купонные выплаты продолжаются (в принципе) вечно. На практике, из-за эффекта (положительного) начисления процентов, в какой-то момент сумма купонов не имеет практического значения, так что (дисконтированная) стоимость контракта конечна.
Простая спецификация
DFA состоит из конечных наборов {S, I, t, s0, F}, представляющих соответственно возможные состояния (S), входы (I), переходы (t), начальное состояние (s0) и конечное состояние (F), также называется принимающим состоянием. Кроме того, можно определить набор действий (a) , которые представляют побочные эффекты выполнения и не определяют результат вычисления.
Для описания и иллюстрации нашей схемы кодификации мы рассмотрим 3-периодную купонную облигацию. Элементы (и обозначения) DFA, которые мы будем рассматривать для такого контракта, могут быть (статически) определены, как указано в таблицах 1–3. Обратите внимание, что начальное состояние определяется S в наших обозначениях, а принимающие состояния - F0 и F1.
После определения этих элементов функционирование системы может быть полностью определено [5] с помощью так называемой таблицы переходов состояний, в которой текущее (начальное / исходное) состояние системы ( строки) вместе с соответствующими входными данными (столбцами) определяют в соответствии с таблицей следующее (конечное / до-) состояние системы, а также действия, которые должны выполняться параллельно с переходом; для нашего примера это приведено в Таблице 4. Обратите внимание, что выполнение понимается как начало в начальном состоянии (S), и единственными возможными конечными (принимающими) состояниями являются F0 и F1. Поскольку эти состояния отмечают завершение выполнения, т.е. с ними не связан переход, их можно не указывать в строках таблицы. Альтернативный формат таблицы переходов приведен в таблице.
Другой (эквивалентный) способ определения функционирования конечного автомата - это так называемая диаграмма состояний [6], в которой состояния системы представлены каплями, вход и действия - прикрепленными метками, а переходы представлены соединительными стрелками; для нашего примера это показано на рисунке 1. Обратите внимание, что конечные (принимающие) состояния F0 и F1 по соглашению обозначены двойной линией для большого двоичного объекта. Для простоты, поскольку они не имеют отношения к работе системы, действия не показаны на этой диаграмме. Значение пунктирной рамки (повторяющиеся состояния) будет пояснено ниже.
Как указано в разделе "Предпосылки", хотя это и не является строго необходимым для функционирования абстрактного DFA, динамическое определение состояния системы, которое может быть прочитано как человеком, так и компьютером, может быть практической необходимостью и составляет основное изобретение, описанное в этой статье. Каждое состояние характеризуется уникальным набором условий, которые либо возникают, либо не возникают, либо не имеют отношения к конкретному состоянию. Каждое условие должно быть чем-то явным и проверяемым, т. Е. Существует определенный (вычислительный) способ определить, наступает ли условие или нет.
В нашем примере это может быть достигнуто с помощью набора условий, представленных в таблице 5, в которой тестируемые состояния указаны в строках, а определенные нами условия - в столбцах. Каждое условие t указывает, наступила ли конкретная дата (например, условие, обозначенное t0, означает t ›t0), и каждое условие ci (или p) определяет, был ли произведен соответствующий платеж. Обратите внимание, что выплата купонов (или основной суммы), срок погашения которых еще не наступил, не имеет значения для состояний, наступивших до наступления соответствующих сроков погашения.
Конечно, используется ли этот или эквивалентный набор условий, не имеет значения, если они однозначно определяют все возможные состояния, то есть цепочка истинных, ложных или нерелевантных значений для каждого состояния уникальна. Также обратите внимание, что хотя в этом примере мы рассмотрели только двоичные (True или False) или нерелевантные условия, в принципе они могут принимать несколько значений. Вдобавок, помимо рассмотренных здесь атомарных условий, каждое условие может, в свою очередь, представлять составное состояние, состоящее из нескольких (под) условий по очереди. Все эти варианты тривиальны по своей природе и также должны рассматриваться как охватываемые настоящим изобретением.
Последний момент, о котором следует подумать, - это значение пунктирной рамки на рисунке 1. Хотя в нынешнем виде диаграмма вполне верна и должна правильно описывать динамику купонной облигации, обратите внимание, что есть интригующее сходство между состояниями Ti и состояниями Ci; то есть они очень похожи по смыслу, отличаются только номером периода времени или купона, к которому они относятся (i). Следовательно, они также могут быть представлены обычным повторяющимся или повторяющимся состоянием, а также дополнительной информацией, указывающей, к какому купону / периоду они относятся. Это может быть естественно распространено на государства с неограниченным повторением, открывая тем самым возможность для кодификации бессрочной жизни. Определение схемы кодификации с такими повторяющимися состояниями будет рассмотрено в следующем разделе ниже.
Спецификация с повторяющимися состояниями
Как упоминалось ранее, некоторые подмножества состояний DFA купонной облигации из последнего раздела или купонной облигации (состояния Ti и Di) соответствуют очень похожим интерпретациям состояния конечного автомата, отличаясь только количеством моментов времени. период или купон, к которому они относятся (i); т.е. в определенном смысле их можно рассматривать как состояние, которое повторяется несколько раз (скажем, от i = 1 до заданного imax, в нашем случае imax = 3). Учитывая это, имеет смысл упростить представление DFA, включив все эти состояния в повторяющееся состояние (R), которое будет обрабатываться отдельно. С таким упрощением мы представляем ниже список состояний контракта (Таблица 6), таблицу переходов состояний (Таблица 7), эквивалентную диаграмму состояний (Рисунок 2) и таблицу определения состояний (Таблица 8) DFA для нашего примера купона. связь; обратите внимание, что другие элементы DFA (входы и действия) не меняются по сравнению с предыдущим разделом.
Конечно, все это просто скрывает сложности динамики облигаций внутри повторяющегося состояния, которое необходимо указывать отдельно. Однако это упрощение может быть важным в случае сложных конечных автоматов. Очевидная аналогия - введение циклов в языки программирования. Само повторяющееся состояние также определяется как конечный автомат, однако обратите внимание, что начальное и принимающее состояния заменяются в этом контексте входом и точками выхода, поскольку выполнение абстрактного вычисление не предназначено для начала или завершения внутри повторяющегося состояния. Ниже представлен список состояний контракта (Таблица 8), таблица переходов состояний (Таблица 9) и диаграмма состояний (Рисунок 3) для повторяющегося состояния.
Новизной этого подхода является введение индекса (i), который отслеживает, сколько раз состояния были заняты. Увеличение этого индекса и аналогичных величин (например, общая сумма выплаченных денег) может быть рассчитано либо извне (как показано ниже для схемы кодификации), либо достигнуто дополнительными действиями DFA, как указано в таблице 9 для состояния C. Также обратите внимание, что входные данные (алфавит) для внутренних состояний этого повторяющегося состояния могут потенциально зависеть от внутреннего индекса (i) и / или подобных величин. Как объяснялось ранее, возможные принимающие состояния системы были заменены точками выхода. Соответствующая эквивалентная диаграмма состояний представлена на рисунке 3.
Схема кодификации для такого повторяющегося состояния при расширении выглядела бы очень похожей на соответствующие части таблицы 5. Однако, поскольку дух этого подхода не в том, чтобы расширять и рассматривать каждое внутреннее (под-) состояние по отдельности, он кажется более правильным. Естественно, нет, чтобы представить это явно в таблице. Вместо этого мы представляем на рисунке 4 псевдокод для алгоритма, который будет назначать правильные значения (True или False) для переменных, связанных с условиями кодификации конечного автомата. Разумеется, переменным, связанным с нерелевантными условиями, не нужно присваивать какое-либо значение. На рисунке 4, как и в таблице 5 выше, каждое условие ti указывает, наступила ли конкретная дата (то есть ti = T означает t ≥ ti), и каждое условие ci указывает, был ли выплачен соответствующий (i-й) купон.
Последний момент, который необходимо решить, - это необходимость в точке завершения, представленной индексом imax. Хотя обычные купонные облигации действительно имеют конечный срок погашения, бессрочный - это аналогичные инструменты, которые (в принципе) действуют вечно. С нашей кодификацией повторяющегося состояния это может быть достигнуто простой модификацией псевдокода, как показано на рисунке 5. Обратите внимание, что в этом случае цикл while завершится, когда он встретит первый период, срок погашения которого еще не достигнут. переменные не имеют значения, и в этот момент все состояния однозначно определяются схемой кодификации, т. е. существует комбинация истинных и ложных значений, уникальная для каждого состояния.
Спецификация с повторяющимися состояниями
Самое интересное, что мы начали патентовать эти идеи до того, как люди подумали, что это возможно на Биткойне. Таким образом, многие существующие проекты, банки и т. Д. Будут размещены на BCH. Это развлечение интеллектуальной собственности, вы не можете просто делать то, что делаете, не платя изобретателям.
использованная литература
[1] https://en.wikipedia.org/wiki/Deterministic_finite_automaton.
[2] nCrypt, Реализация конечных автоматов, WP0307 (2016).
[3] nCrypt, Детерминированные конечные автоматы на основе цепочки блоков, WP0032 (2016).
[4] https://en.wikipedia.org/wiki/DFA_minimization
