En RobertoFest hoy, celebrando los 40 años de contribuciones de Roberto Tamassia a las estructuras de datos autenticadas (¡y más!) ¡Actualizaciones en camino!👇

Michael Goodrich, mostrándonos cómo se sentían las personas acerca de sus libros de algoritmos junto a Roberto:

Antes de esto, @chbpap mostró cómo el trabajo clásico de Roberto sobre diccionarios autenticados persistentes impulsa las blockchains modernas como @ethereum. (Espera a que te cuente de dónde vienen los árboles Verkle…)

@chbpap @ethereum Giuseppe Di Battista, contando a todos cómo utilizaron esta nueva cosa llamada "internet" para enviar un artículo académico porque era demasiado tarde para enviar la copia impresa por correo. (HotCRP aún no se había inventado 😄)

@chbpap @ethereum Ioannis Tollis, recordándonos cómo eran las diapositivas en 1986 👌 Pregunta del público: “¿Qué fuente era esa?” 😅

¡Lo más bonito de la investigación son las personas! ❤️

@chbpap @ethereum @chbpap, ¡como un joven estudiante de doctorado!

¡Es importante establecer bien tus prioridades en la vida académica!

@chbpap @ethereum Árboles de los que nunca había oído hablar antes…

@chbpap @ethereum

@chbpap @ethereum Aprovecha la noche (para trabajar en algoritmos de grafos y estructuras de datos autenticadas)

@chbpap @ethereum Panel de ex-estudiantes de doctorado de Roberto.

@chbpap @ethereum @motiyung contándonos sobre sus peculiares hábitos de investigación…

@chbpap @ethereum @motiyung …y sobre el momento en que conoció a Roberto: cuando los dos tuvieron que fusionar sus dos presentaciones en una sola.

@chbpap @ethereum @motiyung Aparentemente, uno de sus coautores, Jeff Westbrook, ¡es uno de los guionistas de Los Simpson! 🤯 ¡Por eso ves tanta matemática en el programa (como P != NP)

@chbpap @ethereum @motiyung Anna Lysyanskaya, contándonos sobre la regulación EUDI (da miedo) y cómo las credenciales anónimas ayudarían a proporcionar la privacidad tan necesaria a la propuesta inicial de la UE, que está muy defectuosa!

@chbpap @ethereum @motiyung (Tuve que tomar un descanso de publicar: las charlas fueron muy interesantes. Y había una sensación especial en el aire: todos los que dieron una charla lo hicieron desde el fondo de su corazón, recordando memorias, mostrando fotos y a veces colando un poco de contenido técnico.)

@chbpap @ethereum @motiyung @ElaineRShi, comenzando su charla.

@chbpap @ethereum @motiyung @ElaineRShi Elaine nos habló sobre el trabajo de Roberto en ORAMs. (¡Este modelo de memoria externa seguía apareciendo a lo largo de las charlas. Puede que quieras investigarlo!)

@chbpap @ethereum @motiyung @ElaineRShi 1. Compromisos de Papamanthou-Shi-Tamassia (PST): ¡el primer esquema de compromiso polinómico _multivariado_ (hasta donde sé)!

@chbpap @ethereum @motiyung @ElaineRShi Una de mis cosas favoritas sobre este esquema es cómo su lema de descomposición produce una prueba de apertura de PCS.

@chbpap @ethereum @motiyung @ElaineRShi (¡Lee más sobre esto en , se actualizará pronto!)

@chbpap @ethereum @motiyung @ElaineRShi 2. Árboles de acumulación (también conocidos como árboles Verkle)

@chbpap @ethereum @motiyung @ElaineRShi Los árboles de acumulación son simplemente árboles de Merkle k-arios donde la función hash es un acumulador criptográfico (por ejemplo, RSA o bilineal). Fueron diseñados para autenticar conjuntos. Los árboles Verkle son una pequeña variación introducida en [Kusz18].

