conflux

package module
v1.0.0-...-36f0417 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 17, 2015 License: GPL-3.0 Imports: 5 Imported by: 0

README

Build Status

conflux - Distributed database synchronization

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.

Copyright (C) 2012,2013 Casey Marshall casey.marshall@gmail.com

Documentation

Overview

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

Index

Constants

This section is empty.

Variables

View Source 
var ErrLowMBar error = 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 InterpolationFailure = errors.New("Interpolation failed")
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 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() (err 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) (q *Poly, err error)

PolyDiv returns the quotient between two Polys.

func PolyGcd 

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

PolyGcd returns the greatest common divisor between two Polys.

func PolyMod 

func PolyMod(x, y *Poly) (r *Poly, err 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) (rfn *RationalFn, err 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) 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.

Source Files

View all Source files

Directories

Path Synopsis
cmd
dump-leveldb
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.
Package testing provides some unit-testing support functions.
 Package testing provides some unit-testing support functions.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.