optimize.go

// This program empirically tests for the optimal GCS filter size under
// different assumptions of block size, transaction size, number of inputs, etc.

package main

import (
	"fmt"
	"math/rand"

	"github.com/btcsuite/btcutil/gcs/builder"
)

var (
	blockSize     = 1.8 * 1024 * 1024 // 1.8MiB
	numBlocks     = 1008              // Number of test blocks - 1 week
	walletEntries = 2000              // Number of wallet entries
	txEntries     = 4                 // 2 outpoints, 2 pushed data entries - optimize for basic filter
	txSize        = 373               // Average 2 in, 2 out single-sig tx size
	minBits       = 1
	maxBits       = 32 // Number of bits allowed for collision space
)

func main() {
	// Table heading
	// Generate random wallet entries
	randWallet := make([][]byte, walletEntries)
	for i := 0; i < walletEntries; i++ {
		randWallet[i] = make([]byte, 9) // Only need 8 bytes of randomness for SipHash8 but generate 9 to
		// guarantee all matches are false positives
		_, err := rand.Read(randWallet[i])
		if err != nil {
			fmt.Printf("Couldn't generate 9 random bytes: %s", err)
			return
		}
	}
	// Go through each desired collision space size
	fmt.Printf("Block size: %d\n", int(blockSize))
	fmt.Printf("Transaction size: %d\n", txSize)
	fmt.Printf("Filter entries per transaction: %d\n", txEntries)
	blockEntries := int(blockSize) * txEntries / txSize
	fmt.Printf("Filter entries per block: %d\n", blockEntries)
	fmt.Printf("Number of blocks: %d\n", numBlocks)
	fmt.Printf("Wallet entries: %d\n", walletEntries)
	fmt.Printf("Bits\t\tFP Block DL\t\tFilter Size\t\tTotal DL\n")
	for P := minBits; P <= maxBits; P++ {
		// Track number of false positives for the collision space size
		fp := 0
		totalFilterSize := 0 // Watch for overflows on some platforms
		// Sample a number of blocks
		for i := 0; i < numBlocks; i++ {
			b := builder.WithRandomKeyP(uint8(P))
			// Add entries to the builder
			for j := 0; j < blockEntries; j++ {
				entry := make([]byte, 8) // Only 8 bytes of randomness for SipHash8
				_, err := rand.Read(entry)
				if err != nil {
					fmt.Printf("Couldn't generate 8 random bytes: %s", err)
					return
				}
				b.AddEntry(entry)
			}
			// Build the filter and match against it
			f, err := b.Build()
			if err != nil {
				fmt.Printf("Couldn't build filter: %s", err)
				return
			}
			key, err := b.Key()
			if err != nil {
				fmt.Printf("Couldn't get builder key: %s", err)
				return
			}
			matched, err := f.MatchAny(key, randWallet)
			if err != nil {
				fmt.Printf("Couldn't MatchAny with filter: %s", err)
			}
			if matched {
				fp++ // Got a false positive
			}
			totalFilterSize += len(f.NBytes()) // Size of filter as used in BIP
		}
		// Print statistics
		blockDL := blockSize * float64(fp)
		fmt.Printf("%d\t\t%.f\t\t%d\t\t%.f\n", P, blockDL,
			totalFilterSize, blockDL+float64(totalFilterSize))
	}
}