AOSSIE-Org / AOSSIE-Org/OpenVerifiableLLM

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

未關閉
#45 1 則留言 0 個 reaction 已指派 0 人 在 GitHub 檢視
bug
主要語言
Python
星號
18
分支
31
平均合併
1 分鐘
30 天內合併 PR
2

描述

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

貢獻指南

開啟貢獻指南

評估

這個 Issue 還沒有評估資料。

把新 issue 寄到你的電子郵件信箱

精選適合新手參與的 GitHub issue 摘要。