Skip to content

Instantly share code, notes, and snippets.

/HashTest

Created December 29, 2016 05:42
Show Gist options
  • Save anonymous/d30af9d7ea52c0882ed433cd675b5207 to your computer and use it in GitHub Desktop.
Save anonymous/d30af9d7ea52c0882ed433cd675b5207 to your computer and use it in GitHub Desktop.
Download ZIP
Created using browser-solidity: Realtime Ethereum Contract Compiler and Runtime. Load this file by pasting this gists URL or ID at https://ethereum.github.io/browser-solidity/#version=soljson-v0.4.7+commit.822622cf.js&optimize=true&gist=
Raw
HashTest
pragma solidity ^0.4.7;
contract HashVerifier {
function hashing(bytes32 x,uint limit) returns (bytes32){
for (uint i=0;i<limit;++i){
x=sha3(x);
}
return x;
}
function hashingAssmebly(bytes32 x,uint limit) public returns (bytes32){
assembly{
mstore(0x0,x)
let n:=0
loop:
jumpi(loopend, eq(n, limit))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
mstore(0x0,sha3(0x0,32))
n := add(n, 1)
jump(loop)
loopend:
return(x,32)
}
}
}
Raw
ModularSquaring
pragma solidity ^0.4.7;
contract ModSquaring{
//It is faster to pass in the parameters then to store them in the contract
//mu is precomputed as in http://cacr.uwaterloo.ca/hac/about/chap14.pdf 14.42
function squareMod(uint128[] a,uint128[] p,uint128[] mu) returns (uint128[]){
return reduce(square(a),p,mu);
}
//http://cacr.uwaterloo.ca/hac/about/chap14.pdf 14.42
function reduce(uint128[] x,uint128[] p, uint128[] mu) returns (uint128[]) {
uint k=p.length;
uint128[] memory q2=multiply(x,(k-1),x.length,mu);
uint128[] memory resultArr=new uint128[] (k+1);
multiply(q2,k+1,q2.length,p,resultArr);
subtract(x,k+1,resultArr,resultArr);
if(compare(resultArr,p)>0){
subtract(resultArr,resultArr.length,p,resultArr);
}
return resultArr;
}
function multiply(uint128[] a,uint128[] b) returns (uint128[]){
uint128[] memory result=new uint128[](a.length+b.length);
for (uint i=0;i<a.length;++i){
uint128 carry=0;
uint256 ai=uint256(a[i]);
for (uint j =0;j<b.length;++j){
uint256 temp=carry+ai*b[j]+result[i+j];
result[i+j]=uint128(temp);
carry=uint128(temp>>128);
}
result[i+b.length]=carry;
}
return result;
}
function multiply(uint128[] a, uint aStart,uint aEnd,uint128[] b) returns (uint128[]){
uint128[] memory result=new uint128[](aEnd-aStart+b.length);
for (uint i=aStart;i<aEnd;++i){
uint128 carry=0;
uint256 ai=uint256(a[i]);
for (uint j =0;j<b.length;++j){
uint resultIndex=i+j-aStart;
uint256 temp=carry+ai*b[j]+result[resultIndex];
result[resultIndex]=uint128(temp);
carry=uint128(temp>>128);
}
result[i+b.length-aStart]=carry;
}
return result;
}
function multiply(uint128[] a, uint aStart,uint aEnd,uint128[] b,uint128[] result) returns (uint128[]){
for (uint i=aStart;i<aEnd;++i){
uint128 carry=0;
uint256 ai=uint256(a[i]);
for (uint j =0;j<b.length;++j){
uint resultIndex=i+j-aStart;
if(resultIndex<result.length){
uint256 temp=carry+ai*b[j]+result[resultIndex];
result[resultIndex]=uint128(temp);
carry=uint128(temp>>128);
}
}
uint finalIndex=i+b.length-aStart;
if(finalIndex<result.length){
result[finalIndex]=carry;
}
}
}
function square(uint128[] a) returns (uint128[]){
return multiply(a,a);
}
function compare(uint128[] a, uint128[] b) returns (int8){
uint aLength=a.length;
uint bLength=b.length;
uint maxLength=aLength > bLength? aLength : bLength;
for(uint i =maxLength-1;i>=0;--i){
uint128 aVal=i>=aLength?0:a[i];
uint128 bVal=i>=bLength?0:b[i];
if(aVal>bVal){
return 1;
}
if(bVal > aVal){
return -1;
}
}
return 0;
}
//a>b
function subtract(uint128[] a, uint128[] b) returns (uint128[]){
uint128[] memory result=new uint128[](a.length);
uint8 carry=0;
for(uint i=0;i<a.length;++i){
int bVal=i>=b.length?0:b[i];
int resultBuf=a[i]-bVal-carry;
result[i]=uint128(resultBuf);
if(resultBuf<0){
carry=1;
}else{
carry=0;
}
}
return result;
}
//a>b
function subtract(uint128[] a,uint aLength, uint128[] b) returns (uint128[]){
uint128[] memory result=new uint128[](aLength);
uint8 carry=0;
for(uint i=0;i<aLength;++i){
int bVal=i>=b.length?0:b[i];
int resultBuf=a[i]-bVal-carry;
result[i]=uint128(resultBuf);
if(resultBuf<0){
carry=1;
}else{
carry=0;
}
}
return result;
}
//a>b
function subtract(uint128[] a,uint aLength, uint128[] b,uint128[] result) returns (uint128[]){
uint8 carry=0;
for(uint i=0;i<aLength;++i){
int bVal=i>=b.length?0:b[i];
int resultBuf=a[i]-bVal-carry;
result[i]=uint128(resultBuf);
if(resultBuf<0){
carry=1;
}else{
carry=0;
}
}
return result;
}
}
Raw
RefereeContract
pragma solidity ^0.4.7;
import "SequentialHashing";
contract Referee is HashVerifier{
//Should be power of 2
uint8 constant NUM_CHECKPOINTS=1<<3;
//Has to be even
uint8 constant NUM_ROUNDS=10;
uint constant CHALLENGE_RESPONSE_TIMEOUT=5 minutes;
uint constant CHALLENGE_PERIOD=2 hours;
struct ChallengeState{
bool initialized;
bytes32 firstCheckpoint;
bytes32 lastCheckpoint;
bytes32[7] checkpoints;
uint8 round;
uint lastChallenge;
}
bytes32 private challenge;
//This stores the challenge and the beacon;
//TODO: Protect this and beacon getter
ChallengeState private initialState;
mapping(address => ChallengeState) private challenges;
address private prover;
function Referee(){
challenge= block.blockhash(block.number-1);
//Fix for easier debuging
}
function submitBeacon(bytes32 _beacon, bytes32[7] _checkpoints) noBeacon{
initialState=ChallengeState(true,challenge,_beacon,_checkpoints,0,now);
prover=msg.sender;
}
function postChallenge(uint8 prevIndex,bytes32[7] _checkpoints,address challenger) beaconExists inChallengePeriod indexInBounds(prevIndex) {
ChallengeState memory state=challenges[challenger];
if(state.initialized==false){
state=ChallengeState(true,initialState.firstCheckpoint,initialState.lastCheckpoint,initialState.checkpoints,0,now);
}
if(state.round>=NUM_ROUNDS){
throw;
}
if(state.round%2==0&&msg.sender!=challenger){
throw;
}
if(state.round%2==1&&msg.sender!=prover){
throw;
}
if(prevIndex>0){
state.firstCheckpoint=state.checkpoints[prevIndex-1];
}
if(prevIndex<NUM_CHECKPOINTS-2){
state.lastCheckpoint=state.checkpoints[prevIndex];
}
state.checkpoints=_checkpoints;
++state.round;
state.lastChallenge=now;
challenges[challenger]=state;
}
function callTimeout(){
ChallengeState state=challenges[msg.sender];
if(state.round%2!=1){
throw;
}
if(now-state.lastChallenge>CHALLENGE_RESPONSE_TIMEOUT){
selfdestruct(msg.sender);
}
}
function finalChallenge(uint8 prevIndex) inChallengePeriod indexInBounds(prevIndex) returns (bool){
address challenger=msg.sender;
ChallengeState state=challenges[challenger];
if(state.round!=NUM_ROUNDS){
throw;
}
bytes32 claimedResult;
bytes32 computedResult;
bytes32 start;
if(prevIndex==0){
start=state.firstCheckpoint;
claimedResult=state.checkpoints[0];
}else if(prevIndex==NUM_CHECKPOINTS-2){
start=state.checkpoints[prevIndex-1];
claimedResult=state.lastCheckpoint;
}else{
start=state.checkpoints[prevIndex-1];
claimedResult=state.checkpoints[prevIndex];
}
bool verified=verify(start,claimedResult);
if(!verified){
selfdestruct(challenger);
}else{
delete challenges[challenger];
}
return verified;
}
function getChallenge() returns (bytes32){
return challenge;
}
function getBeacon() returns (bytes32){
return initialState.lastCheckpoint;
}
function getCheckpoints() returns (bytes32[7]){
return challenges[msg.sender].checkpoints;
}
function getFirstCheckpoint() returns (bytes32){
return challenges[msg.sender].firstCheckpoint;
}
function getLastCheckpoint() returns (bytes32){
return challenges[msg.sender].lastCheckpoint;
}
//Modifiers
modifier noBeacon(){
if(initialState.initialized==true){
throw;
}
_;
}
modifier beaconExists() {
if(initialState.initialized==false){
throw;
}
_;
}
modifier indexInBounds(uint8 prevIndex){
if(prevIndex>=NUM_CHECKPOINTS-1){
throw;
}
_;
}
modifier inChallengePeriod(){
if(now>initialState.lastChallenge+CHALLENGE_PERIOD){
throw;
}
_;
}
}
Raw
RSASquaring
import "https://github.com/axic/ethereum-rsa/rsaverify.sol";
//This should work (and probably is quick) if RSAVerify does become a precompiled contract
contract Test {
bytes prime="0x00a2904487e49592a42890964f2a758ce58af027ba0fd68f6c9a5684a2d963b6af4127b91e0b9c084aeb0cd9cc81328433d8ed178e4c696c199e2a3d899f85b02f2d16023b57d06ada7e7ab46b49978063d739c9697b3b119783ba870132ac5bba37ccbd99b99a8188fcae7ccce24525dc03c50f78c7a043cc6c2589c90b3f717851d7de5f62d0eafe81aba1287d8e674750090e521589187613518892603dcb9ff37051616805e6fae9ff6185d8037711f2a8cf37db8ccad45fa4410d0e354a029268b22192fabaa45d0b6c72314682143f7e14603a40a9e314644b69cba10910dc651b5fa559a7df46a7758331b24e4ae1a050d280420a49b6119b6e61827749";
function test(bytes root,bytes seed) returns (bool) {
return RSAVerify.rsaverify(seed, prime, 2, root, 1);
}
}
Raw
SequentialFunction
pragma solidity ^0.4.7;
contract SequentialFunction{
function verify(bytes32 x,bytes32 y) returns (bool);
}
Raw
SequentialHashing
pragma solidity ^0.4.7;
import "SequentialFunction";
contract HashVerifier is SequentialFunction{
function verify(bytes32 x,bytes32 y)returns (bool){
return hash(x)==y;
}
//Unrolled loop for speed improvements (48 gas per hash)
//Returns keccack^1024(x)
function hash(bytes32 x) returns (bytes32 r){
assembly{
let nextFree:=mload(0x40)
mstore(0x40,add(nextFree,0x20))
mstore(nextFree,x)
let n:=0
loop:
jumpi(loopend, eq(n, 10))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
n := add(n, 1)
jump(loop)
loopend:
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
mstore(nextFree,sha3(nextFree,0x20))
r:= sha3(nextFree,0x20)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment