diff --git a/go/src/mojom/vanadium/discovery/discovery.mojom.go b/go/src/mojom/vanadium/discovery/discovery.mojom.go
index f39fb62..61c835d 100644
--- a/go/src/mojom/vanadium/discovery/discovery.mojom.go
+++ b/go/src/mojom/vanadium/discovery/discovery.mojom.go
@@ -86,7 +86,7 @@
 }
 
 type Advertiser interface {
-	Advertise(inService Service, inVisibility []string) (outHandle uint32, outErr *Error, err error)
+	Advertise(inService Service, inVisibility *[]string) (outHandle uint32, outInstanceId string, outErr *Error, err error)
 	Stop(inH uint32) (err error)
 }
 
@@ -153,7 +153,7 @@
 
 type advertiser_Advertise_Params struct {
 	inService    Service
-	inVisibility []string
+	inVisibility *[]string
 }
 
 func (s *advertiser_Advertise_Params) Encode(encoder *bindings.Encoder) error {
@@ -164,24 +164,28 @@
 	if err := s.inService.Encode(encoder); err != nil {
 		return err
 	}
-	if err := encoder.WritePointer(); err != nil {
-		return err
-	}
-	encoder.StartArray(uint32(len(s.inVisibility)), 64)
-	for _, elem0 := range s.inVisibility {
+	if s.inVisibility == nil {
+		encoder.WriteNullPointer()
+	} else {
 		if err := encoder.WritePointer(); err != nil {
 			return err
 		}
-		if err := encoder.WriteString(elem0); err != nil {
+		encoder.StartArray(uint32(len((*s.inVisibility))), 64)
+		for _, elem0 := range *s.inVisibility {
+			if err := encoder.WritePointer(); err != nil {
+				return err
+			}
+			if err := encoder.WriteString(elem0); err != nil {
+				return err
+			}
+		}
+		if err := encoder.Finish(); err != nil {
 			return err
 		}
 	}
 	if err := encoder.Finish(); err != nil {
 		return err
 	}
-	if err := encoder.Finish(); err != nil {
-		return err
-	}
 	return nil
 }
 
@@ -227,13 +231,14 @@
 			return err
 		}
 		if pointer0 == 0 {
-			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
+			s.inVisibility = nil
 		} else {
+			s.inVisibility = new([]string)
 			len0, err := decoder.StartArray(64)
 			if err != nil {
 				return err
 			}
-			s.inVisibility = make([]string, len0)
+			(*s.inVisibility) = make([]string, len0)
 			for i0 := uint32(0); i0 < len0; i0++ {
 				pointer1, err := decoder.ReadPointer()
 				if err != nil {
@@ -246,7 +251,7 @@
 					if err != nil {
 						return err
 					}
-					s.inVisibility[i0] = value1
+					(*s.inVisibility)[i0] = value1
 				}
 			}
 			if err := decoder.Finish(); err != nil {
@@ -284,22 +289,29 @@
 				ShortName: &structFieldName_AdvertiserAdvertiseParams_InVisibility,
 			},
 			Type: &mojom_types.TypeArrayType{
-				Value: mojom_types.ArrayType{ElementType: &mojom_types.TypeStringType{mojom_types.StringType{false}}},
+				Value: mojom_types.ArrayType{Nullable: true, ElementType: &mojom_types.TypeStringType{mojom_types.StringType{false}}},
 			},
 		}},
 	}
 }
 
 type advertiser_Advertise_ResponseParams struct {
-	outHandle uint32
-	outErr    *Error
+	outHandle     uint32
+	outInstanceId string
+	outErr        *Error
 }
 
 func (s *advertiser_Advertise_ResponseParams) Encode(encoder *bindings.Encoder) error {
-	encoder.StartStruct(16, 0)
+	encoder.StartStruct(24, 0)
 	if err := encoder.WriteUint32(s.outHandle); err != nil {
 		return err
 	}
+	if err := encoder.WritePointer(); err != nil {
+		return err
+	}
+	if err := encoder.WriteString(s.outInstanceId); err != nil {
+		return err
+	}
 	if s.outErr == nil {
 		encoder.WriteNullPointer()
 	} else {
@@ -317,7 +329,7 @@
 }
 
 var advertiser_Advertise_ResponseParams_Versions []bindings.DataHeader = []bindings.DataHeader{
-	bindings.DataHeader{24, 0},
+	bindings.DataHeader{32, 0},
 }
 
 func (s *advertiser_Advertise_ResponseParams) Decode(decoder *bindings.Decoder) error {
@@ -352,6 +364,21 @@
 			return err
 		}
 		if pointer0 == 0 {
+			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
+		} else {
+			value0, err := decoder.ReadString()
+			if err != nil {
+				return err
+			}
+			s.outInstanceId = value0
+		}
+	}
+	if header.ElementsOrVersion >= 0 {
+		pointer0, err := decoder.ReadPointer()
+		if err != nil {
+			return err
+		}
+		if pointer0 == 0 {
 			s.outErr = nil
 		} else {
 			s.outErr = new(Error)
@@ -368,9 +395,10 @@
 
 // String names and labels used by the MojomStruct types.
 var (
-	structName_AdvertiserAdvertiseResponseParams                = "AdvertiserAdvertiseResponseParams"
-	structFieldName_AdvertiserAdvertiseResponseParams_OutHandle = "OutHandle"
-	structFieldName_AdvertiserAdvertiseResponseParams_OutErr    = "OutErr"
+	structName_AdvertiserAdvertiseResponseParams                    = "AdvertiserAdvertiseResponseParams"
+	structFieldName_AdvertiserAdvertiseResponseParams_OutHandle     = "OutHandle"
+	structFieldName_AdvertiserAdvertiseResponseParams_OutInstanceId = "OutInstanceId"
+	structFieldName_AdvertiserAdvertiseResponseParams_OutErr        = "OutErr"
 )
 
 func discovery_Advertiser_Advertise_ResponseParams__() mojom_types.MojomStruct {
@@ -384,6 +412,11 @@
 			Type: &mojom_types.TypeSimpleType{mojom_types.SimpleType_UinT32},
 		}, mojom_types.StructField{
 			DeclData: &mojom_types.DeclarationData{
+				ShortName: &structFieldName_AdvertiserAdvertiseResponseParams_OutInstanceId,
+			},
+			Type: &mojom_types.TypeStringType{mojom_types.StringType{false}},
+		}, mojom_types.StructField{
+			DeclData: &mojom_types.DeclarationData{
 				ShortName: &structFieldName_AdvertiserAdvertiseResponseParams_OutErr,
 			},
 			Type: &mojom_types.TypeTypeReference{
@@ -394,7 +427,7 @@
 	}
 }
 
-func (p *Advertiser_Proxy) Advertise(inService Service, inVisibility []string) (outHandle uint32, outErr *Error, err error) {
+func (p *Advertiser_Proxy) Advertise(inService Service, inVisibility *[]string) (outHandle uint32, outInstanceId string, outErr *Error, err error) {
 	payload := &advertiser_Advertise_Params{
 		inService,
 		inVisibility,
@@ -433,6 +466,7 @@
 		return
 	}
 	outHandle = response.outHandle
+	outInstanceId = response.outInstanceId
 	outErr = response.outErr
 	return
 }
@@ -606,7 +640,7 @@
 			return err
 		}
 		var response advertiser_Advertise_ResponseParams
-		response.outHandle, response.outErr, err = s.impl.Advertise(request.inService, request.inVisibility)
+		response.outHandle, response.outInstanceId, response.outErr, err = s.impl.Advertise(request.inService, request.inVisibility)
 		if err != nil {
 			return
 		}
@@ -1170,7 +1204,7 @@
 
 type ScanHandler interface {
 	Found(inService Service) (err error)
-	Lost(inInstanceId []uint8) (err error)
+	Lost(inInstanceId string) (err error)
 }
 
 var scanHandler_Name = "discovery::ScanHandler"
@@ -1338,7 +1372,7 @@
 }
 
 type scanHandler_Lost_Params struct {
-	inInstanceId []uint8
+	inInstanceId string
 }
 
 func (s *scanHandler_Lost_Params) Encode(encoder *bindings.Encoder) error {
@@ -1346,13 +1380,7 @@
 	if err := encoder.WritePointer(); err != nil {
 		return err
 	}
-	encoder.StartArray(uint32(len(s.inInstanceId)), 8)
-	for _, elem0 := range s.inInstanceId {
-		if err := encoder.WriteUint8(elem0); err != nil {
-			return err
-		}
-	}
-	if err := encoder.Finish(); err != nil {
+	if err := encoder.WriteString(s.inInstanceId); err != nil {
 		return err
 	}
 	if err := encoder.Finish(); err != nil {
@@ -1392,21 +1420,11 @@
 		if pointer0 == 0 {
 			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
 		} else {
-			len0, err := decoder.StartArray(8)
+			value0, err := decoder.ReadString()
 			if err != nil {
 				return err
 			}
-			s.inInstanceId = make([]uint8, len0)
-			for i0 := uint32(0); i0 < len0; i0++ {
-				value1, err := decoder.ReadUint8()
-				if err != nil {
-					return err
-				}
-				s.inInstanceId[i0] = value1
-			}
-			if err := decoder.Finish(); err != nil {
-				return err
-			}
+			s.inInstanceId = value0
 		}
 	}
 	if err := decoder.Finish(); err != nil {
@@ -1429,14 +1447,12 @@
 			DeclData: &mojom_types.DeclarationData{
 				ShortName: &structFieldName_ScanHandlerLostParams_InInstanceId,
 			},
-			Type: &mojom_types.TypeArrayType{
-				Value: mojom_types.ArrayType{ElementType: &mojom_types.TypeSimpleType{mojom_types.SimpleType_UinT8}},
-			},
+			Type: &mojom_types.TypeStringType{mojom_types.StringType{false}},
 		}},
 	}
 }
 
