Моделирование с метками времени
В заключение этого подраздела приводится свойство некоторого RAM-моделирования, которое будет необходимо для решения задачи доказуемой защиты программ. Это свойство требует, чтобы при восстановлении значения из ячеек памяти, ЦП «знал бы» сколько раз содержимое этих ячеек модифицировалось. То есть, для данного адреса МП
a и общего числа команд (обозначаемого j), выполненных ЦП, общее число команд «запомнить в ячейку a» может быть эффективно вычислено алгоритмом Q(j,a). Далее рассматривается только моделирование детерминированных RAM-машин.
Определение 5.12. Для данной оракульной машины RAM'k'
и машины RAMk предположим, что оракульная RAM'k'
с доступом к оракулу f' моделирует вычисления RAM'k'. Тогда моделирование является моделированием с метками времени, если существует O(k')-временной алгоритм Q(·,·) такой, что выполняется следующее условие. Пусть (i,a,v) – j-тое сообщение, посланное CPU'k' (в процессе повторных выполнений RAM'k'). Тогда, число предыдущих сообщений формы («запомнить»,a,·), посланных CPU'k', равняется точно (j,a).
Далее отметим, что алгоритм Q(j,a) может вычислить любую версию обращения ЦП
к ячейке памяти а в раунде j. Обозначим номер такой версии как версия(a).
Таким образом, чтобы «знать» номер версии любого адреса в некоторый момент времени, достаточно для ЦП сохранить счет числа шагов, которые выполняются. Подчеркнем, что ЦП не мог бы позволить себе хранить номер версии всех адресов памяти, так что проставление меток времени важно только для получения доказуемой защиты программ от вмешательства.
