No RobertoFest hoje, a celebrar os 40 anos de contribuições de Roberto Tamassia às estruturas de dados autenticadas (e mais!) Atualizações a caminho!👇

Michael Goodrich, mostrando-nos como as pessoas se sentiram sobre os livros de algoritmos dele e de Roberto:

Antes disso, @chbpap a mostrar como o trabalho clássico de Roberto sobre dicionários autenticados persistentes alimenta blockchains modernas como a @ethereum. (Espera até eu te contar de onde vieram as árvores Verkle…)

@chbpap @ethereum Giuseppe Di Battista, contando a todos como usaram esta nova coisa chamada "internet" para submeter um artigo académico porque já era tarde demais para enviar a cópia impressa. (O HotCRP ainda não tinha sido inventado 😄)

@chbpap @ethereum Ioannis Tollis, lembrando-nos como eram os slides em 1986 👌 Pergunta da audiência: “Que fonte era essa?” 😅

@chbpap @ethereum A coisa mais bonita sobre a pesquisa são as pessoas! ❤️

@chbpap @ethereum @chbpap, como um jovem estudante de doutoramento!

@chbpap @ethereum É importante definir corretamente as suas prioridades na vida acadêmica!

@chbpap @ethereum Árvores que nunca ouvi falar antes…

@chbpap @ethereum

@chbpap @ethereum Aproveite a noite (para trabalhar em algoritmos de grafos e estruturas de dados autenticadas)

@chbpap @ethereum Painel de ex-alunos de doutoramento do Roberto.

@chbpap @ethereum @motiyung a contar-nos sobre os seus hábitos de pesquisa peculiares…

@chbpap @ethereum @motiyung …e sobre a vez em que conheceu o Roberto: quando os dois tiveram que fundir as suas duas submissões em uma.

@chbpap @ethereum @motiyung Aparentemente, um dos seus co-autores, Jeff Westbrook, é um dos escritores dos Simpsons! 🤯 É por isso que você vê tanta matemática no programa (como P != NP)

@chbpap @ethereum @motiyung Anna Lysyanskaya, a falar-nos sobre a regulamentação EUDI (assustadora) e como credenciais anónimas ajudariam a proporcionar a privacidade tão necessária à proposta inicial da UE, que está cheia de falhas!

@chbpap @ethereum @motiyung (Tive que fazer uma pausa nas postagens: as palestras foram muito envolventes. E havia uma sensação especial no ar: todos que deram uma palestra o fizeram de coração, recontando memórias, mostrando fotos e às vezes inserindo um pouco de conteúdo técnico.)

@chbpap @ethereum @motiyung @ElaineRShi, a começar a sua palestra.

@chbpap @ethereum @motiyung @ElaineRShi A Elaine falou-nos sobre o trabalho do Roberto em ORAMs. (Este modelo de memória externa continuou a surgir ao longo das palestras. Pode querer investigar isso!)

@chbpap @ethereum @motiyung @ElaineRShi 1. Compromissos Papamanthou-Shi-Tamassia (PST): o primeiro (pelo que sei) esquema de compromisso polinomial _multivariado_!

@chbpap @ethereum @motiyung @ElaineRShi Uma das minhas coisas favoritas sobre este esquema é como o seu lema de decomposição gera uma prova de abertura de PCS.

@chbpap @ethereum @motiyung @ElaineRShi (Leia mais sobre isso em , a ser atualizado em breve!)

@chbpap @ethereum @motiyung @ElaineRShi 2. Árvores de acumulação (também conhecidas como árvores Verkle)

@chbpap @ethereum @motiyung @ElaineRShi As árvores de acumulação são apenas árvores de Merkle k-árias onde a função hash é um acumulador criptográfico (por exemplo, RSA ou bilinear) Elas foram projetadas para autenticar conjuntos. As árvores Verkle são uma pequena variação introduzida em [Kusz18].

