Plinko PIR tutorial

Plinko is a private information retrieval protocol that lets a client read from a large database without the server learning which entry it wants, and it reduces communication and server compute from O(N) to O(√N) where N is the number of cells. The protocol is built on classic two-server PIR, whose weaknesses are the need to trust one of two servers, high communication overhead, and server work proportional to half the data per query. Plinko removes the trust assumption by using preprocessing: the client downloads the whole dataset once and keeps roughly 128·√N hints. For a workload of 10 billion 32-byte values, the article estimates the client would store about 390 MB of hints for a 100000×100000 grid, before backup hints and Merkle branches are added.