FastSSZ

https://github.com/ferranbt/fastssz

FastSSZ Changes

#26 - Added the possibility to use a different hash function. Sina wanted to use keccak256 as hash function.

#27 - Added PutUint32, PutUint16, and PutUint8 to the hasher. Used to only have PutUint64.

#28 - Created new schema, - Added verification function for one of the structs, - Some hand-crafted test cases, - Pending to make verify more general so its not only for one struct. - New Files: - tests/codetrie.go: - tests/codetrie_encoding.go: Automatically generated by fastssz - tests/codetrie_test.go: Verify proof tests

#32 - Added new proof.go; which included functions to verify proofs and verify multiproof as other helper functions.

#33 - Added support for multiproof generation

#38 - Adds a --experimental flag to get the tree-backing of an object - Given the tree-backing you can compute the root, generate and verify proofs.

#39 (pending PR) - Remove duplicate leafs from proof

ProveMulti

path: tree.go

• Input: indices
• Output: Multiproof

Get the required indices (getRequiredIndices).

Defines proof as a Multiproof object, declared with the provided indices, an empty Leaves array or arrays, an empty Hashes array of arrays.

For each provided index, get the node based on the index. Adds the node as a Leave.

For each reqIndices, get the node based on that index, Adds the node as a Hash.

Returns the proof.

func (n *Node) ProveMulti(indices []int) (*Multiproof, error) {
	reqIndices := getRequiredIndices(indices)
	proof := &Multiproof{Indices: indices, Leaves: make([][]byte, len(indices)), Hashes: make([][]byte, len(reqIndices))}

	for i, gi := range indices {
		node, err := n.Get(gi)
		if err != nil {
			return nil, err
		}
		proof.Leaves[i] = node.value
	}

	for i, gi := range reqIndices {
		cur, err := n.Get(gi)
		if err != nil {
			return nil, err
		}
		proof.Hashes[i] = hashNode(cur)
	}

	return proof, nil
}

Compress (Multiproof)

• (Multiproof) Compress: Returns a *CompressedMultiproof

tree.go

// Compress returns a new proof with zero hashes omitted.
// See `CompressedMultiproof` for more info.
func (p *Multiproof) Compress() *CompressedMultiproof {
	compressed := &CompressedMultiproof{
		Indices:    p.Indices,
		Leaves:     p.Leaves,
		Hashes:     make([][]byte, 0, len(p.Hashes)),
		ZeroLevels: make([]int, 0, len(p.Hashes)),
	}

	for _, h := range p.Hashes {
		if l, ok := zeroHashLevels[string(h)]; ok {
			compressed.ZeroLevels = append(compressed.ZeroLevels, l)
			compressed.Hashes = append(compressed.Hashes, nil)
		} else {
			compressed.Hashes = append(compressed.Hashes, h)
		}
	}

	return compressed
}

Multiproof:

// Multiproof represents a merkle proof of several leaves.
type Multiproof struct {
	Indices []int
	Leaves  [][]byte
	Hashes  [][]byte
}

CompressedMultiproof:

// CompressedMultiproof represents a compressed merkle proof of several leaves.
// Compression is achieved by omitting zero hashes (and their hashes). `ZeroLevels`
// contains information which helps the verifier fill in those hashes.
type CompressedMultiproof struct {
	Indices    []int
	Leaves     [][]byte
	Hashes     [][]byte
	ZeroLevels []int // Stores the level for every omitted zero hash in the proof
}