Negentropy sync

[staab]

It would be awesome if grain supported syncing with negentropy.

[0ceanSlim]

Yea multiple database types are on the to-do. I need to make some sort of adapter and LMDB is the first on the list since it's the most popular. Can you link me to more docs on negentropy?

[0ceanSlim]

Never mind. I think I found it again. https://github.com/hoytech/negentropy

Any tips for where to begin? I might have to read this several dozen times before it sinks in 😅

[0ceanSlim]

How's this look? Now, where to begin with the implementation...
Core code snippets:

1. Encoding a Varint:

func encodeVarint(x uint64) []byte {
    var buf []byte
    for x >= 0x80 {
        buf = append(buf, byte(x)|0x80)
        x >>= 7
    }
    buf = append(buf, byte(x))
    return buf
}

2. Fingerprint Calculation:

func calculateFingerprint(ids []string) []byte {
    var sum big.Int
    for _, id := range ids {
        idBytes := []byte(id)
        sum.Add(&sum, new(big.Int).SetBytes(idBytes))
    }
    hashInput := append(sum.Bytes(), encodeVarint(uint64(len(ids)))...)
    sha := sha256.Sum256(hashInput)
    return sha[:16]
}

3. Constructing and Sending Messages:

func createMessage(version byte, ranges []Range) []byte {
    var msg []byte
    msg = append(msg, version)
    for _, r := range ranges {
        msg = append(msg, r.toBytes()...)
    }
    return msg
}

func sendMessage(ws *websocket.Conn, msg []byte) error {
    return ws.WriteMessage(websocket.BinaryMessage, msg)
}

4. Handling Incoming Messages:

func handleIncomingMessage(ws *websocket.Conn, message []byte) {
    // Parse the message and handle ranges based on the mode.
    version := message[0]
    if version != 0x61 {
        // Respond with the highest supported version.
        ws.WriteMessage(websocket.TextMessage, []byte{0x61})
        return
    }

    // Parse ranges and respond accordingly...
}

5. Processing Fingerprints and Ranges:

• When receiving a Fingerprint, compare it with your computed value for the same range.
• If they differ, split the range into smaller sub-ranges and request detailed IdList information.
  Synchronizing Missing IDs:

6. For IDs that are missing in your relay, initiate additional requests to fetch the events.

[staab]

I haven't implemented negentropy personally, I just use the javascript version of the code in the repository. Maybe you could use the c version he provides through FFI, or you could use one of the go implementations out there:

• https://pkg.go.dev/github.com/wader/fq/format/negentropy
• https://github.com/HORNET-Storage/go-negentropy

One wrinkle is that Doug has recently released v1 of the protocol, which isn't backwards compatible. So you'd have to choose which versions to support, and there may not be any existing go implementations (if it helps, Coracle/Flotilla only support v1).

[staab]

Also, supporting negentropy doesn't rely on using LMDB, it can be done on top of any database backend I believe.

[0ceanSlim]

Also, supporting negentropy doesn't rely on using LMDB, it can be done on top of any database backend I believe.

I was realizing this as I dug into it further, but more databases are still a huge priority. Just a few small things left and I'd like to implement WOT first. But I'm close.