inkandswitch / inkandswitch/subduction
[bug]: transient false heads
- Dominant language
- Rust
- Stars
- 111
- Forks
- 15
- Avg merge
- 3d 1h
- Merged PRs (30d)
- 6
Description
### Preflight
- [x] I have searched existing issues and this is not a duplicate.
- [x] This is not a security vulnerability (those go to [Security Advisories](https://github.com/inkandswitch/subduction/security/advisories/new)).
### Affected crate(s)
- [ ] automerge_subduction_ingest
- [ ] automerge_subduction_wasm
- [x] sedimentree_core
- [ ] sedimentree_fs_storage
- [ ] sedimentree_wasm
- [ ] subduction_cli
- [x] subduction_core
- [ ] subduction_crypto
- [ ] subduction_ephemeral
- [ ] subduction_http_longpoll
- [ ] subduction_iroh
- [ ] subduction_keyhive
- [ ] subduction_keyhive_policy
- [ ] subduction_wasm
- [ ] subduction_websocket
- [ ] Nix module / packaging
- [ ] CI / tooling
- [ ] Docs
### Version or commit
9c0fbfd06bd499d4a8b53548788119d33af0d1ec
### Operating system
Linux
### System architecture
x86_64
### Environment
- This is on a fork as seen in #136 but I'm confident my changes are no relevant.
### What happened?
A commit whose child hasn't yet arrived during sync was observed to be a head commit. To give an example of a false heads that's possible to observe: imagine a tree that looks like `A -> B -> C`. If the tree is observed when `A` and `C` are present but not `B`, the heads will read as `[A, C]`.
### What did you expect to happen?
Legitimate exchanges and operation should lock prevent transient state from being observable.
### Reproduction
Essentially, in ingest.rs and in other code paths, a lock is held and released per commit write to the in memory sedimentree cache. And the commits are not toposorted before they're written. Any reader that calculates heads in between that will see transient state. Additionally, there are no toposorting guarantees in the sync messages or subscription pushes and so on. I.e. this isn't just a in memory tree issue but could presumably be observed with direct storage reads.
### Relevant logs / output
```shell
```
### Additional context
Now, I understand that making subduction give guarantees over graph state is difficult as a whole since it doesn't have any other graph guarantees. But this was a surprising footgun and I wanted to open a ticket in case there are mitigations I'm missing. Maybe there are access patterns I could rely on to avoid such problems.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by tracing the per-commit writes in ingest.rs and the sync messages and subscription pushes described in the report. Read the sedimentree_core and subduction_core paths that calculate or expose heads, then determine where transient graph state can be observed. Done means an agreed mitigation or explicit guarantee that prevents or accounts for false heads across the affected paths.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- distributed-systems
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100