SOCKS proxy chains

SOCKS proxy chains

Upcoming. This page describes the socks-proxy branch. It is not part of a release, 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 the one chain it writes on. How groups, chains and exits are derived 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 exit feed, 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; when the clock steps back it keeps the last timestamp, as a feed refuses time that runs backwards.

Entries

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

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
88	16	Session fingerprint
104	1	Kind
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

Kind	Code	Payload
JOIN	1	Defined, never written
LEAVE	2	Defined, never written
OPEN	3	A session's request to its exit
ACCEPT	4	The exit's answer
SEALED	5	One sealed message of a session

The payloads of OPEN, ACCEPT and SEALED are on SOCKS proxy implementation.

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), 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, 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 last, and a failure is NOT_AUTHENTIC. An AHEAD entry waits for the missing ones; a NEXT entry is ACCEPTED, and appends with it whatever waited behind it and now links.

Only SEALED entries wait for room: a sealed entry that would take the chain past chainCapacityBytes is refused FULL, while OPEN and ACCEPT are taken all the same, so sessions can open and close on a full chain. 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. An entry that takes the chain over capacity pushes out the oldest entries, and 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.

Gaps and trimming

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, and the Gap it reports names the writer, the skipped sequence numbers and the fingerprints of the entries that waited. At either end, a session whose peer is that writer and whose fingerprint the gap names closes BROKEN.

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/0.0.5 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: a FrameDecoder limited to 8 MiB, the ping stages, the chain codecs and handlers, and UnclaimedFrameHandler, which drops frames of any other type.

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 the writer (32 bytes), the sequence number (u64) and the hash (u64), and a writer named twice among the heads of a packet fails it.

Packet	Id	Payload
JOIN_CHAIN	4000	Request id (u64), writer (32), has chain (u8), chain id (32) when it has one
JOIN_REPLY	4010	Request id (u64), status (u8); when JOINED, chain id (32), n (u16), n heads
CHAIN_ENTRY	4020	n (u16), then n times entry length (u32) and entry; each entry names its chain
CHAIN_HEADS	4030	Chain id (32), n (u16), n heads
FETCH_ENTRIES	4040	Chain id (32), n (u16), n times writer (32), from (u64) and to (u64)
ENTRY_REFUSED	4050	Chain id (32), writer (32), sequence number (u64), admission (u8)
LEAVE_CHAIN	4060	Chain id (32), writer (32)

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.

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 takes no writes, is over its join budget or already holds 4 writers (MAX_WRITERS_PER_STREAM), and for a chain that has clientsPerChain clients or has taken 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; the other refusals are silent. A node's own entries go in through post, are drained on a thread of their own and are not told to its listeners.

Following

A client node keeps a replica of the chain it joined through ChainHost.follow, 4 chains at most 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, sends the retained entries from the refused sequence number on to every stream again, places what waited and reports whether it can write. Members that have the entries drop them as duplicates. Any answer but ACCEPTED, AHEAD, DUPLICATE, REPLAYED or FULL ends the outbox, and its owner starts a new writer: a client joins again, and an exit closes the sessions of the old feed 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 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/Chain.java: admission, the buffer, trimming and gaps
• proxy/src/main/java/org/unigrid/hedgehog/proxy/chain/Feed.java, FeedWriter.java, Link.java, Admission.java: feeds and their answers
• proxy/src/main/java/org/unigrid/hedgehog/proxy/chain/Entry.java, EntryCodec.java, EntryKind.java, FnvJ64.java: entries and their bytes
• proxy/src/main/java/org/unigrid/hedgehog/proxy/chain/WriterKey.java, WriterId.java: writers
• proxy/src/main/java/org/unigrid/hedgehog/proxy/chain/HeadsDiff.java, Gap.java: reconcile and gaps
• application/src/main/java/org/unigrid/hedgehog/service/chain/ChainHost.java, HostedChain.java, Hosting.java: hosting, joins, intake, flooding, following and reconcile
• application/src/main/java/org/unigrid/hedgehog/service/chain/ChainOutbox.java, WriterPauses.java, StreamBudgets.java: posting, pauses and budgets
• application/src/main/java/org/unigrid/hedgehog/model/network/codec/ChainCodecs.java and the packet codecs beside it: the chain packets
• application/src/main/java/org/unigrid/hedgehog/model/network/initializer/StreamRouter.java, ChainStreamInitializer.java: stream 4