1 pv sitten
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! ❤️
3,38 t.
30
Tällä sivulla näytettävä sisältö on kolmansien osapuolten tarjoamaa. Ellei toisin mainita, OKX ei ole lainatun artikkelin / lainattujen artikkelien kirjoittaja, eikä OKX väitä olevansa materiaalin tekijänoikeuksien haltija. Sisältö on tarkoitettu vain tiedoksi, eikä se edusta OKX:n näkemyksiä. Sitä ei ole tarkoitettu minkäänlaiseksi suositukseksi, eikä sitä tule pitää sijoitusneuvontana tai kehotuksena ostaa tai myydä digitaalisia varoja. Siltä osin kuin yhteenvetojen tai muiden tietojen tuottamiseen käytetään generatiivista tekoälyä, tällainen tekoälyn tuottama sisältö voi olla epätarkkaa tai epäjohdonmukaista. Lue aiheesta lisätietoa linkitetystä artikkelista. OKX ei ole vastuussa kolmansien osapuolten sivustojen sisällöstä. Digitaalisten varojen, kuten vakaakolikoiden ja NFT:iden, omistukseen liittyy suuri riski, ja niiden arvo voi vaihdella merkittävästi. Sinun tulee huolellisesti harkita, sopiiko digitaalisten varojen treidaus tai omistus sinulle taloudellisessa tilanteessasi.