Early circuit builder sketch

circuit_builder.go

package onion

import (
	"context"
	"crypto/rand"
	"fmt"
	"github.com/cretz/deaf9/common"
	"github.com/cretz/deaf9/util"
	"math/big"
	"net"
	"sync"
)

type CircuitBuilder struct {
	conf     *Config
	dir      Directory
	circuits *CircuitList
	Log      util.Logger
}

func (c *CircuitBuilder) BuildCircuit(ctx context.Context, target common.Key) (circuit *Circuit, lastError error) {
	// While we take inspiration from Tor, we don't have things like exit nodes and guards
	// and what not...

	// Description of algorithm steps:
	//  1. Reuse existing path if it already exists (these get culled via external timers)
	//  2. Choose CircuitHops - 1 random IDs where each one is at least HopMinDistance away from the other
	//     * Using randomness here reduces predictability
	//     * Using XOR distance here reduces predictability about the circuit
	//     * If this has been called over CircuitAttempts before, FAIL
	//  3. Get closest PeerConsensusLookupCount peers to hop without remote lookup, and ask each for peers closest to itself
	//     * By not using remote on the exact hop ID, we are not broadcasting what ID we're looking for
	//     * By asking several peers for their list close to themselves, it leaks little about what we want
	//  4. Collect not-me peers that PeerConsensusAgreementCount peers agree that are not in ANY lookup list in #3 for ANY hop ID
	//     * If I route to myself, I reduce the literal hop count
	//     * By requiring agreement, we reduce sybil (of course, trusting the DHT's ID generation and closeness)
	//     * By not including peers in the original lookup list, we remove traffic analysis that can occur by timing
	//       the lookup and the forthcoming tunnel request
	//     * Take care to include peer net address in agreement uniqueness
	//     * Take care to not include target in the resulting set
	//     * If any resulting hop ID set to choose from is < MinPeerListToChooseFrom restart at #2
	//  5. Select a random peer for each hop and arrange the hop order also randomly
	//     * No peers can be in the same subnet as defined by PeerIP4NotInSameMask/PeerIP6NotInSameMask
	//     * The peer selected for a hop index cannot be a peer used at that index for any current circuit
	//     * Failure to build the circuit here, after trying PathOrderAttempts times, restarts at #2
	//     * Note, we choose to go a random number of times instead of any other approach because other approaches tend
	//       to become less random after iteratively nixing options
	//  6. Build circuit as hops + final

	// 1. Reuse path if there
	if circuit = c.findExistingCircuit(target); circuit != nil {
		return
	}

	// Need to know the address of the peer we're trying to get to...
	targetPeer := c.dir.FindPeer(ctx, target)
	if targetPeer == nil {
		return nil, fmt.Errorf("Unable to find target")
	}

	for attempt := 0; attempt < c.conf.CircuitBuildMaxAttempts; attempt++ {
		// 2. Build some hop IDs
		hopIDs, err := c.buildHopIDs(ctx, target)
		if err != nil {
			return nil, err
		}

		// 3. Get all peers close to lookups
		allPeersContactedByID, closePeersByHopIDAndPeerID := c.getClosePeers(ctx, hopIDs)

		// 4. Get consensus peers
		consensusPeersByHopID, anyNotBigEnough := c.getConsensusPeers(ctx, target, allPeersContactedByID, closePeersByHopIDAndPeerID)
		if anyNotBigEnough {
			continue
		}

		// 5. Peers in hop order
		peersInHopOrder, couldNotBuild := c.buildPath(consensusPeersByHopID)
		if couldNotBuild {
			continue
		}

		// 6. Add target and try to build the connections
		if circuit, lastError = c.connect(append(peersInHopOrder, targetPeer)); lastError == nil {
			return
		}
	}
	return
}

func (c *CircuitBuilder) findExistingCircuit(target common.Key) *Circuit {
	for _, c := range c.circuits.Circuits() {
		if c.path[len(c.path)-1].Info().ID.Equal(target) {
			return c
		}
	}
	return nil
}