@chbpap @ethereum @motiyung @ElaineRShi [Kusz18]: Verkle Trees, John Kuszmaul, 2018, Mas, na verdade, o paradigma Verkle de árvores Merkle prefixadas k-árias, onde a função hash é um compromisso vetorial, apareceu pela primeira vez em [LY10; Sec. 4], embora no contexto da construção de conjuntos ZK.

@chbpap @ethereum @motiyung @ElaineRShi [LY10] Compromissos Vetoriais Mercuriais Concisos e Conjuntos Independentes de Conhecimento Zero com Provas Curtas; por Libert, Benoît e Yung, Moti; em TCC'10; 2010

@chbpap @ethereum @motiyung @ElaineRShi 3. Árvores de hash generalizadas (ou árvores de Herkle: ) Uma árvore de Merkle com boas propriedades "homomórficas", muito útil para validação sem estado.

@chbpap @ethereum @motiyung @ElaineRShi Em [PSTY13], Roberto e seus co-autores apresentam uma árvore Herkle baseada em rede a partir da função de hash Ajtai. (⚠️ A figura abaixo é uma simplificação excessiva!)

@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] Estruturas de Dados Autenticadas em Streaming; por Papamanthou, Charalampos e Shi, Elaine e Tamassia, Roberto e Yi, Ke; na EUROCRYPT 2013; Infelizmente, este [PSTY13] Herkle tem algumas mudanças de escalabilidade: enquanto a profundidade da árvore é ilimitada, o homomorfismo é limitado.

@chbpap @ethereum @motiyung @ElaineRShi Isso significa que a operação homomórfica só pode ser aplicada um número fixo de vezes, determinado no momento da configuração do esquema. Além disso, quanto mais operações você quiser, menos eficiente o esquema se torna. Isso é meio irritante: gostaríamos de um homomorfismo *eficiente* e sem limites!

@chbpap @ethereum @motiyung @ElaineRShi (Existem outras árvores Herkle como AMTs e Hyperpoofs, que apenas mudam o problema: elas têm homomorfismo não limitado, mas profundidade limitada. Ainda assim, é irritante.) Que grande problema de pesquisa! Eu insto todos a tentarem resolvê-lo.

@chbpap @ethereum @motiyung @ElaineRShi (Existem outras árvores Herkle: AMTs e Hyperpoofs. Mas elas apenas mudam a questão: têm homomorfismo não limitado, mas profundidade limitada. Ainda assim, é irritante.) Que grande problema de pesquisa! Eu insto todos a tentarem resolvê-lo.

@chbpap @ethereum @motiyung @ElaineRShi Muito bem: chega de falar sobre árvores de pessoas que são obcecadas por elas. É hora das considerações finais do Roberto! Isto começou com uma explicação de como ele usou aprendizado de máquina adversarial (ataques de envenenamento) para evitar a supervisão da mãe e escapar para a estrada aberta na sua 🚲 😆

@chbpap @ethereum @motiyung @ElaineRShi O truque foi "(des)habituar" a mãe dele a acreditar que, sempre que ele pega a bicicleta para dar uma volta na pequena estrada em frente à sua casa, ele sempre voltará rapidamente enquanto permanece à vista. Até que um dia, ele encontrou uma oportunidade e, em vez disso, foi direto para a 🛣️

@chbpap @ethereum @motiyung @ElaineRShi O primeiro carro de Roberto, que na verdade tinha "Brown" escrito nele, embora você não possa ver isso nesta foto, quase prevendo onde Roberto passaria a maior parte de sua vida acadêmica: Brown University

@chbpap @ethereum @motiyung @ElaineRShi A noite terminou com um jantar, onde as pessoas continuaram a contar piadas e histórias.

@chbpap @ethereum @motiyung @ElaineRShi Mike Goodrich a dizer-nos qual é o principal ensinamento de Roberto: "otimize sempre a viagem,"

@chbpap @ethereum @motiyung @ElaineRShi Que noite maravilhosa foi esta! ❤️