Replaceable event delta-encoding

[jb55]

original idea here: nostr-protocol/nips#349 (comment)

I'm planning on resolving this by creating a delta-contact list format,
so each change can be represented by "diff" of the previous one you have
stored. This will allow us to show every change in a compact way, very
much like "git diff" for your contact list, and it's backwards
compatible with everything. Then you will be able to review and rollback
to any previous revision, perhaps damus can do this automatically if it
sees large drops of contacts at once.

[jb55]

it would be cool to generalize this to any addressable event, where content is diff-encoded. This would allow us to do version control of editable events like longform posts

[jb55]

Different idea:

Once we implement:

• Replaceable events #60

Then nostrdb could auto-generate delta information from a note when a note is replaced.

[kernelkind]

it would be cool to generalize this to any addressable event, where content is diff-encoded. This would allow us to do version control of editable events like longform posts

this sounds really cool

[jb55]

Notes for implementing this binary deltas (for the contents)

• https://datatracker.ietf.org/doc/html/rfc3284
• https://github.com/google/open-vcdiff

but we can do something much simpler:

Simplified Delta Encoding Format

Three Core Operations:

•	RUN: Repeats a byte multiple times.
•	COPY: Copies a sequence from a specific offset.
•	ADD: Inserts raw data directly.

• Byte-Aligned Instructions: Each instruction begins with an operation byte, making it easy to parse.

Proposed Instruction Format

Byte Index	Content	Description
0	Operation Code (1 byte)	0x00: ADD, 0x01: COPY, 0x02: RUN
1	Length (1–2 bytes)	Length of the data for the operation
2+	Data/Offset (variable)	Depends on the operation type

	•	ADD: Followed by raw data bytes.
	•	Example: 0x00 0x04 ABCD (ADD 4 bytes: “ABCD”).
	•	COPY: Followed by source offset (1–2 bytes) and length.
	•	Example: 0x01 0x02 0x10 (COPY 2 bytes from offset 16).
	•	RUN: Followed by the repeated byte and count.
	•	Example: 0x02 0x05 0x41 (RUN ‘A’ for 5 times).

Example of Encoding

Original File: AAAABBBBCCCCDDDD
	•	Base File: AAAABBBBCCCC
	•	Delta (to generate AAAABBBBCCCCDDDD):
	•	COPY 12 bytes (everything from the base file).
	•	ADD 4 bytes (“DDDD”).

Delta Encoding:

0x01 0x0C 0x00  # COPY 12 bytes from offset 0
0x00 0x04 DDDD  # ADD "DDDD"

Benefits of this Approach
	1.	Compact: Suited for small files; no excessive headers or complexity.
	2.	Simple Parsing: Byte-aligned and minimal instruction set.
	4.	Customizable: Easy to extend if needed, e.g., adding compression.