merklezied proof of custody

custody.go

package main

import (
	"bytes"
	"crypto/rand"
	"fmt"

	"github.com/ethereum/go-ethereum/crypto/sha3"
)

func keccak(data ...[]byte) []byte {
	h := sha3.New256()
	for i := range data {
		h.Write(data[i])
	}
	return h.Sum(nil)
}

func merkelize(chunks [][]byte) [][]byte {
	tree := make([][]byte, len(chunks)-1)
	tree = append(tree, chunks...)
	for i := len(chunks) - 2; i >= 0; i-- {
		tree[i] = keccak(tree[i*2+1], tree[i*2+2])
	}
	return tree
}

func proof(tree [][]byte, chunkPosition int) [][]byte {
	idx := chunkPosition + len(tree)/2 + 1
	branch := make([][]byte, 0)
	for idx > 1 {
		branch = append(branch, tree[idx^1-1])
		idx = idx / 2
	}
	return branch
}

func verify(root []byte, chunk []byte, position int, branch [][]byte) bool {
	idx := position + (1 << uint(len(branch)))
	value := keccak(chunk)
	for i := range branch {
		if idx%2 == 0 {
			value = keccak(value, branch[i])
		} else {
			value = keccak(branch[i], value)
		}
		idx = idx / 2
	}
	return bytes.Compare(root, value) == 0

}

func main() {
	// step 0. split single data ~64kb into 128 equal chunks (~500 bytes each).
	data := make([]byte, 64000)
	rand.Read(data)
	chunks := make([][]byte, 128)
	chunkSize := len(data) / len(chunks)
	start, end := 0, chunkSize
	for i := range chunks {
		chunks[i] = keccak(data[start:end])
		start, end = end, end+chunkSize
	}

	// step 1. storer buids a binary merkle tree.
	// commitment for a validator would be a root of the binary merkle tree (tree[0]) and chunk size:
	// e.g. Commitment{Root: tree[0], ChunkSize: 500} + signature.
	// verifier merkelizes chunks and verifies that returned root is correct.
	tree := merkelize(chunks)

	// step 2. if verifier wants to challenge the storer:
	// it need to commit 4 values on chain:
	// Original commitment with signature. Hash of the chunk and position of the chunk.

	// step 3: storer can respond to a challenge using merkle branch for a concrete chunk.
	// storer always can build a branch, because it knows how chunk is splitted.
	branch := proof(tree, 2) // index of the original chunk
	fmt.Printf("Size of the branch %d. Size of the single chunk %d\n", len(branch)*len(branch[0]), chunkSize)
	assert(verify(tree[0], data[2*chunkSize:3*chunkSize], 2, branch))

	// step 4:
	// storer responds in two ways:
	// 1. if verifier submitted wrong hash it can prove that the hash is wrong by submitting a branch for position
	// provided in a challenge. And if the resulted root of tree matches one from the challenge - challenge is aborted.
	// Verifier must pay to storer, because such situation can be created only intetionally.
	// 2. if verifier submitted correct hash of the chunk - storer can just prove that it has this chunk by providing
	// correct branch and original chunk of bytes. Hash of the original chunk must match the hash from a commitment.
	// This solution requires storer to keep all the data, which is what we want to achieve. Storer never knows which
	// chunk will be requested to prove, so it has to keep all the data.
}

func assert(rst bool) {
	if !rst {
		panic("test didnt met the expectation")
	}
}