search

braid-org / braid-spec

Working area for Braid extensions to HTTP
https://braid.org
233 stars 16 forks source link

Server should indicate rebase mode #92

Closed josephg closed 1 year ago

josephg commented 3 years ago

Spec says:

2.4.  GET a specific version
...

   A server MAY refactor or rebase the version history that it provides
   to a client, so long as it does not affect the resulting state, or
   the result of the patch-type's merges.

It seems like there's 2 modes the server can operate in:

  1. Rebase mode, where every patch coming from a subscription is linearized and can be applied by the client with no merging
  2. DAG mode, where the client is responsible for modelling the time dag and merging when appropriate

I think we should make this choice more explicit, and add a header or something to name which mode the server is in here.

mitar commented 3 years ago

Great point!

toomim commented 3 years ago

I believe these can be distinguished by the presence of a merge-type. In case (1), there is no merging, and thus you do not need to specify a merge-type. In case (2), there is merging, and so each peer must implement the specified merge-type.

Perhaps it would help to articulate these examples explicitly in the spec? Or is there some other distinction beyond merge-type that you want articulated here?

toomim commented 3 years ago

Ah, I just discovered some relevant motivation from Seph in an email thread:

telling the client which model the server is working in... has some implications for what data the client needs to store. (And it has some implications for crypto - because cryptographic signatures won't survive a rebase)

Thank you for adding these use-cases — it's so helpful to know what problem you are trying to solve when I am helping to design the solution.

Problems

I think I understand the first problem. The client needs to know how much history it needs to store in order to merge new versions from the server. In the "rebase" case (which if I'm not mistaken could be restated as the "single-writer" case), the client doesn't need to store any history.

However, I don't understand the second problem, please articulate the "crypto" scenario. Are you imagining a merkle-dag of versions? Or is this about signing individual versions?

Solutions

For the first problem, the existence of merge-type should be enough for the client to know whether to store history or not. So I don't think we try to find consensus on a rebase mode flag yet.

brynbellomy commented 3 years ago

However, I don't understand the second problem, please articulate the "crypto" scenario. Are you imagining a merkle-dag of versions? Or is this about signing individual versions?

Yeah, this has come up in my thinking about Redwood as well, which uses a merkle-dag of signed versions. The only solutions I've been able to come up with that satisfy my requirements around decentralization seem horribly overengineered (a Byzantine fault tolerant consensus algorithm, threshold signatures, etc.), so I haven't made a lot of progress on this front.

The least complex solution would probably be some sort of turn-taking algorithm that allows individual actors in the network to behave like centralized servers. The "leader" of any given round would have permission to rebase old history. Just a thought.

josephg commented 3 years ago

Thank you for adding these use-cases — it's so helpful to know what problem you are trying to solve when I am helping to design the solution.

To me the most pressing use case is that braid needs to support both OT and CRDTs. Sharedb's client code depends on the server linearizing all operations - which means the client doesn't need any local history and doesn't need to query history at all in order for the concurrency system to work correctly. The server also doesn't need to send any of a document's history when a client connects. The current state of the document is enough.

The problem I'm trying to solve is, how does a general purpose braid client know its allowed to make those assumptions when it connects to a server?

For crypto I'm imagining an implementation which signs patches in some form. OT's transform will change the bytes in a patch, so if I send a patch + signature to the server and the server modifies the patch, my signature won't match any more. I think if you want a fully distributed system, you also want to use CRDTs. And that neatly solves the signature problem too because the operations never have to be transformed or anything before being broadcast. (So you can attach & verify the signature as-is)

josephg commented 3 years ago

@toomim So your proposal here is:

Is that right?

Hm - initially I thought that was a bad idea, but the more I think about it the more I think it might be a reasonable solution. That would work fine for OT, but I don't think it would work well for OT + message signing. But the latter might be obscure enough not to worry about it.

toomim commented 1 year ago

Closing this issue; discussion of subscription parameters is moving to https://github.com/braid-org/braid-spec/issues/123.