symflux

package module
v0.0.0-...-69f1692 Latest Latest
Warning

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

 Go to latest Published: Apr 24, 2014 License: GPL-3.0 Imports: 5 Imported by: 9

README

symflux - Symetric Distributed database synchronization

A Two way synchronizing library based on casey marshal's conflux.

Copyright (C) 2014 Pruthvirajsinh Rajendrasinh Chauhan pruthvirajsinh@yahoo.com

Documentation

Overview

Package symflux 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.