transparency-dev / transparency-dev/incubator

vindex: incremental verification

Open
#91 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
Dominant language
Go
Stars
4
Forks
6
Avg merge
3d 23h
Merged PRs (30d)
3

Description

Apologies if I misread the documentation and you already have thought about or are planning this:

It would be neat if verifying updates to the summary map could be done incrementally without storing the whole map. Then a lightweight witness could itself sign off on the summary map, without needing to re-compute or store the map itself.

The crypto machinery for this is mostly straightforward. An inclusion proof for a merkle trie (or other authenticated data structure) is almost the same as a modification proof, since you can encode a lookup proof to a leaf in the old trie, and then re-use that to compute the hash of the trie with a different leaf. This update proof can be stored and published the same way as the log.

Happy to prototype if y’all are interested.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the vindex documentation and its existing summary-map verification flow; the issue names no source files or tests. Establish how proofs are represented and published, then define completion as incremental verification that lets a lightweight witness validate updates without storing or recomputing the whole map.

Written by the indexing model from the issue text.

Assessment

Tech stack
go
Domain
cryptography
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.