Lingkun's Small House

Youth is not a time of life, it is a state of mind.


  • Home

  • Archives

LearnSolidity4 — CrowdSensing

Posted on 2018-03-24 | In Learn Solidity

Solidity学习笔记(4) — Crowdsensing

作者:孔令坤,转载请注明出处

在本文中,我开发了一个使用区块链来做群智感知系统的智能合约。其中,区块链代替了传统的集中式第三方机构,给用户们提供了一个更加安全,更加经济的发布群智感知任务的平台。

1.背景介绍

群智感知即利用目前普及化的移动设备有效地收集数据,在近年来已经引起了人们的广泛兴趣并出现了大量的工程应用。

然而,大多数现有的群智感知系统都依赖于中央服务器,这些服务器受传统基于信任模型的缺陷的影响,容易发生单点故障和隐私泄露的问题。另外,在考虑到恶意用户存在的情况下,这些系统容易遭受分布式拒绝服务(DDoS)和Sybil攻击。此外,群智感知平台收取的高额服务费可能会阻碍这项技术的发展。如何解决这些潜在问题仍然是一个巨大的挑战。

本文提出了一种基于区块链的群智感知应用方案。我们希望借助区块链的科技,将存储、处理数据的数据平台去中心化,提供一种更加安全,并且更加经济的选择。具体而言,我们希望能借助区块链系统,让矿工代替中心化的数据管理平台,并帮助处理来自数据提供方的信息,从而确保用户信息的安全性。同时,由于这个时候数据需求者仅仅需要给矿工和用户提供相应的挖矿和上传数据的报酬,不需经过中心化数据管理平台,从而在经济上有了更多的选择,也避免了由于中心化数据管理平台的垄断而被索取高额的数据提供费用。

2.具体实现

在实际的工程应用中,我们使用智能合约(smart contract)开发出了基于区块链的群智感知系统的框架。

如上图所示,图中的数字标号简单记录了在一次大数据分享任务中整个框架的流程顺序。其中流程标号2*代表此流程2*可以与流程2同步进行,而流程标号x表示此流程可以在流程2后的任意时刻执行。另外,图中的实线代表了必然会发生的流程,而虚线代表了可能在框架流程执行中并不会被执行的流程。

3.核心代码

本文利用一个感知学校wifi信号强度的例子来介绍如何开发类似的群智感知智能合约。

需要注意的是,这里我对核心代码进行了大量的化简,比如忽略了数据提供方对原始数据的加密以及数据需求方广播程序的代码。所以,以下的代码仅仅是一个帮助学习smart contract的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
pragma solidity ^0.4.21;

contract SensingWifi{
uint public rewardUnit;
uint public rewardNum;
uint public dataCount;
bytes32 public wifiName;
address public requester;
enum State {Uncreated, Created, Inactive}
State public state;

mapping(bytes32 => string) dataStatuses; // Either '' or 'Committed'

modifier condition(bool _condition) {
require(_condition);
_;
}

modifier onlyRequester() {
require(msg.sender == requester);
_;
}

modifier inState(State _state) {
require(state == _state);
_;
}

event Aborted();
event TaskInited();
event DataCommited(bytes32 l, bytes32 w, int s);
event TaskDone();

// The requester initiates the task.
// He needs to set the value of rewards for each sensing data,
// as well as the maximum number of data he requires.
function initTask(uint _rewardUnit, uint _rewardNum, bytes32 _wifiName)
public
inState(State.Uncreated)
condition(msg.value >= _rewardUnit * _rewardNum)
payable
{
requester = msg.sender;
rewardUnit = _rewardUnit; // wei
rewardNum = _rewardNum;
wifiName = _wifiName;
state = State.Created;
emit TaskInited();

}

// Abort the Task and reclaim the ether,
// Can only be called by the requester.
function abort()
public
onlyRequester
inState(State.Created)
{
require(dataCount <= rewardNum);
state = State.Inactive;
requester.transfer(this.balance);
emit Aborted();
}

// The worker undertakes the task by obtaining and sending his sensing data,
// such as {"Student Dorm 13", "SJTU", -51}
function commitTask(bytes32 _location, bytes32 _wifiName, int _signalDegree)
public
inState(State.Created)
{
require(dataCount < rewardNum);
bytes memory sensingDataCommit = bytes(dataStatuses[_location]);
// The requester wants to get data from different location.
require(sensingDataCommit.length == 0);

// Make sure that the wifi signal sensed is exactly what requester wants.
require(wifiName == _wifiName);

// The theoretical maximum value of signal strength is -30 dBm.
require(_signalDegree < -30);

dataStatuses[_location] = "Committed";

dataCount += 1;
if(dataCount == rewardNum){
state = State.Inactive;
requester.transfer(this.balance);
emit TaskDone();
}
msg.sender.transfer(rewardUnit);

// The requster collects sensing data by
// listening the log info of DataCommited.
emit DataCommited(_location, _wifiName, _signalDegree);
}
}

