AOSSIE-Org / AOSSIE-Org/OpenVerifiableLLM

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

Aberta
#45 1 comentário 0 reações 0 responsáveis Ver no GitHub
bug
Linguagem predominante
Python
Estrelas
18
Forks
31
Merge médio
1min
PRs com merge (30d)
2

Descrição

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

Guia de contribuição

Abrir o guia de contribuição

Avaliação

Esta issue ainda não foi avaliada.

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.