Il y a 1Â j
At RobertoFest today, celebrating Roberto Tamassiaâs 40 years of contributions to authenticated data structures (and more!)
Updates incoming!đ
Michael Goodrich, showing us how people felt about his and Robertoâs algorithms books:
Before this, @chbpap showcasing how Robertoâs classic work on persistent authenticated dictionaries powers modern blockchains like @ethereum.
(Wait till I tell you about Verkle trees came fromâŠ)
@chbpap @ethereum Giuseppe Di Battista, telling everyone about how they used this new thing called âthe internetâ to submit an academic paper because it was too late to mail the printed copy.
(HotCRP was not invented yet đ)
@chbpap @ethereum Ioannis Tollis, reminding us what slides looked like in 1986 đ
Question from the audience: âWhat font was that?â đ
@chbpap @ethereum The nicest thing about research is the people! â€ïž
@chbpap @ethereum @chbpap, as a young PhD student!
@chbpap @ethereum Itâs important to set your academic life priorities straight!
@chbpap @ethereum Trees I never heard about beforeâŠ
@chbpap @ethereum
@chbpap @ethereum Seize the night (to work on graph algorithms and authenticated data structures)
@chbpap @ethereum Panel of ex-PhD students of Roberto.
@chbpap @ethereum @motiyung telling us about his peculiar research habitsâŠ
@chbpap @ethereum @motiyung âŠand about the time he met Roberto: when the two had to merge their two submissions into one.
@chbpap @ethereum @motiyung Apparently, one of their co-authors, Jeff Westbrook, is one of the writers of The Simpsons! đ€Ż
Thatâs why you see so much math in the show (like P != NP)
@chbpap @ethereum @motiyung Anna Lysyanskaya, telling us about the EUDI regulation (scary) and how anonymous credentials would help give much needed privacy to the initial, heavily-flawed EU proposal!
@chbpap @ethereum @motiyung (I had to take a break from posting: the talks were very engaging. And there was a special feeling in the air: everyone who gave a talk did so from the bottom of their heart, recounting memories, showing pictures and sometimes sneaking in a bit of technical content.)
@chbpap @ethereum @motiyung @ElaineRShi, starting her talk.
@chbpap @ethereum @motiyung @ElaineRShi Elaine told us about Robertoâs work on ORAMs.
(This external memory model kept coming up throughout the talks. May want to look into it!)
@chbpap @ethereum @motiyung @ElaineRShi 1. Papamanthou-Shi-Tamassia (PST) commitments: the first (AFAIK) _multivariate_ polynomial commitment scheme!
@chbpap @ethereum @motiyung @ElaineRShi One of my favorite things about this scheme is how its decomposition lemma yields a PCS opening proof.
@chbpap @ethereum @motiyung @ElaineRShi (Read more about it at , to be updated soon!)
@chbpap @ethereum @motiyung @ElaineRShi 2. Accumulation trees (a.k.a., Verkle trees)
@chbpap @ethereum @motiyung @ElaineRShi Accumulation trees are just k-ary Merkle trees where the hash function is a cryptographic accumulators (e.g., RSA or bilinear )
They were designed to authenticate sets.
Verkle trees are a small variation introduced in [Kusz18].
@chbpap @ethereum @motiyung @ElaineRShi [Kusz18]: Verkle Trees, John Kuszmaul, 2018,
But, really, the Verkle paradigm of k-ary prefix Merkle trees where the hash function is a vector commitment first appeared in [LY10; Sec. 4], although in the context of building ZK sets.
@chbpap @ethereum @motiyung @ElaineRShi [LY10] Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs; by Libert, BenoĂźt and Yung, Moti; in TCC'10; 2010
@chbpap @ethereum @motiyung @ElaineRShi 3. Generalized hash trees (or Herkle trees: )
A Merkle tree with nice "homomorphic" properties, very useful for stateless validation.
@chbpap @ethereum @motiyung @ElaineRShi In [PSTY13], Roberto and his co-authors give a lattice-based Herkle tree from the Ajtai hash function.
(â ïž The figure below is an over-simplification!)
@chbpap @ethereum @motiyung @ElaineRShi [PSTY13] Streaming Authenticated Data Structures; by Papamanthou, Charalampos and Shi, Elaine and Tamassia, Roberto and Yi, Ke; in EUROCRYPT 2013;
Unfortunately, this [PSTY13] Herkle has some scalability changes: while the tree depth is unbounded, the homomorphism is bounded.
@chbpap @ethereum @motiyung @ElaineRShi This means the homomorphic operation can only be applied a fixed number of time, determined at setup time of the scheme.
Plus, the more operations you want, the less efficient the scheme gets.
This is kind of annoying: we'd like *efficient*, unbounded homomorphism!
@chbpap @ethereum @motiyung @ElaineRShi (There are other Herkle trees like AMTs and Hyperpoofs , they just switch the problem around: they have unbounded homomorphism but bounded depth. Still annoying.)
What a great research problem! I urge everyone to try to solve it.
@chbpap @ethereum @motiyung @ElaineRShi (There are other Herkle trees: AMTs and Hyperpoofs . But they just switch the issue around: they have unbounded homomorphism but bounded depth. Still annoying.)
What a great research problem! I urge everyone to try to solve it.
@chbpap @ethereum @motiyung @ElaineRShi Alright: enough about trees from people who are obsessed with them.
Time for Roberto's closing remarks!
These started with an explanation of how he used adversarial machine learning (poisoning attacks) to evade his motherâs supervision and escape to the open road on his đČ đ
@chbpap @ethereum @motiyung @ElaineRShi The trick was to â(mis)habituateâ his mother to believe that, whenever he takes the bicycle for a ride on the small road in front of his house, he will always return quickly while remaining in sight.
Until one day, he found an opportunity, and he instead went straight for the đŁïž
@chbpap @ethereum @motiyung @ElaineRShi Robertoâs first car, which actually had âBrownâ written on it, even though you cannot see it in this picture, almost foretelling where Roberto would spend most of his academic life: Brown University
@chbpap @ethereum @motiyung @ElaineRShi The night ended with a dinner, where people continued to tell jokes and stories.
@chbpap @ethereum @motiyung @ElaineRShi Mike Goodrich telling us what Robertoâs key teaching is: âalways optimize travel,â
@chbpap @ethereum @motiyung @ElaineRShi What a wonderful night this was! â€ïž
4,11Â k
34
Le contenu de cette page est fourni par des tiers. Sauf indication contraire, OKX nâest pas lâauteur du ou des articles citĂ©s et ne revendique aucun droit dâauteur sur le contenu. Le contenu est fourni Ă titre dâinformation uniquement et ne reprĂ©sente pas les opinions dâOKX. Il ne sâagit pas dâune approbation de quelque nature que ce soit et ne doit pas ĂȘtre considĂ©rĂ© comme un conseil en investissement ou une sollicitation dâachat ou de vente dâactifs numĂ©riques. Dans la mesure oĂč lâIA gĂ©nĂ©rative est utilisĂ©e pour fournir des rĂ©sumĂ©s ou dâautres informations, ce contenu gĂ©nĂ©rĂ© par IA peut ĂȘtre inexact ou incohĂ©rent. Veuillez lire lâarticle associĂ© pour obtenir davantage de dĂ©tails et dâinformations. OKX nâest pas responsable du contenu hĂ©bergĂ© sur des sites tiers. La dĂ©tention dâactifs numĂ©riques, y compris les stablecoins et les NFT, implique un niveau de risque Ă©levĂ© et leur valeur peut considĂ©rablement fluctuer. Examinez soigneusement votre situation financiĂšre pour dĂ©terminer si le trading ou la dĂ©tention dâactifs numĂ©riques vous convient.