Hanoi in Assembly x86 (NASM)

Posted on 2018-02-06

Hanoi in NASM — 如何正确学习汇编

曾经的嵌入式课程令人头皮发麻,教材是一本老师们随意拼凑在一起的书,里面的东西毫无学习的逻辑可言。汇编语言的教学更加令人无语,老师说,你们看看书,自己多写写就会了(但是书写的很差,也不适合初学者上手)。

然而最近在看Paul Carter教授编写的PC Assembly Language一书,我猛然悟道了,之前许多一知半解的知识在书中都得到了比较完善的讲解。所以大家学习汇编也可以多看看他写的这本书,确实会对大家理解计算机比较偏底层的知识非常有帮助,毕竟汇编可以说是离硬件最近的一门语言。而且在学完汇编后,你会发现你对C语言的理解也更上了一个台阶。

曾经在嵌入式课上,老师建议我们可以用汇编写一下汉诺塔,但是当时我对汇编中函数调用时寄存器的分配,存储空间的操作一头雾水,并没能自己独立写好。现在,我回过头来重新写这个作业(曾经的bonus作业),也算是给自己补了补课。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
; int main(int argc, const char * argv[]) {  
; printf("Please input the number of plates: ");
; int n;
; scanf("%d",&n);
; hanoi(n, 1, 2, 3);
; return 0;
; }

%include "asm_io.inc"

; init data
segment .data
prompt1 db "Please input the number of plates: ", 0

; uninit data
segment .bss

segment .text
GLOBAL asm_main
asm_main:
enter 0, 0 ; start to run
pusha

mov eax, prompt1
call print_string
call read_int
call print_nl

push eax
mov dword ebx, 1
push ebx
mov dword ecx, 2
push ecx
mov dword edx, 3
push edx

call hanoi

add esp, 16

popa
mov eax, 0; back to C/C++
leave
ret


; void hanoi(int n,int a,int b,int c)
; {
; if(n==1)
; {
; printf: a --> c \n
; }
; else{
; hanoi(n-1,a, c, b);
; printf: a --> c \n
; hanoi(n-1, b, a, c);
; }
; }

segment .data
arrow db " --> ", 0

; ------- High
; n
; -------
; plate 1
; -------
; plate 2
; -------
; plate 3
; ------- Low

segment .text
GLOBAL hanoi
hanoi:
enter 16 , 0 ; 4 parameters: n, plate1, plate2, plate3

mov eax, [ebp + 20]
cmp eax, 1
jne elseif
mov eax, [ebp + 16] ; print plate1 --> plate3
call print_int
mov eax, arrow
call print_string
mov eax, [ebp + 8]
call print_int
call print_nl
jmp quit

elseif:
mov eax, [ebp + 20] ; hanoi(n-1, p1, p3, p2)
dec eax
push eax
mov ebx, [ebp + 16]
push ebx
mov ecx, [ebp + 8]
push ecx
mov edx, [ebp + 12]
push edx
call hanoi
add esp, 16


