(talk) authenticated data structures for stateless validation

2022-08-11 ยท 2 min read

    Video: https://www.youtube.com/watch?v=TuZiEb_SLx0 Author: https://alinush.github.io/papers.html

    why #

    1. Merkle Trees can't do some things efficiently
      • Succinctness
      • Proof and digest updates
      • Proof aggregation
    2. These are needed in new applications
      • Transparency logs (e.g., x509 Certificate Transparency)
      • Stateless validation (e.g., sharded eth, eth light clients)
    3. These things are possible with new techniques
      • Polynomial commitments
      • Hidden-order groups (e.g. RSA)

    cert transparency #

    example #

    • CA gets compromised and issues bad cert for high-value domain like google.com.

    • Instead of preventing the problem (basically impossible), just detect bad CAs and remove them from browser/OS trust roots after the fact (when they're detected).

    • Client gets an extra CT inclusion proof alongside normal cert chain. Client only accepts cert if it's included in a global transparency log.

    • Services (e.g., google.com) also then monitor the global transparency logs for their certs.

    • Transparency logs return complete inclusion proof (i.e., proves google.com certs returned is complete and not missing any).

    • If service finds a bad cert, maybe one they didn't request, then they can ban the bad CA from the browser/CA trust roots.

    • existing merkle accumulator can't easily guarantee completeness b/c the certs are appended in chronological order. log auditors then have to download the entire tree to check for bad certs.

    • new bilinear accumulator and RSA-based accumulator allow for both lookup proof and append-only proof size in log n

    • caveat: slightly worse append time and bilinear accum has many public params

    • these more sophisticated accumulators (bilinear or RSA) allow for O(1) disjointness and subset proofs.

    • perf: append-only proof: 7 KB, lookup proof: 40-120 KB, reduce communication: 10x-100x

    • perf: 1 append/sec :0

    • future work: confident we can go from $4 \lambda$ to $2 \lambda$ to $\log n$ tree depth