(2020) Semi-Fast Byzantine-tolerant Shared Register without Reliable Broadcast

2022-08-27 ยท 3 min read

    properties #

    • BFT shared register w/o reliable broadcast
    • leaderless
    • unauthenticated: doesn't require digital signatures
    • no reconfiguration
    • one-shot read: read from at least f+1
    • two-RTT write: (1) do read from f+1, then (2) send store request to all servers.

    core algorithm #

    • Store an (unauthenticated) tag version counter next to the register.
    • Client Writing:
      • (1) request current tag version from all servers
      • (2) determine the current honest tag $t$ to be the $(f + 1)$-th highest tag version.
        • remember that the register is unauthenticated, so byzantine servers can just return any tag version.
      • (3) send a store request with tag version $t + 1$
    • Client Reading:
      • (1) Request the current register state from all servers
      • (2) Return the value with the highest tag that was witnessed by at least $f + 1$ servers.

    client #

    client-write(S: Servers, w: Writer, v: Value):
    	1. try to get the current tag for the register, t := client-get-tag(S, w)
    	2. try to update the register, client-put-data(S, w, t, v)
    client-get-tag(S: Servers, w: Writer):
    	1. send Query-Tag(w) message to servers in S
    	2. wait for Query-Tag-Response(t, w) messages from (n - f) servers in S
    	3. return t := (f + 1)-th highest tag among responses
    client-put-data(S: Servers, w: Writer, t: Tag, v: Value):
    	1. create new tag, t' := t + 1
    	2. send Put-Data(w, t', v) to servers in S
    	3. wait for ACKs from (n - f) servers in S
    initial local client reader state:
    	t_local := 0,
    	v_local := v_0
    client-read(S: Server, r: Reader, t: Tag):
    	1. send Query-Data(r) to servers in S
    	2. wait for Query-Data-Response(r, t, v) messages from (n - f) servers in S
    	3. W := set of all (r, t, v) tuples with >= f + 1 witnesses
    	4. select tuple (t, v) from witnesses W with highest tag
    	5. if W != {} && t > t_local, then ratchet the local state tag
    	6.     (t_local, v_local) := (t, v)
    	7. return v_local

    server #

    initial local server state (per reader/writer register):
    	t_max := 0
    	v_max := v_0
    server(Query-Tag(w: Writer)):
    	1. return Query-Tag-Response(t_max, w)
    server(Put-Data(w: Writer, t: Tag, v: Value)):
    	1. if t > t_max, then ratchet local register value and ACK:
    	2.     t_max := t
    	3.     v_max := v
    	4.     send ACK response to w
    server(Query-Data(r: Reader)):
    	1. return Query-Data-Response(t_max, v_max) for Reader r