Milestone #3 (RC3): Using new test case from RFC draft.

4 files changed, 290 insertions, 84 deletions

diff --git a/src/cmd/revoke-zonekey/main.go b/src/cmd/revoke-zonekey/main.go
index fe0baaa..7deeda6 100644
--- a/src/cmd/revoke-zonekey/main.go
+++ b/src/cmd/revoke-zonekey/main.go
@@ -31,7 +31,6 @@ import (
         "gnunet/service/revocation"
         "gnunet/util"
 
-        "github.com/bfix/gospel/crypto/ed25519"
         "github.com/bfix/gospel/data"
 )
 
@@ -59,12 +58,12 @@ func main() {
 
         // define layout of persistant data
         var revData struct {
-                Rd      *revocation.RevData // Revocation data
-                T       util.RelativeTime   // time spend in calculations
-                Last    uint64              // last value used for PoW test
-                Numbits uint8               // number of leading zero-bits
+                Rd      *revocation.RevDataCalc // Revocation data
+                T       util.RelativeTime       // time spend in calculations
+                Last    uint64                  // last value used for PoW test
+                Numbits uint8                   // number of leading zero-bits
         }
-        dataBuf := make([]byte, 377)
+        dataBuf := make([]byte, 450)
 
         // read revocation object from file
         file, err := os.Open(filename)
@@ -77,8 +76,7 @@ func main() {
                 if err != nil {
                         log.Fatal("Invalid zonekey: " + err.Error())
                 }
-                pkey := ed25519.NewPublicKeyFromBytes(keyData)
-                revData.Rd = revocation.NewRevData(util.AbsoluteTimeNow(), pkey)
+                revData.Rd = revocation.NewRevDataCalc(keyData)
                 revData.Numbits = uint8(bits)
                 revData.T = util.NewRelativeTime(0)
                 cont = false
@@ -121,11 +119,14 @@ func main() {
         wg.Add(1)
         go func() {
                 defer wg.Done()
+                cb := func(average float64, last uint64) {
+                        log.Printf("Improved PoW: %f average zero bits, %d steps\n", average, last)
+                }
 
                 startTime := util.AbsoluteTimeNow()
-                result, last := revData.Rd.Compute(ctx, bits, revData.Last)
-                if result != 32 {
-                        log.Printf("Incomplete revocation: Only %d of 32 PoWs available!\n", result)
+                average, last := revData.Rd.Compute(ctx, bits, revData.Last, cb)
+                if average < float64(bits) {
+                        log.Printf("Incomplete revocation: Only %f zero bits on average!\n", average)
                 } else {
                         log.Println("Revocation data object:")
                         log.Println("   0x" + hex.EncodeToString(revData.Rd.Blob()))
@@ -158,7 +159,7 @@ func main() {
                                 log.Fatal("Internal error: " + err.Error())
                         }
                         if len(buf) != len(dataBuf) {
-                                log.Fatal("Internal error: Buffer mismatch")
+                                log.Fatalf("Internal error: Buffer mismatch %d != %d", len(buf), len(dataBuf))
                         }
                         n, err := file.Write(buf)
                         if err != nil {
diff --git a/src/gnunet/message/msg_revocation.go b/src/gnunet/message/msg_revocation.go
index 8c7db06..c17f440 100644
--- a/src/gnunet/message/msg_revocation.go
+++ b/src/gnunet/message/msg_revocation.go
@@ -105,6 +105,7 @@ type RevocationRevokeMsg struct {
         MsgSize   uint16            `order:"big"` // total size of message
         MsgType   uint16            `order:"big"` // REVOCATION_REVOKE (638)
         Timestamp util.AbsoluteTime // Timestamp of revocation creation
+        TTL       util.RelativeTime // TTL of revocation
         PoWs      []uint64          `size:"32" order:"big"` // (Sorted) list of PoW values
         Signature []byte            `size:"64"`             // Signature (Proof-of-ownership).
         ZoneKey   []byte            `size:"32"`             // public zone key to be revoked
@@ -116,6 +117,7 @@ func NewRevocationRevokeMsg(zoneKey *ed25519.PublicKey, sig *ed25519.EcSignature
                 MsgSize:   364,
                 MsgType:   REVOCATION_REVOKE,
                 Timestamp: util.AbsoluteTimeNow(),
+                TTL:       util.RelativeTime{0},
                 PoWs:      make([]uint64, 32),
                 Signature: make([]byte, 64),
                 ZoneKey:   make([]byte, 32),
diff --git a/src/gnunet/service/revocation/pow.go b/src/gnunet/service/revocation/pow.go
index 4f7fde2..03a89af 100644
--- a/src/gnunet/service/revocation/pow.go
+++ b/src/gnunet/service/revocation/pow.go
@@ -22,6 +22,8 @@ import (
         "bytes"
         "context"
         "encoding/binary"
+        "fmt"
+        "sort"
         "time"
 
         "gnunet/crypto"
@@ -62,13 +64,13 @@ func NewPoWData(pow uint64, ts util.AbsoluteTime, zoneKey []byte) *PoWData {
         return rd
 }
 
+// SetPoW sets a new PoW value in the data structure
 func (p *PoWData) SetPoW(pow uint64) error {
         p.PoW = pow
-        blob, err := data.Marshal(p)
-        if err != nil {
-                return err
+        p.blob = p.Blob()
+        if p.blob == nil {
+                return fmt.Errorf("Invalid PoW work unit")
         }
-        p.blob = blob
         return nil
 }
 
@@ -98,10 +100,19 @@ func (p *PoWData) Next() {
 // Compute calculates the current result for a PoWData content.
 // The result is returned as a big integer value.
 func (p *PoWData) Compute() *math.Int {
-        key := argon2.Key(p.blob, []byte("gnunet-revocation-proof-of-work"), 3, 1024, 1, 64)
+        key := argon2.IDKey(p.blob, []byte("gnunet-revocation-proof-of-work"), 3, 1024, 1, 64)
         return math.NewIntFromBytes(key)
 }
 
+// Blob returns a serialized instance of the work unit
+func (p *PoWData) Blob() []byte {
+        blob, err := data.Marshal(p)
+        if err != nil {
+                return nil
+        }
+        return blob
+}
+
 //----------------------------------------------------------------------
 // Revocation data
 //----------------------------------------------------------------------
@@ -109,6 +120,7 @@ func (p *PoWData) Compute() *math.Int {
 // RevData is the revocation data (wire format)
 type RevData struct {
         Timestamp util.AbsoluteTime // Timestamp of creation
+        TTL       util.RelativeTime // TTL of revocation
         PoWs      []uint64          `size:"32" order:"big"` // (Sorted) list of PoW values
         Signature []byte            `size:"64"`             // Signature (Proof-of-ownership).
         ZoneKey   []byte            `size:"32"`             // public zone key to be revoked
@@ -121,18 +133,6 @@ type SignedRevData struct {
         Timestamp util.AbsoluteTime // Timestamp of creation
 }
 
-// NewRevData initializes a new RevData instance
-func NewRevData(ts util.AbsoluteTime, pkey *ed25519.PublicKey) *RevData {
-        rd := &RevData{
-                Timestamp: ts,
-                PoWs:      make([]uint64, 32),
-                Signature: make([]byte, 64),
-                ZoneKey:   make([]byte, 32),
-        }
-        copy(rd.ZoneKey, pkey.Bytes())
-        return rd
-}
-
 // NewRevDataFromMsg initializes a new RevData instance from a GNUnet message
 func NewRevDataFromMsg(m *message.RevocationRevokeMsg) *RevData {
         rd := &RevData{
@@ -153,7 +153,7 @@ func (rd *RevData) Sign(skey *ed25519.PrivateKey) error {
                         Size:    48,
                         Purpose: enums.SIG_REVOCATION,
                 },
-                ZoneKey:   rd.ZoneKey,
+                ZoneKey:   util.Clone(rd.ZoneKey),
                 Timestamp: rd.Timestamp,
         }
         sigData, err := data.Marshal(sigBlock)
@@ -182,7 +182,7 @@ func (rd *RevData) Verify(withSig bool) int {
                                 Size:    48,
                                 Purpose: enums.SIG_REVOCATION,
                         },
-                        ZoneKey:   rd.ZoneKey,
+                        ZoneKey:   util.Clone(rd.ZoneKey),
                         Timestamp: rd.Timestamp,
                 }
                 sigData, err := data.Marshal(sigBlock)
@@ -202,8 +202,8 @@ func (rd *RevData) Verify(withSig bool) int {
 
         // (2) check PoWs
         var (
-                zbits int    = 512
-                last  uint64 = 0
+                zbits float64 = 0
+                last  uint64  = 0
         )
         for _, pow := range rd.PoWs {
                 // check sequence order
@@ -213,73 +213,144 @@ func (rd *RevData) Verify(withSig bool) int {
                 last = pow
                 // compute number of leading zero-bits
                 work := NewPoWData(pow, rd.Timestamp, rd.ZoneKey)
-                lzb := 512 - work.Compute().BitLen()
-                if lzb < zbits {
-                        zbits = lzb
-                }
+                zbits += float64(512 - work.Compute().BitLen())
         }
+        zbits /= 32.0
 
         // (3) check expiration
-        ttl := time.Duration((zbits-24)*365*24) * time.Hour
-        if util.AbsoluteTimeNow().Add(ttl).Expired() {
-                return -2
+        if zbits > 24.0 {
+                ttl := time.Duration(int((zbits-24)*365*24)) * time.Hour
+                if util.AbsoluteTimeNow().Add(ttl).Expired() {
+                        return -2
+                }
+        }
+        return int(zbits)
+}
+
+//----------------------------------------------------------------------
+// RevData structure for computation
+//----------------------------------------------------------------------
+
+// RevDataCalc is the revocation data structure used while computing
+// the revocation data object.
+type RevDataCalc struct {
+        RevData
+        Bits        []uint16 `size:"32" order:"big"` // number of leading zeros
+        SmallestIdx byte     // index of smallest number of leading zeros
+}
+
+// NewRevDataCalc initializes a new RevDataCalc instance
+func NewRevDataCalc(pkey []byte) *RevDataCalc {
+        rd := &RevDataCalc{
+                RevData: RevData{
+                        Timestamp: util.AbsoluteTimeNow(),
+                        PoWs:      make([]uint64, 32),
+                        Signature: make([]byte, 64),
+                        ZoneKey:   make([]byte, 32),
+                },
+                Bits:        make([]uint16, 32),
+                SmallestIdx: 0,
         }
-        return zbits
+        copy(rd.ZoneKey, pkey)
+        return rd
 }
 
-// Compute tries to compute a valid Revocation; it returns the number of
-// solved PoWs. The computation is complete if 32 PoWs have been found.
-func (rd *RevData) Compute(ctx context.Context, bits int, last uint64) (int, uint64) {
-        // set difficulty based on requested number of leading zero-bits
-        difficulty := math.TWO.Pow(512 - bits).Sub(math.ONE)
+// Average number of leading zero-bits in current list
+func (rdc *RevDataCalc) Average() float64 {
+        var sum uint16 = 0
+        for _, num := range rdc.Bits {
+                sum += num
+        }
+        return float64(sum) / 32.
+}
 
-        // initialize a new work record (single PoW computation)
-        work := NewPoWData(0, rd.Timestamp, rd.ZoneKey)
+// Insert a PoW that is "better than the worst" current PoW element.
+func (rdc *RevDataCalc) Insert(pow uint64, bits uint16) (float64, uint16) {
+        if bits > rdc.Bits[rdc.SmallestIdx] {
+                rdc.PoWs[rdc.SmallestIdx] = pow
+                rdc.Bits[rdc.SmallestIdx] = bits
+                rdc.sortBits()
+        }
+        return rdc.Average(), rdc.Bits[rdc.SmallestIdx]
+}
 
-        // work on all PoWs in a revocation data structure; make sure all PoWs
-        // are set to a valid value (that results in a valid compute() result
-        // below a given threshold)
-        for i, pow := range rd.PoWs {
-                // handle "new" pow value: set it to last_pow+1
-                // this ensures a correctly sorted pow list by design.
-                if pow == 0 && last != 0 {
-                        pow, last = last, 0
+// Get the smallest bit position
+func (rdc *RevDataCalc) sortBits() {
+        var (
+                min uint16 = 512
+                pos        = 0
+        )
+        for i, bits := range rdc.Bits {
+                if bits < min {
+                        min = bits
+                        pos = i
                 }
-                if pow == 0 && i > 0 {
-                        pow = rd.PoWs[i-1] + 1
+        }
+        rdc.SmallestIdx = byte(pos)
+}
+
+// Compute tries to compute a valid Revocation; it returns the average number
+// of leading zero-bits and the last PoW value tried. The computation is
+// complete if the average above is greater or equal to 'bits'.
+func (rdc *RevDataCalc) Compute(ctx context.Context, bits int, last uint64, cb func(float64, uint64)) (float64, uint64) {
+        // find the largest PoW value in current work unit
+        work := NewPoWData(0, rdc.Timestamp, rdc.ZoneKey)
+        var max uint64 = 0
+        for i, pow := range rdc.PoWs {
+                if pow == 0 {
+                        max++
+                        work.SetPoW(max)
+                        res := work.Compute()
+                        rdc.Bits[i] = uint16(512 - res.BitLen())
+                } else if pow > max {
+                        max = pow
                 }
-                // prepare for PoW_i
-                work.SetPoW(pow)
+        }
+        // adjust 'last' value
+        if last <= max {
+                last = max + 1
+        }
 
-                // Find PoW value in an (interruptable) loop
-                out := make(chan bool)
-                go func() {
-                        for {
-                                res := work.Compute()
-                                if res.Cmp(difficulty) < 0 {
-                                        break
-                                }
-                                work.Next()
-                        }
-                        out <- true
-                }()
-        loop:
-                for {
-                        select {
-                        case <-out:
-                                rd.PoWs[i] = work.GetPoW()
-                                break loop
-                        case <-ctx.Done():
-                                return i, work.GetPoW() + 1
+        // Find PoW value in an (interruptable) loop
+        out := make(chan bool)
+        go func() {
+                work.SetPoW(last + 1)
+                smallest := rdc.Bits[rdc.SmallestIdx]
+                average := rdc.Average()
+                for average < float64(bits) {
+                        res := work.Compute()
+                        num := uint16(512 - res.BitLen())
+                        if num > smallest {
+                                pow := work.GetPoW()
+                                average, smallest = rdc.Insert(pow, num)
+                                cb(average, pow)
                         }
+                        work.Next()
+                }
+                out <- true
+        }()
+loop:
+        for {
+                select {
+                case <-out:
+                        break loop
+                case <-ctx.Done():
+                        break loop
                 }
         }
-        // we have found all valid PoW values.
-        return 32, 0
+        // re-order the PoWs for compliance
+        sort.Slice(rdc.PoWs, func(i, j int) bool { return rdc.PoWs[i] < rdc.PoWs[j] })
+        for i, pow := range rdc.PoWs {
+                work.SetPoW(pow)
+                rdc.Bits[i] = uint16(512 - work.Compute().BitLen())
+        }
+        rdc.sortBits()
+        return rdc.Average(), work.GetPoW()
 }
 
-func (rd *RevData) Blob() []byte {
-        blob, err := data.Marshal(rd)
+// Blob returns the binary data structure (wire format).
+func (rdc *RevDataCalc) Blob() []byte {
+        blob, err := data.Marshal(rdc)
         if err != nil {
                 return nil
         }
diff --git a/src/gnunet/service/revocation/pow_test.go b/src/gnunet/service/revocation/pow_test.go
new file mode 100644
index 0000000..aba07d9
--- /dev/null
+++ b/src/gnunet/service/revocation/pow_test.go
@@ -0,0 +1,132 @@
+package revocation
+
+import (
+        "bytes"
+        "encoding/hex"
+        "fmt"
+        "testing"
+
+        "gnunet/util"
+
+        "github.com/bfix/gospel/crypto/ed25519"
+        "github.com/bfix/gospel/data"
+        "github.com/bfix/gospel/math"
+)
+
+type testData struct {
+        skey    string
+        pkey    string
+        revdata string
+}
+
+var (
+        test_data = []testData{
+                {
+
+                        "e01d304d45676849edcb36c843ad31837c9de8c7e58028a2e7c2a9894f130b6f", // private scalar D
+                        "d2c825295cfd3073b6149c4393aa9483c51cfaf62731d2bf1127856913233b78", // public key
+                        "" +
+                                "0005a5fc192e1d2c" + // timestamp
+                                "0000395d1827c000" + // TTL
+                                "f74d39f9ee9a7344" + // PoW_0
+                                "f74d39f9ee9a7610" +
+                                "f74d39f9ee9a7677" +
+                                "f74d39f9ee9a7774" +
+                                "f74d39f9ee9a777d" +
+                                "f74d39f9ee9a77a3" +
+                                "f74d39f9ee9a77ad" +
+                                "f74d39f9ee9a77b9" +
+                                "f74d39f9ee9a77de" +
+                                "f74d39f9ee9a7851" +
+                                "f74d39f9ee9a786f" +
+                                "f74d39f9ee9a78a3" +
+                                "f74d39f9ee9a78ba" +
+                                "f74d39f9ee9a78ca" +
+                                "f74d39f9ee9a7916" +
+                                "f74d39f9ee9a79a9" +
+                                "f74d39f9ee9a7a37" +
+                                "f74d39f9ee9a7a57" +
+                                "f74d39f9ee9a7a5c" +
+                                "f74d39f9ee9a7a9e" +
+                                "f74d39f9ee9a7ad3" +
+                                "f74d39f9ee9a7b1b" +
+                                "f74d39f9ee9a7b7b" +
+                                "f74d39f9ee9a7b83" +
+                                "f74d39f9ee9a7b8b" +
+                                "f74d39f9ee9a7bbe" +
+                                "f74d39f9ee9a7bcc" +
+                                "f74d39f9ee9a7be6" +
+                                "f74d39f9ee9a7c2b" +
+                                "f74d39f9ee9a7c5b" +
+                                "f74d39f9ee9a7c5f" +
+                                "f74d39f9ee9a7c83" + // PoW_31
+                                "05b94e2ad6496a8938aaf122f91edbacf2401cce8ec02e551e2a4433e0a76256" + // Sig.R
+                                "09195bbe7636e9fd9076f8f20bc62467cc8371c487e7809efeaeb6ef7178b623" + // Sig.S
+                                "d2c825295cfd3073b6149c4393aa9483c51cfaf62731d2bf1127856913233b78", // PKEY
+                },
+        }
+)
+
+func TestRevocationRFC(t *testing.T) {
+
+        for i, td := range test_data {
+                if testing.Verbose() {
+                        fmt.Println("---------------------------------")
+                        fmt.Printf("Test case #%d\n", i+1)
+                        fmt.Println("---------------------------------")
+                }
+
+                // construct private/public key pair from test data
+                skey_d, err := hex.DecodeString(td.skey)
+                if err != nil {
+                        t.Fatal(err)
+                }
+                d := math.NewIntFromBytes(util.Reverse(skey_d))
+                skey := ed25519.NewPrivateKeyFromD(d)
+                pkey_d, err := hex.DecodeString(td.pkey)
+                if err != nil {
+                        t.Fatal(err)
+                }
+                if bytes.Compare(skey.Public().Bytes(), pkey_d) != 0 {
+                        t.Fatal("Private/Public key mismatch")
+                }
+
+                // assemble revocation data object
+                rev_d, err := hex.DecodeString(td.revdata)
+                if err != nil {
+                        t.Fatal(err)
+                }
+                revData := new(RevData)
+                if err = data.Unmarshal(revData, rev_d); err != nil {
+                        t.Fatal(err)
+                }
+                if bytes.Compare(revData.ZoneKey, pkey_d) != 0 {
+                        t.Fatal("Wrong zone key in test revocation")
+                }
+
+                // show revdata content
+                if testing.Verbose() {
+                        fmt.Println("REVDATA:")
+                        fmt.Printf("    Timestamp: %s\n", revData.Timestamp.String())
+                        fmt.Printf("    TTL: %s\n", revData.TTL.String())
+
+                        work := NewPoWData(0, revData.Timestamp, revData.ZoneKey)
+                        for i, pow := range revData.PoWs {
+                                fmt.Printf("    PoW #%d: %d\n", i, pow)
+                                work.SetPoW(pow)
+                                buf := work.Blob()
+                                fmt.Printf("        P: %s\n", hex.EncodeToString(buf))
+                                v := work.Compute()
+                                fmt.Printf("        H: %s\n", hex.EncodeToString(v.Bytes()))
+                                num := 512 - v.BitLen()
+                                fmt.Printf("        --> %d leading zeros\n", num)
+                        }
+                        fmt.Printf("    Signature: %s\n", hex.EncodeToString(revData.Signature))
+                        fmt.Printf("    ZoneKey: %s\n", hex.EncodeToString(revData.ZoneKey))
+                }
+
+                // verify revocation data object
+                rc := revData.Verify(true)
+                fmt.Printf("REV_Verify (pkey): %d\n", rc)
+        }
+}