conflux

package module
v0.0.0-...-6e15c72 Latest Latest
Warning

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

 Go to latest Published: Dec 31, 2013 License: GPL-3.0 Imports: 5 Imported by: 0

README

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 InterpolationFailure = errors.New("Interpolation failed")
View Source 
var LowMBar error = errors.New("Low MBar")
View Source 
var MatrixTooNarrow = errors.New("Matrix is too narrow to reduce")
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 for 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 for 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 for 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 for a finite field Z(P) that includes all 512-bit integers.

View Source 
var P_SKS *big.Int

Finite field P used by SKS, the Synchronizing Key Server.

View Source 
var SwapRowNotFound = errors.New("Swap row not found")

Functions

func PolyDivmod 

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

func Reconcile 

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

func ReverseByte 

func ReverseByte(b byte) (r byte)

func ReverseBytes 

func ReverseBytes(buf []byte) (result []byte)

Types

type Bitstring 

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

func NewBitstring 

func NewBitstring(bits int) *Bitstring

func NewZpBitstring 

func NewZpBitstring(zp *Zp) *Bitstring

func (*Bitstring) BitLen 

func (bs *Bitstring) BitLen() int

func (*Bitstring) ByteLen 

func (bs *Bitstring) ByteLen() int

func (*Bitstring) Bytes 

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

func (*Bitstring) Flip 

func (bs *Bitstring) Flip(bit int)

func (*Bitstring) Get 

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

func (*Bitstring) Lsh 

func (bs *Bitstring) Lsh(n uint)

func (*Bitstring) Rsh 

func (bs *Bitstring) Rsh(n uint)

func (*Bitstring) Set 

func (bs *Bitstring) Set(bit int)

func (*Bitstring) SetBytes 

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

func (*Bitstring) String 

func (bs *Bitstring) String() string

func (*Bitstring) Unset 

func (bs *Bitstring) Unset(bit int)

type Matrix 

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

func NewMatrix 

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

func (*Matrix) Get 

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

func (*Matrix) Reduce 

func (m *Matrix) Reduce() (err error)

func (*Matrix) Set 

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

func (*Matrix) String 

func (m *Matrix) String() string

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)

func PolyGcd 

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

func PolyMod 

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

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

func (*Poly) Add 

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

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

func (*Poly) Factor 

func (p *Poly) Factor() (roots *ZSet, err 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

func (*Poly) Mul 

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

func (*Poly) Neg 

func (p *Poly) Neg() *Poly

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 readable form, such as (z^2 + 2z^1 + 1).

func (*Poly) Sub 

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

type RationalFn 

type RationalFn struct {
	Num   *Poly
	Denom *Poly
}

func Interpolate 

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

type ZSet 

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

func NewZSet 

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

func ZSetDiff 

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

func (*ZSet) Add 

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

func (*ZSet) AddAll 

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

func (*ZSet) AddSlice 

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

func (*ZSet) Equal 

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

func (*ZSet) Has 

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

func (*ZSet) Items 

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

func (*ZSet) Len 

func (zs *ZSet) Len() int

func (*ZSet) Remove 

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

func (*ZSet) String 

func (zs *ZSet) String() string

type Zp 

type Zp struct {
	// The integer's value.
	*big.Int
	// 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 creates an integer in the finite field P initialized to 0.

func Zarray 

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

func Zb 

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

func Zi 

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

Zi creates an 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

func Zs 

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

Zs creates an integer from base10 string s in the finite field p.

func Zzp 

func Zzp(zp *Zp) *Zp

Zzp creates an integer in the finite field P initialized to zp.

func (*Zp) Add 

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

Add two integers.

func (*Zp) Bytes 

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

func (*Zp) Cmp 

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

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

func (*Zp) Copy 

func (zp *Zp) Copy() *Zp

Copy the integer, since operations are mutable.

func (*Zp) Div 

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

func (*Zp) Exp 

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

Exp calculates x**y ("x to the yth power")

func (*Zp) Inv 

func (zp *Zp) Inv() *Zp

Set the multiplicative inverse in P.

func (*Zp) IsZero 

func (zp *Zp) IsZero() bool

IsZero returns true if the integer is zero, otherwise false.

func (*Zp) Mul 

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

Multiply two integers.

func (*Zp) Neg 

func (zp *Zp) Neg() *Zp

Additive inverse of an integer.

func (*Zp) Norm 

func (zp *Zp) Norm() *Zp

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

func (*Zp) SetBytes 

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

func (*Zp) Sub 

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

Subtract two integers.

type ZpSlice 

type ZpSlice []*Zp

func (ZpSlice) String 

func (zp ZpSlice) String() string

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.