tapir/primitives/auditable/auditablestore.go

package auditable

// WARNING NOTE: This is a sketch implementation, Not suitable for production use. The real auditable store is still being designed.

import (
	"encoding/base64"
	"errors"
	"git.openprivacy.ca/cwtch.im/tapir/persistence"
	"git.openprivacy.ca/cwtch.im/tapir/primitives"
	"git.openprivacy.ca/cwtch.im/tapir/primitives/core"
	"git.openprivacy.ca/openprivacy/log"
	"golang.org/x/crypto/ed25519"
	"sync"
)

// SignedProof encapsulates a signed proof
type SignedProof []byte

// Message encapsulates a message for more readable code.
type Message []byte

// State defines an array of messages.
type State struct {
	SignedProof SignedProof
	Messages    []Message
}

const (
	auditableDataStoreProtocol = "auditable-data-store"
	newMessage                 = "new-message"
	commit                     = "commit"
	collapse                   = "collapse"
)

// Store defines a cryptographically secure & auditable transcript of messages sent from multiple
// unrelated clients to a server.
type Store struct {
	state        State
	identity     primitives.Identity
	transcript   *core.Transcript
	LatestCommit []byte
	commits      map[string]int
	mutex        sync.Mutex
	db           persistence.Service
}

// Init initializes an auditable store
func (as *Store) Init(identity primitives.Identity) {
	as.identity = identity
	as.transcript = core.NewTranscript(auditableDataStoreProtocol)
	as.commits = make(map[string]int)
}

const messageBucket = "auditable-messages"

// LoadFromStorage initializes an auditable store from a DB
func (as *Store) LoadFromStorage(db persistence.Service) {
	db.Setup([]string{messageBucket})
	var messages []Message
	db.Load(messageBucket, "messages", &messages)
	log.Debugf("Loaded from Database: %v", len(messages))
	for _, message := range messages {
		as.add(message)
	}
	log.Debugf("Loaded %v Messages from the Database", len(messages))
	as.db = db
}

// Add adds a message to the auditable store
func (as *Store) Add(message Message) SignedProof {
	sp := as.add(message)
	if as.db != nil {
		as.db.Persist(messageBucket, "messages", as.state.Messages)
	}
	return sp
}

// Add adds a message to the auditable store
func (as *Store) add(message Message) SignedProof {
	as.mutex.Lock()
	defer as.mutex.Unlock()
	as.transcript.AddToTranscript(newMessage, message)
	as.LatestCommit = as.transcript.CommitToTranscript(commit)

	as.state.Messages = append(as.state.Messages, message)
	as.state.SignedProof = as.identity.Sign(as.LatestCommit)

	as.commits[base64.StdEncoding.EncodeToString(as.LatestCommit)] = len(as.state.Messages) - 1
	return as.state.SignedProof
}

// GetState returns the current auditable state
func (as *Store) GetState() State {
	as.mutex.Lock()
	defer as.mutex.Unlock()
	return as.state
}

// GetStateAfter returns the current auditable state after a given commitment
func (as *Store) GetStateAfter(commitment []byte) State {
	if commitment == nil {
		return as.GetState()
	}
	var state State
	state.Messages = as.GetMessagesAfter(commitment)
	state.SignedProof = as.identity.Sign(as.LatestCommit)
	return state
}

// GetMessagesAfter provides access to messages after the given commit.
func (as *Store) GetMessagesAfter(latestCommit []byte) []Message {
	as.mutex.Lock()
	defer as.mutex.Unlock()
	index, ok := as.commits[base64.StdEncoding.EncodeToString(latestCommit)]
	if !ok && len(latestCommit) == 32 {
		return []Message{}
	} else if len(latestCommit) == 0 {
		index = -1
	}
	return as.state.Messages[index+1:]
}

// AppendState merges a given state onto our state, first verifying that the two transcripts align
func (as *Store) AppendState(state State) error {
	next := len(as.state.Messages)
	for i, m := range state.Messages {
		as.state.Messages = append(as.state.Messages, m)

		// We reconstruct the transcript
		as.transcript.AddToTranscript(newMessage, m)
		as.LatestCommit = as.transcript.CommitToTranscript(commit)
		log.Debugf("Adding message %d commit: %x", next+i, as.LatestCommit)
		as.commits[base64.StdEncoding.EncodeToString(as.LatestCommit)] = next + i
	}

	// verify that our state matches the servers signed state
	// this is *not* a security check, as a rogue server can simply sign any state
	// however committing to a state allows us to build fraud proofs for malicious servers later on.
	if !ed25519.Verify(as.identity.PublicKey(), as.LatestCommit, state.SignedProof) {
		return errors.New("state is not consistent, the server is malicious")
	}
	return nil
}

// MergeState merges a given state onto our state, first verifying that the two transcripts align
func (as *Store) MergeState(state State) error {
	return as.AppendState(State{Messages: state.Messages[len(as.state.Messages):], SignedProof: state.SignedProof})
}

// VerifyFraudProof  - the main idea behind this is as follows:
//
// Every update requires the server to sign, and thus commit to, a transcript
// Clients reconstruct the transcript via MergeState, as such clients can keep track of every commit.
// if a client can present a signed transcript commit from the server that other clients do not have, it is proof
// that either 1) they are out of sync with the server or 2) the server is presenting different transcripts to different people
//
// If, after syncing, the FraudProof still validates, then the server must be malicious.
// the information revealed by publicizing a fraud proof is minimal it only reveals the inconsistent transcript commit
// and not the cause (which could be reordered messages, dropped messages, additional messages or any combination)
func (as *Store) VerifyFraudProof(fraudCommit []byte, signedFraudProof SignedProof, key ed25519.PublicKey) (bool, error) {

	if !ed25519.Verify(key, fraudCommit, signedFraudProof) {
		// This could happen due to misuse of this function (trying to verify a proof with the wrong public key)
		// This could happen if the server lies to us and submits a fake state proof, however we cannot use this to
		// prove that the server is acting maliciously
		return false, errors.New("signed proof has not been signed by the given public key")
	}

	_, exists := as.commits[base64.StdEncoding.EncodeToString(fraudCommit)]
	if !exists {
		// We have a message signed by the server which verifies that a message was inserted into the state at a given index
		// However this directly contradicts our version of the state.
		// There is still a possibility that we are out of sync with the server and that new messages have since been added
		// We assume that the caller has first Merged the most recent state.
		return true, nil
	}

	return false, nil
}

// Collapse constructs a verifiable proof stating that the server has collapsed the previous history into the current
// root = H(onion)
// L = H(Sign(LatestCommit))
func (as *Store) Collapse() {
	as.LatestCommit = as.identity.Sign(as.transcript.CommitToTranscript(collapse))
}