typos.go

// Copyright 2018 The go-ethereum Authors
// This file is part of go-ethereum.
//
// go-ethereum is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// go-ethereum is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with go-ethereum. If not, see <http://www.gnu.org/licenses/>.

package main

import (
  "encoding/json"
  "fmt"
  "io"
  "log"
  "os"
  "bufio"

  "github.com/arbovm/levenshtein"
)

type fqTreeNode struct {
  key *string
  value interface{}
  children map[int]*fqTreeNode
}

func (n *fqTreeNode) makeInternal(dist int) {
  n.children = make(map[int]*fqTreeNode)
  n.children[dist] = &fqTreeNode{n.key, n.value, nil}
  n.key = nil
  n.value = nil
}

type FQBKTree struct {
  tree *fqTreeNode
  axes []string
}

func (t *FQBKTree) Insert(key string, value interface{}) {
  if t.tree == nil {
    t.tree = &fqTreeNode{&key, value, nil}
    return
  }

  node := t.tree
  for _, axis := range t.axes {
    if node.key != nil {
      // Leaf node
      if *node.key == key {
        return
      }
      node.makeInternal(levenshtein.Distance(*node.key, axis))
    }

    distance := levenshtein.Distance(key, axis)
    child, ok := node.children[distance]
    if !ok {
      node.children[distance] = &fqTreeNode{&key, value, nil}
      return
    }
    node = child
  }

  t.axes = append(t.axes, key)
  if node.key != nil {
    node.makeInternal(levenshtein.Distance(*node.key, key))
  }
  node.children[0] = &fqTreeNode{&key, value, nil}
}

type Pair struct {
  Key string
  Value interface{}
}

func (t *FQBKTree) Lookup(key string, threshold int) (ret []Pair) {
  nodes := []*fqTreeNode{t.tree}
  for _, axis := range t.axes {
    next := []*fqTreeNode{}
    distance := levenshtein.Distance(key, axis)
    for _, node := range nodes {
      if node.key != nil {
        if levenshtein.Distance(key, *node.key) <= threshold {
          ret = append(ret, Pair{*node.key, node.value})
        }
        continue
      }
      for d := distance - threshold; d <= distance + threshold; d++ {
        if child, ok := node.children[d]; ok {
          next = append(next, child)
        }
      }
      nodes = next
    }
  }

  for _, node := range nodes {
    if levenshtein.Distance(key, *node.key) <= threshold {
      ret = append(ret, Pair{*node.key, node.value})
    }
  }
  return ret
}

type DumpAccountFull struct {
	Address  string            `json:"address"`
	Balance  string            `json:"balance"`
	Nonce    uint64            `json:"nonce"`
	Root     string            `json:"root"`
	CodeHash string            `json:"codeHash"`
	Code     string            `json:"code"`
	Storage  map[string]string `json:"storage"`
}

func iterateDump(filename string) <-chan DumpAccountFull {
  out := make(chan DumpAccountFull)
  fh, err := os.Open(filename)
  if err != nil {
    panic(err)
  }
  r := bufio.NewReader(fh)
  // Discard first line
  r.ReadString('\n')

  go func() {
    defer fh.Close()
    defer close(out)

    var account DumpAccountFull
    for i := 0; true; i++ {
      if i % 10000 == 0 {
        log.Printf("Processed %d lines\n", i)
      }
      line, err := r.ReadBytes('\n')
      if err == io.EOF {
        return
      }
      if err != nil {
        panic(err)
      }

      err = json.Unmarshal(line, &account)
      if err != nil {
        panic(err)
      }
      out <- account
    }
  }()
  return out
}

type typo struct {
  RealAccount string `json: realAccount`
  TypoAccount string `json: typoAccount`
  Balance string `json: balance`
}

func findTypos(t *FQBKTree, jobs <-chan DumpAccountFull, results chan *typo) {
  for account := range jobs {
    if account.Nonce == 0 || account.CodeHash == "c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470" {
      continue
    }
    for _, entry := range t.Lookup(account.Address, 1) {
      results <- &typo{
        RealAccount: account.Address,
        TypoAccount: entry.Key,
        Balance: entry.Value.(string),
      }
    }
  }
  results <- nil
}

func main() {
  // Build a tree out of cold wallet accounts
  log.Printf("Building tree...\n")
  t := &FQBKTree{}
  nodeCount := 0
  for account := range iterateDump(os.Args[1]) {
    if account.Nonce > 0 || account.CodeHash != "c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470" {
      continue
    }
    t.Insert(account.Address, account.Balance)
    nodeCount += 1
  }

  log.Printf("Built tree with %d nodes.\n", nodeCount)
  log.Printf("Finding near neighbours...\n")

  jobs := iterateDump(os.Args[1])
  results := make(chan *typo)
  for i := 0; i < 4; i++ {
    go findTypos(t, jobs, results)
  }

  for running := 4; running > 0; {
    result := <-results
    if result == nil {
      running--
      continue
    }
    out, err := json.Marshal(result)
    if err != nil {
      panic(err)
    }
    fmt.Printf("%s\n", out)
  }
}