Closed lukechampine closed 4 months ago
@lukechampine
See:
Scripts:
Data:
I can test this branch soon as well.
Thanks, added those vectors and confirmed they are passing 👍🏻
I'm glad to see everything is working. I have looked at it and can test it fully once verifying slices are implemented. I looked at BaoDecode
and can possibly see how I could refactor this to a streaming io.Reader
, but would require a fork to do so. Right now the verifying use case is on-the-fly, and so I would have to be in control of the Read function vs the automatic recursion.
Thanks.
@lukechampine Is it possible to have an API that takes a chunk (e.g., 256 kb data), the chunk group size, the offset, the outboard proof, and the root hash and statelessly verifies it?
This means having complete control over any seeking or partial verification. I see what you added regarding the write streaming, but I really need to verify a single slice.
Right now, I stream directly from an S3 bucket and wrap that in an io.Reader
that verifies transparently each 256 kb chunk and errors out if it fails. The design will be painful/bad if I have to delegate the whole process to BaoDecode (like using a coroutine).
To give you an idea of what I currently do, here is some of the code:
type Verifier struct {
r io.ReadCloser
proof Result
read uint64
buffer *bytes.Buffer
logger *zap.Logger
readTime []time.Duration
verifyTime time.Duration
}
func (v *Verifier) Read(p []byte) (int, error) {
// Initial attempt to read from the buffer
n, err := v.buffer.Read(p)
if n == len(p) {
// If the buffer already had enough data to fulfill the request, return immediately
return n, nil
} else if err != nil && err != io.EOF {
// For errors other than EOF, return the error immediately
return n, err
}
buf := make([]byte, VERIFY_CHUNK_SIZE)
// Continue reading from the source and verifying until we have enough data or hit an error
for v.buffer.Len() < len(p)-n {
readStart := time.Now()
bytesRead, err := io.ReadFull(v.r, buf)
if err != nil && err != io.EOF && err != io.ErrUnexpectedEOF {
return n, err // Return any read error immediately
}
readEnd := time.Now()
v.readTime = append(v.readTime, readEnd.Sub(readStart))
timeStart := time.Now()
if bytesRead > 0 {
if status, err := bao.Verify(buf[:bytesRead], v.read, v.proof.Proof, v.proof.Hash); err != nil || !status {
return n, errors.Join(ErrVerifyFailed, err)
}
v.read += uint64(bytesRead)
v.buffer.Write(buf[:bytesRead]) // Append new data to the buffer
}
timeEnd := time.Now()
v.verifyTime += timeEnd.Sub(timeStart)
if err == io.EOF {
// If EOF, break the loop as no more data can be read
break
}
}
if len(v.readTime) > 0 {
averageReadTime := lo.Reduce(v.readTime, func(acc time.Duration, cur time.Duration, _ int) time.Duration {
return acc + cur
}, time.Duration(0)) / time.Duration(len(v.readTime))
v.logger.Debug("Read time", zap.Duration("average", averageReadTime))
}
averageVerifyTime := v.verifyTime / time.Duration(v.read/VERIFY_CHUNK_SIZE)
v.logger.Debug("Verification time", zap.Duration("average", averageVerifyTime))
// Attempt to read the remainder of the data from the buffer
additionalBytes, _ := v.buffer.Read(p[n:])
return n + additionalBytes, nil
}
Thanks.
It might not be as bad as you think to invert the control flow. For example, say you're reading a bao encoding from the network, and you want to send verified bytes as an HTTP response. That would look like:
func HandleHTTP(w http.ResponseWriter, req *http.Request) {
data, outboard, root := getBaoEncoding(req)
ok, err := blake3.BaoDecode(w, data, outboard, 8, root)
if !ok || err != nil {
http.Error(/* ... */)
return
}
}
If you want to add logging to the reads, you can wrap the reader:
type loggingReader struct {
r io.Reader
log *zap.Logger
}
func (lr loggingReader) Read(p []byte) (int, error) {
start := time.Now()
n, err := lr.r.Read(p)
lr.log.Debug("Read time", zap.Duration("", time.Since(start)))
return n, err
}
// in HandleHTTP
ok, err := blake3.BaoDecode(w, loggingReader{data, log}, outboard, 8, root)
It's certainly possible to rewrite BaoDecode
so that you Write
to it instead of passing an io.Reader
, but I'd have to swap the recursion for an explicit stack, which would be a tricky refactor. Instead, perhaps you could use io.Pipe()
:
// in NewVerifier
pipeReader, pipeWriter := io.Pipe()
go func() {
ok, err := blake3.BaoDecode(v.buffer, pipeReader, outboard, 8, root)
// handle ok and error, probably by sending them down a channel
}()
// in Verifier
for {
n, err := io.ReadFull(v.r, buf)
pipeWriter.Write(buf[:n]
}
(Needing a goroutine is pretty ugly here, admittedly. Maybe this is the coroutine approach you mentioned.)
I looked and thought I could hack baodecode to do the verify slice, but it would require either forking and adding or forking and exposing internals.
Any effort I make on that would be trial and error since I'm not the expert on this algorithm. However, this is a requirement in the long term if any Go code wants to seek a file and verify it as the canonical Rust version allows.
I am not asking to change BaoDecode but to add a BaoVerifySlice
or BaoDecodeSlice
method.
And yes, what you are saying is similar. I would need a separate thread to let it process and use channels or something else to track it. I feel that's overcomplicating it, and an additional stateless version is best.
The important logic in my code is:
if status, err := bao.Verify(buf[:bytesRead], v.read, v.proof.Proof, v.proof.Hash); err != nil || !status {
return n, errors.Join(ErrVerifyFailed, err)
}
With it verifying a single chunk stateless.
So, yes, I might make this work as-is (I am not 100% sure yet, as I'm not accepting an inbound HTTP, but doing a background cron that makes an s3 SDK request), but it would not be ideal nor cover long-term possibilities with partial streaming/seeking.
Thanks.
Just to be clear, is this your desired API?
type BaoVerifier struct
func (BaoVerifier) Verify(chunk []byte) bool
func NewVerifier(outboard []byte, group int, root [32]byte) *BaoVerifier
That is the API I use in my code (though as a transparent reader, not as a verify object). It should ideally be a single function instead of a class, but that depends on how it needs to be designed.
But roughly high level I am asking for (argument order doesn't matter):
BaoVerifySlice([]byte data, offset uint64, outboard []byte, group int, root [32]byte) bool
The goal is that any chunk in the stream can be verified stateless, knowing its data offset, the chunk data, the proof, the group size, and the root hash.
That is basically what the rust does. Ex from redsolvers code:
pub fn verify_integrity(
chunk_bytes: Vec<u8>,
offset: u64,
bao_outboard_bytes: Vec<u8>,
blake3_hash: Vec<u8>,
) -> u8 {
let res = verify_integrity_internal(
chunk_bytes,
offset,
bao_outboard_bytes,
from_vec_to_array(blake3_hash),
);
if res.is_err() {
0
}else{
42
}
}
pub fn verify_integrity_internal(
chunk_bytes: Vec<u8>,
offset: u64,
bao_outboard_bytes: Vec<u8>,
blake3_hash: [u8; 32],
) -> anyhow::Result<u8> {
let mut slice_stream = abao::encode::SliceExtractor::new_outboard(
FakeSeeker::new(&chunk_bytes[..]),
Cursor::new(&bao_outboard_bytes),
offset,
262144,
);
let mut decode_stream = abao::decode::SliceDecoder::new(
&mut slice_stream,
&abao::Hash::from(blake3_hash),
offset,
262144,
);
let mut decoded = Vec::new();
decode_stream.read_to_end(&mut decoded)?;
Ok(1)
}
Thanks.
Ok, added support for slices. The equivalent of that Rust code is now:
func verifyIntegrityInternal(chunk_bytes []byte, offset uint64, bao_outboard_bytes []byte, blake3_hash [32]byte) bool {
var buf bytes.Buffer
blake3.BaoExtractSlice(&buf, bytes.NewReader(chunk_bytes), bytes.NewReader(bao_outboard_bytes), 8, offset, 262144)
_, ok := blake3.BaoVerifySlice(buf.Bytes(), 8, offset, 262144, blake3_hash)
return ok
}
I'm not in love with this API, but it's workable. I think I implemented the slice format correctly, but pls test
Thanks, I will test this tomorrow. One suggestion I have is that you should edit the BaoDecode
. If keeping dst io.Writer
change:
write := func(p []byte) {
if err == nil {
_, err = dst.Write(p)
}
}
to
write := func(p []byte) {
if err == nil && dst != nil {
_, err = dst.Write(p)
}
}
so that it is an optional feature (vs using io.Discard or something).
I have done testing, and assuming I have not to made an error, it seems to fail at the first chainingValue based on my IDE debugger. I also found your tests only have group 0 and no higher group. I tested abao's default group 4 and s5 group 8 (each requires a new rust build to change the features config).
Here is a test script I created based on some of my portal code:
package main
import (
"bytes"
"encoding/hex"
"errors"
"github.com/docker/go-units"
"github.com/samber/lo"
"go.uber.org/zap"
"io"
"lukechampine.com/blake3"
"os"
"time"
)
const VERIFY_CHUNK_SIZE = 16 * units.KiB
const VERIFY_GROUP = 4
func main() {
filePath := ""
proofPath := "output.obao"
hashStr := "871208da7506cf458575b8d9b44652c66e53a74f94cdbcb4ee1910d6359808c1"
file, err := os.OpenFile(filePath, os.O_RDONLY, 0)
if err != nil {
panic(err)
}
proof, err := os.OpenFile(proofPath, os.O_RDONLY, 0)
if err != nil {
panic(err)
}
hash, err := hex.DecodeString(hashStr)
if err != nil {
panic(err)
}
proofData, err := io.ReadAll(proof)
if err != nil {
panic(err)
}
stats, err := file.Stat()
if err != nil {
panic(err)
}
verifier := NewVerifier(file, Result{
Hash: hash,
Proof: proofData,
Length: uint(stats.Size()),
})
_, err = io.ReadAll(verifier)
if err != nil {
panic(err)
}
}
type Verifier struct {
r io.ReadCloser
proof Result
read uint64
buffer *bytes.Buffer
logger *zap.Logger
readTime []time.Duration
verifyTime time.Duration
}
func (v *Verifier) Read(p []byte) (int, error) {
// Initial attempt to read from the buffer
n, err := v.buffer.Read(p)
if n == len(p) {
// If the buffer already had enough data to fulfill the request, return immediately
return n, nil
} else if err != nil && err != io.EOF {
// For errors other than EOF, return the error immediately
return n, err
}
buf := make([]byte, VERIFY_CHUNK_SIZE)
// Continue reading from the source and verifying until we have enough data or hit an error
for v.buffer.Len() < len(p)-n {
readStart := time.Now()
bytesRead, err := io.ReadFull(v.r, buf)
if err != nil && err != io.EOF && err != io.ErrUnexpectedEOF {
return n, err // Return any read error immediately
}
readEnd := time.Now()
v.readTime = append(v.readTime, readEnd.Sub(readStart))
timeStart := time.Now()
if bytesRead > 0 {
if status, err := verifyIntegrityInternal(buf[:bytesRead], v.read, v.proof.Proof, v.proof.GetProof()); err != nil || !status {
return n, errors.Join(errors.New("verification failed"), err)
}
v.read += uint64(bytesRead)
v.buffer.Write(buf[:bytesRead]) // Append new data to the buffer
}
timeEnd := time.Now()
v.verifyTime += timeEnd.Sub(timeStart)
if err == io.EOF {
// If EOF, break the loop as no more data can be read
break
}
}
if len(v.readTime) > 0 {
averageReadTime := lo.Reduce(v.readTime, func(acc time.Duration, cur time.Duration, _ int) time.Duration {
return acc + cur
}, time.Duration(0)) / time.Duration(len(v.readTime))
v.logger.Debug("Read time", zap.Duration("average", averageReadTime))
}
averageVerifyTime := v.verifyTime / time.Duration(v.read/VERIFY_CHUNK_SIZE)
v.logger.Debug("Verification time", zap.Duration("average", averageVerifyTime))
// Attempt to read the remainder of the data from the buffer
additionalBytes, _ := v.buffer.Read(p[n:])
return n + additionalBytes, nil
}
func (v *Verifier) Close() error {
return v.r.Close()
}
func NewVerifier(r io.ReadCloser, proof Result) *Verifier {
logger, _ := zap.NewDevelopment()
return &Verifier{
r: r,
proof: proof,
buffer: new(bytes.Buffer),
logger: logger,
}
}
type Result struct {
Hash []byte
Proof []byte
Length uint
proof32 [32]byte
}
func (r *Result) GetProof() [32]byte {
var allZero = true
for _, b := range r.proof32 {
if b != 0 {
allZero = false
break
}
}
if allZero && len(r.Proof) > 0 {
copy(r.proof32[:], r.Proof)
}
return r.proof32
}
func verifyIntegrityInternal(chunk_bytes []byte, offset uint64, bao_outboard_bytes []byte, blake3_hash [32]byte) (bool, error) {
var buf bytes.Buffer
err := blake3.BaoExtractSlice(&buf, bytes.NewReader(chunk_bytes), bytes.NewReader(bao_outboard_bytes), VERIFY_GROUP, offset, VERIFY_CHUNK_SIZE)
if err != nil {
return false, err
}
_, ok := blake3.BaoVerifySlice(buf.Bytes(), VERIFY_GROUP, offset, VERIFY_CHUNK_SIZE, blake3_hash)
return ok, nil
}
cargo install bao_bin
, then run bao encode 'FILE' --outboard=output.obao
.cargo install bao_bin
installs standard bao (from crates.io), not abao. After cloning and installing with cargo install --path ./bao_bin
, I got this code to verify an outboard encoding:
func main() {
file, err := os.Open("<path to file>")
if err != nil {
panic(err)
}
proof, err := os.ReadFile("output.obao")
if err != nil {
panic(err)
}
var root [32]byte
hex.Decode(root[:], []byte("871208da7506cf458575b8d9b44652c66e53a74f94cdbcb4ee1910d6359808c1"))
v := &Verifier{
r: file,
proof: proof,
root: root,
}
if _, err := io.Copy(io.Discard, v); err != nil {
panic(err)
}
}
type Verifier struct {
r io.Reader
proof []byte
root [32]byte
buf bytes.Buffer
offset uint64
}
func (v *Verifier) Read(p []byte) (int, error) {
if v.buf.Len() == 0 {
n, err := io.CopyN(&v.buf, v.r, VERIFY_CHUNK_SIZE)
if err != nil && err != io.EOF && err != io.ErrUnexpectedEOF {
return 0, err
} else if !verifyIntegrityInternal(v.buf.Bytes()[:n], v.offset, v.proof, v.root) {
v.buf.Reset() // don't expose unverified data to future Read calls
return 0, fmt.Errorf("integrity check failed at offset %d", v.offset)
}
v.offset += uint64(n)
}
return v.buf.Read(p)
}
func verifyIntegrityInternal(chunk []byte, offset uint64, outboard []byte, root [32]byte) bool {
const group = 4
var buf bytes.Buffer
length := uint64(len(chunk_bytes))
blake3.BaoExtractSlice(&buf, bytes.NewReader(chunk), bytes.NewReader(outboard), group, offset, length)
_, ok := blake3.BaoVerifySlice(buf.Bytes(), group, offset, length, root)
return ok
}
I should note, though, that extracting a new slice for every chunk is not very efficient. (In fact, it is "accidentally quadratic," because BaoExtractSlice
has to read the outboard from the beginning every time.) If you know how many chunks you need to verify ahead of time, you definitely want to be extracting one slice that covers all of them.
package main
import (
"bytes"
"encoding/hex"
"fmt"
"github.com/docker/go-units"
"io"
"lukechampine.com/blake3"
"os"
)
const VERIFY_CHUNK_SIZE = 16 * units.KiB
func main() {
file, err := os.Open("<VIDEO>")
if err != nil {
panic(err)
}
proof, err := os.ReadFile("<PROOF>")
if err != nil {
panic(err)
}
var root [32]byte
hex.Decode(root[:], []byte("871208da7506cf458575b8d9b44652c66e53a74f94cdbcb4ee1910d6359808c1"))
v := &Verifier{
r: file,
proof: proof,
root: root,
}
if _, err := io.Copy(io.Discard, v); err != nil {
panic(err)
}
}
type Verifier struct {
r io.Reader
proof []byte
root [32]byte
buf bytes.Buffer
offset uint64
}
func (v *Verifier) Read(p []byte) (int, error) {
if v.buf.Len() == 0 {
n, err := io.CopyN(&v.buf, v.r, VERIFY_CHUNK_SIZE)
if err != nil && err != io.EOF && err != io.ErrUnexpectedEOF {
return 0, err
} else if !verifyIntegrityInternal(v.buf.Bytes()[:n], v.offset, v.proof, v.root) {
v.buf.Reset() // don't expose unverified data to future Read calls
return 0, fmt.Errorf("integrity check failed at offset %d", v.offset)
}
v.offset += uint64(n)
}
return v.buf.Read(p)
}
func verifyIntegrityInternal(chunk []byte, offset uint64, outboard []byte, root [32]byte) bool {
const group = 4
var buf bytes.Buffer
length := uint64(len(chunk))
blake3.BaoExtractSlice(&buf, bytes.NewReader(chunk), bytes.NewReader(outboard), group, offset, length)
_, ok := blake3.BaoVerifySlice(buf.Bytes(), group, offset, length, root)
return ok
}
I re-dumped the encoding (to double check) and hashed the file I have again and verified, and seem to be getting integrity check failed at offset 32768
. I also compiled and used a local not installed version of abao
with group 4 enabled.
As for the accidentally quadratic
issue, based on my understanding of the code, your basically combining the outboard at X offset with the data chunk provided and then passing that to be verified. My interest in a stateless function is based on what I have been dealing with high level but realize the rust seems to be using some stateful approach every time potentially?
What I am seeing as a possible solution from what I do understand is creating a large array of all the outboard slice parts (possibly a struct type), split up, where it would then get the data injected after on every verification, so your not doing a scan each run but just an index lookup based on memory.
Though If you know how many chunks you need to verify ahead of time, you definitely want to be extracting one slice that covers all of them.
if it is possible to use BaoExtractSlice
if the whole filesize is known, but the whole file can't be read with BaoVerifySlice
/BaoDecodeSlice
that would be good. Otherwise pre-preparing the outboard so it get splits up to be reused for every chunk being verified would likely be needed, unless there is a better approach.
Thanks.
The root hash will always match; increasing the size of the chunk groups does not change the root hash. I checked again, and integrity check failed at offset 32768
is exactly the error you get if you're trying to decode a standard bao
encoding instead of a 16-KIB abao
encoding.
Here's an easy way to check what version of bao
you're using:
$ truncate -s 1M zeroes
$ bao encode zeroes --outboard zeroes.abao
$ wc -c zeroes.abao
If you're running standard bao
, you'll see 65480
. If you're running abao
with 16 KB chunk groups, you'll see 4040
.
As for being accidentally quadratic, I suspect it won't be a big deal in practice, but as always you should benchmark it to make sure.
The quadratic issue seems to be extreme.
I also seem to be unable to get a group 8 encoding to verify, but a group 4 works fine.
In a group 4 encoding:
So there are definitely some outstanding issues here IMHO based on some basic testing. I am using go run to test this with the time
*nix command.
Hmm. Looking into this. Verification works for group <= 4, but not above that. Strange.
In the meantime, can you describe how verified streaming fits into your broader system? I'm wondering if there's a way to avoid the quadratic behavior.
Right now, any file above 100 mb is uploaded to s3.
That is then hashed when downloaded from s3 and both the file and proof are sent to sia. This roughly follows what S5 does. It knows the valid hash ahead of time as its passed in HTTP headers via TUS, and stored in db, following what S5 has implemented.
The more immediate term I have network imports where a file is downloaded off the S5 network and sent to S3. This is effectively network pinning
. It is then queued and verified before being uploaded to Sia.
Q2 per my grant this year, I will also be sharing the Sia file metadata from renterd
between portals, and will need to likely verify the data there as well.
Longer term, I see the slice verification (streaming) usable in go applications, though I don't have any immediate plans besides the portal system.
Overall the key thing regarding the approach ive taken is im streaming on the fly from A to B as a io.Reader
and having the chunks be transparently verified, without the whole file in memory. And while im not rewinding or jumping around currently, I feel having the slice support important long term.
Thanks.
Turned out to be a simple fix. All group sizes should work now.
I agree that there should be an easy, efficient way to verify chunk n given the full outboard encoding. Even the Rust code you posted above, IIUC, is suboptimal, because it extracts a new Bao slice just to immediately verify it -- meaning it duplicates all of the chunk data in memory!
That said, even the optimal version of this (which would read directly from the outboard to verify, instead of materializing a new slice encoding) ends up duplicating work compared to verifying multiple chunks at a time. It won't be O(n^2)
, but it will be O(n log n)
, because you verify log n
nodes per chunk. If you instead verify multiple chunks at a time, you should be able to run at essentially "full speed," i.e. verifying will be just as fast as calling blake3.Sum256
. So I think the API you really want looks more like:
var buf bytes.Buffer
blake3.BaoExtractSlice(&buf, bytes.NewReader(chunkData), bytes.NewReader(outboard), group, offset, length)
v := NewVerifier(r, buf.Bytes(), group, root)
io.Copy(dst, v)
That is, scope each verifier to a particular offset and length, and initialize it with an extracted slice for that range.
I don't think this is easy (perhaps not even possible) with what blake3
currently provides, but I can accommodate it if you agree that it's the right API.
I assume that would basically be put in verify_integrity_internal
/verify_integrity
and can be called for every chunk im reading from. If so and that API ensures im in control of reading on a per-chunk basis vs giving full control over to BaoDecode
and needing co-routine hacks, then im cool with that.
You also say verifying multiple chunks at a time and if you mean somehow batch processing multiple offsets... that's technically possible for me to do as well I think, but I may be mis-understanding :shrug: .
ok, added a BaoVerifyChunks
function, which directly skips over any unneeded portions of the outboard encoding (rather than reading+discarding them). I ran some benchmarks and it's definitely faster than BaoExtractSlice + BaoVerifySlice
, but idk how it stacks up against the Rust version.
I ran some tests myself based on a 1 GB file and 5 GB file. The following data is AI generated.
File Size | Verification Time | Source Data |
---|---|---|
1 GB | 1.1 seconds | 1 GB file takes ~1.1 sec |
5 GB | 5.45 seconds | 5 GB file (4867764 bytes) takes 5.4-5.5 sec |
100 GB | 1.87 minutes | Extrapolated based on 5 GB file |
500 GB | 9.33 minutes | Extrapolated based on 5 GB file |
1 TB | 18.67 minutes | Extrapolated based on 5 GB file |
2 TB | 37.33 minutes | Extrapolated based on 5 GB file |
5 TB | 1.56 hours | Extrapolated based on 5 GB file |
The computation is linear. I also used abao decode
in group 8 abao decode 3e6be628f8a6ddb91905a2465a15b7071f72c61f99e70acbb8529e75ec3bb385 files-5GB-zip --outboard=output.bao &> /dev/null
for the 5GB data file I used (a zip archive) and it was around 7.8 seconds, so you seem to be beating it!, unless its i/o piping overhead causing that.
Based on all this it is a massive improvement and seems to rival the rust version :upside_down_face:. TBD to see how it performs with HTTP streaming, but on disk i/o it seems fine.
Nice! I definitely encourage collecting a few more datapoints to confirm the trend. I would expect it to grow linearithmically (n log n), so I'm curious what the actual time for a 100 GB file would be.
Anyway, it seems like this is good to merge. However, I'm wary of polluting the blake3
namespace with a bunch of Bao functionality, so I'll probably split it into a separate package.
I will provide feedback when I have some data collected on this.
I have gotten this implemented in the portal at https://github.com/LumeWeb/portal/commit/8d98f131d5b090e22c1343356e8d4787a0f0157d and will be testing it on my dev node soon.
Ive just started doing testing and debugging around functions using the verification. The debug timer code I have in is logging in zap that every 256kB chunk, streamed from S5 P2P up into S3, is about 104 ms processing, and this CID, https://cid.one/#z6e5rKQLuohQGLqnRvkUrLVzcsgFhkyM2QxGfWcx5JHC6Z8jXqqYT, 1073741824 bytes takes about 21.6s
total summed up from processing 205 parts.
I have yet to test anything larger, though I will likely end up testing a 1 tb file as that will be something that will get some demand.
This does not isolate all the reader code from the bao verify code directly, so there could be inefficiencies on my side.
Regardless, this is working, and the only thing left is to optimize it if needed in the future.
Kudos :smile:
Merged! Note that all Bao-related code now lives in the bao
package, rather than the top-level blake3
package.
See #17
I don't have test vectors to compare against; @pcfreak30 or @redsolver, can you provide test vectors and/or test this implementation against them? (For 256KiB chunk groups, pass
group = 8
)