func (c *CircuitBuilder) buildHopIDs(ctx context.Context, target common.Key) ([]common.Key, error) {
	// Generate CircuitHops - 1 random IDs where each one is at least HopMinDistance away from the other and from target
	ret := make([]common.Key, c.conf.CircuitHops-1)
	for i := 0; i < c.conf.CircuitHops-1; i++ {
		// Find one that's at least the right distance from all of the others
		ret[i] = make(common.Key, c.conf.IDBitCount/8)
	PossibleLoop:
		for attempt := 0; ; attempt++ {
			select {
			case <-ctx.Done():
				return nil, ctx.Err()
			default:
				if attempt > c.conf.HopIDMaxAttempts {
					return nil, fmt.Errorf("Tried %v times to get next hop ID at index %v, but couldn't", attempt)
				}
				_, err := rand.Read(ret[i])
				if err != nil {
					return nil, err
				}
				// If not the right distance, try again
				for j := 0; j < i; j++ {
					select {
					case <-ctx.Done():
						return nil, ctx.Err()
					default:
						if ret[j].DistTo(ret[i]).Cmp(c.conf.HopMinDistance) < 0 || ret[j].DistTo(target).Cmp(c.conf.HopMinDistance) < 0 {
							continue PossibleLoop
						}
					}
				}
			}
			break
		}
	}
	return ret, nil
}

func (c *CircuitBuilder) getClosePeers(
	ctx context.Context,
	hopIDs []common.Key,
) (allPeersContactedByID map[string]Peer, closePeersByHopIDAndPeerID map[string]map[string][]Peer) {

	// Group all local peers by ID
	allPeersByID := make(map[string]Peer, len(hopIDs)*c.conf.PeerConsensusLookupCount)
	hopIDsByPeerID := make(map[string][]common.Key, len(hopIDs)*c.conf.PeerConsensusLookupCount)
	for _, hopID := range hopIDs {
		for _, peer := range c.dir.FindLocalClosePeers(ctx, hopID, c.conf.PeerConsensusLookupCount) {
			peerIDStr := peer.Info().ID.AsString()
			allPeersByID[peerIDStr] = peer
			hopIDsByPeerID[peerIDStr] = append(hopIDsByPeerID[peerIDStr], hopID)
		}
	}

	// Now that we have all of the peers, do a remote fetch on their own ID
	allPeersContactedByID = make(map[string]Peer, len(allPeersByID))
	closePeersByHopIDAndPeerID = make(map[string]map[string][]Peer, len(hopIDs))
	closePeersByHopIDAndPeerIDLock := new(sync.Mutex)
	wg := new(sync.WaitGroup)
	wg.Add(len(allPeersByID))
	for peerIDStr, peer := range allPeersByID {
		allPeersContactedByID[peerIDStr] = peer
		go func(peerIDStr string, peer Peer) {
			// We ignore error for now
			peers, err := c.dir.FindRemoteClosePeers(ctx, peer.Info().ID)
			if err != nil {
				c.Log.Debugf("Failed to get remote peers for %v", peer)
			}
			// We still add even on error because we need the map to show empty if necessary
			closePeersByHopIDAndPeerIDLock.Lock()
			defer closePeersByHopIDAndPeerIDLock.Unlock()
			for _, hopID := range hopIDsByPeerID[peerIDStr] {
				if m := closePeersByHopIDAndPeerID[hopID.AsString()]; m != nil {
					m[peerIDStr] = peers
				} else {
					closePeersByHopIDAndPeerID[hopID.AsString()] = map[string][]Peer{peerIDStr: peers}
				}
			}
			wg.Done()
		}(peerIDStr, peer)
	}
	wg.Wait()
	return
}

func (c *CircuitBuilder) getConsensusPeers(
	ctx context.Context,
	target common.Key,
	allPeersContactedByID map[string]Peer,
	closePeersByHopIDAndPeerID map[string]map[string][]Peer,
) (consensusPeersByHopID map[string][]Peer, anyNotBigEnough bool) {
	// Get the consensus peer set by the hop ID, making sure to return if any are not enough
	consensusPeersByHopID = make(map[string][]Peer, len(closePeersByHopIDAndPeerID))
	for hopIDStr, peersByWhereFromID := range closePeersByHopIDAndPeerID {
		// Sum up how many agree, of course ignoring myself and any we contacted already
		// We key by the ID plus the addr so we can agree by unique ID+addr combo
		agreementCountByIDPlusAddr := map[string]int{}
		peersByIDPlusAddr := map[string]Peer{}
		for _, peers := range peersByWhereFromID {
			for _, peer := range peers {
				peerIDStr := peer.Info().ID.AsString()
				if !peer.Info().ID.Equal(c.dir.Me().ID) && !peer.Info().ID.Equal(target) && allPeersContactedByID[peerIDStr] == nil {
					peerIDPlusAddr := peerIDStr + ":" + peer.Info().AddrStr
					peersByIDPlusAddr[peerIDPlusAddr] = peer
					agreementCountByIDPlusAddr[peerIDPlusAddr]++
				}
			}
		}

		// Now that we have the number of agreements for the peers on this hop,
		// we can fetch the ones that have consensus
		for peerIDPlusAddr, agreementCount := range agreementCountByIDPlusAddr {
			if agreementCount >= c.conf.PeerConsensusAgreementCount {
				consensusPeersByHopID[hopIDStr] = append(consensusPeersByHopID[hopIDStr], peersByIDPlusAddr[peerIDPlusAddr])
			}
		}

		// Make sure the set is big enough
		if len(consensusPeersByHopID) < c.conf.MinPeerListToChooseFrom {
			anyNotBigEnough = true
			break
		}
	}
	return
}

