README

Build Status GoDoc

conflux - Distributed database synchronization

This package has been moved into https://github.com/hockeypuck/hockeypuck. Further contributions should be made there, this project has been archived.

Conflux synchronizes data by unique content-addressable identifiers. It does this by representing the entire set of identifiers with a polynomial. The difference between the databases is represented as a ratio of these polynomials. However, the polynomials are very large, since they represent every identifier in the database. The difference between databases is communicated by evaluating the difference ratio at a number of constants. Through the magic of rational function interpolation, the difference ratio can be reconstructed from these data points.

This algorithm is described in the papers, "Set Reconciliation with Nearly Optimal Communication Complexity" and "Practical Set Reconciliation".

The reconciliation algorithm are released under the GNU General Public License version 3. The reconciliation network protocol and prefix tree data storage interfaces are released under the Affero General Public License version 3.

Usage

Conflux API is versioned with gopkg. Use in your projects with:

import "gopkg.in/hockeypuck/conflux.v2"

Copyright (c) 2012-2015 Casey Marshall cmars@cmarstech.com

Documentation

Overview

Package conflux provides set reconciliation core functionality and the supporting math: polynomial arithmetic over finite fields, factoring and rational function interpolation.

The Conflux API is versioned with gopkg. Use in your projects with:

import "gopkg.in/hockeypuck/conflux.v2"

Index

Constants

This section is empty.

Variables

View Source
var ErrInterpolate = errors.New("interpolation failed")
View Source
var ErrLowMBar = errors.New("low MBar")
View Source
var ErrMatrixTooNarrow = errors.New("matrix is too narrow to reduce")
View Source
var ErrPowModSmallN = errors.New("PowMod not implemented for small values of N")
View Source
var P_128 = big.NewInt(0).SetBytes([]byte{
	0x1, 0x11, 0xd, 0xb2, 0x97, 0xcd, 0x30, 0x8d,
	0x90, 0xe5, 0x3f, 0xb8, 0xa1, 0x30, 0x90, 0x97, 0xe9})

P_128 defines a finite field Z(P) that includes all 128-bit integers.

View Source
var P_160 = big.NewInt(0).SetBytes([]byte{
	0x1, 0xfe, 0x90, 0xe7, 0xb4, 0x19, 0x88, 0xa6,
	0x41, 0xb1, 0xa6, 0xfe, 0xc8, 0x7d, 0x89, 0xa3,
	0x1e, 0x2a, 0x61, 0x31, 0xf5})

P_160 defines a finite field Z(P) that includes all 160-bit integers.

View Source
var P_256 = big.NewInt(0).SetBytes([]byte{
	0x1, 0xdd, 0xf4, 0x8a, 0xc3, 0x45, 0x19, 0x18,
	0x13, 0xab, 0x7d, 0x92, 0x27, 0x99, 0xe8, 0x93,
	0x96, 0x19, 0x43, 0x8, 0xa4, 0xa5, 0x9, 0xb,
	0x36, 0xc9, 0x62, 0xd5, 0xd5, 0xd6, 0xdd, 0x80, 0x27})

P_256 defines a finite field Z(P) that includes all 256-bit integers.

View Source
var P_512 = big.NewInt(0).SetBytes([]byte{
	0x1, 0xc7, 0x19, 0x72, 0x25, 0xf4, 0xa5, 0xd5,
	0x8a, 0xc0, 0x2, 0xa4, 0xdc, 0x8d, 0xb1, 0xd9,
	0xb0, 0xa1, 0x5b, 0x7a, 0x43, 0x22, 0x5d, 0x5b,
	0x51, 0xa8, 0x1c, 0x76, 0x17, 0x44, 0x2a, 0x4a,
	0x9c, 0x62, 0xdc, 0x9e, 0x25, 0xd6, 0xe3, 0x12,
	0x1a, 0xea, 0xef, 0xac, 0xd9, 0xfd, 0x8d, 0x6c,
	0xb7, 0x26, 0x6d, 0x19, 0x15, 0x53, 0xd7, 0xd,
	0xb6, 0x68, 0x3b, 0x65, 0x40, 0x89, 0x18, 0x3e, 0xbd})

P_512 defines a finite field Z(P) that includes all 512-bit integers.

View Source
var P_SKS *big.Int

