SOCKS proxy chains

Upcoming. This page describes master. The proxy is not part of a release yet, and details may change.

Part of SOCKS proxy. A chain is the shared, append-only log in memory through which a client node and its exits talk. The members of a shard group host the chains of their group, flood new entries to each other and reconcile what they missed; a client node keeps a replica of each chain it writes on. How groups, chains and exits are chosen and how sessions use the entries is on SOCKS proxy implementation.

Chains and writers

A chain merges append-only feeds, one per writer. A writer is an Ed25519 key made fresh for every client attachment and for every session of an exit, and its public key is the writer id. WriterId.verify refuses a key that is not a point of prime order. An entry names its chain, its writer, its sequence number and the hash of the writer’s previous entry, and it is signed over its body and its hash.

A writer orders only its own entries, so a chain cannot fork. Chain orders all entries by timestamp, then writer, then sequence number. FeedWriter signs a writer’s entries in order and stamps them in whole seconds, the clock rounded down, so within a second the stamps tell nothing of how far apart two writers are. When the clock steps back it keeps the last stamp, as a feed refuses time that runs backwards. writeLast signs the last entry of a feed, after which the writer signs nothing more.

Entries

An entry is Entry.OVERHEAD, 181 bytes, plus its payload of n bytes, big-endian throughout. The header is Entry.HEADER_SIZE, 109 bytes.

Offset	Size	Field
0	32	Chain id
32	32	Writer id, an Ed25519 public key
64	8	Sequence number, never negative
72	8	Hash of the writer’s previous entry
80	8	Timestamp, milliseconds since 1970, a whole number of seconds
88	16	Tag
104	1	Marks: 0x01 is the end mark of the last entry of a feed; any other bit makes the entry invalid
105	4	Payload length n
109	n	Payload
109 + n	8	Hash: FNVJ64 of bytes 0 to 108 + n
117 + n	64	Ed25519 signature over bytes 0 to 116 + n

Nothing in the clear says what an entry carries. The tag names its session for the two ends alone, and the payload is an opening, an answer or one sealed message, see SOCKS proxy implementation. The hash and the signature cover the end mark.

Size classes. An entry, its overhead included, is 1024 bytes, 4096 bytes or maxEntryBytes long, each class only where it does not exceed maxEntryBytes (SizeClasses). An opening, an answer and a short message fill the smallest class, so the size of an entry does not tell them apart.

FNVJ64

FnvJ64 is the FNVJ64 hash that greenrobot essentials dropped. It starts from the FNV-1a offset basis 0xcbf29ce484222325 and uses the FNV prime 0x100000001b3, but each round multiplies the state by the prime first and then XORs in eight bytes at once, read as a big-endian word, the last word padded with zeros. The value is the final state times the prime, XOR the length in bytes, times the prime once more. The hash is fast and not collision resistant, so the signature covers the body itself and not only the hash.

Admission

Chain.offer first trims the chain and then refuses, in this order, an entry for another chain (WRONG_CHAIN), one larger than maxEntryBytes (TOO_LARGE), one whose size is no size class or whose timestamp is no whole second (MALFORMED), and one whose timestamp is more than the retention window ahead of the local clock (FUTURE) or behind it (EXPIRED). The writer’s feed then judges the link:

Link	When
NEXT	The next sequence number, with the head’s hash as previous hash and a timestamp no older than the head’s
AHEAD	Past the next sequence number
DUPLICATE	The head itself, seen again
REPLAYED	Below the head
BROKEN	At the next sequence number or the head but not linked to it, time running back, past the last entry of a feed that ended, or the sequence number 2⁶³ − 1, which nothing can follow
FOREIGN	Signed by another writer

DUPLICATE and REPLAYED are answered as such, BROKEN and FOREIGN as BROKEN, without checking the signature, since entries a chain already has arrive over and over. The signature is checked next, and a failure is NOT_AUTHENTIC. Then an AHEAD entry waits for the missing ones, and a NEXT entry is ACCEPTED and appends with it whatever waited behind it and now links, unless either finds no room.

An entry that would take the chain past chainCapacityBytes is refused FULL. An entry of the smallest class may also take a reserve of max(smallest class, capacity / 16) beyond the capacity, so a chain full of larger entries still lets sessions open, answer and close. Entries past a gap wait in a buffer of max(maxEntryBytes, capacity / 4) bytes, and one that does not fit it is refused FULL too. Entries released from the buffer are not checked again: past the room, the oldest larger entries go until the larger ones fit the capacity, then the oldest of all until everything fits the capacity and the reserve. Every feed keeps its head. A feed may also start after a head that a member named, through Chain.anchor; the first entry after such a head is not held to the head’s timestamp, which the feed never saw, and a head with the end mark starts the feed ended.

Gaps, trimming and ended feeds

Once a second Chain.trim drops the entries older than the retention window, and expireGaps gives up on a gap whose first waiting entry has aged past it, since every member has trimmed the missing entries by then. The feed skips past the entries that waited, or ends at the first of them that carries the end mark, and the Gap it reports names the writer, the skipped sequence numbers and the tags of the entries that waited. A client session whose exit is that writer closes BROKEN, as the exit writes each session as a writer of its own; at the exit, a session whose client is that writer closes so only when it looks out for one of those tags.

In the same second the host forgets every feed whose last entry carries the end mark and is older than the retention window: its head and what the chain kept of it go, and its writer’s place comes free. Whatever the writer signed is refused EXPIRED from then on. A feed that did not end is never forgotten, however long it was quiet.

Chain packets

Chain traffic has a QUIC stream of its own, so it never holds up the main stream. Only between peers that agreed on hedgehog-proxy/0.0.2 or hedgehog-ledger/0.0.2, which only nodes run with --preview offer, does the client of a connection open it after the main stream, with a PING, which makes its id Network.CHAIN_STREAM_ID, 4. StreamRouter gives that stream its own pipeline (ChainPipeline.streamHandlers): FrameDecoder.forChainStream(), the ping stages, the chain codecs and handlers, and UnclaimedFrameHandler. That decoder has a size table of its own: it takes frames of at most 8 MiB, header included, and only the ping and the chain packets, each within the size its fields allow. The decoder of the main stream has no chain packets in its table and refuses them.

The packets use the frame header of the Peer-to-peer network protocol. A packet holds at most 64 entries of at most 1 MiB each, or 4096 heads or ranges. A head is 57 bytes: the writer (32), the sequence number (u64), the hash (u64), the timestamp of the entry (u64) and its marks (u8). A writer named twice among the heads of a packet fails it.

Packet	Id	Payload
JOIN_CHAIN	5000	Request id (u64), writer (32), has chain (u8), chain id (32) when it has one
JOIN_REPLY	5010	Request id (u64), status (u8); when JOINED, chain id (32), n (u16), n heads
CHAIN_ENTRY	5020	n (u16), then n times entry length (u32) and entry; each entry names its chain
CHAIN_HEADS	5030	Chain id (32), n (u16), n heads
FETCH_ENTRIES	5040	Chain id (32), n (u16), n times writer (32), from (u64) and to (u64)
ENTRY_REFUSED	5050	Chain id (32), writer (32), sequence number (u64), admission (u8)
LEAVE_CHAIN	5060	Chain id (32), writer (32)
CHAIN_STEM	5070	As CHAIN_ENTRY: entries passed on before any member floods them, see The stem

Status and admission bytes are enum ordinals. A status is JOINED 0, FULL 1, DISABLED 2, UNKNOWN_CHAIN 3 or ERROR 4; no node sends ERROR, and an unknown byte reads as it. An admission is the ordinal of Admission, in which FULL is 10 and MALFORMED 11.

Joins and intake

Joins. ChainHost.join answers DISABLED while the proxy is off and UNKNOWN_CHAIN when the request names a chain that is not a current chain of the member. It answers FULL for a stream that is over its join budget or already holds 4 writers (MAX_WRITERS_PER_STREAM), and for a chain that has clientsPerChain clients or holds 4096 writers (HostedChain.MAX_WRITERS). A request without a chain id is placed on the chain the writer is attached to, else on the one with the fewest clients, the lowest index among equals. The reply carries the chain’s heads, and a chain with more heads than one packet holds takes no client. A stream that takes no writes is sent no reply, and the request times out.

A writer keeps the live stream it attached through: another stream that names it is refused while that stream lives, and the unsigned LEAVE_CHAIN is believed only from it. When the stream closes, its writers are detached.

Intake. A member stream may relay any writer’s entries, a client stream only its own writer’s; other entries are dropped before anything is verified. receive offers a packet’s entries under the chain’s delivery lock and queues what was appended, at most 4096 deliveries. Beyond that a delivery is dropped, its entries staying in the chain but not flooded, and the log is warned when the queue fills. One thread at a time drains the queue with no lock held: it floods the entries to every member stream and attached client except the one they came from, skipping streams that are closed or take no writes, and then tells ClientSessions and ChainExit. An entry refused FULL is answered with ENTRY_REFUSED while the stream takes writes; the other refusals are silent. A client node’s own entries go in through post, are drained on a thread of their own and are not told to its listeners; an exit’s go out on the stem through postStem.

Following

A client node keeps a replica of each chain it joined through ChainHost.follow, 8 chains at most, twice its 4 attachments so that the chains of an ended epoch can drain, and none it hosts itself. The replica is anchored at the heads of the join replies, less the node’s own writer. It takes entries from the member streams it follows the chain through, floods none of them on, and posts the node’s own entries on every one of those streams. It is forgotten when the last of them closes.

Refusals

A FULL refusal from a member of the chain’s group, or from a stream the chain is followed through, pauses the writer in WriterPauses at the lowest refused sequence number; the latest 1024 pauses are kept. ChainOutbox posts a writer’s entries in order, and one that the local replica has no room for waits with everything after it, the writer paused at its sequence number.

Once a second the outbox lifts the pause and places what waited. A client’s outbox first sends the retained entries from the refused sequence number on to every stream again, and members that have them drop them as duplicates. An exit’s outbox sends nothing again, as the stem moved the refused entries on when the refusal came. Any answer but ACCEPTED, AHEAD, DUPLICATE, REPLAYED or FULL ends the outbox: a client then joins again with a new writer, and an exit closes the session of that writer BROKEN.

Reconcile

Once a second each current chain of a member that has any feed sends its heads to one random member stream that is open and takes writes. The receiving member answers with a FETCH_ENTRIES for what HeadsDiff.missing finds: per writer it lags on and can take, the next 64 entries after its own head, at most 8 ranges, starting at a random place in the list when there are more. The peer serves them oldest first, up to one 8 MiB frame, as CHAIN_ENTRY packets. Only members are answered, and only while their stream takes writes.

Nothing is adopted from a peer’s heads: a feed the chain has not seen starts at its first entry, and if that is gone the entries after it wait until the gap expires. A client never reconciles, so a flood it missed stays lost until the gap expires.

Stream budgets

StreamBudgets limits what one stream may ask of a host in a window of one second. A join over the budget is answered FULL; the other requests are dropped. The window opens with the first request after the last one closed, so a stream can use up to twice its budget across the turn from one window to the next.

Budget	Per second
Joins	8
Entries to verify, counted per CHAIN_ENTRY or CHAIN_STEM packet before any is verified	4096
CHAIN_HEADS packets	16
Ranges served	64
Bytes of fetched entries	32 MiB

In the source

• proxy/src/main/java/org/unigrid/hedgehog/proxy/chain/: chains, feeds, entries, size classes, admission, reconcile and gaps
• application/src/main/java/org/unigrid/hedgehog/service/chain/: hosting, joins, intake, flooding, the stem, following, reconcile, posting, pauses and budgets
• application/src/main/java/org/unigrid/hedgehog/model/network/: the chain packets and their codecs
• application/src/main/java/org/unigrid/hedgehog/transport/: in handler the handlers of the chain packets, and in initializer the pipeline of stream 4 (ChainPipeline, ChainStreamInitializer)