circuits/combine_pms_shares.casm

# This circuit sums 2 256-bit values and (if needed) reduces the sum mod P-256 prime
# ideally, we would need a proper circuit for 256-bit addition 
# since we only have a 64-bit circuit, we work around by summing chunks
# (and waste ~500 AND gates in the process :( )

24 1348
2 256 256
1 256

# the map of wires
# 0|>512 inputs
# 512: zero bit
# 513: carry bit
# 514|>257 sum of pms shares
# 771|>64 temp storage for chunk additions 
# 835 "is less than" bit
# 836|>256 prime's "one's complement"
# 1092|>256 outputs

2 1 0 0 512 XOR #zero

# add 1st batch of 63-bit summands
128 64 [0|>63] 512 [256|>63] 512 [514|>63] 513 adder64.txt

# add the carry bit to one of the 2nd summands (pad the carry to 64 bits)
128 64 [63|>63] 512 513 [512*63] [771|>64] adder64.txt

# add 2nd batch of summands
128 64 [771|>64] [319|>63] 512 [577|>63] 513 adder64.txt

# carry bit + 3rd batch summand
128 64 [126|>63] 512 513 [512*63] [771|>64] adder64.txt

# add 3rd batch of summands
128 64 [771|>64] [382|>63] 512 [640|>63] 513 adder64.txt

# carry bit + 4th batch summand
128 64 [189|>63] 512 513 [512*63] [771|>64] adder64.txt

# add 4th batch of summands
128 64 [771|>64] [445|>63] 512 [703|>63] 513 adder64.txt

# one last batch of only 4 bits left
#carry bit + 5th batch summand
128 64 [252|>4] [512*60] 513 [512*63] [771|>64] adder64.txt

# add 5th batch of summands
# only 5 bits of output go to the sum, the rest is discarded by assigning to some unused wires
128 64 [771|>64] [508|>4] [512*60] [766|>5] [836|>59] adder64.txt

# --------------- 10 gates at this point

# temporarily store the value in outputs section
2 256 0 1 [1092|>256] getP256prime.casm

# check if prime is less than sum of shares 
# we only compare 32 msb (ideally we'd need a 256-bit comparing circuit)
# we are comparing 256bits vs 257bits, so adding a 0 bit to prime's msb
64 1 [1317|>31] 512 [739|>32] 835 compare-lt-32-bit-unsigned-old.txt

# temporarily store the value in outputs section
2 256 0 1 [1092|>256] getP256primeOnesComplement.casm

# if sum of shares < prime, then we subtract 0, otherwise subtract prime
257 256 [1092|>256] 835 [836|>256] mult256by1.casm

# we subtract using the "one's complement" method:
# we add chunks of 63 bits like earlier to arrive at a 257-bit sum
# (since we already know that minuend > subtrahend, the leading bit of the sum will always be one)
# then drop the leading 1 of the sum and add 1 to the sum

# add 1 from "one's complement" method to lsb of one of the batch1 summands
# note that if sum of shares < prime, we add 0 instead of 1 
128 64 [514|>63] 512 835 [512*63] [771|>64] adder64.txt

# batch 1 add 
128 64 [771|>64] [836|>63] 512 [1092|>63] 513 adder64.txt

# add the carry bit to one of the 2nd summands (pad the carry to 64 bits)
128 64 [577|>63] 512 513 [512*63] [771|>64] adder64.txt

# add the 2nd batch of summands
128 64 [771|>64] [899|>63] 512 [1155|>63] 513 adder64.txt

# carry bit + 3rd batch summand
128 64 [640|>63] 512 513 [512*63] [771|>64] adder64.txt

# add 3rd batch of summands
128 64 [771|>64] [962|>63] 512 [1218|>63] 513 adder64.txt

# -------------------20 gates at this point

# carry bit + 4th batch summand
128 64 [703|>63] 512 513 [512*63] [771|>64] adder64.txt

# add 4th batch of summands
128 64 [771|>64] [1025|>63] 512 [1281|>63] 513 adder64.txt

# one last batch of only 4 bits left
# carry bit + 5th batch summand
128 64 [766|>5] [512*59] 513 [512*63] [771|>64] adder64.txt

# add 5th batch of summands
# only 4 bits of output go to the sum
# (the 5th bit is discarded because of the "one's complement" method),
# the rest is discarded by assigning it to some unused wires
128 64 [771|>64] [1088|>4] [512*60] [1344|>4] [836|>60] adder64.txt