На RobertoFest сегодня отмечаем 40 лет вклада Роберто Тамассии в аутентифицированные структуры данных (и не только!) Обновления на подходе!👇

Майкл Гудрич показывает, как люди относились к его и Роберто книгам об алгоритмах:

Перед этим @chbpap демонстрирует, как классическая работа Роберто над постоянными аутентифицированными словарями поддерживает современные блокчейны, такие как @ethereum. (Подождите, пока я расскажу вам о том, откуда пришли деревья Веркла…)

@chbpap @ethereum Джузеппе Ди Баттиста рассказывает всем о том, как они использовали эту новую вещь под названием "интернет" для подачи академической статьи, потому что было слишком поздно, чтобы отправить печатную копию по почте. (HotCRP еще не был изобретен 😄)

@chbpap @ethereum Иоаннис Толлис напоминает нам, как выглядели слайды в 1986 году 👌 Вопрос из зала: "Какой это был шрифт?" 😅

@chbpap @ethereum Самое приятное в исследовании — это люди! ❤️

@chbpap @ethereum @chbpap, как молодой аспирант!

@chbpap @ethereum Важно правильно расставить приоритеты в вашей академической жизни!

@chbpap @ethereum Деревья, о которых я никогда не слышал раньше…

@chbpap @ethereum

@chbpap @ethereum Захватите ночь (чтобы поработать над графовыми алгоритмами и аутентифицированными структурами данных)

@chbpap @ethereum Панель бывших аспирантов Роберто.

@chbpap @ethereum @motiyung рассказывает нам о своих необычных привычках в исследовании…

@chbpap @ethereum @motiyung …и о том времени, когда он встретил Роберто: когда им пришлось объединить свои две заявки в одну.

@chbpap @ethereum @motiyung Видимо, один из их соавторов, Джефф Уэстбрук, является одним из сценаристов Симпсонов! 🤯 Вот почему в шоу так много математики (например, P != NP)

@chbpap @ethereum @motiyung Анна Лысянская рассказывает нам о регулировании EUDI (страшно) и о том, как анонимные учетные данные могут помочь обеспечить столь необходимую конфиденциальность первоначальному, сильно дефектному предложению ЕС!

@chbpap @ethereum @motiyung (Мне пришлось сделать перерыв в публикациях: обсуждения были очень увлекательными. И в воздухе витало особое чувство: каждый, кто выступал, делал это от всего сердца, рассказывая воспоминания, показывая фотографии и иногда вставляя немного технического контента.)

@chbpap @ethereum @motiyung @ElaineRShi, начинает свою речь.

@chbpap @ethereum @motiyung @ElaineRShi Элейн рассказала нам о работе Роберто над ORAM. (Эта модель внешней памяти постоянно упоминалась в ходе разговоров. Возможно, стоит в это углубиться!)

@chbpap @ethereum @motiyung @ElaineRShi 1. Обязательства Papamanthou-Shi-Tamassia (PST): первая (насколько я знаю) _многомерная_ схема обязательств полинома!

Одно из моих любимых вещей в этой схеме — это то, как ее лемма разложения дает доказательство открытия PCS.

@chbpap @ethereum @motiyung @ElaineRShi (Читать больше об этом на , будет обновлено скоро!)

@chbpap @ethereum @motiyung @ElaineRShi 2. Деревья накопления (также известные как Verkle деревья)

@chbpap @ethereum @motiyung @ElaineRShi Деревья накопления — это просто k-арные деревья Меркла, где хеш-функция является криптографическим аккумулятором (например, RSA или билинейный) Они были разработаны для аутентификации наборов. Деревья Веркла — это небольшая вариация, введенная в [Kusz18].

@chbpap @ethereum @motiyung @ElaineRShi [Kusz18]: Веркл-деревья, Джон Кузмаул, 2018, Но на самом деле парадигма Веркл k-арных префиксных Меркле-деревьев, где хеш-функция является векторным обязательством, впервые появилась в [LY10; Sec. 4], хотя и в контексте построения ZK множеств.

@chbpap @ethereum @motiyung @ElaineRShi [LY10] Краткие меркуриальные векторные обязательства и независимые нулевые знания с короткими доказательствами; авторы: Либерт, Бенуа и Юнг, Моти; в TCC'10; 2010

@chbpap @ethereum @motiyung @ElaineRShi 3. Обобщенные хэш-деревья (или деревья Херкла: ) Дерево Меркла с хорошими "гомоморфными" свойствами, очень полезное для безгосударственной валидации.

@chbpap @ethereum @motiyung @ElaineRShi В [PSTY13] Роберто и его соавторы представляют решеточное дерево Херкла на основе хеш-функции Аджтаи. (⚠️ Ниже приведена упрощенная схема!)

@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] Стриминг аутентифицированных структур данных; авторы: Папаманту, Харалампос и Ши, Элейн и Тамассия, Роберто и И, Ке; в EUROCRYPT 2013; К сожалению, этот [PSTY13] Herkle имеет некоторые изменения в масштабируемости: хотя глубина дерева не ограничена, гомоморфизм ограничен.

@chbpap @ethereum @motiyung @ElaineRShi Это означает, что гомоморфная операция может быть применена только фиксированное количество раз, определяемое на этапе настройки схемы. Кроме того, чем больше операций вы хотите, тем менее эффективной становится схема. Это довольно раздражает: нам хотелось бы *эффективного*, неограниченного гомоморфизма!

@chbpap @ethereum @motiyung @ElaineRShi (Существуют и другие деревья Херкла, такие как AMT и Hyperpoofs, они просто меняют задачу: у них неограниченная гомоморфность, но ограниченная глубина. Все равно раздражает.) Какой замечательный исследовательский вопрос! Призываю всех попробовать его решить.

@chbpap @ethereum @motiyung @ElaineRShi (Существуют и другие деревья Херкла: AMT и Hyperpoofs. Но они просто меняют проблему местами: у них неограниченная гомоморфность, но ограниченная глубина. Все равно раздражает.) Какой замечательный исследовательский вопрос! Призываю всех попытаться его решить.

@chbpap @ethereum @motiyung @ElaineRShi Ладно: хватит говорить о деревьях от людей, которые одержимы ими. Время для заключительных замечаний Роберто! Они начались с объяснения того, как он использовал противостоящее машинное обучение (атаки отравления), чтобы избежать контроля своей матери и сбежать на открытые дороги на своем 🚲 😆

@chbpap @ethereum @motiyung @ElaineRShi Хитрость заключалась в том, чтобы "(не)привыкнуть" его матери верить, что, когда он берет велосипед для поездки по маленькой дороге перед домом, он всегда быстро вернется, оставаясь на виду. Пока однажды он не нашел возможность и вместо этого направился прямо к 🛣️

@chbpap @ethereum @motiyung @ElaineRShi Первая машина Роберто, на которой действительно было написано "Brown", хотя вы не можете увидеть это на этой фотографии, почти предвещала, где Роберто проведет большую часть своей академической жизни: Университет Брауна

@chbpap @ethereum @motiyung @ElaineRShi Ночь закончилась ужином, где люди продолжали рассказывать шутки и истории.

@chbpap @ethereum @motiyung @ElaineRShi Майк Гудрич рассказывает нам, чему учит Роберто: "всегда оптимизируйте поездки,"

@chbpap @ethereum @motiyung @ElaineRShi Какая замечательная ночь была! ❤️