mov eax, [ebp + 16] ; print plate1 --> plate3
call print_int
mov eax, arrow
call print_string
mov eax, [ebp + 8]
call print_int
call print_nl

mov eax, [ebp + 20] ; hanoi(n-1, p2, p1, p3)
dec eax
push eax
mov ebx, [ebp + 12]
push ebx
mov ecx, [ebp + 16]
push ecx
mov edx, [ebp + 8]
push edx
call hanoi
add esp, 16
jmp quit
quit:
leave
ret

更加完整的文档我放到了我自己的github上(包括如何编译的说明),大家如果有兴趣可以自行下载。

Needleman–Wunsch algorithm

Posted on 2018-02-06

Introduction

The Needleman–Wunsch algorithm is an algorithm used in bioinformatics to align protein or nucleotide sequences. It was one of the first applications of dynamic programming to compare biological sequences.

In this article, we try to use Needleman-Wunsch algorithm to find the minimum mismatch between two different DNA sequences.

Definition of Mismatches

Here we have two different DNA sequences, i.e., S1 and S2, where

S1 = "GCATGCU",

S2 = "GCTTAGCU".

One solution to match these two DNA sequences is listed as below:

S1* = "GCAT-GCU",

S2* = "GCTTAGCU",

in which - is called as “gap”, i.e., in this position the DNA is supposed to be unknown.

Match: The two letters are the same, except both two letters are gapped.

Mismatch: The two letters are differential or both two letters are gapped.

By above definition, the solution we find for matching S1 and S2 has two mismatches — T & A and - & A.

Codes for finding minimum mismatches

Here I list the python code for finding minimum number of mismatches between two DNA sequences. The insights of codes below can be viewed by supplemental documents here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
'''
input:
S1 = ['A','B','C','D']
S2 = ['A','B','C']
output:
1
print info:
New S1 is: ABCD
New S2 is: ABC-
'''
def MinMismatch(S1, S2):
'''
First of all, we construct matrix for counting maximum length of common subsequence.
'''
l1, l2 = len(S1), len(S2)
matrix = [[0 for j in range(l2+1)] for i in range(l1+1)]

for i in range(1, l1+1):
for j in range(1, l2+1):
if S1[i-1] == S2[j-1]:
matrix[i][j] = matrix[i-1][j-1] + 1
else:
matrix[i][j] = max(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j])
'''
Dynamic programming. Tracing back the matrix and construct two DNA sequences with gaps.
We saved the restructured sequences into A (originally S1) and B (originally S2).
'''
left_up, up, left = 0, 1, 2
i, j = l1, l2
A, B = [], []
while (i,j) != (0,0):
if i == 0:
i, j = i, j-1
flag = left
elif j == 0:
i, j = i-1, j
flag = up
elif S1[i-1] == S2[j-1] or matrix[i-1][j-1] == max(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]):
i, j, flag = i-1, j-1, left_up
elif matrix[i-1][j] == max(matrix[i-1][j-1], matrix[i][j-1], matrix[i-1][j]):
i, j, flag = i-1, j, up
else:
i, j, flag = i, j-1, left

if flag == left_up:
A.append(S1[i])
B.append(S2[j])
elif flag == up:
A.append(S1[i])
B.append('-')
else:
A.append('-')
B.append(S2[j])
'''
Print info about new DNA sequences with minimum number of mismatches.
'''
A.reverse()
B.reverse()
printA, printB = '',''
for i in range(len(A)):
printA += A[i]
for i in range(len(B)):
printB += B[i]
print('New S1 is: '+ printA)
print('New S2 is: '+ printB)
'''
Calculate the number of mismatches.
'''
mismatch = 0
for i in range(len(A)):
if A[i] != B[i] or (A[i] == '-' and B[i] == '-'):
mismatch += 1
return mismatch

if __name__=="__main__":
S1 = list("GGATCGA")
S2 = list("GAATTCAGTTA")
print(MinMismatch(S1,S2))

Micropayment

Posted on 2018-01-08 | In Learn Solidity

Smart Contract: Micropayment

作者:孔令坤,转载请注明出处

在Solidity的官网上,Micropayment Channel的例子目前暂待开发。于是我决定自己写一个Micropayment的合约。

Background

什么是Micropayment?

假设你是一个中国移动用户,正在拨打国际长途电话,然后中国移动会根据你的通话时长来进行收费,每分钟1元钱,并按照满分钟计算(比如打了2分钟20秒,记为3分钟)。这个时候,我们可以通过一个智能合约,进行你与中国移动之间的付款。显然,如果你每分钟都要给中国移动付钱,那么这样就太麻烦了,相当于你每打一分钟电话就要再掏出一分钟的话费。这个时候,我们可以用所谓的Micropayment,来进行一次性的费用支付。

如上图所示,Alice 通过智能合约向Bob(服务提供者)进行支付。首先,Alice往合约里存100单位的钱,然后获得Bob提供的服务。此后,智能合约开始计算时长。当Alice停止服务后,他将调用合约的函数,进行服务的停止。然后合约会自动结算Bob的服务费,然后将存在合约里的钱分别给到Alice和Bob手里。

同时,为了防止Alice一直不停止服务,Bob拿不到应该拿到的服务费用,我们应当在合约中提供让Bob终止合约,并拿到所有的钱的选项。这个选项的判定条件应当是Alice已经用完了所有服务的时长。

Code 1:

以下是第一段代码,需要注意的是这里我在code中并没有像传统的Micropayment Channel一样使用multi-sig。但是事实上,由于remix特殊的编程环境,user需要在service provider发起的合约的地址下At Address进行startService函数的使用。因此,其实从某种一样上,这个合约里也存在着用户与服务提供方对协议的共识。此代码remix亲测可用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
pragma solidity ^0.4.11;

contract Micropayment{
uint public value;
uint public feePerMinute; // the fee is counted by wei
uint public startTime;
uint public endTime;
address public serviceProvider;
address public user;

function Micropayment(uint fee) public {
require(fee > 0);
serviceProvider = msg.sender;
feePerMinute = fee;
}

modifier condition(bool _condition) {
require(_condition);
_;
}

modifier onlyProvider() {
require(msg.sender == serviceProvider);
_;
}

modifier onlyUser() {
require(msg.sender == user);
_;
}

event ServiceStarted();
event ServiceEnded();
event ForceEnd();

/// Force end the Micropayment (the service provider),
/// and get paid,
/// when user has run out his time.
function forcePay()
public
onlyProvider
{
require(now >= endTime);
ForceEnd();
serviceProvider.transfer(this.balance);
}

/// Start service as user.
/// Give a expected service time.
function startService(uint eT) // minutes
public
condition(msg.value >= feePerMinute * eT)
payable
{
ServiceStarted();
user = msg.sender;
startTime = now;
endTime = now + eT * 1 minutes;
value = msg.value;
}

/// End the service (the user).
/// Pay bill to service provider according to using time.
function endService()
public
onlyUser
{
require(now < endTime);
uint usingTime = (now - startTime) / 60 + 1;
uint bill = usingTime * feePerMinute;
user.transfer(value - bill);
serviceProvider.transfer(this.balance);
ServiceEnded();
}
}

也可以在我的github中找到:https://github.com/Ohyoukillkenny/Learn-Solidity

Potential Improvement

目前的micropayment合约有一个比较伤的缺点,就是无法防止service的提供者, i.e., 中国移动耍赖。比如线下的时候明明还没有到服务截止时间,就停止了服务。从合约的角度来讲,目前无法杜绝这种情况的发生。所以和之前的remote purchase合约一样,需要线下有第三方的监管。

Code 2:

