wendy

README

The good little fairness widget

Wendy acts as an additional widget for an existing blockchain, and is largely agnostic to the underlying blockchain and its security assumptions. Furthermore, it is possible to apply it to the protocol only for a subset of the transactions, and thus run several independent fair markets on the same chain. We have implemented Wendy to run on a simulator to get first performance estimates. As Wendy runs parallel to the actual blockchain, the core impact it has (apart from adding some network traffic) is that some transactions are put into a later block than they would be without fairness.

This repository contains a simulation of Wendy, a protocol for implementing different concepts of fairness. This implementation is not close to production ready, but it does demonstrate how Wendy impacts performance given various parameters.

Research paper

Dr Klaus Kursawe's original research paper is available on IACR or on the Vega website. Or you can watch him talk through the paper on YouTube:

Tendermint

We are currently working on a Wendy implementation for Tendermint. Wendy is implemented as a mempool replacement.

Notes

The initial Wendy implementation can be found under v0.0.1 tag.

Documentation

Overview

Package wendy is the reference implementation of Wendy (https://eprint.iacr.org/2020/885), the Good Little Fairness Widget. The project is still under development and it has NOT been tested in production. It properly handles transactions order via a voting system. It defines its own primitive types so that it remains independent from a particular blockchain implementation. Primitive types are simple and should satisfy most implementation.

Index

• Constants
• Variables
• type Block
• type BlockingSet
  • func (set BlockingSet) String() string
• type Hash
  • func Checksum(v []byte) Hash
  • func (h Hash) String() string
• type ID
• type NewBlockOptions
• type Peer
  • func NewPeer(pub Pubkey) *Peer
  • func (p *Peer) AddVote(v *Vote) (bool, error)
  • func (p *Peer) AddVotes(vs ...*Vote) error
  • func (p *Peer) Before(tx1, tx2 Tx) bool
  • func (p *Peer) LastSeqSeen(label string) uint64
  • func (p *Peer) Seen(tx Tx) bool
  • func (p *Peer) UpdateTxSet(txs ...Tx)
• type Pubkey
  • func NewPubkeyFromID(id ID) Pubkey
  • func (pk Pubkey) Bytes() []byte
  • func (pk Pubkey) String() string
• type SignedVote
  • func NewSignedVote(key ed25519.PrivateKey, v *Vote) *SignedVote
  • func (sv *SignedVote) Verify() bool
• type SimpleTx
  • func NewSimpleTx(bytes, hash string) *SimpleTx
  • func (tx *SimpleTx) Bytes() []byte
  • func (tx *SimpleTx) Hash() Hash
  • func (tx *SimpleTx) Label() string
  • func (tx *SimpleTx) String() string
• type Tx
• type Txs
  • func NewTxs(list ...Tx) *Txs
  • func (txs *Txs) ByHash(hash Hash) Tx
  • func (txs *Txs) List() []Tx
  • func (txs *Txs) Push(tx Tx) bool
  • func (txs *Txs) RemoveByHash(hash Hash) bool
• type Validator
• type Vote
  • func NewVote(pub Pubkey, seq uint64, tx Tx) *Vote
  • func (v *Vote) Hash() Hash
  • func (v *Vote) Key() ID
  • func (v *Vote) String() string
  • func (v *Vote) WithPrevHash(hash Hash) *Vote
• type Wendy
  • func New() *Wendy
  • func (w *Wendy) AddBlock(block *Block)
  • func (w *Wendy) AddTx(tx Tx) bool
  • func (w *Wendy) AddVote(v *Vote) (bool, error)
  • func (w *Wendy) AddVotes(vs ...*Vote) error
  • func (w *Wendy) BlockingSet() BlockingSet
  • func (w *Wendy) CommitBlock(block Block)
  • func (w *Wendy) HonestMajority() int
  • func (w *Wendy) HonestParties() int
  • func (w *Wendy) IsBlocked(tx Tx) bool
  • func (w *Wendy) IsBlockedBy(tx1, tx2 Tx) bool
  • func (w *Wendy) NewBlock() *Block
  • func (w *Wendy) NewBlockWithOptions(opts NewBlockOptions) *Block
  • func (w *Wendy) UpdateValidatorSet(vs []Validator)
  • func (w *Wendy) VoteByTxHash(hash Hash) *Vote

Constants

const (
	HashLen = 32
)

Variables

var ErrVoteHashesDontMatch = errors.New("vote hashes don't match")

var (
	// Quorum defines the ratio of neccesary votes to consider something valid.
	// Changing this is uncommon but it might be required on some blockchains
	// or for testing purposes.
	Quorum = float64(2) / 3
)

var Rand = rand.New(
	rand.NewSource(time.Now().UnixNano()),
)

Rand is a random generator using `time.Now()` as the seed.

Types

type Block

type Block struct {
	Txs []Tx
}

Block holds a list of Tx.

type BlockingSet

type BlockingSet map[Hash][]Tx

func (BlockingSet) String

func (set BlockingSet) String() string

type Hash

type Hash [HashLen]byte

func Checksum

func Checksum(v []byte) Hash

Checksum returns a sha256 checksum of v

func (Hash) String

func (h Hash) String() string

type ID

type ID string

type NewBlockOptions

type NewBlockOptions struct {
	// TxLimit limits the maximum number of Txs that a produced block might
	// contain.
	TxLimit int

	// MaxBlockSize limits the maximum size of a block.
	// MaxBlockSize is set in bytes and is computed as the sum of all
	// `len(tx.Bytes())`.
	// If a tx makes exceed the BlockSize, it is removed from the block and the
	// function returns.
	// NewBlock will not try to optimize for space.
	MaxBlockSize int

	// AddBlock flag determines if the newly created block should be also added.
	AddBlock bool
}

NewBlockOptions are options that control the behaviour of NewBlock method.

type Peer

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

Peer represents a node in the network and keeps track of the votes Wendy emits. The Peer stores one state per label in a peerBucket. Peers are not safe for concurrent access. NOTE: Since the Peer never cleans up it's internal state, it always grow, hence, we might need to add a persistent storage.

func NewPeer

func NewPeer(pub Pubkey) *Peer

NewPeer returnsa new Peer instance.

func (*Peer) AddVote

func (p *Peer) AddVote(v *Vote) (bool, error)

AddVote adds a vote to the vote list. It returns true if the vote hasn't been added before, otherwise, the vote is not added and false is returned.

func (*Peer) AddVotes

func (p *Peer) AddVotes(vs ...*Vote) error

AddVotes is a helper of AddVote to add more than one vote on a single call, it ignores the return value.

func (*Peer) Before

func (p *Peer) Before(tx1, tx2 Tx) bool

Before returns true if tx1 has a lower sequence number than tx2. If tx1 and/or tx2 are not seen, Before returns false. Txs MUST belong to the same Label() otherwise Before will panic.

func (*Peer) LastSeqSeen

func (p *Peer) LastSeqSeen(label string) uint64

LastSeqSeen returns the last higher consecutive Seq number registered by a vote.

func (*Peer) Seen

func (p *Peer) Seen(tx Tx) bool

Seen returns whether a tx has been voted for or not. A Tx considered as seen iff there are no gaps befre the votes's seq number.

func (*Peer) UpdateTxSet

func (p *Peer) UpdateTxSet(txs ...Tx)

UpdateTxSet will remove from its internal state all the references to a corresponging tx present in the txs argument. updateTxSet should be called when a new block is commited. NOTE: This should interface a blockchain implementation to keep track of commited Txs.

type Pubkey

type Pubkey []byte

Pubkey represents a public key bytes.

func NewPubkeyFromID

func NewPubkeyFromID(id ID) Pubkey

NewPubkeyFromString turns a `[0x]<HEX>` (0x prefix is optional) string into a Pubkey. If the format of s is not hex encoded it panics.

func (Pubkey) Bytes

func (pk Pubkey) Bytes() []byte

func (Pubkey) String

func (pk Pubkey) String() string

String returns the string representation of the public key. This is hex encoded and 0x prefixed.

type SignedVote

type SignedVote struct {
	Signature []byte
	Data      *Vote
}

SignedVote wraps a vote with its signature.

func NewSignedVote

func NewSignedVote(key ed25519.PrivateKey, v *Vote) *SignedVote

NewSignedVote signs a vote and return it wrapped inside a SignedVote.

func (*SignedVote) Verify

func (sv *SignedVote) Verify() bool

Verify verifies the signature from SignedVote given the vote's pubkey.

type SimpleTx

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

func NewSimpleTx

func NewSimpleTx(bytes, hash string) *SimpleTx

func (*SimpleTx) Bytes

func (tx *SimpleTx) Bytes() []byte

func (*SimpleTx) Hash

func (tx *SimpleTx) Hash() Hash

func (*SimpleTx) Label

func (tx *SimpleTx) Label() string

func (*SimpleTx) String

func (tx *SimpleTx) String() string

type Tx

type Tx interface {
	Bytes() []byte
	Hash() Hash
	Label() string
}

type Txs

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

Txs keeps track of one or more Tx in order (.List()) but it also provide a fast way to locate them by Hash (.ByHash). Txs keeps unique transactions, and it discards added Txs that are duplicated. Txs is not safe for concurrent access and the caller should protect it from races.

func NewTxs

func NewTxs(list ...Tx) *Txs

NewTxs returns a new Txs and optionally initializes with Txs.

func (*Txs) ByHash

func (txs *Txs) ByHash(hash Hash) Tx

ByHash returns a Tx given its Hash, if the Tx is not found, it returns nil. ByHash provides a fast way to retrieve a Tx without iterating the whole set.

func (*Txs) List

func (txs *Txs) List() []Tx

List returns the underlying slice of pushed transactions.

func (*Txs) Push

func (txs *Txs) Push(tx Tx) bool

Push pushes a new tx to the list and returns true if the above tx hasn't been added before. If the tx has been already added, it's not added again and it returns false.

func (*Txs) RemoveByHash

func (txs *Txs) RemoveByHash(hash Hash) bool

RemoveByHash removes a Tx by its hash, it returns true if the Tx has been effectively removed and false if the Tx was not found.

type Validator

type Validator Pubkey

Validators are identified by their public key.

type Vote

type Vote struct {
	Pubkey Pubkey

	// Label is used for bucketing, it can be empty
	Label string

	// The following fields are used to produce the digest.
	// NOTE: it's hard to keep in sync these fields and the one used in
	// `digest()`.
	// When adding a Field here you'll need to add it in `digest()` too.
	// An alternative could be to define a tag on the fields to be used for the
	// digest and use reflection.
	Seq      uint64
	TxHash   Hash
	Time     time.Time
	PrevHash Hash
}

func NewVote

func NewVote(pub Pubkey, seq uint64, tx Tx) *Vote

NewVote returns a new Vote

func (*Vote) Hash

func (v *Vote) Hash() Hash

Hash returns the sha256 hash of the vote's digest, which is the same digest used for signing.

func (*Vote) Key

func (v *Vote) Key() ID

Key returns the Vote's Publickey formated as a ID.

func (*Vote) String

func (v *Vote) String() string

func (*Vote) WithPrevHash

func (v *Vote) WithPrevHash(hash Hash) *Vote

WithPrevHash returns an updated Vote with hash set as .PrevHash.

type Wendy

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

Wendy is the root of the Wendy fairness implementation. It holds a set of peers and acts as a proxy to them. Wendy keeps track of all Peers's state and aggregates them in order to do vote counting.

Invoking Wendy methods is thread safe.

func New

func New() *Wendy

New returns a new Wendy instance. Normally a mempool should hold only one instance.

func (*Wendy) AddBlock

func (w *Wendy) AddBlock(block *Block)

AddBlock will clean all the added txs (via AddTx). Once a block has been added, all the txs will be removed from Wendy, thus new blocks (NewBlock) won't return them anymore.

func (*Wendy) AddTx

func (w *Wendy) AddTx(tx Tx) bool

AddTx adds a tx to the list of tx to be mined. AddTx returns false if the tx was already added.

func (*Wendy) AddVote

func (w *Wendy) AddVote(v *Vote) (bool, error)

AddVote adds a vote to the list of votes. Votes are positioned given it's sequence number. AddVote returns alse if the vote was already added.

func (*Wendy) AddVotes

func (w *Wendy) AddVotes(vs ...*Vote) error

func (*Wendy) BlockingSet

func (w *Wendy) BlockingSet() BlockingSet

BlockingSet returns a list of blocking Txs for all the currently seen Txs.

func (*Wendy) CommitBlock

func (w *Wendy) CommitBlock(block Block)

CommitBlock iterate over the block's Txs set and remove them from Wendy's internal state. Txs present on block were probbaly added in the past via AddTx().

func (*Wendy) HonestMajority

func (w *Wendy) HonestMajority() int

HonestMajority returns the minimum number of votes required to assure that I have a honest majority (2t + 1, which is equivalent to n-t). It's also the maximum number of honest parties I can expect to have.

func (*Wendy) HonestParties

func (w *Wendy) HonestParties() int

HonestParties returns the required number of votes to be sure that at least one vote came from a honest validator. t + 1

func (*Wendy) IsBlocked

func (w *Wendy) IsBlocked(tx Tx) bool

IsBlocked identifies if it is pssible that a so-far-unknown transaction might be scheduled with priority to tx.

func (*Wendy) IsBlockedBy

func (w *Wendy) IsBlockedBy(tx1, tx2 Tx) bool

IsBlockedBy determines if tx2 might have priority over tx1. We say that tx1 is NOT blocked by tx2 if there are t+1 votes reporting tx1 before tx2.

func (*Wendy) NewBlock

func (w *Wendy) NewBlock() *Block

NewBlock produces a potential block given the computed BlockingSet. The new block will contain a set of Txs that need to go all together in the same block.

func (*Wendy) NewBlockWithOptions

func (w *Wendy) NewBlockWithOptions(opts NewBlockOptions) *Block

NewBlockWithOptions produces a potential block given the computed BlockingSet and a set of options. The new block will contain a set of Txs that need to go all together in the same block.

func (*Wendy) UpdateValidatorSet

func (w *Wendy) UpdateValidatorSet(vs []Validator)

UpdateValidatorSet updates the list of validators in the consensus. Updating the validator set might affect the value of the Quorum field. Upon updating the peers that are not in the new validator set are removed.

func (*Wendy) VoteByTxHash

func (w *Wendy) VoteByTxHash(hash Hash) *Vote

VoteByTxHash returns a vote given its tx.Hash Returns nil if the vote hasn't been seen.