func (c *CircuitBuilder) buildPath(
	consensusPeersByHopID map[string][]Peer,
) (peersInHopOrder []Peer, couldNotBuild bool) {
	// Grab all the circuits from the list eagerly for checking peer indices
	existingCircuits := c.circuits.Circuits()

	// We need to try a random one from each, then put them in a random order
	peersInHopOrder = make([]Peer, 0, len(consensusPeersByHopID))
NewAttempt:
	for attempt := 0; attempt < c.conf.PathOrderMaxAttempts; attempt++ {
		// Go ahead and validate while building
		foundMaskedIPs := map[string]bool{}
		// Put the result back to empty keeping allocd mem
		peersInHopOrder = peersInHopOrder[:0]
		// Grab a random peer and put in random order
		for _, peers := range consensusPeersByHopID {
			// Grab random peer
			randomPeerIndex, err := rand.Int(rand.Reader, big.NewInt(int64(len(peers))))
			if err != nil {
				panic(fmt.Errorf("Unexpected rand err: %v", err))
			}
			randomPeer := peers[int(randomPeerIndex.Uint64())]

			// Is our random peer in the same mask that exists? We consider it failed validation of the
			// whole and completely start over (NOT pick a new random peer)
			masks := c.addrMaskBases(randomPeer.Info().AddrStr)
			if len(masks) == 0 {
				panic(fmt.Errorf("Unexpected no mask for addr %v", randomPeer.Info().AddrStr))
			}
			for _, mask := range masks {
				if foundMaskedIPs[string(mask)] {
					continue NewAttempt
				}
				foundMaskedIPs[string(mask)] = true
			}

			// Random order, ref: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
			bigJ, err := rand.Int(rand.Reader, big.NewInt(int64(len(peersInHopOrder)+1)))
			if err != nil {
				panic(fmt.Errorf("Unexpected rand err: %v", err))
			}
			j := int(bigJ.Uint64())
			if j == len(peersInHopOrder) {
				peersInHopOrder = append(peersInHopOrder, randomPeer)
			} else {
				peersInHopOrder = append(peersInHopOrder, peersInHopOrder[j])
				peersInHopOrder[j] = randomPeer
			}

			// Make sure the peer we just put there is not already at that index somewhere else
			for _, existingCircuit := range existingCircuits {
				if j < len(existingCircuit.path) && existingCircuit.path[j].Info().ID.Equal(randomPeer.Info().ID) {
					continue NewAttempt
				}
			}
		}

		// We made it here, we're good
		return
	}
	couldNotBuild = true
	return
}

func (c *CircuitBuilder) addrMaskBases(addr string) (masked []net.IP) {
	host, _, err := net.SplitHostPort(addr)
	if err != nil {
		panic(fmt.Errorf("Unexpected err parsing %v: %v", addr, err))
	}
	ip := net.ParseIP(host)
	// TODO: not sure how mixed ipv4/ipv6 addresses should be handled with this rule
	// TODO: watch what Tor does with https://trac.torproject.org/projects/tor/ticket/15518
	if ip4 := ip.To4(); ip4 != nil {
		masked = append(masked, ip4.Mask(c.conf.PeerIP4NotInSameMask))
	}
	if len(ip) == net.IPv6len {
		masked = append(masked, ip.Mask(c.conf.PeerIP6NotInSameMask))
	}
	return
}

func (c *CircuitBuilder) connect(peersInHopOrder []Peer) (*Circuit, error) {
	// TODO
	panic("TODO")
}