在与他人的交流中,有一位大佬觉得Code 1中的合约其实不是传统意义上的Micropayment Channel,所以这里我又写了一段代码,加入了传统的multi-sig,使得合约更加贴近通常意义上的Micropayment Channel。

这里我假设Bob, i.e., worker是给Alice, i.e., moneyProvider干活的人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
pragma solidity ^0.4.11;

contract Channel {

address public moneyProvider;
address public worker;
uint public startTime;
uint public timeOut;
mapping (bytes32 => address) signatures;

function Channel(address to, uint t) payable {
worker = to;
moneyProvider = msg.sender;
startTime = now;
timeOut = t;
}
// this function can be both called by moneyProvider and worker,
// we use sha3 as hash function in this case.
function CloseChannel(bytes32 h, uint8 v, bytes32 r, bytes32 s, uint value){
address signer;
bytes32 proof;
// get signer from signature
signer = ecrecover(h, v, r, s);
// signature is invalid, throw
require (signer == moneyProvider || signer == worker);
proof = sha3(this, value);
// signature also needs to match the data provided
require (proof == h);
if (signatures[proof] == 0)
signatures[proof] = signer;
else if (signatures[proof] != signer){
// channel completed, both signatures provided
worker.transfer(value);
selfdestruct(moneyProvider);
}
}
// this function is called by moneyProvider, when worker is malicious.
function moneyBack(){
require (startTime + timeOut > now && msg.sender == moneyProvider);
selfdestruct(moneyProvider);
}
}

总体而言,传统的写法对后端执行的要求更多,需要涉及哈希和签名的处理,另外支付的金额也是在后台进行计算的。此外由于有比较长的数据包要被smart contract多次处理,所以会消耗相对而言多得多的gas。

另外在code 2的逻辑中,同样无法避免的是moneyProvider耍赖的情况,因为最后是由moneyProvider决定最后给worker发多少钱, i.e., value,假如moneyProvider发的钱和之前说好的不一样,合约也无法对其进行制裁。所以我们仍然需要第三方进行监管。但是由于应当支付的钱不断被worker用closeChannel函数作为transaction写到block里面去,所以相对而言,最后moneyProvider要发多少是被记录下来的,是有迹可循的。

NULL in Solidity

Posted on 2018-01-07 | In Learn Solidity

Inexistent NULL in Solidity

作者:孔令坤,转载请注明出处

在Solidity中,并没有Null值的存在。所有的变量在初始化后都会被默认为0值。这导致我们在写代码的时候需要多加注意。

比如之前我遇到的enum:

1
2
enum State { Created, Locked, Inactive }
// Created = 0, Locked = 1, Inactive = 2

之后,代码在没有对myState变量进行赋值的情况下,直接判断:

1
require(myState == Created.Created);

所以这个时系统断定判断通过,而且并不会报错。

那么,如何判断mapping中是否某个键是否”为空”呢?

比较标准的做法是建立一个专门和value相关的结构体,用一个布尔型变量来看是否这个key所对应的value被赋过值,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
library Library {
struct data {
uint val;
bool isValue;
}
}
contract myContract{
using Library for Library.data;
mapping(address => Library.data) cluster;
function ifExist(address id) returns(bool){
if(cluster[id].isValue) return true;
return flase;
}
function addCluster(address id){
if(cluster[id].isValue) throw; // duplicate key
// add ...
cluster[id].isValue = true;
}
//...
}

此外,我们也可以简单的来看一下value所对应的length来判断这个值是否被赋值过(零值无法判断!):

1
2
3
4
mapping(address => uint) public deposits;
if(deposits[msg.sender].length == 0){
// deposit[msg.sender] is empty, do your thing
}

如果我们不用判断某个变量是否为赋过值后的零值时,我建议用第二种通过length来判断的方法,因为后者将大大减少合约gas的消耗。

1234

Lingkun Kong

17 posts
4 categories
4 tags
© 2018 Lingkun Kong
Powered by Hexo v3.7.1
|
Theme — NexT.Muse v6.1.0