consensus.go raw

   1  package gnarlring
   2  
   3  import (
   4  	"crypto/rand"
   5  	"io"
   6  )
   7  
   8  // Vote represents a binary choice encoded as a short vectors norm direction.
   9  // A YES vote produces a short vector z where the first coefficient is +1
  10  // (or more generally, has positive aggregate norm). A NO vote produces z
  11  // with negative-norm first coefficient.
  12  type Vote struct {
  13  	Z *Poly27 // short vector encoding the vote
  14  }
  15  
  16  // CastVote produces a short-vector vote. sign = +1 for YES, -1 for NO.
  17  func CastVote(sign int) *Vote {
  18  	return CastVoteFrom(sign, nil)
  19  }
  20  
  21  // CastVoteFrom produces a vote with a given randomness source.
  22  // The vote is a fresh Gaussian vector with the first coefficient encoding
  23  // the sign: 1 for YES, Q-1 for NO (centered = -1).
  24  func CastVoteFrom(sign int, rng io.Reader) *Vote {
  25  	if rng == nil {
  26  		rng = rand.Reader
  27  	}
  28  	gs := NewGaussSamplerFrom(DefaultSigma(), rng)
  29  	z := gs.SamplePoly()
  30  
  31  	if sign >= 0 {
  32  		z.Coeffs[0] = 1
  33  	} else {
  34  		z.Coeffs[0] = Q - 1 // centered = -1
  35  	}
  36  	return &Vote{Z: z}
  37  }
  38  
  39  // VoteTally aggregates multiple votes into a single short vector.
  40  // z_total = Σ vote_i.Z. The norm of z_total encodes the net YES-NO count.
  41  type VoteTally struct {
  42  	Z        *Poly27
  43  	YesCount int
  44  	NoCount  int
  45  }
  46  
  47  // NewVoteTally creates an empty tally.
  48  func NewVoteTally() *VoteTally {
  49  	return &VoteTally{Z: NewPoly27()}
  50  }
  51  
  52  // Add includes a vote in the tally.
  53  func (vt *VoteTally) Add(v *Vote, isYes bool) {
  54  	vt.Z = Add(vt.Z, v.Z)
  55  	if isYes {
  56  		vt.YesCount++
  57  	} else {
  58  		vt.NoCount++
  59  	}
  60  }
  61  
  62  // ConsensusResult returns whether the tally meets a k-of-n threshold.
  63  // True if net YES votes ≥ threshold.
  64  func (vt *VoteTally) ConsensusResult(threshold int) bool {
  65  	return vt.YesCount >= threshold
  66  }
  67  
  68  // NormEstimate returns the expected norm range for k YES votes among
  69  // n total participants. Each vote contributes approximately
  70  // sqrt(N) * DefaultSigma() ≈ 54 to the squared norm.
  71  func VoteNormEstimate(k int) float64 {
  72  	sigma := DefaultSigma()
  73  	perVote := float64(N) * sigma * sigma // expected ||z||² per vote
  74  	return perVote * float64(k)
  75  }
  76  
  77  // VerifyVoteTally checks that the tally's Z vector has norm consistent
  78  // with the expected range for the given yes/no counts.
  79  func VerifyVoteTally(vt *VoteTally) bool {
  80  	expectedYes := VoteNormEstimate(vt.YesCount)
  81  	expectedNo := VoteNormEstimate(vt.NoCount)
  82  	// Net norm: yes contributions mostly cancel with no contributions.
  83  	// The residual norm is sqrt(yes + no) * per_vote * (yes-no)/total.
  84  	// Simplified: check that the observed norm is plausible.
  85  	observed := float64(NormSq(vt.Z))
  86  
  87  	// Maximum possible: all votes aligning (yes - no all same sign).
  88  	maxPossible := expectedYes + expectedNo
  89  
  90  	// Minimum: complete cancellation.
  91  	minPossible := 0.0
  92  
  93  	if observed > maxPossible*1.5 || observed < minPossible {
  94  		return false
  95  	}
  96  	return true
  97  }
  98  
  99  // EncryptedVote wraps a vote in Ring-LWE encryption for private broadcast.
 100  type EncryptedVote struct {
 101  	Ct *LWECiphertext // encrypted vote vector (bit-by-bit or as ring element)
 102  }
 103  
 104  // EncryptVote encrypts a child's vote under the coordinator's LWE public key.
 105  // The vote's sign is encoded as a single LWE-encrypted bit.
 106  func EncryptVote(lwePK *LWEPublicKey, v *Vote, rng io.Reader) *EncryptedVote {
 107  	if rng == nil {
 108  		rng = rand.Reader
 109  	}
 110  	// Decode the sign from the vote vector: compare centered signs.
 111  	// First coefficient encodes the vote: 1 = YES, Q-1 = NO.
 112  	first := v.Z.Coeffs[0]
 113  	bit := 0
 114  	if first == 1 {
 115  		bit = 1 // centered positive = YES
 116  	}
 117  	ct := LWEEncryptFrom(lwePK, bit, rng)
 118  	return &EncryptedVote{Ct: ct}
 119  }
 120  
 121  // DecryptVote decrypts an encrypted vote and returns whether it was YES.
 122  func DecryptVote(lweSK *LWESecretKey, ev *EncryptedVote) bool {
 123  	return LWEDecrypt(lweSK, ev.Ct) == 1
 124  }
 125