commit dfbb3455b58cfa7b74c4442cae0c8bade7ffef7c
parent 58968de4f88aad3014ca1cfd5ce3d99590733642
Author: Bernd Fix <brf@hoi-polloi.org>
Date: Tue, 26 May 2020 11:09:41 +0200
Milestone #3 (RC3): Using new test case from RFC draft.
Diffstat:
4 files changed, 290 insertions(+), 84 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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)
+ }
+}
