Plinko Protocol Visualization

Single-Server PIR with Sublinear Online Time via Invertible PRFs

Key Innovation: Plinko achieves O(1) hint updates after database changes using invertible PRFs (iPRFs). The client can find all affected hints in constant time without scanning.

1. Protocol Overview

Plinko is a Private Information Retrieval (PIR) scheme that allows a client to query a database without revealing which entry they're accessing.

Key Components

Component	Purpose	Complexity
HintInit	Offline preprocessing - stream database to compute hints	O(n)
Query/Answer	Single query round trip	O(n/w)
UpdateHint	Update hints after database change	O(1)

Parameters

n = database size (bits)

w = block size

c = n/w (number of blocks)

lambda = security parameter

2. PMNS: Pseudorandom Multinomial Sampler

Named after the Plinko game! Simulates throwing n balls into m bins using a binary tree. At each peg, the ball bounces left or right based on a PRF-derived probability.

Key Property: Both forward (ball -> bin) and inverse (bin -> balls) operations run in O(log m) time by traversing the binary tree of pegs.

Balls Dropped

Last Bin

Distribution

Rows: 8

Algorithm: trace_ball (Forward)

def trace_ball(x, n, m):
    low, high = 0, m - 1  # bin range
    ball_count = n
    while low < high:  # descend tree
        mid = (low + high) // 2
        p = (mid - low + 1) / (high - low + 1)  # left probability
        left_count = binomial_sample(ball_count, p, PRF(node))
        if x < left_count:  # go LEFT
            high = mid
            ball_count = left_count
        else:  # go RIGHT
            x -= left_count
            low = mid + 1
            ball_count -= left_count
    return low  # final bin

3. SwapOrNot: Small-Domain PRP

A pseudorandom permutation for small domains based on Morris-Rogaway 2013.

Key Insight: Each round is an involution (self-inverse). Inversion simply runs rounds in reverse order.

Domain [0, N):

Round 0 / 6

Input X: 3

Single Round

def swap_or_not_round(x, round_key, round):
    partner = (round_key - x) mod N
    canonical = max(x, partner)
    if PRF(round, canonical) == 1:
        return partner  # swap
    return x  # no swap

4. iPRF: Invertible Pseudorandom Function

Combines SwapOrNot PRP with PMNS to create an invertible PRF.

Forward: iF.F(k, x) = S(k_pmns, P(k_prp, x))
Inverse: iF.F^-1(k, y) = {P^-1(k_prp, z) : z in S^-1(k_pmns, y)}

Input

x = 5

SwapOrNot PRP

P(x) = ?

PMNS

S(P(x)) = ?

Output

y = ?

Inverse: Finding all preimages of y

Input

y = ?

PMNS^-1

S^-1(y) = {...}

PRP^-1

{P^-1(z) : z in ...}

Preimages

{...}

x: 5

5. HintInit: Offline Hint Generation

The client streams the entire database once to initialize hints. Each database entry is mapped to O(1) hints using iPRF inversion.

Hint Types

Regular Hints (H): (P_j, p_j) - subset of c/2+1 blocks + parity

Backup Hints (T): (B_j, l_j, r_j) - subset of c/2 blocks + two parities

Database Stream

Regular Hints (lambda*w slots)

Backup Hints (q slots)

HintInit Algorithm

# Generate keys and initialize hints
for i in 1..c:
    K[i] = iF.Gen(1^lambda)
for j in 1..lambda*w:
    H[j] = (random_subset(c/2+1), 0)
for j in 1..q:
    T[j] = (random_subset(c/2), 0, 0)
# Stream database entries
for i in 0..n:
    d = stream(D[i])
    (block, offset) = (i / w, i mod w)
    for j in iF.F^-1(K[block], offset):  # O(1) hints!
        if j < lambda*w:
            if block in H[j].P:
                H[j].parity ^= d
        else:
            if block in T[j].B:
                T[j].parity_in ^= d
            else:
                T[j].parity_out ^= d

6. Complexity Summary

Operation	Time	Communication	Notes
HintInit	O(n)	O(n)	One-time offline, streaming
Query (client)	O(1)	O(c) = O(n/w)	Find hint via iPRF^-1
Answer (server)	O(n/w)	O(B)	Compute parities
UpdateHint	O(1)	O(log n)	iPRF^-1 finds affected hints
Client Storage	O(lambda*w + q) hints		Plus c iPRF keys

Why O(1) Updates Matter: Previous PIR schemes required O(n) or O(sqrt(n)) time to update hints after database changes. Plinko's iPRF inversion finds all O(1) affected hints directly, making it practical for dynamic databases like Ethereum state.