P_SKS is the finite field used by SKS, the Synchronizing Key Server.

Functions

func IsInterpolateFailure

func IsInterpolateFailure(err error) bool

func PolyDivmod

func PolyDivmod(x, y *Poly) (q *Poly, r *Poly, err error)

PolyDivmod returns the quotient and remainder between two Polys.

func Reconcile

func Reconcile(values []*Zp, points []*Zp, degDiff int) (*ZSet, *ZSet, error)

Reconcile performs rational function interpolation on the given output values at sample points, to return the disjoint values between two sets.

Types

type Bitstring

type Bitstring struct {
	// contains filtered or unexported fields
}

Bitstring describes a sequence of bits.

func NewBitstring

func NewBitstring(bits int) *Bitstring

NewBitstream creates a new zeroed Bitstring of the specified number of bits.

func NewZpBitstring

func NewZpBitstring(zp *Zp) *Bitstring

NewZpBitstring creates a new Bitstring from a Zp integer over a finite field.

func (*Bitstring) BitLen

func (bs *Bitstring) BitLen() int

BitLen returns the number of bits in the Bitstring.

func (*Bitstring) ByteLen

func (bs *Bitstring) ByteLen() int

ByteLen returns the number of bytes the Bitstring occupies in memory.

func (*Bitstring) Bytes

func (bs *Bitstring) Bytes() []byte

Bytes returns a new buffer initialized to the contents of the Bitstring.

func (*Bitstring) Clear

func (bs *Bitstring) Clear(bit int)

Clear clears the bit at the given position to a 0.

func (*Bitstring) Flip

func (bs *Bitstring) Flip(bit int)

Flip inverts the bit at the given position.

func (*Bitstring) Get

func (bs *Bitstring) Get(bit int) int

Get returns the bit value at the given position. If the bit position is greater than the Bitstring size, or less than zero, Get panics.

func (*Bitstring) Lsh

func (bs *Bitstring) Lsh(n uint)

Lsh shifts all bits to the left by one position.

func (*Bitstring) Rsh

func (bs *Bitstring) Rsh(n uint)

Rsh shifts all bits to the right by one position.

func (*Bitstring) Set

func (bs *Bitstring) Set(bit int)

Set sets the bit at the given position to a 1.

func (*Bitstring) SetBytes

func (bs *Bitstring) SetBytes(buf []byte)

SetBytes sets the Bitstring bits to the contents of the given buffer. If the buffer is smaller than the Bitstring, the remaining bits are cleared.

func (*Bitstring) String

func (bs *Bitstring) String() string

String renders the Bitstring to a string as a binary number.

type Matrix

type Matrix struct {
	// contains filtered or unexported fields
}

Matrix represents a rectangular array of numbers over a finite field Z(p).

func NewMatrix

func NewMatrix(columns, rows int, x *Zp) *Matrix

NewMatrix returns a new Matrix of the given dimensions and finite field p.

func (*Matrix) Get

func (m *Matrix) Get(i, j int) *Zp

Get returns the value at the given (row, column) location.

func (*Matrix) Reduce

func (m *Matrix) Reduce() error

Reduce performs Gaussian elimination on a matrix of coefficients, in-place.

func (*Matrix) Set

func (m *Matrix) Set(i, j int, x *Zp)

Set sets the value at the given (row, column) location.

func (*Matrix) String

func (m *Matrix) String() string

String returns a string representation of the matrix.

type Poly

type Poly struct {
	// contains filtered or unexported fields
}

Poly represents a polynomial in a finite field.

func NewPoly

func NewPoly(coeff ...*Zp) *Poly

NewPoly creates a polynomial with the given coefficients, in ascending degree order.

For example, NewPoly(1,-2,3) represents the polynomial 3x^2 - 2x + 1.

func PolyDiv

func PolyDiv(x, y *Poly) (*Poly, error)

PolyDiv returns the quotient between two Polys.

func PolyGcd

func PolyGcd(x, y *Poly) (*Poly, error)

PolyGcd returns the greatest common divisor between two Polys.

func PolyMod

func PolyMod(x, y *Poly) (*Poly, error)

PolyDiv returns the mod function between two Polys.

func PolyRand

func PolyRand(p *big.Int, degree int) *Poly

