inkandswitch / inkandswitch/subduction

[bug]: transient false heads

Open
#283 0 comments 0 reactions 0 assignees View on GitHub
bug
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.