conflux.v2: gopkg.in/hockeypuck/conflux.v2 Index | Files | Directories

package conflux

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

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

Package Files

bitstring.go decode.go matrix.go poly.go zp.go

Variables

var ErrInterpolate = errors.New("interpolation failed")
var ErrLowMBar = errors.New("low MBar")
var ErrMatrixTooNarrow = errors.New("matrix is too narrow to reduce")
var ErrPowModSmallN = errors.New("PowMod not implemented for small values of N")
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.

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.

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.

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.

var P_SKS *big.Int

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

func IsInterpolateFailure Uses

func IsInterpolateFailure(err error) bool

func Zarray Uses

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

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

func Zpoints Uses

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

Generate points for rational function interpolation.

type Bitstring Uses

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

Bitstring describes a sequence of bits.

func NewBitstring Uses

func NewBitstring(bits int) *Bitstring

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

func NewZpBitstring Uses

func NewZpBitstring(zp *Zp) *Bitstring

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

func (*Bitstring) BitLen Uses

func (bs *Bitstring) BitLen() int

BitLen returns the number of bits in the Bitstring.

func (*Bitstring) ByteLen Uses

func (bs *Bitstring) ByteLen() int

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

func (*Bitstring) Bytes Uses

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

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

func (*Bitstring) Clear Uses

func (bs *Bitstring) Clear(bit int)

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

func (*Bitstring) Flip Uses

func (bs *Bitstring) Flip(bit int)

Flip inverts the bit at the given position.

func (*Bitstring) Get Uses

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 Uses

func (bs *Bitstring) Lsh(n uint)

Lsh shifts all bits to the left by one position.

func (*Bitstring) Rsh Uses

func (bs *Bitstring) Rsh(n uint)

Rsh shifts all bits to the right by one position.

func (*Bitstring) Set Uses

func (bs *Bitstring) Set(bit int)

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

func (*Bitstring) SetBytes Uses

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 Uses

func (bs *Bitstring) String() string

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

type Matrix Uses

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

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

func NewMatrix Uses

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

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

func (*Matrix) Get Uses

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

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

func (*Matrix) Reduce Uses

func (m *Matrix) Reduce() error

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

func (*Matrix) Set Uses

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

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

func (*Matrix) String Uses

func (m *Matrix) String() string

String returns a string representation of the matrix.

type Poly Uses

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

Poly represents a polynomial in a finite field.

func NewPoly Uses

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 Uses

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

PolyDiv returns the quotient between two Polys.

func PolyDivmod Uses

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

PolyDivmod returns the quotient and remainder between two Polys.

func PolyGcd Uses

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

PolyGcd returns the greatest common divisor between two Polys.

func PolyMod Uses

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

PolyDiv returns the mod function between two Polys.

func PolyRand Uses

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 Uses

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

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

func (*Poly) Add Uses

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 Uses

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 Uses

func (p *Poly) Copy() *Poly

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

func (*Poly) Degree Uses

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 Uses

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

Equal compares with another polynomial for equality.

func (*Poly) Eval Uses

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

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

func (*Poly) Factor Uses

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 Uses

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

IsConstant returns whether the Poly is just a constant value.

func (*Poly) Mul Uses

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

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

func (*Poly) Neg Uses

func (p *Poly) Neg() *Poly

Neg negates the Poly, returning the result.

func (*Poly) P Uses

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

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

func (*Poly) String Uses

func (p *Poly) String() string

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

func (*Poly) Sub Uses

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

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

type RationalFn Uses

type RationalFn struct {
    Num   *Poly
    Denom *Poly
}

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

func Interpolate Uses

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 Uses

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

ZSet is a set of integers in a finite field.

func NewZSet Uses

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

NewZSet returns a new ZSet containing the given elements.

func Reconcile Uses

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.

func ZSetDiff Uses

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 Uses

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

Add adds an element to the set.

func (*ZSet) AddAll Uses

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

AddAll adds all elements in another set.

func (*ZSet) AddSlice Uses

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

AddSlice adds all the given elements to the set.

func (*ZSet) Equal Uses

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

Equal returns whether this set is equal to another set.

func (*ZSet) Has Uses

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

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

func (*ZSet) Items Uses

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

Items returns a slice of all elements in the set.

func (*ZSet) Len Uses

func (zs *ZSet) Len() int

Len returns the length of the set.

func (*ZSet) Remove Uses

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

Remove removes an element from the set.

func (*ZSet) RemoveAll Uses

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

RemoveAll removes all elements in another set from this one.

func (*ZSet) RemoveSlice Uses

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

RemoveSlice removes all the given elements from the set.

func (*ZSet) String Uses

func (zs *ZSet) String() string

String returns a string representation of the set.

type Zp Uses

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 Uses

func Z(p *big.Int) *Zp

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

func Zb Uses

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

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

func Zi Uses

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

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

func Zrand Uses

func Zrand(p *big.Int) *Zp

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

func Zs Uses

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

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

func Zzp Uses

func Zzp(zp *Zp) *Zp

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

func (*Zp) Add Uses

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 Uses

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

Bytes returns the byte representation of Zp.

func (*Zp) Cmp Uses

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

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

func (*Zp) Copy Uses

func (zp *Zp) Copy() *Zp

Copy returns a new Zp instance with the same value.

func (*Zp) Div Uses

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 Uses

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 Uses

func (zp *Zp) Inv() *Zp

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

func (*Zp) IsZero Uses

func (zp *Zp) IsZero() bool

IsZero returns whether the integer is zero.

func (*Zp) Mul Uses

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 Uses

func (zp *Zp) Neg() *Zp

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

func (*Zp) Norm Uses

func (zp *Zp) Norm() *Zp

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

func (*Zp) SetBytes Uses

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

SetBytes sets the integer from its byte representation.

func (*Zp) Sub Uses

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

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

type ZpSlice Uses

type ZpSlice []*Zp

ZpSlice is a collection of integers in a finite field.

func (ZpSlice) String Uses

func (zp ZpSlice) String() string

String returns a string representation of the ZpSlice.

Directories

PathSynopsis
reconPackage recon provides the SKS reconciliation protocol, prefix tree interface and an in-memory prefix-tree implementation.
recon/leveldbPackage leveldb provides a key-value storage implementation of the recon prefix tree interface.
recon/testingPackage testing provides some unit-testing support functions.

Package conflux imports 6 packages (graph) and is imported by 11 packages. Updated 2016-07-16. Refresh now. Tools for package owners.