PolyRand generates a random polynomial of degree n. This is useful for probabilistic polynomial factoring.

func PolyTerm

func PolyTerm(degree int, c *Zp) *Poly

PolyTerm creates a new Poly with a single non-zero coefficient.

func (*Poly) Add

func (p *Poly) Add(x, y *Poly) *Poly

Add sets the Poly instance to the sum of two Polys, returning the result.

func (*Poly) Coeff

func (p *Poly) Coeff() []*Zp

Coeff returns the coefficients for each term of the polynomial. Coefficients are represented as integers in a finite field Zp.

func (*Poly) Copy

func (p *Poly) Copy() *Poly

Copy returns a deep copy of the polynomial and its term coefficients.

func (*Poly) Degree

func (p *Poly) Degree() int

Degree returns the highest exponent that appears in the polynomial. For example, the degree of (x^2 + 1) is 2, the degree of (x^1) is 1.

func (*Poly) Equal

func (p *Poly) Equal(q *Poly) bool

Equal compares with another polynomial for equality.

func (*Poly) Eval

func (p *Poly) Eval(z *Zp) *Zp

Eval returns the output value of the Poly at the given sample point z.

func (*Poly) Factor

func (p *Poly) Factor() (*ZSet, error)

Factor reduces a polynomial to irreducible linear components. If the polynomial is not reducible to a product of linears, the polynomial is useless for reconciliation, resulting in an error. Returns a ZSet of all the constants in each linear factor.

func (*Poly) IsConstant

func (p *Poly) IsConstant(c *Zp) bool

IsConstant returns whether the Poly is just a constant value.

func (*Poly) Mul

func (p *Poly) Mul(x, y *Poly) *Poly

Mul sets the Poly to the product of two Polys, returning the result.

func (*Poly) Neg

func (p *Poly) Neg() *Poly

Neg negates the Poly, returning the result.

func (*Poly) P

func (p *Poly) P() *big.Int

P returns the integer P defining the finite field of the polynomial's coefficients.

func (*Poly) String

func (p *Poly) String() string

String represents a polynomial in a more readable form, such as "z^2 + 2z^1 + 1".

func (*Poly) Sub

func (p *Poly) Sub(x, y *Poly) *Poly

Sub sets the Poly to the difference of two Polys, returning the result.

type RationalFn

type RationalFn struct {
	Num   *Poly
	Denom *Poly
}

RationalFn describes a function that is the ratio between two polynomials.

func Interpolate

func Interpolate(values []*Zp, points []*Zp, degDiff int) (*RationalFn, error)

Interpolate returns the ratio of two polynomials RationalFn, given a set of sample points and output values. The coefficients of the resulting numerator and denominator represent the disjoint members in two sets being reconciled.

type ZSet

type ZSet struct {
	// contains filtered or unexported fields
}

ZSet is a set of integers in a finite field.

func NewZSet

func NewZSet(elements ...*Zp) (zs *ZSet)

NewZSet returns a new ZSet containing the given elements.

func ZSetDiff

func ZSetDiff(a *ZSet, b *ZSet) *ZSet

ZSetDiff returns the set difference between two ZSets: the set of all Z(p) in a that are not in b.

func (*ZSet) Add

func (zs *ZSet) Add(v *Zp)

Add adds an element to the set.

func (*ZSet) AddAll

func (zs *ZSet) AddAll(other *ZSet)

AddAll adds all elements in another set.

func (*ZSet) AddSlice

func (zs *ZSet) AddSlice(other []*Zp)

AddSlice adds all the given elements to the set.

func (*ZSet) Equal

func (zs *ZSet) Equal(other *ZSet) bool

Equal returns whether this set is equal to another set.

func (*ZSet) Has

func (zs *ZSet) Has(v *Zp) bool

Has returns whether the set has the given element as a member.

func (*ZSet) Items

func (zs *ZSet) Items() (result []*Zp)

Items returns a slice of all elements in the set.

func (*ZSet) Len

func (zs *ZSet) Len() int

Len returns the length of the set.

func (*ZSet) Remove

func (zs *ZSet) Remove(v *Zp)

Remove removes an element from the set.

func (*ZSet) RemoveAll

func (zs *ZSet) RemoveAll(other *ZSet)

RemoveAll removes all elements in another set from this one.

func (*ZSet) RemoveSlice

