LL
скорее всего такого нет потому что если было бы, то его давно бы притащили в криптовалюты вместо меркл-три
Такого нет по простой причине: конечное количество информации не может однозначно определять бесконечное множество :/
Size: a a a
2020 July 07
@
ну вот да. какие-то такие ощущения
KP
Подскажите по дереву Меркла или другому алгоритму позволяющему узнать наличие ключа в цепочке, с фиксированной длиной коренного ключа. Можно ли обновить коренной ключ динамически, не зная всех нод и проверить наличие ключа в цепочке
Как пример:
У Алиса есть два ключа, она высчитывает коренной ключ из них.
Как пример:
У Алиса есть два ключа, она высчитывает коренной ключ из них.
Node1Hash + Node2Hash => RootHashAliceПередает коренной ключ Бобу. Тот добавляет в цепочку свой ключ и формирует новый коренной
RootHashAlice + Node3Hash => RootHashBobВ системе также есть Ева, которая знает только RootHashBob и Node1Hash. И хочет проверить входит ли Node1Hash в цепочку RootHashBob
Это можно сделать на классических деревьях Меркла; для вычисления нового корня не нужно ничего, кроме proof of nonexistence (то есть цепочки из парных частичных хешей по пути до самой близкой к искомой ячейке) ключа в текущем дереве
KP
Дальше просто заменяем один узел, и каскадно обновляем хеши снизу вверх, до корневого (потому что в каждой паре один из двух частичных хешей надо будет обновлять, начиная с хеша от нашего нового элемента)
KP
скорее всего такого нет потому что если было бы, то его давно бы притащили в криптовалюты вместо меркл-три
А это ровно дерево Меркла и есть (если я правильно понял проблему), и в криптовалютах используется именно оно и именно поэтому.
Никто естественно не перехеширует все элементы ради обновления одного, это было бы O(N²) на обновление вместо O(logN)
Никто естественно не перехеширует все элементы ради обновления одного, это было бы O(N²) на обновление вместо O(logN)
@
не очень понятно конечно что хотел спросить автор. я так понял что ему важна проверка существования листа в корне без проверки цепочки
@
тоесть описание вопроса об одном, а пример об другом
KP
не очень понятно конечно что хотел спросить автор. я так понял что ему важна проверка существования листа в корне без проверки цепочки
Мне показалось, что @co_in достаточно, чтобы узлы не знали всех элементов, а знали постоянно только корень фиксированной длины (и на лету ещё оперировали бы пруфами логарифмической длины, которые им генерирует кто-то другой, и которые после окончания операции можно выбросить).
Это ровно дерево Меркла.
Но я действительно не очень внимательно прочитал
Это ровно дерево Меркла.
Но я действительно не очень внимательно прочитал
CI
Пропробую уточнить на еще одном примере
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
KP
Пропробую уточнить на еще одном примере
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
Тебе нужен пруф того, что hello на данный момент не входит ы цепочку
KP
Его тебе рассчитает кто-то, у кого есть полные данные
KP
Имея этот пруф (2logN хешей) ты сможешь рассчитать новый хеш корня
KP
Всех остальных значений ключа, которые участвовали в изначальном хеша корня, тебе знать не надо
KP
Но кому-то в сети — надо; теорию информации не наебёшь
CI
Но кому-то в сети — надо; теорию информации не наебёшь
(((
KP
(((
И ты не можешь, зная только корневой хеш, проверить вхождение произвольного элемента.
Но ты можешь удостовериться, что кто-то другой (у кого есть все ключи, или по крайней мере все ключи на этой ветке дерева) не пиздит тебе, что такой ключ есть
Но ты можешь удостовериться, что кто-то другой (у кого есть все ключи, или по крайней мере все ключи на этой ветке дерева) не пиздит тебе, что такой ключ есть
KP
Собственно, все фичи дерева Меркла
YB
Пропробую уточнить на еще одном примере
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
Мне передали хеш цепочки допустим 69bf145f9328e02df695c610006809c944ff0beefa5cf14c3b1ab1680e652bb7. Я не знаю из каких значений он сформировался
Я хочу добавить к цепочке значение Hello, в результате получается другой хеш вроде
7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873
Теперь я скидываю хеш 7c2aff231d94b5647263e27bfeb447103677e2281bc12d5a533f92946e2dc873 в этот чат. И по этому хешу пользователи могу проверить участвовало ли значение Amigo например в его формировании. При этом не зная всех значений участвовавших в формировании хеша
Мне б такой архиватор
CI
И ты не можешь, зная только корневой хеш, проверить вхождение произвольного элемента.
Но ты можешь удостовериться, что кто-то другой (у кого есть все ключи, или по крайней мере все ключи на этой ветке дерева) не пиздит тебе, что такой ключ есть
Но ты можешь удостовериться, что кто-то другой (у кого есть все ключи, или по крайней мере все ключи на этой ветке дерева) не пиздит тебе, что такой ключ есть
Ну вот я не сильно понял как я могу удостовериться. К примеру мобильный кошелёк крипты какой-то загружает заголовки блоков, в которых хранится корневой хеш транзакций. Как мобильный кошелёк, может проверить пиздит ли ему полная нода или нет отдавшая этот заголовок, о том что транзакция входит в это дерево? Нужно запросить у полной ноды всю ветку с этой транзакцией. И потом самому пройдясь снизу вверх можно получить пруф. Верно?
@
он в итерактивном режиме запрашивает у полной ноды путь