Skip to content

Instantly share code, notes, and snippets.

View litecoinmessiah's full-sized avatar
💭
I may be slow to respond.

litecoinmessiah

💭
I may be slow to respond.
View GitHub Profile
@litecoinmessiah
litecoinmessiah / balanced_merkle_path_update.md
Created May 24, 2019 00:17 — forked from gavinandresen/balanced_merkle_path_update.md
Updating old paths (witnesses) for a balanced merkle forest accumulator

Introduction

It would be spiffy to use the balanced merkle forest idea for ethereum tokens or to store unspent transaction outputs.

Tadge Dryja has been working on 'utreexo' (presentation) for storing unspent transaction outputs in log(n) space; this gist is inspired by, and is very similar to, that work.

So my previous gist describes really simple algorithms for adding and removing items from a balanced merkle forest. This gist extends those operations to create