Есть, предположительно, огромный массив (или что-то более структурированное, например btree), из однотипных элементов (но могущих быть разного размера в байтах). У этого списка надо организовать криптографическую проверку целостности с помощью хэша, но с дополнительным условием: при вставке/удалении/замене элемента откуда-то из середины надо чтобы не требовалось заново пробегать по каждому из элементов и пересчитывать его.
(этот абзац для задачи не важен, просто информация для интереса) Использоваться будет для хранения огромных директорий в формате btree в системе контроля версий, чтобы с одной стороны хэш не зависел от того, как распределены ноды по дереву, а с другой - чтобы при замене одного файла не требовалось подгружать все ноды с диска и считать заново хэш по ним.
Придумал вроде бы несложное решение, но хочется посоветоваться с кем-нить на предмет его возможных проблем. То есть, не будет ли это решение понижать криптографическую надёжность хэша в каком-нить аспекте (в первую очередь - давать возможность подменить исходные данные при сохранении того же хэша).
Предлагаемая схема. Берём некий уже готовый традиционный криптохэш, считающийся надёжным по условию извне задачи. Этим хэшом хэшируем каждый элемент списка отдельно. Итоговый хэш списка считаем как степенной ряд с хэшами элементов в качестве коэфициентов:
hash(item[0..N-1]) = hash(item[0]) + hash(item[1]) * k + hash(item[2]) * pow(k,2) + ... + hash(item[N-1]) * pow(k,N-1)где k - некое большое простое число, разрядностью равной или чуть меньше разрядности базовой хэш-функции, N - количество элементов списка, item[] - массив элементов, pow() - функция возведения в степень большой разрядности, hash() - базовая хэш-функция. Вся арифметика считается по модулю разрядности хэша, разумеется.
Очевидный, условно, недостаток: если у нас есть два хэша, отличающихся на один элемент, и известно в каком именно индексе этот элемент расположен - то вычислить его содержимое будет заметно проще, чем при монолитном сквозном хэше всего массива (особенно просто, если этот элемент занимает всего несколько байт). Но конкретно этот аспект в данном случае не учитываем, ищем что-то другое.
И ещё вопрос: если базовая хэш-функция уже обладает какими-то недостатками, но ещё не проявляющимися на практике (т.е. отдалённо-теоретическими), может ли её использование в указанной выше схеме обострить значимость этих недостатков и сделать их практически эксплуатируемыми?
И ещё вопрос: а если k имеет заметно меньшую разрядность чем базовая хэш-функция, это чему-то навредит?