func (zs *ZSet) RemoveSlice(other []*Zp)

RemoveSlice removes all the given elements from the set.

func (*ZSet) String

func (zs *ZSet) String() string

String returns a string representation of the set.

type Zp

type Zp struct {

	// Int is the integer's value.
	*big.Int

	// P is the prime bound of the finite field Z(p).
	P *big.Int
}

Zp represents a value in the finite field Z(p), an integer in which all arithmetic is (mod p).

func Z

func Z(p *big.Int) *Zp

Z returns a new integer in the finite field P initialized to 0.

func Zarray

func Zarray(p *big.Int, n int, v *Zp) []*Zp

Zarray returns a new array of integers, all initialized to v.

func Zb

func Zb(p *big.Int, b []byte) *Zp

Zb returns a new integer in the finite field p from a byte representation.

func Zi

func Zi(p *big.Int, n int) *Zp

Zi returns a new integer n in the finite field p.

func Zpoints

func Zpoints(p *big.Int, n int) []*Zp

Generate points for rational function interpolation.

func Zrand

func Zrand(p *big.Int) *Zp

Zrand returns a new random integer in the finite field p.

func Zs

func Zs(p *big.Int, s string) *Zp

Zs returns a new integer from base10 string s in the finite field p.

func Zzp

func Zzp(zp *Zp) *Zp

Zzp returns a new integer in the finite field P initialized to zp.

func (*Zp) Add

func (zp *Zp) Add(x, y *Zp) *Zp

Add sets the integer value to the sum of two integers, returning the result.

func (*Zp) Bytes

func (zp *Zp) Bytes() []byte

Bytes returns the byte representation of Zp.

func (*Zp) Cmp

func (zp *Zp) Cmp(x *Zp) int

Cmp compares zp with another integer. See big.Int.Cmp for return value semantics.

func (*Zp) Copy

func (zp *Zp) Copy() *Zp

Copy returns a new Zp instance with the same value.

func (*Zp) Div

func (zp *Zp) Div(x, y *Zp) *Zp

Div sets the integer value to x/y in the finite field p, returning the result.

func (*Zp) Exp

func (zp *Zp) Exp(x, y *Zp) *Zp

Exp sets the integer value to x**y ("x to the yth power"), returning the result.

func (*Zp) Inv

func (zp *Zp) Inv() *Zp

Inv sets the integer value to its multiplicative inverse, returning the result.

func (*Zp) IsZero

func (zp *Zp) IsZero() bool

IsZero returns whether the integer is zero.

func (*Zp) Mul

func (zp *Zp) Mul(x, y *Zp) *Zp

Mul sets the integer value to the product of two integers, returning the result.

func (*Zp) Neg

func (zp *Zp) Neg() *Zp

Neg sets the integer to its additive inverse, returning the result.

func (*Zp) Norm

func (zp *Zp) Norm() *Zp

Norm normalizes the integer to its finite field, (mod P).

func (*Zp) SetBytes

func (zp *Zp) SetBytes(b []byte)

SetBytes sets the integer from its byte representation.

func (*Zp) Sub

func (zp *Zp) Sub(x, y *Zp) *Zp

Sub sets the integer value to the difference of two integers, returning the result.

type ZpSlice

type ZpSlice []*Zp

ZpSlice is a collection of integers in a finite field.

func (ZpSlice) String

func (zp ZpSlice) String() string

String returns a string representation of the ZpSlice.

Directories

Path Synopsis
cmd
primegen
primegen is a utility for generating large primes that bound a given bit length.
primegen is a utility for generating large primes that bound a given bit length.
sks-dump-ptree
sks-dump-ptree is a debugging utility developed to parse and reverse engineer the SKS PTree databases.
sks-dump-ptree is a debugging utility developed to parse and reverse engineer the SKS PTree databases.
Package recon provides the SKS reconciliation protocol, prefix tree interface and an in-memory prefix-tree implementation.
Package recon provides the SKS reconciliation protocol, prefix tree interface and an in-memory prefix-tree implementation.
leveldb
Package leveldb provides a key-value storage implementation of the recon prefix tree interface.
Package leveldb provides a key-value storage implementation of the recon prefix tree interface.
testing
Package testing provides some unit-testing support functions.
Package testing provides some unit-testing support functions.