AOSSIE-Org / AOSSIE-Org/OpenVerifiableLLM

[BUG]: Merkle Sibling Index Inconsistency in `generate_merkle_proof()` May Failures

Offen
#45 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
bug
Vorherrschende Sprache
Python
Sterne
18
Forks
31
Ø Merge
1 Min.
Gemergte PRs (30 T.)
2

Beschreibung

### Bug Description


### Description

There is a structural inconsistency in how odd-length tree levels are handled between `compute_merkle_root()` and `generate_merkle_proof()`. While both functions produce correct results today, they use different strategies for padding odd nodes — meaning any future modification to one function without the other will cause proofs to silently fail against the root.

Additionally, the sibling index calculation uses a raw XOR (`index ^ 1`), which is only safe because of the pre-padding step above it. This is fragile and non-obvious.

---

### Root Cause

| Function | Odd-node strategy |
|---|---|
| `compute_merkle_root()` | Inline: `right = left if i+1 >= len(leaves)` |
| `generate_merkle_proof()` | Pre-pads: `leaves.append(leaves[-1])` |

The sibling calculation in `generate_merkle_proof()`:

```python
# Fragile — only safe due to pre-padding above
sibling_index = index ^ 1
```

---

### Expected Behaviour

Both functions should use the same, explicit odd-node strategy, and sibling index calculation should be self-evidently safe without relying on a prior mutation of the array.

---

### Suggested Fix

Replace the XOR with an explicit parity check:

```python
# In generate_merkle_proof()
sibling_index = index - 1 if index % 2 == 1 else index + 1
# Guard: ensure sibling doesn't exceed bounds (handles odd levels)
if sibling_index >= len(leaves):
sibling_index = index # duplicate self
```

And unify the padding strategy across both functions for long-term maintainability.

---

### Impact

- Merkle proofs may silently fail if either function is modified independently
---

Medium - Feature works but has issues

### Code of Conduct

- [x] I have joined the [Discord server](https://discord.gg/hjUhu33uAn) and will post updates there
- [x] I have searched existing issues to avoid duplicates

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.