Merge "x/ref/services/syncbase: Update Glob implementation"
diff --git a/x/ref/services/syncbase/signing/hashcache/hashcache.go b/x/ref/services/syncbase/signing/hashcache/hashcache.go
new file mode 100644
index 0000000..26e8c94
--- /dev/null
+++ b/x/ref/services/syncbase/signing/hashcache/hashcache.go
@@ -0,0 +1,77 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package hashcache implements a simple cache intended to be indexed by hash
+// values. The keys are of type []byte. Values are arbitrary interface{}
+// values. Entries may expire if not used for a duration specified by the
+// client.
+package hashcache
+
+import "sync"
+import "time"
+
+// An internalValue is the client's data plus the data's expiry time.
+type internalValue struct {
+ data interface{}
+ expiry time.Time
+}
+
+// A Cache allows the user to store arbitrary values, keyed by the contents of
+// byte vectors. Entries may be added, deleted, and looked up. They may
+// expire if not used.
+type Cache struct {
+ expiry time.Duration
+ mu sync.Mutex // protects fields below.
+ entries map[string]*internalValue
+ insertionsSinceGC int // number of insertions since last GC
+}
+
+// New() returns a pointer to a new, empty Cache.
+// Entries may expire if not used for "expiry".
+func New(expiry time.Duration) *Cache {
+ return &Cache{expiry: expiry, entries: make(map[string]*internalValue)}
+}
+
+// Lookup() returns the data associated with key[] in *c, and whether there is
+// such a value. The client may not modify the returned data; it is shared
+// with *c.
+func (c *Cache) Lookup(key []byte) (data interface{}, isPresent bool) {
+ var value *internalValue
+ c.mu.Lock()
+ value, isPresent = c.entries[string(key)]
+ if isPresent {
+ value.expiry = time.Now().Add(c.expiry)
+ data = value.data
+ }
+ c.mu.Unlock()
+ return data, isPresent
+}
+
+// Add() associates data with key[] in *c. Any data previously associated with
+// key[] are forgotten. The implementation may discard the association at some
+// future time (set by NewCache()) to limit the size of the cache. data may
+// not be modified after this call; it is shared with *c.
+func (c *Cache) Add(key []byte, data interface{}) {
+ c.mu.Lock()
+ now := time.Now()
+ c.entries[string(key)] = &internalValue{data: data, expiry: now.Add(c.expiry)}
+ c.insertionsSinceGC++
+ // Scan to expire entries if 20% were added since last scan.
+ if c.insertionsSinceGC*5 > len(c.entries) {
+ for ik, iv := range c.entries {
+ if iv.expiry.Before(now) {
+ delete(c.entries, ik)
+ }
+ }
+ c.insertionsSinceGC = 0
+ }
+ c.mu.Unlock()
+}
+
+// Delete() removes any association of data with key[] in *c.
+func (c *Cache) Delete(key []byte) {
+ c.mu.Lock()
+ delete(c.entries, string(key))
+ c.mu.Unlock()
+}
diff --git a/x/ref/services/syncbase/signing/hashcache/hashcache_test.go b/x/ref/services/syncbase/signing/hashcache/hashcache_test.go
new file mode 100644
index 0000000..96ba865
--- /dev/null
+++ b/x/ref/services/syncbase/signing/hashcache/hashcache_test.go
@@ -0,0 +1,83 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package hashcache_test tests the hashcache package.
+package hashcache_test
+
+import "runtime"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/hashcache"
+
+// checkHashesWithNoData() checks that hash[start:] have no data in the cache.
+// (The start index is passed, rather than expecting the caller to sub-slice,
+// so that error messages refer to the index.)
+func checkHashesWithNoData(t *testing.T, cache *hashcache.Cache, start int, hash [][]byte) {
+ _, _, callerLine, _ := runtime.Caller(1)
+ for i := start; i != len(hash); i++ {
+ value, found := cache.Lookup(hash[i])
+ if value != nil || found {
+ t.Errorf("line %d: unset cache entry hash[%d]=%v has value %v, but is expected not to be set", callerLine, i, hash[i], value)
+ }
+ }
+}
+
+func TestCache(t *testing.T) {
+ hash := [][]byte{
+ []byte{0x00, 0x01, 0x02, 0x3},
+ []byte{0x04, 0x05, 0x06, 0x7},
+ []byte{0x08, 0x09, 0x0a, 0xb}}
+ var value interface{}
+ var found bool
+ var want string
+
+ cache := hashcache.New(5 * time.Second)
+
+ // The cache should initially have none of the keys.
+ checkHashesWithNoData(t, cache, 0, hash)
+
+ // Add the first key, and check that it's there.
+ want = "hash0"
+ cache.Add(hash[0], want)
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ checkHashesWithNoData(t, cache, 1, hash)
+
+ // Add the second key, and check that both it and the first key are there.
+ want = "hash1"
+ cache.Add(hash[1], want)
+ value, found = cache.Lookup(hash[1])
+ if s, ok := value.(string); !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 1, hash[1], s, want)
+ }
+ want = "hash0"
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ checkHashesWithNoData(t, cache, 2, hash)
+
+ // Wait for all entries to time out.
+ time.Sleep(6 * time.Second) // sleep past expiry time
+
+ // Add the first key again, and so many that it will trigger garbage
+ // collection.
+ for i := 0; i != 10; i++ {
+ want = "hash0 again"
+ cache.Add(hash[0], want)
+ value, found = cache.Lookup(hash[0])
+ if s, ok := value.(string); !found || !ok || s != want {
+ t.Errorf("cache entry hash[%d]=%v got %v, want %v", 0, hash[0], s, want)
+ }
+ }
+ // The entry for hash1 should have expired, since the expiry time has
+ // passed, and many things have been inserted into the cache.
+ checkHashesWithNoData(t, cache, 1, hash)
+
+ cache.Delete(hash[0])
+ checkHashesWithNoData(t, cache, 0, hash)
+}
diff --git a/x/ref/services/syncbase/signing/krl/krl.go b/x/ref/services/syncbase/signing/krl/krl.go
new file mode 100644
index 0000000..422f53e
--- /dev/null
+++ b/x/ref/services/syncbase/signing/krl/krl.go
@@ -0,0 +1,39 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package krl implements a trivial, in-memory key revocation list.
+// It is a placeholder for a real key revocation mechanism.
+package krl
+
+import "crypto/sha256"
+import "time"
+
+// A KRL is a key revocation list. It maps the hashes of keys that have been revoked
+// to revocation times.
+type KRL struct {
+ table map[[sha256.Size]byte]time.Time
+}
+
+var notYetRevoked = time.Now().Add(100 * 365 * 24 * time.Hour) // far future
+
+// New() returns a pointer to a new, empty key recovation list.
+func New() *KRL {
+ return &KRL{table: make(map[[sha256.Size]byte]time.Time)}
+}
+
+// Revoke() inserts an entry into *krl recording that key[] was revoked at time
+// "when".
+func (krl *KRL) Revoke(key []byte, when time.Time) {
+ krl.table[sha256.Sum256(key)] = when
+}
+
+// RevocationTime() returns the revocation time for key[].
+// If key[] is not in the list, a time in the far future is returned.
+func (krl *KRL) RevocationTime(key []byte) (whenRevoked time.Time) {
+ var found bool
+ if whenRevoked, found = krl.table[sha256.Sum256(key)]; !found {
+ whenRevoked = notYetRevoked
+ }
+ return whenRevoked
+}
diff --git a/x/ref/services/syncbase/signing/krl/krl_test.go b/x/ref/services/syncbase/signing/krl/krl_test.go
new file mode 100644
index 0000000..73f48ad
--- /dev/null
+++ b/x/ref/services/syncbase/signing/krl/krl_test.go
@@ -0,0 +1,54 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package krl tests the key revocation list package.
+package krl_test
+
+import "runtime"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+
+// checkKeysNotRevoked() checks that key[start:] have not been revoked. (The
+// start index is passed, rather than expecting the called to sub-slice, so
+// that error messages refer to the expected index.)
+func checkKeysNotRevoked(t *testing.T, krl *krl.KRL, start int, key [][]byte, now time.Time) {
+ _, _, callerLine, _ := runtime.Caller(1)
+ year := 365 * 24 * time.Hour
+ for i := start; i != len(key); i++ {
+ revoked := krl.RevocationTime(key[i])
+ if revoked.Before(now.Add(year)) {
+ t.Errorf("line %d: unrevoked key[%d]=%v has revocation time %v, which is not far enough in the future", callerLine, i, key[i], revoked)
+ }
+ }
+}
+
+func TestKRL(t *testing.T) {
+ now := time.Now()
+ key := [][]byte{
+ []byte{0x00, 0x01, 0x02, 0x3},
+ []byte{0x04, 0x05, 0x06, 0x7},
+ []byte{0x08, 0x09, 0x0a, 0xb}}
+ var revoked time.Time
+
+ krl := krl.New()
+
+ checkKeysNotRevoked(t, krl, 0, key, now)
+
+ krl.Revoke(key[0], now)
+ if revoked = krl.RevocationTime(key[0]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[0], revoked, now)
+ }
+ checkKeysNotRevoked(t, krl, 1, key, now)
+
+ krl.Revoke(key[1], now)
+ if revoked = krl.RevocationTime(key[0]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[0], revoked, now)
+ }
+ if revoked = krl.RevocationTime(key[1]); !revoked.Equal(now) {
+ t.Errorf("unrevoked key %v has revocation time %v, but expected %v", key[1], revoked, now)
+ }
+ checkKeysNotRevoked(t, krl, 2, key, now)
+}
diff --git a/x/ref/services/syncbase/signing/signeddata.vdl b/x/ref/services/syncbase/signing/signeddata.vdl
new file mode 100644
index 0000000..4b4ceb8
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signeddata.vdl
@@ -0,0 +1,72 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package signing
+
+import "v.io/v23/security"
+
+// A DataWithSignature represents a signed, and possibily validated, collection
+// of Item structs.
+//
+// If IsValidated==false and the AuthorSigned signature is valid, it means:
+// The signer whose Blessings have hash BlessingsHash asserts Data.
+//
+// If IsValidated==true and both AuthorSigned and ValidatorSigned signatures are is valid,
+// it means both:
+// 1) The signer whose Blessings b have hash BlessingsHash asserts Data.
+// 2) If vd is the ValidatorData with hash ValidatorDataHash, the owner of
+// vd.PublicKey asserts that it checked that at least the names vd.Names[] were
+// valid in b.
+//
+// The sender obtains:
+// - BlessingsHash (and the wire form of the blessings) with ValidationCache.AddBlessings().
+// - ValidatorDataHash (and the wire form of the ValidataData) with ValidationCache.AddValidatorData().
+//
+// The receiver looks up:
+// - BlessingsHash with ValidationCache.LookupBlessingsData()
+// - ValidatorDataHash with ValidationCache.LookupValidatorData()
+//
+// If not yet there, the receiver inserts the valus into its ValidationCache with:
+// - ValidationCache.AddWireBlessings()
+// - ValidationCache.AddValidatorData()
+type DataWithSignature struct {
+ Data []Item
+ // BlessingsHash is a key for the validation cache; the corresponding
+ // cached value is a security.Blessings.
+ BlessingsHash []byte
+ // AuthorSigned is the signature of Data and BlessingsHash using the
+ // private key associated with the blessings hashed in BlessingsHash.
+ AuthorSigned security.Signature
+
+ IsValidated bool // Whether fields below are meaningful.
+
+ // ValidatorDataHash is a key for the validation cache returned by
+ // ValidatorData.Hash(); the corresponding cached value is the
+ // ValidatorData.
+ ValidatorDataHash []byte
+ ValidatorSigned security.Signature
+}
+
+// An Item represents either a marshalled data item or its SHA-256 hash.
+// The Data field is a []byte, rather than an "any" to make signatures
+// determistic. VOM encoding is not deterministic for two reasons:
+// - map elements may be marshalled in any order
+// - different versions of VOM may marshal in different ways.
+// Thus, the initial producer of a data item marshals the data once, and it is
+// this marshalled form that is transmitted from device to device. If the
+// data were unmarshalled and then remarsahalled, the signatures might not
+// match. The Hash field is used instead of the Data field when the recipient
+// of the DataWithSignature is not permitted to see certain Items' Data
+// fields.
+type Item union {
+ Data []byte // Marshalled form of data.
+ Hash []byte // Hash of what would have been in Data, as returned by SumByteVectorWithLength(Data).
+}
+
+// WireValidatorData is the wire form of ValidatorData.
+// It excludes the unmarshalled form of the public key.
+type WireValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
diff --git a/x/ref/services/syncbase/signing/signeddata.vdl.go b/x/ref/services/syncbase/signing/signeddata.vdl.go
new file mode 100644
index 0000000..f96fe50
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signeddata.vdl.go
@@ -0,0 +1,128 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file was auto-generated by the vanadium vdl tool.
+// Source: signeddata.vdl
+
+package signing
+
+import (
+ // VDL system imports
+ "v.io/v23/vdl"
+
+ // VDL user imports
+ "v.io/v23/security"
+)
+
+// A DataWithSignature represents a signed, and possibily validated, collection
+// of Item structs.
+//
+// If IsValidated==false and the AuthorSigned signature is valid, it means:
+// The signer whose Blessings have hash BlessingsHash asserts Data.
+//
+// If IsValidated==true and both AuthorSigned and ValidatorSigned signatures are is valid,
+// it means both:
+// 1) The signer whose Blessings b have hash BlessingsHash asserts Data.
+// 2) If vd is the ValidatorData with hash ValidatorDataHash, the owner of
+// vd.PublicKey asserts that it checked that at least the names vd.Names[] were
+// valid in b.
+//
+// The sender obtains:
+// - BlessingsHash (and the wire form of the blessings) with ValidationCache.AddBlessings().
+// - ValidatorDataHash (and the wire form of the ValidataData) with ValidationCache.AddValidatorData().
+//
+// The receiver looks up:
+// - BlessingsHash with ValidationCache.LookupBlessingsData()
+// - ValidatorDataHash with ValidationCache.LookupValidatorData()
+//
+// If not yet there, the receiver inserts the valus into its ValidationCache with:
+// - ValidationCache.AddWireBlessings()
+// - ValidationCache.AddValidatorData()
+type DataWithSignature struct {
+ Data []Item
+ // BlessingsHash is a key for the validation cache; the corresponding
+ // cached value is a security.Blessings.
+ BlessingsHash []byte
+ // AuthorSigned is the signature of Data and BlessingsHash using the
+ // private key associated with the blessings hashed in BlessingsHash.
+ AuthorSigned security.Signature
+ IsValidated bool // Whether fields below are meaningful.
+ // ValidatorDataHash is a key for the validation cache returned by
+ // ValidatorData.Hash(); the corresponding cached value is the
+ // ValidatorData.
+ ValidatorDataHash []byte
+ ValidatorSigned security.Signature
+}
+
+func (DataWithSignature) __VDLReflect(struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.DataWithSignature"`
+}) {
+}
+
+type (
+ // Item represents any single field of the Item union type.
+ //
+ // An Item represents either a marshalled data item or its SHA-256 hash.
+ // The Data field is a []byte, rather than an "any" to make signatures
+ // determistic. VOM encoding is not deterministic for two reasons:
+ // - map elements may be marshalled in any order
+ // - different versions of VOM may marshal in different ways.
+ // Thus, the initial producer of a data item marshals the data once, and it is
+ // this marshalled form that is transmitted from device to device. If the
+ // data were unmarshalled and then remarsahalled, the signatures might not
+ // match. The Hash field is used instead of the Data field when the recipient
+ // of the DataWithSignature is not permitted to see certain Items' Data
+ // fields.
+ Item interface {
+ // Index returns the field index.
+ Index() int
+ // Interface returns the field value as an interface.
+ Interface() interface{}
+ // Name returns the field name.
+ Name() string
+ // __VDLReflect describes the Item union type.
+ __VDLReflect(__ItemReflect)
+ }
+ // ItemData represents field Data of the Item union type.
+ ItemData struct{ Value []byte } // Marshalled form of data.
+ // ItemHash represents field Hash of the Item union type.
+ ItemHash struct{ Value []byte } // Hash of what would have been in Data, as returned by SumByteVectorWithLength(Data).
+ // __ItemReflect describes the Item union type.
+ __ItemReflect struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.Item"`
+ Type Item
+ Union struct {
+ Data ItemData
+ Hash ItemHash
+ }
+ }
+)
+
+func (x ItemData) Index() int { return 0 }
+func (x ItemData) Interface() interface{} { return x.Value }
+func (x ItemData) Name() string { return "Data" }
+func (x ItemData) __VDLReflect(__ItemReflect) {}
+
+func (x ItemHash) Index() int { return 1 }
+func (x ItemHash) Interface() interface{} { return x.Value }
+func (x ItemHash) Name() string { return "Hash" }
+func (x ItemHash) __VDLReflect(__ItemReflect) {}
+
+// WireValidatorData is the wire form of ValidatorData.
+// It excludes the unmarshalled form of the public key.
+type WireValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
+
+func (WireValidatorData) __VDLReflect(struct {
+ Name string `vdl:"v.io/syncbase/x/ref/services/syncbase/signing.WireValidatorData"`
+}) {
+}
+
+func init() {
+ vdl.Register((*DataWithSignature)(nil))
+ vdl.Register((*Item)(nil))
+ vdl.Register((*WireValidatorData)(nil))
+}
diff --git a/x/ref/services/syncbase/signing/signing.go b/x/ref/services/syncbase/signing/signing.go
new file mode 100644
index 0000000..0115f37
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signing.go
@@ -0,0 +1,358 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package signing signs syncbase updates using public key signatures, and
+// allows these signatures to be checked on other nodes.
+//
+// The functionality is geared specifically towards syncbase synchronization
+// because it is designed to allow a signature to remain valid during its
+// propagation across the syncgroup once it has been accepted by at least one
+// member of a syncgroup, even if the original key or its blessings are
+// invalidated in the meantime.
+//
+// There are three types of participant:
+// - an "author", which creates an update, and signs it with Sign().
+// - one or more "validators", each of which receives a change directly from
+// the author, and applies Check() to validate it.
+// - zero or more "checkers', each of whom receives a change from a validator
+// or another checker, and applied Check() to check it.
+//
+// A validator checks the signature and blessings provided by the author, and
+// then appends its own signature, vouching for the fact that the author's
+// signature was good at the time the validator saw it.
+//
+// A checker checks the signatures of both the author and validator but uses
+// weaker checks for signature validity than a validator. In particular, it
+// uses a significant grace period for key expiry so that a change admitted to
+// the syncgroup by a validator has an opportunity to propagate to all the
+// nodes in the syncgroup if the keys or blessings are revoked after the change
+// is admitted, but before it is fully propagated. The intent is that the
+// grace period be chosen to be greater than the diameter of the syncgroup
+// (measured in time). One way to ensure that is to insist that members sync
+// with a central server at least every T time units, and make the grace period
+// be 2T. The central server may sign the data anew to allow new members to pick
+// it up.
+//
+// The model is further complicated by performance concerns. An update written
+// to syncbase might be quite small (perhaps tens of bytes) but:
+// a) a public key signature or verification can take on the order of a
+// millisecond. (Currently, ECDSA signing might a little under 1ms and
+// verification just over 2ms on a workstation. A checker performs two such
+// verifications.)
+// b) unmarshalling even a simple Blessings object can take milliseconds. (!)
+// c) marshalling a public key can take 10us.
+// d) a Blessings object is of the order of a kilobyte of more, which may
+// represent substantial space overhead if duplicated.
+//
+// Because of (a), we wish to batch syncbase updates, so that a single
+// signature check applies to several updates. Thus the Data in a
+// DataWithSignature is a vector of Item, rather than a single Item.
+//
+// However, we will not always wish to put all updates in the same batch. For
+// example, an author and a validator might share two different syncgroups with
+// different memberships. In such a case, the author might keep the batches
+// for one syncgoup separate from batches for the other syncgroup, even though
+// the author blessings and validator identities are the same for all the
+// batches. Thus, because of (b,c,d), it's worth decoupling the author's
+// Blessings data and the validator's key data separately from the signed
+// batches itself, so that the blessings and validator data can be processed
+// once, even though several batches of updates are being sent. A
+// ValidationCache is used to hold this data separately, and allow it to be
+// sent just once, rather than once per signature.
+//
+// Lastly, imagine that the author sends a batch of 10 updates to a validator,
+// and the validator then syncs with a checker that is permitted to see only
+// half of the updates; perhaps ACLs prevent if from seeing the others. This
+// requires that the signature on the batch remain valid even if some of the
+// updates in the batch are removed. This is accomplished via the Item type,
+// which is a VDL union type that contains either the bytes of the marshalled
+// form of the update, or (if the update must not be sent) the SHA-256 hash of
+// the data (which can be computed with SumByteVectorWithLength()).
+package signing
+
+import "bytes"
+import "crypto/sha256"
+import "encoding/binary"
+import "hash"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+import "v.io/v23/context"
+import "v.io/v23/security"
+import "v.io/v23/verror"
+
+const pkgPath = "v.io/syncbase/x/ref/services/syncbase/signing"
+
+// These are among the errors may be returned by Check(), and indicate that the
+// operation should be retried when new data has been added to the
+// ValidationCache. The errors are public to make it easier for the client to
+// test for them.
+var (
+ ErrNeedAuthorBlessingsAndValidatorDataForHash = verror.Register(
+ pkgPath+".ErrNeedAuthorBlessingsAndValidatorDataForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache contains neither the author blessings nor the validator data{:_}")
+ ErrNeedAuthorBlessingsForHash = verror.Register(
+ pkgPath+".ErrNeedAuthorBlessingsForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache does not contain the author blessings{:_}")
+ ErrNeedValidatorDataForHash = verror.Register(
+ pkgPath+".ErrNeedValidatorDataForHash",
+ verror.RetryRefetch,
+ "{1:}{2:} The ValidationCache does not contain the validator data{:_}")
+)
+
+// These errors are less likely to be tested for, and so are not exported.
+var (
+ errAuthorKeyIsRevoked = verror.Register(
+ pkgPath+".errAuthorKeyIsRevoked",
+ verror.NoRetry,
+ "{1:}{2:} The author key has been revoked{:_}")
+ errBadAuthorSignature = verror.Register(
+ pkgPath+".errBadAuthorSignature",
+ verror.NoRetry,
+ "{1:}{2:} Author signature verification failed{:_}")
+ errBadValidatorSignature = verror.Register(
+ pkgPath+".errBadValidatorSignature",
+ verror.NoRetry,
+ "{1:}{2:} Validator signature verification failed{:_}")
+ errAuthorBlessingsHaveNoValidNames = verror.Register(
+ pkgPath+".errAuthorBlessingsHaveNoValidNames",
+ verror.NoRetry,
+ "{1:}{2:} Author Blessings have no valid names{:_}")
+ errMayNotValidateOwnSignature = verror.Register(
+ pkgPath+".errMayNotValidateOwnSignature",
+ verror.NoRetry,
+ "{1:}{2:} Author may not validate its own signature{:_}")
+ errSenderIsNotAuthor = verror.Register(
+ pkgPath+".errSenderIsNotAuthor",
+ verror.NoRetry,
+ "{1:}{2:} Author is not sender of RPC; will not validate{:_}")
+ errValidatesWrongNames = verror.Register(
+ pkgPath+".errValidatesWrongNames",
+ verror.NoRetry,
+ "{1:}{2:} The validated names are not a subset of the names sent by the checker{:_}")
+ errValidatorIsSigner = verror.Register(
+ pkgPath+".errValidatorIsSigner",
+ verror.NoRetry,
+ "{1:}{2:} The signature was validated by its author; treating as invalid{:_}")
+ errValidatorKeyIsRevoked = verror.Register(
+ pkgPath+".errValidatorKeyIsRevoked",
+ verror.NoRetry,
+ "{1:}{2:} The validator key is revoked{:_}")
+)
+
+// --------------------------------------------
+
+// SignData() uses authorPrincipal to sign data using blessings (which must be
+// associated with the authorPrincipal). A pointer to a newly constructed
+// DataWithSignature with IsValidated==false is returned. Ensures that the
+// blessings are stored in *cache. Typically, "authorPrincipal" is obtained from
+// v23.GetPrincipal(ctx).
+//
+// If a recipient of the result *d complains that it does not understand the
+// hash d.BlessingHash, the signer should present it with
+// blessingsData.MarshalledBlessings, which will allow the recipient to
+// construct the Blessings. The Blessings are transmitted out of line because
+// they are large, and may be reused for multiple signatures.
+func SignData(ctx *context.T, cache *ValidationCache, authorPrincipal security.Principal,
+ blessings security.Blessings, data []Item) (d *DataWithSignature, blessingsData *BlessingsData, err error) {
+
+ d = new(DataWithSignature)
+ d.Data = data
+ d.BlessingsHash, blessingsData, err = cache.AddBlessings(ctx, blessings)
+ if err == nil {
+ d.AuthorSigned, err = authorPrincipal.Sign(d.authorSignatureHash())
+ }
+ return d, blessingsData, err
+}
+
+// hashByteVectorWithLength() calls hasher.Write() on a representation of
+// len(b), followed by the contents of b.
+func hashByteVectorWithLength(hasher hash.Hash, b []byte) {
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(b)))
+ hasher.Write(length[:])
+ hasher.Write(b)
+}
+
+// SumByteVectorWithLength() returns a SHA-256 hash of
+// len(b), followed by the contents of b.
+func SumByteVectorWithLength(b []byte) []byte {
+ hasher := sha256.New()
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(b)))
+ hasher.Write(length[:])
+ hasher.Write(b)
+ return hasher.Sum(nil)[:]
+}
+
+// authorSignatureHash() returns the hash that the author should sign.
+func (d *DataWithSignature) authorSignatureHash() []byte {
+ hasher := sha256.New()
+ var length [8]byte
+ binary.LittleEndian.PutUint64(length[:], uint64(len(d.Data)))
+ hasher.Write(length[:])
+ for i := range d.Data {
+ if data, gotData := d.Data[i].(ItemData); gotData {
+ hasher.Write(SumByteVectorWithLength(data.Value))
+ } else if hash, gotHash := d.Data[i].(ItemHash); gotHash {
+ hasher.Write(hash.Value)
+ } else {
+ // d.Data is neither a Data nor a Hash. This shouldn't
+ // happen unless the mashalled data is somehow
+ // corrupted. The signature will not match unless the
+ // original author of the data was seeing the same.
+ hasher.Write([]byte("no data"))
+ }
+ }
+ hashByteVectorWithLength(hasher, d.BlessingsHash)
+ return hasher.Sum(nil)[:]
+}
+
+// validatorSignatureHash() returns the hash that the validator should sign,
+// given the hash that the author signed.
+func (d *DataWithSignature) validatorSignatureHash(authorSignatureHash []byte) []byte {
+ var buffer [32]byte
+ var buf []byte = buffer[:]
+ if len(d.AuthorSigned.Hash) > len(buf) {
+ buf = make([]byte, len(d.AuthorSigned.Hash))
+ }
+ hasher := sha256.New()
+ hashByteVectorWithLength(hasher, authorSignatureHash)
+ hashByteVectorWithLength(hasher, d.AuthorSigned.Purpose)
+ hashByteVectorWithLength(hasher, buf[:copy(buf, d.AuthorSigned.Hash)])
+ hashByteVectorWithLength(hasher, d.AuthorSigned.R)
+ hashByteVectorWithLength(hasher, d.AuthorSigned.S)
+ hashByteVectorWithLength(hasher, d.ValidatorDataHash)
+ return hasher.Sum(nil)[:]
+}
+
+// Check() verifies the signature(s) on *d:
+//
+// If d.IsValidated==false, checks that:
+// 1. the author's signature is available in *cache.
+// 2. the author's signature over its blessings and the data is
+// cyprotgraphically valid.
+// 3. security.SigningBlessingNames() yields a non-empty list of names when
+// applied to the author's blessings.
+// 4. the author's public key is not known to be revoked.
+// 5. the local's public key (call.LocalPrincipal().PublicKey()) is not known
+// to be revoked.
+// 6. the author's public key is the public key of the RPC caller.
+// 7. the author's public key and the local public key differ.
+// If checks pass and there are no other errors:
+// - records the list of names found in check (3) in the ValidationData
+// - adds a validation signature using the local public key (which is now the
+// validator)
+// - sets d.IsValidated
+// - returns the list of names found in check (3), and a nil error.
+// Otherwise returns a nil list of names and a non-nil error.
+//
+// If d.Validated==true, checks that:
+// 1. the author's signature and the validator data are available in *cache.
+// 2. the author's signature over its blessings and the data is
+// cyprotgraphically valid.
+// 8. the list of names stored in the ValidatorData by the validator is
+// non-empty.
+// 9. the author's public key and the validator's public key differ.
+// 10. the list of names stored in the ValidatorData by the validator is a
+// subset of the list of names that the author's blessings could have
+// represented.
+// 11. the author's public key is not known to be revoked more than
+// gracePeriod ago.
+// 12. the validator's public key is not known to be revoked more than
+// gracePeriod ago.
+// 13. the validator's signature is cryptographically valid.
+// If checks pass and there are no other errors:
+// - returns the list of names in the validator's data, and a nil error.
+// Otherwise returns a nil list of names and a non-nil error.
+func (d *DataWithSignature) Check(ctx *context.T, cache *ValidationCache, call security.Call,
+ krl *krl.KRL, gracePeriod time.Duration) (names []string, err error) {
+
+ // Verify that we have the Blessings and ValidatorData.
+ var authorBlessingsData *BlessingsData = cache.LookupBlessingsData(ctx, d.BlessingsHash)
+ var validatorData *ValidatorData
+ if d.IsValidated {
+ validatorData = cache.LookupValidatorData(ctx, d.ValidatorDataHash)
+ }
+ if authorBlessingsData == nil || (validatorData == nil && d.IsValidated) { // Check (1).
+ if authorBlessingsData == nil && (validatorData == nil && d.IsValidated) {
+ err = verror.New(ErrNeedAuthorBlessingsAndValidatorDataForHash, ctx)
+ } else if authorBlessingsData == nil {
+ err = verror.New(ErrNeedAuthorBlessingsForHash, ctx)
+ } else {
+ err = verror.New(ErrNeedValidatorDataForHash, ctx)
+ }
+ }
+
+ // Check the author signature.
+ var authorSignatureHash []byte
+ if err == nil {
+ authorSignatureHash = d.authorSignatureHash()
+ if !d.AuthorSigned.Verify(authorBlessingsData.UnmarshalledBlessings.PublicKey(), authorSignatureHash) { // Check (2).
+ err = verror.New(errBadAuthorSignature, ctx)
+ }
+ }
+
+ // Check or create the validator signature.
+ now := time.Now()
+ if err != nil {
+ // err already set
+ } else if !d.IsValidated {
+ // Not yet validated, so this run will attempt to validate.
+ var validatedNames []string
+ var localKeyMarshalled []byte
+ var senderKeyMarshalled []byte
+ validatedNames, _ = security.SigningBlessingNames(ctx, call.LocalPrincipal(),
+ authorBlessingsData.UnmarshalledBlessings)
+ if len(validatedNames) == 0 { // Check (3).
+ err = verror.New(errAuthorBlessingsHaveNoValidNames, ctx)
+ } else if localKeyMarshalled, err = call.LocalPrincipal().PublicKey().MarshalBinary(); err != nil {
+ // err already set
+ } else if krl.RevocationTime(authorBlessingsData.MarshalledPublicKey).Before(now) { // Check (4).
+ err = verror.New(errAuthorKeyIsRevoked, ctx)
+ } else if krl.RevocationTime(localKeyMarshalled).Before(now) { // Check (5).
+ err = verror.New(errValidatorKeyIsRevoked, ctx)
+ } else if senderKeyMarshalled, err = call.RemoteBlessings().PublicKey().MarshalBinary(); err != nil {
+ // err already set
+ } else if !bytes.Equal(senderKeyMarshalled, authorBlessingsData.MarshalledPublicKey) { // Check (6).
+ err = verror.New(errSenderIsNotAuthor, ctx)
+ } else if bytes.Equal(localKeyMarshalled, authorBlessingsData.MarshalledPublicKey) { // Check (7).
+ err = verror.New(errMayNotValidateOwnSignature, ctx)
+ } else {
+ // Local principal is different from author, so can validate.
+ validatorData = &ValidatorData{
+ Names: validatedNames,
+ PublicKey: call.LocalPrincipal().PublicKey(),
+ MarshalledPublicKey: localKeyMarshalled,
+ }
+ d.ValidatorDataHash = cache.AddValidatorData(ctx, validatorData)
+ d.ValidatorSigned, err = call.LocalPrincipal().Sign(d.validatorSignatureHash(authorSignatureHash))
+ d.IsValidated = (err == nil)
+ }
+ } else { // Data already validated; check the validator siganture.
+ if len(validatorData.Names) == 0 { // Check (8).
+ err = verror.New(errAuthorBlessingsHaveNoValidNames, ctx)
+ } else if bytes.Equal(validatorData.MarshalledPublicKey, authorBlessingsData.MarshalledPublicKey) { // Check (9).
+ err = verror.New(errValidatorIsSigner, ctx)
+ } else if !authorBlessingsData.UnmarshalledBlessings.CouldHaveNames(validatorData.Names) { // Check (10).
+ err = verror.New(errValidatesWrongNames, ctx)
+ } else if krl.RevocationTime(authorBlessingsData.MarshalledPublicKey).Before(now.Add(-gracePeriod)) { // Check (11).
+ err = verror.New(errAuthorKeyIsRevoked, ctx)
+ } else if krl.RevocationTime(validatorData.MarshalledPublicKey).Before(now.Add(-gracePeriod)) { // Check (12).
+ err = verror.New(errValidatorKeyIsRevoked, ctx)
+ } else if !d.ValidatorSigned.Verify(validatorData.PublicKey, d.validatorSignatureHash(authorSignatureHash)) { // Check (13).
+ err = verror.New(errBadValidatorSignature, ctx)
+ } // else success.
+ }
+
+ // If there were no errors, return the list of names from the validator.
+ if err == nil {
+ names = make([]string, len(validatorData.Names))
+ copy(names, validatorData.Names)
+ }
+
+ return names, err
+}
diff --git a/x/ref/services/syncbase/signing/signing_test.go b/x/ref/services/syncbase/signing/signing_test.go
new file mode 100644
index 0000000..96881f3
--- /dev/null
+++ b/x/ref/services/syncbase/signing/signing_test.go
@@ -0,0 +1,421 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package signing_test implements a test for the package
+// v.io/syncbase/x/ref/services/syncbase/signing
+package signing_test
+
+import "crypto/sha256"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing"
+import "v.io/syncbase/x/ref/services/syncbase/signing/krl"
+import "v.io/v23/naming"
+import "v.io/v23/security"
+import "v.io/v23/vdl"
+import "v.io/v23/vom"
+import "v.io/v23/verror"
+import "v.io/x/ref/test"
+import lib_security "v.io/x/ref/lib/security"
+
+import _ "v.io/x/ref/runtime/factories/generic"
+
+// --------------------------------------
+// The following implements a fake security.Call.
+type fakeCall struct {
+ localPrincipal security.Principal
+ localBlessings security.Blessings
+ remoteBlessings security.Blessings
+}
+
+func (fc *fakeCall) Timestamp() time.Time { return time.Now() }
+func (fc *fakeCall) Method() string { return "the_method_name" }
+func (fc *fakeCall) MethodTags() []*vdl.Value { return nil }
+func (fc *fakeCall) Suffix() string { return "the_suffix" }
+func (fc *fakeCall) LocalDischarges() map[string]security.Discharge { return nil }
+func (fc *fakeCall) RemoteDischarges() map[string]security.Discharge { return nil }
+func (fc *fakeCall) LocalPrincipal() security.Principal { return fc.localPrincipal }
+func (fc *fakeCall) LocalBlessings() security.Blessings { return fc.localBlessings }
+func (fc *fakeCall) RemoteBlessings() security.Blessings { return fc.remoteBlessings }
+func (fc *fakeCall) LocalEndpoint() naming.Endpoint { return nil }
+func (fc *fakeCall) RemoteEndpoint() naming.Endpoint { return nil }
+
+// --------------------------------------
+
+// A principalDesc holds the local state of a single principal in the tests below.
+type principalDesc struct {
+ name string
+ principal security.Principal
+ blessings security.Blessings
+ krl *krl.KRL
+ authorBlessingsData *signing.BlessingsData
+ names []string
+ marshalledBlessings []byte
+ blessingsHash []byte
+ validatorData *signing.ValidatorData
+ validatorHash []byte
+ cache *signing.ValidationCache
+ data *signing.DataWithSignature
+}
+
+// makePrincipal() returns a pointer to a newly-initialized principalDesc,
+// with a unique key, and a single blessing named with its own name.
+func makePrincipal(t testing.TB, name string) (desc *principalDesc) {
+ var err error
+ desc = new(principalDesc)
+ desc.name = name
+ desc.principal, err = lib_security.NewPrincipal()
+ if err != nil {
+ t.Fatalf("security.CreatePrincipal %q failed: %v", desc.name, err)
+ }
+ desc.blessings, err = desc.principal.BlessSelf(desc.name)
+ if err != nil {
+ t.Fatalf("principal.BlessSelf %q failed: %v", desc.name, err)
+ }
+ desc.krl = krl.New()
+ desc.cache = signing.NewValidationCache(5 * time.Second)
+ return desc
+}
+
+// makePrincipals() creares one principal per name, and adds
+// the blessings of each to the roots of all.
+func makePrincipals(t testing.TB, names ...string) (principals []*principalDesc) {
+ for i := range names {
+ principals = append(principals, makePrincipal(t, names[i]))
+ }
+ for i := range principals {
+ for j := range principals {
+ principals[j].principal.AddToRoots(principals[i].blessings)
+ }
+ }
+ return principals
+}
+
+// BenchmarkHashData() measures the time taken to do a cryptogrqaphic hash of
+// 1kBytes.
+func BenchmarkHashData(b *testing.B) {
+ var block [1024]byte
+ hasher := sha256.New()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ hasher.Write(block[:])
+ }
+}
+
+// BenchmarkSignData() measures the time taken to sign something with
+// signing.SignData().
+func BenchmarkSignData(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+ author := makePrincipal(b, "author")
+ dataToSign := []signing.Item{signing.ItemData{Value: []byte("hello")}}
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ }
+ if err != nil {
+ panic(err)
+ }
+}
+
+// BenchmarkSign1000Data() measures the time taken to sign 1000 small data
+// items with signing.SignData().
+func BenchmarkSign1000Data(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+ author := makePrincipal(b, "author")
+ var dataToSign []signing.Item
+ for i := 0; i != 1000; i++ {
+ dataToSign = append(dataToSign, signing.ItemData{Value: []byte("hello")})
+ }
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ }
+ if err != nil {
+ panic(err)
+ }
+}
+
+// BenchmarkSignData() measures the time taken to check a validated signature
+// with DataWithSignature.Check().
+func BenchmarkCheckData(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+
+ principals := makePrincipals(b, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ dataToSign := []signing.Item{signing.ItemData{Value: []byte("hello")}}
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ panic(err)
+ }
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ validator.names, err = author.data.Check(ctx, author.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ panic(err)
+ }
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ checker.names, err = author.data.Check(ctx, author.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ }
+}
+
+// BenchmarkSign1000Data() measures the time taken to check a validated
+// signature over 1000 small data items with DataWithSignature.Check().
+func BenchmarkCheck1000Data(b *testing.B) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+ var err error
+
+ principals := makePrincipals(b, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ var dataToSign []signing.Item
+ for i := 0; i != 1000; i++ {
+ dataToSign = append(dataToSign, signing.ItemData{Value: []byte("hello")})
+ }
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ panic(err)
+ }
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ validator.names, err = author.data.Check(ctx, author.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ panic(err)
+ }
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ checker.names, err = author.data.Check(ctx, author.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ }
+}
+
+// BenchmarkMarshallBlessings() measures the time taken to marshal a Blessings.
+func BenchmarkMarshallBlessings(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ author.marshalledBlessings, err = vom.Encode(author.blessings)
+ }
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+}
+
+// BenchmarkUnmarshallBlessings() measures the time taken to unmashal a Blessings.
+func BenchmarkUnmarshallBlessings(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ author.marshalledBlessings, err = vom.Encode(author.blessings)
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+ var blessings security.Blessings
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ err = vom.Decode(author.marshalledBlessings, &blessings)
+ }
+ if err != nil {
+ b.Fatalf("vom.Encode failed: %v", err)
+ }
+}
+
+// BenchmarkMarshallPublicKey() measures the time taken to marshal a PublicKey.
+func BenchmarkMarshallPublicKey(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, err = author.principal.PublicKey().MarshalBinary()
+ }
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+}
+
+// BenchmarkUnmarshallPublicKey() measures the time taken to unmarshal a PublicKey.
+func BenchmarkUnmarshallPublicKey(b *testing.B) {
+ var err error
+ author := makePrincipal(b, "author")
+ var marshalledKey []byte
+ marshalledKey, err = author.principal.PublicKey().MarshalBinary()
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ _, err = security.UnmarshalPublicKey(marshalledKey)
+ }
+ if err != nil {
+ b.Fatalf("MarshalBinary() failed: %v", err)
+ }
+}
+
+// TestSignData() tests that a complete flow of signing, validating, and
+// checking works on a DataWithSignature.
+func TestSignData(t *testing.T) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+
+ var err error
+
+ principals := makePrincipals(t, "author", "validator", "checker")
+ author := principals[0]
+ validator := principals[1]
+ checker := principals[2]
+
+ // Add each princpipal's blessings to each principal's roots.
+ pdList := []*principalDesc{author, validator, checker}
+ for i := 0; i != len(pdList); i++ {
+ for j := 0; j != len(pdList); j++ {
+ pdList[j].principal.AddToRoots(pdList[i].blessings)
+ }
+ }
+
+ // --------------------------------------
+ // Author
+ // Sign some data.
+ dataToSign := []signing.Item{
+ signing.ItemData{Value: []byte("hello")},
+ signing.ItemData{Value: []byte("world")},
+ signing.ItemData{Value: []byte("!")},
+ }
+ author.data, author.authorBlessingsData, err =
+ signing.SignData(ctx, author.cache, author.principal, author.blessings, dataToSign)
+ if err != nil {
+ t.Fatalf("signing.SignData failed: %v", err)
+ }
+ if author.data.IsValidated {
+ t.Fatalf("signing.SignData generated data with IsValidated set")
+ }
+
+ // --------------------------------------
+ // Validator
+ callToValidator := fakeCall{
+ localPrincipal: validator.principal,
+ localBlessings: validator.blessings,
+ remoteBlessings: author.blessings,
+ }
+ // The validator receives author.data from the author.
+ validator.data = new(signing.DataWithSignature)
+ *validator.data = *author.data
+ // Initially the validator doesn't have the author BlessingsData.
+ validator.authorBlessingsData = validator.cache.LookupBlessingsData(ctx, validator.data.BlessingsHash)
+ if validator.authorBlessingsData != nil {
+ t.Errorf("found non-nil BlessingsData for validator.data.BlessingsHash in validator's ValidationCache")
+ }
+ validator.names, err = validator.data.Check(ctx, validator.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedAuthorBlessingsForHash.ID {
+ t.Fatalf("validator.data.Check got err %v, want %s", err, signing.ErrNeedAuthorBlessingsForHash.ID)
+ }
+
+ // The validator receives the author's marshalled blessings from the author.
+ validator.marshalledBlessings = author.authorBlessingsData.MarshalledBlessings
+ validator.blessingsHash, validator.authorBlessingsData, err = validator.cache.AddWireBlessings(ctx, validator.marshalledBlessings)
+ if err != nil {
+ t.Fatalf("validator can't add author's marshalled belssings to its ValidationCache: %v", err)
+ }
+
+ validator.names, err = validator.data.Check(ctx, validator.cache, &callToValidator, validator.krl, 24*30*time.Hour)
+ if err != nil {
+ t.Fatalf("validator error calling Check() on data: %v", err)
+ }
+ if !validator.data.IsValidated {
+ t.Fatalf("signing.Check didn't set IsValidated")
+ }
+ // Validator's cache should now have the author's BlessingData, and the validator's ValidatorData.
+ validator.authorBlessingsData = validator.cache.LookupBlessingsData(ctx, validator.data.BlessingsHash)
+ if validator.authorBlessingsData == nil {
+ t.Errorf("didn't finf BlessingsData for validator.data.BlessingsHash in validator's ValidationCache")
+ }
+ validator.validatorData = validator.cache.LookupValidatorData(ctx, validator.data.ValidatorDataHash)
+
+ // --------------------------------------
+ // Checker
+ callToChecker := fakeCall{
+ localPrincipal: checker.principal,
+ localBlessings: checker.blessings,
+ remoteBlessings: validator.blessings,
+ }
+ // The checker recieves validator.data from the validator, except that
+ // data item 1 is replaced by its hash, because (for example) the
+ // check is not allowed to see it.
+ checker.data = new(signing.DataWithSignature)
+ *checker.data = *validator.data
+ checker.data.Data[1] = signing.ItemHash{Value: signing.SumByteVectorWithLength(checker.data.Data[1].(signing.ItemData).Value)}
+
+ // Initially the checker doesn't have the author BlessingsData, or the validator ValidatorData.
+ checker.authorBlessingsData = checker.cache.LookupBlessingsData(ctx, checker.data.BlessingsHash)
+ if checker.authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for checker.data.BlessingsHash hash in checker's ValidationCache")
+ }
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedAuthorBlessingsAndValidatorDataForHash.ID {
+ t.Fatalf("checker.data.Check got err %v, want %s", err, signing.ErrNeedAuthorBlessingsAndValidatorDataForHash.ID)
+ }
+
+ // The checker receives the author's marshalled blessings from the validator.
+ checker.marshalledBlessings = validator.marshalledBlessings
+ checker.blessingsHash, checker.authorBlessingsData, err = checker.cache.AddWireBlessings(ctx, checker.marshalledBlessings)
+ if err != nil {
+ t.Fatalf("checker can't add author's marshalled belssings to its ValidationCache: %v", err)
+ }
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if verror.ErrorID(err) != signing.ErrNeedValidatorDataForHash.ID {
+ t.Fatalf("checker.data.Check got err %v, want %s", err, signing.ErrNeedValidatorDataForHash.ID)
+ }
+
+ // The checker receives the validator's data from the validator, passing through the wire format.
+ wvd := signing.ToWireValidatorData(validator.validatorData)
+ var vd signing.ValidatorData
+ vd, err = signing.FromWireValidatorData(&wvd)
+ if err != nil {
+ t.Fatalf("signing.FromWireValidatorData got error: %v", err)
+ }
+ checker.validatorData = &vd
+
+ // The checker adds the ValidatorData to its cache.
+ checker.validatorHash = checker.cache.AddValidatorData(ctx, checker.validatorData)
+
+ // And now the Check() operation should work.
+ checker.names, err = checker.data.Check(ctx, checker.cache, &callToChecker, checker.krl, 24*30*time.Hour)
+ if err != nil {
+ t.Fatalf("checker.data.Check got unexpected err %v", err)
+ }
+}
diff --git a/x/ref/services/syncbase/signing/validationcache.go b/x/ref/services/syncbase/signing/validationcache.go
new file mode 100644
index 0000000..1c95bd0
--- /dev/null
+++ b/x/ref/services/syncbase/signing/validationcache.go
@@ -0,0 +1,190 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This module implements a cache of data associated with the
+// signatures, keyed by hash values of the data. The intent is that
+// communicating devices will refer to the data using hashes, and transmit the
+// data itself only if the device on the other side does not have the data in
+// its cache.
+
+package signing
+
+import "crypto/sha256"
+import "encoding/binary"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing/hashcache"
+import "v.io/v23/context"
+import "v.io/v23/security"
+import "v.io/v23/vom"
+
+// --------------------------------------------
+
+// A BlessingsData contains information about a security.Blessings object. The
+// object itself is referred to by UnmarshalledBlessings. The implementation
+// constructs all instances; the client should not modify fields.
+type BlessingsData struct {
+ UnmarshalledBlessings security.Blessings // The Blessings.
+ MarshalledBlessings []byte // VOM encoded Blessings.
+ MarshalledPublicKey []byte // Value from blessings.PublicKey().MarshalBinary().
+}
+
+// A ValidatorData is the extra data that a validator signs when validating and
+// signing a DataWithSignature. Clients may construct instances to pass to
+// AddValidatorData(), but should not modify the fields of a constructed
+// ValidatorData.
+type ValidatorData struct {
+ Names []string // Names of valid signing blessings in the Blessings referred to by BlessingsHash.
+ PublicKey security.PublicKey // The key used to create ValidatorSigned.
+ MarshalledPublicKey []byte // PublicKey, marshalled with MarshalBinary().
+}
+
+// hash() returns the hash of *vd. This hash should be used in the
+// ValidatorDataHash field of DataWithSignature, and as the cache key of *vd
+// in a ValidationCache.
+func (vd *ValidatorData) hash() []byte {
+ hasher := sha256.New()
+ var buffer [256]byte
+ var buf []byte = buffer[:]
+ binary.LittleEndian.PutUint64(buf[:], uint64(len(vd.Names)))
+ hasher.Write(buf[:8])
+ for i := range vd.Names {
+ if len(vd.Names[i]) > len(buf) {
+ buf = make([]byte, len(vd.Names[i])+256)
+ }
+ hashByteVectorWithLength(hasher, []byte(vd.Names[i]))
+ }
+ hashByteVectorWithLength(hasher, vd.MarshalledPublicKey)
+ return hasher.Sum(nil)[:]
+}
+
+// A ValidationCache records recently-seen instances of BlessingsData and
+// ValidatorData values, keys by hashes of the blessings and validator keys
+// respectively. Values may expire from the cache if unused for a duration
+// specified with NewValidationCache().
+type ValidationCache struct {
+ blessingsCache *hashcache.Cache
+ validatorCache *hashcache.Cache
+}
+
+// NewValidationCache() returns a pointer to a new, empty ValidationCache with
+// the specified expiry duration..
+func NewValidationCache(expiry time.Duration) *ValidationCache {
+ return &ValidationCache{
+ blessingsCache: hashcache.New(expiry),
+ validatorCache: hashcache.New(expiry)}
+}
+
+// LookupBlessingsData() returns a pointer to the BlessingsData associated with
+// blessingsHash in *vc. blessingsHash should have been returned by a previous
+// call to AddBlessings() or AddWireBlessings() (possibly on another machine).
+// nil is returned if the data is not present. The client should not modify
+// *result, since it is shared with *vc.
+func (vc *ValidationCache) LookupBlessingsData(ctx *context.T, blessingsHash []byte) (result *BlessingsData) {
+ value, found := vc.blessingsCache.Lookup(blessingsHash)
+ if found {
+ result = value.(*BlessingsData)
+ }
+ return result
+}
+
+// addBlessings() adds a BlessingsData for blessings to *vc, and returns a hash
+// value, which if passed to LookupBlessingsData() will yield a pointer to the
+// BlessingsData, or a non-nil error. The fields of BlessingsData other than
+// MarshalledBlessings and UnmarshalledBlessings are constructed by this
+// routine. Requires that blessings and marshalledBlessings represent the same
+// data, or that marshalledBlessings be nil.
+func (vc *ValidationCache) addBlessings(ctx *context.T, blessings security.Blessings,
+ marshalledBlessings []byte) (blessingsHash []byte, data *BlessingsData, err error) {
+
+ blessingsHash = blessings.UniqueID()
+ if value, found := vc.blessingsCache.Lookup(blessingsHash); found {
+ data = value.(*BlessingsData)
+ } else { // not found
+ var marshalledKey []byte
+ if marshalledBlessings == nil {
+ marshalledBlessings, err = vom.Encode(blessings)
+ }
+ if err == nil {
+ marshalledKey, err = blessings.PublicKey().MarshalBinary()
+ }
+ if err == nil {
+ data = &BlessingsData{
+ UnmarshalledBlessings: blessings,
+ MarshalledBlessings: marshalledBlessings,
+ MarshalledPublicKey: marshalledKey}
+ vc.blessingsCache.Add(blessingsHash, data)
+ }
+ }
+ return blessingsHash, data, err
+}
+
+// AddBlessings() adds a BlessingsData for blessings to *cv, and
+// returns a hash value, which if passed to LookupBlessingsData() will yield a
+// pointer to the BlessingsData, or a non-nil error. The fields of
+// BlessingsData other than UnmarshalledBlessings are constructed by this
+// routine.
+func (vc *ValidationCache) AddBlessings(ctx *context.T, blessings security.Blessings) (blessingsHash []byte, data *BlessingsData, err error) {
+ return vc.addBlessings(ctx, blessings, nil)
+}
+
+// AddWireBlessings() adds a BlessingsData for blessings to *cv, and
+// returns a hash value, which if passed to LookupBlessingsData() will yield a
+// pointer to the BlessingsData, or a non-nil error. The fields of
+// BlessingsData other than MarshalledBlessings are constructed by this
+// routine.
+func (vc *ValidationCache) AddWireBlessings(ctx *context.T,
+ marshalledBlessings []byte) (blessingsHash []byte, data *BlessingsData, err error) {
+
+ var blessings security.Blessings
+ err = vom.Decode(marshalledBlessings, &blessings)
+ if err == nil {
+ blessingsHash, data, err = vc.addBlessings(ctx, blessings, marshalledBlessings)
+ }
+ return blessingsHash, data, err
+}
+
+// LookupValidatorData() returns a pointer to the ValidatorData associated with
+// hash validatorHash in *vc validatorHash should have been returned by a
+// previous call to AddValidatorData() (possibly on another machine). nil is
+// returned if the data is not present. The client should not modifiy *result,
+// since it it shared with *vc.
+func (vc *ValidationCache) LookupValidatorData(ctx *context.T, validatorHash []byte) (result *ValidatorData) {
+ value, found := vc.validatorCache.Lookup(validatorHash)
+ if found {
+ result = value.(*ValidatorData)
+ }
+ return result
+}
+
+// AddValidatorData() adds a ValidatorData *vd to cache *vc, and returns a hash
+// value, which if passed to LookupValidatorData() will yield a pointer to the
+// ValidatorData. The client should not modify *vd after the call, since it is
+// shared with *vc.
+func (vc *ValidationCache) AddValidatorData(ctx *context.T, vd *ValidatorData) (validatorDataHash []byte) {
+ validatorDataHash = vd.hash()
+ vc.validatorCache.Add(validatorDataHash, vd)
+ return validatorDataHash
+}
+
+// ToWireValidatorData() puts the wire form of ValidatorData *vd in *wvd.
+func ToWireValidatorData(vd *ValidatorData) (wvd WireValidatorData) {
+ wvd.Names = make([]string, len(vd.Names))
+ copy(wvd.Names, vd.Names)
+ wvd.MarshalledPublicKey = make([]byte, len(vd.MarshalledPublicKey))
+ copy(wvd.MarshalledPublicKey, vd.MarshalledPublicKey)
+ return wvd
+}
+
+// FromWireValidatorData() puts the in-memory form of WireValidatorData *wvd in *vd.
+func FromWireValidatorData(wvd *WireValidatorData) (vd ValidatorData, err error) {
+ vd.PublicKey, err = security.UnmarshalPublicKey(wvd.MarshalledPublicKey)
+ if err == nil {
+ vd.Names = make([]string, len(wvd.Names))
+ copy(vd.Names, wvd.Names)
+ vd.MarshalledPublicKey = make([]byte, len(wvd.MarshalledPublicKey))
+ copy(vd.MarshalledPublicKey, wvd.MarshalledPublicKey)
+ }
+ return vd, err
+}
diff --git a/x/ref/services/syncbase/signing/validationcache_test.go b/x/ref/services/syncbase/signing/validationcache_test.go
new file mode 100644
index 0000000..a45835b
--- /dev/null
+++ b/x/ref/services/syncbase/signing/validationcache_test.go
@@ -0,0 +1,189 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// This file tests the validationcache.go module.
+
+package signing_test
+
+import "bytes"
+import "testing"
+import "time"
+
+import "v.io/syncbase/x/ref/services/syncbase/signing"
+import "v.io/v23/security"
+import "v.io/x/ref/test"
+import _ "v.io/x/ref/runtime/factories/generic"
+import lib_security "v.io/x/ref/lib/security"
+
+// A principalVDesc holds the local state of a single principal in the tests below.
+type principalVDesc struct {
+ name string
+ principal security.Principal
+ blessings security.Blessings
+ blessingsHash []byte
+ blessingsData *signing.BlessingsData
+ validatorHash []byte
+ validatorData *signing.ValidatorData
+ cache *signing.ValidationCache
+}
+
+// makePrincipalVDesc() returns a pointer to a newly-initialized principalVDesc,
+// with a unique key, and a single blessing named with its own name.
+func makePrincipalVDesc(t *testing.T, name string) (desc *principalVDesc) {
+ var err error
+ desc = new(principalVDesc)
+ desc.name = name
+ desc.principal, err = lib_security.NewPrincipal()
+ if err != nil {
+ t.Fatalf("lib_security.NewPrincipal %q failed: %v", desc.name, err)
+ }
+ desc.blessings, err = desc.principal.BlessSelf(desc.name)
+ if err != nil {
+ t.Fatalf("principal.BlessSelf %q failed: %v", desc.name, err)
+ }
+ desc.cache = signing.NewValidationCache(5 * time.Second)
+ return desc
+}
+
+func TestValidationCache(t *testing.T) {
+ ctx, shutdown := test.V23Init()
+ defer shutdown()
+
+ var err error
+
+ // Make a principalVDesc for each of the author, validator, and checker.
+ // (The author creates a signed change; the validator is a device
+ // author syncs with; the checker is a device a validator syncs with.)
+ author := makePrincipalVDesc(t, "author")
+ validator := makePrincipalVDesc(t, "validator")
+ checker := makePrincipalVDesc(t, "checker")
+
+ // Add each princpipal's blessings to each principal's roots.
+ pdList := []*principalVDesc{author, validator, checker}
+ for i := 0; i != len(pdList); i++ {
+ for j := 0; j != len(pdList); j++ {
+ pdList[j].principal.AddToRoots(pdList[i].blessings)
+ }
+ }
+
+ // --------------------------------------
+ // Author
+ arbitraryBlessingsData := author.cache.LookupBlessingsData(ctx, []byte{0x00})
+ if arbitraryBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for nonsense hash in author's ValidationCache")
+ }
+ author.blessingsHash, author.blessingsData, err = author.cache.AddBlessings(ctx, author.blessings)
+ if err != nil {
+ t.Fatalf("error from author.cache.AddBlessings(): %v", err)
+ }
+ // Check that the author's data is as we expect.
+ if author.cache.LookupBlessingsData(ctx, author.blessingsHash) != author.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in author's ValidationCache: %v vs %v",
+ author.cache.LookupBlessingsData(ctx, author.blessingsHash), author.blessingsData)
+ }
+
+ // --------------------------------------
+ // Validator
+ // The validator receives author.blessingsHash from the author.
+ // Initially the validator doesn't have the author BlessingsData.
+ authorBlessingsData := validator.cache.LookupBlessingsData(ctx, author.blessingsHash)
+ if authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for author.blessingsHash hash in validator's ValidationCache")
+ }
+ // The validator receives the author's marshalled blessings from the author.
+ validator.blessingsHash, validator.blessingsData, err =
+ validator.cache.AddWireBlessings(ctx, author.blessingsData.MarshalledBlessings)
+ if err != nil {
+ t.Fatalf("validator can't add author's marshalled blessings to its ValidationCache: %v", err)
+ }
+ if !bytes.Equal(author.blessingsHash, validator.blessingsHash) {
+ t.Errorf("validator's copy of the blessingsHash different from author's")
+ }
+ // Check that we could have got the blessingsData with a lookup if this were the second time.
+ if validator.cache.LookupBlessingsData(ctx, validator.blessingsHash) != validator.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in validator's ValidationCache")
+ }
+ var marshalledPublicKey []byte
+ marshalledPublicKey, err = validator.principal.PublicKey().MarshalBinary()
+ if err != nil {
+ t.Fatalf("validator.principal.PublicKey().MarshalBinary() got error: %v", err)
+ }
+
+ var validatedNames []string
+ validatedNames, _ = security.SigningBlessingNames(ctx, validator.principal,
+ validator.blessingsData.UnmarshalledBlessings)
+ validator.validatorData = &signing.ValidatorData{
+ Names: validatedNames,
+ PublicKey: validator.principal.PublicKey(),
+ MarshalledPublicKey: marshalledPublicKey}
+ validator.validatorHash = validator.cache.AddValidatorData(ctx, validator.validatorData)
+ if validator.cache.LookupValidatorData(ctx, validator.validatorHash) != validator.validatorData {
+ t.Fatalf("LookupValidatorData returned wrong ValidatorData pointer in validator")
+ }
+
+ // --------------------------------------
+ // Checker
+ // The checker receives validator.blessingsHash from the validator.
+ // Initially the checker doesn't have the author BlessingsData.
+ authorBlessingsData = checker.cache.LookupBlessingsData(ctx, validator.blessingsHash)
+ if authorBlessingsData != nil {
+ t.Errorf("found non-nil blessings data for author.blessingsHash hash in checker's ValidationCache")
+ }
+ // The checker receives the author's marshalled blessings from the validator.
+ checker.blessingsHash, checker.blessingsData, err =
+ checker.cache.AddWireBlessings(ctx, validator.blessingsData.MarshalledBlessings)
+ if err != nil {
+ t.Fatalf("checker can't add author's marshalled blessings (from validator) to ValidationCache: %v", err)
+ }
+ if !bytes.Equal(author.blessingsHash, checker.blessingsHash) {
+ t.Errorf("checker's copy of the blessingsHash different from author's")
+ }
+ // Check that we could have got the blessingsData with a lookup if this where the second time.
+ if checker.cache.LookupBlessingsData(ctx, checker.blessingsHash) != checker.blessingsData {
+ t.Fatalf("found wrong blessings data for hash in checker's ValidationCache")
+ }
+ // The checker recieves validator.validatorHash from the validator.
+ // Initially the checker doesn't have the ValidatorData.
+ validatorData := checker.cache.LookupValidatorData(ctx, validator.validatorHash)
+ if validatorData != nil {
+ t.Errorf("found non-nil validator data for validator.validatorHash hash in checker's ValidationCache")
+ }
+ // The checker receives the validator's data from the validator (or another checker).
+ checker.validatorHash = checker.cache.AddValidatorData(ctx, validator.validatorData)
+ if !bytes.Equal(validator.validatorHash, checker.validatorHash) {
+ t.Fatalf("checker's copy of the validatorHash different from validator's")
+ }
+ // Get the validatorData
+ checker.validatorData = checker.cache.LookupValidatorData(ctx, checker.validatorHash)
+ if checker.validatorData == nil {
+ t.Fatalf("found nil valdidatorData for checker.validatorHash hash in checker's ValidationCache")
+ }
+}
+
+func TestWireValidatorData(t *testing.T) {
+ var err error
+
+ pDesc := makePrincipalVDesc(t, "some_principal")
+
+ var vd signing.ValidatorData
+ vd.Names = []string{"wombat", "foo"}
+ vd.PublicKey = pDesc.principal.PublicKey()
+ vd.MarshalledPublicKey, err = vd.PublicKey.MarshalBinary()
+ if err != nil {
+ t.Fatalf("failed to marshel public key: %v\n", err)
+ }
+
+ var wvd signing.WireValidatorData
+ var vd2 signing.ValidatorData
+
+ wvd = signing.ToWireValidatorData(&vd)
+ vd2, err = signing.FromWireValidatorData(&wvd)
+ if err != nil {
+ t.Fatalf("FromWireValidatorData failed: %v\n", err)
+ }
+ if len(vd.Names) != len(vd2.Names) {
+ t.Fatalf("ToWireValidatorData/FromWireValidatorData failed to transfer Names list correctly:\nold\n%v\n\nnew\n%v\n\nwire\n%v\n",
+ vd, vd2, wvd)
+ }
+}
