Repository navigation
transport strawman ladder outline #27
Description
Activity
this should be for expositional purposes, no need to go into details, and just tor and ohttp are representative enough - one is stream based and the other datagram based and with framing both can provide async typed message bidirectional channel is enough to establish what a p2p channel is.
also ignore wire level considerations like TLV encoding, framing, message types, ... if you want to discuss we can revisit those details later and add them as an addendum to this document, but it's better if this stays abstract in regards to those details so that this document doesn't go stale
no need to review IP, UDP, TCP here - that was just context i felt you should have
honest, semi-honest and byzantine threat models, and which rungs suffice for each
no need to address at all, just the privacy taxonomy.
this layer takes care of message delivery, not view consistency, or even the communication model (synchronous, partial synchrony or async, if synchronous then any timeouts at the protocol level are more or less independent of timeouts on the transport level).
1b - can be a designated leader (participating node) or 3rd party server.
compatibility limitations of web clients (including PWAs) and how OHTTP can bridge them to other privacy overlays should be discussed as 0b i guess, and then 1b can be related to that (there's some details relating to that in the existing strawman ladder)
kvac credentials only make sense for the 3rd party server, participating peers don't need (coalition formation will have built in rate limiting and txn construction has other DoS protection).
layered trust on the ohttp side, from non-collusion through multi-path key consistency and tee attestation to onion routing, with details living in hartig
tor and nym likewise have non-collusion assumptions, they are just more robust due to longer paths and in nym's case some symmetry properties of the network structure and the loopix traffic patterns.
details of key consistency, tee attestation etc are not really relevant for this outline, at least not yet IMO.
Focus on the communication patterns required. Given p2p channels, we want all participants, even with asymmetric capabilities (e.g. some clients may be bandwidth constrained) to arrive at the same set of messages, order insensitive, in multiple epochs as efficiently as possible.
There are many tradeoffs, for example epidemic broadcast will likely win on latency but set reconcilation will win on communication complexity. There is a whole spectrum of network coding possibilities. Multiparty set reconcilation has not yet been studied as far as I'm aware (recent set reconcilation papers have focused on 2 party cases).
The same building blocks may not be applicable to both public/open broadcast (coalition formation) and private/closed group broadcast (transaction construction), or, independently of the message type, the type of peer 3rd party server vs. participating peer. even for 3rd party servers, if we assume multiple servers vs. a single server there may be large variations.
then there is the parameter range for the messages themselves. for example, segwit inputs are (mostly) safe to sign with just the prevout data, whereas legacy inputs require the full previous transaction. full nodes will be able to find prevouts in their utxo set, but other clients may expend different amounts of bandwidth resources depending on their capabilities and trust model, and for this reason it may be desirable to use on set reconcilation for this auxilirary data as well (this can be constrained a co-spend proposal txn parameter allowing exclusion or requirement of these data in broadcast). all this is mainly to say that the message count and size may also vary substantially, even for the same set of parameters.
and underlying goal of this is to help you organize your understanding of the task dependency graph relating to this:
- what is the minimum - we already know this more or less
- what is a logical sequence of improvements we can make with information already known
- what do we need to find out to make decisions about the other things
- where do we expect the pareto frontier to be, the right balance of development effort and efficiency (both bandwidth and compute/battery consumption)
there are many results in the literature on gossip, set reconciliation and network coding. we could spend a lifetime studying these... we should map out the most relevant ones and sequence them in order of decreasing simplicity.
so this document is to help you, and readers, understand the logic of these communication patterns, why they are appropriate for the protocols (coalition formation and txn construction, in particular no strong ordering requirement for messages, just set consensus) and how roughly how they work in practice
thank you @nothingmuch
preliminaries (not rungs)
- absorbs transport parts of Strawman ladder #17, sneakernet stays in proposed overview structure #21
- expositional - wire level (framing, encodings, message types) deferred to addendum
- scope: message delivery only, not view consistency or the communication model (synchrony assumptions)
- why these patterns suffice: the protocols need only set consensus, no strong ordering
- privacy taxonomy
- webrtc/iroh (honest, e2e only), tor (local passive), nym (global passive), ohttp (relay/gateway non-collusion)
- non-collusion underlies tor, nym and ohttp alike, robustness varies (tor path length; nym network symmetry + loopix traffic)
- global passive adversary defeats all but nym, and can link protocol traffic to the txn broadcast
- bitcoin p2p as running case study
- p2p channels
- async typed bidirectional message channel, confidentiality & integrity, explicit delivery semantics, no ordering or dedup
- tor (stream) and ohttp (datagram) as representative substrates - with framing both provide the same channel
- sender-anonymous vs authenticated opening
- problem: a channel connects exactly two peers
0b. web clients
- compatibility limits of web clients incl. PWAs, hardest on mobile
- ohttp as bridge to the other overlays (as in bip 77 mailboxes)
- fully connected clique
- send on every channel, static membership, shared-secret handshake
- minimum: rungs 0 + 1 (+ 1b for web clients) suffice for small static groups - later rungs add robustness (dynamic membership, partial connectivity) and efficiency
- problems: n² circuits, partial connectivity, dynamic membership, mobile peers
1b. coordinator broadcast, transport analog of the trusted coordinator
- designated leader (participating node, asymmetric burden) or 3rd party server
- per-topic grow-only message set, multi-homing (server case)
- what 0b relies on; constrained clients can opt out of relaying
- group api: post once, fetch only what's missing (linear per client)
- DoS: kvac per utxo, server case only (peers covered by protocol level protections)
- problem: coordinator trusted with liveness
- gossip
- re-send on all channels, logical message identity across transports
- discovery: bip 322 ownership proofs certify listen advertisements (endpoint metadata), themselves gossiped
- robust overlays (churn tolerance, random walk peer sampling), w/ and w/o the ohttp service, three-way interop
- overlay robustness under churn?
- bitcoin case study: inv/getdata, tx relay, addr gossip
- problems: redundant bandwidth, selective omission
- set reconciliation
- goal: all participants converge on the same message set, order insensitive, multiple epochs, asymmetric capabilities included
- sketches (erlay (https://arxiv.org/abs/1905.10518)/minisketch); partition recovery (rateless iblt, certainsync, multi-server)
- which primitive? range-based / rateless iblt / certainsync / minisketch vs kleppmann 22 bloom filters - benchmark on mobile, realistic message sizes
- tradeoffs: epidemic broadcast (latency) vs reconciliation (bandwidth); erasure coding (cubic to quadratic); network coding spectrum in between
- erasure coding payoff vs plain gossip at target scale?
- multiparty reconciliation thinly studied (mitzenmacher-pagh 18, characteristic polynomials, MCFsyn) - assumes honest parties / single epoch, none cover our setting; recent primitives are otherwise 2-party (rateless iblt has a relay extension) - open research question
- message size/count varies (legacy inputs need full prev txns, segwit just prevouts) - aux data reconciliation, constrainable per co-spend proposal
- frontier hypothesis: gossip over robust overlays + one reconciliation primitive (eager push happy path, anti-entropy sad path)? network coding and multiparty reconciliation only if measurements demand - to be validated by the benchmarks above
- problem: reconciliation under equivocation needs a hash-linked causal structure
cross-cutting
- setting matrix: open broadcast (coalition formation) / closed group (txn construction), peer / server, single / multi server
- dependency graph: known minimum (rung 1), improvement sequence (the rungs in order), research needed (the ? items), pareto frontier (hypothesis at rung 3, to be validated)
- literature mapped in decreasing simplicity
future rungs, parallel to the upper ladder
- blocklace (https://arxiv.org/abs/2402.08068) as causal gossip structure
- bft crdts (kleppmann 22 (https://martin.kleppmann.com/papers/bft-crdt-papoc22.pdf))
- reliable / consistent / atomic broadcast, BBCA?; set reconciliation + gradecast (byzantine set union consensus)
- agreement primitives over the disseminated set
hmm sneakernet can be helpful to think about here
in the preliminaries, IMO no need to say what it is not about, that's claudish
no need to discuss bitcoin p2p, i just think that would be useful for you all to review (lightning stuff too, i think bolts 1, 8, maybe 7 too though the gossip layer will be quite different it's a good basis for comparison
btw more typical name for fully connected clique that eluded me yesterday is "multicast"
0b - it is in principle possible for webrtc to also be used peer to peer, using a server only to exchange ICE messages, there is no way to have transport metadata privacy from other peers with this. if it is ok for all peers to learn the IPs of other peers, something like DC nets could also be used, which wuold still provide message anonymity within this set of peers.
since we want to support honest, semi-honest and BFT settings, this would potentially allow a limited peer to use another trusted peer to broadcast on its behalf if we add a mechanism for it. for example your node at home may support webrtc and tor, and you want to execute a coinjoin using your hardware wallet, which you do have on you, i think it would make more sense to treat the node at home as the actual user agent and provide remote RPCs for it in this particular example, but in some situations, for example imagine a group of friends that all have mobile devices but only one of them has a server at home, even if that server is not publicly reachable on the internet it could proxy from webrtc to tor for its trusted peers (the friends' mobile phones).
1b:
what 0b relies on; constrained clients can opt out of relaying
to be a bit more precise, some peers may have publicly reachable IPs and support HTTP or even OHTTP, but that would mean light clients would be trusting a participant in the transaction for their transport level privacy, or a pair of them to not collude, with no authorization mechanism, so in the BFT setting it seems like this would have to be 3rd party services.
DoS: kvac per utxo, server case only (peers covered by protocol level protections)
btw could also be in exchange for payment (lightning, cashu like https://athenut.com/) or proof of work, the main thing is to limit the data rate from both a 3rd party service's point of view and the peers' pov
erasure coding payoff vs plain gossip at target scale?
initially up to hundreds of peers in transaction construction setting, many messages per peer, small messages on the happy path, larger messages for validity proofs
but potentially many more for open gossip setting for order book/coalition formation, with few messages per peer, but potentially large-ish messages (co-spend proposals in particular)
also note that KVACs are just what i'm most familiar with, but rate limiting credentials are not just based on KVACs, see for example Bitcoin-PIR's implementation
preliminaries (not rungs)
- absorbs transport parts of Strawman ladder #17; sneakernet spec stays in proposed overview structure #21 but anchors the model here:
- the limiting case of delivery: messages are psbt fragments merging with a partial order, and delivery may take arbitrarily long
- every rung must degrade gracefully to it - conceptually, as a validation oracle: anything that breaks over sneakernet was secretly relying on timing or ordering
- expositional - wire level (framing, encodings, message types) deferred to addendum
- the ladder's contract: eventual message delivery with set convergence - the protocols need only set consensus (order insensitive), which the rungs build up to with increasing robustness and efficiency
- rungs 0-2 (p2p channels → epidemic gossip) are the near-term work and carry the most detail; rung 3 is under active investigation; future rungs are directional only
- privacy taxonomy
- webrtc/iroh (honest, e2e only), tor (local passive), nym (global passive), ohttp (relay/gateway non-collusion)
- non-collusion underlies tor, nym and ohttp alike, robustness varies (tor path length; nym network symmetry + loopix traffic)
- global passive adversary defeats all but nym, and can link protocol traffic to the txn broadcast
- target scales:
- txn construction - up to hundreds of peers, many small messages on the happy path, larger validity proofs
- open broadcast (order book / coalition formation) - potentially many more peers, few but large-ish messages (co-spend proposals in particular)
- p2p channels
- async typed bidirectional message channel, confidentiality & integrity, explicit delivery semantics, no ordering or dedup
- tor (stream) and ohttp (datagram) as representative substrates - with framing both provide the same channel
- sender-anonymous vs authenticated opening
- problem: a channel connects exactly two peers
- 0b. web clients & constrained peers
- compatibility limits of web clients incl. PWAs, hardest on mobile
- ohttp as bridge to the other overlays (as in bip 77 mailboxes)
- webrtc peer to peer (server only for ICE) - no transport metadata privacy from other peers
- if peer IPs may be mutually known (as with webrtc p2p), DC nets can still provide message anonymity within the group. opt-in trusted-peer groups only (metadata trust is never sampled), honest/semi-honest settings; composed with the delegated bridge below, the delegate is reduced to liveness trust (can censor, not deanonymize; 1-of-k deniability). see Arbitrary Length k-Anonymous Dining-Cryptographers Communication, which leaves group formation to external trust: here, the peer's own trust list. (directional)
- delegated broadcast via a trusted peer (honest/semi-honest settings):
- the home node as the actual user agent driven by remote RPC (hardware wallet case)
- or a trusted peer proxying webrtc→tor for its group (mobile-only friends + one home server)
- problem: all bridges trade privacy or trust - constrained clients rely on non-collusion (ohttp), leak IPs to peers (webrtc/DC nets), or trust a delegate
- multicast
- send on every channel, static membership, shared-secret handshake
- minimum: rungs 0 + 1 (+ 1b for web clients) suffice for small static groups
- later rungs add robustness (dynamic membership, partial connectivity) and efficiency
- problems: n² circuits, partial connectivity, dynamic membership, mobile peers
- 1b. coordinator broadcast, transport analog of the trusted coordinator
- a parallel branch, not a step toward 2. solves rung 1's problems by centralizing, and stays necessary for constrained clients
- designated leader (participating node, asymmetric burden) or 3rd party server
- a participant-hosted coordinator (public IP, http/ohttp) puts a txn participant or a non-colluding pair in charge of light clients' transport privacy with no authorization mechanism:
- acceptable in honest/semi-honest only
- in the bft setting this must be a 3rd party service
- per-topic grow-only message set, multi-homing (server case)
- what 0b relies on; constrained clients can opt out of relaying
- group api: post once, fetch only what's missing (linear per client)
- DoS (server case only, peers covered by protocol-level protections):
- anonymous rate-limiting credentials - kvac or arc (as in bitcoin-pir)
- issued per utxo, in exchange for payment (lightning, cashu e.g. athenut), or via proof of work
- the goal is bounding data rate from both the service's and the peers' pov
- problem: coordinator trusted with liveness
- gossip (epidemic broadcast)
- supersedes multicast directly, not 1b, and only gossip bridges overlays, where peers on different networks can only reach each other through a peer that speaks both
- re-send on all channels, logical message identity across transports
- push (rumor mongering) vs pull (anti-entropy) vs hybrid; fanout and round parameters govern the latency/redundancy tradeoff
- eager + lazy push (epidemic broadcast trees / plumtree over hyparview partial views, as in iroh-gossip):
- full messages over a spanning tree, ids only on the remaining links, tree repair under churn
- discovery: bip 322 ownership proofs certify listen advertisements (endpoint metadata), themselves gossiped
- robust overlays (churn tolerance, partial views / random walk peer sampling), w/ and w/o the ohttp service, three-way interop
- overlay robustness under churn?
- problems: redundant bandwidth (mitigated but not eliminated by lazy push), selective omission
- set reconciliation
- goal: all participants converge on the same message set, order insensitive, multiple epochs, asymmetric capabilities included
- sketches (erlay, minisketch)
- partition recovery (rateless iblt, certainsync, multi-server)
- which primitive?
- recursive/range-based costs log(n) round trips per peer pair - expensive over anonymous transports
- rateless (rateless iblt, certainsync) needs no rounds and no difference estimate, at the cost of coding overhead and a shared strong hash
- benchmark against minisketch and kleppmann 22 bloom filters on mobile, realistic message sizes
- tradeoffs:
- epidemic broadcast (latency) vs reconciliation (bandwidth)
- erasure coding (cubic to quadratic); network coding spectrum in between
- payoff to be evaluated at the target scales above
- multiparty reconciliation thinly studied (mitzenmacher-pagh 18, characteristic polynomials, MCFsyn) - open research question
- honest parties / single epoch only, none cover our setting
- recent primitives otherwise 2-party (rateless iblt has a relay extension)
- message size/count varies (legacy inputs need full prev txns, segwit just prevouts)
- aux data reconciliation, constrainable per co-spend proposal
- frontier hypothesis: gossip over robust overlays + one reconciliation primitive (eager push happy path, anti-entropy sad path)?
- network coding and multiparty reconciliation only if measurements demand - to be validated by the benchmarks
- problem: reconciliation under equivocation needs a hash-linked causal structure
cross-cutting
- setting matrix: open broadcast (coalition formation) / closed group (txn construction), peer / server, single / multi server
- dependency graph: known minimum (rungs 0 + 1, + 1b for web clients), improvement sequence (the rungs in order), research needed (the ? items), pareto frontier (hypothesis at rung 3, to be validated)
- literature mapped in decreasing simplicity
- how each rung is verified: conformance suite, nixos vms, convergence e2e, restart recovery
future rungs, parallel to the upper ladder
- dissemination is the single substrate of all trust settings:
- honest & semi-honest are pure gossip of psbt fragments with eventual consistency
- bft, on the wire, only adds block and validity proof message types
- blocklace (talk), kleppmann 22 as the bft extension:
- per-validator linear logs weave into a causal log for the session
- concurrent psbt state machine, validity proofs in the sad path, agreement
- validators opt in via acceptance signatures (n=1 degenerates to the coordinator, n ≥ 3f+1 for bft)
- set consensus without total ordering: union of ratified candidate blocks instead of an unpredictable coin? (cordial miners variant - liveness proof to be checked; see also byzantine set union consensus, honeybadger ACS)
- post-MVP scalability:
- blocklace as implicit reconciliation feedback (toward O(nm))
- minimal perfect hash (MPH)/seed handshake sketch of the set complement (half a round trip; xor decode for collisions, rateless fallback)
- bip 152-style compact encodings
- robustness preserved under coded dissemination (falcon-style adversarial→random omission reduction)
- f+1 / erasure-coded anonymous submission
- stronger broadcast primitives (reliable / consistent / atomic, BBCA?)
- only if the blocklace path falls short
- absorbs transport parts of Strawman ladder #17; sneakernet spec stays in proposed overview structure #21 but anchors the model here:
The 1 → 1b → 2 relationship isn't strictly sequential, right? 1b solves n²/mobile but not partial connectivity, and gossip re-solves rung 1's problems independently of 1b. 1b is just a branch, not a required step toward 2.
Reacted by CindyThe 1 → 1b → 2 relationship isn't strictly sequential, right? 1b solves n²/mobile but not partial connectivity, and gossip re-solves rung 1's problems independently of 1b. 1b is just a branch, not a required step toward 2.
thanks @0xZaddyy good point!
right, 1b is a branch, not a step toward 2, gossip supersedes multicast directly. i've reindented the outline so 0b and 1b now nest under their parent rungs, keeping the spine 0 → 1 → 2 → 3 explicit. seems better?
Okay, that makes sense. I don't really think there is any need to make it explicit like that; we just need to make it clear.
Rung 1 lists several problems, but 1b only solves the n² connections and mobile-peer problems. Could we separate the list into what 1b solves and what remains for Rung 2 to solve with gossip? Also, could the "gossip supersedes multicast directly" reasoning be folded into the outline itself, but we just need soft wording like "gossip builds on multicast directly, bypassing 1b"?
added a line to each
Could we separate the list into what 1b solves and what remains for Rung 2 to solve with gossip?
"a parallel branch, not a step toward 2. solves rung 1's problems by centralizing, and stays necessary for constrained clients"
1b solves all four. everyone talks to the coordinator instead of each other (kills n² circuits and partial connectivity), late joiners just fetch the log (dynamic membership), and constrained clients don't relay (mobile peers)
"gossip builds on multicast directly, bypassing 1b"?
"supersedes multicast directly, not 1b, and only gossip bridges overlays, where peers on different networks can only reach each other through a peer that speaks both"
1b isn't bypassed, it's the ohttp side of the bridge
this is an initial proposal for us to move forward
each rung builds broadcast from the primitives of the previous one and ends with the problem that motivates the next
preliminaries (not rungs)
1b. server broadcast, the transport analog of the upper ladder's trusted coordinator
cross-cutting
future rungs, parallel to the upper ladder
@Mshehu5 @0xZaddyy @zealsham please share your thoughts, if there's anything missing or that could be improved