@chbpap @ethereum @motiyung @ElaineRShi [Kusz18]: Verkle Trees, John Kuszmaul, 2018, Pero, en realidad, el paradigma Verkle de árboles Merkle de prefijo k-ario donde la función hash es un compromiso vectorial apareció por primera vez en [LY10; Sec. 4], aunque en el contexto de la construcción de conjuntos ZK.

@chbpap @ethereum @motiyung @ElaineRShi [LY10] Compromisos vectoriales mercuriales concisos y conjuntos de conocimiento cero independientes con pruebas cortas; por Libert, Benoît y Yung, Moti; en TCC'10; 2010

@chbpap @ethereum @motiyung @ElaineRShi 3. Árboles hash generalizados (o árboles Herkle: ) Un árbol Merkle con agradables propiedades "homomórficas", muy útil para la validación sin estado.

@chbpap @ethereum @motiyung @ElaineRShi En [PSTY13], Roberto y sus coautores presentan un árbol Herkle basado en retículas a partir de la función hash de Ajtai. (⚠️ ¡La figura a continuación es una sobre-simplificación!)

@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] Estructuras de Datos Autenticadas en Streaming; por Papamanthou, Charalampos y Shi, Elaine y Tamassia, Roberto y Yi, Ke; en EUROCRYPT 2013; Desafortunadamente, este [PSTY13] Herkle tiene algunos cambios de escalabilidad: mientras que la profundidad del árbol es ilimitada, el homomorfismo está limitado.

@chbpap @ethereum @motiyung @ElaineRShi Esto significa que la operación homomórfica solo se puede aplicar un número fijo de veces, determinado en el momento de la configuración del esquema. Además, cuanto más operaciones quieras, menos eficiente se vuelve el esquema. Esto es un poco molesto: ¡nos gustaría un homomorfismo *eficiente* y sin límites!

@chbpap @ethereum @motiyung @ElaineRShi (Hay otros árboles Herkle como AMTs y Hyperpoofs, solo que cambian el problema: tienen homomorfismo ilimitado pero profundidad limitada. Sigue siendo molesto.) ¡Qué gran problema de investigación! Insto a todos a intentar resolverlo.

@chbpap @ethereum @motiyung @ElaineRShi (Hay otros árboles Herkle: AMTs y Hyperpoofs. Pero solo cambian el problema: tienen homomorfismo no acotado pero profundidad acotada. Aún así, es molesto.) ¡Qué gran problema de investigación! Insto a todos a intentar resolverlo.

@chbpap @ethereum @motiyung @ElaineRShi Bien: suficiente sobre los árboles de personas que están obsesionadas con ellos. ¡Es hora de las palabras finales de Roberto! Esto comenzó con una explicación de cómo utilizó el aprendizaje automático adversarial (ataques de envenenamiento) para evadir la supervisión de su madre y escapar a la carretera abierta en su 🚲 😆

@chbpap @ethereum @motiyung @ElaineRShi El truco era "(des)habituar" a su madre para que creyera que, cada vez que él toma la bicicleta para dar un paseo por la pequeña carretera frente a su casa, siempre regresará rápidamente mientras permanece a la vista. Hasta que un día, encontró una oportunidad, y en su lugar se fue directamente hacia la 🛣️

@chbpap @ethereum @motiyung @ElaineRShi El primer coche de Roberto, que en realidad tenía "Brown" escrito en él, aunque no se puede ver en esta imagen, casi presagiando dónde pasaría la mayor parte de su vida académica: la Universidad de Brown

@chbpap @ethereum @motiyung @ElaineRShi La noche terminó con una cena, donde la gente continuó contando chistes e historias.

@chbpap @ethereum @motiyung @ElaineRShi Mike Goodrich nos dice cuál es la clave de la enseñanza de Roberto: “siempre optimiza los viajes,”

@chbpap @ethereum @motiyung @ElaineRShi ¡Qué noche tan maravillosa fue esta! ❤️