AOSSIE-Org / AOSSIE-Org/OpenVerifiableLLM

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

Abierto
#45 1 comentario 0 reacciones 0 asignados Ver en GitHub
bug
Lenguaje dominante
Python
Estrellas
18
Forks
31
Merge medio
1 min
PR fusionados (30 d)
2

Descripción

### 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

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.