-func (p *ScanHandler_Proxy) Lost(inInstanceId []uint8) (err error) {
+func (p *ScanHandler_Proxy) Lost(inInstanceId string) (err error) {
 	payload := &scanHandler_Lost_Params{
 		inInstanceId,
 	}
@@ -1560,32 +1576,34 @@
 }
 
 type Service struct {
-	InstanceUuid  []uint8
-	InstanceName  string
+	InstanceId    *string
+	InstanceName  *string
 	InterfaceName string
-	Attrs         map[string]string
+	Attrs         *map[string]string
 	Addrs         []string
 }
 
 func (s *Service) Encode(encoder *bindings.Encoder) error {
 	encoder.StartStruct(40, 0)
-	if err := encoder.WritePointer(); err != nil {
-		return err
-	}
-	encoder.StartArray(uint32(len(s.InstanceUuid)), 8)
-	for _, elem0 := range s.InstanceUuid {
-		if err := encoder.WriteUint8(elem0); err != nil {
+	if s.InstanceId == nil {
+		encoder.WriteNullPointer()
+	} else {
+		if err := encoder.WritePointer(); err != nil {
+			return err
+		}
+		if err := encoder.WriteString((*s.InstanceId)); err != nil {
 			return err
 		}
 	}
-	if err := encoder.Finish(); err != nil {
-		return err
-	}
-	if err := encoder.WritePointer(); err != nil {
-		return err
-	}
-	if err := encoder.WriteString(s.InstanceName); err != nil {
-		return err
+	if s.InstanceName == nil {
+		encoder.WriteNullPointer()
+	} else {
+		if err := encoder.WritePointer(); err != nil {
+			return err
+		}
+		if err := encoder.WriteString((*s.InstanceName)); err != nil {
+			return err
+		}
 	}
 	if err := encoder.WritePointer(); err != nil {
 		return err
@@ -1593,50 +1611,54 @@
 	if err := encoder.WriteString(s.InterfaceName); err != nil {
 		return err
 	}
-	if err := encoder.WritePointer(); err != nil {
-		return err
-	}
-	encoder.StartMap()
-	{
-		var keys0 []string
-		var values0 []string
-		for key0, value0 := range s.Attrs {
-			keys0 = append(keys0, key0)
-			values0 = append(values0, value0)
-		}
+	if s.Attrs == nil {
+		encoder.WriteNullPointer()
+	} else {
 		if err := encoder.WritePointer(); err != nil {
 			return err
 		}
-		encoder.StartArray(uint32(len(keys0)), 64)
-		for _, elem1 := range keys0 {
+		encoder.StartMap()
+		{
+			var keys0 []string
+			var values0 []string
+			for key0, value0 := range *s.Attrs {
+				keys0 = append(keys0, key0)
+				values0 = append(values0, value0)
+			}
 			if err := encoder.WritePointer(); err != nil {
 				return err
 			}
-			if err := encoder.WriteString(elem1); err != nil {
+			encoder.StartArray(uint32(len(keys0)), 64)
+			for _, elem1 := range keys0 {
+				if err := encoder.WritePointer(); err != nil {
+					return err
+				}
+				if err := encoder.WriteString(elem1); err != nil {
+					return err
+				}
+			}
+			if err := encoder.Finish(); err != nil {
+				return err
+			}
+			if err := encoder.WritePointer(); err != nil {
+				return err
+			}
+			encoder.StartArray(uint32(len(values0)), 64)
+			for _, elem1 := range values0 {
+				if err := encoder.WritePointer(); err != nil {
+					return err
+				}
+				if err := encoder.WriteString(elem1); err != nil {
+					return err
+				}
+			}
+			if err := encoder.Finish(); err != nil {
 				return err
 			}
 		}
 		if err := encoder.Finish(); err != nil {
 			return err
 		}
-		if err := encoder.WritePointer(); err != nil {
-			return err
-		}
-		encoder.StartArray(uint32(len(values0)), 64)
-		for _, elem1 := range values0 {
-			if err := encoder.WritePointer(); err != nil {
-				return err
-			}
-			if err := encoder.WriteString(elem1); err != nil {
-				return err
-			}
-		}
-		if err := encoder.Finish(); err != nil {
-			return err
-		}
-	}
-	if err := encoder.Finish(); err != nil {
-		return err
 	}
 	if err := encoder.WritePointer(); err != nil {
 		return err
@@ -1688,23 +1710,14 @@
 			return err
 		}
 		if pointer0 == 0 {
-			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
+			s.InstanceId = nil
 		} else {
-			len0, err := decoder.StartArray(8)
+			s.InstanceId = new(string)
+			value0, err := decoder.ReadString()
 			if err != nil {
 				return err
 			}
-			s.InstanceUuid = make([]uint8, len0)
-			for i0 := uint32(0); i0 < len0; i0++ {
-				value1, err := decoder.ReadUint8()
-				if err != nil {
-					return err
-				}
-				s.InstanceUuid[i0] = value1
-			}
-			if err := decoder.Finish(); err != nil {
-				return err
-			}
+			(*s.InstanceId) = value0
 		}
 	}
 	if header.ElementsOrVersion >= 0 {
@@ -1713,13 +1726,14 @@
 			return err
 		}
 		if pointer0 == 0 {
-			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
+			s.InstanceName = nil
 		} else {
+			s.InstanceName = new(string)
 			value0, err := decoder.ReadString()
 			if err != nil {
 				return err
 			}
-			s.InstanceName = value0
+			(*s.InstanceName) = value0
 		}
 	}
 	if header.ElementsOrVersion >= 0 {
@@ -1743,8 +1757,9 @@
 			return err
 		}
 		if pointer0 == 0 {
-			return &bindings.ValidationError{bindings.UnexpectedNullPointer, "unexpected null pointer"}
+			s.Attrs = nil
 		} else {
+			s.Attrs = new(map[string]string)
 			if err := decoder.StartMap(); err != nil {
 				return err
 			}
@@ -1829,7 +1844,7 @@
 			for i0 := 0; i0 < len0; i0++ {
 				map0[keys0[i0]] = values0[i0]
 			}
-			s.Attrs = map0
+			(*s.Attrs) = map0
 		}
 	}
 	if header.ElementsOrVersion >= 0 {
@@ -1874,7 +1889,7 @@
 // String names and labels used by the MojomStruct types.
 var (
 	structName_Service                    = "Service"
-	structFieldName_Service_InstanceUuid  = "InstanceUuid"
+	structFieldName_Service_InstanceId    = "InstanceId"
 	structFieldName_Service_InstanceName  = "InstanceName"
 	structFieldName_Service_InterfaceName = "InterfaceName"
 	structFieldName_Service_Attrs         = "Attrs"
@@ -1887,16 +1902,14 @@
 			ShortName: &structName_Service,
 		}, Fields: []mojom_types.StructField{mojom_types.StructField{
 			DeclData: &mojom_types.DeclarationData{
-				ShortName: &structFieldName_Service_InstanceUuid,
+				ShortName: &structFieldName_Service_InstanceId,
 			},
-			Type: &mojom_types.TypeArrayType{
-				Value: mojom_types.ArrayType{ElementType: &mojom_types.TypeSimpleType{mojom_types.SimpleType_UinT8}},
-			},
+			Type: &mojom_types.TypeStringType{mojom_types.StringType{true}},
 		}, mojom_types.StructField{
 			DeclData: &mojom_types.DeclarationData{
 				ShortName: &structFieldName_Service_InstanceName,
 			},
-			Type: &mojom_types.TypeStringType{mojom_types.StringType{false}},
+			Type: &mojom_types.TypeStringType{mojom_types.StringType{true}},
 		}, mojom_types.StructField{
 			DeclData: &mojom_types.DeclarationData{
 				ShortName: &structFieldName_Service_InterfaceName,
@@ -1907,7 +1920,7 @@
 				ShortName: &structFieldName_Service_Attrs,
 			},
 			Type: &mojom_types.TypeMapType{
-				Value: mojom_types.MapType{KeyType: &mojom_types.TypeStringType{mojom_types.StringType{false}},
+				Value: mojom_types.MapType{Nullable: true, KeyType: &mojom_types.TypeStringType{mojom_types.StringType{false}},
 					ValueType: &mojom_types.TypeStringType{mojom_types.StringType{false}},
 				},
 			},
diff --git a/go/src/vanadium/discovery/internal/discovery.go b/go/src/vanadium/discovery/internal/discovery.go
index 3ae5da2..512e19a 100644
--- a/go/src/vanadium/discovery/internal/discovery.go
+++ b/go/src/vanadium/discovery/internal/discovery.go
@@ -17,7 +17,7 @@
 	"v.io/v23/verror"
 )
 
-type id uint32
+type handleT uint32
 
 // DiscoveryService implements the mojom interface mojom/vanadium/discovery.DiscoveryService.  It
 // is basically a thin wrapper around the Vanadium Discovery API.
@@ -29,13 +29,13 @@
 	mu sync.Mutex
 
 	// The id to assign the next advertisement.
-	nextAdv id
+	nextAdv handleT
 	// A map of advertisement ids to the cancellation function.
-	activeAdvs map[id]func()
+	activeAdvs map[handleT]func()
 	// The id to assign to the next scan.
-	nextScan id
+	nextScan handleT
 	// A map of scan id to the cancellataion func()
-	activeScans map[id]func()
+	activeScans map[handleT]func()
 }
 
 func v2mError(err error) *mojom.Error {
@@ -53,32 +53,38 @@
 		ctx:         ctx,
 		discovery:   v23.GetDiscovery(ctx),
 		nextAdv:     1,
-		activeAdvs:  map[id]func(){},
-		activeScans: map[id]func(){},
+		activeAdvs:  map[handleT]func(){},
+		activeScans: map[handleT]func(){},
 	}
 }
 
-// Advertise advertises the mojom service passed only to the giveen blessing patterns. Returns the
-// handle to this Advertise call.
-func (d *DiscoveryService) Advertise(s mojom.Service, patterns []string) (uint32, *mojom.Error, error) {
+func (d *DiscoveryService) Advertise(service mojom.Service, visibility *[]string) (uint32, string, *mojom.Error, error) {
 	vService := discovery.Service{
-		InstanceUuid:  s.InstanceUuid,
-		InterfaceName: s.InterfaceName,
-		InstanceName:  s.InstanceName,
-		Attrs:         discovery.Attributes(s.Attrs),
-		Addrs:         s.Addrs,
+		InterfaceName: service.InterfaceName,
+		Addrs:         service.Addrs,
+	}
+	if service.InstanceId != nil {
+		vService.InstanceId = *service.InstanceId
+	}
+	if service.InstanceName != nil {
+		vService.InstanceName = *service.InstanceName
+	}
+	if service.Attrs != nil {
+		vService.Attrs = *service.Attrs
+	}
+	var vVisibility []security.BlessingPattern
+	if visibility != nil {
+		vVisibility := make([]security.BlessingPattern, len(*visibility))
+		for i, p := range *visibility {
+			vVisibility[i] = security.BlessingPattern(p)
+		}
 	}
 
 	ctx, cancel := context.WithCancel(d.ctx)
-
-	perms := make([]security.BlessingPattern, len(patterns))
-	for i, pattern := range patterns {
-		perms[i] = security.BlessingPattern(pattern)
-	}
-	done, err := d.discovery.Advertise(ctx, vService, perms)
+	done, err := d.discovery.Advertise(ctx, &vService, vVisibility)
 	if err != nil {
 		cancel()
-		return 0, v2mError(err), nil
+		return 0, "", v2mError(err), nil
 	}
 	d.mu.Lock()
 	currId := d.nextAdv
@@ -88,13 +94,13 @@
 	}
 	d.nextAdv += 2
 	d.mu.Unlock()
-	return uint32(currId), nil, nil
+	return uint32(currId), vService.InstanceId, nil, nil
 }
 
 func (d *DiscoveryService) stopAdvertising(handle uint32) error {
 	d.mu.Lock()
-	stop := d.activeAdvs[id(handle)]
-	delete(d.activeAdvs, id(handle))
+	stop := d.activeAdvs[handleT(handle)]
+	delete(d.activeAdvs, handleT(handle))
 	d.mu.Unlock()
 	if stop != nil {
 		stop()
@@ -103,17 +109,23 @@
 }
 
 func v2mService(s discovery.Service) mojom.Service {
-	return mojom.Service{
-		InstanceUuid:  s.InstanceUuid,
+	mService := mojom.Service{
 		InterfaceName: s.InterfaceName,
-		InstanceName:  s.InstanceName,
-		Attrs:         s.Attrs,
 		Addrs:         s.Addrs,
 	}
+	if len(s.InstanceId) > 0 {
+		mService.InstanceId = &s.InstanceId
+	}
+	if len(s.InstanceName) > 0 {
+		mService.InstanceName = &s.InstanceName
+	}
+	if len(s.Attrs) > 0 {
+		attr := map[string]string(s.Attrs)
+		mService.Attrs = &attr
+	}
+	return mService
 }
 
-// Scan scans for all services that match the query string passed in and calls scanHandler with updates.
-// Returns the handle to this Scan.
 func (d *DiscoveryService) Scan(query string, scanHandler mojom.ScanHandler_Pointer) (uint32, *mojom.Error, error) {
 	ctx, cancel := context.WithCancel(d.ctx)
 	scanCh, err := d.discovery.Scan(ctx, query)
@@ -134,7 +146,7 @@
 			case discovery.UpdateFound:
 				proxy.Found(v2mService(value.Value.Service))
 			case discovery.UpdateLost:
-				proxy.Lost(value.Value.InstanceUuid)
+				proxy.Lost(value.Value.InstanceId)
 			}
 		}
 	}()
@@ -151,8 +163,8 @@
 
 func (d *DiscoveryService) stopScan(handle uint32) error {
 	d.mu.Lock()
-	cancel := d.activeScans[id(handle)]
-	delete(d.activeScans, id(handle))
+	cancel := d.activeScans[handleT(handle)]
+	delete(d.activeScans, handleT(handle))
 	d.mu.Unlock()
 	if cancel != nil {
 		cancel()
diff --git a/go/src/vanadium/discovery/internal/discovery_test.go b/go/src/vanadium/discovery/internal/discovery_test.go
index 6aa62b4..2c64631 100644
--- a/go/src/vanadium/discovery/internal/discovery_test.go
+++ b/go/src/vanadium/discovery/internal/discovery_test.go
@@ -5,12 +5,13 @@
 package internal
 
 import (
+	"fmt"
+	"math/rand"
 	"reflect"
+	"strconv"
 	"sync"
 	"testing"
 
-	"third_party/go/tool/android_arm/src/fmt"
-
 	mojom "mojom/vanadium/discovery"
 
 	"v.io/v23/context"
@@ -32,10 +33,13 @@
 	deleteCh chan struct{}
 }
 
-func (d *mockDiscovery) Advertise(ctx *context.T, s discovery.Service, perms []security.BlessingPattern) (<-chan struct{}, error) {
+func (d *mockDiscovery) Advertise(ctx *context.T, s *discovery.Service, perms []security.BlessingPattern) (<-chan struct{}, error) {
+	if len(s.InstanceId) == 0 {
+		s.InstanceId = strconv.Itoa(rand.Int())
+	}
 	d.mu.Lock()
 	currId := d.id
-	d.services[currId] = s
+	d.services[currId] = *s
 	d.id++
 	d.mu.Unlock()
 	done := make(chan struct{})
@@ -65,6 +69,15 @@
 	return nil
 }
 
+func mkMojomService(instanceId, interfaceName string, attrs map[string]string, addrs []string) mojom.Service {
+	return mojom.Service{
+		InstanceId:    &instanceId,
+		InterfaceName: interfaceName,
+		Attrs:         &attrs,
+		Addrs:         addrs,
+	}
+}
+
 func TestAdvertising(t *testing.T) {
 	mock := &mockDiscovery{
 		trigger:  idiscovery.NewTrigger(),
@@ -76,48 +89,37 @@
 	ctx, shutdown := vtest.V23Init()
 	defer shutdown()
 
-	s := NewDiscoveryService(ctx)
-	testService := mojom.Service{
-		InterfaceName: "v.io/v23/discovery.T",
-		Attrs: map[string]string{
-			"key1": "value1",
-			"key2": "value2",
-		},
-		InstanceName: "service1",
-		Addrs:        []string{"addr1", "addr2"},
-	}
-	id, e1, e2 := s.Advertise(testService, nil)
+	ds := NewDiscoveryService(ctx)
 
+	s1 := mkMojomService("s1", "v.io/discovery", map[string]string{"k1": "v1", "k2": "v2"}, []string{"addr1", "addr2"})
+	h1, id1, e1, e2 := ds.Advertise(s1, nil)
 	if e1 != nil || e2 != nil {
-		t.Fatalf("Failed to start service: %v, %v", e1, e2)
+		t.Fatalf("failed to start service: %v, %v", e1, e2)
+	}
+	if got, want := id1, "s1"; got != want {
+		t.Errorf("got instance id %s, but want %s", got, want)
 	}
 	if len(mock.services) != 1 {
 		t.Errorf("service missing in mock")
 	}
 
 	for _, service := range mock.services {
-		if err := compare(service, testService); err != nil {
+		if err := compare(service, s1); err != nil {
 			t.Error(err)
 		}
-
 	}
 
-	testService2 := mojom.Service{
-		InterfaceName: "v.io/v23/naming.T",
-		Attrs: map[string]string{
-			"key1": "value1",
-			"key2": "value2",
-		},
-		InstanceName: "service2",
-		Addrs:        []string{"addr1", "addr2"},
-	}
-
-	_, e1, e2 = s.Advertise(testService2, nil)
+	s2 := mkMojomService("", "v.io/naming", map[string]string{"k1": "v1", "k2": "v2"}, []string{"addr3", "addr4"})
+	_, id2, e1, e2 := ds.Advertise(s2, nil)
 	if e1 != nil || e2 != nil {
-		t.Fatalf("Failed to start service: %v, %v", e1, e2)
+		t.Fatalf("failed to start service: %v, %v", e1, e2)
 	}
+	if len(id2) == 0 {
+		t.Error("empty instance id returned")
+	}
+	s2.InstanceId = &id2
 
-	s.Stop(id)
+	ds.Stop(h1)
 	// Wait for the deletion to finish.
 	<-mock.deleteCh
 	if len(mock.services) != 1 {
@@ -125,13 +127,12 @@
 	}
 
 	for _, service := range mock.services {
-		if err := compare(service, testService2); err != nil {
+		if err := compare(service, s2); err != nil {
 			t.Error(err)
 		}
-
 	}
 
-	s.StopAll()
+	ds.StopAll()
 	<-mock.deleteCh
 	if len(mock.services) != 0 {
 		t.Errorf("service should have been removed")
diff --git a/lib/gen/dart-gen/mojom/lib/discovery/discovery.mojom.dart b/lib/gen/dart-gen/mojom/lib/discovery/discovery.mojom.dart
index ced6cc3..6c91ff7 100644
--- a/lib/gen/dart-gen/mojom/lib/discovery/discovery.mojom.dart
+++ b/lib/gen/dart-gen/mojom/lib/discovery/discovery.mojom.dart
@@ -15,7 +15,7 @@
   static const List<bindings.StructDataHeader> kVersions = const [
     const bindings.StructDataHeader(48, 0)
   ];
-  List<int> instanceUuid = null;
+  String instanceId = null;
   String instanceName = null;
   String interfaceName = null;
   Map<String, String> attrs = null;
@@ -58,11 +58,11 @@
     }
     if (mainDataHeader.version >= 0) {
       
-      result.instanceUuid = decoder0.decodeUint8Array(8, bindings.kNothingNullable, bindings.kUnspecifiedArrayLength);
+      result.instanceId = decoder0.decodeString(8, true);
     }
     if (mainDataHeader.version >= 0) {
       
-      result.instanceName = decoder0.decodeString(16, false);
+      result.instanceName = decoder0.decodeString(16, true);
     }
     if (mainDataHeader.version >= 0) {
       
@@ -70,8 +70,10 @@
     }
     if (mainDataHeader.version >= 0) {
       
-      var decoder1 = decoder0.decodePointer(32, false);
-      {
+      var decoder1 = decoder0.decodePointer(32, true);
+      if (decoder1 == null) {
+        result.attrs = null;
+      } else {
         decoder1.decodeDataHeaderForMap();
         List<String> keys0;
         List<String> values0;
@@ -121,14 +123,14 @@
   void encode(bindings.Encoder encoder) {
     var encoder0 = encoder.getStructEncoderAtOffset(kVersions.last);
     
-    encoder0.encodeUint8Array(instanceUuid, 8, bindings.kNothingNullable, bindings.kUnspecifiedArrayLength);
+    encoder0.encodeString(instanceId, 8, true);
     
-    encoder0.encodeString(instanceName, 16, false);
+    encoder0.encodeString(instanceName, 16, true);
     
     encoder0.encodeString(interfaceName, 24, false);
     
     if (attrs == null) {
-      encoder0.encodeNullPointer(32, false);
+      encoder0.encodeNullPointer(32, true);
     } else {
       var encoder1 = encoder0.encoderForMap(32);
       int size0 = attrs.length;
@@ -165,7 +167,7 @@
 
   String toString() {
     return "Service("
-           "instanceUuid: $instanceUuid" ", "
+           "instanceId: $instanceId" ", "
            "instanceName: $instanceName" ", "
            "interfaceName: $interfaceName" ", "
            "attrs: $attrs" ", "
@@ -174,7 +176,7 @@
 
   Map toJson() {
     Map map = new Map();
-    map["instanceUuid"] = instanceUuid;
+    map["instanceId"] = instanceId;
     map["instanceName"] = instanceName;
     map["interfaceName"] = interfaceName;
     map["attrs"] = attrs;
@@ -318,8 +320,10 @@
     }
     if (mainDataHeader.version >= 0) {
       
-      var decoder1 = decoder0.decodePointer(16, false);
-      {
+      var decoder1 = decoder0.decodePointer(16, true);
+      if (decoder1 == null) {
+        result.visibility = null;
+      } else {
         var si1 = decoder1.decodeDataHeaderForPointerArray(bindings.kUnspecifiedArrayLength);
         result.visibility = new List<String>(si1.numElements);
         for (int i1 = 0; i1 < si1.numElements; ++i1) {
@@ -337,7 +341,7 @@
     encoder0.encodeStruct(service, 8, false);
     
     if (visibility == null) {
-      encoder0.encodeNullPointer(16, false);
+      encoder0.encodeNullPointer(16, true);
     } else {
       var encoder1 = encoder0.encodePointerArray(visibility.length, 16, bindings.kUnspecifiedArrayLength);
       for (int i0 = 0; i0 < visibility.length; ++i0) {
@@ -364,9 +368,10 @@
 
 class AdvertiserAdvertiseResponseParams extends bindings.Struct {
   static const List<bindings.StructDataHeader> kVersions = const [
-    const bindings.StructDataHeader(24, 0)
+    const bindings.StructDataHeader(32, 0)
   ];
   int handle = 0;
+  String instanceId = null;
   Error err = null;
 
   AdvertiserAdvertiseResponseParams() : super(kVersions.last.size);
@@ -410,7 +415,11 @@
     }
     if (mainDataHeader.version >= 0) {
       
-      var decoder1 = decoder0.decodePointer(16, true);
+      result.instanceId = decoder0.decodeString(16, false);
+    }
+    if (mainDataHeader.version >= 0) {
+      
+      var decoder1 = decoder0.decodePointer(24, true);
       result.err = Error.decode(decoder1);
     }
     return result;
@@ -421,18 +430,22 @@
     
     encoder0.encodeUint32(handle, 8);
     
-    encoder0.encodeStruct(err, 16, true);
+    encoder0.encodeString(instanceId, 16, false);
+    
+    encoder0.encodeStruct(err, 24, true);
   }
 
   String toString() {
     return "AdvertiserAdvertiseResponseParams("
            "handle: $handle" ", "
+           "instanceId: $instanceId" ", "
            "err: $err" ")";
   }
 
   Map toJson() {
     Map map = new Map();
     map["handle"] = handle;
+    map["instanceId"] = instanceId;
     map["err"] = err;
     return map;
   }
@@ -796,7 +809,7 @@
   static const List<bindings.StructDataHeader> kVersions = const [
     const bindings.StructDataHeader(16, 0)
   ];
-  List<int> instanceId = null;
+  String instanceId = null;
 
   ScanHandlerLostParams() : super(kVersions.last.size);
 
@@ -835,7 +848,7 @@
     }
     if (mainDataHeader.version >= 0) {
       
-      result.instanceId = decoder0.decodeUint8Array(8, bindings.kNothingNullable, bindings.kUnspecifiedArrayLength);
+      result.instanceId = decoder0.decodeString(8, false);
     }
     return result;
   }
@@ -843,7 +856,7 @@
   void encode(bindings.Encoder encoder) {
     var encoder0 = encoder.getStructEncoderAtOffset(kVersions.last);
     
-    encoder0.encodeUint8Array(instanceId, 8, bindings.kNothingNullable, bindings.kUnspecifiedArrayLength);
+    encoder0.encodeString(instanceId, 8, false);
   }
 
   String toString() {
@@ -1030,9 +1043,10 @@
   static const String name = AdvertiserName;
 
 
-  AdvertiserAdvertiseResponseParams _AdvertiserAdvertiseResponseParamsFactory(int handle, Error err) {
+  AdvertiserAdvertiseResponseParams _AdvertiserAdvertiseResponseParamsFactory(int handle, String instanceId, Error err) {
     var result = new AdvertiserAdvertiseResponseParams();
     result.handle = handle;
+    result.instanceId = instanceId;
     result.err = err;
     return result;
   }
@@ -1336,7 +1350,7 @@
 
 abstract class ScanHandler {
   void found(Service service);
-  void lost(List<int> instanceId);
+  void lost(String instanceId);
 
 }
 
@@ -1388,7 +1402,7 @@
       _proxyImpl.sendMessage(params, kScanHandler_found_name);
     }
   
-    void lost(List<int> instanceId) {
+    void lost(String instanceId) {
       if (!_proxyImpl.isBound) {
         _proxyImpl.proxyError("The Proxy is closed.");
         return;
diff --git a/mojom/vanadium/discovery.mojom b/mojom/vanadium/discovery.mojom
index f61ccdb..f29ddd2 100644
--- a/mojom/vanadium/discovery.mojom
+++ b/mojom/vanadium/discovery.mojom
@@ -6,17 +6,17 @@
 
 // Copied from v.io/v23/discovery/types.vdl
 struct Service {
-  // The 128 bit (16 byte) universal unique identifier of a service instance.
-  // If this is not specified, a random UUID will be used.
-  array<uint8> InstanceUuid;
+  // The universal unique identifier of a service instance.
+  // If this is not specified, a random 128 bit (16 byte) UUID will be used.
+  string? InstanceId;
   // Optional name of the service instance.
-  string InstanceName;
+  string? InstanceName;
   // The interface that the service implements.
   // E.g., 'v.io/v23/services/vtrace.Store'.
   string InterfaceName;
   // The service attributes.
   // E.g., {'resolution': '1024x768'}.
-  map<string, string> Attrs;
+  map<string, string>? Attrs;
   // The addresses that the service is served on.
   // E.g., '/host:port/a/b/c'.
   array<string> Addrs;
@@ -37,7 +37,7 @@
   //
   // It is an error to have simultaneously active advertisements for two identical
   // instances (service.InstanceUuid).
-  Advertise(Service service, array<string> visibility) => (uint32 Handle, Error? Err);
+  Advertise(Service service, array<string>? visibility) => (uint32 Handle, string instanceId, Error? Err);
 
   // Stop Stops the advertisement associated with the given handle.
   Stop(uint32 h);
@@ -71,5 +71,5 @@
   Found(Service service);
 
   // Lost will be called when a service is lost.
-  Lost(array<uint8> instanceId);
+  Lost(string instanceId);
 };